This is another example of the implementation of the birthday "paradox" to hashes as the so-called "birthday attack".
No it isn't.
This attack is much more efficient than a birthday attack. The MD5 attack used in this paper required around 2^37 computations of MD5, whereas a birthday attack would require around 2^64 computations in addition to some severe space requirements.
But if it wasn't let's just clear a few things up. MD5 is a cryptographic hash function, and is intended for use in things like digital signatures, message authentication codes, and many, many other applications. The attack in the paper demonstrates that MD5 is not suitable for use with digital signatures.
By the pigeon hole principle, your "magical fingerprint" can never exist for compressing arbitrary files.
Re:Not a problem (yet)
on
SHA-1 Broken
·
· Score: 1
If anyone's still listening...
Concatenating the outputs of two functions is not as secure as one might think. In a paper presented in 2004 at the CRYPTO conference (the same one where the MD5 and SHA0 hash collisions were announced), (http://springerlink.metapress.com/openurl.asp?gen re=article&issn=0302-9743&volume=3152&spage=306)
Antoine Joux shows that, assuming the attack on SHA1 is valid, that a collision could be found in the concatenation of two SHA1 hashes (with differing IVs) in time around 69 * 2^69.
This generalizes - if n SHA1 hashes are concatenated, then it would take roughly (69)^{n-1}*2^{69} work to find a collision.
Yes, by the pigeon hole principle all hash functions have collisions.
It's just a matter of how much time it takes to find one.
You try to design the hash function such that even an adversary with computing power measured in acres does not have enough resources to find a collision in a pratical amount of time.
Update from the CRYPTO rump session (I was in attendance): Collisions were found in MD4, MD5, RIPEMD, and HAVEL (and SHA-0).
No collisions were found in SHA-1, but progress has been made in finding near collisions.
The presenter didn't give many details about how the collisions were derived, but did give some timing results. The highlight of the evening was when the slide for MD4 came up, and in the timing results section there was text similar to: "4 to 24 iterations. Can be done by hand." Ouch.
I think for MD5 it only took a couple of hours to find the collisions.
PLUS, in the talk on near collisions of SHA-0, the presenters were able to find messages that collided through ~30 rounds and were decipherable as english sentences...
Other talks seemed to indicate that SHA-1 *and* SHA-2 (256/512 bit) may be susceptible.
All in all, it was not a good day for hash function primitives.
Perci Diaconis, the main researcher cited in the study, is one of the most respected combinatorialists in math. In fact, in the domain of combinatorics of cards, he is the most prominent researcher in the field. I once heard him introduced as "When you play cards with Perci, technically you're not gambling."
This is not some quack. He's brilliant (and a very entertaining lecturer to boot). You get your PhD in math from Harvard in three years and then you can make fun of him.
I live in Boulder and I've got a great view of the city from my house. If I see the laser tonight I'll take some pictures and post them so my school's server can get/.ed.
Slashdot Mirror
This attack is much more efficient than a birthday attack. The MD5 attack used in this paper required around 2^37 computations of MD5, whereas a birthday attack would require around 2^64 computations in addition to some severe space requirements.
But if it wasn't let's just clear a few things up. MD5 is a cryptographic hash function, and is intended for use in things like digital signatures, message authentication codes, and many, many other applications. The attack in the paper demonstrates that MD5 is not suitable for use with digital signatures.
By the pigeon hole principle, your "magical fingerprint" can never exist for compressing arbitrary files.
If anyone's still listening... Concatenating the outputs of two functions is not as secure as one might think. In a paper presented in 2004 at the CRYPTO conference (the same one where the MD5 and SHA0 hash collisions were announced), (http://springerlink.metapress.com/openurl.asp?gen re=article&issn=0302-9743&volume=3152&spage=306)
Antoine Joux shows that, assuming the attack on SHA1 is valid, that a collision could be found in the concatenation of two SHA1 hashes (with differing IVs) in time around 69 * 2^69.
This generalizes - if n SHA1 hashes are concatenated, then it would take roughly (69)^{n-1}*2^{69} work to find a collision.
No passwords were stolen. No rated games were played, and all games (unrated/rated) were only played between authors of the paper.
Yes, by the pigeon hole principle all hash functions have collisions.
It's just a matter of how much time it takes to find one.
You try to design the hash function such that even an adversary with computing power measured in acres does not have enough resources to find a collision in a pratical amount of time.
That's the intuition, anyway.
Update from the CRYPTO rump session (I was in attendance):
Collisions were found in MD4, MD5, RIPEMD, and HAVEL (and SHA-0).
No collisions were found in SHA-1, but progress has been made in finding near collisions.
The presenter didn't give many details about how the collisions were derived, but did give some timing results. The highlight of the evening was when the slide for MD4 came up, and in the timing results section there was text similar to: "4 to 24 iterations. Can be done by hand." Ouch.
I think for MD5 it only took a couple of hours to find the collisions.
PLUS, in the talk on near collisions of SHA-0, the presenters were able to find messages that collided through ~30 rounds and were decipherable as english sentences...
Other talks seemed to indicate that SHA-1 *and* SHA-2 (256/512 bit) may be susceptible.
All in all, it was not a good day for hash function primitives.
Perci Diaconis, the main researcher cited in the study, is one of the most respected combinatorialists in math. In fact, in the domain of combinatorics of cards, he is the most prominent researcher in the field. I once heard him introduced as "When you play cards with Perci, technically you're not gambling."
This is not some quack. He's brilliant (and a very entertaining lecturer to boot). You get your PhD in math from Harvard in three years and then you can make fun of him.
I live in Boulder and I've got a great view of the city from my house. If I see the laser tonight I'll take some pictures and post them so my school's server can get /.ed.