How was SHA-0 broken? - What is the significance of a mere handful of hash collisions?
I wanted to understand how the SHA0 hash function was broken. I understand that utilising the birthday problem/pigeon-hold principle, hash collision(s) were found. http://www.mail-archive.com/cryptography%40metzdowd.com/msg02554.html contains an example message.
What I’m having trouble finding/understanding: Does this mean there is a timely, mathematical way to ALWAYS produce a hash collision?
Can I eventually find a m2 for a given m1 such that m1 != m2, sha(m1) == sha(m2) or is it only possible on a subset of possible messages? R开发者_如何学JAVAephrased: Are the chances of my password having another message for a collision guaranteed?
What is the significance of finding 2 random long messages such as in the link above that have the same hash value? Why did they have to sift through long random messages for a collision instead of figuring a collision for a practical message like “The brown dog jumped over the fox” ?
A couple examples of hash collisions don’t seem as important as a timely method to generate a collision for any message, but all the posts talk about the former.
Thanks for any help/your time! I've read alot of posts/articles, but can't work my brain around my confusion. I suspect I have the same questions for other broken hash functions like MD5.
EDIT:
The paper (explaining improved method for finding collisions) referenced in the answer
From Wikipedia:
In February 2005, an attack by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu was announced which could find collisions in SHA-0 in 2^39 operations.
That kind of complexity is completely insufficient for cryptographic purposes with the computing power currently available. It guarantees the discovery of a collision for any message in a very reasonable amount of time.
精彩评论