Cracking SHA-1 and the Game of Tom & Jerry

Let me start bluntly by saying that if you use md4/md5 hashes, then you're faint of heart and this post is definitely not for you.

SHA-1 is a big improvement over MD5 in terms of collisions, and hashes generated using it are much harder to crack than MD5 hashes.

Unfortunately that is about to change dramatically in a way that makes it very easy for attackers to crack SHA-1 hashes, while making it more difficult for victims to 'get on with the times' and use safer alternatives, what which fragile web app architecture and poor, poor extensibility in widely-used web apps.

I'm talking about how easy it has become now to crack a SHA-1 hash using the cloud. Amazon now provides EC2 Clusters with GPU powers. Yes, rental of machines with superior GPU-computation abilities, and guess which pieces of hardware are extremely good at cracking hashes? Yup, GPUs.

If I'm not mistaken, it goes as cheap as 2 dollars for an hour of GPU-hotness, which is more than enough to crack a certain hash that's driving you crazy.

So what is the solution you might ask? Here is where the proverbial game of cat and mouse comes into play. SHA-1 hashes were considered secure because it is difficult for an attacker to brute-force the inverse of the hash; that is reverse the operation of hashing to find the original text (in this case password plaintext), but now with the 'increased' use of the cloud and perhaps many botnet herders wishing to utilize the GPUs of their zombies and bots, the effort needed by the SHA-1 cracker is well within his/her grasp.

So you need to up the ante. You need to make it even more harder to crack your hashes while still making it reasonable and affordable to create the hash yourself. You don't want the user waiting for three minutes while his password is being hashes, unless you're The BOFH, which is fine, but let's not stray far from the point:
Use algorithms that put more work in creating the hash and therefore orders of magnitude more work for the cracker and his cloud. Things like PBKDF2 or scrypt (To be honest I haven't tried scrypt yet so don't blame me for anything wrong with it). PBKDF2 is already supported in many web application frameworks like .NET, so for many applications the migration should not be THAT much difficult.

To make a long story short, PBKDF2 works by taking a key(In this case a password), a salt (No, not NaCl, get away from my blog, chemists!) and an iteration count to derive a key (In our case the final hash value). This differs in that you now have to go through the entire iteration count in order to derive one hash from one plaintext, which is obviously much harder to compute.


Using PBKDF2 or scrypt is not a panacea, however, because you still need to do it correctly.  For example, you shouldn't even think about using an iteration count of less than 2000 (some say the minimum is 1000), but many systems use iteration counts of up to 10,000, which is delicious. Have you heard about the BlackBerry backup data encryption cracked a few months ago? They used one iteration count, effectively rendering all advantages of PBKDF2 (stands for Password Based Key Derivation Function 2, btw) utterly useless.

If your business case permits, you don't even need to disclose the salt and iteration count to add a bit more obscurity to your security (add, not replace, mind you; obscurity is not a replacement for actual security).

Oh, and that's just one great usage of the cloud to crack passwords or maybe perform pen-tests (haha), see this example of cracking WPA passwords using the cloud: WPA Cracker.

That's it for now, for more info you can read about Amazon's GPU clusters or StackSmashing's coverage of this interesting topic.