Is CBC mode encryption vulnerable to a reordering attack?

Question

I know that, if CBC-MAC is used in such a way that the tag is the concatenation of all the blocks' outputs (and not just the last one), it's insecure under CPA for the simplest case of 2 blocks CBC-MAC where:

• the message is $m=m_1\mathbin\|m_2$, where $|m_1|=|m_2|$ equals the block size of the cipher, and
• the tag is $t=t_1\mathbin\|t_2$, where $t_1 = F_k(m_1)$ and $t_2=F_k(t_1\oplus m_2)$.

In this case, the attacker can change the plaintext and create a valid tag of reverse order. The new message will be $m'=m'_1\mathbin\|m'_2$, where

• $m'_1=m_2\oplus t_1$,
• $m'_2=m_1\oplus t_2$, and
• $t'=t_2\mathbin\|t_1$.

Is a similar attack also possible for the CBC encryption mode (where we have a random $IV$ xored to $m_1$)?

EDIT: My question actually is whether a CPA attacker (who knows $c=IV\mathbin\|c_1\mathbin\|c_2$ and $m=m_1\mathbin\|m_2$) can modify the ciphertext that is sent to the destination and be able to predict what the plaintext resulting from it will be?

Answer 1

Yes. Assume that the attacker knows the ciphertext $c = c_1 \mathbin\| c_2$, the initialization vector $v$ and the plaintext $m = m_1 \mathbin\| m_2$. This tells them that

• $D_k(c_1) = m_1 \oplus v$ and
• $D_k(c_2) = m_2 \oplus c_1$,

where $D_k(\cdot)$ denotes block cipher decryption under the (unknown) key $k$.

In particular, this implies that, if the attacker reverses the order of the ciphertext blocks to produce the modified ciphertext $c' = c_2 \mathbin\| c_1$, then they will know that it will decrypt to $m' = m'_1 \mathbin\| m'_2$, where

• $m'_1 = D_k(c_2) \oplus v = m_2 \oplus c_1 \oplus v$ and
• $m'_2 = D_k(c_1) \oplus c_2 = m_1 \oplus c_2 \oplus v$.

There should be nothing particularly surprising about this: like all non-authenticated block cipher modes of operation, CBC mode is known to be malleable, meaning that an attacker who can change the ciphertext is also able, at least to some extent, to predict the effects of the changes on the resulting plaintext. If you don't want that (and you usually don't), you need to use an authenticated encryption mode, possibly constructed by combining a conventional mode like CBC with a secure MAC.

(In fact, a further attack on CBC is possible if, as usual, the initialization vector $v$ is transmitted alongside the ciphertext: in that case, the attacker can change the first block of the plaintext to anything they want, without affecting the other blocks, simply by changing the IV.)