LWN.net Logo

Rainbow tables

Rainbow tables

Posted Jun 8, 2012 15:37 UTC (Fri) by tialaramex (subscriber, #21167)
In reply to: Responsible disclosure in open source: The crypt() vulnerability by dps
Parent article: Responsible disclosure in open source: The crypt() vulnerability

Other commentators have observed that Rainbow tables have been "eclipsed" by the rapid progress of GPU-based parallel brute force attacks for most scenarios where they would once have been viable.

Rainbow tables are a time-space tradeoff, RAM and disk space continues to be only marginally cheaper than it was a few years ago, while GPU based "brute force" attacks can be thousands of times faster than CPU based attacks from a few years ago. So rather than buy 50TB of storage for rainbow tables targeting a single algorithm, it is more tempting for attackers to buy, rent, or indeed steal (through a botnet) a dozen mid-range gaming GPUs and have the flexibility to attack dozens of different algorithms for which GPU-based brute forcers are available.

Salt does still mean the attackers have to attack every individual password, rather than gathering a list of the most common hashes and attacking those for disproportionate gain, and it also means if some day rainbow tables or a newer time-space tradeoff would otherwise have been viable that's sidestepped. But it's far less important today than it was a few years ago.


(Log in to post comments)

Rainbow tables

Posted Jun 8, 2012 15:57 UTC (Fri) by intgr (subscriber, #39733) [Link]

> Rainbow tables have been "eclipsed" by the rapid progress of GPU-based parallel brute force attacks

The time-space tradeoff goes both ways. By using GPU instead of CPU for the time-intensive parts, you can increase the storage efficiency of rainbow tables (generate longer hash chains); the speedup would still be the same proportion. However, I don't know whether there are any actual implementations of this.

Rainbow tables

Posted Jun 8, 2012 20:18 UTC (Fri) by jackb (subscriber, #41909) [Link]

GPU-based parallel brute force attacks
You could probably blame Bitcoin in part for making these kinds of rigs popular.

Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds