Re: [Cfrg] AES GCM SIV analysis

>>> Is this a meaningful recommendation?
>>> How would one go about following this recommendation in a practical
implementation?

This is a very valid question, that is answered in the specification. But
perhaps it is worth clarifying on the mailing list. It is rather easy to
adhere to the recommendation. Simply choose the 96-bit nonce uniformly at
random. After, say, 2^{50} encryptions, what the probability that a nonce
repeated, even 5 times, can be bounded from above (see the "multibirthday"
reference in the spec) by 2^(-134).
(To this, you need to add occurrences where the keys also collide. All this
analysis will be posted soon, together with the matching bounds).

>>> Do we really need a 32-bit counter for this mode?
>>> Why not have a 16-bit counter?
Also a very valid question.
The answer is that you don't really need a 32-bit counter.
It is possible for a usage to specify a shorter restriction on the allowed
message length. This will improve the security bounds, which are also a
function of k, where 2^k is the largest number of blocks in a message. You
can choose any k <= 32.

Thanks, Shay

2017-01-18 12:51 GMT-08:00 Brian Smith <brian@briansmith.org>:

> On Wed, Jan 18, 2017 at 7:34 AM, Adam Langley <agl@imperialviolet.org>
> 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?
>
> 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.
>
> Cheers,
> Brian
> --
> https://briansmith.org/
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>