17
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ GCM runs CTR internally which requires a 16-byte counter. The IV provides 12 of those, the other 4 are an actual block-wise counter. If you supply a larger-than-12-bytes IV then it needs to be "hashed" allowing collisions to happen and raising the risk for (devastating) IV reuse unneccessarily high. Similar could happen with shorter IVs (if they're being post-processed, I don't know for sure) or you have similar problems anyways because there's less space to pick a unique IV from. $\endgroup$ – SEJPM Nov 17 '16 at 10:30
  • 1
    $\begingroup$ GCM simply performs these calculations to re-generate a 12 byte IV from the given bytes if I remember correctly. And those calculations can therefore only be detrimental to security, never better. $\endgroup$ – Maarten Bodewes Nov 17 '16 at 11:15
  • $\begingroup$ When the IV is 96-bit long, the 4 byte counter for the internal CTR cipher is always 1. When the IV has a different length, the 4 byte counter for CTR is taken from the GHASH of the IV - so it is uniformly randomized across 32 bits. That means that - when the IV is taken from an RNG, which is what everybody does - due to the birthday paradox it seems more secure (though slower) to supply a non-standard 128-bit IV than a standard 96-bit IV. $\endgroup$ – SquareRootOfTwentyThree Jan 8 at 20:55
17
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Maarten, this answer will be much better if you add the results and link to your other answer $\endgroup$ – kelalaka Jan 5 at 9:57
  • $\begingroup$ I think you just did that :) But this question was particularly for when the IV was 96 bits, not different from 96, so if you don't mind I'll leave the answer alone. Unless you meant something else, in which case I'm happy to be corrected. $\endgroup$ – Maarten Bodewes Jan 5 at 11:50
  • $\begingroup$ Yes :) The result of the if statement wasn't clear for me without deeper understading of Ghash. $\endgroup$ – kelalaka Jan 5 at 12:03
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.