AES-GCM recommended IV size: Why 12 bytes?

Question

When using AES-GCM, a 96-bit IV is generally recommended. Most implementations I've seen also use 96-bit. However, I'm unsure on where this recommendation or convention comes from.

Let's assume a shorter IV is bad. Assuming all other constraints for IV generation are still met, would using a longer IV necessarily have a negative security impact, or severe performance impact without adding any security benefit?

For instance, an answer in Ciphertext and tag size and IV transmission with AES in GCM mode specifically states

For GCM a 12 byte IV is strongly suggested as other IV lengths will require additional calculations.

I'm very interested in this statement, but I'm unable to find an explanation on these "additional operations" or other security implications of when using a longer IV. The NIST Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC did not clarify this for me.

So is there any specific reason for everyone using 12 bytes, or is everyone just following convention?

Answer 1

From the proposal of GCM (rewritten if statement):

if $\operatorname{len}(IV) = 96$ then $Y_0 = IV || 0^{31}1$ else $Y_0 = \operatorname{GHASH}(H, \{\}, IV)$.

So there are additional calculations for IV's other than 96 bits. This is why the original proposal has this recommendation:

96-bit IV values can be processed more efficiently, so that [ed: this] length is recommended for situations in which efficiency is critical.

but also in the security section it is explained that the IV-processing of GCM was not previously taken into account for GHASH:

Counter mode was suggested in 1979 by Diffie and Hellman [21], and was shown to be secure in a strong, concrete sense by Bellare et. al. [22]. While the proof of security for GCM rests on those proofs, there are some differences. The derivation of the hash key $H$ from the block cipher key $K$, the hashing of the $IV$, and the use of that key for both IV-processing and message authentication are important details.

---

NIST SP-800 38D has a whole chapter - chapter 8 - dedicated discussing key and IV uniqueness and the maximum number of invocations of GCM.

If the uniqueness of the IV / key combination cannot be met then security of GCM fails catastrophically.

Then again, that goes for any other cipher as well, particularly those build upon CTR mode encryption (which includes GCM, but also EAX, CCM etc.).

---

My suggestion is that if you've got small but unique IV input that you expand that input yourself to 12 bytes, if possible according to the hints in NIST SP-800-38D: 8.2.1 Deterministic Construction.

If it is not possible to generate a value that is unique and 12 bytes or below then you might want to consider a fully random IV consisting of 12 bytes.

Answer 2

In the general case, the security goal is to reduce the probability that the internal 128-bit counter block ever takes the same value when instantiating the GCM cipher with a given key. That is catastrophic in combination with the CTR mode.

The best strategy to minimize such probability depends on how the IV is generated.

Case 1: IV is deterministic, 96 bits long

If the IV is deterministic, it means that the sender has access to a reliable mechanism (like a counter) to produce a sequence of unique values through all invocations done with the same key.

A 96 bit IV is directly copied into the counter block, so the uniqueness properties of the counter directly transfer to the counter block. The IV (and the counter block) will only repeat after $2^{96}$ invocations, which is a huge number.

The NIST specification concedes you can actually fix 32 bits of the IV to context information, and just have a 64 bit counter.

Case 2: IV is deterministic, but longer than 96 bits

If the IV is deterministic but longer than 96 bits, the uniqueness properties of the counter do not transfer to the counter block.

Now you have to consider the consequences of the birthday paradox because the initial counter block will now be a digest of the IV. Specifically, you end up with 96 randomized bits in the counter block that may collide.

You are likely to hit a collision with 50% probability after $2^{48}$ invocations. If order to reduce the probability below $2^{-32}$ (as required by NIST), you must stop much earlier, before $2^{32}$ invocations.

Case 3: IV is random

If the IV is created randomly at each invocation, the birthday paradox kicks in with 96 bit nonces too. You will need to invoke the cipher with the same key no more than $2^{32}$ times in all cases.

Conclusion

The recommendation to use a 96-bit nonce is motivated by interoperability (i.e. it's easier if everybody uses one length only) and efficiency.

A 96 bit nonce is more secure than longer nonces only when combined with a counter (and - informally - only if you create a lot of ciphertexts under the same key). A longer nonce is not less secure in case nonces are generated randomly (which is by far the most common approach).

Bootnote

As a matter of fact, long random nonces are more secure than 96-bit random nonces, at least in case of short plaintext (i.e. consiting of $<<2^{32}$ blocks). The reason is that in the former case the 32-bit CTR counter field is also randomized, whereas the field is fixed to $0^{31} || 1$ in the latter (see section 7.1 in NIST SP 800-38D).

With long random nonce, you may witness a clash in the initial counter block with the target probability $2^{-32}$ only after $2^{48}$ invocations, which is a better bound than what you get with a 96-bit long random nonce.