Subject: [Cfrg] AES-GCM-SIV security of the additional data

From: Daniel Bleichenbacher <[email-masked]>
Date: Fri, 24 Jun 2016 13:35:24 +0200

I'm wondering what can or should be expected about the security of the
additional data.

In particular, I'm considering the following scenario:

Sender and receiver share a secret S.
The sender knows the public key of the receiver and the receiver of course
knows the private key.
They use a hybrid encryption as follows:

The sender chooses a new AES-GCM-SIV key, encrypts his message
and includes S as additional data. The AES-GCM-SIV key is wrapped with
the receivers public key and the wrapped key and ciphertext are sent to the
receiver.

Here an attacker can use that AES-GCM-SIV allows to select a key such that
the
element H used for POLYVAL is 0. In this case it would not be necessary for
the sender
to know S to construct a ciphertext that validates.
A similar attack using AES-GCM seems much harder since the value H for the
GHASH
is obtained by encrypting 0 and thus I'm not aware of a way to do the same
thing here.

The attack does of course not violate any of the guarantees claimed.
However, in the industry lots of ad hoc protocols are designed without
proper security reductions and hence it seems a bit scary to me to allow
this kind of "weak" keys. And since abuse resistance is
one of the goals it might be a good idea to avoid such type of abuses.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 24 Jun 2016 13:24:40 +0000

Hi Daniel,

Thanks for your message.

The usual expectation in AEAD is that the AD is integrity protected, but
there's no assurance as to its confidentiality. It's not usually
considered part of the ciphertext, but might be included along with it in
a message being sent to a receiver, or might be reconstructed from other
data/context by the receiver.

In your scenario it looks like you are trying to use the shared secret S
to provide authentication of the sender to the receiver, along with
confidentiality for the message being delivered. In this scenario, it's
not clear to me why the sender and receiver would not just use S as an
AES-GCM-SIV key to transport a session key K, and then use K in another
instance of AES-GCM-SIV to transport the desired messages. Of course, this
construction would not prevent replay attacks; for that you'd need
additional mechanisms, like incorporating a counter into the AD of the
key-transporting AEAD.

But perhaps one should not underestimate the ingenuity of implementers in
wanting to use public key encryption. Is this where you are coming from?

On a related point, my view is that it is a disbenefit that the
AES-GCM-SIV proposal has two separate keys (one for encryption, the other
for authentication) as inputs. That's not the AEAD interface that we have
raised our implementers on. I raised this point at the CFRG meeting in
Vienna back in May. Simply concatenating the two keys in the current
proposal into one would address this issue, but not the one you raise (if
I understand it correctly).

(The minutes of the meeting can be found here:
https://www.ietf.org/proceedings/interim-2016-cfrg-01/minutes/minutes-inter
im-2016-cfrg-1) 

Regards

Kenny  

On 24/06/2016 12:35, "Cfrg on behalf of Daniel Bleichenbacher"
<[email-masked] on behalf of [email-masked]> wrote:

>The sender knows the public key of the receiver and the receiver of
>course knows the private key.
>the receivers public key and the wrapped key and ciphertext are sent to
>the receiver.
>
>
>Here an attacker can use that AES-GCM-SIV allows to select a key such
>that the
>element H used for POLYVAL is 0. In this case it would not be necessary
>for the sender
>A similar attack using AES-GCM seems much harder since the value H for
>the GHASH
>is obtained by encrypting 0 and thus I'm not aware of a way to do the
>same thing here.
>
>

---

From: Antonio Sanso <[email-masked]>
Date: Fri, 24 Jun 2016 13:40:31 +0000

hi Kenny

On Jun 24, 2016, at 3:24 PM, Paterson, Kenny <[email-masked]> wrote:

> confidentiality for the message being delivered

to me this seems a pretty common scenario.
If I am not completely wrong in my understanding is for example what JWE does [0] and [1] for example

regards

antonio

[0] https://tools.ietf.org/html/rfc7516#page-32
[1] https://tools.ietf.org/html/rfc7516#page-36

> . In this scenario, it's
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 24 Jun 2016 13:53:46 +0000

Hi Antonio,

>[1] https://tools.ietf.org/html/rfc7516#page-36

Key transport via PKE using, for example RSA-OAEP, is a certainly an
option in JWE. But what Daniel describes has an additional symmetric key
("S") for the purposes of authentication, I think, and does not strictly
match anything I've seen in the JSON RFCs. But let's allow Daniel to
answer on that one...

Cheers

Kenny

---

From: Daniel Bleichenbacher <[email-masked]>
Date: Fri, 24 Jun 2016 16:14:42 +0200

> match anything I've seen in the JSON RFCs. But let's allow Daniel to

