# Why must we hash lot of times in rainbow tables?

I don't get the utility to chain and reduce in generating rainbow tables. Hash functions are made to not have collisions, or at least chain only 2 times so we don't return to the concept of the hash dictionary.

So why do we bother the machine to hash and reduce thousand of times to only store the latest value?

-
@StephenTouset This question is about hash chains in rainbow tables, a concept that isn't related to making a hash slow. –  CodesInChaos Jul 24 '13 at 7:19
@Abdelou With some tricks you can compare the end of the chain with the hash you want to break so you know if the target hash can be a part of that chain. If it is, you recompute that chain from the beginning checking after each step. –  CodesInChaos Jul 24 '13 at 7:22
@StephenTouset thank you, but i was asking about chaining in the rainbow tables. –  Abdelouahab Pp Jul 24 '13 at 10:19
@AbdelouahabPp I think you store the start and end of each chain. Possibly in some implicit form. –  CodesInChaos Jul 24 '13 at 10:39
Recommended reading: What are rainbow tables and how are they used? –  Gilles Jul 30 '13 at 17:58

The comments attempt to answer by looking at the details of how rainbow tables work; however if you examine the problem they're attempting to solve, you can see that they would require a large number of hash computations, no matter how they operate internally.

Now, rainbow tables are a generic way to find preimages to an arbitrary function; that is, given a function:

$$Y = H(X)$$

where $H$ is a deterministic function. Then, given a value $Y$, it tries to find an $X$ that satisfies the above equation. It does this by evaluating $H(X_i)$ when building the rainbow table, and encoding all those into the table. Then, given a specific $Y$, we search through the table to see if there was an $X_i$ that we evaluated that happened to hash to $Y$.

Here's the rub; the rainbow table method is generic; it does not attempt to examine the internals of $H$. So, the obvious question is: if we give it a hash value $Y$ where we did not evaluate the corresponding $H(X)$ during the build phase, how can it work? Well, obviously it can't. That means that, if we build a rainbow table that covers a dictionary of a trillion possible passphrases, that means that the we need to evaluate $H$ for those trillion possible passphrases. That is, building a rainbow table is going to be expensive, and unless we can rely on some cryptographical weaknesses of $H$ or some other special property, there isn't anything we can do about it.

So, since rainbow tables do not decrease the amount of work, does this mean that they are useless? No, it doesn't. For one, we need to build the table once. Yes, that is expensive, but looking up an entry in a rainbow table is cheap. Once we've evaluated those trillion hashes, we can later reuse that rainbow table many times to attack many hashes (and we don't need to know those values when building the rainbow table).

In addition, the other obvious question is "if that's what rainbow tables do, why don't we just build a large table of $(X_i, H(X_i))$ pairs, when we get a hash, we can then just look it up. Yes, that would work; however if we expressed that table in the obvious way, it'd be huge -- disk space is getting cheap, but not that cheap. Rainbow tables are essentially a clever way of making up such a table, but in a way that makes the table much smaller (that is, take up less disk space) than what you'd expect.

-
thank you for the answer, from what i understand; rainbow table is a kind of hash table with pairs (x, f(n)(x)) instead of (x, f(x)) we will end at the same size no? –  Abdelouahab Pp Jul 24 '13 at 17:11
No, a rainbow table is distinctly smaller than a list of preimages and their hashes. The idea is that the a rainbox table entry stands for the n preimages $X, f(X), f^2(X), ..., f^{n-1}(X)$. If Y happens to be any of those values, then the rainbow table lookup will succeed; hence the single pair $(X, f^n(X))$ really stands for $n$ different hashed images. –  poncho Jul 24 '13 at 18:18
sorry if am slow to get the idea, but why do we calculate n times f(x) and then when we find the result we must recalculate it? and both (rainbow table and preimage hashs) will contain hashs as second value? –  Abdelouahab Pp Jul 24 '13 at 18:44