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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
Random functions have collisions, random permutations (block ciphers) don't. See Is it possible to distinguish a securely-encrypted ciphertext from random noise? I'd guess the paper describes a variant of that, but I didn't look at it. – CodesInChaos Jan 8 '14 at 10:06
ok, thank you for the explanation. – user11291 Jan 9 '14 at 15:45

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.

share|improve this answer
Thank you for the explanations. It is helpful. – user11291 Jan 9 '14 at 15:47

Your Answer


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.