Rainbow table attacks

Brute-force attacks are attacks in which, unlike when using rainbow tables, an attempt is made to guess the password by simply trying out all available passwords of a certain length and complexity. Trying out is only carried out according to a method that prevents the same password from being tested more than once. There are no further optimizations or adjustments. That is why we speak of brute force. This form is also called exhaustive search in cryptography, because in the worst case the entire range (keyspace) of possible passwords of a certain “strength” has to be tried out before the correct password is found.

Brute force attacks are the “simplest” form of attacks for guessing passwords, but unlike other attacks, they can be successful in most scenarios (at least in theory). Brute force attacks and other password attacks can be carried out online or offline.

In order to understand the dangers of the further attack method, it is first necessary to explain two different cases of password attacks, then the attack with rainbow tables is explained. A basic distinction is made between online and offline attacks on passwords.

In the event of online attacks, the passwords are saved directly on a log-in mask, e.g. B. tried with a server or a logon to the operating system of a computer. These attack attempts are usually noticed quickly because a large number of failed login attempts are registered. One protection mechanism against this form of attack is blocking the source of these login attempts (e.g. an IP address via which the registrations are sent). However, this protective measure has the disadvantage that the measure itself can be used again for an attack on the protected service, because a targeted triggering of the protective measure can block users or service or administration accounts (denial-of-service attack). In the case of online attacks, the direct use of rainbow tables is not advisable, as the password itself has to be entered in clear text in the log-in mask.

Offline attacks attempt to compute passwords from intercepted information about passwords. This can be the result of a data breach in a password database, as we unfortunately experience it almost every day, or after password hashes were recorded or intercepted during transmission. All offline attacks are then used to return such a hash value to what is known as plain text, i.e. a password as entered by the user. This is very costly, because cryptographically secure hash procedures are one-way functions. So the function cannot simply be reversed. Therefore, a plain text must be found that delivers the same hash value by using the corresponding hash function. Because hash functions are never collision-resistant, there is always the possibility that different input values ​​provide the same hash value. It is therefore irrelevant whether it is the actual password. So the hash value is guessed. “Cracking” the hashes is necessary because passwords should not be stored in plain text. This means: A server or other functions that check a password do not themselves have the clear text version of the password.

Offline attacks, for example using rainbow tables, have the advantage for the attacker that they can use a lot more resources such as time and computing power to crack the passwords. In contrast to online attacks, this effort is not noticeable because the passwords are first returned to their plain text and only a successfully cracked password is used on a log-in mask.

One form of offline attacks on passwords is rainbow table attacks. These attacks using rainbow tables represent a compromise between the time required and the storage space required to carry out a specific attempt at cracking passwords can be calculated before the actual attack attempt.

In theory, an attacker could calculate a hash table for each hash process and a defined set of possible passwords (e.g. all passwords with a maximum length of 8 characters, consisting of upper and lower case letters and numbers) in which each of these Passwords are assigned the corresponding hash value. In order to assign the corresponding password (s) to a hash value, you then only have to search this table for the appropriate hash, which is much faster than hashing all passwords again.

However, a table with all possible hash values ​​cannot be used in practice because, even with very weak passwords, the memory requirement for this table is so large that it becomes impossible to save the information. By using rainbow tables, the size of the table used can be reduced so that the rainbow table can be saved on modern data media. The initial computational effort for creating the rainbow table remains similar to creating a simple hash table. As a compromise, however, a higher (but acceptable) computing effort must be expected during the actual attack attempt. Rainbow table attacks are therefore a so-called space-time tradeoff, which offers a feasible compromise between computational effort and memory requirements.

Rainbow tables are composed of hash chains. This procedure is based on a method introduced by Martin Hellman. Based on a certain number of possible passwords that serve as the starting point for the hash chains, the chains are hashed and “reduced” the resulting hash value into a form that meets the password criteria and can then be hashed again . It is important here that the reduction functions that carry out the reduction are not a reverse of the hash process, because such an inverse function does not exist. The reduction turns the hash, which is much larger than the original password, i.e. much more complex, is just a value that meets the criteria of password strength.

Example: The exemplary hash value of the “password” is hunter22

20d2fe5e369db54ec7090639a9dc30ec4d608604936239d39e2de07fda09eb0b

The reduction of this could be to use only the first 8 characters of the hash as the next password in the chain. These would then be “20d2fe5e” and can be hashed again as the next step.

