2

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.

1
  • 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
    Commented Mar 20, 2018 at 7:37

1 Answer 1

2

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

2
  • 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
    Commented Oct 29, 2020 at 2:53
  • Sorry, I barely even remember what I was asking. Commented Oct 29, 2020 at 22:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .