1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.