SHA-0 Broken, MD5 Rumored Broken

An anonymous reader writes "Exciting advances in breaking hash functions this week at the CRYPTO conference. SHA-0 has definitely been broken (collision found in the full function). Rumors are that at the informal rump session, a researcher will announce a collision in full MD5 and RIPEMD-128. And Ed Felten is speculating about collisions in SHA-1! Many systems, especially those that use cryptography for digital signatures are most at risk here."

Consequences?

[Fruny]

Can a crypto-geek sum up the consequences for all of us dummies? Thanks.

privacy

[bunburyist]

In the wake of stories like this, and last year's story about RSA-576 being cracked (here [slashdot.org]), is this a message that we need more secure forms of encryption than we already have? RSA is great so far, but how long until 1024 is broken? Or any other schemes, like the MD5 hashing that's used for digital signatures? Topics that people with lots of credentials behind their names are going to have to solve. Keeping ahead of the crackers is a big concern not only for security of transactions, but for personal privacy as well.

Re:Just a Thought . . .

[ThisNukes4u]

Well, even if they confirm a collision, that doesn't mean that it can be exploited, especially if they don't release many details of how they got the collision and under what circumstances.

It probably isn't a big deal... or is it?

[chrispyman]

Considering that MD5 is mostly use to "sign" programs, how likely do you think it is that someone could "trojan" your app while keeping the MD5 sums the same. On another note, there could be big problems when we uses these in, oh, a password database. I guess the severity of the problem really depends on how you're using it.

Re:Don't the laws of computing make it...

[BethLogic]

When used properly, One Time Pad is impossible to break. Of course, carrying around enough truely random characters/bytes for all of your encrypting needs without getting caught is another story. And humans are notoriously good at not following directions properly....

The real point...

[chicagozer]

Right, in theory collisions are possible.

However, if the algorithm is weak enough to allow a collision to be manufactured deterministically, then an attacker can craft a substitute message that returns the same hash. Think appending a junk file to the end of an archive to force the same hash.

Can you see the problem with that?

Re:Umm...

[rhysweatherley]

I'm a neophyte, so excuse my ignorance, but how does the fact that a full-time researcher (working on the SHA-0 algorithm), using a computation requiring: (direct quote follows): ... to find two different input values which produce the same output value (I presume that's what they did.. I could be wrong) make _any_ sort of practical difference?

Once upon a time, you needed millions of dollars and specialized hardware to crack 56-bit DES. Now it can be done with commodity hardware and a little time. Moore's Law is relentless. Today's TERA NOVA is tomorrow's PDA.

No, No, No!

[chicagozer]

Obtaining the original data is hardly the point of breaking the hash. You can't recreate the Illiad from 2048 bits for God's sake.
An attacker's goal would be to substitute something else for the original data and make you trust it.

Re:Consequences?

[NotQuiteReal]

It also means you can deny stuff. "Hey Mr. Lawman, sure that encrypted stuff looks incrimidating, but really is is just innocent spam that I encrypted and signed as a test. The fact that you decrypted it to kiddie porn is just a coincidence. Prolly no better odds than O.J.'s blood match - they let him off..."

Re:Should We Fear?

[Anonymous Coward]

Because he's funny?

Re:Should We Fear?

[Anonymous Coward]

Well, I'll take a wild guess:

Because his comment was funny.

Next question?

Re:Umm...

[shadow_slicer]

"Now, if it were possible to generate a message to collide with a given hash, that would be a big deal."

Really? I don't think so.
In order to do anything with it it would also have to pass all the other sanity checks.

Use an faked md5 to put out rootkitted .tgz? Odds are that any other message with the same hash isn't going to be a valid .tgz.

Use md5 to verify logins? Then who cares if someone can generate a message to collide with your password's hash when it's computationally more difficult than regenerating your password.

For the all applications that I've heard md5 being used, I don't think it would be a big deal. But of course I probably am not thinking of some other places md5 is used...

collision != broken

[Rex Code]

I wouldn't consider MD5 "broken" unless someone had discovered an easy way to add bits to an existing file to produce a desired checksum. If that were the case, I'd be seriously concerned.

Finding a single example of an MD5 collision in 80000 CPU hours is an interesting exercise, but I think we always knew collisions were possible (with any hash function), and I fail to see how this finding reduces the security of MD5 in any practical way.

Mod this legerdemain down

[Anonymous Coward]

He subtly switched from "checksum" to "hash" starting from his point #2 in order to demolish the grandparent's post about "checksums" using arguments for "hashes".

Re:Of course!

[prichardson]

You seem to have misunderstood my post. In any function where f(a) can never equal f(b) where a and b are two unequal real numbers there is an inverse to function f. The reason that MD5 works for what it's intended to is because it has collisions. Since it has collisions, and because it's a fairly complex function, it's impossible to come up with any kind of inverse. With anything that isn't loss-less compression you can't be absolutely sure that you have the same data that was originally hashed. There is always going to be some input that will generate the same hash. Hashes are used to reduce the probability that your data has been tempered with. Hashes reduce the probability so much that everyone considers them proof that no tampering has been done, including me. Until someone can use a hash to create a file that can be hashed and get THE SAME hash MD5 will not be broken.

