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