# probability of a collision on a n bit secure hash.

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.

• 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. – Evan Sep 21 '13 at 5:10
• 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?? – mike Sep 21 '13 at 12:33
• 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? – Evan Sep 21 '13 at 15:44
• 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. – mike Sep 21 '13 at 18:31
• 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? – mike Sep 21 '13 at 18:37