[IncRnd]

A rainbow table is named "rainbow table" due to the lines created on a graph when drawing a continuous line through hash and reduction function chain. The graph can visually appear like a rainbow.

A hash function is a one way mapping, and so is a reduction (attempting to invert the hash function but usually failing).

Think of it this way:

Draw a line from plaintext P on the left to hash output H on the right. Then a line from H back to P2 (plaintext 2 on the left), which is the output of the reduction function over H. Draw a line from P2 to H2 (output of the hash function over P2). Do this for a little bit of the chain, and you will visually have a rainbow.

You can also get banding, when drawing them linearly instead of left to right, when taking closed chains into consideration.

If someone sees such a graph of a rainbow table, that explains the concept directly. Caching in a table is just the implementation.

[sverige]

This makes sense to me. Any idea when they were first called rainbow tables?

[IncRnd]

2003[1] by Oechslin[2] (extending Hellman's[3] idea):

We call our chains rainbow chains. They use a successive reduction function for each point in the chain. They start with reduction function 1 and end with reduction function t−1. Thus if two chains collide, they merge only if the collision appears at the same position in both chains. If the collision does not appear at the same position, both chains will continue with a different reduction function and will thus not merge. For chains of length t, if a collision occurs, the chance of it being a merge is thus only 1/t.

If you read these, you may get the idea that what people call Rainbow Tables really aren't Rainbow tables but Hash Lookup Tables. That's the price we unfortunately pay when people use the wrong words over time, like "Magic Tables" to describe data structures.

  [1] https://lasec.epfl.ch/~oechslin/publications/crypto03.pdf
  [2] https://lasec.epfl.ch/~oechslin/
  [3] https://ee.stanford.edu/~hellman/publications/36.pdf

[sverige]

Thank you for this.

[IncRnd]

You're welcome.