4
$\begingroup$

enter image description here enter image description here

Can anyone explain why CBC-MAC is not secure for variable length message?

I read many books, but there are still some confusion. Such as the highlighted parts in previous pictures

Questions:

  1. why need to set $T''=C_0$?
  2. why $T'''=T''$. How to prove this relationship?
  3. $new\ message = P_0,P_1,(P_0 \oplus T')$?
$\endgroup$
  • $\begingroup$ If the given answer satisfies you, could you please accept it by clicking on the right mark? $\endgroup$ – Raoul722 May 24 '16 at 14:44
8
$\begingroup$

Can anyone explain why CBC-MAC is not secure for variable length message?

For the previous question I'll quote Matthew Green's post from 2013:

A quick reminder. CBC-MAC is very similar to the classic CBC mode for encryption, with a few major differences. First, the Initialization Vector (IV) is a fixed value, usually zero. Second, CBC-MAC only outputs the last block of the ciphertext -- this single value forms the MAC.

enter image description here

Many dumb implementations stop here. And that leads to big problems.

Most notably, if your system allows for variable-length messages -- as it should -- there is a simple attack that allows you to forge new messages. First, get a MAC T on a message M1. Now XOR the tag T into the first block of some arbitrary second message M2, and get a MAC on the modified version of M2.

The resulting tag $T'$ turns out to be a valid MAC for the combined message $(M1 || M2)$. This is a valid forgery, and in some cases can actually be useful.

The standard fix to prepend the message length to the first block of the message before MACing it. But a surprisingly large number of (dumb) implementations skip this extra step. And many CBC-MAC implementations are dumb implementations.

(more info here)

First question, why need to set $T′′=C0$?

Actually it is not set. $T''$ is computed as written in the slide and the result is $C_0$.

Second question which is biggest question I don't understand, why $T′′′=T′′$. How to prove this relationship? Third question, why is $\text{new message}=P_0,P_1,(P_0⊕T′)$?

Let's compute the tag for $P'''$: after processing second bloc ($P_1$) one have $T'$, so when processing next bloc ($P_0 \oplus T'$) one computes the encryption of $T' \oplus P_0 \oplus T' = P_O$ that is, by definition, the tag of the second message: $T''$ ($P_0$ is the second message $P''$).

Roughly the idea is to add a bloc that cancel all previous computations and restart the CBC-MAC computation for a message which MAC is already know by the attacker. "Canceling" is done by xoring to the first added bloc the tag of the previous chain to the first bloc of an other message which MAC is known.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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