Misplaced Pages

Revision as of 00:04, 9 February 2021

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (March 2009) (Learn how and when to remove this message)

A rainbow table is a precomputed table for caching the output of cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a key derivation function (or credit card numbers, etc.) up to a certain length consisting of a limited set of characters. It is a practical example of a space–time tradeoff, using less computer processing time and more storage than a brute-force attack which calculates a hash on every attempt, but more processing time and less storage than a simple key derivation function with one entry per hash. Use of a key derivation that employs a salt makes this attack infeasible.

Rainbow tables were invented by Philippe Oechslin as an application of an earlier, simpler algorithm by Martin Hellman.Cite error: A <ref> tag is missing the closing </ref> (see the help page).

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 time/memory tradeoff, which he implemented in the Windows password cracker Ophcrack. The more powerful RainbowCrack program was later developed that can generate and use rainbow tables for a variety of character sets and hashing algorithms, including LM hash, MD5, and SHA-1.

In the simple case where the reduction function and the hash function have no collision, given a complete rainbow table (one that makes you sure to find the corresponding password given any hash) the size of the password set |P|, the time T that had been needed to compute the table, the length of the table L and the average time t needed to find a password matching a given hash are directly related:

${\displaystyle T=|P|}$

${\displaystyle t={\frac {|P|}{2L}}}$

Thus the 8-character lowercase alphanumeric passwords case (|P| ≃ 3×10) would be easily tractable with a personal computer while the 16-character lowercase alphanumeric passwords case (|P| ≃ 10) would be completely intractable.

Defense against rainbow tables

A rainbow table is ineffective against one-way hashes that include large salts. For example, consider a password hash that is generated using the following function (where "+" is the concatenation operator):

saltedhash(password) = hash(password + salt)

Or

saltedhash(password) = hash(hash(password) + salt)

The salt value is not secret and may be generated at random and stored with the password hash. A large salt value prevents precomputation attacks, including rainbow tables, by ensuring that each user's password is hashed uniquely. This means that two users with the same password will have different password hashes (assuming different salts are used). In order to succeed, an attacker needs to precompute tables for each possible salt value. The salt must be large enough, otherwise an attacker can make a table for each salt value. For older Unix passwords which used a 12-bit salt this would require 4096 tables, a significant increase in cost for the attacker, but not impractical with terabyte hard drives. The SHA2-crypt and bcrypt methods—used in Linux, BSD Unixes, and Solaris—have salts of 128 bits. These larger salt values make precomputation attacks against these systems infeasible for almost any length of a password. Even if the attacker could generate a million tables per second, they would still need billions of years to generate tables for all possible salts.

Another technique that helps prevent precomputation attacks is key stretching. When stretching is used, the salt, password, and some 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. The user's password hash is the concatenation of the salt value (which is not secret) and the final hash. The extra time is not noticeable to users because they have to wait only a fraction of a second each time they log in. On the other hand, stretching reduces the effectiveness of brute-force attacks in proportion to the number of iterations because it reduces the number of attempts an attacker can perform in a given time frame. This principle is applied in MD5-Crypt and in bcrypt. 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.

Specific intensive efforts focused on LM hash, 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 Unix, Linux, and BSD use hashes with salts, though many applications use just a hash (typically MD5) with no salt. The Microsoft Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method (based on MD4) and is also unsalted, which makes it one of the most popularly generated tables. Rainbow tables have seen reduced usage as of 2020 as salting is more common and GPU-based brute force attacks have become more practical. However, Rainbow tables are available for eight and nine character NTLM passwords.

See also

• A4/1
• Brute-force attack
• DistrRTgen
• Pollard's kangaroo algorithm

Notes

1. ^ Cite error: The named reference ophpaper was invoked but never defined (see the help page).
2. Lasecwww.epfl.ch
3. ^ Alexander, Steven (June 2004). "Password Protection for Modern Operating Systems" (PDF). Login. 29 (3). USENIX Association.
4. Ferguson, Neils; Bruce Schneier (2003). Practical Cryptography. Indianapolis: John Wiley & Sons. ISBN 978-0-471-22357-3.
5. Provos, Niels; Mazières, David (June 6, 1999). "A Future-Adaptable Password Scheme" (PDF). Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference. Monterey, CA, USA: USENIX Association.
6. Manber, U. (1996). "A simple scheme to make passwords based on one-way functions much harder to crack" (PDF). Computers & Security. 15 (2): 171–176. CiteSeerX 10.1.1.102.2597. doi:10.1016/0167-4048(96)00003-X.
7. Kelsey, J.; Schneier, B.; Hall, C.; Wagner, D. (1998). "Secure applications of low-entropy keys" (PDF). Information Security. LNCS. Vol. 1396. p. 121. doi:10.1007/BFb0030415. ISBN 978-3-540-64382-1.
8. How to prevent Windows from storing a LAN manager hash of your password in Active Directory and local SAM databases, Microsoft
9. A Case for Modern Rainbow Table Usage

References

• Oechslin, Philippe (2003-08-17). "Making a Faster Cryptanalytic Time-Memory Trade-Off". Making a Faster Cryptanalytical Time-Memory Trade-Off (PDF). Lecture Notes in Computer Science. Vol. 2729. Santa Barbara, California, USA: Springer. pp. 617–630. doi:10.1007/978-3-540-45146-4_36. ISBN 978-3-540-40674-7. {{cite book}}: |journal= ignored (help)

External links

Template:Z148

• Ophcrack page by Philippe Oechslin The original rainbow table research
• Template:DMOZ

• Cryptographic attacks
• Search algorithms
• Cryptographic hash functions
• Hash based data structures