Re: [Cfrg] Multi-recipient public key authenticated encryption

Paul Grubbs <> Thu, 07 May 2020 20:39 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id C4BE33A0D6F for <>; Thu, 7 May 2020 13:39:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 9qrTN9ZvTlta for <>; Thu, 7 May 2020 13:39:51 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::82b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 585403A0D6B for <>; Thu, 7 May 2020 13:39:50 -0700 (PDT)
Received: by with SMTP id x8so1694952qtr.2 for <>; Thu, 07 May 2020 13:39:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=g.20171207; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=huZOETTH+PaSTOJ57t3yoCfblbcHHeC17B4mxzNJCd4=; b=gbUr3G9mFoFcgvfozDMJdjbQL6WU8IgT97PsJ+D9/WAKn1SQyZhTJxxHx+GdumXTFQ DqelB5CKteRSKxUjDNn/BMaCpibtV7N2ks7aXJUlSxR4EV6Q9VB63AZDQrNuqtwYC40C L30qczDp0vjj+fV8YGtZk43XY9823gp9JcNKw6jPc37g/yOw7vc7flHOerqMp06neh/4 9IAZzF9TlptDUYQQhZqObN3ols89OOoygjgqsN3v4rRJJkqerw3DU0SskqLYrffGmF9x KcShwNyLzKrmPcpwwhG1PHnj7Kdb5CXn7qZP3RW7vdRcMo0JtR9inFh7JoftkgwsuP1K pMzQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=huZOETTH+PaSTOJ57t3yoCfblbcHHeC17B4mxzNJCd4=; b=mnPY7nSSDen4g3eH6wJ6Rkb+Ux5WkwM3jm3KUbzh8bTmOFBy5F4S6aAgRRILy7Y4W6 WNLiJx8IXYHmoRb8JMW/vwBMbq41qbqjkgjH+33uwE6NVnB6JNYXhgMgv1nA+4ePOG0n rnTf31vZgZvezaCQUAtA8uonO+VI1QeUhf4PyrtGMuEe/H7Ruxa6f7aP8wc9xP+GdnCK 7TagbsMWFD8EuntfBRkdMU76104jyyyFKJPROKJF9lOi/8hrptoRqKY09F2nPwZabMoL arYmH1SxDIFCjfexHW5s6KLC26L89i6C+LKWgPAGvyc+6JxB6bXhEZ+AEBD3pHSOIrBN oXAQ==
X-Gm-Message-State: AGi0PuZt+pzigTAOj1dPgY7EoGhcmBBlOzMkBNAd1vpkz8+QbaC+iP/1 y1Z/g/HuZtaTTXHtxpm52+CyLYIesnjTjK3VefeXDw==
X-Google-Smtp-Source: APiQypJiD3CMfR45ZDXcU32xgEK+3saGj28m4Nfko0SN3J3J9r3aJgMbTwv/Le0YStvT1ZW/Me/VyJWUIlzlPR5t5+8=
X-Received: by 2002:ac8:1387:: with SMTP id h7mr1949475qtj.229.1588883989573; Thu, 07 May 2020 13:39:49 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <>
In-Reply-To: <>
From: Paul Grubbs <>
Date: Thu, 07 May 2020 16:39:38 -0400
Message-ID: <>
To: Neil Madden <>
Cc: Dan Brown <>, CFRG <>
Content-Type: multipart/alternative; boundary="000000000000c9cde005a514e122"
Archived-At: <>
Subject: Re: [Cfrg] Multi-recipient public key authenticated encryption
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 07 May 2020 20:39:55 -0000

Yes, as long as keying is done correctly (the CBC and HMAC keys must be
derived from a single parent key) then CBC+HMAC is compactly committing.

On Thu, May 7, 2020 at 10:26 AM Neil Madden <> wrote:

