Rainbow Tables

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.

Exploitation

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.