Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document

From: denis bider <[email-masked]>
Date: Thu, 31 Mar 2016 02:56:40 +0100

I believe Dan's point was that AES256-GCM-SIV uses a 128-bit tag to derive the final encryption key.

Regardless of the original input key size, the encryption key is derived in a way that, at some point, is reduced to 128 bits of entropy.

I find this to be a good point, and indeed, a plausible concern.

----- Original Message -----
From: Tony Arcieri 
Sent: Wednesday, March 30, 2016 19:11
To: Dan Harkins 
Cc: Yehuda Lindell ; [email-masked] ; Adam Langley 
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document

On Wed, Mar 30, 2016 at 12:22 PM, Dan Harkins <[email-masked]> wrote:
Would you agree that AEAD_AES_256_GCM_SIV provides no more
security than AEAD_AES_128_GCM_SIV? I say this because the
authentication key is 128-bits regardless 

I disagree with this. 128-bits of symmetric security is fine today. The threats where you might want 256-bit encryption are things like hypothetical future quantum computers which are able to use Grover's algorithm.

Encryption needs to stand the test of time. Authentication has less burdensome demands. If it's possible to pull off an online chosen ciphertext attack after the advent of quantum computers which can use Grover's algorithm to break 128-bit crypto (10+ years in the future maybe?), the story might be different, but for long-term confidentiality of ciphertexts I think a larger key size for a symmetric cipher is more important.

The same argument can be applied to digital signatures and quantum cryptography: they matter less than encryption, because we can resign data if a quantum attack seems imminent, but if a quantum attacker already has access to ciphertexts there's nothing we can do.

-- 

Tony Arcieri

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 30 Mar 2016 19:23:13 -0700

On Mar 30, 2016 9:56 PM, "denis bider" <[email-masked]> wrote:
> Regardless of the original input key size, the encryption key is derived
in a way that, at some point, is reduced to 128 bits of entropy.
> I find this to be a good point, and indeed, a plausible concern.

If true, it may even be a fairly large concern.  If each message uses a
separate 128-bit key, then this could plausibly be subject to the type of
parallel attack djb loves talking about where each *message* is a target.
That would make collecting 2^64 or so potentially interesting ciphertexts
considerably easier than with most modes.

But it looks like the key is just a normal key.

--Andy

> Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant
Authenticated Encryption" as a CFRG document
> I disagree with this. 128-bits of symmetric security is fine today. The
threats where you might want 256-bit encryption are things like
hypothetical future quantum computers which are able to use Grover's
algorithm.
>
> Encryption needs to stand the test of time. Authentication has less
burdensome demands. If it's possible to pull off an online chosen
ciphertext attack after the advent of quantum computers which can use
Grover's algorithm to break 128-bit crypto (10+ years in the future
maybe?), the story might be different, but for long-term confidentiality of
ciphertexts I think a larger key size for a symmetric cipher is more
important.
>
> The same argument can be applied to digital signatures and quantum
cryptography: they matter less than encryption, because we can resign data
if a quantum attack seems imminent, but if a quantum attacker already has
access to ciphertexts there's nothing we can do.

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 30 Mar 2016 20:40:56 -0700

> the final encryption key.

No?

4.  Encryption

   AES-GCM-SIV encryption takes a 16-byte authentication key, a 16- or
   32-byte AES key, a 128-bit nonce, and arbitrary-length plaintext and
   additional data inputs.  It outputs an authenticated ciphertext that
   will be 16 bytes longer than the plaintext.

-- 
Tony Arcieri

---

From: Yoav Nir <[email-masked]>
Date: Thu, 31 Mar 2016 07:13:47 +0300

Hi, Tony

> On 31 Mar 2016, at 6:40 AM, Tony Arcieri <[email-masked]> wrote:
> 
> On Wed, Mar 30, 2016 at 6:56 PM, denis bider <[email-masked] <mailto:[email-masked]>> wrote:

I think the relevant section is the next paragraph where the record encryption key is defined. That too is defined to be the same length as the input key:

   If the AES key is 16 bytes long then define the _record-encryption
   key_ as the encryption of the nonce using the AES key.  If AES-256 is
   being used then this is insufficient as 256 bits of key material are
   needed.  Therefore the record-encryption key in this case is the
   concatenation of the result of encrypting, using the AES key, the
   nonce with the least-significant bit of the first byte set to zero
   and then to one.

Yoav

---

From: "Gueron, Shay" <[email-masked]>
Date: Thu, 31 Mar 2016 04:38:02 +0000

Hello everyone,
To clarify a possible confusion about the 256-bit variant: no 256-bit 
key is ever derived from a 128-bit key (as Yoav pointed out). The 
authentication key has 128 bits, and so does the authentication tag.

