While you might think of Rainbow Tables as eclectic colorful furniture, those aren't the ones we are going to discuss. The Rainbow Tables that we are talking about are used to crack passwords and are yet another tool in the hacker's ever growing arsenal.
What the heck are Rainbow Tables? How could something with such a cute and cuddly name be so harmful?
Here's the basic concept behind Rainbow Tables:
I'm a bad guy who has just plugged a thumb drive into a server or workstation, rebooted it, and ran a program that copies the security database file containing user names and passwords to my thumb drive.
The passwords in the file are encrypted so I can't read them. I will have to crack the passwords in the file (or at least the administrator password) so that I can use them to access the system.
What are my options for cracking passwords? I can try and use a brute-force password cracking program such as John the Ripper ,which pounds away at the password file, trying to iteratively guess every possible combination of a password. My second option is to load a password cracking dictionary containing hundreds of thousands of commonly used passwords and see if it gets any hits. These methods can take weeks, months, or even years if the passwords are strong enough.
When a password is "tried" against a system it is "hashed" using encryption so that the actual password is never sent in clear text across the communications line. This prevents eavesdroppers from intercepting the password. The hash of a password usually looks like a bunch of garbage and is typically a different length than the original password. Your password might be "shitzu" but the hash of your password would look something like "7378347eedbfdd761619451949225ec1".
To verify a user, a system takes the hash value created by the password hashing function on the client computer and compares it to the hash value stored in a table on the server. If the hashes match, then the user is authenticated and granted access.
Hashing a password is a 1-way function, meaning that you can't decrypt the hash to see what the clear text of the password is. There is no key to decrypt the hash once it is created. There is no "decoder ring" if you will.
Password cracking programs work in a similar way to the login process. The cracking program starts by taking plaintext passwords, running them through a hash algorithm, such as MD5, and then compares the hash output with the hashes in the stolen password file. If it finds a match then the program has cracked the password. As I said before, this process can take a very long time.
Enter the Rainbow Tables: Rainbow Tables are basically huge sets of precomputed tables filled with hash values that are pre-matched to possible plaintext passwords. The Rainbow Tables essentially allow hackers to reverse the hashing function to determine what the plaintext password might be. It's possible for two different passwords to result in the same hash so it's not important to find out what the original password was, just as long as it has the same hash. The plaintext password may not even be the same password that was created by the user, but as long as the hash is matched, then it doesn't matter what the original password was.
The use of Rainbow Tables allow for passwords to be cracked in a very short amount of time compared with brute-force methods, however, the trade-off is that it takes a lot of storage (sometimes Terabytes) to hold the Rainbow Tables themselves, Storage these days is plentiful and cheap so this trade-off isn't as big a deal as it was a decade ago when terabyte drives weren't something that you could pick up at the local Best Buy.
Hackers can purchase precomputed Rainbow Tables for cracking passwords of vulnerable operating systems such as Windows XP, Vista, Windows 7, and applications using MD5 and SHA1 as their password hashing mechanism (many web application developers still use these hashing algorithms).
How can you protect yourself against Rainbow Tables-based password attacks?
I wish I had better advice on this one for everybody. I would like to say that a stronger password would help, but this is not really true because it's not the weakness of the password that's the problem, it's the weakness associated with the hashing function being used to encrypt a password.
The best advice I can give users is to stay away from web applications that restrict your password length to a short number of characters. This is a clear sign of vulnerable old school password authentication routines. Extended password length and complexity may help a bit, but is not a guaranteed form of protection. The longer your password is, the larger the Rainbow Tables would have to be to crack it, but a hacker with a lot of resources can still accomplish this.
My advice on how to defend against Rainbow Tables is really meant for application developers and system administrators. They are on the front lines when it comes to protecting users against this type of attack.
Here are some developer tips on defending against Rainbow Table attacks:
1. Don't use MD5 or SHA1 in your password hashing function.
MD5 and SHA1 are outdated password hashing algorithms and most rainbow tables used to crack passwords are built to target applications and systems using these hashing methods. Consider using more modern hashing methods like SHA2.
2. Use a cryptographic "Salt" in your password hashing routine
Adding a cryptographic Salt to your password hashing function will help defend against the use of Rainbow Tables used to crack passwords in your application. To see some coding examples of how to use a cryptographic salt to help "Rainbow-Proof" your application please check out the WebMasters By Design site which has a great article on the topic.
If you want to see how hackers perform a password attack using Rainbow Tables, you can read this excellent article from About.com's own Tim Fisher at the About.com PC Support site.