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."
It's a hashing algorithm - SHA stands for Secure Hashing Algorithm.
Is it so hard to look it up?
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.
"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
That any algorithm is vulnerable to brute-force attacks is totally uninteresting. It's a given in cryptography that given encrypted data, you can try all the possible keys, or re-hash lots of data, until you find one that works. It's up to you to pick a key long enough that it will take anyone else an impractically long time to crack it.
Now, that has nothing to do with this article. These guys are alleging that SHA-1 can be defeated significantly faster than brute-force. This would be a defect in the algorithm and potentially a bad thing. So did this "have to happen"? No, absolutely not. Some algorithms are provably secure for certain purposes.
I'm not a smorgasbord.
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
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
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.
Your example doesn't really make too much sense, and your definition of NP-complete is purely wrong. There are easily demonstrable problems that are not NP-complete where you have to compute the solution for every possible answer, because they are not even in NP to begin with. Example: "If I removed a city from a set of cities in the traveling salesman problem, which city removal would cause the largest reduction in the shortest path length?" In this problem, each possible "answer" (to use your terminology) is NP-complete, thus yielding a non-NP and therefore non-NP-complete solution (unless P==NP).
Furthermore, an NP-complete problem is not unsolvable as you state -- in fact, to be labeled as NP-complete, a solution has to be known. The solution must be formed in terms of a polynomial-time "reduction" from another NP-complete problem. To be NP-complete means merely that the only known solutions would require a non-deterministic "computer" to solve them in polynomial time. As we don't exactly have such machines sitting around, we have to rely on non-polynomial solutions.
Now if we can figure out a way to compute an NP-complete problem in deterministic polynomial time, then all NP-complete problems will be able to be solved in deterministic polynomial time (since all NP-complete problems are declared NP-complete by relating them to each other). But there was always a known solution.
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."