0
$\begingroup$

I'm learning the rainbow table and hellman table and I'm curious about the difference between them, so I left a question like this.

Wikipedia describes the following sentence:

The term, "Rainbow Tables," was first used in Oechslin's initial paper. The term refers to the way different reduction functions are used to increase the success rate of the attack. The original method by Hellman uses many small tables with a different reduction function each. Rainbow tables are much bigger and use a different reduction function in each column. When colors are used to represent the reduction functions, a rainbow appears in the rainbow table. Figure 2 of Oechslin's paper contains a black-and-white graphic that illustrates how these sections are related. For his presentation at the Crypto 2003 conference, Oechslin added color to the graphic in order to make the rainbow association more clear. The enhanced graphic that was presented at the conference is shown to the right.

According to this, hellman table uses the same reduction function for each table while storing several tables of size $m\times t$.

On the other hand, the rainbow table creates one much larger table and uses a different reduction function for each column.

At this point, a few questions arise.

  1. In the end, whichever of the two methods is used, isn't it advantageous to store a large number of elements (Of course, there will be a lot of pre-calculation.)?

  2. Does the difference in how the reduction function is used lead to different results?

  3. From my point of view, in general, people seem to use rainbow tables more than Hellman tables, but why?

Thank you.

$\endgroup$

1 Answer 1

0
$\begingroup$

There are a number of dimensions to consider your question(s) and a brief answer is not really possible.

The paper Analysis of the Rainbow Tradeoff Algorithm Used in Practice below provides a very detailed overview of the use of rainbow tables and how to choose parameters.

https://eprint.iacr.org/2013/591.pdf

Abstract:

Cryptanalytic time memory tradeoff is a tool for inverting one-way functions, and the rainbow table method, the best-known tradeoff algorithm, is widely used to recover passwords. Even though extensive research has been performed on the rainbow tradeoff, the algorithm actually used in practice differs from the well-studied original algorithm. This work provides a full analysis of the rainbow tradeoff algorithm that is used in practice. Unlike existing works on the rainbow tradeoff, the analysis is done in the external memory model, so that the practically important issue of table loading time is taken into account. As a result, we are able to provide tradeoff parameters that optimize the wall-clock time. Most importantly

However, in practice, the very large pre-computation tables of the rainbow tradeoff must initially reside on slow disks and these need to be loaded into smaller main memory for processing. This situation is quite different from the RAM model of computation and the highly non-localized memory access behavior of the original rainbow tradeoff makes its straightforward implementation on a modern computer quite impractical for use, except in the less interesting case of small search spaces.

A number of statistical analyses are also carried out in the paper.

Happy reading!

$\endgroup$
1
  • $\begingroup$ Thank you for your recommendation! $\endgroup$
    – pioneer
    Apr 6 at 4:49

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.