Subject: Re: [Cfrg] AES GCM SIV analysis
From: Dan Harkins <[email-masked]>
To: Adam Langley <[email-masked]>, Brian Smith <[email-masked]>
Cc: "Cooley, Dorothy E" <[email-masked]>, "[email-masked]" <[email-masked]>
Date: Thu, 26 Jan 2017 18:26:17 -0800
List-Id: Crypto Forum Research Group <cfrg.irtf.org>

Hello,

On 1/19/17 9:33 AM, Adam Langley wrote:
> On Wed, Jan 18, 2017 at 7:53 PM, Brian Smith <[email-masked]> wrote:
>> Perhaps: "We recommend instead that an implementation try to avoid
>> repeating a nonce for a specific key, just like it would it would do
>> for an AEAD that isn't nonce-misuse-resistant." This shifts the
>> emphasis away from the 2^8 number to where it belongs, IMO. Note that
>> "256" and how it is derived and why it is safe is explained in the
>> next paragraph anyway.
> After some discussions on Twitter I've discovered that several people
> (possibly including Brian) understand "nonce-misuse resistant" to mean
> a stronger property than AES-GCM-SIV has. Namely they understood it to
> mean that the value of the nonce is /irrelevant/ for security, except
> that a fixed nonce discloses equality of plaintexts.

   But that is the definition used in the seminal work on the matter, [1].
If you want to have a different notion concerning a lesser restriction on
nonce reuse then you should use a different term.

> AES-GCM-SIV doesn't have this property. It is robust to random nonce
> duplication but not designed for a fixed nonce. Specifically, after
> 2^n full-sized (i.e. 64MB) messages, there's ~2^(96-2n) chance that
> two of the messages reused counter values and thus keystream. (The
> bounds are better if messages are smaller.)
>
> Consider a broken TLS implementation that always uses a zero nonce and
> is sending 16KB records as fast as possible. By the time it has sent
> 2^40 records (44 TB) there's about a 2^-32 chance that two of those
> records shared keystream bytes. (That's very rough and there might be
> a few stray factors of two missing in there.)
>
> That's a lot better than AES-GCM, but we're not saying that the nonces
> are completely irrelevant to security.
>
> Perhaps we need a different term to clarify this? Occasional nonce
> duplication tolerant?

   Which brings up a question I've resisted asking: Why are you doing this?

   If you want to have an AEAD scheme that is nonce-misuse resistant that
can use a fast(er) authentication scheme then why not just do RFC 5297
with GHASH instead of AES-CMAC? You're defining a new irreducible
polynomial that, to my knowledge, is not in existing hardware the way
that PCLMULQDQ using x^128 + x^7 + x^2 + x + 1, is in Intel chips.
You're defining a(nother) KDF /inside/ the cipher mode itself instead of
just letting a KDF, which all users of AES-GCM-SIV will use, generate a
double-wide key. And I don't see the reason for either.

>>> I agree that large AEAD messages have several problems. But I don't
>>> think that we have any need for a larger nonce (see above). (And the
>>> nonce is used with a counter only in the KDF phase, so it's unrelated
>>> to the maximum plaintext size.)
>> Is there any way that a larger nonce (e.g. 120 bits) hurts, other than
>> being inconsistent with existing IETF AEADs?
> With three bits for the counter, the largest the nonce could be is 125
> bits. But I think a nonce that's not a whole number of bytes would be
> too confusing.
>
> The nonce could be 120 bits (15 bytes) but that has no practical
> advantage over 96 bits. If you're picking nonces at random then the
> change in bounds is trivial (see multibirthday reference in the spec).
> If your nonce generation is broken and you're using a fixed value then
> the size is irrelevant.
>
> 96 bits is a "rounder" number and might save some alignment problems
> is all, really.

   The size of the nonce should not matter to a generic misuse-resistant
cipher mode.

   regards,

   Dan.

   [1] https://eprint.iacr.org/2006/221.pdf

>
>
> Cheers
>
> AGL
>