Re: [Cfrg] AES GCM SIV analysis

[Adam Langley <[e-mail]>]

On Wed, Jan 18, 2017 at 7:53 PM, Brian Smith <[e-mail]> 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.

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?

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


Cheers

AGL

-- 
Adam Langley [e-mail] https://www.imperialviolet.org