security - Why is using a Non-Random IV with CBC Mode a vulnerability?

Question

I understand the purpose of an IV. Specifically in CBC mode this insures that the first block of of 2 messages encrypted with the same key will never be identical. But why is it a vulnerability if the IV's are sequential? According to CWE-329 NON-Random IV's allow for the possibility of a dictionary attack. I know that in practice protocols like WEP make no effort to hide the IV. If the attacker has the IV and a cipher text message then this opens the door for a dictionary attack against the key. I don't see how a random iv changes this. (I know the attacks against wep are more complex than this.)

What security advantage does a randomized iv have? Is this still a problem with an "Ideal Block Cipher"? (A perfectly secure block cipher with no possible weaknesses.)

Answer 1

Predictable IVs can be exploited by chosen plain text.

Pretend that Eve is a DBA at an insurance company. The company collects medical histories from beneficiaries that include a lot of true/false check boxes about medical conditions. This company also happens to its own health insurance provider. Eve realizes that Alice could be blackmailed if she can discover that Alice has a particularly embarrassing medical condition. However, the value in each of these fields is encrypted, so even though Eve is the DBA, she only has access to the cipher text.

In CBC, the IV is XORed (noted by "⊕" below) with the plain text, then run through the block cipher: C₁ = E_k(IV ⊕ P₁).

Since Eve is a beneficiary of the insurance company, she can choose the plain text for her own medical record, and since she is the DBA, she can examine anyone's cipher text. In addition to using predictable IVs, the sloppy application developer did a poor job of validating the application inputs. If Eve can predict the IVs that will be applied to her (IV_eve) and Alice's (IV_alice) records in advance, she can choose the plain text for her own record like this: P_eve = IV_eve ⊕ IV_alice ⊕ "false"

The application encrypts this plain text like this:

C_eve = E_k(IV_eve ⊕ P_eve) = E_k(IV_eve ⊕ (IV_eve ⊕ IV_alice ⊕ "false"))

The IV_eve ⊕ IV_eve cancels out, which means that C_eve = E_k(IV_alice ⊕ "false")

Now Eve can compare C_eve and C_alice. If they are different, she knows that Alice must have entered "true" for that medical condition.

Making IVs unpredictable thwarts this attack, and an easy way to make them unpredictable is to choose them randomly after the plain text has been supplied.