0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fgrieu Oct 9 '17 at 13:30
2
$\begingroup$

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

Here's how an attacker can exploit that to break the MAC scheme, given the restriction that all messages presented to CBC-MAC has an all-0 block at the end:

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.

So, the attacker asks for one, and he then knows the MAC of the other.

$\endgroup$

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.