Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
What you describe $is$ CBC encryption mode (albeit with $IV=0$). Read through your own logic: consider what happens if you replace $m_1$ with $m_1\oplus IV$? –  figlesquidge Nov 19 '13 at 23:15
    
Can you write it down? I didn't succeeded... The most I did succeed was to show that given a plaintext m=m1||m2 and ciphertext c a CPA attacker can create a c' that after decryption becomes: m2||m' where m' is unpredictable... –  Bush Nov 20 '13 at 19:17
add comment

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
Well in my comment below my question I said that I succeeded to bring m2 to be the new m1 - You gave the general attack in your answer (that attacker can modify the 1st block of the message to everything he wants). –  Bush Nov 20 '13 at 20:14
1  
@Bush: The attacker won't (AFAIK) be able to construct a ciphertext that would decrypt to $m_2 \mathbin\| m_1$, if that's what you're asking. He can, however, construct one that he knows will decrypt to $(m_2 \oplus c_1 \oplus v) \mathbin\| (m_1 \oplus c_2 \oplus v)$. (And if he can modify the IV, he can replace the first half of that with anything he wants.) –  Ilmari Karonen Nov 20 '13 at 20:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.