Slashdot Mirror
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."
Can a crypto-geek sum up the consequences for all of us dummies? Thanks.
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....
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.
ZZ
"Now, if it were possible to generate a message to collide with a given hash, that would be a big deal."
.tgz? Odds are that any other message with the same hash isn't going to be a valid .tgz.
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
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...
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.
Tom Swiss | the infamous tms | my blog
You cannot wash away blood with blood
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).
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:
- "Joe will send Dr. Blue $10. Confirmation number 1234567."
- "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!
Okay, jokes aside, this shows how social engineering will always be among the best tools for cracking. Krunch, you da man.
taken! (by Davidleeroth) Thanks Bingo Foo!
For more fun see Ultimate physical limits to computation by Seth Lloyd
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.
main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
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
Live today, because you never know what tomorrow brings
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.
-- Ed Avis ed@membled.com
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....