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."
One collision in 2**69 operations... that's quite minimal...
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.
Finding a single collision after a huge search isn't the same as being able to generate a collision on demand, which is what the SHA-1 breakage apparently purports to be.
There's a significant difference.
It is still probably difficult (hard to say without looking at the paper) for someone to find a different document with the same hash as a document you create, but it's now not all that hard to find a pair of documents with the same hash. Someone could give you a document to sign, and get your signature on a different document. Also, IIRC for previous work by this group, the attack applies to chosen pairs of documents with sufficient "random" padding; you can search for a padding for each to generate a hash collision.
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.
The article says that 2**69 hash operations are needed to find a collision. If you have a SuperHashOMatic that can do 1 Billion hashing operations per second, thats still an average time of about 18700 years.
In order for the time to be something to be concerned about (~10 years), you would need a machine capable of doing 1.87e12 hashing operations per second. Thats 1.87 TRILLION hashing operations per second.
Ah, but what about distributed computing?
Let's assume that there are 1 billion desktop computers working on this project. Then they must be able to do 1870 hashing operations per second. This is a ridiculously large number for today's implementations (mine gets 100 per second, most could do about twice that).
So is it bad? Somewhat. Further breaks could make it worse.
We should move away from SHA-1. But this isn't not the end of the world.
SHA-1 is not used for encryption, it is used for message authentication. Part of the NSA's mandate is to secure government traffic; it would gain little from promoting a broken digest algorithm. It arguably might have an interest in promoting a broken encryption algorithm, but SHA-1 is used for digital signatures.
You have a bit of a logic flaw in your comment.
Maybe you don't realise where he is coming from.
With a digital signature, you can easily have knowledge of the signed message (input to message digest function) and thus change the message while retaining the signature.
With a hashed password, you don't have access to the password (input to message digest function).
The hashed password would require figuring out the password so as to allow changing it to make the same hash. This requires going the wrong way against this one way hash algorithm. If you were able to do this, then you would not bother generating an equivalent password, because you would know the original.
I think the point is, that the one way nature of SHA-1 might still be strong. Meaning digital signatures are weak, but hashed passwords are not.
There is no logic flaw in his comment.
War crimes, torture, lies, illegal spying... Would someone give Bush a blowjob, already, so he can be impeached?
Judging from what's been said about how difficult it is to break SHA-1 even with this discovery, I would think it's fine for now, but a new hash should probably be included with BitTorrent2.
Actually most implementations store the salt along with the hash, so that you can move passwords from system to system, systems like nis, certain ldap implementations (read: not Active Directory), etc... wouldn't function if it was a per server salt. It is also much better to come up with a new salt for each password. The main purpose for this is to prevent pre-computed hash tables from being effective. Long live LANMAN :)
Yes, they found a way to break the hash function. But as the parent said, it does not mean it's suddenly invalid. Sure, the group found a way to break the algorithim, but look at According to TFA a collision can be found in about 2**69 hash operations. That's 590295810358705651712 attempts before they can find a match, as opposed to the 2**80 (1208925819614629174706176) that was expected before the paper. While the paper means it is orders of magnitude less work, it still means a lot of work for the attacker. Lets look at two relevant examples: disc images and passwords. Lets say I have an ISO disk image. I hack it, and want to modify some of the 'junk' bits using their algorithm. I'd still need to perform 590295810358705651712 hash operations on that image. Computing the hash of a disc is a slow operation. That's not something I could do in a day, week, or even a few months. Perhaps if I had a massivly parallel computer available, I could do it, but not as an individual. For a password, hopefully your system would lock the account long before there are that many failed login attempts. However, if your attacker has that kind of resources, you can assume it is feasable for them to find a hash collision. That's really only significant for governments, multi-national organizations, and other major enterprises, but not for most people.
//TODO: Think of witty sig statement
although I'll probably get modded down for this I have to say that after reading all of Dan Brown's books I find his plot structure to be exactly the same in every novel, and he exercises very poor character development. :)
It's almost as if the man had a NYT Best seller creating mad-lib.
His Idea of character development is giving them a disability, or a tweed coat
Those who know, do not speak. Those who speak, do not know. ~Lao Tzu
Guess who wants to send meaningless data... bittorrent relies on SHA-1 which is I imagine what the moderator was most interested in.
I might be paranoid but it wouldn't be inconceivably difficult for **AA to upload single blocks of corrupted data and destroy every torrent as it streams, they certainly have the resources.
MD5 was 'broken' in 1995 by Hans Dobbertin who discovered compressor function collisions. It was almost another 10 years before the compressor function collisions were turned into an attack which produced hash collisions.
So there is a serious security problem here but it does not mean that everything that uses SHA-1 is now vulnerable. There are many applications where MD5 is completely adequate. If you have a really good reason to do so and a really good understanding of the security requirements and risks you can use even something like MD2.
Today paul Kocher complained that Microsoft was using MD5 in its anti-spyware to identify known bad software. This is not actually a major problem, much worse would be using MD5 to identify known good software to keep, that is when a collision would bite. For known bad programs well i don't want any variant of the program to run...
But if you are writing an entirely new application then use SHA-256 or SHA-512, more rounds, more bits.
Meanwhile we need to research some new hash functions pronto.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/