Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 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 this paper on CBC-MAC by Petrank and Rackoff.

share|improve this question
    
en.wikipedia.org/wiki/… $\;$ –  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
add comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
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
    
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. –  pg1989 Nov 1 '13 at 23:35
    
@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. –  J.D. Nov 1 '13 at 23:45
    
You're right - I hadn't thought of that. Accepting this answer. –  pg1989 Nov 6 '13 at 23:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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