Comment by nkurz | Hacker News Reader

Comment by nkurz | Hacker News Reader

Parent Full thread

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.

Reply on news.ycombinator.com