Slashdot Log In
SHA-1 Broken
Posted by
timothy
on Tue Feb 15, 2005 10:25 PM
from the sha-na-na dept.
from the sha-na-na dept.
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Sigh (Score:5, Funny)
Re:Sigh (Score:5, Funny)
About a month ago, I needed a mechanism for password hashes.
After some research, I decided that SHA1 was more secure than MD5.
So I hunted down some good public domain SHA1 code, read through it, and added it to my code.
Thanks /.!
Parent
Not a problem (yet) (Score:5, Informative)
OTOH, this attack indicates that other types of attacks may be found sooner than was previously thought. So it is still a good idea to move away from SHA-1 in the medium to long term. Though it's not entirely clear what you should move to. And it is not certain that more attacks will be found soon.
Parent
Re:Well... (Score:5, Funny)
Parent
Info on what exactly SHA-1 is ... (Score:5, Informative)
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
Parent
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
Parent
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
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).
Parent
Re:Info on what exactly SHA-1 is ... (Score:5, Insightful)
Parent
Re:Info on what exactly SHA-1 is ... (Score:5, Insightful)
There's a significant difference.
Parent
Prison. (Score:5, Funny)
Time to start a panic (Score:5, Funny)
Brought to You By (Score:5, Informative)
US Secure Hash Algorithm 1 (Score:5, Informative)
SHA-1 Hash Algorithm [ietf.org] and Source Code [cr0.net].
Bittorrent? (Score:5, Interesting)
How hard is it going to be for people to provide garbage data with correct SHA-1 hashes to screw up downloads?
Broken, but not for everything... (Score:5, Insightful)
Sure, for signatures, it means that you can't trust the algorithm 100% anymore.
But for storing passwords, and other operations where collisions are not important, it doesn't matter much, even if there's another password that can generate the same hash, you still need to brute-force it.
So what's the big deal for the rest of us? (Score:5, Interesting)
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!
Re:So what's the big deal for the rest of us? (Score:5, Insightful)
Essentially, don't sign anything that someone else has given you without changing it in some way, or your signature might also apply to some other document they have chosen.
Parent
Unfortunately the SHA series seems to be suspect (Score:5, Interesting)
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.
Re:Now what do we use? (Score:5, Informative)
The Hashing Function Lounge [terra.com.br] also lists Cellhash, Parallel FFT-Hash , RIPEMD-128, RIPEMD-160, Subhash and Tiger as (so far) unbroken.
Parent
Re:Well (Score:5, Informative)
No algorithm is all-powerful - it only withstands attacks for so long.
No, it didn't. In fact, this is the most important problem in CS. The theory is that there are certainly problems where checking a solution is easy (2 and 3 are unique factors of 6 because it's easy to see that 2*3 == 6) but where the only possible way to find the solution given the answer is to compute the solution for every possible answer.
It's not been proven whether hashing is this type of problem (whether it's NP-complete). Moreover, it's never been proven that there isn't a solution for problems we think are NP.
What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.
Parent
Re:Yeah... (Score:5, Informative)
I'm not sure if you are talking about retrieving the original file from the hash, but if you are, then you don't understand what hash functions are for. In this case, there are an infinite number of combinations of bytes that have the same SHA-1 hash. The goal is to find one that has the same hash value, regardless of whether it is actually the same file. SHA-1 is not a cipher.
Parent
Re:Damn it (Score:5, Informative)
Some attacker would have to be REALLY dedicated to use this vulnerability to harm you, and they would still require hideous amounts of processor time to mount an effective attack. Digests are a quick and easy way to verify that some message or file is correct. If the hash is signed as well, then you can verify the sender, too. When you download something like a Linux ISO, there is often another file on the server containing the hashes of the files, so you can verify that everything downloaded correctly. If you want to make sure that nobody other than a trusted person modified the files, then that trusted person could encrypt the digest with their private key, allowing anybody with their public key to verify that everything's correct.
A person can, with a broken hash, create another ISO file, perhaps with malicious code inserted, that has the same digest, meaning you can no longer trust the signed digest. Let's say that this vulnerability reduces the average time needed to find a collision from 2^48 tries via the Birthday paradox (If this isn't a 96-bit hash, then I really need to get more sleep) to 2^32 tries. That's over 65,000 times faster, but you know why I'm not worried? That's still over 4,000,000,000 ISO files that the attacker would have to try before hitting on one that's got the wanted characteristics and the correct digest to boot, and if it requires equivalent memory usage to its time usage, then I'd expect it to use at least 48 gigabytes of memory to store all of the previous attempted hashes. If it takes 15 seconds to compute one digest, then you're looking at a mere 2,000 processor years to find a vulnerability, compared to the much more comfortable 130,000,000 processor years that it would have required using the brute force method.
Feel better now? If I really got mixed up, and was wrong about the size, then just multiply all the listed times by 2^32, and wake me in 8 trillion AD.
Parent
Re:Hmm (Score:5, Informative)
Not true. SHA-1 is the hashing algorithm of practically all common security standards. It's found in SSL/TLS, X.509, PGP (the protocol, not the program, so that means GPG also!), S/MIME, etc. In other words... everything. Replacing this is going to suck.
Parent
Re:May be a big deal... (Score:5, Informative)
You do not quite understand correctly. MD5 and SHA-1 are hashing algorithms, and as such it is expected (and accepted) that there are collisions. That is, you might find that your
That is, you can either keep a backup copy of your filesystem to compare against or you can keep a list of hashes, and mathematically, all this "break" has demonstrated is that the chances are 1:590295810358705651712 not 1:1208925819614629174706176 of a collision. In other words, don't lose sleep.
Now, for secure cryptographic signatures, the implications are much more unpleasant. It's not the end of the world, but this is that big red light that says: switch to SHA-512 (or something equally secure) ASAP!
Parent