SHA-0 Broken, MD5 Rumored Broken 707
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."
Should We Fear? (Score:2, Interesting)
Don't the laws of computing make it... (Score:1, Interesting)
What are the rammifications? (Score:3, Interesting)
Umm... (Score:5, Interesting)
The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system developped by BULL SA, installed in the CEA DAM open laboratory TERA TECH). It required approximatively 80 000 CPU hours. The complexity of the attack was about 2^51.
What are the ramifications? (Score:3, Interesting)
Firstly, perhaps someone here on slashdot.org might be able to shed some light on the particular encryption algorythms mentioned in the article...thier basic differences, weaknesses and strengths.
Secondly, I am assuming that a "collision" is not as seriuos as a crack...what is a collision, and what are the ramifications of this in my ssh sessions and the like...
I have read about and used encryption, but have never really delved into it. I would venture to say that a good many of us would benefit from some enlightenment.
Re:Consequences? (Score:2, Interesting)
Reading the list, it looks like some people in China managed to produce a hash collision using unknown means...
Although the mention in the paper that the result was obtained in one hour (using a P690, whatever that is) sounds scary... There is very little information though, for example we don't know if the message was special in any way.
Basically, they have managed to find two particular messages which collide, but I'm not yet convinced that they know how to make a collision for any abritary message.
But then... I'm not a cryto person.
Re:Don't the laws of computing make it... (Score:5, Interesting)
In fact, advances in computer speed tend to favor people encrypting data, rather than those trying to decrypt it. For example, increasing CPU speed by a factor of four or five will generally allow you to use a key two or three times as large, and still get the same performance. However, it definitely won't let you crack a key twice as large.
Suppose your faster CPU inspires you to move from 128-bit keys to 256-bit. What happens to the guy trying to decrypt your message? He now has to work 68,056,473,384,187,692,692,674,921,486,354,000,000 times as long, even if he buys the 5x faster CPU. Ouch!
Re:Should We Fear? (Score:5, Interesting)
Re:Umm... (Score:2, Interesting)
SHA wasn't "broken" at all... a brute-force attack found a single collision.
Whoop-dee-do.
Now, if it were possible to generate a message to collide with a given hash, that would be a big deal.
One collision out of 80 kilohours of CPU time isn't newsworthy, IMO.
Re:Collision != Broken (Score:3, Interesting)
>I just don't think this is anything special.
From the article;
The finding of a single collision in SHA-1 would not, by itself, cause much trouble, since one arbitrary collision won't do an attacker much good in practice. But history tells us that such discoveries are usually followed by a series of bigger discoveries that widen the breach, to the point that the broken primitive becomes unusable. A collision in SHA-1 would cast doubt over the future viability of any system that relies on SHA-1; and as I've explained, that's a lot of systems. If SHA-1 is completely broken, the result would be significant confusion, reengineering of many systems, and incompatibility between new (patched) systems and old.
Biggest problem with MD5 breaking (Score:4, Interesting)
Re:Don't the laws of computing make it... (Score:5, Interesting)
Not really...nobody expects this trend in processing performance to continue forever. There are in fact provable limitations given things such as the number of atoms available in the universe that can be harnessed for computation... ignoring little details like quantum computation and such :-). These limitations may seem "out there" but in fact they aren't nearly as unrealistic as you might think. Exponentials grow FAST.
It's trivial to continue scaling the computing requirements required to break encryption schemes by simply adding more bits. That is, assuming the encryption/hash scheme itself doesn't have some fatal flaw which may allow for a sub-exponential cracking algorithm.
Re:Don't the laws of computing make it... (Score:5, Interesting)
More realistically, what if the subject of the communication was a long standing bank account or evidence of a government scandal?
Advances in computing power can work for attackers who stand to profit from a long-delayed payoff. Advances in quantum computing will lower the expiration date of protection for anything you encrypted in the past even more. The further in the past the ciphertext was made, the weaker it gets. This will be generally true for any arbitrary past date and future date. No ciphertext can be considered indefinitely secure. We can only assume that reasonable protection only exists for the short-to-medium term.
Fairly long OTP messages may be one exception.
No, this is a huge deal (Score:3, Interesting)
Re:Should We Fear? (Score:4, Interesting)
The proof that they have computed two values that have the same hash is significant because it proves that it is computationally feasible with today's computing resources to calculate a second different string or dataset that hashes to the same value as the original. It shows that a md5 hash can be "faked" or duplicated using current computing power. There is nothing significant about the values themselves presented in the story just that such values can now be theoretically found in a reasonable amount of time using available resources.
Why this is a bad thing:
Say I sign a program using md5. An attacker writes his own different program and appends some gibberish data in such a way that the two files are different but have the same md5 hash. There is now no way (using md5) to tell the two programs apart. (Of course the programs would have to be similar in other ways, size etc... for the spoof to work.) This same thing could be used to calculate new passwords for md5 hashes that are known to the attacker.
Why should we not panic: It took a long time to find the collision. Chances are a script kiddie wont be able calculate such hashes to crack into your site. But it show that banks or other highly confidential data stores should now look elsewhere for their hashing needs. (Which they probably already do).
Strater
Re:What are the rammifications? (Score:1, Interesting)
What would make that really bad is if the cracker wrote a trojaned version of the software and padded it with extra random data (say in the block padding at the end of a tar file) to make the hashed value of the file come out the same. Now you have a working trojan and a seemingly valid hash.
Re:Don't the laws of computing make it... (Score:5, Interesting)
If you do OTP right, it is unbreakable* because the only possible attack is to brute force it by trying every possible key, and trying every possible key on an n character cyphertext gives you every possible n character plaintext, with no way of telling which one is right. (That is, if you had the 16 character cyphertext "bhgisngukfgxd gyt" you would get all possible 16 character strings as possible plaintexts, including "attack US friday", "shoot Osama soon" and "I like chocolate", and you would have no way to tell which was the actual plaintext.)
*except for rubber-hosing, but that affects all crypto systems, and is a weakness of the people involved, not the crypto.
Re:Don't the laws of computing make it... (Score:5, Interesting)
Re:Consequences? (Score:5, Interesting)
What this means for passwords is simple. People don't decrypt your password and compare it to a stored copy. They hash it, and then store the hash. When you log in, they hash your attempt, and if the hashes match, then the assumption is that the passwords matched, and you are let in. Hashes are very difficult to reverse, which is why they are used. The chances of two passwords producing the same hash is 1/2^2048. However, either one can be substituted for the other. We just trust in the extreme unlikelyness that two passwords would have the same hash and go on our merry ways.
Now suppose that someone has the hash of your password. They may be extremely unlikely to find your password, but they can find something just as good, if a bit unwieldly, since there's no guarantee that the substitute password is just as short as yours. If you don't mind a million character password, then there are likely about 2^8,386,560 passwords that will spoof yours.
why not do both a md5sum and a sha-0 ? (Score:2, Interesting)
Re:Should We Fear? (Score:3, Interesting)
However, I don't know enough about MD5 or SHA-[01] to know if collision is possible for every combination of bytes in certain fixed-sized samples. I suppose only quantum comping can tell. :)
Re:Don't the laws of computing make it... (Score:2, Interesting)
Secrets and lies discusses security not cryptography and does and excellent job at it. Although I had the vegue concept that no security system is really secure before I read the book, I came away from my reading thanking Schneier for drilling the idea into my head so that I would not be naive. It is the best book on security I have read and I recommend it to anyone interested in this facinating field.
Mmmhmm (Score:2, Interesting)
Significance of collision (Score:2, Interesting)
But that period of time should be measured in decades. The author of this paper did it in just a little over 13 days. I'm not quite sure what he did; something about neutral bits... which sounds an awful lot like a way to predict which bits can be switched together to produce the same hash.
Cryptographic strength is based on np complete problems. The problems that you have to solve to break a hash function are typically characterized as one that can only be solved in less than polynomial time by having an oracle function; that is, some way to know the result of a calculation without having to actually do that calculation.
Neutral bits sounds like an oracle function. 80 000 CPU hours on a 256-way system is just a little over 14 days. Now I'm just waiting to see if SHA-1 is vulnerable. (let's hope not!!!)
Re:Should We Fear? (Score:2, Interesting)
1) Has the same MD5 hash.
2) Has the same byte count.
And perhaps most importantly,
3) Still does something an attacker would want it to do (like execute on the target's computer).
Like the parent poster, I won't be losing much sleep over this announcement either.
Re:Don't the laws of computing make it... (Score:4, Interesting)
Want something that will really blow your mind? Think about this: your computer monitor can display anything someone can take a picture of with a digital camera. Anything that is visible, can have its picture taken and thus can be displayed in your 1024x768 32-bit color monitor.
Now, one would normally think that there is an infinite number of possible pictures that one can take in our universe. Heck, just using a paper clip on a table could result in thousands of unique pictures considering the different angles, lighting, etc. Every situation, every person, place or thing you see during your lifetime could have its picture taken and displayed on that monitor! The near-infinite amount of photos that could be displayed on your computer monitor would encompass every visible event from the past, things going on right now, and events in the future. Some of these photos would be real, most would not be.
Above, I assume our computer monitor is 1024x768 & 32-bit color. To see all these pictures -- here & now, in the future on Mars, in a pretend past where Julius Caesar isn't murdered -- all one needs to do is program their computer to serially go through every pixel & color combination. Although it would take a very, very, very long time, eventually every pixel & color combination will be shown, thus showing everything that can ever be seen. A photograph of everything that could ever be seen, and even many situations that didn't/won't happen will be shown on that computer monitor. EVERYTHING.
Of course, many more times that in just random pixels & colors will be shown, too.
If SHA-1 is not enough, use lots of CHFs (Score:3, Interesting)
Basicly you're saying that if SHA-1 alone is not good enough then use some combination of cryptographic hash functions and that will be better.
Well, OK. But it does not address the reason that so many people hope that the attack on MD5 and SHA-1 are not solid. These algorithms have a number of attractive characteristics. They are not hugely expensive to compute (the algorithm above is). They can be used to calculate a (supposedly) unique signature for an input. And the signature does not consume a large number of bits (another problem with the algorithm proposed above).
On a related note: I wonder if the attack on these algorithms has something to do with the number of bits used as input. Intuitively it seems that the larger the number of bits in the input stream, the more unique (widely distributed) the hash should be. So if you used small inputs then collision might be more likely.
Re:Don't the laws of computing make it... (Score:3, Interesting)
Even better, the pigeon-hole principle tells you that infinitely many different events will have the same picture.
Re:Should We Fear? (Score:5, Interesting)
One thing is secure forever (Score:3, Interesting)
One time pads. If the pad's bits are generated by truly stochastic events (say, radioactive decay) and the pad is longer than the plaintext, there is provably no way to ever ever ever ever recover the plaintext without the key; the only method is to simply guess all possible plaintexts.
Re:Don't the laws of computing make it... (Score:4, Interesting)
What should make you feel small is that physicist have figured out a way to count all the possible states for a particular volume of matter (assuming an upper bound on temperature, if that makes any difference). That means the entirety of the observable universe has only a finite number of possible states.
If the unobservable universe is infinite, and if states are distributed probabilistically (and why wouldn't they be?), that means that your hypothetical world where Julius Caesar wasn't murdered actually exists, out there, somewhere, far out of reach.
Re:Should We Fear? (Score:3, Interesting)
The article was referring to software that ran checksums on itself to make sure it wasn't tampered-with as anti-piracy protection, but it could be modified for other uses.
I think it would be more complex on MD5s and such, but...
(too bad Fravia moved on to other things - the articles were absolutely fascinating. Fortunately there are still some mirrors around).
Re:Should We Fear? (Score:2, Interesting)
Really, really no. (Score:5, Interesting)
It absolutely is incredibly hard to make an encryption algorithm more secure. Just "doing some math with the hashes" is the type of bit-twiddling at which cryptologists both wince and sneer. "Then I'll multiply the second one by three, then add them together! Then modulo it 17! Then oohoohooh, square root the whole thing and drop the first digit! No one will _ever_ figure this out!" Crap like this does not add any new cryptographic strength, just a dependency on a secret algorithm. And any method which relies on a secret algorithm is hopelessly flawed.
There is still considerable debate in the cryptographic community about whether 3des is actually any stronger than des. Many people feel that if an attack is found to be effective against the des algorithm, the extra layers of stirring the bits around will not make the plaintext any more secure.
I'm afraid that Schneier covered this succinctly: "Anyone who creates his or her own cryptographic primitive is either a genius or a fool. Given the genius/fool ratio for our species, the odds aren't very good."
Re:Explain ? (Score:3, Interesting)
What has happened here (IIUC) is that somebody has shown that it's possible to create a new file with the same hash key as some other file. Which means that I could put up a file for download and provide a hash key for it, but someone could "mirror" the file and change it to something different which still generates the same hash key. Which means that the "guarantee" that the hash-key gives is broken - a receiver can no longer be sure that a matching hash key means a matching file.
Can be used as a DoS (Score:2, Interesting)
What if you find a hole in the sanity checks, or if there aren't any sanity checks at all? It's highly likely there are many programs out there which "trust" data which passes authentication, and don't bother with much in the way of checking. Now this is obviously a short sighted thing to do, but given that SHA-1 and friends are apparently not broken, I wouldn't be surprised.
Personally, I think breaking authentication has far more effect than breaking encryption. Often all you need is a garbage message to be accepted, e.g:
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.
No, but it will cause the application to fail in an unexpected way: an authenticated .tar.gz which doesn't untar. How about a scarier example: run you an apparently "safe" signed client-side piece of executable code off a web page, except it's actually garbage and it causes your web browser to crash. Or your web server does an automatic update from the vendor only to have its installation corrupted. Or simply inserting garbage but authenticated packets into a network stream thereby causing it to disconnect (or even crash one or both sides).
An interesting thing I notice in the SHA-0 collision is that there aren't that many bits changed - the message looks largely the same. I wouldn't be surprised if you could apply the technique to signed executable code such that a collision is found which would crashes a program in just the right place and just the right way to execute arbitrary code, e.g fork a shell.
What if (Score:3, Interesting)
Unless the hashes have a lot on common, it seems like this would be a simple way to extend the useful life of both hashes.
URL for MD5 Collision (Score:2, Interesting)