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."

Well

[metlin]

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.

Re:Broken or not?

[defile]

It is when Bruce Schneir says so.

Re:Hmm

[metlin]

It's a hashing algorithm - SHA stands for Secure Hashing Algorithm.

Is it so hard to look it up? [wikipedia.org]

Re:Hmm

[Anonymous Coward]

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.

Re:Hmm

[mek2600]

Fucking Google It [fuckinggoogleit.com]

Re:Sigh

[ottothecow]

Well, without /. they would be quietly circulating a paper on how to break your hashes and it would still be quiet.

Maybe its easier to upgrade from SHA1 than it was from MD5.

Broken, but not for everything...

[JM]

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.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Broken, but not for everything...

[beaststwo]

You never could trust it 100%! That was the idea! The algorithm gives you a very high probability of authenticity, not any kind of guarantee (unless the original message is shorter than the output of the hash and everyone who hashes it later absolutely knows the length of the original message).

It's an assurance, that's all. The only guarantee is a one-time pad, and Bruce Schneier's website is full of info on why these aren't practical!

Re:And they scoffed at my continued reliance on MD

[js7a]

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.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

Any encryption scheme that lasts about 10 years has given a pretty good service I would think.

SHA-1 is not an encryption scheme, it's a cryptographic one-way hash function.

There's a significant difference.

Re:Unfortunately the SHA series seems to be suspec

[tidewaterblues]

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).

Re:Let me be the first to say...

[Vidael]

"can we reasonably move to H(x)=MD5(SHA-1(x))?"

No. The composition of two compromized functions isn't going to solve anything.

Re:Info on what exactly SHA-1 is ...

[Omnifarious]

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.

Re:Well

[Herbmaster]

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.

Re:Bittorrent?

[Mr. Sketch]

s/people/MPAA|RIAA/

There, now it reads more like what will probably happen.

Re:So what's the big deal for the rest of us?

[iabervon]

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.

Is it that bad?

[Anonymous Coward]

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.

Re:Info on what exactly SHA-1 is ...

[ftobin]

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.

Re:Not a problem (yet)

[Shanep]

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.

Re:Bittorrent?

[rsmith-mac]

I don't think it's practical right now, but that doesn't mean it will hold true for too much longer. As it stands right now, BitTorrent files have 2 hashes: each chunk has a hash, and then the file as a whole has its own hash. This means that for a torrent to be perfectly polluted(that is, polluted without anyone knowing), the garbage data needs to fit both hashes, which will be harder, though breaking a chunk hash is enough to kill a torrent swarm, even if users know about it. However, the **AA organizations aren't exactly poor, and as unlikely as it is, they do have the finances to get access to a large computing cluster, which would allow them to cause some damage.

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.

Re:Both statements are fine -- salt explained

[Knightmare]

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 :)

Re:Sigh

[Frobnicator]

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.

Whirlpool paper: an eye opener.

[Anonymous Coward]

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).

Anyway, you guys should check that paper out: This is a link to their page. [terra.com.br] 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 .... 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.

Re:Info on what exactly SHA-1 is ...

[jessecurry]

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 :)

Re:I'm still content with SHA-1 and DES

[Anonymous Coward]

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...

Re:Info on what exactly SHA-1 is ...

[Myria]

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 [wikipedia.org].

Melissa

Re:Well

[ityllux]

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.

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.

Re:Time to switch....

[Anonymous Coward]

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.

Question for you

[Anonymous Coward]

Now that your law suit has ended, how about releasing your cryptography lecture material in the internet?

Re:So what's the big deal for the rest of us?

[boots@work]

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.

Re:Hmm

[boots@work]

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.

Re:Cryptographic break =/= practical break

[Deliveranc3]

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.

Don't panic! 'Broken' is not Cracked

[Zeinfeld]

After some research, I decided that SHA1 was more secure than MD5.

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.

Re:Cryptographic break =/= practical break

[swillden]

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.

Re:Don't panic! 'Broken' is not Cracked

[jlcooke]

Humm, no.

Differentials in SHA-256 can be found with the new techniques.

The problem is with the new differential attack our Chinese friends discoverd. Fidning differentials through addition mod 2^32.

SHA-256 uses the same. For now, yes, it's safe. But as of right now, the crypto community is hugerly trying to build new hashs with more complex compression function chaining. Whirlpool is an example of this newer view on hash functions.

It's based heavily on AES's core operations which would make me feel uneasy. Diversity in the underlying techniques for crypto algos is exemplified here by how just about every hash we use today fell because of a lack of diversity.

In short:
- Use SHA-256 for now.
- In 2-3 years, upgrade to whatever becomes the standard, it'll be stronger than SHA-256

Please define "broken"

[mwood]

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."