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

Andreas Hülsing <> Wed, 06 May 2020 09:51 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id C659E3A0895 for <>; Wed, 6 May 2020 02:51:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.798
X-Spam-Status: No, score=-1.798 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id kBzriKk5BV6C for <>; Wed, 6 May 2020 02:51:09 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 86E833A07EA for <>; Wed, 6 May 2020 02:51:09 -0700 (PDT)
Received: from ([]) by with esmtpsa (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.89_1) (envelope-from <>) id 1jWGhm-0006AJ-7F for; Wed, 06 May 2020 11:51:06 +0200
Received: from [] (helo=[]) by with esmtpsa (TLSv1.3:TLS_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from <>) id 1jWGhm-0005HK-34 for; Wed, 06 May 2020 11:51:06 +0200
References: <> <> <>
From: Andreas Hülsing <>
Message-ID: <>
Date: Wed, 06 May 2020 11:51:05 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: multipart/alternative; boundary="------------684E1B07199259BB4F8645D5"
Content-Language: en-US
X-Virus-Scanned: Clear (ClamAV 0.102.2/25803/Tue May 5 14:19:25 2020)
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: Wed, 06 May 2020 09:51:13 -0000

I might miss something, but you also require collision resistance for
the KDF in this case (which is non-standard afaik), right?



On 28-04-2020 14:30, 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