Jeff Atwood recently wrote about a technique to crack passwords called "Rainbow Hash Cracking". The technique, a variant on a dictionary attack, relies on a speedy search mechanism to do a table lookup against precomputed hash values. Jeff begins by surveying the password storage landscape, pointing out that passwords should never be stored in plain text:
Passwords are never stored in plaintext. At least they shouldn't be, unless you're building the world's most insecure system using the world's most naïve programmers. Instead, passwords are stored as the output of a hash function. Hashes are one-way operations. Even if an attacker gained access to the hashed version of your password, it's not possible to reconstitute the password from the hash value alone.The Rainbow Tables technique pre-computes the hash value, saving time at the expense of creating very large tables:
But it is possible to attack the hashed value of your password using rainbow tables: enormous, pre-computed hash values for every possible combination of characters. An attacking PC could certainly calculate all these hashes on the fly, but taking advantage of a massive table of pre-computed hash values enables the attack to proceed several orders of magnitude faster-- assuming the attacking machine has enough RAM to store the entire table (or at least most of it) in memory.Ophcrack, a Windows Password cracker, uses the Rainbow Tables technique. Jeff was able to use the smallest available table that ships with ophcrack (at 388 Mb) to find two out of five passwords within 3 minutes on a Windows XP machine. This table contains mixed case letters and numbers (about 80 billion hashes), and is able to crack 99.9% of Windows LanManager passwords. Jeff advises that support for LM hash, the early Microsoft encryption mechanism susceptible to a Rainbow Table attack, is not disabled by default:
I'm stunned that the legacy Lan Manager support "feature" is still enabled by default in Windows Server 2003. It's highly advisable that you disable Lan Manager hashes, particularly on Windows servers which happen to store domain credentials for every single userLM Hash is vulnerable to this type of attack because it does not use today's common method of introducing "salt" to the encryption process. If encrypted passwords do not use a salt it is relatively simple to do a reverse lookup to find the plain text password.
But when a remote hacker obtains a large list of hashed passwords from a server or database, we're in trouble. There's significant risk from a rainbow table attack. That's why you should never rely on hashes alone-- always add some salt to your hash so the resulting hash values are unique.A "salt" consists of random bits used as an input to the hash function in conjunction with the password, and mitigates the risk in two major ways:
- it increases the length of the hashed value and potentially adds characters that were not part of the character set used in generating the table
- you effectively need a separate Rainbow Table for each password as the salt is unique for each user
Jeff concluded that the solution to protect your password from rainbow table attacks is to salt your passwords.Why is bcrypt such a huge win? Think of the problem from two perspectives: the server, and the attacker.
First, the server: you get tens of thousands of logins per hour, or tens per second. Compared to the database hits and page refreshes and IO, the password check is negligable. You don’t care if password tests take twice as long, or even ten times as long, because password hashes aren’t in the 80/20 hot spot.
Now the attacker. This is easy. The attacker cares a lot if password tests take twice as long. If one password test takes twice as long, the total password cracking time takes twice as long.