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.

  • $\begingroup$ 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. $\endgroup$ – Manohar Sep 29 '18 at 19:52
  • $\begingroup$ 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. $\endgroup$ – Meir Maor Sep 30 '18 at 4:10
  • $\begingroup$ ideone.com, also in security.stackexchange.com/questions/20052/… $\endgroup$ – kelalaka Sep 30 '18 at 6:28

Your Answer

