Re: [Cfrg] Do we need a selection contest for AEAD?

[Martin Thomson <[e-mail]>]

On Sat, Jun 20, 2020, at 03:32, Stanislav V. Smyshlyaev wrote:
> 5) Ability to safely encrypt a larger maximum number of bytes per key 
> (discussed in QUIC WG)..

I might suggest expanding this a little to include better bounds for attacker advantage in both single-user and multi-user settings.  We're digging into the mu analysis of AES-GCM and finding that the bounds aren't entirely satisfactory under some sets of assumptions.  In part, that demonstrates some lack in the research into the properties of the AEAD.  But it does show some of the limitations of the ciphers themselves.

To give a concrete example, the mu analysis of AES-GCM in https://eprint.iacr.org/2018/993.pdf ends up being dominated by a term that places the total number of blocks encrypted against the block size (\sigma.B/2^n in Equation (1) from the same paper, which - if you consider \sigma to be largely inflexible as I do - might be better restated as \sigma^2/u/2^n where u is the number of users or distinct keys).  Some back of the envelope calculations show that a \sigma of 2^70 is almost plausible, which means that the distribution of usage across large numbers of keys is the only real safeguard remaining.

This isn't cause for immediate concern, partly because I think that the threat model implied by the analysis isn't totally realistic.  However, it demonstrates how we have less headroom in these ciphers than might be immediately obvious.  AES has an option for larger keys, which helps in some cases, but it doesn't come with a larger block size.  The huge amount of use this cipher gets means that we probably need to pay attention to this when it comes to selecting a potential successor.