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

["Gueron, Shay" <[e-mail]>]

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" <[e-mail]>
To: "Tony Arcieri" <[e-mail]>
Cc: "Yehuda Lindell" <[e-mail]>; "[e-mail]" 
<[e-mail]>; "Adam Langley" <[e-mail]>
Sent: 3/31/2016 7:13:47 AM
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant 
Authenticated Encryption" as a CFRG document

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