# Is there a strong cryptographic reason for GCM's 2^39 - 256 bit limit, why Not 2^39 [duplicate]

While examining the initial GCM specification by McGrew and Viega in 2005, it appears that the formation of the 128-bit Initialization Vector by combining a 96-bit nonce and a 32-bit unsigned wrapping counter seems somewhat random. This choice results in a repetition of the scrambling pattern every 2^32 16-byte blocks. During the analysis, it is puzzling why they subtracted 256 bits from 2^39 instead of utilizing 2^7 * 2^32 = 2^39 for the calculation. This decision to subtract 256 bits deviates from the expected outcome based on a straightforward multiplication of 2^7 and 2^32, resulting in 2^39.

• Does this answer your question? What if an AES GCM nonce overflows and collides with the GHASH nonce (0^128)? The extra two blocks are used inside AES-GCM to choose the GHASH key for authentication Commented Nov 22, 2023 at 18:56
• Huh, I don't see that defined there. Commented Nov 22, 2023 at 19:41
• @MaartenBodewes Ah, it was here Commented Nov 22, 2023 at 19:46
• Too much part of a different question to me. I've answered. Commented Nov 22, 2023 at 21:21

Let's assume that GCM is used with a default sized IV: a 12 byte nonce. Let's, for demonstration purposes, assume that we start off with an IV / nonce set to all-zero.

The first steps in GCM show how:

1. Let $$H = \operatorname{CIPH}_K(0^{128})$$ - this is identical to the encryption of an all zero counter if the IV / nonce is set to all zeros;
2. If $$\operatorname{len}(IV)=96$$, then let $$J_0 = IV \| 0^{31} \|1$$ - so here the initial counter for CTR mode is set to value 1;
3. Let $$C=\operatorname{GCTR}_K(\operatorname{inc32}(J_0), P)$$.
4. ...
5. ...
6. Let $$T=\operatorname{MSB}_t(GCTR_K(J_0, S))$$ - and here are the rest of the counter values used.

So as you can see, the first block of all zero is used in step 1 if the IV is all zero, and the second counter counter calculated in step 2 is used to encrypt the value $$S$$ in step 6, which is the outcome of the GHASH over the ciphertext and the additional data.

This removes two 128 bit blocks or 256 bits from the total amount of bits available for the key stream generated by the counter mode, and as many bits from the plaintext that can be kept confidential by a single call to GCM.

• "This removes two 128 bit blocks or 256 bits from the total amount of bits available for the key stream generated by the counter mode..." but notice that in step 1. above it uses $\operatorname{CIPH}_K$ not the $\operatorname{GCTR}_K$ in Counter mode. Another caveat is that step 6. is not what happens in GCM and once again $\operatorname{CIPH}_K$ is used on J0 which is then xor-ed with tag from GHASH. In original paper it says T = MSBt(GHASH64(H, A, C) ⊕ E(K, Y0)) so no two blocks from Counter mode are actually wasted.
– wqw
Commented Dec 15, 2023 at 21:08
• 1. It uses $\text{CIPH}_k$ over an all zero block, which collides with an all zero "IV" / nonce and zero based counter. 2. Similarly, for a 12 byte nonce, the formula for $J_0$ does collide with a nonce and counter value 1 (31 zeros followed by a 1). Commented Dec 15, 2023 at 21:22
• This makes sense. They should have used something like Incr(IV) || Counter for these two blocks to leave full 2^32 blocks for the counter mode. I’m honestly sometimes baffled by odd choices in reputable and widely used constructions made by professionals :))
– wqw
Commented Dec 15, 2023 at 21:45
• Cryptographers also think that having 96 bits / 12 bytes for the nonce is a bit on the low side; remember that for random nonces the birthday bound should also be taken into account. This is one reason for larger block sizes - but then GMAC would have to be fit to them as GMAC is inherently 128 bits. Your construction makes this collision more probable, so it's not that easy (I'll not go into a counter as nonce, that should be evidently a problem from the start). There is something to be said to go for ChaCha20 or simply HMAC (etc.) instead of GCM. Commented Dec 15, 2023 at 21:49
• That is a different question, I would not be surprised if having a SIV alters the situation. Commented Dec 16, 2023 at 15:37