Re: Rainbow table

["John Hummel" <john.c.hummel () gmail com>]

On Tue, Apr 22, 2008 at 10:43 AM,  <koolanwar () gmail com> wrote:
> How does Rainbow table Function.
>
>  Please explain how reduction function computes hash value and then in the next stage generates a plain text.
>
>
>  What Hash algorithms does Rainbow table use.

It doesn't - and anything you want.

Let me put it this way.  The point of a good hash algorithm is that
you can't deduce the original from the hash value.  So if you have:

hash(x) = hashed_value_x

hash(1) = abcajkl;ads
hash(2) = 23478faadf
....

So, looking at the values, you can't figure out what the hash value
was before it was hashed.

Now, a Rainbow Table approach says "Well, so I can't figure out what
the original was based on the hash value.  But - I can simply compute
all possible values, get the hash, and store the result.  Then, with
the hash result, I can get the original.  Not by applying an
algorithm, but by simply looking up the hash in a table and seeing
what the original was."

So you supply the hash type - MD5, DES, SHA1 - whatever.  Then all
your rainbow table program is:

int i = 0;
while(1)
{
  hashvalue = hash(i);
  insert into table Rainbow (i, hashvalue);
  i++;

}

You're not reducing anything - just letting the program run, and run,
and run, and generate all possible values.  Will this take some time?
Oh, sure - it can take a long time, and take up oodles of hard drive
space.  Of course, if you distribute the algorithm a la the SETI
project, then lots of people can work on various values and report
back to a central location to make a big Rainbow Table, then
distribute those gigabytes of data out there.

Not that anyone would *do* that (yeah, right).

This it the basic gist as I understand it.  There's more detail than
this, but basically it's just a giant while loop generating hashed
values from the original and storing the result.

-- 

John Hummel
(813) 944-7064