Say goodbye to SHA-1
Thursday, August 18. 2005, 00:31
Xiaoyun Wang, chinese cryptographer and well known for her analysis of the SHA1 function, was not allowed to travel to the US to attend the Crypto conference starting today (via Bruce Schneier).
Too bad, because she discovered some new results on the attacks on SHA1, which reduce it to a complexity of 2^63 to generate a collission. Adi Shamir, well known cryptographer and one of the RSA-inventors, presented these results.
These news are important, because 2^63 is a complexity that can be broken with todays hardware if you invest enough money and time. This would be an interesting project for distributed computing, although I don't know if the attack can be implemented on common hardware (maybe someone with cryptographic experiences wants to comment if this is possible).
Too bad that most software devs have not noticed the recent results on hash-functions. Most of them still use MD5 (which has been broken about a year ago), SHA-1 is widely used. The GNU Coreutils don't have any tools for modern hash-functions, same goes with most programming languages (PHP, Python), while they implement some sort of md5sum or sha1sum, no sha256sum or whirlpoolsum at all.
Too bad, because she discovered some new results on the attacks on SHA1, which reduce it to a complexity of 2^63 to generate a collission. Adi Shamir, well known cryptographer and one of the RSA-inventors, presented these results.
These news are important, because 2^63 is a complexity that can be broken with todays hardware if you invest enough money and time. This would be an interesting project for distributed computing, although I don't know if the attack can be implemented on common hardware (maybe someone with cryptographic experiences wants to comment if this is possible).
Too bad that most software devs have not noticed the recent results on hash-functions. Most of them still use MD5 (which has been broken about a year ago), SHA-1 is widely used. The GNU Coreutils don't have any tools for modern hash-functions, same goes with most programming languages (PHP, Python), while they implement some sort of md5sum or sha1sum, no sha256sum or whirlpoolsum at all.
Comments
Display comments as
(Linear | Threaded)
Couldn't gentoo (and others) use two algorithms (md5 AND sha-1 or an other one) to check for errors and possible modification? Surely fooling one algorithm is becoming easier, but fooling two on the same file has to be way more complicated ... wouldn't it?
Rémi
Rémi
That doesn't help that much. It only improves the security to the better one of the hash-functions and some bits more. It makes no sense to use two broken functions, but it maybe is a good idea to combine several of the new hash-functions, because they're not so well testet and may discover unexpected weaknesses (e.g. using sha-256 + whirlpool + tiger).
I think you didnt understand the initial comment. Trying to modify a file in such a way that would produce a collision with one algo surely cannot also produce a collision with another. The question involves whether there is any gain if integrity is your goal and you take a SHA1 of a given file as well as an MD5 (both of which are 'broken') -- not an MD5 of a SHA1 sum.
-tjs
-tjs
While these results sure are a great advance in cryptography, their effect on practical uses of MD5 or SHA1 is greatly overrated, IMO.
For example, the story on MD5 is here -> http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html
It says that you can produce a collision in such and such time and that the algorithm is not mathematically perfect since it produces collisions in the first place. This is very different from being able to break an MD5 digest in such and such time - to do it you need to generate a new message with a given hash, not any two messages with the same hash.
I have not read the entire paper, but the fact that collisions exist does not, by itsefl, imply that they exist for any digest.
In short - even if you were able to create a collision for a given digest, which AFAIK you can not do, there are far simpler and cheaper ways of breaking our precious portage tree :)
For example, the story on MD5 is here -> http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html
It says that you can produce a collision in such and such time and that the algorithm is not mathematically perfect since it produces collisions in the first place. This is very different from being able to break an MD5 digest in such and such time - to do it you need to generate a new message with a given hash, not any two messages with the same hash.
I have not read the entire paper, but the fact that collisions exist does not, by itsefl, imply that they exist for any digest.
In short - even if you were able to create a collision for a given digest, which AFAIK you can not do, there are far simpler and cheaper ways of breaking our precious portage tree :)
Add Comment
Hanno Böck explained the current state of SHA1-brokeness.
Tracked: Aug 18, 12:34
SHA-1 ist tod. ...
Tracked: Aug 18, 15:38
As the article some days ago about SHA1 got a lot of interest, I thought I'll write some more background info about this, especially for people thinking that collisions aren't a big problem. Cryptographic hash functions are functions where you can put
Tracked: Aug 22, 01:05