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 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 $CBC-MAC(a||c) = CBC-MAC(b||c)$. An ideal block cipher is used in $CBC-MAC$.

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

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

share|improve this question
1  
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? –  zeion 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? –  zeion Nov 5 '13 at 1:04
    
Beats me. The question is really poorly-worded. –  pg1989 Nov 5 '13 at 1:25
add comment

1 Answer

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

share|improve this answer
    
Why did it have to emphasize that c is block length 1? –  zeion Nov 5 '13 at 14:53
    
Like @pg1989 said, beats me. The question is really poorly-worded. –  archie Nov 5 '13 at 19:10
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.