Assume that a one-way Hash function is secure and the best way to attack it is by using the brute force attack. It produces an $m$-bit output. Finding a message that hashes to a given hash value would require hashing $2^m$ random messages. Finding two messages that hash to the same value would only require hashing $2^{\frac{m}{2}}$ random messages.

I know only about birthday paradox involving 23 people. How do I relate the birthday paradox with this attack?


$2^m$ requirement is for the pre-image attack. You have to hash approximately $2^m$ messages to find the message that has the same value you were looking for if the hash function has pre-image resistance.

In a collision attack, you are looking for two messages that have the same hash value.

If you look at Wikipedia Birthday Paradox at section Cast as a collision problem, it is also generalized for the arbitrary number of days not just for 365 days. The approximation is given by

$$n \approx \sqrt{2^m}$$ and we call it generic birthday attack.

Note that: if you find an attack which is faster than generic birthday attack like SHA-1 attack you will be famous.

| improve this answer | |

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.