# Why is CBC with predictable IV considered insecure against chosen-plaintext attack?

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

The answer by mwhs is very wrong about CBC-MAC and its use of IV!! It is perfectly fine and secure to use the same IV for CBC-MAC! In fact, Jonathan Katz and Yehuda Lindell recommend using zero vector IV when invoking CBC-MAC because it saves storage and bandwidth in practical settings! (souce: Introduction to Modern Cryptography, Second Edition)

The attack described by mwhs is due to the lack of input length checking by an oracle. To pull off such an attack, the process with the CBC-MAC key (the oracle) must be willing to accept values of any length from an external adversary and provide the resulting tag. CBC-MAC is secure for fixed-length messages, however, by itself, it is not secure for variable-length messages. This is regardless of IV used.

To answer the question: The biggest failure is being able to guess a message from a ciphertext (Ilmari Karonen answers it succinctly).

Note that security of encryption means that a plaintext message can't be guessed any easier by knowing the ciphertext than it was before knowing the ciphertext (also known as Shannon Secrecy). Furthermore, in a secure system, the only part of the system that is secret is the key; an adversary knows the algorithms.

So, if I can predict the IV, I can craft a plaintext message guess, M (e.g. "bomb pearl harbor") by XORing it with the IV used with the original ciphertext, IVold, and with the predicted IV, IVnew, before encryption and observe the ciphertext, Cnew.

Cnew = F_k(IVnew XOR IVnew XOR IVold XOR M) = F_k(IVold XOR M)

If Cnew is the same as the message I am trying to guess, I win. Secrecy is lost.

I find it helpful to look at a picture of how CBC mode works : https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Cipher_Block_Chaining_.28CBC.29

• Hi bhass1. I think you are right when looking at the answer of mwhs. IMHO it already derails here "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)." Obviously when talking about CBC encryption we're not going to use the final block as MAC, CBC + CBC-MAC should at least be a two pass protocol using two different keys (and CMAC should be preferred). – Maarten Bodewes Mar 1 '17 at 13:41
• However, if you don't mind I'll flag this answer as to convert the first two sections into comments below mwhs. – Maarten Bodewes Mar 1 '17 at 13:42
• As your own answer, I think it is obvious that guessing the first part of the message is a possibility, you don't need to guess the whole of the message. After the split between answer and comments by one of the mods (hi e-sushi) I'll edit in some $\LaTeX$ fu if you don't mind. Finally, welcome to crypto and thanks for chiming in! – Maarten Bodewes Mar 1 '17 at 13:44
• Sounds good Maarten. I didn't know the syntax to include LATEX (is it just ?) and I was somewhat rushed in typing out the final answer. If by "first part of the message" you mean first block, then yes, but it is also possible to guess a multi-block message and verify the whole thing using the same technique by XORing the IV's to the first block of your guess. Once the first block is correct it will cascade through the rest of CBC the same as the original message and all ciphertext blocks will match if your entire guess is correct. – bhass1 Mar 5 '17 at 22:24
• Yes, $LaTeX$ inclusion is just between \$LaTeX\$ (using MathJax, just right click any formula here to see the context menu, the word "LaTeX" is just for demo in there of course). And you can center a formula by using \$\$LaTeX\$\$. – Maarten Bodewes Mar 6 '17 at 9:10

To simplify it: it's considered insecure because it has predicable values. The closer to random your cipher gets the stronger it becomes.