7
$\begingroup$

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.)

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ This is still a problem if you have a split counter, though, isn't it? $\endgroup$ – immibis Sep 6 '15 at 19:29
1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This - in my opinion - doesn't seem to answer the question. $\endgroup$ – Maarten Bodewes Aug 17 '15 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.