Re: [Cfrg] AES GCM SIV analysis

Adam Langley <agl@imperialviolet.org> Wed, 18 January 2017 17:34 UTC

MIME-Version: 1.0
Sender: alangley@gmail.com
In-Reply-To: <D120A224329B7F4CA6F000FB5C0D964C01EBE26FEA@MSMR-GH1-UEA07.corp.nsa.gov>
References: <D120A224329B7F4CA6F000FB5C0D964C01EBE26F73@MSMR-GH1-UEA07.corp.nsa.gov> <D120A224329B7F4CA6F000FB5C0D964C01EBE26F86@MSMR-GH1-UEA07.corp.nsa.gov> <D120A224329B7F4CA6F000FB5C0D964C01EBE26FEA@MSMR-GH1-UEA07.corp.nsa.gov>
From: Adam Langley <agl@imperialviolet.org>
Date: Wed, 18 Jan 2017 09:34:31 -0800
Message-ID: <CAMfhd9V77LN41QTt4YvNs-bjUan_PtdrEiQeHvKXY+G+k2z1kw@mail.gmail.com>
To: "Cooley, Dorothy E" <decoole@nsa.gov>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/rnyd9zoCZgVM8ruK3Zh_aLb-WIg>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] AES GCM SIV analysis
Precedence: list

On Wed, Jan 18, 2017 at 8:49 AM, Cooley, Dorothy E <decoole@nsa.gov> 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.
>
> decoole@nsa.gov

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] AES GCM SIV analysis Cooley, Dorothy E
Re: [Cfrg] AES GCM SIV analysis Adam Langley
Re: [Cfrg] AES GCM SIV analysis Adam Langley
Re: [Cfrg] AES GCM SIV analysis Brian Smith
Re: [Cfrg] AES GCM SIV analysis Shay Gueron
Re: [Cfrg] AES GCM SIV analysis Adam Langley
Re: [Cfrg] AES GCM SIV analysis Brian Smith
Re: [Cfrg] AES GCM SIV analysis John Mattsson
Re: [Cfrg] AES GCM SIV analysis Shay Gueron
Re: [Cfrg] AES GCM SIV analysis Shay Gueron
Re: [Cfrg] AES GCM SIV analysis Adam Langley
Re: [Cfrg] AES GCM SIV analysis Dan Harkins
Re: [Cfrg] AES GCM SIV analysis Adam Langley
Re: [Cfrg] AES GCM SIV analysis Alex Cope
Re: [Cfrg] AES GCM SIV analysis Watson Ladd
Re: [Cfrg] AES GCM SIV analysis Shay Gueron
Re: [Cfrg] AES GCM SIV analysis Alex Cope
Re: [Cfrg] AES GCM SIV analysis Andy Lutomirski