Re:Don't the laws of computing make it...

[Mr. Slippery]

Not really, because you could still guess what the pad is on your first shot. It's not likely, but its not "impossible".

The beauty of the OTP is that it doesn't matter if you guess what the pad is - you can't tell you've got it rigbt.

Given a cyphertext of length 9, there are keys that will decrypt it to read "Kill Bush", "Save Bush", "FuckOsama", "Bomb Iraq", "Love Boat", "qwertyuio", "!@#3fst9$-", and every other 9 character string. Since the OTP is random, all these keys have equal probability of being the correct one.

Re:collision != broken

[44BSD]

Collision == broken if the reason the collisions were found lies in a property of the algorithm which until now was misunderstood.

Collision == broken if the research leads to subsequent work which further weakens the algorithm.

Agreed that finding a collision via an exhaustive search is no big whoop, but I don't *think* that is what this rumor is about ;^).

Basically, that crack in your foundation *might* be no big deal, but it *might* mean that there's a spring running 6" below the foundation wall and in six months your mansion collapses.

Re:Paradigm Shift long overdue

[Anonymous Coward]

Argh!!!! Digital Fortress had good characters, but absolutely rotten-to-the-core technicals. It's funny that someone would quote the "Bergofsky Principle", which Dan Brown made up out of the whole cloth (I've certainly never heard of it). The author is a technology ignoramus, which is not a fatal flaw except that he was pretending to be an expert, and getting almost everything wrong to one degree or another. The fact that I finished reading it is a testimony to his skill as a crafter of good fiction writing, not to its interest as a techno-thriller.

See earlier post about a thought experiment Bruce Schneier carried out that showed 256-bit symmetric encryption (if it had no holes) would be proof against any attack that could be carried out using (using our current knowledge of physics, that is).

Probably not a big deal...

[barfy]

The discovery of a single collision is not a big deal. Discovery of an algorithm to create a collision WOULD be a very big deal.

The greatest weakness would be in password systems where only hashes are stored. If you could create an arbitrary password that had the same hash as one stored on the system (and there have been attacks on the password generation side, but none successfully on the side of specifically creating a password *based* on a hash), then you can get in.

There may yet be discovered a formula for creating that collision, now that we have discovered one, we can determine if there is a relationship between the two plaintexts that can be exploited if we know either the plaintext, or the hash, and can generate an arbitrary collision.

Document signatures are much less problematic. You would have to create a *sensible* document to replace the hashed document. This is way less likely to occur, to the point that would be attacking by far the strongest link in the chain.

Re:Should We Fear?

[Dr. Blue]

First step is MATCHING some checksums (this has been done)
The next step is CHOOSING the chekcsum (aka DEADBEEF attack)
The next step is MANIPULATING, i.e. adding junk to a given binary file to allow you to choose the cheksum. that's the scary one!

Actually, you can do interesting and dangerous things with variants of your first step, not even progressing to step two. The MD5 collisions (well, almost collisions) are largely the same input data that has differences in only a few places. Now imagine that I have two messages that say something like this:

1. "Joe will send Dr. Blue $10. Confirmation number 1234567."
2. "Joe will send Dr. Blue $100000. Confirmation number 6451234."

Now lets say I can manipulate the confirmation numbers in those two messages so that they have the same hash value -- I don't care what the hash is, as long as it's the same in both cases. Then I send you the $10 message.

If you agree, you sign it. But you realize that digital signatures don't actually sign the message, right? They sign the hash of the message, so I can later produce the $100000 message, with your signature, and it will verify that you signed that message!

Re:md5 is so weak

[Bingo Foo]

Okay, jokes aside, this shows how social engineering will always be among the best tools for cracking. Krunch, you da man.

Re:Don't the laws of computing make it...

[MG]

Indeed, here's another novel argument from Bruce Schneier's book.... in regards to the strength of 256-bit encryption: now, the annual energy output of our sun is about 121 * 10^41 ergs. this is enough to power about 2.7 * 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. if we build a dyson sphere around the sun and captured all of its energy output for 32 years, without any loss, we should power a computer to count up to 2 ^ 192. of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

That is an erroneous conclusion based upon the (incorrect) assumption that a small amount of energy (kT) must be dissipated for each elementary computational step. If the computation is carried out using a reversible (classical) computer, this is not the case. Thermodynamics does not place any such restriction on computation. On the other hand, quantum mechanics does place constraints on the speed of a classical computer.
For more fun see Ultimate physical limits to computation [arxiv.org] by Seth Lloyd

Re:Should We Fear?

[Anonymous Coward]

Nothing to worry about yet, sort of like the first proof-of-concept brute force crack of DES.

... the first proof-of-concept DES crack that we know about.

Re:Don't the laws of computing make it...

[Spy Hunter]

