# Is there a strong cryptographic reason for GCM's 2^39 - 256 bit limit?

In reading through the original GCM specification (McGrew & Viega '05), the composition of the 128 bit Initialization Vector as a concatenation of a 96b nonce and a 32b unsigned wrapping counter seems arbitrary and forces the scrambling pattern to repeat every 232 16-byte block.

Is the algorithm expected to be secure for significantly longer stream lengths if for example the IV were a 128b nonce XORed with a 64b or 128b counter, or are there known cryptanalysis issues that begin to arise?

• With concatenation the caller only has to ensure the nonce is unique. For example they can use a counter. If you use xor or add nonce and counter you get overlaps, so a counter as nonce would be fatally broken. – CodesInChaos Jan 27 '15 at 17:15
• I'm pretty certain that neither XOR nor modular addition of a counter harm uniqueness. There is no nonce for which two different counter values XOR or sum to the same value, unlike say with OR or AND. – Jeff Jan 27 '15 at 17:20
• For GCM to be secure the inputs to AES must be unique. With concatenation having a unique nonce (responsibility of the caller) and a unique block counter (part of GCM itself) is enough to guarantee unique inputs to AES. With XOR the caller must make sure that the 128 bit nonces are spaced far enough from each other so that xor-ing the counter doesn't cause a collision. That's annoying. – CodesInChaos Jan 27 '15 at 17:26
• I agree with your point below about needing to scan an entire 64 GiB message before validating the whole is cumbersome, but I think your assertion here about XOR is mathematically incorrect. XOR or modular addition of a constant is a true 1-to-1 mapping of [0,2^n-1] to [0,2^n-1], so it's impossible for a given key and nonce tuple to have two distinct counter values that yield the same E(K, nonce XOR counter) output. – Jeff Jan 27 '15 at 17:38
• I'm talking about using a message counter as nonce. That way you can have a collision between (k, n_1, c_1) and (k, n_2, c_2). – CodesInChaos Jan 27 '15 at 17:41

• With concatenation the caller only has to ensure the nonce is unique. For example they can use a counter that increments for each message. Incrementing a counter for each message is convenient in many scenarios, including encrypted network transports like TLS.

If you use xor or add nonce and counter you get overlaps, so a counter as nonce would be fatally broken.

• The security of GHash, the MAC part of GCM, decreases as the length of the message increases. This means that it's a good idea to limit the maximal size of messages the receiver is willing to accept.

• forces the scrambling pattern to repeat every 2^32 16-byte block"

The pattern doesn't repeat, you simply MUST not encrypt a message longer than that size.

A 64 GiB message is a very unusual for authenticated encryption, since the receiver can't use the data before they verified the MAC on all of it. Typically you split long data into multiple messages, each with their own MAC. That way the receiver can verify individual blocks and then work with the plaintext, safe in the knowledge that it wasn't manipulated.

• The convenience of verifying smaller authenticated messages makes sense, but I don't think your assertions about addition/XOR collisions is true at all, and I've not seen any other claim about the GHash/GMAC fragility at longer message lengths. Do you have any sources on either of these claims? – Jeff Jan 27 '15 at 17:41
• @Jeff: the security proof for GCM states that if you have a valid $N$ block encrypted message, any change to the message (made by someone who doesn't know the AES key) would authenticate with probability at most $(N+2) 2^{-128}$. By allowing large values of $N$ (by allowing long messages), this significantly reduces the integrity guarantees of GCM – poncho Jan 27 '15 at 18:15