A rainbow table is a lookup table offering a time-memory tradeoff used in recovering the plaintext password from a password hash generated by a hash function, often a cryptographic hash function. In Computer science, a lookup table is a Data structure, usually an Array or Associative array, often used to replace a runtime computation with In Computer science, a space-time or time-memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution or In Cryptography, plaintext is the information which the sender wishes to transmit to the receiver(s In computing a password is a Word or string of characters that is entered often along with a user name, in modern times usually into a computer system A hash function is any well-defined procedure or mathematical function for turning some kind of Data into a relatively small integer, that may A cryptographic Hash function is a transformation that takes an input (or 'message' and returns a fixed-size string which is called the hash value (sometimes A common application is to make attacks against hashed passwords feasible. A salt is often employed with hashed passwords to make this attack more difficult, often unfeasible. In Cryptography, a salt comprises random Bits that are used as one of the inputs to a Key derivation function.

Simplified rainbow table with 3 reduction functions

## Overview

A rainbow table is a compact representation of related plaintext password sequences (or chains). Each chain starts with an initial password, which is passed through a hash function. The resulting hash is then fed into a reduction function, which produces a different plaintext password. The process is then repeated for a fixed number of iterations. The initial and final passwords of the chain comprise a rainbow table entry.

Recovering a password using a rainbow table is a two step process. First, the password hash is run through the above reduce-hash sequence. The structure of the table and its reduction function guarantee that the running password will match a final password of one of the chains. This yields the initial password of the chain. Second, the iteration is repeated starting with this initial password until the original hash is found. The password used at the last iteration is the password being recovered.

The table content does not depend on the input of the algorithm. It is created once and then repeatedly used for the lookups unmodified.

Increasing the length of the chain decreases the size of the table. It also increases the time required to iterate over each chain, and this is the time-memory trade-off of the rainbow table. In a simple case of one-item chains, the lookup is very fast, but the table is very big. Once chains get longer, the lookup slows down, but the table size goes down.

### Example

We have a hash (re3xes) and we want to find the password that produced that hash.

1. Starting from the hash ("re3xes"), one computes the last reduction used in the table and checks whether the password appears in the last column of the table (step 1).
2. If the test fails (rambo doesn't appear in the table), one computes a chain with the two last reductions (these two reductions are represented at step 2)
• Note: If this new test fails again, one continues with 3 reductions, 4 reductions, etc. until the password is found. If no chain contains the password, then the attack has failed.
3. If this test is positive (step 3, linux23 appears at the end of the chain and in the table), the password is retrieved at the beginning of the chain that produces linux23. Here we find passwd at the beginning of the corresponding chain stored in the table.
4. At this point (step 4), one generates a chain and compares at each iteration the hash with the target hash. The test is valid and we find the hash re3xes in the chain. The current password (culture) is the one that produced the whole chain : the attack is successful.

Rainbow tables use a refined algorithm with a different reduction function for each "link" in a chain, so that when there is a hash collision in two or more chains the chains will not merge so long as collision doesn't occur at the same position in each chain. As well as increasing the probability of a correct crack for a given table size, this use of multiple reduction functions approximately doubles the speed of lookups. See the paper cited below for details.

Rainbow tables are specific to the hash function they were created for e. g. , MD5 tables can crack only MD5 hashes. In Cryptography, MD5 ( Message-Digest algorithm 5) is a widely used partially insecure Cryptographic hash function with a 128- Bit hash value The theory of this technique was first pioneered by Philippe Oechslin [1] as a fast form of time-memory tradeoff [1], which he implemented in the Windows password cracker Ophcrack. In Computer science, a space-time or time-memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution or Microsoft Windows is a series of Software Operating systems and Graphical user interfaces produced by Microsoft. Password cracking is the process of recovering Passwords from data that has been stored in or transmitted by a Computer system. Ophcrack is an Open source ( GPL license program that cracks Windows LM hashes using Rainbow tables The program includes the 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, SHA1, etc. RainbowCrack is the name of a computer program which generates Rainbow tables to be used in Password cracking. LM hash or LAN Manager hash is one of the formats that Microsoft LAN Manager and Microsoft Windows versions previous to Windows Vista use to store user In Cryptography, MD5 ( Message-Digest algorithm 5) is a widely used partially insecure Cryptographic hash function with a 128- Bit hash value

## Defense against rainbow tables

A rainbow table is ineffective against one-way hashes that include salts. In Cryptography, a salt comprises random Bits that are used as one of the inputs to a Key derivation function. For example, consider a password hash that is generated using the following function (where ". " is the concatenation operator):

`hash = MD5 (password . For concatenation of general lists see Append. In Computer programming, string concatenation is the operation of joining two character salt)`

Salt effectively extends the length and potentially the complexity of the password. If the rainbow tables do not have passwords matching the length (e. g. 8 bytes in the password, and 2 bytes of salt, is now effectively a 10 byte password) and complexity (non-alphanumeric salt increases the complexity of strictly alphanumeric passwords) of the salted password, then the password will not be found. If found, one would have to remove the salt from the password before it could be used. To prevent against a site specific rainbow table it is important that salts are stored per user, otherwise an attacker can just create a rainbow table including that site's salt + possible passwords, which for a large site will produce a number of hits.

Also, Rainbow tables tend to have little or no success when extrapolating outside the range of symbols or password length computed into the table. So, choosing a password that is longer or contains symbols not accounted for inside a Rainbow table can be very effective. Because of the sizable investment in computing processing, Rainbow tables beyond 8 places in length are not yet common. However, certain intensive efforts focused on LM hash, an older hash algorithm used by Microsoft, exist in the public domain. LM hash or LAN Manager hash is one of the formats that Microsoft LAN Manager and Microsoft Windows versions previous to Windows Vista use to store user

## 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. Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer Linux (commonly pronounced ˈlɪnəks In Cryptography, MD5 ( Message-Digest algorithm 5) is a widely used partially insecure Cryptographic hash function with a 128- Bit hash value The Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method and is also unsalted, which makes it one of the more popularly generated tables. LM hash or LAN Manager hash is one of the formats that Microsoft LAN Manager and Microsoft Windows versions previous to Windows Vista use to store user NTLM (NT LAN Manager (not to be confused with LAN Manager) is a Microsoft Authentication protocol used with the SMB protocol

## History

Rainbow tables are a refinement of an earlier, simpler, and less efficient algorithm that used the inversion of hashes by looking up precomputed hash chains.

Each table depends on the hash function and the reduce function used. The reduce function is a surjective ("onto") function which maps a hash to a password using the desired character set and password length. In Mathematics, a function f is said to be surjective or onto, if its values span its whole Codomain; that is for every Therefore, a reduce function for lowercase alphanumeric passwords of 8 characters length is different from a reduce function for case-sensitive alphanumeric passwords of 5–16 characters length.

A chain is a sequence of passwords. A starting password is chosen, and the following is done to get the next one in the chain:

After a chain containing a suitable number of passwords is created, the final password in the chain is hashed, and the final hash and the starting password are stored together in the rainbow table.

To reverse a hash, look for it in the table. If it isn't found, the following is done to get another hash to try:

hash(reduce(a hash)) → next hash

This is repeated until a hash is finally found in the table.

When a match is found, the original password that started the chain that ended with that hash can then be used to generate all the other passwords, and hence hashes, in the chain. Each of the hashes thus generated will be checked against the original target hash, thus hopefully revealing the correct password.

The end result is a table that contains statistically high chance of revealing a password within a short period of time, generally less than a minute. The success probability of the table depends on the parameters used to generate it. These include the character set used, password length, chain length, and table count.

Success probability is defined as the probability that the plaintext can be found for a given ciphertext. In the case of passwords, the password is the plaintext, and the hash of the password is the ciphertext, so the success probability is the probability that the original password can be recovered from the password hash.