5
$\begingroup$

In the FFX spec, there is a note about using CBC-MAC as the round function.

Security notes. The round function F is constructed in such a way that the set of inputs on which the CBC-MAC is invoked is prefix-free. (A set of strings is prefix-free if for any distinct x, y in the set, x is not a prefix of y.) The CBC-MAC is known to be a good PRF when it is invoked on a set of prefix-free inputs, assuming AES is a good PRP [23].

Why is it important that the input be prefix-free? The citation is for Erez Petrank and Charles Rackoff, ‘CBC MAC for Real-Time Data Sources’, Journal of Cryptology 13(3), 2000, pp. 315–338 (paywall-free, tech report, preprint).

Improve this question
$\endgroup$
3
  • $\begingroup$ en.wikipedia.org/wiki/… $\;$ $\endgroup$
    – user991
    Nov 1, 2013 at 21:36
  • $\begingroup$ Is this really a practical attack on a Feistel network that just uses CBC-MAC as its round function? $\endgroup$
    – pg1989
    Nov 1, 2013 at 21:45
  • $\begingroup$ How could "a Feistel network that just uses CBC-MAC as its round function" $\hspace{1.58 in}$ invoke CBC-MAC on inputs of different lengths? $\:$ $\endgroup$
    – user991
    Nov 1, 2013 at 21:52

1 Answer 1

Reset to default
7
$\begingroup$

Because CBC-MAC with inputs that are not prefix free is weak against existential forgery, meaning it is not a "secure" MAC. More precisely, CBC-MAC is easily distinguishable from a random function (i.e. not a PRF) when the input domain is not prefix-free. This is because an adversary can request the CBC-MAC of messages $M_0$ and $M_1$, and then xor the MAC for $M_0$ with the first block of $M_1$, and thereby trivially construct another message, $M_2$ (such that $M_2 = M_0||\overline{M_1}$, where $\overline{M_1}$ is $M_1$ with the first block altered). $M_2$ will have the same MAC as $M_1$, which is a collision that should be very hard to find for a PRF. Note that $M_0$ is a prefix of $M_2$.

CBC-MAC can be made secure by either i) only using it for fixed-length messages (because no message of length $l$ can be a prefix of any other message of length $l$), or ii) always prepending $L_m$, the length of the message, to the message and using CBC-MAC on the string $L_m || M$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ In ii), one has to only use it for fixed-length $L_m$. $\:$ Option iii) would presumably be $\hspace{1.4 in}$ composing with a prefix-free code. $\;\;\;$ $\endgroup$
    – user991
    Nov 1, 2013 at 22:54
  • $\begingroup$ Yeah but an adversary against a Feistel cipher with AES-CBC-MAC as its round function won't have a MACing oracle, it will only have oracle encrypt/decrypt for the whole cipher. $\endgroup$
    – pg1989
    Nov 1, 2013 at 23:35
  • $\begingroup$ @pg1989 - The known proofs require vanilla CBC-MAC to be prefix free in order for it to be a provably secure PRF. The FFX authors evidently wanted to use the PRF-ness of CBC-MAC in their mode of operation without having to prove a non-prefix-free variant of it would still be secure when embedded in a Feistel construction. There's no point re-inventing the wheel if you don't have to. $\endgroup$
    – J.D.
    Nov 1, 2013 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.