The raised concern is that since the flow derives a 256-bit key by 
applying AES256 to a 128-bit nonce (with 0 and 1), then we actually have 
maximum 2^128 possible keys as a result, and not maximum 2^256. Thus, 
the entropy seems reduced to 2^128.

However, if AES256 is secure as a pseudorandom permutation, then even if 
you derive a key by applying to 0 and 1 (and therefore have only 1 
option), the effect is still pseudorandom to anyone not being able to 
break AES256. It is not the number of possible derived keys, but their 
strength. By using AES256 to derive them, the strength is that of 
256-bit security.

Thanks,
Shay and Yehuda

------ Original Message ------
From: "Yoav Nir" <[email-masked]>
To: "Tony Arcieri" <[email-masked]>
Cc: "Yehuda Lindell" <[email-masked]>; "[email-masked]" 
<[email-masked]>; "Adam Langley" <[email-masked]>
Sent: 3/31/2016 7:13:47 AM
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant 
Authenticated Encryption" as a CFRG document

>>On Wed, Mar 30, 2016 at 6:56 PM, denis bider 
>><[email-masked]> wrote:
>>4. Encryption AES-GCM-SIV encryption takes a 16-byte authentication 
>>key, a 16- or 32-byte AES key, a 128-bit nonce, and arbitrary-length 
>>plaintext and additional data inputs. It outputs an authenticated 
>>ciphertext that will be 16 bytes longer than the plaintext.
>
>I think the relevant section is the next paragraph where the record 
>encryption key is defined. That too is defined to be the same length as 
>the input key:
>
>If the AES key is 16 bytes long then define the _record-encryption key_ 
>as the encryption of the nonce using the AES key. If AES-256 is being 
>used then this is insufficient as 256 bits of key material are needed. 
>Therefore the record-encryption key in this case is the concatenation 
>of the result of encrypting, using the AES key, the nonce with the 
>least-significant bit of the first byte set to zero and then to one.
>
>Yoav

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 30 Mar 2016 22:09:28 -0700 (PDT)

On Wed, March 30, 2016 8:40 pm, Tony Arcieri wrote:
>> I believe Dan's point was that AES256-GCM-SIV uses a 128-bit tag to
>> derive
>> the final encryption key.
>>
>
> No?
>
> 4.  Encryption
>

  Not sure what you mean by "No?".

  My point was that regardless of whether it's the 128- or 256-bit
option the _authentication key_ used is only 128-bits; and, when
using the 256-bit option the "record encryption key" can only take
on 2^128 values.

  So, if the effective authentication and encryption keys being used
in the cipher mode are always 128-bits then the 256-bit option does
not provide any more security than the 128-bit option. And if that's
the case then there is no reason to have AEAD_AES_256_GCM_SIV. Right?

  regards,

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 30 Mar 2016 22:24:04 -0700

> the case then there is no reason to have AEAD_AES_256_GCM_SIV. Right?

Let's try to do some math here. Standard PRP conjectures say that
AES_k(0), AES_k(1) for k 256 bits is indistinguishable from the values
of a permutation chosen uniformly at random with success probability
q/2^256 where q is some computation measure. PRP->PRF says that with
advantage at most 2^{-128} this is indistinguishable from two random
values. So the distinguishability of the resulting key from a random
256 bit key is q/2^256+1/2^128. It's true that there is a 1/2^128 in
the answer, but it isn't multiplied by q.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 30 Mar 2016 22:38:51 -0700 (PDT)

On Wed, March 30, 2016 9:13 pm, Yoav Nir wrote:
>> On Wed, Mar 30, 2016 at 6:56 PM, denis bider <[email-masked]
>> <mailto:[email-masked]>> wrote:
>> derive the final encryption key.
>>
>> No?
>> 4.  Encryption
>>

  It's not the length, it's the number of values possible in that
length. Because this cipher mode is using AES-256-ECB as a 128-bit
PRP it is generating two distinct 128-bit blobs and concatenating
them. That means that there can only be 2^128 possible values of
that 256-bit key.

  So I guess it's still using AES-256-CTR to encrypt the data but
the 256-bit key used in that invocation can only take 2^128 possible
values. And that, to me, seems like a shortcoming especially when
you consider that the authentication key is always 128-bits
regardless of the length of the encryption key.

  If some 256-bit cipher mode specified that the high-order 128-bits
of the key MUST be set to zero would you say the cipher was any
better than a 128-bit equivalent that used all 128-bits?

  regards,

  Dan.

> Yoav_______________________________________________
> Cfrg mailing list
> [email-masked]

---

From: Yoav Nir <[email-masked]>
Date: Thu, 31 Mar 2016 09:01:45 +0300

> On 31 Mar 2016, at 8:38 AM, Dan Harkins <[email-masked]> wrote:
> 
> 
> 

