Rainbow table
A rainbow table is a for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a password (or credit card numbers, etc) up to a certain length consisting of a limited set of characters. It is a practical example of a , using less computer processing time and more storage than a which calculates a hash on every attempt, but more processing time and less storage than a simple with one entry per hash. Use of a key derivation function that employs a makes this attack infeasible.
Rainbow tables were invented by Philippe Oechslin
Contents
Background
Any computer system that requires password authentication must contain a database of passwords, either hashed or in , and various methods of password storage exist. Because the tables are vulnerable to theft, storing the plaintext password is dangerous. Most databases therefore store a of a user’s password in the database. In such a system, no one—including the authentication system—can determine what a user’s password is simply by looking at the value stored in the database. Instead, when a user enters his or her password for authentication, it is hashed and that output is compared to the stored entry for that user (which was hashed before being stored). If the two hashes match, access is granted.
After gathering a password hash, using said hash as a password would fail since the authentication system would hash it a second time. In order to learn a user’s password, a password that produces the same hashed value must be found, usually through a brute-force or dictionary attack.
Rainbow tables are one tool that has been developed in an effort to derive a password by looking only at a hashed value.
Rainbow tables are not always needed, for there are simpler methods of hash reversal available. and are the simplest methods available, however these are not adequate for systems that use large passwords, because of the difficulty of storing all the options available and searching through such a large database to perform a reverse-lookup of a hash.
To address this issue of scale, reverse lookup tables were generated that stored only a smaller selection of hashes that when reversed could generate long chains of passwords. Although the reverse lookup of a hash in a chained table takes more computational time, the lookup table itself can be much smaller, so hashes of longer passwords can be stored. Rainbow tables are a refinement of this chaining technique and provide a solution to a problem called chain collisions.
Precomputed hash chains
- Note: The hash chains described in this article are a different kind of chain from those described in the hash chains article.
Source:
Rainbow tables are specific to the hash function they were created for e.g., MD5 tables can crack only MD5 hashes. The theory of this technique was invented by Philippe Oechslin as a fast form of , These larger salt values make precomputation attacks against these systems infeasible for almost any length of password. Even if the attacker could generate a million tables per second, he would still need billions of years to generate tables for all possible salts.
Another technique that helps prevent precomputation attacks is . When stretching is used, the salt, password, and a number of intermediate hash values are run through the underlying hash function multiple times to increase the computation time required to hash each password. For instance, MD5-Crypt uses a 1000 iteration loop that repeatedly feeds the salt, password, and current intermediate hash value back into the underlying MD5 hash function. It also greatly increases the time needed to build a precomputed table, but in the absence of salt, this needs only be done once.
An alternative approach, called key strengthening, extends the key with a random salt, but then (unlike in key stretching) securely deletes the salt. This forces both the attacker and legitimate users to perform a brute-force search for the salt value. Although the paper that introduced key stretching referred to this earlier technique and intentionally chose a different name, the term “key strengthening” is now often (arguably incorrectly) used to refer to key stretching.
Rainbow tables and other precomputation attacks do not work against passwords that contain symbols outside the range presupposed, or that are longer than those precomputed by the attacker. However tables can be generated that take into account common ways in which users attempt to choose more secure passwords, such as adding a number or special character. Because of the sizable investment in computing processing, rainbow tables beyond fourteen places in length are not yet common. So, choosing a password that is longer than fourteen characters may force an attacker to resort to brute-force methods.
Certain intensive efforts focused on , an older hash algorithm used by Microsoft, are publicly available. LM hash is particularly vulnerable because passwords longer than 7 characters are broken into two sections, each of which is hashed separately. Choosing a password that is fifteen characters or longer guarantees that an LM hash will not be generated.
Common uses
Nearly all distributions and variations of , Linux, and use hashes with salts, though many applications use just a hash (typically MD5) with no salt. The Microsoft Windows NT/2000 family uses the and hashing method (based on MD4) and is also unsalted, which makes it one of the most popularly generated tables.