I'm not familiar with JWE so I can't comment on this protocol.
A typical scenario where S can't be used directly as key are low entropy
secrets
such as passwords.

One motivation for me  to look into this is the question whether AES-GCM-SIV
could be used as a drop-in replacement for AES-GCM without doing an
additional
security review of the resulting protocol.
So far, I'm not convinced that this can be done in all cases.

---

From: "Gueron, Shay" <[email-masked]>
Date: Fri, 24 Jun 2016 14:23:36 +0000

Hello to Daniel (and all) –

This is a very interesting point, raised by Daniel.
It does not attack AES-GCM-SIV, but rather a particular (imaginary) way 
to (not) use it.
Daniel's demonstration shows that there exists a protocol that is safe 
(I guess) when using AES-GCM as a component, but not safe when 
(carelessly) using AES-GCM-SIV as this component. Indeed, so.

But, as Daniel indicated, it does not violate the promise of 
AES-GCM-SIV, and the simple answer is: don’t use protocols (certainly 
not made-up) without proper analysis.

To Kenny: it does not matter here if the there is a single key where a 
part of it are used for encryption, and another part for the 
authentication, or 2 separate keys. Because, the adversary controls this 
key (or the two keys) in the described scenario.

About the protocol: if there is already a shared secret (S), why not use 
it directly with AES-GCM-SIV (where different nonces, that yield 
different encryption keys), as Kenny has already indicated.

If someone insists on using such a hybrid protocol (why?), then how 
about this change in it: draw K1 and x uniformly at random, and define 
K1 as the encryption key, and K2 = ENC_S (x) as the authentication key. 
Then use AES-GCM-SIV with these keys and the mentioned protocol. This 
addresses the root cause for the protocol’s failure: now, the adversary 
does not control the authentication key and cannot force a “weak” (zero) 
one to be used.
[disclaimer: I have not analyzed the protocol in depth]
Thanks, Shay
------ Original Message ------
From: "Paterson, Kenny" <[email-masked]>
To: "Antonio Sanso" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Sent: 6/24/2016 4:53:46 PM
Subject: Re: [Cfrg] AES-GCM-SIV security of the additional data

>>On Jun 24, 2016, at 3:24 PM, Paterson, Kenny 
>><[email-masked]>
>>wrote:
>>
>>>
>>If I am not completely wrong in my understanding is for example what 
>>JWE
>>does [0] and [1] for example
>>
>>regards
>>
>>antonio
>>
>>>  instance of AES-GCM-SIV to transport the desired messages. Of 
>>>course,
>>>this
>>>  But perhaps one should not underestimate the ingenuity of 
>>>implementers
>>>in
>>>  proposal into one would address this issue, but not the one you 
>>>raise
>>>(if

---

From: "Gueron, Shay" <[email-masked]>
Date: Fri, 24 Jun 2016 17:10:23 +0000

Hello everyone,

I start a new tread.

It is a branch off the one entitled "AES-GCM-SIV security of the 
additional data" and initiated by Daniel.

It combine Kenny's inputs about having two separate keys and the AEADE 
interface (which he raised at the CFRG meeting in
Vienna in May and also mentioned, in the previous thread, that 
concatenating 2 separate keys does not solve the problem that Daniel 
raised).

It also address a comment that Bart Preneel made at that CFRG meeting.

****

It is possible to define AES-GCM-SIV with a standard interface that has 
a single key (say, MK for "Master Key"), which can be 128 or 256 bits. 
Basically, by adding the following key derivation step:

     Using MK, derive two new keys K and H: K for encryption and H for 
authentication.
     From that point on, apply AES-GCM-SIV as it is defined now, where 
(K, H) are the keys.

Note that K and H are derived statically from MK. The "record encryption 
key" for the encryption depends on the nonce N, via another derivation, 
as it is currently defined in AES-GCM-SIV.

Note: the derivations are different for the 128 and the 256 bit keys, 
but such derivations are already in use by AES-GCM-SIV.
With this, AES-GM-SIV could be used with the protocol Daniel described, 
and would address Kenny's comment on the AEAD interface.
(I guess that it could be better viewed as a drop in replacement to 
AES-GCM)

The cost is the additional key derivation. this cost could be low if the 
message is long, or if many messages are encrypted (so that K, H can be 
cached).

An alternative would be to incorporate the nonce from the beginning, 
during the derivation of K, H from MK. This will modify the record 
encryption key and also the hash key per each nonce. In that case the 
extra derivation of the record encryption key (per nonce) could be 
skipped (but also could be not done).

I would appreciate any comments on this.

Thanks, Shay

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 24 Jun 2016 18:07:14 +0000

Since the traditional assumption for AEAD interface is “you use one key
that is responsible for both confidentiality and integrity”, I’m in favor
of defining such an interface for AES-GCM-SIV.

In that case IMHO it makes sense to incorporate nonce from the beginning,
using the same AES-OFB approach.

Thanks!
-- 
Regards,
Uri Blumenthal

---

From: "Jim Schaad" <[email-masked]>
Date: Fri, 24 Jun 2016 14:40:24 -0700

From: Cfrg [mailto:[email-masked]] On Behalf Of Daniel Bleichenbacher
Sent: Friday, June 24, 2016 7:15 AM
To: Paterson, Kenny <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] AES-GCM-SIV security of the additional data

