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

[Yoav Nir <[e-mail]>]

> On 31 Mar 2016, at 9:23 AM, Dan Harkins <[e-mail]> wrote:
> 
> 
> 
> On Wed, March 30, 2016 11:01 pm, Yoav Nir wrote:
>> 
>>> 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.
> 
>  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.

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.

>> 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.

Right.

Yoav