I have a homework question that I need confirmation on.

Wikipedia states that a hash of n bits can be broken in $2^{n/2}$. Meaning that $2^{n/2}$ of hashes is expected to be computed in order to find a collision. http://en.wikipedia.org/wiki/Collision_attack

I've got 2 questions.

  1. (Part of the homework question) If it takes $2^{n/2}$ calculation to create a collision, will it take $10*2^{n/2}$ calculations to find 10 collisions? Is my assumption correct?

  2. (Not part of the homework), how did they calculate $2^{n/2}$? I know it's similar to the birthday problem, but I still don't understand how they got that value.

  • $\begingroup$ Did you read this one too: en.m.wikipedia.org/wiki/Birthday_attack ? Also Intuitively I would expect 10 collisions not to take 10 times longer because you have already generated many distinct hashes by the time you have found 1. $\endgroup$ – Evan Sep 21 '13 at 5:10
  • $\begingroup$ Yeah I've read the birthday problem. Your right, I didn't take the hashes that was already created into account. So would it be 2^n/2+10?? $\endgroup$ – mike Sep 21 '13 at 12:33
  • $\begingroup$ Probably more than that, would have to understand how they got the first figure. In the link they have a few derivations and approximations. what part are you getting stuck at? $\endgroup$ – Evan Sep 21 '13 at 15:44
  • $\begingroup$ whats 1.25 square root of H. Where did they get that from? Also where did they get that initial equation p(n;H). The article makes a lot of assumptions but does not show how these things were derived. $\endgroup$ – mike Sep 21 '13 at 18:31
  • $\begingroup$ What I derived from the birthday problem and other sources, I got 1-(2^n!)/((2^n-2)!*2^2n), but how does that give me 2^n/2? $\endgroup$ – mike Sep 21 '13 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.