AES-GCM and breaking it on nonce reuse

> unless an implementation only uses 96-bit IVs that are generated by the deterministic construction: The total number of invocations of the authenticated encryption function shall not exceed 2^32, including all IV lengths...

Which would be the conclusion if the hash was always reduced to 96 bits. What it actually goes on to say though is:

> For the RBG-based construction of IVs, the above requirement, in conjunction with the requirement that r(i)≥96, is sufficient to ensure the uniqueness requirement in Sec. 8

So, it's a bound. If there are at least 96 random bits, it should all be ok. But it strangely leaves open the possibility, without saying either way, that a longer iv, with r(i)>96 random bits might allow generating more iv's. As you point out, it will depend on the properties of GHASH (and potentially on how the result is used downstream from there). At this point I don't know, but the spec says:

> For IVs, it is recommended that implementations restrict support to the length of 96 bits, to promote interoperability, efficiency, and simplicity of design.

So personally, not being an expert, I'd follow the advice and use 96 bit iv's. And if using random iv's, re-key before using the key a billion times. I'd certainly want a reference to a careful analysis before assuming that I could ever use an AES-GCM key with longer random iv's more than that.

We are, after all, talking about the country that terrorized an Austrian town into changing its name after decades of sign theft and jokes [0]

[0]https://en.wikipedia.org/wiki/Fugging,_Upper_Austria

The vast majority of encryption algorithms must be used in a nonce-respecting scenario. This is part of the contract to achieve the claimed security properties.

Alternatives require multiple passes over the data, which is not applicable to some protocols in addition to having performance implications.

Common protocols such as TLS transparently handle nonces in a safe way. But the primitives used in TLS may require additional steps to be safely used is other contexts, especially in distributed systems.

Whenever applications try to use these primitives directly, using a fixed key and picking nonces at random is a very common practice. Unfortunately, due to their small size, nonces collisions can quickly happen.

We're missing standard constructions with large nonces that would alleviate this problem, because IETF protocols haven't needed them. But there's a lot of evidence that many custom applications and protocols do.

There are multiple great proposals to derive AES-GCM subkeys and nonces from a key and a large nonce. We may expect convergence and adoption in crypto libraries soon.

Until then, constructions such as XSalsa20 and XChaCha20 are widely implemented and deployed. If you don't need NIST compliance, they're excellent choices.

But my recommendation today would be to replace AES-GCM with the AEGIS family of algorithms whenever possible. They have nice properties that AES-GCM doesn't have, including more comfortable usage limits, much better performance and large nonces up to 256 bits.

This page [1] and that draft [2] summarize usage limits of common constructions, including when using random nonces.

[2] https://doc.libsodium.org/secret-key_cryptography/aead

[3] https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits...

This is actually generally fine for nonces (used in CTR and GCM modes, and in ChaCha20). Typically the only requirement for a nonce is that it is only used once. It is even safe to use a simple incrementing counter.

IVs, on the other hand, are required to be cryptographically random.