This whole question pertains to CBC-MAC.

Let's say $a$ is one cipher block long, and the attacker knows the MAC $M(a)$ of $a$, which was generated with a random key. How can the attacker forge the MAC of a two block message under the same key?

For example, if I have $M(a)$, can I forge $M(b||c)$, where $b$ and $c$ are both one block each?

If that is not possible, is it possible to forge $M(a||b)$ or $M(b||a)$?


Given just $a$ and $M(a)$, you can construct the message $a\,\|\,b$, where $b = a \oplus M(a)$, which gives the same CBC-MAC output $M(a\,\|\,b) = M(a)$ as $a$ itself.

Indeed, we can append the block $b$ to the message as many times as we like without changing the MAC value: $M(a) = M(a\,\|\,b) = M(a\,\|\,b\,\|\,b) = M(a\,\|\,b\,\|\,b\,\|\,b) = \dots$

The reason this works should be apparent by looking at the structure of CBC-MAC:

CBC-MAC structure

As the diagram shows, a message like $a\,\|\,b\,\|\,b\,\|\,\dots$ is processed block by block. In the first step, we encrypt $a \oplus 0 = a$ with the block cipher, and obtain $M(a) = E_k(a)$ as the output. If the message ended here, this would be the resulting MAC value. However, if the message continues, the next block $b$ is XORed with the output $M(a)$ of the previous step and encrypted with the block cipher again. If we choose $b = a \oplus M(a)$, then the input to the block cipher will be $b \oplus M(a) = a \oplus M(a) \oplus M(a) = a \oplus 0 = a$ again, and thus the output will also be $E_k(a) = M(a)$ again.


Welcome to Stackoverflow!

What you may be looking for https://en.wikipedia.org/wiki/CBC-MAC#Security_with_fixed_and_variable-length_messages


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.