Slashdot Mirror
SHA-1 Broken
Nanolith writes "From Bruce Schneier's weblog: 'SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results...'" Note, though, that Schneier also writes "The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team."
So SHA-1 was created by the NSA, and was broken nine years after it was released. Is there any chance that the NSA knew it had a secret weakness, and promoted it for that specific reason?
Is it time to update bittorrent?
How hard is it going to be for people to provide garbage data with correct SHA-1 hashes to screw up downloads?
Rats would be more funny if they could fart.
I'm not a cryptographer, just a nerdy engineer, but let me explain my rationale: a hash algorithm takes an arbitrary message and generates a fixed-length signature that has a high probability (10**50 or better for most modern algorithms) of being the original.
Let's assume that your hash algorithm generates a 128-bit hash. Anyone who knows anything about probability can see that is the original message is greater than 128 bits, there MUST be more than one message that will generate the same hash. For long messages, there may be thousands or millions of messages out of a filed of 10**50 (or better) that have the same hash, although many of them will be meaningless garbage.
So SHA-1 has been broken by a group of cryptographers/mathematicians. Does this really mean that they can generate can alter any message in a way that will generate the same hash as the original, thus fooling the math that we use to validate content? No Way! I read Bruce Scheier's Cryptogram every month and he often makes the same argument.
So yes, this means that from a long-term systems security standpoint, we should all move to stronger hashes. Does it mean that SHA-1-based transactions are inherently secure right now?
I think not!
If this definite break is confirmed, I think we will need to conclude that the entire family is suspect for any genuinely important purpose.
There are a bunch of hashing algorithms on the Hashing Function Lounge that are listed as having no known attacks. At present, the most widespread is Whirlpool. I think it likely that one of these will replace SHA as the hashing function of choice in major cryptographic areas.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
DES had a weakness nobody but the NSA knew about, so they recommended changes to it without saying the reasons for them. years later an attack was found against DES, but the NSA changes prevented it from being useful. Why would they change their tune to SHA-1?
Your hair look like poop, Bob! - Wanker.
So SHA-1 was created by the NSA, and was broken nine years after it was released. Is there any chance that the NSA knew it had a secret weakness, and promoted it for that specific reason?
I don't know about this, but when SHA (the Secure Hash Algorithm) was submitted as an approved algorithm for government use, the NSA reviewed it and suggested a minor change. That modified algorithm is what we now know as SHA-1. It was a few years before public-sector cryptographers caught on to what the significance of the changes was (I wish I could explain it, but it is beyond me).
Thought by much of the Slashdot community, as general reaction to this article shows. Until today, the prevailing Slashdot wisdom was that MD5 was weak and broken and SHA-1 was strong. Now we know that's not the case. Maybe this is no surprise to your circle of cryptography guru friends, but nobody told me until now.
main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
You know, of course, that the NSA did the same thing with SHA right? The original algorithm submitted was SHA-0, then the NSA recommended an unexplained minor change.
Last August SHA-0 was broken, so their tweak appears to have added about 6 months of extra life for SHA-1.
What about what OpenBSD is doing? Have multiple hashes per file (MD5, SHA1, etc..) for a given signature.
For quite a few applications the hash is broken even if I cannot easily find a second string with the same hash as one given. Even if I can "only" at will find two strings with the same hash, that is a pretty serious weakness.
I could, for example, create two documents with the same hash, have you sign one, and then claim you signed the other one. Since the hashes are the same your digital signature will be valid for both.
For other applications, like replacing a signed document with another without being detected you're rigth -- that would only work if one could easily find a document with a given hash.