[kbolino]

No, this makes random nonces safe in the first place. With standard AES-GCM, you should use deterministic nonce generation since 96 bits is not enough to avoid random collisions. Also, you must change the nonce (or key) after 2^32 blocks regardless of how it was generated because the counter rolls over and the next block would use the same nonce+counter as the first block.

[chc4]

You are wrong. NIST recommendations outline both deterministic or RBG-based construction. The 2^32 invocation limit is only for random nonce or if your deterministic construction is less than 96bits. Lots of people are doing random nonces.

https://csrc.nist.gov/pubs/sp/800/38/d/final

[kbolino]

That link says the document needs revising, specifically "to clarify the guidance in connection with the IV constructions" (NIST calls the nonce an IV). It defines GCM normatively but its non-normative recommendations are outdated.

I also don't agree with the specific claim (made or at least implied by NIST) that a single 96-bit deterministic nonce isn't limited to 2³² blocks. The counter block will wrap around regardless of how the nonce was generated, because the GCTR function that is used to compute the ciphertext and authentication tag sets CBᵢ = inc32(CBᵢ₋₁) and CB₁ = ICB = inc₃₂(J₀) with J₀ a function of the nonce and inc₃₂ only incrementing the bottom 32 bits. Modern recommendations do not make this distinction around how the nonce was generated and I see no justification made for it by NIST. Perhaps it was meant to apply to the case where a portion of the nonce was implicit and thus not sent or stored in the clear, but deterministic generation doesn't always mean partially implicit nonces and the implicit part is too small (usually 32 bits) and too easy to obtain (often derived from a hardware identifier) to provide any additional security anyway.

Using any nonce lengths other than 96 bits is not recommended today, regardless of the recommendations in 2007. Shorter lengths are obviously a poor choice, but longer lengths are not always supported by implementations. Moreover, while the published standard supports various lengths (with support for <96 bits marked for removal), the invocation of the GHASH function and its effect on nonce entropy is not well studied AFAIK and all nonces other than 96 bits are fed into GHASH. Thus, one shouldn't use a nonce longer than 96 bits, which means the birthday paradox can become a real problem if the same key is used to encrypt a large number of messages, each with different nonces. A single or relatively small number of CSPRNG-generated nonces for the same key is usually okay; a lot is a problem. This problem is a major reason why AES-GCM-SIV, XChaCha20-Poly1305, and XAES-256-GCM even exist.

[kbolino]

For some elaboration on my issues with NIST recommendations, let us consider NIST's response to public comments from 2021:

NSA raised the issue of "Counter wrapping, or integer overflow, because counter is 32 bits" to which NIST replied that "WITH CURRENT COMPUTING ABILITIES [...] Counter should not overflow". I find that to be a thoroughly inadequate response. Obviously current computing capabilities can overflow a 32-bit counter. That also translates (as NSA also pointed out) to 68GB of data encrypted with the same nonce, which is still "a lot" for some use cases, but easy to exceed for other use cases in the age of terabytes and petabytes.

On the issue of nonce reuse specifically, NIST respond to NSA's concerns with 'Generate a new 96-bit nonce for each message using a cryptographically strong PRNG. Re-key at reasonably regular intervals, where "reasonably regular" is defined by how much data and how many messages are being encrypted'. I think that broadly validates what I said. However, "reasonably regular" is not actionable guidance, and it is not always possible to re-key easily.

https://csrc.nist.gov/csrc/media/projects/crypto-publication...

[kbolino]

I framed that as NIST responses to NSA concerns, but on re-reading, it seems that the table I'm quoting is entirely produced by the NSA. This doesn't really affect the substance of what I wrote with regard to technical details, but I may have misattributed statements to NIST that came from NSA.

[tptacek]

They're not wrong, and the limited nonce space in standard GCM is one of the most common problems cryptography engineers have with GCM.