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

From: Andreas Hülsing <[email-masked]>
Date: Wed, 6 May 2020 11:51:05 +0200

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 <[email-masked]
>> <mailto:[email-masked]>> 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 <[email-masked]
>> <mailto:[email-masked]>> *On Behalf Of *Neil Madden
>> *Sent:* Monday, April 27, 2020 10:12 AM
>> *To:* CFRG <[email-masked] <mailto:[email-masked]>>
>> *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
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Neil Madden <[email-masked]>
Date: Thu, 7 May 2020 12:17:30 +0100

The proof of theorem 3 in [1] (section 5.3) models the KDF as a random oracle, which seems fairly standard, and is a stronger assumption than collision resistance, isn’t it? But I think you’re right that the collision resistance of the hash used in the KDF will be important in practice and should be mentioned.

I’m not a cryptographer so please correct me if I’m wrong.

[1]: https://eprint.iacr.org/2005/056.pdf <https://eprint.iacr.org/2005/056.pdf> 

> On 6 May 2020, at 10:51, Andreas Hülsing <[email-masked]> wrote:
> 
> I might miss something, but you also require collision resistance for the KDF in this case (which is non-standard afaik), right? 
> 
> Best,
> 
> Andreas
> 
>> 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 <https://saltpack.org/encryption-format-v2> (scroll down to Payload Packets)
>> 
>> Best,
>> 
>> Neil
>> 
>>> On 27 Apr 2020, at 16:19, Dan Brown <[email-masked] <mailto:[email-masked]>> 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 <https://eprint.iacr.org/2005/056.pdf>. (Section 5).
>>> See https://tools.ietf.org/html/rfc3278#section-4.1.2 <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 <[email-masked] <mailto:[email-masked]>> On Behalf Of Neil Madden
>>> Sent: Monday, April 27, 2020 10:12 AM
>>> To: CFRG <[email-masked] <mailto:[email-masked]>>
>>> 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:
>>>  
>>> 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.
>> 
>> 
>> 
>> [email-masked] <mailto:[email-masked]>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>

---

From: Neil Madden <[email-masked]>
Date: Thu, 7 May 2020 12:27:57 +0100

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 <[email-masked]> 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] https://eprint.iacr.org/2017/664 <https://eprint.iacr.org/2017/664>
> [2] https://eprint.iacr.org/2019/016.pdf <https://eprint.iacr.org/2019/016.pdf>
> On Tue, Apr 28, 2020 at 8:30 AM Neil Madden <[email-masked] <mailto:[email-masked]>> wrote:

---

From: [email-masked]
Date: Thu, 7 May 2020 09:39:11 -0400

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 <[email-masked]> wrote:
> 
>> [1] https://eprint.iacr.org/2017/664
>> [2] https://eprint.iacr.org/2019/016.pdf
>> 
>>> On Tue, Apr 28, 2020 at 8:30 AM Neil Madden <[email-masked]> wrote:
>>> [1] https://saltpack.org/encryption-format-v2 (scroll down to Payload Packets)
>>> 
>>> Best,
>>> 
>>> Neil
>>> 
>>>> On 27 Apr 2020, at 16:19, Dan Brown <[email-masked]> wrote:
>>>> 
>>>> Hi Neil,
>>>> See https://tools.ietf.org/html/rfc3278#section-4.1.2 the very short “note”.
>>>>  
>>>> From: Cfrg <[email-masked]> On Behalf Of Neil Madden
>>>> To: CFRG <[email-masked]>

---

From: Neil Madden <[email-masked]>
Date: Thu, 7 May 2020 15:26:47 +0100

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, [email-masked] wrote:
> 
>>> On 28 Apr 2020, at 16:14, Paul Grubbs <[email-masked] <mailto:[email-masked]>> wrote:
>>>

---

From: Paul Grubbs <[email-masked]>
Date: Thu, 7 May 2020 16:39:38 -0400

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 <[email-masked]> 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.
>
>
> 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.
>
>
> 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
>
> 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.
>
>
>> 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.
>>
>> 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 <[email-masked]> *On Behalf Of *Neil Madden
>> *To:* CFRG <[email-masked]>
>> feedback from members of CFRG about solutions to a particular issue if any
>> of you have time.
>>
>> 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).
>>
>> 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:
>>
>>
>> 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.
>>
>> 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:
>>
>> 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?
>>
>> ------------------------------
>> 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.
>>
>>

