Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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 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.

share|improve this question
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 '14 at 7:48
Thanks for your comment and edit. :) – user11291 Mar 24 '14 at 1:49

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.

share|improve this answer
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? – user11291 Mar 24 '14 at 1:57
@user11291, read fgrieu's earlier comment, and do some learning on your own about the birthday paradox. – D.W. Mar 28 '14 at 2:48
okay, thanks a lot – user11291 Mar 29 '14 at 10:44

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.