Rainbow tables, where have I got it wrong?

Question

There seems to be some error in my understanding of the concept of rainbow tables, despite going through quite a bit of articles on it.

Let me show what I don't seem to agree with.

My plain text is 5-digit numeric input. Hash function - MD5 Reducing func - Get the first 5 decimal digits from the cryptotext

Constructing a single chain

12345   827ccb0eea8a706c4c34a16891f84e7b
82708   71b8e22700e63c2a0c1bad6506549d3b
71822   03010f7d7933a011782c10faf91c4fca
03010   cae05e8533d17be83bce0f451d5c7dd7
05853   a6864772e19671240f491bc2c89a36e0

This gets me one entry in my Rainbow table

12345 -- a6864772e19671240f491bc2c89a36e0

Lets test this with a sample:

• Test hash (nota bene: this is not a valid hash, just for consideration)

  th = tb05be8531317be83bce0f451d5c7dd7
  

• With the reducing function:

  R(th) = 05853
  

• Then on hashing gives us:

  a6864772e19671240f491bc2c89a36e0
  

Now, though the end result matches, its doesn't resolve my hash into a valid plain text.

Would this not be the case for every hash generated through this process? The only true hash match would be the last plain text value which is hashed, and doesn't really relate to the initial plain text.

Answer 1

Note that for Rainbow tables you should use different reduction functions for each column.

Once you have a match on chain endpoint, you should get the start point of this chain and regenerate chain up to hash value you're looking for. This will give you the plaintext you're looking for.

To search for a matching chain, you guess the column $i$ where you think password is located and compute the chain from column $i$ to the end. In practice, $i$ is chosen to minimise attack runtime, i.e. $i=(N-1, N-2, ..., 0)$ ("walking" the chain backwards).

To check a particular column you re-compute remaining part of the chain by applying reduction and hash functions the same way you do during table generation (Note: remember that in Rainbow tables each column uses different reduction function, so to recompute chain you have to guess position in the chain). Once you have obtained a candidate endpoint, you check if it matches any of the endpoints from a table. If it doesn't, you take next $i$ and repeat the above process. If you've tried all columns with no luck, then password you're looking for is not covered by the table and the search have failed.

Once matching endpoint is found, you get corresponding starting point and recompute the chain up to column $i$. What you will get is the password you're looking for. Or maybe not because there might be collisions, in which case you go to a previous step and continue with next $i$.

In your particular simplified example (with identical reduction functions):

1. You start with $h=$`03010f7d7933a011782c10faf91c4fca`, compute $H(R(h))=H(05853)$=a6864772e19671240f491bc2c89a36e0
2. You locate a6864772e19671240f491bc2c89a36e0 in the table and get corresponding starting point – 12345.
3. You recompute the chain, starting with 12345, to get plaintext for the column where you've got a match, which will be 03010.