Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
There is a difference between collisions existing and actually being able to find them. –  CodesInChaos Nov 12 '13 at 16:01
add comment

2 Answers

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. –  Owen 'Coves' Jones Nov 12 '13 at 16:33
add comment

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. –  Owen 'Coves' Jones Nov 12 '13 at 16:32
add comment

Your Answer

 
discard

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.