Why this complexity defining AES-GCM counter block?

AES-GCM counter block is defined as nonce || IV || counter. Why this complexity? Knowing that it does not need to be secret and its only required property is to be unique, why not use a 128 bits true random number for the whole block? The counter instead of starting at 0 will start at some random value, wrapping around when reaching maximum value.

• Problem to this approach: You're hosed if you generate randomly two successive (or with a small additive distance) starting blocks. – SEJPM Feb 5 '18 at 19:54
• @SEJPM What are the chances of that happening with 128 bits? – user3368561 Feb 5 '18 at 20:03
• Indeed the chances of this happening for properly sampled values is quite low, however this also requires you to impose a stronger structure on the nonces (requires uniform randomness), as opposed to the current uniquness which make eg counters valid as nonce / IV input to GCM. – SEJPM Feb 5 '18 at 20:05
• @SEJPM Of course it has some cons, but current approach is not free of them. Nonce reuse isn't an easy problem in parallel/distributed systems. In the end, you also need a good random source to generate the secret key. – user3368561 Feb 5 '18 at 20:11
• Note that it is perfectly possible to use a 96 bit random nonce in the nonce || counter. As it is only 96 bits you should restrict the number of messages to a low $2^{32}$ or so, but that's something you'd have to do with a 128 bit random IV as well. – Maarten Bodewes Feb 6 '18 at 16:20

Knowing that it does not need to be secret and its only required property is to be unique, why not use a 128 bits true random number for the whole block? The counter instead of starting at 0 will start at some random value, wrapping around when reaching maximum value.

First, imagine you're encrypting a sequence of messages with an ephemeral key scoped to the session. If you're using random 128-bit IVs, those need to be communicated along with each message, which is an overhead. With counter nonces the two parties can just start from zero and increment the nonce for each message.

Note that this is a generic advantage of nonces over random IVs like used in CBC. So if you dive deeper into this, the question becomes rather about the relative merits of nonce-based vs. random IV-based ciphers. GCM has chosen to be nonce-based, so it doesn't demand random IVs to start with.

Second, the concatenated IV guarantees an injective property: the IVs for the messages encrypted with two different nonces will never collide for any block of the messages. With your proposal, on the other hand, it's possible for some of the blocks in one message to be encrypted with the same keystream as some of the blocks in a second message, even though different nonces were used.

You might think the probability that this would happens is low, but the more precise statement is that the probability that it happens depends on the volume of data you encrypt with the same key. This means that statements about how much data you can securely encrypt with the same key get more complicated, for no good reason.

Going back to the choice of nonce-based vs. random-IV based cipher, if a cipher has chosen the former, it's just a good idea for the function that combines the nonce and block counter to be injective. It makes reasoning about these issues simpler when you can just say straightforwardly that the maximum message length is such-and-such.

• First problem is solved initializing first block with a random IV and subsequent ones as with a counter nonce. Second problem is another thing. Now I see the problem of overlapping IV with the counter. Effectively, you only get 96 bit IV, not the expected 128 bits, so its collision resistance maybe to low. – user3368561 Feb 6 '18 at 0:04

AES-GCM counter block is defined as nonce || IV || counter

That is not true. AES-GCM effectively has two different versions. If you have a 96 bit nonce, then the counter block is (by your terminology) $$nonce || counter$$

However, if the nonce is any other size, it computes a temp value $J = GHASH(K, Nonce)$, and then makes the counter block

$$J \boxplus counter$$

(where $\boxplus$ is addition which ignores the carry from bit 31 to bit 32).

As $J$ is effectively a random number, this second possibility is mostly what you are suggesting.

Now, it has since been found to have inferior security properties compared to the first idea (the proof had a flaw), so I don't suggest you actually use it

• Can you add a link to the proof, please? It isn't the case that this construction is weaker because J isn't a true random number? – user3368561 Feb 5 '18 at 23:52

First, usually AES-GCM is defined with just nonce and counter—if the term ‘IV’ appears, it is typically a stand-in for ‘nonce’; there's no separate nonce and IV parameters. So the input to the AES permutation is $n \mathbin\Vert c$, for a 96-bit nonce $n$ and 32-bit counter $c$.

The question is whether we can safely use $n + c$ for a 128-bit nonce and 32-bit counter instead. The answer is yes, at the cost of some security.

• When each nonce is guaranteed to be unique, as in a message sequence number, then $n \mathbin\Vert c$ is also guaranteed to be unique for every message block in every message, and the only thing we have to worry about is birthday distinguishers on CTR mode.

• When nonces are chosen randomly, there is some nonzero probability of getting the same value of $n_0 + c_0$ and $n_1 + c_1$ for two message blocks in different messages—and thus some nonzero probability that you will reuse the one-time pad that is your AES-CTR stream, which gets you in trouble.

Sometimes that cost in security comes at a benefit: AES-SIV of RFC 5927 does more or less this—derives an initial counter block $n$ pseudorandomly from the plaintext for use in $n + c$ as the AES input. (Actually it is $n - (n \bmod{2^{32}}) + (n + c \bmod{2^{32}})$ but the difference is immaterial.)

This comes at the cost of smaller limits on the total volume of data encrypted and authenticated—but AES-SIV is itself a nonce-misuse-resistant authenticated encryption scheme, which takes a ‘nonce’ of its own as a parameter but unlike AES-GCM provides security even if you reuse the nonce. The way it breaks down is that if you reuse a nonce and encrypt the same message, the adversary can tell that the message was the same because the ciphertext is the same.

Helpfully, RFC 5297 does not actually advise what volumes of data are safe; thus it is an exercise to the reader to estimate the probability that you're in trouble as a function of the number and size of messages!

• Oh, well, I had a long conversation with an RFC author that got the amount of plaintext bytes wrong, so it could be worse. – Maarten Bodewes Feb 6 '18 at 16:12