On Fri, Jun 24, 2016 at 3:53 PM, Paterson, Kenny <[email-masked] <mailto:[email-masked]> > wrote:

Hi Antonio,

On 24/06/2016 14:40, "Antonio Sanso" <[email-masked] <mailto:[email-masked]> > wrote:

>hi Kenny
>
>On Jun 24, 2016, at 3:24 PM, Paterson, Kenny <[email-masked] <mailto:[email-masked]> >
>wrote:
>
>>

Cheers

Kenny

A typical scenario where S can't be used directly as key are low entropy secrets

such as passwords.

could be used as a drop-in replacement for AES-GCM without doing an additional

[JLS] This is probably not a good example for doing this.  I would agree that having separate keys for this is not a good way to approach this situation.  Just not having AD is a better way even if you have to generate the key.

JWE is a poor example of this because it is difficult to generate situations where there is not additional data generated by JWE itself for encrypting the content.  Also, if one is interested in doing a degree of origination one would either directly generate the key, in which case generating the authentication key would be part of the process or one would want to use the value in the KDF step rather than having an indirection involved.  Doing the indirection almost guarantees that you need to have additional steps in the process to guarantee that origination is going to be part of the process.

Jim

>> <[email-masked] <mailto:[email-masked]>  on behalf of [email-masked] <mailto:[email-masked]> > wrote:
>>
>> [email-masked] <mailto:[email-masked]>

---

From: Adam Langley <[email-masked]>
Date: Fri, 24 Jun 2016 18:43:02 -0700

> I understand it correctly).

The two keys are already concatenated in the draft, or else I
misunderstood your point:
https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-01#section-6

"Since the definition of an AEAD requires that the key be a single
value we define AEAD_AES_128_GCM_SIV to take a 32-byte key: the first
16 bytes of which are used as the authentication key and the remaining
16 bytes are used as the AES key. Likewise AEAD_AES_256_GCM_SIV takes
an 48-byte key: the first 16 bytes are again the authentication key
and the remaining 32 bytes is the AES key."

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 25 Jun 2016 08:40:51 +0000

Hi Adam,

Thanks for the clarification. My remarks were based on the scheme as presented by Shay at Vienna; there, he introduced the misconception that two separate keys were involved; he did not clarify this during questioning (see the minutes). 

Of course the draft is definitive document and it's good that it presents the normal API. 

Cheers,

Kenny

Sent from my iPhone

> On 25 Jun 2016, at 02:43, Adam Langley <[email-masked]> wrote:
>

---

From: "Gueron, Shay" <[email-masked]>
Date: Sat, 25 Jun 2016 09:58:34 +0000

I would like to clarify a point.

The API is a technical matter, so K1||K2 are K1, K2 are the same - from 
the logical viewpoint. The interface can use a single 32/48 bytes key, 
and this is how the draft is stated. This separation seemed to us as a 
*advantage* of the design, and this is what I tried to communicate in 
Vienna. I guess the confusion is due to my explanation... and hope it is 
clarified here.

With both interfaces, the property is that the authentication key is 
independent of the encryption key, and both are a direct input (unlike 
AES-GCM that derives the authentication key from a single input key).

Daniel's example showed that here exists a (flawed/artificial) protocol 
that would not work when using AES-GCM-SIV, but would be OK with 
AES-GCM.
It is not a problem of AES-GCM-SIV, which is designed as an AEAD scheme 
for the standard usage, and also, the protocol does not make much sense 
(to me, at least). Still, it is a very interesting observation.

The difference stems exactly from using 2 independent keys with 
AES-GCM-SIV, while using a single key with AES-GCM, and deriving H from 
it (by a one way function). It is the same for other AEAD schemes that 
use independent encryption and hash keys, where there are some "weak" 
hash keys (e.g., 0). This property affects any protocol that benefits a 
malicious sender (who could choose a bad hash key).

Should this needs to be addressed? I am not sure. A malicious sender is 
not part of the AEAD threat model.

But in any case, it could be addressed if AES-GCM-SIV used a single key 
(MK) and derived K1 and K2 from MK (and possibly the nonce). I raised 
this point in another thread.

Thanks, Shay

