# Why is CBC with predictable IV considered insecure against CPA

I just learned that using CBC encryption with an IV which is predictable is not secure.

From what I understand, using certain plain texts, and then guessing the IV that is uses, the attacker can verify if the IV he guessed was right. How does this qualify as an attack?

-

The CBC IV attack does more than that.

If I guess the plaintext corresponding to any ciphertext block I've seen before, and can predict a future IV, I can verify my guess by submitting a suitable message to be encrypted with that IV. Obviously, that could be bad if, say, I knew the plaintext to be either "yes" or "no", and only needed to find out which one it is.

More concretely, the BEAST attack for example allows the recovery of cookies sent by a web browser over HTTPS. The way it works is (more or less) that you first convince the browser to send an HTTPS request where a block boundary falls just after the first unknown byte in the cookie (e.g. by adjusting the length of the requested URL) and intercept the ciphertext.

So now you have a ciphertext block that you know corresponds to, say, the string Cookie: secret=X, where X is an unknown byte. Now you use the CBC IV attack to test all possible values of X and find the right one. Then you repeat the process with a URL that's one byte shorter, so that you get a ciphertext block corresponding to ookie: secret=XY, where you now know X but don't yet know Y. Then just keep repeating the process until you've recovered the entire cookie, byte by byte.

See this answer to a related question for more details.

-
So, aren't there 2 necessary conditions here ? 1. You are able to predict the next IV ( quite possible reading the BEAST attack with SSL) and 2. You guess the ciphertext block of a previously received message. Is the latter always possible ? – asudhak Sep 27 '12 at 13:34
Not always, but more often than you'd think. See my edit above for a practical example. – Ilmari Karonen Sep 27 '12 at 13:57
@asudhak: we typically assume that the attacker can see ciphertext. If he can't, then why are we encrypting at all? – poncho Sep 27 '12 at 14:05
oh no, I meant knowing that a specific block of plain text corresponds to a cipher text. That was clarified by the last edit. – asudhak Sep 27 '12 at 18:20

If your IV is predictable this is as (in)secure as assuming that you have a zero vector IV.

And a zero vector IV allows you to perform a so-called Adaptive Chosen Plaintext Attack (ACPA).

Why?

Assume that you have a encryption mechanism that works in CBC mode. This means, that on the first iteration the $IV$ is XORed with your input message (which is only the size of one block) and then encrypted. On the following iterations the output of the previously encrypted block is used instead of the $IV$.

If we can predict the $IV$ that is going to be used, then we can XOR our message $x$ with that $IV$ before putting it in the CBC-thing. The CBC-thing is then going to XOR our message with the same (guessed) $IV$ again.

$(x \oplus IV) \oplus IV = x$

With this knowledge we can deduce the behaviour of our CBC-mode encryption as if the IV was non-existant or a zero vector.

This is especially important or meaningful in a scenario where you only consider the final output of the CBC-mechanism to be important, which is the case of a CBC-MAC (a MAC constructed with a block cipher used in CBC mode).

If you are able to send a few test blocks to some MAC-function with predictable $IV$ and receive the response, you may be able to produce valid MACs for a specific message without knowing the key and without submitting this very message for authentication.

Note that MACs are usually only produced by the key owner for messages that he approves. If you can trick the key owner into authenticating a few apparently random blocks of data for you, his MACs are attackable.

Small example, where we assume, that the block size of the encryption function is five (5) characters long (for demo purposes):

Scenario: Let's assume that the key owner is willing to authenticate any bizarre data with his CBC-MAC for you, but under no circumstances would he want to authenticate the message "HelloWorld". The goal of the attack is thus to gain enough knowledge from the key owner to produce a MAC for the message "HelloWorld". Of course without stealing the key or slamming him with a ruber tube.

Here is how it could work:

1.) Correctly guess the $IV_1$. This somehow is optional, see below. It maybe makes understanding the attack easier, but usually a CBC-MAC will publish the used $IV$ together with the MAC, because both parameters are needed for verification later. An $IV$ thus only needs to be guessed beforehand if the attacker wants to neutralize the $IV$, which is what we will do in step 3.

2.) Send the string $s_1$ = "Hello" (XORed with the $IV_1$) to the CBC-MAC-function and receive or read the resulting encrypted data $y_1$, which is in this case also the MAC $m_1$ for $s_1$ in case the $IV$ is the zero vector or for $s_1 \oplus IV_1$. If neutralizing the $IV$ this resolves to the encryption of the single block $s_1$ without any $IV$.

$MAC(s_1 \oplus IV_1) = y_1 = m_1 = encrypt_K(s_1)$

or

$MAC(s_1) = y_1 = m_1 = encrypt_K(s_1 \oplus IV_1)$

3.) Guess the next $IV_2$. This really neutralizes the unwanted $IV$ and instead simulates a chaining from a previous block, which we actually don't have. => The core of the attack!

4.) Send the string $s_2$ = "World" XORed with the $IV_2$ and XORed with $m_1$ to the CBC-MAC-Function and receive the resulting data $y_2 = m_2$. XORing $s_2$ with $IV_2$ neutralizes the $IV$ of the CBC-mechanism and XORing that with $m_1$ simulates an cipher-block-chaining from the previous block "Hello".

$MAC(s_2 \oplus IV_2 \oplus m_1) = y_2 = m_2$

5.) The MAC for the Message "HelloWorld" is $m_2$ if the $IV$ is set to be the zero vector at verification time (because $m_1$ is the MAC for "Hello" with a neutralized $IV$). Alternatively, as described above, if one would find a zero vector $IV$ to be odd-looking one could just not XOR $s_1$ with $IV_1$ in step 1, and instead store $IV_1$ for later use in the verification step.

(remember: the block size is five characters, HelloWorld is thus two blocks.)

Since the IVs are sent along the MAC for verification the attacker constructed a valid MAC for the two concatenated blocks ("Hello", "World") without knowing the Key and without submitting this message ("HelloWorld") to the MAC function for authentication.

I hope I could provide you with a good example about the problem of a predictable $IV$ in the context of chosen plaintext attacks.

Update: on a side note, and to precisely answer your question: you can verify that the guessed $IV$ is correct by XORing a test block with the $IV$ and sending it to the CBC-mechanism. Then you repeat the operation again with another correctly guessed IV. If both resulting outputs are equal the guessed IVs were correct. If not either the first or the second or no $IV$ was correctly guessed.

It is important to understand, that especially in the case of CBC-MACs the $IV$ is not a static configuration, but a random value chosen by the mechanism on each invocation.

-