# CBC first block malleability

Let $m_1 = \underbrace{ \{0,1\}^n \times \cdots \times \{0,1\}^n }_{L\text{ times}}$ be a message of space $\mathcal{M}^L$, where $\mathcal{M} = \{0,1\}^n$.

Let $c_1$ be the encryption of $m_1$ using CBC mode.

Let $x \in \mathcal{K}$ be some binary string.

Finally, let $m_2$ be another message such that:

• $m_2 = m_1 \oplus x$
• $m_2[i] = m_1[i]$ for $i = 2, ... ,n$

How can I modify $c_1$ to be a $c_2$ that is the encryption of $m_2$ ?

I didn't figure out how to modify $c_1$ directly, I could only think about something like $\oplus$ing the Initialization Vector with $x$, so $c_2$ would somehow have both $m$ and $x$ used in its computed first block.

• "I could only think about something like $\oplus$ing the Initialization Vector with $x$"; and why isn't that a valid answer? – poncho May 1 '18 at 18:33
• @poncho because I'm supposed to modify $c$ and not the initialization vector. – Daniel May 1 '18 at 18:55
• Isn't the IV part of the ciphertext? – poncho May 1 '18 at 19:00
• now that you mentioned, I'm uncertain. I've seen some constructions where the IV is only used to be $\oplus$ed with the first block of the message and generate the first block of the cipher, but I think I've seen a construction that puts IV in the beginning of the cipher as well... – Daniel May 1 '18 at 19:10

Yes, you can modify the initialization vector to accomplish your goal (as mentioned in the comments, the initialization vector is the first block of the cipher text). So, by computing a new initialization vector, $IV_2 = IV_1 \oplus x$, the cipertext/IV pair $(c_1, IV_2)$ is a valid encryption of $m_2$ with CBC mode. This is because $m_2 = m_1 \oplus x$, so $$m_2 \oplus IV_2 = (m_1 \oplus x) \oplus (IV_1 \oplus x) = m_1 \oplus IV_1$$ This way, the first blocks of input to the blockcipher are the same for both messages ($\oplus$'d with their respective IVs), and the encrypted outputs are valid for both messages.