1
$\begingroup$

As I read up on rainbow tables, I found that most sources suggest storing a plaintext - the result of Rk(hk) - in the last column, while others just store the hash hk, basically stopping one step earlier.

Is there a point in computing and storing the plaintext, instead of storing the hash? What do we gain from the extra reduction step?

$\endgroup$
1
$\begingroup$

The Rainbow table's average chain length determined during design time. Let cal it $t$.

If we want the table contains $N$ entries we need at least $N/t$ endpoints. To save storage, you want to make $t$ big as much as possible, but up to some point. $t$ determines the search time, $t^2$. You may want to reduce the space if you have a change, that can speed up the table lookup timing.

The storage table is a pair;

| Start Point | End Point |

In password cracking

  • if you store the hashes as the endpoints then we can immediately search on the endpoints for the given password hash.
  • if we store after the reduction, as in Wikipedia or Oechslin we need to first apply a reduction to the given hash value, then we can search.

If you are looking for 128-bit size passwords and building the table for SHA256, then for the endpoints, instead of storing the hash you can store the reduced value. In this case, you will gain approximately $\frac{128 N}{t} $ bits with a cost of applying a reduction for every new search. Therefore, if there is a space gain is available it is preferable.

Interestingly, most passwords are weak, instead of building the costly Rainbow table, a hash table that contains only the weak passwords is a better alternative.

$\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.