# Why does CBC-MAC need prefix-free inputs to be a good PRF?

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 preﬁx-free. (A set of strings is preﬁx-free if for any distinct x, y in the set, x is not a preﬁx of y.) The CBC-MAC is known to be a good PRF when it is invoked on a set of preﬁx-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).

• – user991
Commented Nov 1, 2013 at 21:36
• Is this really a practical attack on a Feistel network that just uses CBC-MAC as its round function? Commented Nov 1, 2013 at 21:45
• 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? $\:$
– user991
Commented Nov 1, 2013 at 21:52

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$.
• 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. $\;\;\;$