开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