Rainbow Tables
Last updated
Applied Cryptography
Last updated
We can invert a digest function with a table.
For all possible input, we compute and store the digest.
But the table size is given by the digest length.
Not usually applicable.
Solution: rainbow tables.
Trade space with time.
Store only part of the outputs.
For direct matching.
Find for more matches using computation.
They are based on a reverse function R
Which is not the inverse of H
The goal of R is to produce a new input given a hashing result.
R functions are likely to produce collisions.
But we can use many different R functions.
Collisions scan still occur.
But will not create a problem unless occurring at the exact same column.
And that case can be identified (and discarded) by identical outputs.
A table with m k-length rows can invert k×m hashes.
At most.
Only I0 and Ik is stored per row.
A set of m random inputs is generated.
I0 = {I0,1, ... I0,m}
A set of m k-length chain outputs is computed.
Ik = {Ik,1, ... Ik,m}
Given a target o
Look for R(o) in Ik.
If found in row r, compute chain from I0,r.
until finding i such that H(i) = o
If not found, compute o_r from o using H and R for each row r.
and see if o_r = Ik,r.
H and R are applied 1 to k times, using different R functions.
