How Lookup and Rainbow Tables Work
Introduction
------------------------------------------------
Sensitive data is stored as hashes in the database or file with hashing algorithms such as MD5 or SHA-2 hashing the value of the original password (or what is called the plaintext). Take the password anthony123 for example. Hashing it with MD5 and SHA-2 outputs:
Quote:
MD5: anthony123 => 72f99c7aa7eb9860ca506a67d0845688
SHA-2: anthony123 => 708b03176702e0295a5b6126f51472ef0aac8a1e
Two different hashes are produced, and there is no way to decrypt these hashes since the a hash is one-way encryption of a value. This means that there is no algorithm that can reverse a hash.
This is what is stored in a database/file, so putting this in the context of a login system: a user wants to login, and so enters his/her password in the script and submits the data. The original value is hashed using the same hashing function(s) that was done during registration to store the password. This newly hashed password is then checked against the hashed password in the database. If there is a match, the user has successfully logged in!
Lookup Tables
------------------------------------------------
These are much simpler in their use for determining the original value of a hash, because for every hash there is a plaintext value associated with it. Imagine a table with a hash in one column, and a plaintext value in the second column. The table below would represent a hash and its associated password.
Lookup tables can also be thought of simple lists. An array is an example of a simple lookup table (h being the variable)!
Rainbow Tables
------------------------------------------------
I want to go over Rainbow Tables briefly so you get an idea of what these are. A rainbow table stores the hash of commonly used words and combinations. For example, a word as part of a phrase has a hash value associated with it, which is stored for later use in a rainbow table. This is done by the table's reduction functions. In contrast to a lookup table, a rainbow table will store parts of rather than whole hashes, and use a series of chains to reach the plaintext value.
A reduction function simply returns a usable plaintext value from a hash. An example of a reduction function can be seen as follows, with H() representing a hash function (in this case, it will be MD5), R() the reduction function, p the plaintext, h the hashed value:
Quote:
h1 = H('anthony123')
= 72f99c7aa7eb9860ca506a67d0845688
r1 = R(h1)
= 72f99c7aa7eb9860
In the above example, you can see the reduction value from the hash is 72f99c7aa7eb9860. Take a close look at the MD5 hash produced, and you will (hopefully!) notice it's the same as the first half of the hash. A reduction function just compresses the hash into a usable plaintext value. A rainbow table will possibly have many different reduction functions.
The chains in a rainbow table are the series of hash and reduction functions made on a plaintext to result in a final hash. This is placed in a lookup table which is used to initialize the rainbow table. The plaintext is in the left column (or at the beginning of the chain), and the final hash is in the right column (end of chain).
I really enjoyed the example rainbow table provided by this blog, so I will use it for our purposes. In this rainbow table, the hash function takes a two-digit plaintext value and hashes it into four digits. The reduction function simply two digits of the hash (this is denoted by the red underline in the below picture of the rainbow table).
So, let's see if we can find the plaintext of the hash: 5520. Note: The image on the top is the lookup table for the rainbow table, and the bottom image is the actual rainbow table.
Here's a break down of what's going on:
- The hash (5520) is looked up in the rainbow table's lookup table, on the left side of the chain, we find the plaintext value of 68.
- The plaintext value (p1) is then hashed using the hash function. Does it match the original? No.
- Now reduce into another plaintext value (p2). The reduction function here takes the last two digits of the hash. This creates the first part of the chain.
- p2 is then hashed again, and this time, does the hash match the original hash? Since 3790 is not 5520, 31 is NOT the original plaintext, so move on and reduce the hash again (this reduction function takes the first two digits). This creates another chain.
- p3 is then hashed (h3) and now we check again to see if its hashed value matches our original hash. It does! This means the plaintext 32 is what 5520 is the hash of. Therefore, 5520 decrypts to 37.
Okay, so what happens if the original hash isn't in the lookup table? Let's say we start with the hash: 3955. This means a little extra work is required:
- Since the hash isn't in the original lookup table, we need to step backwards in the rainbow table. So start with the last reduction function in the table by reducing the hash to a plaintext of 39.
- Hash that plaintext value to obtain a hash that isn't found in the lookup table. Now check again, using the next reduction function on 3955 which outputs a plaintext of 55. Hey, it's in the rainbow table!
- Now we continue as usual, by hashing it to get 4532 (which isn't found in the lookup table) and reducing it to 45.
- Hash it again to receive an output of 3708 and check the lookup table again. We manage to find its plaintext match of 03.
- Begin the entire process from the beginning again. 03 hashes into 3955, so does it match the original? Yes! This means that the hash 3955 decrypts to the plaintext value of 03!
Whew, I'm glad that's over. I hope you understand the basics on lookup tables and rainbow tables.