Re: [Cfrg] AES GCM SIV analysis

[Adam Langley <[e-mail]>]

On Wed, Jan 18, 2017 at 12:51 PM, Brian Smith <[e-mail]> wrote:
> On Wed, Jan 18, 2017 at 7:34 AM, Adam Langley <[e-mail]> wrote:
>> 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.
>
> The actual text in the draft is "Thus with AES-GCM-SIV we recommend
> that, for a specific key, a nonce not be repeated more than 2^8
> times."
>
> Is this a meaningful recommendation? How would one go about following
> this recommendation in a practical implementation? In particular,
> AES-GCM-SIV is mostly interesting in implementations that cannot
> reliably and/or consistently save state, and it seems like any attempt
> to write code to enforce this relies on saving state in the manner. Is
> the idea here that one would, every 2^8 or so messages, force some
> kind of "sync state or force rekey" operation that would be too
> expensive to do on every message?

No, nothing like that. Perhaps this part of the document isn't clear.

Basically, before we noted that AES-GCM-SIV with a fixed nonce like
like AES-GCM with a random nonce (except that it also leaks when
plaintexts are equal). We noted that NIST recommends no more than 2^32
messages be encrypted with a given key in that context.

So someone could, not completely unreasonably, say that they're not
worried about leaking when plaintexts are equal and use AES-GCM-SIV
with a fixed nonce for 2^32 messages.

We're now clearly saying that's not a great idea. Instead, generate
nonces at random. With a random, 96-bit nonce you don't have to worry
about the probability of having repeated a single value > 2^8 times
until you have a staggering number of plaintexts: greater than 2^100
of them. Since that vastly exceeds our current recommendation for
number of plaintexts per key (2^50), it's basically not a concern.

If that makes sense, what could we have written to be clearer?

> Do we really need a 32-bit counter for this mode? Why not have a
> 16-bit counter? This would allow single messages up to 1MB. Then one
> could more safely use a 96-bit random + 16-bit fixed ID nonce or an
> 80-bit random + 32-bit fixed ID nonce. In general, super large
> messages don't work well with AEADs because it's hard to verify the
> integrity of a giant message before using the plaintext, so 32-bit
> counters seem excessive. I expect protocols would limit the maximum
> message length such that a ~16-bit counter would be sufficient.

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


Cheers

AGL

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