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$?

  • 1
    $\begingroup$ en.wikipedia.org/wiki/CBC-MAC should help you understand the algorithm. $\endgroup$ – pg1989 Nov 4 '13 at 20:53
  • $\begingroup$ 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? $\endgroup$ – FluffyBeing Nov 5 '13 at 1:01
  • $\begingroup$ $y$ doesn't even need to be block length one, you can just XOR $t$ into the first block if it's longer. $\endgroup$ – pg1989 Nov 5 '13 at 1:01
  • $\begingroup$ 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? $\endgroup$ – FluffyBeing Nov 5 '13 at 1:04
  • $\begingroup$ Beats me. The question is really poorly-worded. $\endgroup$ – 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$)

For your example:

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

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

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.