Which values to store in rainbow table generation?

Question

According to the Wikipedia and Philippe Oechslin's Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf), both starting points and endpoints are keys. Here is an example from Wikipedia:

_{As you can see, key kiebgt is the endpoint of this chain.}

However, according to this site, it is hash values, rather than keys, that are stored in a rainbow table. That is to say, in the example above, hash value 920ECF10 should be shored as an endpoint.

So which one is the correct approach? The second one seems better to me, because we can skip one calculation(the first step) of reduction function R when looking up.

Answer 1

You can do either and the method works. Depending on which value is stored you check for existence in the table at different points in the computation. If the chains are long enough, the addition of a half step does not matter much for time, especially as the reduction function is typically very fast.

However, when you are trying to break a key with a size smaller than the hash size, it makes sense to store the former. Contrarily, if you are looking for passwords which do not have a lot of entropy and may even have different lengths, it can be more efficient to store the hash or a part of it instead.

(Note that the image you quoted is not for a rainbow table, but a simpler hash chain with the same reduction function at each step.)