2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ There is a difference between collisions existing and actually being able to find them. $\endgroup$ Nov 12, 2013 at 16:01

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks. That makes sense. It was the way that it gets referred to. $\endgroup$ Nov 12, 2013 at 16:33
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Ah, that explains it. Essentially the confusion was just a terminology confusion. $\endgroup$ Nov 12, 2013 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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