------ Original Message ------
From: "Paterson, Kenny" <[email-masked]>
To: "Adam Langley" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Sent: 6/25/2016 11:40:51 AM
Subject: Re: [Cfrg] AES-GCM-SIV security of the additional data

>Hi Adam,
>
>Thanks for the clarification. My remarks were based on the scheme as 
>presented by Shay at Vienna; there, he introduced the misconception 
>that two separate keys were involved; he did not clarify this during 
>questioning (see the minutes).
>
>>>raise (if

---

From: Aaron Zauner <[email-masked]>
Date: Sun, 26 Jun 2016 16:07:36 +0800

Hi,
> On 25 Jun 2016, at 01:10, Gueron, Shay <[email-masked]> wrote:
> 
> An alternative would be to incorporate the nonce from the beginning, during the derivation of K, H from MK. This will modify the record encryption key and also the hash key per each nonce. In that case the extra derivation of the record encryption key (per nonce) could be skipped (but also could be not done).

Could you clarify on that paragraph? e.g. with pseudocode?

Incorporating the nonce in the MK derivation step makes sense to me.

But; I don't fully grasp the last part of this paragraph; if you skip the extra derivation per record encryption key per nonce you lose nonce-MR?! Given the nonce is incorporated in the MK derivation step, this isn't an issue, but I'm not 100% sure what your suggestion here is.

Thanks,
Aaron

---

From: "Gueron, Shay" <[email-masked]>
Date: Sun, 26 Jun 2016 08:26:12 +0000

Of course - let me describe.
For simplicity, I describe the case of a 128-bit MK.

Option 1: K1 = E_MK (0), K2 = E_K1 (0)  (K1 will be used for encryption, 
and K2 for the authentication)
Then continue AES-GCM-SIV as it is defined now (including a derivation 
of a record encryption key, per nonce N)

Option 2: K1 = E_MK (N), K2 = E_K1 (N)
Then AES-GCM-SIV as it is defined now, but without an  additional 
derivation of a record encryption key; just set K1 as the record 
encryption key.

Note: Option 1 is merely a static "pre-derivation" (where K1, K2 can be 
cached). Here, MK is used directly only twice.
Option 2 uses MK (directly) with each nonce. Here, the hash key also 
depend on the nonce.

There is another option.

Option 3: K1 = E_MK (0), K2 = E_K1 (0)
Then continue AES-GCM-SIV as it is defined now (including a derivation 
of a record encryption key, per nonce N) and also define a record hash 
key via E_K2 (N).

These options offer different nuances, and would have a noticeable 
performance effect only for short messages. My favorite, among these 3, 
is Option 3 (that seems to enjoy all the benefits, at a small additional 
latency).

Shay

------ Original Message ------
From: "Aaron Zauner" <[email-masked]>
To: "Gueron, Shay" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>; "Yehuda Lindell" 
<[email-masked]>; "Adam Langley" <[email-masked]>
Sent: 6/26/2016 11:07:36 AM
Subject: Re: [Cfrg] AES-GCM-SIV with a new key hierarchy

>But; I don't fully grasp the last part of this paragraph; if you skip 
>the extra derivation per record encryption key per nonce you lose 
>nonce-MR?! Given the nonce is incorporated in the MK derivation step, 
>this isn't an issue, but I'm not 100% sure what your suggestion here 
>is.
>
>Thanks,
>Aaron

---

From: Aaron Zauner <[email-masked]>
Date: Sun, 26 Jun 2016 18:37:30 +0800

Hi Shay,

Thank you for your explanation.

So if that'd be a CFRG poll I'd go with the following preference:

> On 26 Jun 2016, at 16:26, Gueron, Shay <[email-masked]> wrote:
> 
> Option 1: K1 = E_MK (0), K2 = E_K1 (0)  (K1 will be used for encryption, and K2 for the authentication)
> Then continue AES-GCM-SIV as it is defined now (including a derivation of a record encryption key, per nonce N)

+

> Then AES-GCM-SIV as it is defined now, but without an  additional derivation of a record encryption key; just set K1 as the record encryption key.

+++

> 
> Note: Option 1 is merely a static "pre-derivation" (where K1, K2 can be cached). Here, MK is used directly only twice.
> Option 2 uses MK (directly) with each nonce. Here, the hash key also depend on the nonce.
> 
> There is another option.
> 
> Then continue AES-GCM-SIV as it is defined now (including a derivation of a record encryption key, per nonce N) and also define a record hash key via E_K2 (N).

++

Aaron

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sun, 26 Jun 2016 16:18:02 +0000

Hi Shay

Thanks for presenting these options.

Could you summarise what the impact would be on your security proofs of
each of the three options, if any?

I'd also be interested to see an explicit accounting for the performance
impacts - this could be roughly characterised in terms of the number of
AES operations involved in key derivation per message in each case.

Cheers

Kenny