# Distinguishing attack on CBC-MAC

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.