(no subject)

[bellwether]

From: "Steven M. Bellovin" <smb@cs.columbia.edu>
To: cryptography@metzdowd.com
Subject: SHA-1 cracked
Date: Tue, 15 Feb 2005 23:29:43 -0500

According to Bruce Schneier's blog
(http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a
team has found collisions in full SHA-1.  It's probably not a practical
threat today, since it takes 2^69 operations to do it and we haven't
heard claims that NSA et al. have built massively parallel hash
function collision finders, but it's an impressive achievement
nevertheless -- especially since it comes just a week after NIST stated
that there were no successful attacks on SHA-1.

This comes in the shadow of the SHA-0 collisions announced at CRYPTO '04. This means that it's 2048 times easier to come up with a piece of data which hashes to the same hash as a chosen piece of text. It doesn't mean that your banking sessions are insecure--not yet at any rate. It does mean we need to be looking for a replacement algorithm to use for digital signing.

Comments

[bellwethr.livejournal.com]

So, SHA stands for "Secure Hash Algorithm" and it's a standard algorithm for hashing, or reducing a large chunk of data into a smaller, representative chunk of data, often called a hash code--it's kind of like a fingerprint. These are used to quickly look up data. The ideal characteristic for a hash function H() is that if H(x) == H(y) then x == y.

Collisions refer to two different pieces of data hashing to the same hash code. Cryptographers like to talk about ideal, collision free hash functions in which every unique block of data has a unique hash code, but in reality this is a very difficult property to prove. We use hashes in cryptography to create digital signatures of data, proving that the data was not modified in transit. If collisions are possible, it is possible to alter data while leaving its signature intact.

In reality, the news regarding SHA-1 (a supposedly much stronger hash function than SHA-0), means very little in the near term. Collisions are possible, but engineering them in all likelihood still remains difficult. This means while it may be possible in 2^69 steps to generate a piece of data that hashes to a specific value, it will still be very difficult to modify an existing piece of data to make it say what you want to say and still retain the same hash code.

[donaithnen.livejournal.com]

Cryptographers like to talk about ideal, collision free hash functions in which every unique block of data has a unique hash code, but in reality this is a very difficult property to prove.

Actually it's very easy to prove that collisions exist, given the difference in size between the data being hashed and the resulting hash. What they'd like to believe about a supposedly ideal hash is that the distribution is completly random and that you can't take any shortcuts when trying to find a collision.

And in other news, crap, that's going to make work interesting. I don't remember off the top of my head if Crypto API has any other good hashes. I'll have to talk to my boss and see what he thinks about it.

[bellwethr.livejournal.com]

Hah. Good point--you're absolutely right, hashing is a many to one mapping.

[bellwethr.livejournal.com]

Oh, and you're using the Windows Crypto API? You have my sympathy. I dealt with it all summer long last year at Intel. Ugh. I do know X.509 certificate creation and management inside and out now, though... :)