Term: rainbow table

A rainbow table is a complete list of all possible passwords up to a given length, with their corresponding hash for a given hashing algorithm.

When implemented properly, passwords are never stored directly by software. Instead, a mathematical hash is stored instead. For example, instead of storing the password “iforgot”, software might store a value calculated from that password, such as “62072d95acb588c7ee9d6fa0c6c85155”. When someone logs in using the password, the hash is calculated again, and if it matches the saved hash, then the password must have been entered correctly.

This approach safeguards passwords because the password cannot be recovered from the hash. Even if the hash were exposed, as is often the case in large scale data breaches, it would be of little value to a hacker, because they would be unable to determine the corresponding password.

A rainbow table takes a brute force approach to this problem. For a given maximum password length, the hash values for all possible passwords are calculated and stored in a table. If a hash is known, it can simply be looked up in the table to determine the corresponding password, with no further calculation required.

Rainbow tables have severe limitations that make them less useful than we might fear.

1. Password length. A rainbow table for 8-character passwords might be on the order of 20 trillion entries in length – currently a somewhat manageable number. Tables for a 10-character password requires over 4 quadrillion entries, and for a 12-character password, approaches 9 quintillion. The time to create such large tables, as well as the space to store them, remains impractical.
2. Algorithm-specific. There are several standard hashing algorithms, and hackers would have to know which was used. A rainbow table would need to be created for each different algorithm. In addition, some algorithms are specifically designed to be slow. While fast enough for single-password use, when applied to all possible passwords it becomes impractical.
3. Easily invalidated. Hashing algorithms are now often applied not on the password alone, but on some modification of the password. For example, rather than just hashing “password”, an implementation might hash “accountname-password”. This breaks the general purpose nature of rainbow tables.

Current best practice in password storage is to use all three: long passwords, a “slow” hashing algorithm, and a modified hash.