Rainbow Tables, despite their family friendly name, are quite a force in the cryptography world. Rainbow Tables are an advanced tool, along with hash tables, dictionary attacks and dumb brute force, for cracking password hashes.
Before we get started, I’d like to cover a common misconception about Rainbow Tables and that is that Rainbow Tables are different from hash tables. Hash tables are key/value pair list of pre-computed password hashes, normally of commonly used passwords. The key being the plain text password and the value being the corresponding hash. You compare a captured password hash against this a hash table and see if you find a match. Once a match is found, you have the plain text password.
Rainbow tables are a different beast. Rainbow Tables require two key functionalities to create:
- A hashing algorithm (the same hashing algorithm you are trying to crack)
- A reduction function
I went over hashing algorithms in a previous post. The reduction function takes a given hash and reduces it to a plain text value with specific properties (i.e. size, encoding, case).
Note: reduction functions do not reverse hashes, because hashes are not reversible, but instead map hashes to plain texts values (possibly from a provided, finite list).
To create a Rainbow Table, start with a password list. Choose a random password off the list to start with. Hash the password. Reduce the hash using the reduction function. Hash the returned plain text. Continue this for ??? times. You now have a hash chain for a starting plain text and ending hash. Store both the plain text and ending hash for the chain. Continue with other passwords in your list until satisfied (or until you run out of memory).
Hash Chain = hash -> reduction function -> plain text -> hash algorithm -> hash -> reduction function -> plain text -> …..continue a lot of times….. -> ending plain text
So how does this all work?
You have a hashed password that you “acquired”. Follow these steps:
- Look for the hash in the Rainbow Table.
- If the hash isn’t found, apply the reduction function and hash the resulting plain text. Repeat step 1.
- If the hash is found, that means you have a chain that will lead you to the final plain text.
- Now you know you can follow the hash chain backwards, knowing that you will eventually find the starting hash in the chain, which will also provide the corresponding plain text.
How do I defend against this?
Just a little salt, that’s it. No really, salt is a term for appending a complex string to the end of a password to conceal it from attacks. Most modern kernels store passwords with large salts, making Rainbow Table attacks unlikely to succeed.
TL;DR Ugh you should probably read