# Time complexity of looking up in a rainbow table

It is mentioned in the famous paper Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf) by Philippe Oechslin that:

The total number of calculations we have to make is thus $\frac{t(t−1)}{2}$. This is half as much as with the classical method. Indeed, we need $t^2$ calculations to search the corresponding $t$ tables of size $m × t$.

However, my result doesn't agree with his. Here is my idea:

If we count a single application of a reduction function as 0.5 calculation, we'll have to do $0.5 + 1.5 + ... + t-0.5$ calculations in the worst case when looking up in a rainbow chart, that is, $\frac{t^2}{2}$ calculations, greater than the author's $\frac{t(t-1)}{2}$. In contrast, the original method seems to call for $t(t-\frac{1}{2})$ calculations, fewer than the author's $t^2$.

Also, the author's $\frac{t(t-1)}{2}$ and $t^2$ gives $0$ and $1$ respectively when $t=1$, which seems strange.

So who is wrong?

If we count a single application of a reduction function as 0.5 calculation [...]

That does not seem to be an assumption made in the paper? I would expect the reduction function to take much less time than a hash/cipher, so discounting them completely is a good enough approximation. That gives the value in the paper.

If you count it as 0.5, then it would take $0.5 + 2 + 3.5 +\dots + (t-1+0.5t)$ rather than what you have, since at each step you add 1.5 work for both another hash/cipher and another reduction.

In contrast, the original method seems to call for $t(t-\frac{1}{2})$ calculations, fewer than the author's $t^2$.

This part I am not sure about. I would think it should be $t(t-1)$, which matches the later text saying that a rainbow table approach takes half the time of the original.

A m * t rainbow tables requires t(t-2)/2 hash invocations and the same number of reduction functions. Classical approach with t tables of the same size would require twice as many hash invocations but also twice as many reductions. Recall that the different tables are made different by adding an extra cheap invertible function just like in rainbow tables. The difference is that classically we use a different reduction per table and in rainbow tables we use a different reduction per column, but we still add a reduction to every hash invocation.

Also as noted the reduction is usually very cheap, usual xor with a constant will work well, so the Kth reduction function is simply xoring with k. This is cheap, usually much cheaper then a hash invocation. I would expect the hash invocation to take a few hundred cycles and the reduction function to take 1 or maybe a handful with some inevitable overhead almost definitely at least an order of magnitude less.