Slashdot Mirror

How you got modded insightful is beyond me. This shit is real, very real, not just some propaganda from the Chinese. The attack on MD5 has been demonstrated by generating a couple of forged X.509 certificates based on the MD5 hash. It has long been suspected that MD5 harbored significant weaknesses, but it was confirmed in 2005 when Wang and her team demonstrated in a 2005 paper (warning PDF link) that it is possible to generate MD5 collisions with only about 2^39 hash computations (approx. 500 billion), a level of computational work which is doable in a matter of a few days even on the computer which I am using to type this post, and a very long way from the 2^64 computations required by a brute force attack. MD5 is well and truly broken, and not just in the academic sense, and anyone who says that the break doesn't affect the vast majority of its uses is either hopelessly uninformed or willfully ignorant. Checksums and digital signatures based on MD5 are now all suspect, and the only major application of the algorithm that remains unaffected is its use as a message authentication code, and the fact that the algorithm shown significant weakness in so many other areas should make anyone think twice before using it even for that. The biggest names in cryptography have been watching her work and that of her team with the keenest of interest, and there was an announcement (also here) that SHA-1 collisions could be found in 2^63 operations, which, while not feasible on my humble little PC, is within the realm of feasibility of today's fastest supercomputers and distributed computation clusters. Meaning that the NSA could probably generate SHA-1 collisions if they wanted to. Her most recent peer-reviewed paper on the subject gave a work factor of 2^69 for generating collisions, which while quite high, is quite a ways from the 2^80 required by true brute force, and that would make any serious cryptographer worried about using the algorithm.

How you got modded insightful is beyond me. This shit is real, very real, not just some propaganda from the Chinese. The attack on MD5 has been demonstrated by generating a couple of forged X.509 certificates based on the MD5 hash. It has long been suspected that MD5 harbored significant weaknesses, but it was confirmed in 2005 when Wang and her team demonstrated in a 2005 paper (warning PDF link) that it is possible to generate MD5 collisions with only about 2^39 hash computations (approx. 500 billion), a level of computational work which is doable in a matter of a few days even on the computer which I am using to type this post, and a very long way from the 2^64 computations required by a brute force attack. MD5 is well and truly broken, and not just in the academic sense, and anyone who says that the break doesn't affect the vast majority of its uses is either hopelessly uninformed or willfully ignorant. Checksums and digital signatures based on MD5 are now all suspect, and the only major application of the algorithm that remains unaffected is its use as a message authentication code, and the fact that the algorithm shown significant weakness in so many other areas should make anyone think twice before using it even for that. The biggest names in cryptography have been watching her work and that of her team with the keenest of interest, and there was an announcement (also here) that SHA-1 collisions could be found in 2^63 operations, which, while not feasible on my humble little PC, is within the realm of feasibility of today's fastest supercomputers and distributed computation clusters. Meaning that the NSA could probably generate SHA-1 collisions if they wanted to. Her most recent peer-reviewed paper on the subject gave a work factor of 2^69 for generating collisions, which while quite high, is quite a ways from the 2^80 required by true brute force, and that would make any serious cryptographer worried about using the algorithm.

They have been found, in theory, to not be as collision-proof as previously thought, but noone has yet found a way to take one block of data and modify it such that it would have an identical hash signature as the original.

Here is a coral cache of professor Xiaoyun Wang's actual site with PDFs of her papers Its in English. Note that loading the original URL takes quite a while because its hosted in china, and the coral cache of her papers is much faster.

Professor Wang Xiaoyun's publications Shandong University are listed at here. Most SHA-1 and MD5 papers are downloadable, read if you have interests.

She is working for Tsinghua University now.

This appears to be the professors website:

http://www.infosec.sdu.edu.cn/people/wangxiaoyun.h tm

The details on the hash collision can be found in the following papers:

Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Finding Collisions in the Full SHA-1,Crypto'05
http://www.infosec.sdu.edu.cn/paper/Finding%20Coll isions%20in%20the%20Full%20SHA-1.pdf

Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Collision Search Attacks on SHA1,2005
http://www.infosec.sdu.edu.cn/paper/Collision%20Se arch%20Attacks%20on%20SHA1.pdf