> That is interesting, thanks. JOSE does also support AES-CBC + HMAC (EtM),
> so it may perhaps then be simpler to forbid the use of GCM for
> multi-recipient messages in this spec and save myself a lot of trouble. It
> seems from your papers that CBC+HMAC is one of the schemes you looked at
> and it would be compactly committing, so this is fortunate.
> On 7 May 2020, at 14:39, wrote:
> Oh ok, it’s too bad JOSE only supports GCM. You should be careful with
> using plain GCM in these multi-receiver settings - because it’s
> non-committing, it’s possible to craft a single ciphertext that different
> receivers decrypt to different plaintexts.
> On May 7, 2020, at 7:28 AM, Neil Madden <> wrote:
> Apologies, I forgot to respond to this. I think the ccAE approach is a
> nice way of solving the problem. Unfortunately, JOSE allows specifying the
> key exchange algorithm and AEAD cipher entirely independently so I have to
> have a solution that works with the AES-GCM based AEADs that are already
> part of the standard. But I will read these papers closely, because I do
> think the security notions are very similar to what I’m trying to achieve.
> — Neil
> On 28 Apr 2020, at 16:14, Paul Grubbs <> wrote:
> I think you can get away without the additional hash of the ciphertext
> entirely if you use a compactly committing AEAD (ccAE) scheme [1]. A ccAE
> has a two-part ciphertext C = (C1, C2) with the property that C2 is a
> binding commitment to the plaintext and key. At least intuitively, then,
> using C2 in the KDF prevents a receiver from modifying the message. (This
> is morally similar to including the MAC tag in the KDF, as suggested, but
> sidesteps questions about MAC security and may be faster if optimal-rate
> schemes like HFC [2] are used.) I haven't analyzed this construction
> formally, though, so take this advice with a bit of salt.
> [1]
> [2]
> On Tue, Apr 28, 2020 at 8:30 AM Neil Madden <>
> wrote:
>> Thanks, section 5 of the eprint is very useful. In that you discuss the
>> solution of including the MAC tag in the KDF and you say that this requires
>> collision resistance of the MAC, where I had previously assumed only 2nd
>> preimage resistance would be enough. As I understand it, the potential
>> attack is that if Charlie has access to an Alice-oracle by which he can get
>> Alice to authenticate arbitrary messages to himself and Bob then he can use
>> this to perform a collision search to find two messages with the same MAC
>> tag (if the MAC is not collision resistant).
>> I think this active attack would also apply to my proposed solution using
>> a hash of the authenticated ciphertext as input to the KDF. So my assertion
>> that 2nd preimage is enough is only valid for passive attacks, and full
>> collision resistance would be needed in general. That also means that if I
>> do pick SHA-256 to be consistent with existing use in JOSE then the
>> security against such attacks would be limited to ~128 bit level. Perhaps
>> that’s an incentive for me to also change the KDF in the scheme from JOSE’s
>> existing Concat-KDF to HKDF with SHA-512.
>> I think the same attack would also apply to saltpack [1], if I understand
>> correctly? In saltpack a per-recipient MAC is calculated over a SHA-512 of
>> the ciphertext.
>> [1] (scroll down to Payload
>> Packets)
>> Best,
>> Neil
>> On 27 Apr 2020, at 16:19, Dan Brown <> wrote:
>> Hi Neil,
>> I too have encountered this interesting and well-known (perhaps not
>> widely-known) problem.
>> See (Section 5).
>> See the very short
>> “note”.
>> I forget the details of the various claimed past solutions, but will try
>> to remember, maybe in a couple weeks.  Meanwhile, since the problem is
>> fresh in your mind, and you might try to make sense the couple of old
>> suggestions above, though I expect your knowledge has already advance past
>> this old stuff.
>> Best regards,
>> Dan
>> *From:* Cfrg <> *On Behalf Of *Neil Madden
>> *Sent:* Monday, April 27, 2020 10:12 AM
>> *To:* CFRG <>
>> *Subject:* [Cfrg] Multi-recipient public key authenticated encryption
>> Hi all,
>> I am working on an enhancement to the JOSE standards and would like
>> feedback from members of CFRG about solutions to a particular issue if any
>> of you have time.
>> In JOSE currently if you wish to create a message that has both
>> confidentiality and sender authentication using public key cryptography
>> then the only option is to both sign and then encrypt the message. This is
>> expensive because it involves multiple passes over the message and results
>> in a very bulky nested message structure with two layers of base64-encoding.
>> Given that many uses of this sign-then-encrypt pattern do not require the
>> strong security properties of signatures, I have proposed [1] a public key
>> authenticated encryption mode based on NIST’s one-pass unified model from
>> SP 800-56A. This avoids the nested structure and means that you don’t need
>> multiple cryptographic primitives. The proposed algorithm uses two ECDH key
>> agreements: one between the sender’s ephemeral private key and the
>> recipient’s long-term public key; and a second between the two parties’
>> long term keys. The two shared secrets are concatenated and passed through
>> a KDF along with some context arguments. For a single recipient this
>> achieves sender authentication (subject to replay), and the single
>> recipient case is what I am primarily concerned about.
>> (If you squint this is also roughly similar to the Noise framework “K”
>> one-way pattern, but my hands are waving quite a lot here).
>> To support multiple recipients I copied the existing pattern used in
>> JOSE’s ECDH-ES+A256KW algorithm family in which the message is encrypted
>> using a random Content Encryption Key (CEK) and then the CEK is encrypted
>> for each recipient using AES-KeyWrap with the ECDH-derived key. As I then
>> mention in the security considerations this leads to any recipient being
>> able to produce a forgery using that CEK and claim it came from the
>> original sender:
>>    When Key Agreement with Key Wrapping is used, with the same Content
>>    Encryption Key (CEK) reused for multiple recipients, any of those
>>    recipients can produce a new message that appears to come from the
>>    original sender.  The new message will be indistinguishable from a
>>    genuine message from the original sender to any of the other
>>    participants.  To avoid this attack, the content SHOULD be encrypted
>>    separately to each recipient with a unique CEK or a nested signature
>>    over the content SHOULD be used.
>> Because I am primarily interested in single-recipient use cases, this
>> seemed like an acceptable trade-off. However, I have since been contacted
>> by people who would like to use this draft for multi-recipient messages and
>> would not like to fall back on a nested signature structure.
>> An initial proposal was to solve this by simply including the MAC tag
>> from the content encryption in either the per-recipient payload (encrypted
>> using AES-KeyWrap) or as an additional context field to the KDF. But the
>> MAC is computed using the CEK that is known to all recipients, so for this
>> to be secure would require second preimage resistance of the MAC with a
>> known key, which cannot be guaranteed for JOSE because it supports content
>> encryption using AES-GCM for which second preimages can be trivially
>> computed if you know the key.
>> Assuming that a per-recipient MAC is too much overhead, an alternative
>> would be to include a collision-resistant hash of entire ciphertext (and IV
>> and associated data) in the KDF. This is unfortunate as it requires another
>> pass over the entire message when we’ve already encrypted and MACed, but it
>> appears to be a solution and at least is no more inefficient than the
>> original signed-then-encrypted approach which also needs to hash the entire
>> message.
>> So two questions:
>> 1. Is including a hash (e.g., SHA-512) of the ciphertext (assuming
>> symmetric AE) in the per-recipient KDF calculation sufficient to prevent
>> forgeries in the multi-recipient setting?
>> 2. Are there more efficient alternatives that don’t assume 2nd preimage
>> resistance of the underlying symmetric MAC?
>> [1]:
>> <>
>> Kind regards,
>> Neil Madden
>> ------------------------------
>> This transmission (including any attachments) may contain confidential
>> information, privileged material (including material protected by the
>> solicitor-client or other applicable privileges), or constitute non-public
>> information. Any use of this information by anyone other than the intended
>> recipient is prohibited. If you have received this transmission in error,
>> please immediately reply to the sender and delete this information from
>> your system. Use, dissemination, distribution, or reproduction of this
>> transmission by unintended recipients is not authorized and may be unlawful.
>> _______________________________________________
>> Cfrg mailing list