2
$\begingroup$

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 ?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Sep 29, 2018 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
    Commented Sep 30, 2018 at 4:10
  • $\begingroup$ ideone.com, also in security.stackexchange.com/questions/20052/… $\endgroup$
    – kelalaka
    Commented Sep 30, 2018 at 6:28
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.