Unpredictability and non-secret IVs

Question

There are two main properties of an initialization vector (IV): Randomness and Predictability. In most cases, the IV is not kept secret and known to anybody. Say for CBC mode, we need to ensure that the IV is unpredictable because of (adaptive) chosen plaintext attack. So, since the IV is already known, how does predictability address the attack? Rather, why would one still need to predict the value of the IV when it is usually known? I am confused and hope to understand better, thanks.

Answer 1

In an adaptive chosen plaintext attack, the adversary is given the opportunity to query an oracle for encryptions of messages of the attacker choice. In a CPA attack against CBC, for each query the oracle chooses a fresh IV at random, CBC-encrypts the adversary's message with that IV, and returns the IV-prefixed ciphertext.

One consequence of this is that the adversary only learns the IV that was chosen to encrypt their plaintext after they've made the query. This is what "non-secret but unpredictable" means in this context.

Predictable IVs would mean that the adversary is able to learn what IVs will be used before choosing the messages to query for. In that case the adversary can cancel the effect of the IVs by XORing their binary complements to the first blocks of the messages they query. For example, if the adversary knows that the next IV will be $\mathrm{IV}_i$ they can query for the encryptions of $\overline{\mathrm{IV}_i} \oplus P_i$ (for a one-block plaintext $P_i$), and they get:

$$ \begin{align} C_i &= \mathrm{IV}_i \| E_k(\mathrm{IV}_i \oplus \overline{\mathrm{IV}_i} \oplus P_i) \\ C_i &= \mathrm{IV}_i \| E_k(P_i) \end{align} $$

So they've basically tricked the oracle into revealing what $P_i$ encrypts to with an all-zero IV.