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

  • $\begingroup$ en.wikipedia.org/wiki/… $\;$ $\endgroup$ – user991 Nov 1 '13 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 '13 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 '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$.

| improve this answer | |
  • $\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 '13 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 '13 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 '13 at 23:45

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.