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