She has also previously found methods for collisions in X.509, MD4/MD5, HAVAL-128, RIPEMD and SHA-0.

However, the problem is not entirely the algorithms, there will always be collisions on hashing algorithms, if you could represent an infinite amount of data in 160/128/whatever bits then there would be no point in having 161/129/whatever bits, the fact that your hard drive is much larger than that is a testament that collisions in any type of algorithm where you try to uniquely represent X bits in Y bits (where X > Y) (Yes I realize this is a somewhat oversimplified exaplantion).

The problem is in the paradigm in which these algorithms get used, 'one hash to represent them all' is a broken mentality, use multiple hashing algorithms when it matters, while it is indeed possible that the same data can cause a collision in all of the employed algorithms, its incredibly unlikely and AFAIK no one has created a PoC where two sets of data produce the same checksum in both md4 and sha-0.

This appears to be the professors website:

http://www.infosec.sdu.edu.cn/people/wangxiaoyun.h tm

The details on the hash collision can be found in the following papers:

Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Finding Collisions in the Full SHA-1,Crypto'05
http://www.infosec.sdu.edu.cn/paper/Finding%20Coll isions%20in%20the%20Full%20SHA-1.pdf

Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Collision Search Attacks on SHA1,2005
http://www.infosec.sdu.edu.cn/paper/Collision%20Se arch%20Attacks%20on%20SHA1.pdf

She has also previously found methods for collisions in X.509, MD4/MD5, HAVAL-128, RIPEMD and SHA-0.

However, the problem is not entirely the algorithms, there will always be collisions on hashing algorithms, if you could represent an infinite amount of data in 160/128/whatever bits then there would be no point in having 161/129/whatever bits, the fact that your hard drive is much larger than that is a testament that collisions in any type of algorithm where you try to uniquely represent X bits in Y bits (where X > Y) (Yes I realize this is a somewhat oversimplified exaplantion).

The problem is in the paradigm in which these algorithms get used, 'one hash to represent them all' is a broken mentality, use multiple hashing algorithms when it matters, while it is indeed possible that the same data can cause a collision in all of the employed algorithms, its incredibly unlikely and AFAIK no one has created a PoC where two sets of data produce the same checksum in both md4 and sha-0.

This appears to be the professors website:

http://www.infosec.sdu.edu.cn/people/wangxiaoyun.h tm

The details on the hash collision can be found in the following papers:

Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Finding Collisions in the Full SHA-1,Crypto'05
http://www.infosec.sdu.edu.cn/paper/Finding%20Coll isions%20in%20the%20Full%20SHA-1.pdf

Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Collision Search Attacks on SHA1,2005
http://www.infosec.sdu.edu.cn/paper/Collision%20Se arch%20Attacks%20on%20SHA1.pdf

She has also previously found methods for collisions in X.509, MD4/MD5, HAVAL-128, RIPEMD and SHA-0.

However, the problem is not entirely the algorithms, there will always be collisions on hashing algorithms, if you could represent an infinite amount of data in 160/128/whatever bits then there would be no point in having 161/129/whatever bits, the fact that your hard drive is much larger than that is a testament that collisions in any type of algorithm where you try to uniquely represent X bits in Y bits (where X > Y) (Yes I realize this is a somewhat oversimplified exaplantion).

The problem is in the paradigm in which these algorithms get used, 'one hash to represent them all' is a broken mentality, use multiple hashing algorithms when it matters, while it is indeed possible that the same data can cause a collision in all of the employed algorithms, its incredibly unlikely and AFAIK no one has created a PoC where two sets of data produce the same checksum in both md4 and sha-0.

The article has links to the previous SHA attack papers and Xiaoyun Wang's publication list. (These links were added after the article was posted, so maybe you missed them.)

Heh, thanks :)

As long as we're discussing the MD5 stuff:

Slashdot
E-Print of the original paper
Vlastimil Kilma's research on the topic
The finally released paper by Xiaoyun Wang, the original discoverer of this attack

Enjoy!

--Dan

I think the same as you about that matter, but the chinese researchers have already released the paper containing the full details (I think) of their method:

http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf

I saw this link at the page linked in this /.'s article: http://cryptography.hyperlink.cz/MD5_collisions.ht ml