clarification on how rainbow tables use multiple reduction functions to avoid collisions

Question

I understand how Hellman's time-memory trade-off tables work by creating chains of hash and reduction function results and storing the last result after a number of operations. since the reduction function maps from hash space (crapton of characters) into password space (let's say up to 10 characters), it's obviouts we are going to have a ton of collisions.

Rainbow tables try to solve this by using multiple reduction functions. I dont understand How or why that helps.

This wikipedia article seems to try to put some light into it, but I just cant make sense of what it's trying to say.

Rainbow tables effectively solve the problem of collisions with ordinary hash chains by replacing the single reduction function R with a sequence of related reduction functions R₁ through R_k. In this way, for two chains to collide and merge they must hit the same value on the same iteration.

Answer 1

OK, I think I figured it out.

I made an illustration since It seems to be the best way of explaining what's going on.

Rainbow tables use a different reduction function on each link in the chain (this can be viewed as a different function on each column, where chains are rows)

In the following illustration

• H() is the Hashing function

• R() is a common reduction function used on every link (not a rainbow table)

• R1() to R3() are different reduction functions on every link (Rainbow table)

• A-Z are plaintexts obtained by a reduction function

• Hash1-5 are hashes obtained by the Hashing function

In the illustration you will find:

• What happens during a collision in a Hellmans table (the predecessor of the Rainbow table, uses a single reduction function R())
• What happens during a collision in a Rainbow table (identical to the Hellmans table, but uses different Reduction functions on each chain link)
• What happens during a Collision occurring on the same spot on a Rainbow table (It's statistically unlikely, but if this happens then the chains end up being identical, but since this does not happen often it's not that much of a concern)