# How to prove that a rainbow table is complete?

Passwords that are hashed but not salted can be cracked using the rainbow table. I went through this and this which explains the logic behind rainbow table very well.

But I am missing something about the rainbow tables; how can one be sure that the hashes for all valid passwords are covered by the table ?

Lets say the passwords are 8 characters are long from [a-z][A-Z][0-9]. If I am constructing a rainbow table with 10000 hash & reverse iteration in a chain how can I determine at what point the table is complete ? ie: the password and the final hash stored includes the hashes for all the 628 valid passwords somewhere in the chain ?

Is there a mathematical way to verify the completeness of a rainbow table ?

Rainbow tables are not complete. But some have good coverage. We estimate how many distinct hashes are covered by a rainbow tables using statistical tools.

We can build perfect rainbow tables where we throw out colliding chains. This reduces redundancy in the final table. But even in a "perfect" rainbow a certain hash can appear twice(but not in the same column) so we still need to estimate the coverage.

As we approach full coverage it becomes more and more expensive. Because with a table with high coverage nearly anything we add would already be covered.

• Do you have any pointers to those statistical tools ? curious how they work, because I think the coverage of a table would depend heavily on the Reversal functions used per column. – Manohar Sep 29 '18 at 19:52
• The originalb paper with all formulas is here: infoscience.epfl.ch/record/99512/files/Oech03.pdf but we model things randomly each new hash has equall chance of being any in the space so if we already covered C distinct hashes out of N that is the chance of us colliding and not increase our table. With perfect tables we do this column wise and don't deal with merging chains. – Meir Maor Sep 30 '18 at 4:10
• – kelalaka Sep 30 '18 at 6:28

Rainbow tables are probabilistic. The hash and reduction function act like a random number generator to select the passwords that appear in the chains. It is like throwing balls randomly into boxes. You can throw as many balls as you want, there is still a chance that one box stays emtpy.

The only way to be sure is to note which passwords are generated when the tables are created. You then know exactly which passwords are missing. Obviously, this is only possible for smaller sets of passwords as the amount of storage and of work would make the creation of the tables very expensive (in time and memory).

ElcomSoft has done exactly this and called it Rainbow and Thunder tables (see https://blog.elcomsoft.com/2009/05/thunder-tables/). The thunder is a table that contains the hashes and passwords that are missing in the rainbow table. They have done that for 40-bit keys used to break the encryption of older Ms-Office documents.