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."
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):
... in order 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?
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.
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!
maybe I should have read this first: http://www.freedom-to-tinker.com/archives/000661.h tml
"And now the rumor is that somebody has extended Joux's method to find a collision in SHA-1."
"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. "
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.
This is all true. However, you have to think about how long you need to keep something a secret. Let's say for the sake of argument that you confessed to a murder and encrypted it with single-DES in 1979. Anyone who got a hold of an intercept of it between then and now has evidence of a felony with no statute of limitations. Single-DES has been practically crackable by brute force since at least the mid-90s.
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.
Here is the significance of this story:
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
No, it's the OTP key that needs to be random. The main problems with OTP are that the key needs to be as long as the message, can only be used once, and a secure channel is needed to distribute the key.
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.
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.
"Anyone who attempts to generate random numbers by deterministic means is living in a state of sin." -- John von Neumann
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.
Or say Microsoft signs the hash of Windows XP SP3 with their special key. I tweak the firewall to allow in a nasty backdoor, put data in the padding to give it the same hash as before, and put it out on a BitTorrent site for hundreds of unsuspecting geeks to download. The signature verifies fine, so it must be OK, right?
Karma: Segmentation fault (tried to dereference a null post)
Ummm... 1024x768x32bit = 25165824 bits. Cycling through these bits is exactly equivalent to the "counting up" problem you're responding to. Since we've already established we can't count that high, there's no danger anyone is ever going to show you ever possible picture. Given the thousands of possible variations of goatse guy, this is probably a good thing.
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.
fish and pipes
If there is a fundamental flaw in the hash algorithm itself, simply using it more often will probably not solve the problem.
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."