10
$\begingroup$

I know that length prepending improves security of CBC-MAC. However, wouldn't inserting the length elsewhere (middle, end or any other part of message) be equally good? After all, even the length is processed by the underlying cipher block.

$\endgroup$
19
$\begingroup$

Well, let's try it, and see how hard it is to forge a message.

Let's say for illustrative purposes that each character is a block, and that numbers represent the length indicator section. And let's start by putting the length indicator at the end. So,

XXXXXXX7

represents a 7-block message, with the '7' indicator at the end. Let's also say that,

$_{MAC}($XXXXXXX7$) = M_0$

represents the MACing of that 7-block message, with the resulting Tag $M_0$.

How hard is it to forge? It is trivially easy. All you need to do is request the MAC of three messages like so:

1) $_{MAC}($AAAAA5BBB9$) = M_1$

Note the '5' in the middle of the message. For this first MAC, that is just part of the requested message -- only the '9' at the end has been added by the length-appending algorithm to indicate the total length of the message.

2) $_{MAC}($AAAAA5$) = M_2$

3) $_{MAC}($CCCCC5$) = M_3$

Then xor $M_2$ and $M_3$:

$M_2 \oplus M_3 = D$

And let $ E = B \oplus D$, and now you can trivially forge the Tag for a new message that you did not request from the MAC Oracle:

$_{MAC}($CCCCC5EBB9$) = M_1$

Note that the same logic applies if the length indicator is anywhere in the message except right at the beginning.

$\endgroup$
2
  • 1
    $\begingroup$ I assume that B in this case means BBB9, right? $\endgroup$ – TheRookierLearner Oct 19 '13 at 13:00
  • 4
    $\begingroup$ No, B is just the first block of the string BBB9. So you only modify the first block of that string to get EBB9, which can be concatenated with CCCCC5. When the MAC algorithm processes CCCCC5, the output is $M_3$, which when xored to E will equal $B \oplus M_2$ - and that is precisely the input into the 7th encryption function that you get when MACing AAAAA5BBB9. $\endgroup$ – J.D. Oct 19 '13 at 13:07

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.