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

In the FFX spec, there is a note about using CMAC 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 this paper on CBC-MAC by Petrank and Rackoff.

-
–  Ricky Demer Nov 1 '13 at 21:36
Is this really a practical attack on a Feistel network that just uses CBC-MAC as its round function? –  pg1989 Nov 1 '13 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? $\:$ –  Ricky Demer Nov 1 '13 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. $\;\;\;$ –  Ricky Demer Nov 1 '13 at 22:54