"What stops you from resolving the hash via the rainbow tables and then removing the salt from the resulting cleartext ?"

You can't resolve a salted password in the tables (at least, it's extremely unlikely). The Rainbow Tables aren't a magical device for inverting any hash, they are simply a clever and very efficient way of storing the results of doing many forward lookups (actually that's an oversimplification; it's actually an optimised time/memory tradeoff attack). So you try every possible password up to 8 printable character (total, 7 x 10^^15 candidates) and store various indices ("chain endpoints") in the table. It takes a long time to create the table (2 years in this case), but once you have it any candidate can be looked up in just a few minutes. It also takes a lot of disk space to store it, but nothing like as much disk space as if you used a more "brute force" approach -- about 4 x 10^^12 bits to store the results of 7 x 10^^15 candidates!! The way this is possible is that not all results are stored, only intermediate points from which one can skip ahead with a few hundred thousand calculations in the space of a minute or so.

However, as soon as you have a few dozen bits of salt the number of candidate hashes balloons by an enormous factor, and the table size, generation time, and lookup time all become unmanageable, even with the rainbow table optimisations. In fact, the rainbow table size increases roughly as the 2/3 power of the space of salts, so a 48 bit salt (quite common nowdays) would require a table 2^^32 (about 4 billion) times bigger! Even the old Unix 12 bit salt, introduced back in the 1970s, would make the attack about 256 times harder.

[ reply ]

Link to this comment: http://www.securityfocus.com/comments/articles/11355/32731#32731