A hash chain therefore consists of “alternating” possible passwords and their corresponding hash values. Taken alone, this method does not offer any advantage over the theoretical use of a simple hash table, because if the hash chains are used to an extent that covers all possible passwords of the corresponding complexity and then these chains are stored in a table the required storage space is at least as large as that of a simple hash table. Therefore only the starting point, ie the first password and the last “password”, ie a last reduction of the last hash value created in a chain, is saved in a table. The table therefore consists of a corresponding number of start and end points of hash chains.

If you now have a hash value, this can be tested using the reduction function to determine whether the hash value is part of one of the hash chains created. To do this, the reduction function is applied to the hash value. If the result of the function is one of the end points of the chain, then the hash chain has been found in which the password for the existing hash value is located. In the best case just described, this would be the penultimate password in the chain, which led to the last hash value in the chain. As a rule, however, you will not find a password directly in the first reduction step. Therefore, the reduction function (s) and the hash function have to be repeatedly applied to the originally captured hash value. You can imagine this as an example of trying to put the hash chain containing the captured hash value back together starting from the back. The moment the partially built hash chain has an end point that is stored in the rainbow table, the complete hash chain has been found and the password can be extracted in plain text.

In contrast to the method proposed by Martin Hellmann, in which only one reduction function is used, rainbow tables use a different reduction function for each reduction step in the hash chain. This is where the name rainbow table comes from, because applying a new function to each column of the table would be reminiscent of a rainbow if the reduction functions were displayed in different colors. The use of various reduction functions in rainbow tables has the advantage that hash collisions occur much less frequently. Collisions describe the case in which two different passwords generate the same hash value. Such collisions are very rare because cryptographic hash functions have the property of having a high level of collision resistance, but collisions can never be ruled out. If such a collision occurs in a hash chain with only one reduction function, the further course of the hash chain will always be the same. This is known as merging the hash chains. The number of passwords represented by the chains therefore decreases with each collision. As a result, the efficiency of this method becomes less and less as the size of the table increases, and thus more and more storage space is required. The use of different reduction functions in rainbow tables has the consequence that a hash collision and, as a result, a merging of the chains only occurs if the collision occurs in the same column of the table, i.e. when the same reduction function is used. Rainbow tables are therefore more efficient than simple tables made from hash chains.

Countermeasures for attacks with rainbow tables are the use of modern key derivation functions. These are special hash functions that should be used for hashing passwords. Primarily for protection against rainbow tables is the use of a so-called salt. A salt is a random string that is combined with the entered password the first time it is hashed and then saved together with the password hash and the username. If the password is re-entered, the salt is added to the input each time and the correct hash for authentication can only be generated through this combination. The salt doesn’t have to be kept secret. In order to be able to attack such a password successfully with a rainbow table, the tables would have to be precalculated for each individual possible salt value. If the salt is sufficiently complex, this is not possible because the computing effort and memory requirements are too great to realistically calculate these tables. Another property of key derivation functions is that they repeatedly hash the original password. Usually between 10,000 and 100,000 repetitions are usual. With a single password, the difference in the duration of the hash process can hardly be felt by the user. But if you scale the effort for the precalculation of a very large number of passwords, this quickly becomes uneconomical or even unrealistic due to the 10,000 to 100,000 times the computing effort even when using rainbow tables.

Another measure that every user has in their own hands to counteract a rainbow table attack is the choice of a sufficiently complex password. By lengthening the passwords used and using as many different characters as possible, the complexity of the password increases so quickly that it is no longer possible to calculate rainbow tables or crack using brute force. A recommendation for this is a password length of at least 12 characters and the use of upper and lower case letters, numbers and special characters. The password should also be randomly combined from these character sets. Since such secure passwords are difficult to remember, a password manager should always be used. In order to support users in choosing secure passwords, they should be trained in how to use them and the tools that can be used during their use. The user should also be made aware of the dangers of trivial passwords and the reuse or insecure storage of passwords.

Although modern cryptographically secure hash procedures and key derivation functions are used as standard today, rainbow tables still offer a benefit. NTLM hashes are still used today for Windows authentication, through which the password for Windows access is hashed. These hashes can, for example, be intercepted if a company network is compromised by hackers. Because these hashes are based on outdated hash procedures, they can be cracked using rainbow tables. MD5 hashes without a salt can also be cracked using rainbow tables.