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

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 R1 through Rk. In this way, for two chains to collide and merge they must hit the same value on the same iteration.

• Please don't post text as images. Its hard (or for some, impossible) to read and search. Just copy paste the quote instead. Commented Mar 20, 2018 at 7:37

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)

• Very helpful graphic! What are good/common reduction functions used in practice. Most examples just mention taking some characters of the hashed output, but I doubt that's actually useful in practice, is it? Commented Oct 29, 2020 at 2:53
• Sorry, I barely even remember what I was asking. Commented Oct 29, 2020 at 22:33