This article discusses the best practices of secure password storage along with the commonly used rainbow table attack and how it can be defeated. Storing passwords in an unencrypted plain text field of a database (also known as cleartext) is plain stupid. Storing a password using only a standard encryption scheme (formally known as a cryptographic hash function) such as SHA-1 or MD5 is still a bad idea, since the cracker will be able to quite easily decrypt your password through the use of a rainbow table attack (a rainbow table is also known as lookup table or hash table).
Recent Hacks
This is how some of the more recently publicized hacks have succeeded:
- The HB Gary hack of 6-Feb-2011, by Anonymous started with an SQL injection attack, which then gave the attackers access to a database containing a table of usernames and passwords. HBGary's supposedly expert cyber-security developers had implemented unsalted, plain MD5 encryption making it completely vulnerable to a rainbow table attack.
- The Gawker hack on 12-Dec-2010 resulted in the emails and password hashes of 1.3 million users being compromised and once again rainbow tables were used to decrypt the simple MD5 encryption and thereby crack an eventual 200,000 accounts.
- The MtGox Bitcoin Exchange hack of 19-Jun-2011 resulted in some 60,000 user accounts being compromised, due to the passwords being stored as unsalted MD5 hashes.
- Online gaming website Battlefield Heroes was also hacked and taken offline on 23-Jun-2011, and yes this one too was using plain MD5 encryption with no salt.
- Unsalted, MD5-hashed passwords belonging to Mozilla add-on account holders were accidentally made public on 17-Dec-2010.
- On 11-Jul-2011, US government security contractor Booz Allen Hamilton was targeted by members of the Antisec hacktivist group, during which they gained access to 90,000 military email addresses and passwords, yet again protected only by an unsalted MD5 hash.
- So from media companies, through to games and even high-tech military suppliers, we've seen that all were using an outdated, broken form of password storage that was vulnerable to Rainbow Table attacks. It wasn't the fact they were using MD5 which made them vulnerable, it was the fact they didn't use something called a salt; more on that later.
Rainbow Tables
How rainbow tables work, a simple example:
- Take a list of the 500 most common passwords of all time. I'm talking "123456", "password", you get the idea. I mean something like 10% of all passwords currently in use are one of these.
- Pass all of them through the encryption scheme of choice (e.g. MD5 for example) to create a hash.
- Store the results in a table where each row comprises the cleartext password and the resulting hash.
- You now have 500 hundred hash values that you can reverse back to the cleartext password.
- This is known as rainbow table.
- This table should be able to crack 10% or so of any password database that uses the same unsalted encryption scheme that you chose in step 2 above.
- Take your table of usernames with password hashes
- For each hash
- Look for it in the rainbow table.
- If it’s there, you've cracked it.
To get around this vulnerability, developers should add a salt (also known as a nonce, number used once) to the password before encrypting it which, when properly done, makes lookup table attacks simply infeasible to do for all but supercomputer-level of hardware. Salting is really a way to add entropy or unpredictablility to the hashing process to specifically defeat the rainbow table type attack - just by making the salt a random number you introduce an exponential level of difficulty. For example, by using an 8 byte salt, you have increased the number of variants of each password encryption by 2^64 (18,446,744,073,709,551,616). A common misconception of a salt is to simply add the same unique string to all passwords before encryption, however it recommended, and far better, to add unique salts to every password, and typically to use a 8 to 16 byte wide random number, which is different for every user. Another error when implementing salt is to use the username as a salt, this too is not recommended, since crackers will most likely be able to guess that a common username will be admin, root, or just michael for example.
Best Practices
In the database then, for each user, the developer should be storing the following: the user id (such as email address), the user's unique salt, and the encrypted password. Remember the salt itself can be stored in the database unencrypted (as cleartext). And then finally to verify a password then, the developer just encrypts the cleartext password value prefixed (or suffixed) with the salt, and compares it to the hashed value stored in the database. The final piece of advice is never try and invent your own crypto algorithm, always rely on the proven cryptographic schemes of experts, one of the best of which is bcrypt, discussed below.
Undefeatable...?
This has explained the use of a salt to defeat rainbow table attack, but how about defeating a brute force attack? One of the best encryption schemes around, and one that can't be brute forced is bcrypt: as well as using a salt to protect against rainbow table attacks, bcrypt is an adaptive hash: over time it can be made slower and slower (in step with Moore's law) so that it remains resistant to specific brute-force search attacks against the hash and the salt.
Further Reading:
