# MD5 theoretical question

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?

-
There is a difference between collisions existing and actually being able to find them. – CodesInChaos Nov 12 '13 at 16:01

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.

-
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".

-
Ah, that explains it. Essentially the confusion was just a terminology confusion. – Seej Nov 12 '13 at 16:32