another cipher bites the dust

[rone]

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

Comments

[lusercop.livejournal.com]

Thank god NIST have certified SHA-256 and SHA-512 (http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf) then (FIPS180-2), I guess. I don't know what the current status of the NIST DSS is, though. DSS(v1) specifies SHA-1 and relies on the 160-bit block, IIRC. This is, if true, lots of fun after people have just started the long process to migrate away from MD5 and towards SHA-1.

[nothings.livejournal.com]

If 2^69 is insecure, why isn't 2^80? They're only a factor of 2000 apart. Where do you draw the line?

[paracelsvs.livejournal.com]

It's not "secure" or "insecure", it's "not broken" or "broken". Anything less than the brute-force results means the algorithm is broken. It may still be secure, and in this case it should be, but it is definitely no longer trusted. Further research may find an even faster attack.

[mskala.livejournal.com]

You draw the line at brute-force. Collision on an n-bit secure hash ought to require 2^(n/2) operations, which in the case of the 160-bit hash function SHA1 means 2^80. That's how long it takes to attack by brute force, which is an attack that would work on any hash function of the same size regardless of its internal workings. If your function can be attacked faster than that, then your hash function is broken, in the precise technical sense of "broken" used by cryptography people.

In the case of MD5, which is a 128-bit function, the theoretical best possible security is 2^64, so SHA1 is still ahead of the best security MD5 ever claimed to achieve, on raw numbers - but raw numbers are the wrong thing to compare.

[mskala.livejournal.com]

But SHA-256 and SHA-512 are designed on the same principles as SHA1. It seems quite plausible that the recent attack on SHA1, which is basically another example of the same technique that was also successful against MD5 and some other similar hashes, would be applicable to SHA-256 and SHA-512. It would be preferable to study the attack and find some hash function that can be proven not to be vulnerable to it.

[tongodeon.livejournal.com]

The part I still don't understand is how this gets turned into encryption. I understand that you can use hashes to certify the state of a file, digesting a large amount of data into a 128-bit string, but I don't understand how this can be applied to a cryptographic system.

[mskala.livejournal.com]

SHA1 isn't an ecryption system; it's a secure hash function. The title of tihs posting is misleading, because it's not a "cipher".

However: hash functions like SHA1 are normally used along with ciphers, in contexts where they are important to the security of the overall system. An example would be in SSL-protected Web connections, where if I can generate hash collisions, then I can take the valid signature from a certificate of a server I want to attack, instead attach it to a fake certificate of my own invention that also has the same hash value, and then use the fake certificate to authenticate to you. You think you're establishing a secure connection to Amazon, actually you're establishing a secure connection to me, you type in your credit card number, I capture it. The design of signature schemes sometimes means that I can do this general sort of thing just by creating collisions (two different strings with the same hash value) instead of the more difficult preimages (a string with a chosen hash value the same as the hash value of some other string I don't get to choose).

It is also possible to construct ciphers based on hash functions (the "Luby-Rackoff construction" is one thing to look up for more information on that), so that if you have a hash function you really trust then you can use it to build a cipher that is provably at least as strong, but those constructions tend to be inefficient, aren't used in practice, and aren't really a big concern.

[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

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

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