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.)

Formalism

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.

Apteral

+1 I think this is the right answer. Great example, but I think sql injection is a better attack scenario than being a dba ;). Thanks for the detailed explanation. This is why your #1 for encryption tags on SO. – Formalism

Great answer, but I think you should emphasize one point a little more. Correct me if I'm wrong, but in this particular scenario it isn't important that Alices's IV can be predicted because Eve would already has access to it. More importantly, the IV that will be generated for the encryption of Eve's next set of inputs can be predicted. – No

@JohnBubriski Eve has to choose a plain text that is XOR'd with Alice's IV. But, if Alice has already enrolled, it's true that the only "prediction" necessary is for Eve's own IV. – Apteral

@Apteral Thanks for confirming my thought process! – No

what if key is only known to alice and not DBA ? – Edgy

@JigarJoshi In my example, neither Alice nor Eve know the key. Both can choose plaintext, Eve can read ciphertext. If you are curious about a particular scenario, can you explain your question more completely? – Apteral

alice has key k1 that key is just known to alice (server or nobody knows it), alice uses public salt s1, public iv IV1 and k1 to encrypt her message m1 into c1, now eve (the dba) has access to IV1, S1 and he knows the scope of plain text (fixed set of named disease) - for this scenario, I don't understand why would hardcoded IV will make eve's job easier – Edgy

@JigarJoshi If only Alice—and not the service—can use use the key k1 for encryption, than a predictable IV is not a problem, because we can presume Alice won't execute a chosen plaintext attack against herself. But in that case, the service would be unable to decrypt the value and use it for any legitimate purpose. – Apteral

If you can input any text then you can still try and get random trash inside the plaintext. In the end authenticated encryption should be used to avoid this trap, rather than CBC with an unpredictable IV. – Maier

Answer 2

The other answers are good, though highly technical.

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

When you encrypt data with a key, if the data and the key are the same (have not changed) then the encrypted data will be the same. If the encrypted data is the same then sets of encrypted data can be analyzed for patterns which can then be used to gain knowledge about the encrypted data.

CBC (Cipher Block Chaining) resolves this issue by XORing the encrypted data from the previous bock with the data to be encrypted. This means that blocks with the same data will be different if the encrypted data from the previous block is different, even if the keys are the same.

The problem with CBC is what to do with the first block, since there is no previous block to get the encrypted data from. Instead, the data is XORed with a block of random bits called an IV (Initialization Vector).

You can consider the security of the IV to be the same as the security of the encrypted data blocks. In other words, if they can be given the encrypted data then they can also be given the IV.

Cess

I like erickson's answer a lot better. An attack involving per-computation and chosen plain-text. – Formalism

Yes, and another way to look at it is that IV for CBC mode is a little bit like a salt but for the message. If you analyze the memorysteam output from a CBC message you'll see the IV in the beginning of the message. And if you format this back to text, you'll see the same two messages for "Testing" will result in "d0Testing" and "7eTesting" where CBC will cause an avalanche effect with the small differences in the beginning of the message and make them unrecognizable. – Passably

Answer 3

i want to explain your question by using WEP which is vulnerable and now other protocols such as WPA2 is used.

the simple rule IEEE says that :

Basic rule is never use a key+IV twice, ever

One of the reason that WEP is compromised is due to the reason of IV generation.

As seen in the picture, when WEP first appeared the length of the IV was 24 bits (later it is increased 48 bits) if the attacker knows the how the IV are generated or in this situation IVs are small enough for the attacker to exploit the messages.

If anyone knows about the generation of the IV or it overlaps (because IVs are 24 bits it means 2^24 IVs) during the transmission of the packets the attacker who is sniffing the traffic can : if the IVs are sequential it means still there is a possibility that the IVs will be overlap in some time.

let's assume,

passphrase key Kp

initialization vector Ivi

plaintext data D1, D2 (for separateblocks)

Traffic Key:Kti=Kp||Ivi

Ciphertext: E(Kti,Di)=RC4(Kti) xor Di

and assume that

IV1=IV2  (created sequentially and from 0 to 2^24 again returns back)

Attacker has,

(RC4(Kt1) xor D1) Xor  (RC4(Kt1) xor D2) = D1 XOR D2

This can be broken by using Aircrack-NG using network traces. The idea that i showed is the basic one more complex assumption can be made, again never ever use same IV that will overlap.

Perish

+1 this is a good answer and I agree for the most part. But what about using the primary key in a database as the iv? This is never going to overlap but its sequential. Wouldn't that still be a violation of CWE-329? Also a truly random value would introduce the possibility of an overlap, although this could be avoided. – Formalism

I think your close, but I think Erikson has hit the nail on the head for this specific CWE. Thanks for the answer. – Formalism

The question is specifically about CBC mode, so this answer is tangential to the question. – Krilov