Pure Math III - The SHA Also Rises

While perusing SlashDot, I came across an entry saying that the SHA-1 hashing algorithm has been broken.  If you have any familiarity with cryptography, you'll realize just what this means.  After all, SHA-1 is at the heart of SSL, digital signature and (wait for it) strongly named .NET assemblies.  So does this signify the end of days?  Total anarchy? Cats and dogs living together? 

Not so much.  From a practical perspective, what has really happened is that brute force is no longer the best way to find a string that will hash to a given value. Consider for a moment what the job of a hashing algorithm is:  to take a given string of arbitrary length and convert it to another string of a specified length (160 bits for SHA-1).  The properties of the hash are that there should be close to a one-to-one correspondence between the initial string and the hashed string.  It should also not be possible to regenerate the original string given only the hash.

Of course, complete one-to-oneness is impossible.  There are more strings of arbitrary length then there are of a specified length.  When two strings hash to the same value, it is called a collision.  And it means that when either of those strings are used, for example, as part of a digital signature, the results will be the same.  If it were easy to go from a hashed value to any string that would generate the hash, the algorithm would be poor.

For a few years, it was believed that the best way to find the collision for a given hash was brute force.  That is, randomly generate strings until a collision was found.  What it means to say that SHA-1 is broken is that brute force is no longer the fastest way to a collision.  The researchers have described a technique that reduces the effort by a factor of 2000.  Now that means that instead of 280 calculations, only 269 are required. Still not a meager number, but quite a breakthrough. 

A more complete description of the implications can be found here.