Multi-target attacks on AES-CTR with a random nonce

Question

128-bit block ciphers are vulnerable to multi-target attacks where the attacker seeks to attack a collection of keys instead of a single key. A simple example:

• Generate keys $k_1, k_2, ...,k_{2^{40}}$.
• Pick a 128-bit message block $m$ and provide $m$ to the attacker.
• Compute $E(k_1, m), E(k_2, m), ..., E(k_{2^{40}}, m)$ and provide these ciphertexts to the attacker.
• The attacker can compute $E(k, m)$ for various keys $k$ finding a ciphertext that matches one of the ciphertexts provided. This will take $2^{87}$ evaluations of $E$ on average.

I'm interested in what practical impact this has on the CTR mode of operation. Some amount of known or controlled plaintext is clearly required for the attacker to get the block cipher output. More importantly, this attack depends on the block cipher being fed the same plaintext block across many keys.

CTR mode encrypts blocks as $E(k, n \| c) \oplus P$, where $P$ is the plaintext block, $n$ is the nonce and $c$ is the block index. Protocols that generate nonces deterministically would seem to be vulnerable to this attack.

My question: is it possible to adapt this attack to work against protocols that use CTR mode with a random nonce? Does randomizing the nonce successfully protect CTR mode from multi-target attacks?

Answer 1

Some amount of known or controlled plaintext is clearly required for the attacker to get the block cipher output.

Actually, that's not much of an issue; we can often get a reasonable amount of known plaintext from real encrypted messages. In fact, the known plaintext for each message doesn't have to be the same, and you don't have to have completely known plaintexts; a sufficient number of linear equations in the plaintext will work.

More importantly, this attack depends on the block cipher being fed the same plaintext block across many keys.

Yes, that is key. CTR encryption is:

$$C = AES_k(n) \oplus P$$

This multitarget attack works by evaluating (for a test $k$) $AES_k(n)$ once, and then using that to check all plaintext, ciphertext pairs in parallel (say, by comparing that value to the list of $C_i \oplus P_i$ values you have precompiled.

However, this works only if every plaintext/ciphertext pair had the same $n$. If each one used a different $n$, then you'd have to evaluate $AES_k(n)$ separately for each plaintext/ciphertext pair; in that case, you're no better off than picking one message, and just bruteforcing that.

This protection isn't a novel idea; for both TLS and IPsec, the GCM RFC's ask that 32 bits of random (actually, KDF derived) salt is included in the nonce, specifically to frustrate this type of attack.