Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Ok, so this is a very possible stupid question, but one of those things that has sat at the back of my mind for a while.

We all know that MD5 has issues, and these have been known for about a decade. So this is theoretical. I'm not considering using it for anything.

Question is this. If MD5 generates a 32 digit number in hex, given that 32 is finite, and we can hash longer and longer values, didn't we know from the offset that MD5 had to have collision issues?

share|improve this question
There is a difference between collisions existing and actually being able to find them. – CodesInChaos Nov 12 '13 at 16:01
up vote 2 down vote accepted

Basically all hash functions have this "problem". Pretty much all are finite in length.

The real problem happens when collisions can be generated in less work than brute force. Due to the birthday problem with an $n$-bit hash function we would expect to see a collision after computing $n/2$ digests. If $n$ is large enough (say $n=160$) we would not expect any realistic adversary to be able to generate collisions.

A hash function is broken when someone can demonstrate collisions in fewer than $n/2$ operations.

share|improve this answer
Thanks. That makes sense. It was the way that it gets referred to. – Seej Nov 12 '13 at 16:33

Because MD5 has a 128 bit output, we knew up front that we could find an MD5 collision by simply hashing $2^{64}$ values; with that many values, we're likely to see the same output twice (Birthday Paradox).

Today, $2^{64}$ would not be considered sufficient; there are currently large entities that could perform that much work, if it was important enough. However, when MD5 was originally designed (1991), the amount of computer resources any adversary might have was significantly less; $2^{64}$ was plausibly "more than anyone could reasonably have".

share|improve this answer
Ah, that explains it. Essentially the confusion was just a terminology confusion. – Seej Nov 12 '13 at 16:32

Your Answer


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.