# Rainbow tables, where have I got it wrong?

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
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.

-

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.
-
When we use precomputed hash chain for Raninbow tables, don't we store just the first plaintext and the last hash value-How do I guess i and start from the middle of the chain? || Does this mean that my plaintext value need not necessarily be found in the hash chain even though the last hash matches? || Noted: using different reduction functions in each step/column of the hash chain – nonexistent myth Aug 19 '14 at 16:46
Correct, you only store first and last element of the chain. $i$ above is the column number, you guess it by trying all possible values of $i=(N-1, N-2, ..., 1, 0)$. Essentially, you make a series of assumptions: let's assume that my password is in the last column, let's check it (by recomputing remaining of the chain and checking endpoint). No? Maybe it's in the previous one? Again no? Let's take the previous one. And so on, until you reach the beginning of the chain, in which case search has failed. Does that make more sense? – Andrey Aug 19 '14 at 17:22