another cipher bites the dust

[rone]

Bruce Schneier announces that SHA-1 has been cracked.  Thanks to cdy.

Comments

[ronebofh.livejournal.com]

OK, so what's the difference between a secure hash function and a cipher? The former isn't meant to be bidirectional?

[paracelsvs.livejournal.com]

Yes, along with certain other more esoteric cryptographic properties. (Two strings where only one or a few bits differ should generate as different hashes as two strings with many differing bits, for instance. Well, I guess that is true for symmetric ciphers to some extent too.)

http://en.wikipedia.org/wiki/Cryptographic_hash_function

[paracelsvs.livejournal.com]

I should add that one of the esoteric cryptographic properties is that it should be hard to find two inputs that generate the same output, no matter what the output happens to be. "Hard" means "as hard as with a birthday attack" - those work on any given hash function, and will (probably) find a collision in 2^(n/2) tries, where n is the number of bits in the output from the hash function. In the case of SHA-1, n is 160, so a birthday attack would take 2^80 tries. This break finds a collision in 2^69 tries.

[mskala.livejournal.com]

Secure hash functions are one-way; you shouldn't be able to "decrypt" the output of the secure hash to find the input. That's different from a cipher, where you are supposed to be able to reverse it and your adversary isn't. Part of how the one-wayness works is that a secure hash function has a fixed output size, and normally takes a variable-length input; so unambiguous decryption is trivially impossible (there will be many collisions, i.e. different inputs that give the same output, just because there are an infinite number of possible input values and only a finite number of possible output values) but even ambiguous decryption is supposed to be impossible (given an output value, it should be hard to find any input value to give that output, never mind whether it was the "right" one). Ciphers, on the other hand, have an output basically the same size as the input (modulo some additional wrinkles in the case of public-key systems), and decrypt unamibugously (unless they're special ciphers designed not to...).

Also, secure hash functions as such do not have keys, whereas ciphers do. There are reasons you might sometimes want a secure hash that does have a key, but when you want that, you'd normally get it by using a standard unkeyed hash along with a construction like HMAC designed to make an unkeyed hash into a keyed hash.

As I mentioned, it's possible to build a cipher out of a hash function. The reverse is also true - there are ways to build a hash function based on a cipher. That's what Unix crypt(3) does.