What is a Rainbow Table (for password cracking)?

Rainbow Tables are used in password recovery, IT forensics, penetration testing, and password cracking. The Rainbow Table is a data structure that enables a fast, memory-efficient search for the original string (usually a password) for a given hash value. Searching via a rainbow table is considerably faster than using the brute force method, but the memory requirement is higher. Such a trade-off is called a time-memory tradeoff.

This assumes a hash function (such as MD5) without salt, as is the case with passwords for earlier versions of Windows and many routers. Comparatively extensive tables have been calculated for LM hashes and MD5 and are available from various sources.

Brute force is plain guessing of the correct password. It is easy to use this method unless the site locks after the next attempt. The next method is a dictionary attack, which uses a rainbow table to figure out your password, which we are discussing. In the old days, passwords were saved in some files such as /etc/passwd, in this kind of format:

username:MD5 hashed password

It is easy to use MD5 tool to hash any string:

As the tool is the same, and the number of characters is limited if two users use the same password, the hashed string will be the same! That is a basic example of “collision”. These days, we add salt before hashing the password. Plus we no longer use MD5 as a hashing algorithm for passwords. Modern hash values are far longer than it was with MD5 output.

Basics of a Rainbow Table

A rainbow table is a compact representation of connected password sequences, so-called chains. Each of these chains starts with an initial password, which is passed through a hash function. The resulting hash is in turn passed through a reduction function with the result of having another potential plaintext password. This process is repeated for a predetermined number, and finally, the first password of the chain is stored along with the last hash value.

When creating the table, make sure that on the one hand, no password that occurs in a chain is used as a starting password (collision), but on the other hand, all possible passwords occur in the table. The tables are created only once and then serve as a lookup table.

Figuring out a password requires a two-step process. First, the hash of the searched password is passed through the sequence of reduction and hash functions until the resulting hash value appears in the column of the last chain links in some chain (the “right side” of the table). This has found the chain that contains the given hash. Starting from the start password of this chain, you now apply the hash reduction sequence until you get the given hash value. The password that precedes the hash value is the password you are looking for.

The length of the chain, i.e. the number of iterations to create the tables, affects the size of the table: the longer the iterations are chosen, the smaller the resulting table. In the simplest case, the number of iterations is equal to 1, so the table contains all password hash pairs.

This is an example of rainbow table generator:

How Rainbow Table Works

A hash function assigns a binary sequence of fixed length to a binary sequence of arbitrary length. In the case of the MD5 hash function, this output length is 128 bits or 32 4-bit characters. To a random string with the length n a hash value is calculated. This result of the hash function (with length 32) is converted into a new string by a reduction function R, which again returns the length n possesses. Because the sequential execution of the hash function and the reduction function do not change the length of the string, these two steps can be repeated alternately as often as desired. In the end, the sequence of intermediate results forms a chain. The initial and final values of this chain are stored. This sequence of steps will also be x repeated times and forms a universal Rainbow Table.

The reduction function shortens a hash value to n Sign. Each of these reductions yields a new “unique” 128-bit string, or a collision, e.g. by MD5. A collision is a hash value that can be generated by different output strings. To avoid collisions, various reduction functions are used, which periodically allow a unique assignment of the input string and the output hash. This method is a more efficient method for n-character strings than, for example, a brute-force attack with a key lookup of [a-//////], because the latter converts many strings into hashes that are highly likely never dropped or chosen.

In the case of poorly programmed or trivial reduction functions, collisions occur after a few runs, which lead to repetitions of the reduced texts and thus also of the hashes. Such internal loops then cause the algorithm to fail: you laboriously calculate thousands of elements, and only a few of them are distinguishable.

In this example, we are looking for the string whose MD5 hash value corresponds to 97fae39bfd56c35b6c860aa468c258e0 in the hexadecimal representation (Domino). The traditional way of calculating all MD5 hashes for all possible variations and comparing them is very computationally intensive and needs to be repeated in new searches.

It would now make sense to store all hashes that have already been calculated in a database and only have to compare whether the hash you are looking for is already known when searching again. A search of more than 64 possible characters [A-Za-z0-9./], which could have each digit of the introductory text, yields 64^6 Variations. If text and hash are stored in a database, 16 bytes per pair are needed for the hash and 6 bytes for the plaintext, and thus about 1.4 terabytes for the complete data. In most cases, these data volumes cannot be processed and must be reduced.

Instead of storing all values and keys, only the initial string and the last string of a n-element chain. In this way, it is possible to n-1 represent hashes by a start and end value and recalculate them in a comparatively short time and thus find the input text again. If a final value is formed from a reduced hash (= plaintext), this chain is recalculated from the starting value until the given hash is obtained; the text preceding it is the source text you are looking for. With a chain length of n=10,000. This means that only 9,999 hash calculations are needed to find the source text for a hash.

The probability of obtaining exactly the desired input text from the reduced hashes depends on the quality of the reduction function(s) and the parameters when creating the rainbow table, since only the reduced hashes (= plaintexts) can be found later. For example, if the reduction function(s) are reduced to numbers only, the plain text “Domino” cannot be found. If the reduction function(s) to seven digits (out of 32), then 6-digit plaintexts are not calculated and “dominoes” cannot be found here either.