I want to ask about distinguishing attack on CBC MAC, as in the paper published by Ketting Jia, Xiaoyun Wang, Zheng Yuan, and Guangwu Xu: Distinguishing Attack and Second-Preimage Attack on the CBC-like MACs.

In that paper it is said that "if there is a collision in the structure, the MAC function is random function. Otherwise it is a CBC MAC."

What is the meaning of that statement?

As I know, random function does not have collision, but in that statement it is said that if there is a collision, it is random function.


The quoted sentences means: if there is a collision among the MACs of the $2^{(n+1)/2}$ messages submitted, the attacker playing the distinguishing game announces that the oracle is a random function; else announces that the oracle is CBC-MAC.

This works because the messages submitted differ only in their first block, thus will never collide under CBC-MAC, when they collide with odds $0.632\dots$ (by the birthday "paradox") for a random function. The attacker employing the strategy outlined in a game where the objective is distinguishing between an oracle implementing a random function, and an (equally likely) oracle implementing CBC-MAC with a fixed random key, will have an advantage compared to announcing a result at random.

Update: to prove that there are never collisions with CBC-MAC, assume that there is such collision between two messages identical in all but the first block; use that a block cipher with a fixed key is a permutation over the set $\{0,1\}^n$; and conclude that the first block must be identical in the two messages.

So far, this is purely a distinguisher, without much practical applications. However the paper goes on to explain another attack, which I'll illustrate in a simplified version below.

Assume CBC-MAC using messages of three blocks, a block cipher of $n$ bits, and $n$-bit output. The attacker obtains the MAC of $2^{(n+1)/2}$ messages $M_j=j||j||0$ where the first two blocks are $j$ and the third block all-zero. Odds that a collision on the MAC occurs is about $0.632\dots$ (both for a random function and CBC-MAC). If that happens for messages $M_a$ and $M_b$, the adversary submits $M'_a=a||a||1$ and $M'_b=b||b||1$. If the MAC is CBC-MAC, there will with certainty be a MAC collision between $M'_a$ and $M'_b$, whereas odds of such a collision would be $2^{-n}$ if the MAC was a random function.

This allows computing a second preimage of a message with any desired third block, after little more than $2^{n/2}$ queries.

This attack is known as a birthday forgery. It is briefly discussed in ISO/IEC 9797-1, which standardizes CBC-MAC, as early as in the 1999 edition, with attribution to Bart Preneel and Paul C. van Oorschot: MDx-MAC and Building Fast MACs from Hash Functions, published in the proceedings of Crypto 1995.

For in-depth coverage of similar attacks on CBC-MAC, see the work of Antoine Joux, Guillaume Poupard, and Jacques Stern: New attacks against standardized MACs, published in the proceedings of FSE 2003; or/and Karl Brincat and Chris J. Mitchell: New CBC-MAC forgery attacks (preliminary zipped version here), published in the proceedings of ACISP 2001.


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.