The Rainbow Table Is Dead | Hacker News Reader

The Rainbow Table Is Dead

blog.ircmaxell.com

9 pointstoni5 comments

Those size constraints are based on the concept of storing every password and its hash in the table. However, that gives a reverse lookup table, not a rainbow table. The key to a rainbow table is that you look at an initial password, hash it, use the hash to generate a new password, then repeat a few thousand times. Then you store only the initial password and the ending hash. To use the table, you do the same thing, but check each of the intermediate hashes against the rainbow table; if you find it, you start at the initial value and follow the chain until you get the password.

So, of the OP's points: 1) Storage space: cut by a factor of several thousand. Assuming that you're OK with chains of 50K passwords, that's only about 1T total for something that will (probably) cover most of the password space. 2) Hash algorithms: If you're using a single SHA256 to hash passwords, you're doing it wrong. SHA256 was designed to be fast. Real password hash algorithms are much, much slower. 3) Salts: As AppSec says, most sites screw up salts.

So, while rainbow tables aren't that useful against a properly secure system, they still have their uses.

You are much kinder to the original post than I think is warranted. I'd go so far as to say "the author fundamentally misunderstands the concept of rainbow tables". I don't want to pick on him unduly: it can be much better to write something clear and wrong and have it corrected than to persist in fuzzy thinking. But let's not waffle: this piece is clear and wrong.

As you point out, rainbow tables are fundamentally about chains of hashes, and about saving only the entry points into those chains. One would never save every entry, and if one did it would not be a rainbow table. It's an arbitrary time-storage tradeoff, and faster GPU's simply change the "sweet spot". The limit is not the storage space, but remains the amount of time you are willing to spend pre-computing, and GPU's give you much greater leverage here.

I tried to look through the article and find some positive pieces to point out, but I couldn't do it. He the conflates floating point performance with hash speed, asserts that one needs to scan the full rainbow table from disk to use it, and concludes that rainbow tables are limited to 4 character passwords. The general conclusion is correct (worry about brute force attacks) but there are so many other large errors that I cringe in fear.

Author (should you read this): I don't mean be impolite, and I don't understand these issues well enough myself to try to teach them, but I truly am scared by your apparent fluency with these concepts combined with the level of inaccuracy. Please do what you can to keep educating yourself about these concepts before applying them professionally.

Thank you for the comments! My point wasn't to show how wasteful or bad rainbow tables are. My point was that brute forcing is actually significantly easier than people realize (to the point of being almost as efficient as rainbow tables depending on the circumstances). And since any standard measure that prevents brute forcing will also help prevent rainbow tables, the point that I was trying to convey is that you should not try to protect against rainbow tables exclusively, but you should try to protect against brute forcing and get the rainbow table protection that comes naturally from that step...

With respect to the 4 character password limitation, that was mainly to show how powerful brute forcing can be, not how bad rainbow tables are.

Sure, you can make a dictionary rainbow table based off a normal english dictionary with perturbations (caps/symbol replacements) and have it be more efficient than a brute force for any size. But I was looking at it form a guaranteed match aspect, not a "probable match". So for a guaranteed match against an 8 character password, the rainbow table would have to be gigantic, but brute forcing would likely not take as much time.

Perhaps I should have presented it a bit differently. But I purposely wanted to take the worst case approach to demonstrate just how efficient brute forcing can be. If that painted a slightly tainted picture, then fine. But I think it got the point across (although how it got it across has been questioned)...

I appreciate your response. I still disagree with your basic premise. The difficulty with making large Rainbow Tables is not the storage space, but the time necessary to create the initial table. Faster GPU's make Rainbow Tables more effective for large password spaces, not less. The size of the table can be arbitrarily reduced by using longer chains. The real limiting factor is the time to generate the initial table, which is comparable to making a single brute force search.

The theory is beyond my ability to explain, but as a practical example, this page might be useful: http://ophcrack.sourceforge.net/tables.php

It's not an exact match up, but look at "Vista 7" table. For complete coverage of a 95 character set (not sure how you calculated 77 printable ASCII) up to 7 characters, they require 36 GB instead of the 417 TB you propose. Since theirs ships and works, I'm inclined to believe that your theory is in error.

Also, I could be mistaken, but I don't think there is such a thing as a "Dictionary Rainbow Table". You can choose any character set you want, but because of the way the algorithm works I don't think you can restrict to a prechosen word set.

I might have missed it, but there should have been a few caveats listed:

1) The size of the rainbow table can also be adjusted for password rules. (your password must have 1 upper, 1 lower, 1 number, 1 non-alpha numeric, no repeating characters, no in the dictionary, etc...)

2) This is a specifically brute force attack against a specific user. If you are looking at 1.7 days against an entire user store, the numbers don't look as promising. (note: this isn't a comment in favor of rainbow tables, just as point of interest).

3) A lot of sites still don't have salts/hashes done correctly.

Reply on news.ycombinator.com