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."
Had to happen, didn't it?
No algorithm is all-powerful - it only withstands attacks for so long.
The strength of the algorithm lies in how long it can stand up - to attacks and to future technologies.
It is when Bruce Schneir says so.
It's a hashing algorithm - SHA stands for Secure Hashing Algorithm.
Is it so hard to look it up?
So... anyone care to explain exactly what SHA-1 is?
Sure. SHA-1 is something you could and should look up, thereby gaining an answer more quickly, and not wasting the time of others in a techinical forum.
Next week: How to find the number for 911.
Fucking Google It
Maybe its easier to upgrade from SHA1 than it was from MD5.
Bottles.
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.
In realistic terms, would you have predicted such rapid advancement in computer processing power over the last 9 years? Ok, so maybe the answer to that question is yes, but encryption schemes are not specifically meant to protect things forever, just the length of time that the information contained could be damaging in the 'wrong hands'
Any encryption scheme that lasts about 10 years has given a pretty good service I would think.
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.
Is anyone really surprised by this? In the long run I don't think there is a hash algorithm (or crypto algorithm for that mater) in existence that will not be broken, either by increased computational complexity or some mathematical flaw.
The thing I use these hash algorithms for the most is generating unique ID's without having to think about it too much. I don't believe I am alone either; I don't do a lot of cryptography. Still, I'd like to have a better understanding of the properties of each algorithm, and the class of activities it is good for. A chart along these lines would be neat: "algorithms good for file verification", "algorithms good for password hashing", " algorithms good for higher security needs".
If we start to think of hash algorithms in terms of functional classes, it will be easier to develop drop-in replacements for each of them (something we will need as algorithms keep getting bumped off of the "acceptable" list).
...En að Besta Sem Guð Hefur Skapað Er Nýr Dagur
"can we reasonably move to H(x)=MD5(SHA-1(x))?"
No. The composition of two compromized functions isn't going to solve anything.
I don't think the NSA would gain a lot from a weakness in a secure hash algorithm. In an encryption algorithm, yes, but not a secure hash algorithm.
Need a Python, C++, Unix, Linux develop
s/people/MPAA|RIAA/
There, now it reads more like what will probably happen.
Things you think are in the Constitution, but are not.
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
Damn, just stumbled through the paper on Whirlpool - wow, that is very nice. Downloaded the ref code already and will have a few evenings of digging through new code; always a good time ... well, some of the time anyway (perl, i'm looking at you, sweetie).
.... nags at me you see. They have a very real, very serious intrest in having the most secure, assured, and proofable encryption/hashing/etc algos in the world. Great for them, i'd just like to stick to something from someone else for now ... in case our views of 'private' and 'no-longer-private-for-citizens' begin to differ.
Anyway, you guys should check that paper out: This is a link to their page. Good stuff.
Something else that's nagging me about SHA-1 (and the other SHA family members). Call me paranoid or whatever you like, but we all know the NSA has had the best hardware on the planet for a long time, probably more than just a few razor sharp minds come through (money does talk from time to time), and well, it just does sit plausible with me that a 'perfect' hashing algorithm (or any other for that matter) would be released to the public by the NSA. Let 'em have this flawed one, see what they do with it, can they can break it, see if they break it, if they do, release the next in line of closer-but-not-the-real-deal algos. Just
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
building a DES cracker was possible in 1998 if you had $250K and the know how ( http://www.eff.org/Privacy/Crypto/Crypto_misc/DESC racker/).
There is technology public available now (FPGAs ) that makes it possible to crack DES today (in way less than 3 months computing time) if you spend the $15K on hardware...
That's not quite correct. One-way hashers and block ciphers are really the same thing, just used in different modes of operation. See SHACAL on Wikipedia.
Melissa
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
Doesn't matter. The only difference is key length. The algorithm is the same.
Not quite. SHA-224 and SHA-256 are based on the same algorithm (with some very minor tweaks), and SHA-384 and SHA-512 are related to each other in the same way, but SHA-256 and SHA-512 aren't the same algorithms. Very close in many ways, but some major differences (just to throw out an obvious one, SHA-256 uses 32 bit operations internally, SHA-512 uses 64 bit operations).
And there is no key length here, as these are all hashes.
Now that your law suit has ended, how about releasing your cryptography lecture material in the internet?
No, wrong. This weakness does not allow generation of text with a chosen hash. So the MPAA cannot insert corrupt blocks with the right SHA-1 into someone else's torrent. All they can do is generate their own corrupt torrents, but they (can) do that already.
sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud.
Do you have any evidence for that? SSL, PGP and NTLM all depend on them, as far as I know.
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/
they certainly have the resources.
No, they don't. Not unless (until?) the attack is improved significantly.
In the first place, the attack is a collision attack, not a pre-image attack. That means that it's still necessary to hash, on average 2^159 blocks to find a match to a given block in a given download. They can improve that by looking for a match to any block in a given download, and improve it further by looking to match any block in any download, but it's still going to be computationally infeasible. And I mean computationally infeasible for anyone, even someone with vastly more computing resources than the RIAA.
Second, even if it were a pre-image attack, it requires 2^69 hash operations to succeed. That's still a very large number. Even if they were searching for any of a million blocks in parallel (looking for one match out of a whole bunch of song blocks), and even if their machines could test a million per second, and they had a thousand machines working on it, they would still need on the order of 2^19 seconds per match found, which means they'd find one song per year that they could corrupt a portion of. That's a lot of expense for very little return.
And the attack doesn't allow it anyway.
Your warez and your pirated movies and music are safe.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
That's an awfully vague term. We've got an Ethernet hub with a corner knocked off its case, so theoretically you could say it's "broken", but it still works as well as it ever did. A lot of cryptologic results are like that: we know more than we did before about X, but X is not suddenly rendered useless or even worrisomely less strong. Whereas, in the movies, "we broke their code" generally means, "we have the key and can read their secret messages as quickly and easily as they can."