---

From: Mihir Bellare <[email-masked]>
Date: Fri, 8 May 2020 13:48:51 -0700

Public-key authenticated encryption is, I think, what in the literature is
called Signcryption.
While early formulations were single recipient, a multi-recipient
formulation is given in Section 3 of https://eprint.iacr.org/2020/224
This defines security goals of privacy, authenticity, and one that combines
them, in two forms, insider and outsider, depending on whether or not the
adversary is a key holder.
It sounds from what you say that what you want may be insider security.
The above paper does not give schemes of the form you give. My question is
that, perhaps, do the definitions capture what you want to target?

Mihir

On Mon, Apr 27, 2020 at 7:12 AM Neil Madden <[email-masked]> wrote:

> 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

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 12 May 2020 14:06:45 -0400

It is an interesting question. One approach is to look at it from a systems
angle.

Alice is going to send a message to Bob, Carol and herself. She wants each
to be able to authenticate the message but without being able to prove
Alice sent it (so can't just sign).

Let us begin by assuming we are using ECDH. This means that we are going to
need a keywrap for each recipient under the agreed key. We can generate a
unique input to a MAC at the same time.

So to put the pieces together:

Alice generates an ephemeral key {g^e, e} and an encryption session key k.
She encrypts and authenticates the message resulting in a ciphertext we can
ignore at this point and an authentication tag t.

For each recipient, Alice calculates

IKM_p = (P)^e where P is the recipient public key.
kw_p = WRAP (k, HKDF (IKM, "keywrap"))
Auth_p = HMAC(t, HKDF (IKM, "tagmac"))

So each recipient has an independent verification tag that is derived from
the same key exchange used to encrypt the data for their use.

I am sure this can't be a novel construction simply because it is so
heavily constrained. If we are going to use a MAC to authenticate data, we
must encrypt to data that is only shared bilaterally. Which means we have
to look at the output of the El-Gamal key agreement. Since we have a KDF in
there already, the approach falls out naturally.

The other detail that is commonly missed out is what to do about signing.
Do we sign then encrypt or encrypt then sign?

I use a similar approach to get around the limitations of either approach.
At the protocol level it is almost invariably essential to be able to
verify the signature before decrypting. So if we only calculate one message
digest, it has to be over the ciphertext.

We can however prove that the party who had the ability to access the
plaintext approved signature by creating a witness value as a
one-way function of (k, S, MD(C)) where S is the public signature key and
MD(C) is the message digest of the content.

That is not identical as a signature over the plaintext value but it is
close enough to defeat the application protocol level attacks that come
from assumptions made about ciphertext being signed.

This does not really affect the constructs I use in DARE very much because
I generate the encryption key for each envelope from k by means of unique
per-envelope salt value and a second KDF.

---

From: Neil Madden <[email-masked]>
Date: Mon, 18 May 2020 11:36:30 +0100

Apologies for the delay in replying. I am still digesting the paper you suggested. It is very interesting and informative, thank you.

I think the notions in section 3 do capture a lot of what I’m aiming for, but I have a question about the meaning of “non-repudiation”. On page 10 in the paragraph on “Capturing outsider authenticity” you write, regarding insider security:

"This, in particular, implies that SC assures non-repudiation, meaning that the sender cannot deny the validity of a ciphertext it sent to a recipient (since the knowledge of the recipient’s secret key does not help to produce a forgery).”

To my mind, that term (non-repudiation) is strongly linked with 3rd-party verifiability - that is, if Bob receives a message from Alice she not only can’t deny to Bob that she sent that message, but she also can’t deny it to any other 3rd party. For example, this is the definition of non-repudiation given in [1] (section 13.7.5.2):

"Suppose Alice encrypts a message m to Bob and obtains the ciphertext c. The question is, does c, together with Bob’s secret key, provide Bob with enough evidence to convince a third party that Alice actually sent the message m to Bob? We call this property non-repudiation."

In the scheme I proposed, each recipient is assured of the authenticity of a (K, T) pair where K is an ephemeral secret key used to encrypt and authenticate the message contents, and T is the (compactly committing) MAC tag for that message. Assuming that K is chosen fresh for each message, then each recipient is assured that the message came from the original sender and that no other recipient is able to produce a different message and claim it came from that sender, even though they have access to K.

But crucially, no recipient can prove to any 3rd party (who is not in the recipient list) that Alice really did send this message. Within the group of recipients something like non-repudiation does hold - Alice has provided a commitment to each of them of the contents of the message in the form of the MAC tag. So if Alice sends a message to Bob and Charlie, then Bob can prove to Charlie that Alice sent him the message, but he cannot prove the same to Doris (who wasn’t in the original recipients).

Does your definition of signcryption insider security imply Boneh & Shoup’s definition of non-repudiation, and so 3rd-party verifiability? Or would the scheme that I’ve sketched also meet this goal?

[1]: https://toc.cryptobook.us <https://toc.cryptobook.us/> (Boneh and Shoup, A Graduate Course in Applied Cryptography)

Kind regards,

Neil

> On 8 May 2020, at 21:48, Mihir Bellare <[email-masked]> wrote:
> 
> Public-key authenticated encryption is, I think, what in the literature is called Signcryption.
> While early formulations were single recipient, a multi-recipient formulation is given in Section 3 of https://eprint.iacr.org/2020/224 <https://eprint.iacr.org/2020/224>
> This defines security goals of privacy, authenticity, and one that combines them, in two forms, insider and outsider, depending on whether or not the adversary is a key holder.
> The above paper does not give schemes of the form you give. My question is that, perhaps, do the definitions capture what you want to target?
> 
> Mihir
> 
> 
> 
> On Mon, Apr 27, 2020 at 7:12 AM Neil Madden <[email-masked] <mailto:[email-masked]>> wrote:
> Hi all,
> 
> [1]: https://tools.ietf.org/html/draft-madden-jose-ecdh-1pu-03 <https://tools.ietf.org/html/draft-madden-jose-ecdh-1pu-03>
> 
> Kind regards,
> 
> Neil Madden

---

From: Neil Madden <[email-masked]>
Date: Mon, 18 May 2020 11:57:14 +0100

Thanks for the reply, some comments below:

> On 12 May 2020, at 19:06, Phillip Hallam-Baker <[email-masked]> wrote:
> 
> It is an interesting question. One approach is to look at it from a systems angle.
> 
> Alice is going to send a message to Bob, Carol and herself. She wants each to be able to authenticate the message but without being able to prove Alice sent it (so can't just sign).
> 
> Let us begin by assuming we are using ECDH. This means that we are going to need a keywrap for each recipient under the agreed key. We can generate a unique input to a MAC at the same time.
> 
> She encrypts and authenticates the message resulting in a ciphertext we can ignore at this point and an authentication tag t.
> 
> So each recipient has an independent verification tag that is derived from the same key exchange used to encrypt the data for their use.

In my case WRAP is AES-KW of RFC 3394, which is already an authenticated encryption scheme [*] so I can just wrap (k, t) together for each recipient. I did consider this kind of approach, but if you have many recipients then this adds quite a lot of overhead. E.g., assuming HMAC-SHA256 with a 32-byte Auth_p tag then if you have a thousand recipients then there is an overhead of 32kB. By contrast, feeding the message MAC tag (or a hash of the message) into the KDF adds no additional per-recipient overhead.

This makes me realise that there is yet another approach that could be used: swap AES-KW for SIV-AES and then feed the message MAC tag as additional authenticated data. (Again, assuming the MAC is compactly committing/collision-resistant).

[*] Albeit with a ciphertext expansion of just 64 bits.

> 
> I am sure this can't be a novel construction simply because it is so heavily constrained. If we are going to use a MAC to authenticate data, we must encrypt to data that is only shared bilaterally. Which means we have to look at the output of the El-Gamal key agreement. Since we have a KDF in there already, the approach falls out naturally.

I believe this is basically what Saltpack does (https://saltpack.org/encryption-format-v2 <https://saltpack.org/encryption-format-v2>).

— Neil