[sverige]

OK, so "rainbow table" is what we all call them, but frankly I've always found that name to be baffling. Why are they called that? What is the origin of the name? What do they have to do with rainbows?

Yes, googling "magic list" will not produce the same results as "rainbow table," but it's a good substitute when teaching non-technical people the concept. It might even help them avoid googling unsuccessfully for the origin of the actual name. (If you know the origin, I'd love to know, and so would the people at Wikipedia.)

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

[ams6110]

A real rainbow represents all colors: the full spectrum. A rainbow table has all possible passwords within its spectrum (8 characters, alphanumeric, or however it's defined).

A non-technical term I might use is to call a rainbow table a "reverse phone book for passwords"

[sverige]

Fair enough, but many (probably most) of the people this training is aimed at have no idea what a reverse phone book is. I haven't seen a physical copy of one for a couple of decades.

Do you have a source for the origin of the name, or is it just what comes to your mind when you think of it?

[tCfD]

Iirc they acquired that nickname because early rainbow tables, which were in plain text or another simple uncompressed format, looked very much like ASCII rainbow patterns in a text editor due to the iterative nature of the key, salt, and hash stepping.

[ams6110]

I don't have a source, but the analogy seems obvious to me. If you're more curious, I guess you could do your own research?

[sverige]

I have, actually. I can't find a reliable source for the origin of the name, even in the original papers written to describe them.

[fjsolwmv]

There's no need to comment if you aren't sharing any information or ideas.

[fjsolwmv]

The people in the training haven't used "magic" recently either, seeing as magic doesn't exist.