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

That paper says: "The adversary makes $2^{(n+1)/2}$ queries with $m$-block messages that have the same last $m−1$ blocks."

What I want to ask is why the authors choose $2^{(n+1)/2}$?

As we know, block cipher's input width is usually even, so if we operated it with $2^{(n+1)/2}$ the result will not be an integer, but fractional.

  • 1
    $\begingroup$ For why odds of collision are better than 50% after $2^{(n+1)/2}$ queries but not $2^{n/2}$, study the birthday problem, focusing on the case of a large set. Note: Here, $2^{(n+1)/2}$ is written $2^{(n+1)/2}$ $\endgroup$
    – fgrieu
    Mar 20, 2014 at 7:48

1 Answer 1


Why approximately $2^{(n+1)/2}$ queries? Because it makes the attack work.

As far as your final comment, it sounds like you are confusing $(n+1)/2$ with $2^{(n+1)/2}$. If we use AES, then $n=128$, so $(n+1)/2=64.5$. However, $2^{64.5}$ is a very large number. The exact number of queries is not important as long as it is approximately $2^{64.5}$, and it is easy to choose an integer near that number.

  • $\begingroup$ Thanks for the answer. But I mean why the authors choose $2^{(n+1)/2}$ ? Why the authors not choose $2^{n/2}$ ? Is it based in birthday paradox or what? $\endgroup$
    – user11291
    Mar 24, 2014 at 1:57
  • $\begingroup$ @user11291, read fgrieu's earlier comment, and do some learning on your own about the birthday paradox. $\endgroup$
    – D.W.
    Mar 28, 2014 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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