# Why restrict nonce/IV and counter to specific sizes?

When setting up a nonce/IV and counter (e.g. for AES-GCM-128), why are the nonce/IV and counter restricted to specific sections (e.g. random nonce/IV in first 8 bytes and counter in last 8 bytes)? This results in the last 8 bytes always starting off at a predictable value (0), reduces uniqueness (only 8 bytes of random data), and requires more frequent re-keying due to counter wrapping.

Is there a reason the entire 16 bytes cannot be initialized to random data, start the counter from there, and allow the counter to use the entire 16 bytes?

-
Where did you read that the counter section is 8 bytes and only 8 bytes? –  mikeazo Jul 3 '13 at 14:45
In the case of nonce we don't really care about predictability, we only require it to be a value that doesn't repeat throughout the session. Yes many crypto software start their nonces at 0. I don't recall any schemes having specific IV size limits, maybe I'm missing something? –  rath Jul 3 '13 at 14:54
@rath That isn't always the case. Sometimes the term nonce has some sort of randomness associated: crypto.stackexchange.com/a/8498/706 –  mikeazo Jul 3 '13 at 15:02
@rath Also, sometimes (or maybe often) counter mode is presented as splitting the IV/nonce portion and the counter portion (e.g., 8 bytes for IV/nonce and 8 bytes for counter). See Wikipedia CTR –  mikeazo Jul 3 '13 at 15:07
I didn't mean to imply an 8 byte nonce, 8 byte counter was a requirement. I've just noticed it's common for specs to recommend a split like that (or 12/4) and I wasn't sure why. –  skillzero Jul 4 '13 at 8:03

The answer is that you can do exactly what you say. Initialize the counter to a random 16 byte number and start counting. Wikipedia (not sure if that is where you got the idea that it must be 8 bytes and 8 bytes) has the following note:

The IV/nonce and the counter can be combined together using any lossless operation (concatenation, addition, or XOR) to produce the actual unique counter block for encryption.

There is some benefit to separating things though. For example, splitting it into 8 bytes and 8 bytes, as long as you never generate the same 8 byte nonce/IV while using the same key, your encryption stream will never repeat. Further, you know exactly how many nonces/IVs you can generate before expecting to see a repeat ($2^{32}$ from the birthday paradox) with about a 0.5 probability. In a submission to NIST by some very reputable cryptographers, this method of doing CTR mode was called "the recommended usage scenario".

Lets instead assume you generate a 16 byte nonce/IV and just start incrementing it. What happens if two nonces/IVs have a difference of 1000 (i.e., $|n_1 - n_2| = 1000$). Well, after encrypting 1000 blocks (with the same key) you will now be using the same encryption stream. Analyzing this is a bit more tricky as you need to know the probability of generating two nonces that are within some range of each other (the range being determined by how many blocks you will encrypt). Depending on the application this could be a major problem. My guess though is that in the majority of applications it isn't a problem.

-
Thanks for the response. Regarding two nonces/IVs having a difference of 1000/etc, wouldn't reducing the random nonce portion (and initializing the counter portion to 0) increase the probability of having a small difference due to the smaller nonce space? –  skillzero Jul 4 '13 at 8:10
@skillzero, if the nonce/IV portion and the counter portion are separate, the difference between two nonces doesn't matter. –  mikeazo Jul 4 '13 at 11:26
But in order for the difference between nonces to be within 1000, it would mean the first 118 bits of both random nonces would need to be the same (128 - log2(1000) = ~118 bits). If that were the case then using a smaller nonce portion (e.g. 8 bytes) would hit that case much more frequently because only the first 64 bits would need to match (54 fewer bits of uniqueness) since the remaining counter bits would be 0. Or is there something I'm missing? –  skillzero Jul 4 '13 at 15:32
@skillzero, with it split 8 and 8, the 8 byte nonce part never increments. You only increment the counter portion. Thus, even a nonce portion of 1000 and then 1001 (a difference of only 1) is okay. –  mikeazo Jul 4 '13 at 16:22
With a 16 byte nonce/counter, the upper 8 bytes would only increment after 2^64 bytes (where 8/8 would wrap and collide). Are you saying that if the full thing is random (8 digits total to illustrate), I might get 10010000 and 10009999 (collides after 1 byte), but with a 4/4 split, the 9999 would be truncated to 0 and they would start at 10010000 and 10000000 and wouldn't collide until the 10000th byte? –  skillzero Jul 4 '13 at 18:12