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

[Andreas Hülsing <[e-mail]>]

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

Best,

Andreas

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] https://saltpack.org/encryption-format-v2 (scroll down to Payload
> Packets)
>
> Best,
>
> Neil
>
>> On 27 Apr 2020, at 16:19, Dan Brown <[e-mail]
>> <mailto:[e-mail]>> wrote:
>>
>> Hi Neil,
>> I too have encountered this interesting and well-known (perhaps not
>> widely-known) problem.
>> See https://eprint.iacr.org/2005/056.pdf. (Section 5).
>> See https://tools.ietf.org/html/rfc3278#section-4.1.2 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 <[e-mail]
>> <mailto:[e-mail]>> *On Behalf Of *Neil Madden
>> *Sent:* Monday, April 27, 2020 10:12 AM
>> *To:* CFRG <[e-mail] <mailto:[e-mail]>>
>> *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]: https://tools.ietf.org/html/draft-madden-jose-ecdh-1pu-03
>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Dmadden-2Djose-2Decdh-2D1pu-2D03&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=mf6j6fOClApRsArWE9wqI1rEGUVkfxZ0aXWmn35nK_c&m=pABr2aBl1c_ofW8vypgq6rz4tGVZWkxu0IU_RSNb_L4&s=E_agQvNgeBlLsyPF6xyJ1TFQLBAJsGTY1FJf7EK3iqs&e=>
>>  
>> 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
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg