# Generalizing a CBC-MAC collision with a common final message block

I found this question from a textbook but I don't really understand what it is asking:

Suppose $c$ is $1$ block long, $a$ and $b$ are strings that are a multiple of the block length, and $\text{CBC-MAC}(a||c) = \text{CBC-MAC}(b||c)$. An ideal block cipher is used in $\text{CBC-MAC}$.

Explain for which most general class of messages $d$, $\text{CBC-MAC}(a||d) = \text{CBC-MAC}(b||d)$.

I don't understand how can $CBC-MAC(a||c) = CBC-MAC(b||c)$ unless $a = b$?

• en.wikipedia.org/wiki/CBC-MAC should help you understand the algorithm. – pg1989 Nov 4 '13 at 20:53
• So if $\\ \\ CBC-MAC(x) = t \\ CBC-MAC(y) = t' \\ Then CBC-MAC(x || y \oplus t) = t' \\$ If y is block length 1 correct? – FluffyBeing Nov 5 '13 at 1:01
• $y$ doesn't even need to be block length one, you can just XOR $t$ into the first block if it's longer. – pg1989 Nov 5 '13 at 1:01
• Okay. But I still don't know what the question is asking. What does "most general class of messages" mean? Do I need to talk about what c is? – FluffyBeing Nov 5 '13 at 1:04
• Beats me. The question is really poorly-worded. – pg1989 Nov 5 '13 at 1:25

CBC-MAC is calculated by iterating a block cipher in CBC mode over the blocks of the message, using a start value of 0 - i.e. $CBC{-}MAC(a)$ is actually $CBC{-}MAC(0,a)$.

Since the first part of the messages (i.e. $a$,$b$) in your example have sizes that are multiples of the block length, the $CBC{-}MAC$ of each of them creates a chaining value that can be used as the input to $CBC{-}MAC$ of the second part of the message ($c$,any $d$)

$CBC{-}MAC(a||c)$
$= CBC{-}MAC(0, a||c)$
$= CBC{-}MAC(CBC{-}MAC(0, a), c)$

So $CBC{-}MAC(a||c) = CBC{-}MAC(b||c)$ when $a = b$, but more generally when $CBC{-}MAC(a) = CBC{-}MAC(b)$

When this is true, it's easy to see that $CBC{-}MAC(a||d) = CBC{-}MAC(b||d)$ for all $d$.
i.e. once a collision is found with $CBC{-}MAC$ for two messages $a,b$ whose lengths are multiples of the block size, then the $CBC-MAC$ of $a||d,b||d$ will also be equal for all $d$.

I'm not sure why the exercise focuses on this property (except to illustrate what's obvious from the CBC basis of the design).

• Why did it have to emphasize that c is block length 1? – FluffyBeing Nov 5 '13 at 14:53
• Like @pg1989 said, beats me. The question is really poorly-worded. – archie Nov 5 '13 at 19:10