Why is it good to split a CTR-mode counter into nonce and counter?

Question

When discussing the CTR mode of block ciphers, Wikipedia says the following:

Simply adding or XORing the nonce and counter into a single value would completely break the security under a chosen-plaintext attack.

I don't understand the difference between the split nonce/counter design and simply using a random value and incrementing. Why is using nonce +/⊕ counter insecure whereas nonce || counter is secure?

I don't see the difference between a split nonce/counter and nonce +/⊕ counter. At first glance, isn't split nonce/counter mode the same as concatenating a bunch of 0 bits to the nonce and using nonce +/⊕ counter mode?

(By "+/⊕", I mean either addition or XOR, since it doesn't seem to matter which is used for this purpose.)

Answer 1

Suppose you do CTR mode as:

$E(k,nonce+1) \oplus m_1$, $E(k,nonce+2) \oplus m_2$, $E(k,nonce+3) \oplus m_3$, etc.

The wikipedia page is talking about a non-random nonce, with a specific example of a packet counter. So suppose $nonce$ is a packet counter and in each packet you encrypt several blocks. You might end up with the following:

In packet #$p$:

$E(k,p+1) \oplus m_1$, $E(k,p+2) \oplus m_2$, $E(k,p+3) \oplus m_3$, etc.

In packet # $p+1$:

$E(k,(p+1)+1) \oplus m'_1$, $E(k,(p+1)+2) \oplus m'_2$, $E(k,(p+2)+1) \oplus m'_3$, etc.

The nonces are unique, but CPA security is broken. You have used $E(k,p+2)$ as a mask twice, and are leaking the value of $m_2 \oplus m'_1$.

Answer 2

I don't understand the difference between the split nonce/counter design and simply using a random value and incrementing. Why is using nonce +/⊕ counter insecure whereas nonce || counter is secure?

Here's the context of your Wikipedia quote (my bold):

If the IV/nonce is random, then they can be combined together with the counter using any lossless operation (concatenation, addition, or XOR) to produce the actual unique counter block for encryption. In case of a non-random nonce (such as a packet counter), the nonce and counter should be concatenated (e.g. storing nonce in upper 64-bit and the counter in lower 64-bit). Simply adding or XORing the nonce and counter into a single value would completely break the security under a chosen-plaintext attack.

With a random nonce it's perfectly fine to use the whole 128 bits for the nonce and add the counter value to that. Unless you have some way to make sure your nonces don't collide, it's probably the best way to go, even, since it gives you the lowest probability of colliding inputs.

However, with non-random nonces it is in general not, and CTR nonces don't need to be random. Mikero shows the case of a counter in the other answer, but similar attacks would be possible for e.g. monotonically increasing clocks (with a long enough message first).

---

(By "+/⊕", I mean either addition or XOR, since it doesn't seem to matter which is used for this purpose.)

Well, XOR allows you to go "backwards" while addition does not, so there are nonce strategies where addition would be fine, but XOR not. For example, always starting from a nonce of (previous nonce + previous message length).

Answer 3

The answer is that it depends very much exactly on what you are considering. However, better bounds can be achieved by using a 96 bit nonce and a 32 bit counter. This is certainly true for GCM as was proved in this paper (Breaking and Repairing GCM Security Proofs). Note that GCM uses CTR inside, so this is relevant.