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

[Neil Madden <[e-mail]>]

Thanks for the reply, some comments below:

> On 12 May 2020, at 19:06, Phillip Hallam-Baker <[e-mail]> 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.
> 
> 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.

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