Attacking CBC with predictable but encrypted IV

Question

Let P be a secure block cipher, eg AES-128.

Let's say a server has a CBC encryption oracle which uses an attacker-selected yet unique nonce to generate the IV for each message = P(key, nonce). The same key is used to generate the IV from the nonce as to encrypt the message.

This system is not semantically secure against an attacker who can choose plaintexts and nonces (with the stipulation that all nonces must be unique).

A similar system with predictable (but unencrypted) IV has the vulnerability where an attacker can make a guess as to the contents of a target ciphertext.

Is there a comparable attack on this system?

Does this attack still hold if the nonce is merely predictable (ie a counter) instead of attacker selected?

Can this attack work if there is a restriction against sending blocks containing zero-vectors to the oracle?

Answer 1

Generating the IV for CBC mode by encrypting a counter is one of the IV generation methods recommended in NIST SP 800-38A, Appendix C:

"There are two recommended methods for generating unpredictable IVs. The first method is to apply the forward cipher function, under the same key that is used for the encryption of the plaintext, to a nonce. The nonce must be a data block that is unique to each execution of the encryption operation. For example, the nonce may be a counter, as described in Appendix B, or a message number. The second method is to generate a random data block using a FIPS-approved random number generator."

This scheme is also endorsed by the classic paper by Bellare et al., "A Concrete Security Treatment of Symmetric Encryption" (2000):

"To make a proper counter version of CBC, one can let the initialization vector be $y_0 = f(ctr)$ and increment $ctr$ by one following every encryption. The scheme is capable of encrypting at most $2^l$ messages. An analog to Theorem 17 is then possible. The result is easiest (following as a corollary to Theorem 17) if the key used to determine $y_0$ is separate from the key used for the rest of the CBC encryption."

Alas, their proof is somewhat hard to follow for the casual reader, and frankly, the alternative proof given by Wooding in "New proofs for old modes" (2008) is not much better.¹ At least the author is kind enough to summarize their conclusions:

"We prove that CBC mode is still secure if an encrypted counter is used in place of a random string as the IV for each message."

Indeed, for a reasonably readable proof sketch, you could do worse than take a look at this answer by Seth right here on crypto.SE.

---

All of these proofs, however, assume that the counter sequence is predetermined. If the attacker can choose counter values, things fall apart.

In particular, given a known plaintext/ciphertext pair $(P = P_1 P_2 \dots P_n, C = C_1 C_2 \dots C_n)$, an attacker can force the IV to equal any ciphertext block $C_i$ (for $i \ge 2$) by choosing $C_{i-1} \oplus P_i$ as the nonce.

Among other things, this allows the attacker to check whether a ciphertext block $c_j$ (and the preceding block $c_{j-1}$) in another message corresponds to a guessed plaintext $p_j$ by submitting the message $c_{j-1} \oplus p_j \oplus C_i$ for encryption, using the nonce $C_{i-1} \oplus P_i$, and checking whether the first block of the resulting ciphertext equals $c_j$. This is exactly analogous to the attack based on predictable IVs that you refer to in your question.

---

^{1) Actually, the main issue with the Wooding paper is a profusion of notation. If you can remember what all the variables and functions stand for, it's actually fairly clear. Still, I'd like to know who (besides, obviously, the author) considered something like "$\scriptstyle \mathcal E\text-CBCH^{\mathcal P^\ell,c,V_0}_{n_L,0,n_E}$" a reasonable notation for an encryption scheme.}