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

["Dan Harkins" <[e-mail]>]

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.

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