Re: [Cfrg] AES GCM SIV analysis

[Shay Gueron <[e-mail]>]

Dear CFRG,

In the interests of keeping things on the working-group mailing list, I am
including the two follow-ups that we sent, previously, in response to this

(note: the discussion with  "NSA Information Assurance Standards" team took
place in two  back-and-forth iterations. Hence we sent two replies, which
are attached here).

Due to the limit on the size of a posting, the two files will be
transmitted in two separate mails.

This attachment: Reply 1

Thank you, Shay Gueron


2017-01-18 9:46 GMT-08:00 Shay Gueron <[e-mail]>:

> Dear CFRG,
>
>
> In the interests of keeping things on the working-group mailing list, I am
> including the two follow-ups that we sent, previously, in response to this
>
>
> (note: the discussion with  "NSA Information Assurance Standards" team
> took place in two  back-and-forth iterations. Hence we sent two replies,
> which are attached here).
>
>
> Thank you, Shay Gueron
>
>
>
> 2017-01-18 9:34 GMT-08:00 Adam Langley <[e-mail]>:
>
>> On Wed, Jan 18, 2017 at 8:49 AM, Cooley, Dorothy E <[e-mail]>
>> wrote:
>> > NSA's Information Assurance organization did some analysis of
>> AES-GCM-SIV,
>> > as described in "AES-GCM-SIV:  Nonce Misuse-Resistant Authenticated
>> > Encryption", dated August 29, 2016 [1].  We shared this analysis
>> privately
>> > with the three authors of AES-GCM-SIV, who requested that we post it to
>> the
>> > CFRG forum. The attachment describes the results of the analysis. We
>> believe
>> > the authors will be posting an update shortly.
>> >
>> >
>> >
>> > Any comments on this work can be directed to me.  But I will note that I
>> > didn't do the actual analysis (I can't claim to be a 'real'
>> cryptographer
>> > these days).
>> >
>> >
>> >
>> > Deb Cooley
>> >
>> > NSA Information Assurance Standards.
>> >
>> > [e-mail]
>>
>> Dear CFRG,
>>
>> We thank Deb Cooley's team very much for doing this analysis! As she
>> mentioned, they shared their results with us prior to posting here so
>> we already had an update ready and we've just posted
>> https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-03.
>>
>> This update contains three noteworthy changes:
>>
>> 1) We now XOR the nonce into the result of POLYVAL before encrypting
>> to form the tag. This was in the original paper, it was even specified
>> for /decryption/ in -02, but it was omitted in the specification for
>> encryption. This was a mistake. Without it, an attacker can build a
>> lookup table of encryptions of zero under a variety of per-nonce keys
>> and then attack them in parallel (as pointed out in the comments from
>> the IAD), under a single-user-multi-key model.
>>
>> Draft -03 fixes this omission and reintroduces the nonce.
>>
>> 2) A different KDF. As I mentioned at the previous CFRG meeting (in
>> Seoul, 2016) , we had this design in mind but didn't feel that it
>> warranted a new version of the design. However, since we needed a
>> respin because of (1), we have included it.
>>
>> Previously, per-nonce key material was generated by repeated
>> encryption, E(nonce), E(E(nonce)), and so on. This cascade leads to
>> impractical but needling issues including those noted by IAD. We now
>> generate keys by using counter mode and discarding half of each
>> ciphertext block. This solves those issues and also gives improved
>> indistinguishability bounds.
>>
>> In order to make room for the counter, the nonce size has been reduced
>> to 96 bits.
>>
>> 3) A much more minor change is that we now suggest a limit of 2^8 as
>> the maximum number of plaintexts encrypted with a single nonce. We
>> previously noted that AES-GCM-SIV with a fixed nonce is similar to
>> AES-GCM with a random nonce, and that NIST recommends a limit of 2^32
>> messages in that context.
>>
>> Note that we do NOT recommend nonce reuse by choice even inside
>> AES-GCM-SIV. This is for two reasons. First, encrypting the same
>> message twice will be detected. Second, the security bounds when using
>> different nonces are better. For example, when encrypting 2^{32}
>> messages with the same nonce, the probability of a bad event is
>> 2^{-32}. However, as we have shown, when encryption with different
>> nonces, it is possible to go up to about 2^{50} messages without any
>> problem.
>>
>> If nonces repeat mistakenly, for which providing protection is the
>> main aim of this mode of operation, then very strong bounds are still
>> obtained for a large number of ciphertexts (much more than 2^32) as
>> long as a single nonce is not repeated more than say 2^8 times. In
>> practice, such an event is highly unlikely.
>>
>>
>>
>> Cheers
>>
>> AGL
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>