I am reading material on cryptographic hash functions and it says

"Collision resistant property : for a hash of length L, a perfect hash would take $2^{L/2}$ attempts."

Can someone explain why?

Thanks you


If an attacker repeatedly generated hash values at random, the collision question is "how many attempts would it take to generate a value that had been seen before"? This is an example of the generalized birthday problem: If you repeatedly sample items at random with replacement from a set of $d$ items, how large must $n$ be before there is a reasonable chance of seeing an item twice? The answer is $n$ is proportional to $\sqrt d$.

Application to perfect hashing: The length $L$ of a hash is the number of bits it outputs. A perfect hash would return $2^L$ possible values, so by the birthday problem it would take on the order of $\sqrt{2^L}=2^{L/2}$ attempts to generate a collision.

  • $\begingroup$ why "with replacement" ? I think if we try brute force attack we discard values that did not work for us.. $\endgroup$ – YohanRoth Apr 25 '15 at 15:55
  • $\begingroup$ The purpose of a birthday attack is to find two messages that hash to the same value. This is done by randomly generating hash values until a duplicate is found. See en.wikipedia.org/wiki/Collision_attack and en.wikipedia.org/wiki/Birthday_attack $\endgroup$ – grand_chat Apr 26 '15 at 18:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.