A rainbow table is a data structure developed by Philippe Oechslin. It is used to quickly find the original character string (usually a password) for a given hash value in a memory-efficient way. And even if the memory requirement is higher, a search using a rainbow table is faster than using the brute force method.
Rainbow tables are used in penetration tests, in IT forensics and in password recovery and hacking. However, this is only possible if a hash function is used that does not involve salting.
The starting point for a rainbow table is always an initial password. This password is converted into a hash value using a pre-selected hash function. The hash value is then run through a reduction function to obtain a completely new plaintext password, which is then again converted into a hash value.
For example, the password “ABCXYZ123$” becomes the hash value “zl9wkb2”. The hash value “zl9wkb2” is used with the help of the reduction function to create the plain text password “Sommer2020!” and from that the hash value “2dh7wm1”.
This process takes is repeated many times, resulting in a long chain of passwords and hash values. However, only the first password and the last hash value are stored in the final table. These two values and the reduction function used are sufficient to determine all other values within the chain.
A table consists of multiple chains. To avoid collisions, it is important that a starting password does not occur in any other chain within the table. However, all possible passwords should be considered. To ensure better results, a different reduction function can be used for each step. Since these are often displayed in different colors, a finished table often resembles a colorful rainbow, hence the term rainbow table.
If a hash value is available for which the password is to be determined, the first step is to check whether the hash value has already been stored as a value in the final table. If this is the case, then the iterations of the chain “hash -> reduction -> hash -> reduction…” must be repeated until the end of the chain is reached, where the plaintext password is at the penultimate position before the hash value.
If the hash value cannot be found directly in the rainbow table, start by reducing the hash value that was used to create the chains. The result is hashed again, and the process is repeated until the hash value matches one of the hash values in the table, allowing the corresponding chain to be found. Then, starting at the beginning of the chain, the hash and reduction function are performed alternately until the hash value and thus the password you are looking for is found.
Rainbow tables can be several hundred gigabytes in size, depending on the length of a chain or the number of iterations. The longer the iterations are chosen, the smaller the resulting table. The simplest case is when the number of iterations is equal to 1. In this case, each row contains a particular password and its corresponding hash value, which, with billions of possible passwords, means a corresponding number of rows.