Радужные таблицы: взлом паролей и методы защиты

Password cracking dataset
A rainbow table is a precomputed table for caching the outputs of a cryptographic hash function, usually for cracking password hashes. Passwords are typically stored not in plain text form, but as hash values. If such a database of hashed passwords falls into the hands of an attacker, they can use a precomputed rainbow table to recover the plaintext passwords. A common defense against this attack is to compute the hashes using a key derivation function that adds a "salt" to each password before hashing it, with different passwords receiving different salts, which are stored in plain text along with the hash. Rainbow tables are a practical example of a space–time tradeoff: they use 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 table that stores the hash of every possible password. Rainbow tables were invented by Philippe Oechslin

For user authentication, passwords are stored either as plaintext or hashes. Since passwords stored as plaintext are easily stolen if database access is compromised, databases typically store hashes instead. Thus, no one – including the authentication system – can learn a password merely by looking at the value stored in the database. When a user enters a password for authentication, a hash is computed for it and then compared to the stored hash for that user. Authentication fails if the two hashes do not match; moreover, authentication would equally fail if a hashed value were entered as a password, since the authentication system would hash it a second time. To learn a password from a hash is to find a string which, when input into the hash function, creates that same hash. This is the same as inverting the hash function. Though brute force attacks (e. g. dictionary attacks) may be used to try to invert a hash function, they can become infeasible when the set of possible passwords is large enough. An alternative to brute force is to use precomputed hash chain tables. Rainbow tables are a special kind of such table that overcome certain technical difficulties.

The term rainbow tables was first used in Oechslin's initial paper. The term refers to the way different reduction functions are used to increase the success rate of the attack. The original method by Hellman uses many small tables with a different reduction function each. Rainbow tables are much bigger and use a different reduction function in each column. When colors are used to represent the reduction functions, a rainbow appears in the rainbow table. Figure 2 of Oechslin's paper contains a black and white graphic that illustrates how these sections are related. For his presentation at the Crypto 2003 conference, Oechslin added color to the graphic in order to make the rainbow association more clear. The enhanced graphic that was presented at the conference is shown in the illustration.

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.