# CBC-MAC for Arbitrary Length Messages

Katz/Lindell propose the following modification to the basic CBC-MAC scheme to handle variable length messages (p.125):

We sample two uniform independent keys $k_1, k_2\in \{0,1\}^n$. Then to authenticate a message $m$, we first compute the basic CBC-MAC of $m$ using $k_1$ and call the resulting tag $t$. Then we let the output tag be $t' = F_{k_2}(t)$.

My question is why do we need to use two keys? That is, why is the scheme insecure if we compute the output tag $t'$ using $F_{k_1}$?

• Hint: assuming messages restricted to a multiple of the block size, no padding, and $k_1=k_2$, compare $t'$ for a certain message to $t$ for the same message followed by a block full of zeroes. Derive an explicit attack using a similar principle (and adapt it to the padding, if any). If that's not homework, I can be more explicit. – fgrieu Oct 9 '17 at 13:30

That is, why is the scheme insecure if we compute the output tag $t'$ using $F_{k_1}$?
Computing $F_{k_1}( \text{CBCMAC}_{k_1}(M))$ is precisely equivalent to taking the padded message $M$, appending an all-zero block to it, and then preforming the CBC-MAC on it (sans the padding operation).
First, ask for $a = \text{CBCMAC}_k(M_1 || 0)$, and $b = \text{CBCMAC}_k(M_2 || 0)$
Then, we know that $\text{CBCMAC}_k(M_1 || 0 || u || 0)$ and $\text{CBCMAC}_k(M_2 || 0 || u\oplus a \oplus b || 0)$ are the same (for any single block $u$); this happens because, when the two MACs xor in the $u$ or the $u \oplus a \oplus b$ blocks, then both set their internal states to $u \oplus a$, and all other processing is identical past that point.