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.

  • 2
    Please don't post text as images. Its hard (or for some, impossible) to read and search. Just copy paste the quote instead. – Anders Mar 20 '18 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)

enter image description here

  • 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? – Kyu96 Oct 29 '20 at 2:53
  • Sorry, I barely even remember what I was asking. – Joaquin Brandan Oct 29 '20 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.