SHA-1 cracked for $2. Or a load of rubbish?

We’re into the back end of November, so you were probably thinking that nothing would have time to oust Stuxnet as computer security hyperbole of the year.

Seems you were wrong. The security news wires are abuzz with even more dramatic stories today.

I’m not going to name and shame here, since some of those who have written about this are friends of mine. But if you’ve seen any of the many articles about the escapades of one Thomas Roth of Germany, you’ve probably read words to the effect of “German hacker cracks SHA-1 hash algorithm for $2.”

To be perfectly fair to Herr Roth, he isn’t claiming to have cracked anything, though he is suggesting that SHA-1 is no longer fit for one specific purpose: password hashing.

His results do seem to support this contention, but only for very weak passwords used with a very weak password hashing system. So not only has nothing been cracked here, but also his $2 worth of Amazon ‘cloud supercomputer’ time only deals with the pitifully-bad use of a woefully-implemented password hash.

To explain: password hashes are used in many operating systems and web backends as a way to avoid storing a user’s real password, whilst allowing that password to be verified. That means the user’s password isn’t at risk if the password database is stolen.

What you do is calculate a cryptographic hash of the password, and store that instead. Then, to check the password, you hash it again and check it against the stored value. So the password itself never needs to be written to disk – it only needs to be in memory temporarily.

And whilst a cryptographic hash is easy to calculate from its input, it’s also designed to be effectively impossible (‘computationally unfeasible’) to reverse the hash to recover the password. So if you steal a password hash, you can’t go backwards. You have to try every possible password in turn, go forwards by computing its hash, and stop when you get a match. This is called a brute force attack, for rather obvious reasons.

Herr Roth’s experiments did exactly that. He took a challenge list of 14 SHA-1 hashes, and brute-forced all one to six character passwords against that list. In just 49 minutes of ‘cloud supercomputing’, he recovered 10 of the 14 passwords belonging to those hashes.

Big deal.

I can recover 8 of those 14 passwords, using the same challenge list, in the background, on my Macbook Pro, in the same time he took to crack 10 of 14.

Roth stopped counting the elapsed time after he’d tried up to six characters of password; that recovered 10 passwords. I stopped after five characters; that gave me eight hits. These results reflect the unsuitability of the test data passwords, and nothing more.

Also, Roth’s password hash consisted of directly computing the SHA-1 hash of each password. (Each password character was drawn from a set of 94 printable ASCII characters.) But real-world password hashing schemes don’t work like that. They compute the hash of the password, then the hash of the hash, and so on, specifically to add additional iterations to a brute force attack.

Linux, for example, has two mainstream password hashing systems. The older one uses MD5 hashes (which are about 40% faster to calculate that SHA-1s, but use a similar sort of algorithm), and uses 1000 iterations of the ‘hash-of-the-hash-of-the-password’ approach. The newer password system uses SHA256 and SHA512 hashes (variants of SHA-1 which take longer to compute) with 5000 iterations.

So even if we accept 1000 iterations as an acceptable minimum for a modern password hashing system, Roth would need 1000 times longer – and $2000 to blow on Amazon – because each password would require 1000 times as many calculations to hash.

And if we insist that all our passwords are eight characters long, that’s 94 times 94 times as many passwords to check to achieve any sort of success. That’s another increase of nearly 9000 in the so-called work factor.

Not quite so big a story now.

For the record, SHA-1 is considered in need of replacement by cryptography experts. That’s not because it’s been cracked, but because the MD5 algorithm, which uses a very similar internal structure, has been found to have a specific sort of weakness. (This weakness doesn’t apply to the way MD5 is used in Linux password hashing, by the way.)

For that reason, a competition is underway to decide on an internationally credible replacement, to be called SHA-3, for today’s mainstream hashes. A result is expected in 2012. The competition is taking its time because SHA-1 isn’t actually broken yet, so rushing in its replacement without years of deep, expert scrutiny, isn’t actually necessary.