# Distinguishing Attack on CBC-MACs

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.

• 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}$
– fgrieu
Mar 20, 2014 at 7:48

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.
• 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? Mar 24, 2014 at 1:57