Take the 2-minute tour ×
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.

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

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.

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

Your Answer

 
discard

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.