How to guarantee every plaintext is in a rainbow table?

Question

This guide says that for a rainbow table or pre-computed hash chain, you can only get a probability that a plaintext is in a table, not a guarantee. Is there a way to guarantee every possible plaintext (of a certain length) is in a table? My thought would be by storing entire chains and generating more chains if a plaintext isn't in any of them, but I think that defeats the purpose of a rainbow table.

Answer 1

You could, but generating such a table may get prohibitively expensive. It may also prevent other optimizations, like merged chain removal.

If you had a data structure keeping track of the whole dictionary, you could tick off each entry when you add it to a chain at any point, then start each chain from an entry not already used. However, in the cases where you'd use a rainbow table, rather than a simple hash table, you may not be able to store all that. The extra space usage is proportional to the chain length.

Alternatively, if you already have a table with e.g. 99% probability, you could iterate over all the inputs, see if they are in the table, then add chains starting with those that are not. This should require relatively little extra space, but increases the number of hash function invocations by a factor of about $l^2$, where $l$ is the chain length, since you need about that many hash iterations for each input to check if they are in the table.

Once you had such a table, it wouldn't necessarily be that much more costly to use, except by virtue of being larger.

Answer 2

Let's assume 7 bits per character (ascii). So for each character, there are $2^7$ different choices. So, if you are looking at 5 character passwords, that's $2^{7^5}=2^{35}$ different passwords. If the hash function output is 256 bits, we have to store (at the absolute minimum) $2^{35} * 256$ bits. That works out to be $1024$ gigabytes of data (1TB). So in that case, it seems feasible.

How does it change for just a few more characters. With 7 character passwords, you'd have to store 16,384TB. Maybe do able with cloud storage, but the cost would be pretty high. As you can see, things get moving pretty fast though. For 9 character passwords, you are looking at 268,435,456TB.

So, that is why things are probabilistic. If salts are used, that is only going to add to the storage requirements, so you'll get to the point where it is infeasible to store it all even faster.