Why this complexity defining AES-GCM counter block?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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!