CTR Mode and Chosen Plaintext Attacks

Question

P.71 of Cryptography Engineeering states "Any weakness in CTR encryption mode immediately implies a chosen plaintext attack on the block cipher." It seems to me that "any weakness" is vague. I'm not quite getting what the author has in mind. Can someone please elaborate?

EDIT:

The purpose of the statement seems to be to highlight the relationship between the security of the block cipher and CTR mode - a break of CTR implies a break in the underlying block cipher (except information leakage and traffic analysis). I don't see how a break of CTR means the break in the block cipher is necessarily of the chosen plaintext variety.

Answer 1

Suppose you know a way to distinguish a message encryption scheme of the form $$\operatorname{CTR}[E_k](n, m) = (E_k(f(n, 0)) \oplus m_0) \mathbin\Vert (E_k(f(n, 1)) \oplus m_1) \mathbin\Vert \cdots$$ for unknown $k$ from a uniform random string with probability better than you would get for CTR mode $\operatorname{CTR}[\pi](n, m)$ of a uniform random permutation.

Here $f$ is a standard injection from nonce/counter pairs to cipher blocks (say, $(n, i) \mapsto n \mathbin\Vert i$ on 96-bit nonces and 32-bit counters), $n$ is a nonce, and $m$ is a message $m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots$. Note that there is always a generic birthday attack on CTR mode, so the premise is that you have a distinguisher with higher success probability than the generic birthday attack for the same number of queries to the oracle.

How could you use this to distinguish $E_k$ for uniform random $k$ from a uniform random permutation $\pi$? You are allowed to feed in $f(n, 0)$ and throw $m_0$ into the mix if you know some $n$ and $m_0$ that lets you break $\operatorname{CTR}[E_k]$, for example—it is a chosen plaintext attack.

Answer 2

The technical answer was given already. I just wanted to add that your question is fully justified and this is why exact definitions are so important in this field. The correct formulation of this claim is:

"If CTR mode is not secure (indistinguishable) against chosen-plaintext attacks as encryption, then the block cipher is not a pseudorandom permutation/function."

Formally, the definition of a pseudorandom function is a type of "chosen plaintext attack", so this is the minimal notion. Furthermore, saying "any weakness" is very problematic. Specifically, CTR mode is NOT secure against a chosen-ciphertext attack; is that a weakness?

Anyway, this is just a rant about the importance of being precise.