Rainbow Tables – Part 5 (Chains and Rainbow Tables)

This is Part 5 of a five part series:

1. Introduction
2. Encryption and Hashes
3. Simple Hashes and Collisions
4. Reduction Functions
5. Rainbow Tables and Chains (you are here)

1. Addendum

So – here we go!  Let’s look at rainbow tables!

Here is a sample lookup table for a very simplistic encryption algorithm (discussed in Part 2) that takes a number from 0 to 99 and hashes it into a 4 digit number:

p1	h3
3	3708
10	5850
25	4202
68	5520
89	5109

It looks like a plain old lookup table with plaintext in the left column, and the hashed value in the right column.  But, that isn’t the case.  In fact, with the encryption algorithm we’re using for the example, the hashed value for 3 is 3955.  So what are we looking at?

As we discussed in Part 1, a basic lookup table would simply list every possible password (plaintext) and its corresponding encrypted value (hash).  If you know the encrypted value, you just look it up and see what the password is.  The problem with an ordinary lookup table is that it can quickly get huge.  A rainbow table provides a way to make it dramatically smaller.  A rainbow table does this through the use of chains and reduction functions.

The beauty of a rainbow table is that you don’t store the whole table. Instead, you store the left-most column and the right-most column, and you calculate the values in between as needed.  The table we saw above contains those two columns (leftmost and rightmost) from this rainbow table:

p1	h1=H(p1)	p2=R1(h1)	h2=H(p2)	p3=R2(h2)	h3=H(p3)
3	3955	55	4532	45	3708
10	0823	23	5603	56	5850
25	2059	59	3626	36	4202
68	3131	31	3790	37	5520
91	2554	54	3213	32	5109

Because we’ve used 10 entries to represent the 30 entries in table above, we’ve reduced the space by 66%!  Of course, there is a cost – we have more calculations to do. It is a tradeoff between size and speed.  We’ll look into that later; for now, lets just see how the rainbow table works by considering some examples.

Let’s say you have an encrypted value of 5520 that you want to decrypt.  Let’s look it up in our table.  Remember, we’ve only stored the lookup table, not the full rainbow table, so that is where we need to look:

p1	h3
3	3708
10	5850
25	4202
68	5520
89	5109

Yay!  We have a match!  If this were a simple lookup table, we would be done.  But it isn’t!  This lookup table represents the rainbow table above.  Because we’ve saved space, we have some calculations to do.  Time to pay the piper…  (This is where it gets interesting.)

Right now, all we know is that we have a hashed value of 5520, which is the right-most value in the chain that begins with 68:

p1	h1=H(p1)	p2=R1(h1)	h2=H(p2)	p3=R2(h2)	h3=H(p3)
68	3131	31	3790	37	5520

So, we take 68 and hash it to get 3131.  With hashes, we can always hash a plaintext value, to get its resulting hashed value, but we cannot go backwards (see Part 3). We can’t take a hashed value and get its plaintext value. (That’s what rainbow tables are for!)   Great – so we have 3131.  Now what do we do?

Here we meet the really clever part of rainbow tables.  Rainbow tables use something called reduction functions to “reduce” the hashed value (4 digits in our case) to a valid plaintext value (2 digits for us).  Reduction functions are really important, and are discussed in more detail in Part 4.  For now, let’s just learn enough about them to be able to walk through our examples.  A few important points:

• A reduction function is NOT an inverse of a hash function. Hash functions don’t have an inverse.
• But, a reduction function DOES consistently map a hashed value to some plaintext value.  But the plaintext value is meaningless. (Meaningless, but helpful for the rainbow table!)
• For any given valid hash value (eg, 3131), the reduction function MUST generate a valid plaintext value.
• Just like hashes have collisions, so do reduction functions. Because of this, rainbow tables use multiple reduction functions.  (More about this in Part 4.)

So, for our example, we apply our reduction function, R1, to the value we got from encrypting 68.  R1(3131) = 31.  Next, we hash 31:  H(31)=3790.  We pause, check if that is the value we started with (5520), notice that it is not, and repeat the steps.

That is, we apply our second reduction function, R2, to 3790.  R2(3790) = 37.  We hash 37, which results in H(37)=5520.  We pause, check if this is the value we started with (5520), and it is!  So we stop, knowing that 37 hashes into 5520.  So our plaintext is 37.

Boy, that was a lot of work, especially given that we had a match in our table!  Yes, that’s true.  Remember – we’re doing extra work to save space.

So let’s recap the algorithm we have seen so far:

1. Find the hashed value in the lookup table.
2. Take the plaintext value and hash it.
3. Does that hash match the hash we have?
   If so, stop. The value you just hashed is the value you're looking for.
4. If not, apply the reduction function to get a new plaintext value,
   and go back to step 2.

So what happens if the hashed value we have isn’t in the lookup table?  For example, what would we do if we started with the hashed value of  3626?  Step 1 in our algorithm obviously isn’t sufficient!

The solution is to apply the reduction function.  Since this is essentially walking backwards through the chains, we apply the last reduction function (R2).  What is R2(3626)?  Well, you don’t know (unless you’ve read Part 4), but that is okay.  Let R1 and R2 be “black boxes” for now and take my word for it – R2 (3626) is 36.  (Take a close look at what you’ve seen so far for R1 and R2 – you might be able to guess the algorithms.)  Hash that number, H(36)=4202, and try the algorithm again.  Looking back at the lookup table (not the full rainbow table), this time we find 4202.  We see that its corresponding value for p1 is 25.  Now we can go on to step 2: H(25)=2059.  Step3: is 2059 the number we’re looking for?  No, we looking for 3626, so on to step 4: R1(2059)=59.  Back to step 2: H(59)=3626.  Step 3: s 3626 the number we’re looking for?  Yes!  Therefore, 59 is its plaintext.

So, let’s rewrite the algorithm a little bit:

1. Find the hashed value in the lookup table.  If you find it, go to step 2.
  If not:
  1a. Starting with the last reduction function (e.g., R2), "reduce" the
      hashed value to get a new plaintext number. Every time you repeat
      step 1, you go to the next lowest reduction function (e.g., R2,
      then R1).
  1b. Hash the new plaintext number and repeat step 1 from he beginning
      with this new hash value.
2. Take the plaintext value and hash it.
3. Does that hash match the hash we have?
   If so, stop. The value you just hashed is the value you're looking for.
4. If not, apply the reduction function to get a new plaintext value, and
   go back to step 2.

Essentially, step 1 backs you up column-by-column in the rainbow table until you find a hash and can match a row.  Then, steps 2-4 move you forward through a specific row to obtain the value you need.  (And if you don’t find a value in these steps, then your rainbow table doesn’t have the information you’re looking for.)

Try it on your own, perhaps using 2554.

So, there you go – a gentle introduction to Rainbow Tables.  Hopefully this will help make other descriptions (such as those at wikipedia and kuliukas) a bit easier.  I encourage playing around with the spreadsheet and walking through the process with other sample values.