Also, with using individual atoms for computing, whilst it would be nice, it's also impossible(?) - given that the more accurately you try to measure one property of an atom, the less accurately you can measure it's other properties. There's a name for this, but I can't remember.

It's the Heisenburg uncertainty principle, and it doesn't rule out computing with individual atoms. It just means that computing with individual atoms will work a lot differently than it does with normal, mostly deterministic electronics. The field of quantum computing is all about exploiting the weird quantum properties of atoms to do even more computation than would be possible if they were completely deterministic little point particles.

breaking BitTorrent

[oskie]

Finding a SHA-1 collision would break current versions of BitTorrent. Recent versions identify each piece of the file by its SHA-1 checksum. First the pieces are downloaded out of order, in consecutive order. Then they are reordered based on SHA-1 checksum. If one put two different pieces with same SHA-1 checksum in a file, it is likely that 50% of the time you would end up with an invalid file if transferred over torrent. This could be used to prevent certain files to be transferred over BitTorrent, such as copyrighted files.

Re:Should We Fear?

[Spy der Mann]

That's why we'd need LOCAL hashes and not just one big global hash.

So let's say that for a 160megs file you store an md5 hash for every chunk (1, 2, 10 megs maybe?),

AND THEN you check the global MD5...

or who knows. Just do some math with the hashes themselves. It's not that hard to make an encryption algorithm more secure.

Like they did with DES -> 3DES.

Re:Probably not a big deal...

[evilviper]

If you could create an arbitrary password that had the same hash as one stored on the system [...], then you can get in.

Well, that doesn't have much to do with *collisions* at all.

If you have any method at all (collisions or not) to generate a string from a hash, then you have a problem with password systems... A collision would only be necessary if, for some strang reason, finding the ORIGINAL password isn't good enough, which isn't the case in any password-protected systems I can think of.

we can determine if there is a relationship between the two plaintexts that can be exploited if we know either the plaintext, or the hash, and can generate an arbitrary collision.

Well, if you need to have the plaintext to generate the collision, it's not at all useful for finding hashed values, such as passwords.

Document signatures are much less problematic. You would have to create a *sensible* document to replace the hashed document.

Indeed, it would be extremely difficult to exploit a collision, even if you do have a method to find them easily...

Sigh...

[Kjella]

1. If you can produce a hash collision between two random inputs, that is rarely a problem. Either input will be junk. It doesn't matter that you have two interchangable pieces of junk.

2. If you can produce a hash identical to a desired hash, you can mostly only sabotage (poison) a transfer.

3. If you can take an existing file and append data to match a hash, you have a total and very dangerous compromise.

From what I can tell, we're at #1. Make it #2, and things will break as people move to a new algorithm, but I doubt there'll be much problems. Now do #3, and I'm worried...

Kjella

Re:Explain ?

[Ed Avis]

Nobody has 'shown that it's possible to create a new file with the same hash key as some other file'. That has been known all along and it's true for any hashing function where the length of the hash is shorter than the length of the original file. For example, if your hash function produces a result 100 bits long then there are 2 ** 100 possible hashes. Obviously there are more files than this so it is _always_ the case that there are two different files with the same hash value. Usually I'd expect an infinite number of files with any given hash value!

So I don't know what the news item is here, except as a curiosity ('look we found it' - like finding the next Mersenne prime) or some technique has been found for making hash collisions which is better than brute force. If all they did was brute-force hash lots of files until finding two with the same MD5sum or whatever, it's obvious they were going to find a collision eventually.

Re:Umm...

[rew]

For passwords, the collision avoidance of MD5 will make sure that your very complicated password is not "cracked" by some stupid child typing "hi" at your password prompt. But not much more.

The important issue starts when you use PGP to sign your message.

Suppose you sign:

mybank: Please transfer $100 to my son's account: 12345678 ref: Have a nice vacation!

then your PGP program will calculate the MD5 sum of this message and sign that using RSA (or DSA). As all know those algorithms are very very strong.

Next, the attacker will change your message to:

mybank: Please transfer $1000,000 to J. Crook account 87654321 Ref: XXXXXXXXXXXXXXXXXXXXXXXXXXXX

and when the crook can then adjust the XXX part in such a way that an MD5 has collision occurs.... You just authorized your bank to do something you may not have wanted....

There should be about 28 X's in there. That will allow the crook over 2^160 possible messages. Trying them all, there is a high probability that at least one of them has a hash collision with your signed original message. If calculating which one of the possible over 2^160 messages has the "right" MD5sum, costs significantly less than 2^160 operations, then that's considered breaking the hash....

Re:Should We Fear?

[Dwonis]

It's not quite so simple.

I don't know about other public-key algorithms, but with RSA, the numeric value of your message must be less than the modulus. So if you want to directly sign a 100 MB file with a 2048-bit RSA key, you have to split the 100 MB file into at least 390625 separate messages, and sign them individually. Even then, you run into problems with people re-ordering your messages, so you'd have to insert some sort of sequence-numbered header into each sub-message to prevent that.

With that many signatures and a predetermined header format, you start giving out an awful lot of data to perform known ciphertext attacks on.