Randomness and increment of nonce in GCM

2 questions about nonce usage in GCM:

• Is it safe to use non-random nonce in GCM? Say I use 0x1 for m1, 0x2 for m2, so on.
• How much should a nonce increased for a file? Say I use 0x1000 as a nonce to encrypt a 1000x block size file (128,000bits). Then should the next safe nonce to use for the next file be simply 0x1001, or after addition of the number of blocks used, i.e. 0x2000?

1 Answer

Is it safe to use non-random nonce in GCM? Say I use 0x1 for m1, 0x2 for m2, so on.

It is perfectly safe to use a non-random nonce in GCM, as long as you never reuse a nonce for two different messages. So, if you use the message count for the nonce, that's fine; if you accidentally forget that you used nonce 0x5 for a message, and use that again, well, that's not so fine.

How much should a nonce increased for a file?

The file size doesn't matter; use any increment you want (other than 0). You don't have to increment the nonce more for large files.

• If 96 bit nonces are used, then only 68 GB ($2^{36}$) can be safely encrypted for AES. Dec 11, 2015 at 14:02
• So you mean it's even fine to start counting from 1? And for counter increment, my unclear understanding is how internally GCM generates the encryption stream. My assumption was that it use the nonce as a start ctr, and for i-th block, it generates an E(k, ctr + i) to xor the i-th message block. (I know there is something different for the first 1 or 2 blocks, but I assume this scheme generally applies). My concern was if that's true, and if I increment the counter by 1, it may collide with the 2nd block of the previous message.
– Vin
Dec 11, 2015 at 14:38
• @Vin: yes, iit's fine to start counting from 1, and nope, collisions won't happen. If you look at the internals of GCM, you'll see that a 96 bit nonce is placed in one section of the 128 bit counter block, while the block counter is placed in another section; there's no chance that the blocks between different messages would collide. Dec 11, 2015 at 14:41
• @ArtjomB.: are you referring to $2^{36}$ bytes in a single message? GCM can't handle messages larger than that (no matter what the nonce size is). Dec 11, 2015 at 21:43
• If 96 bit nonces are used then 32 bit counter can only produce $2^{32}$ different blocks at 16 bytes per block. If nonce+counter repeats for some block between two ciphertexts then the same (partial) keystream was created and the plaintext may be deduced based on XOR. So the limit is $2^{36}$ B and "The file size doesn't matter" is factually incorrect. Dec 11, 2015 at 21:43