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.


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