Actually it’s 2^127, because the least significant bit of the first byte is set first to zero and then to one, rather than for example setting it to the original value first and flipping it for the second.

But it is 2^127 possibilities for a record encryption key that is used either once or a very few times, and despite knowing that there are only 2^127 possibilities, I don’t see how you could iterate on them without either breaking AES-256 or iterating over the entire 2^256 space. 

I guess it would be nice to explain why they chose not to use a 256-bit nonce, but enlarging the nonce is not free.

Yoav

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 30 Mar 2016 23:08:14 -0700 (PDT)

> the answer, but it isn't multiplied by q.

  OK, so what you're saying is there's 2^256 - 2^128 possible
values, not 2^128 possible values. Right?

  Got it. So I retract my statements.

  Dan.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 30 Mar 2016 23:23:32 -0700 (PDT)

On Wed, March 30, 2016 11:01 pm, Yoav Nir wrote:
> Actually it’s 2^127, because the least significant bit of the first byte
> is set first to zero and then to one, rather than for example setting it
> to the original value first and flipping it for the second.

  The key is a concatenation of the output of two runs of AES-256-ECB.
It doesn't matter that one bit was set or cleared.

> But it is 2^127 possibilities for a record encryption key that is used
> either once or a very few times, and despite knowing that there are only
> 2^127 possibilities, I don’t see how you could iterate on them without
> either breaking AES-256 or iterating over the entire 2^256 space.

  As Watson pointed out, the number of values is 2^256 - 2^128.
You don't need to iterate over the entire 2^256 space to know which
values won't be possible keys, it's all 2^128 of them where the first
128 bits match the second 128 bits.

> I guess it would be nice to explain why they chose not to use a 256-bit
> nonce, but enlarging the nonce is not free.

  The nonce has to be the same size as the field that POLYVAL operates
on, and that's 2^128 bits.

  regards,

  Dan.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 31 Mar 2016 09:29:12 +0300

> On 31 Mar 2016, at 9:23 AM, Dan Harkins <[email-masked]> wrote:
> 
> 
> 

Right. That is over all uses of AES-GCM-SIV ever. But for a single 256-bit AES-GCM-SIV key, there are only 2^127 possible AES-CTR keys because the nonce determines the record key.

> on, and that's 2^128 bits.

Right.

Yoav

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 31 Mar 2016 01:22:44 -0700

> >
> > Regardless of the original input key size, the encryption key is
derived in a way that, at some point, is reduced to 128 bits of entropy.
> But it looks like the key is just a normal key.

I take this back.  I was reading the GCM-SIV paper, not the draft, and I'm
having trouble reconciling them.

If AES-128 is used, or if AES-256 is used with a 256-bit user-supplied key
(I think -- the draft is vague and should IMO be clarified), then the key
is just the key.

If AES-256 is used with a 128-bit key, then the key is munged with the
nonce to make a new key.  I don't like this at all:

1. What's the point?  Why not require an appropriate length of key to begin
with?

2. By deriving a nonce-dependent key, you add a key scheduling step that
might kill performance for short messages, I think.

3. Is it possible that this invalidates the security proof?  After all, it
sounds like you can have two instantiations that share an authentication
key but not a record key, and I don't think the proof was meant to cover
this case.

4. Since this claims nonce-MR, setting nonce=0 is valid.  If someone does
this, then I think they are vulnerable to the extra-easy parallel attack.

To what extent is this draft supposed to match the paper?

--Andy

---

From: Adam Langley <[email-masked]>
Date: Thu, 31 Mar 2016 10:38:27 +0100

> 128 bits match the second 128 bits.

(As an aside: this is what the final paragraph of the Security
Considerations section is aiming at:

"The construction of the record-encryption key in AEAD_AES_256_GCM_SIV
cannot result in the first and second halves of the key having the
same value.  Thus 2^128 of the 2^256 keys cannot occur.  We consider
this to be insignificant.")

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Thu, 31 Mar 2016 10:48:07 +0100

On Thu, Mar 31, 2016 at 9:22 AM, Andy Lutomirski <[email-masked]> wrote:
> (I think -- the draft is vague and should IMO be clarified), then the key is
> just the key.
>
> If AES-256 is used with a 128-bit key, then the key is munged with the nonce
> to make a new key.  I don't like this at all:

I think that draft is, indeed, vague on this point for which I
apologise. To clarify: there is no case where AES-256 is used with a
128-bit key.

In both the AES-128 and AES-256 cases, the record-encryption key is
generated by encrypting the nonce.

> might kill performance for short messages, I think.

Key scheduling is not a big deal with AES hardware but this is an overhead, yes.

(I'll leave questions about the security proof to the authors of the paper.)

Cheers

AGL