Join Log in
Score:0
pioneer avatar Crypto

About the differences between the rainbow table and hellman table

in flag
pioneer

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.

28
0 + 0
Score:0
kodlu avatar Crypto
sa flag
kodlu

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!

0 + 0
pioneer avatar
in flag
pioneer
Thank you for your recommendation!
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.