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.
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.
9 comments on “SHA-1 cracked for $2. Or a load of rubbish?”
SHA1 needs to be replaced because MD5 has problems? something seems a little off about the cause and effect relationship there.
The internals of SHA-1 (and, for that matter, the SHA256 and SHA512 hashes) are very similar to those of MD5. More rounds, bigger hash sizes, but the same basic 'mechanical components' for mixing together the input data to produce the hash.
So a conservative cryptographer might reasonably assume that the cryptanalytical techniques used to attack MD5 (now known to be unsafe against calculated collisions) could be developed and extended to attack SHA-1 and other hashes of that basic internal type.
The link I gave above (to NIST's competition), says it fairly simply: "The competition is NIST’s response to recent advances in the cryptanalysis of hash functions."
Might give us a chance to switch our approach to hashing to an entirely new set of mechnisms which can be shown to be safe against attacks known so far.
i don't doubt there are similarities between SHA1 and MD5, but the use of MD5 has been deprecated for the past 15 years due to pseudocollisions found in the mid-nineties. if those similarities were going to shake the trust people had in SHA1 i would have expected it to happen much sooner. the interest in a new standard hashing algorithm is more likely a consequence of relatively recent cryptographic results against SHA1 itself (whereby an attack can be mounted successfully that is, while still outside the realm of practicality right now, somewhat better than brute force).
see these two posts on schneier's blog for more details http://www.schneier.com/blog/archives/2005/02/cry… http://www.schneier.com/blog/archives/2005/08/new…
I expect, Paul, you're aware of the Password Strength Checker at http://www.hammerofgod.com/passwordcheck.aspx, which is instructive. The short take-away from all this is that a 6 character password is quite inadequate these days. Increasing the length to 8 or more dramatically improves password strength.
By a factor of about 9000 (94×94), assuming that each of Mr Roth's 94 characters is equally likely to be chosen.
In practice, not every printable ASCII character is equally likely to be selected. Most users choose more lower-case letters than upper case, more letters than numbers, and more letters than punctuation.
Most user-selected passwords probably have between five and six bits' worth of entropy per character. (Five bits means a character set of 32; six of 64).
With that in mind, you want to go for more than eight characters in your passwords, as you can see Graham doing here:
Hi, my name is Thomas Roth, not Ross 😉
Thanks for not being like all the other sites and just state that I've cracked SHA1 😉 Especially because a lot of people were stating that, I'm trying to get the facts straight here: http://stacksmashing.net/2010/11/20/cracking-pass…
My apologies. Don't know where "Ross" came from, since your name is clearly spelled out on your website. Sorry about that.
I've edited the article (and one of my comments) to get your name right.
No problem 😉 Only the tags are still on Ross 🙂
It's nice to see that there are people who know what they are writing about and don't fall for populism.
Is whirlpool stronger than SHA?