2003: rainbow tables "As an example we have implemented an attack on MS-Windows password hashes. Using 1.4GB of data (two CD-ROMs) we can crack 99.9% of all alphanumerical passwords hashes (237) in 13.6 seconds" Philippe Oechslin, "Making a Faster Cryptanalytic Time-Memory Trade-Off", 2003 Martin Hellman's time-memory trade-off (1980) enhanced and applied to password hashes Storage needs are a lot lower than for QCrack's naive approach Nevertheless, infeasible with large random salts Each hash being cracked requires extra processing With a very large number of saltless hashes it may be quicker not to use rainbow tables, but instead to hash each candidate password and compare against all hashes being cracked, with an efficient comparison algorithm