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

[Yoav Nir <[e-mail]>]

> On 31 Mar 2016, at 8:38 AM, Dan Harkins <[e-mail]> wrote:
> 
> 
> 
> On Wed, March 30, 2016 9:13 pm, Yoav Nir wrote:
>> Hi, Tony
>> 
>>> On 31 Mar 2016, at 6:40 AM, Tony Arcieri <[e-mail]> wrote:
>>> 
>>> On Wed, Mar 30, 2016 at 6:56 PM, denis bider <[e-mail]
>>> <mailto:[e-mail]>> 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
>>> 
>>>   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.
> 
>  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.

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