The standard procedure for authentication is to request a password, usually in combination with a username.
SEven if other authentication methods are used, a password is often implemented as an alternative or as a fallback solution.
The use of passwords as an authentication method offers numerous opportunities for attack, through which it is possible for unauthorized persons to gain possession of a password. The length and composition (complexity) of passwords are decisive for security, i.e. protection against guessing by third parties. The relevant attacks on passwords and their areas of application and countermeasures are explained below.
As a Brute force attack is an attack in which, unlike when using rainbow tables, an attempt is made to guess the password by simply trying all existing passwords of a certain length and complexity. The trial and error is only carried out using a method that prevents the same password from being tested more than once. There are no other optimizations or adjustments. That's why we're talking about 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" must be tried before the correct password is found.
Brute force attacks are the “simplest” form of password guessing attacks, 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 other attack method, it is first necessary to explain two different cases of password attacks, and then the attack with rainbow tables is explained. A basic distinction is made between online and offline attacks on passwords.
In the case of online attacks, the passwords are directly attached to a log-in mask, e.g. B. tried on a server or a login to the operating system of a computer.
These attack attempts are usually noticed quickly because a large number of failed login attempts are registered. A protection mechanism against this form of attack is to block the source of these login attempts (e.g. an IP address from which the logins 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 users or service or administration accounts can be blocked if the protective measure is triggered in a targeted manner (denial-of-service attack). In the case of online attacks, the direct use of rainbow tables is not advisable, since the password itself has to be entered in plain text in the log-in mask.
Offline attacks attempt to calculate passwords from intercepted information about passwords. This can be the result of a data breach in a password database, which we unfortunately experience almost every day, or after password hashes were recorded or intercepted during transmission. All offline attacks subsequently serve to return such a hash value to so-called plain text, i.e. a password as entered by the user. This involves a great deal of effort because it is cryptographically secure hashing are one-way functions. So the function cannot simply be reversed. Therefore, a plaintext must be found that delivers the same hash value by applying the corresponding hash function. Because hash functions are never collision-resistant, there is always the possibility that different input values return the same hash value. It is therefore irrelevant whether it is the actual password. So the hash value is guessed. The "cracking" of 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 plain text version of the password.
Offline attacks, for example using rainbow tables, have the advantage for the attacker that he can use many more resources, such as time and computing power, to crack the passwords. This effort is not noticeable, unlike with online attacks, 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 password attack is a rainbow table attack. These attacks using rainbow tables represent a compromise between the time required and the memory space required to carry out a specific attempt to crack passwords. The reduced time required per attack on a specific password hash is achieved by the fact that the so-called rainbow tables are unique and therefore already long can be calculated before the actual attack attempt.
In theory, an attacker could calculate a hash table for each hash method 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 or passwords to a hash value, you only have to search this table for the appropriate hash, which is much faster than hashing all the passwords again.
However, a table with all possible hash values cannot be used in practice because even with very weak passwords the memory requirements for this table are so large that it is 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 carriers. The initial computational effort to create 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 viable compromise between computing effort and storage 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, which serve as the starting point for the hash chains, the chains are hashed and the resulting hash value is "reduced" into a form that meets the password criteria and can then be hashed again . It is important here that the reduction functions that perform the reduction are not an inverse of the hash procedure, 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, into a value that meets the password strength criteria.
Example: The example hash value of the "password" is hunter22
20d2fe5e369db54ec70906 39a9dc30ec4d6086049362 39d39e2de07fda09eb0b
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 consists of "alternating" possible passwords and their corresponding hash values. On its own, however, 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, i.e. the first password and the last "password", i.e. a last reduction of the last created hash value of a chain, is stored in a table. The table thus consists of a corresponding number of start and end points of hash chains.
If you now have a hash value, you can use the reduction function to test whether the hash value is part of one of the created hash chains. 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 you have found the hash chain that contains the password for the existing hash value. In the most favorable 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 must be repeatedly applied to the originally captured hash value. One can imagine this by trying to put the hash chain containing the captured hash value back together again, starting at the end. The moment the partially constructed hash chain has an endpoint stored in the rainbow table, you have found the complete hash chain and can extract the password in plain text.
In contrast to the method proposed by Martin Hellmann, which uses only one reduction function, rainbow tables use a different reduction function for each reduction step in the hash chain. Hence the name rainbow table, because applying a new function to each column of the table would resemble a rainbow if the reduction functions were plotted in different colors. Using different reduction functions in rainbow tables has the advantage that hash collisions occur much less frequently. Collisions refer to the case in which two different passwords produce the same hash value. Although such collisions are very rare because cryptographic hash functions have the property of having a high collision resistance, collisions can never be ruled out. If such a collision occurs in a hash chain with only one reduction function, then the further course of the hash chain will always be the same. This is known as merging the hash chains. The set of passwords mapped by the chains therefore decreases with each collision. As a result, the efficiency of this method decreases as the size of the table increases, and more and more storage space is required. The use of different reduction functions in rainbow tables means 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 using the same reduction function. Rainbow tables are therefore more efficient than simple tables made up of hash chains.
Countermeasures against attacks with rainbow tables are the use of modern key derivation functions. These are special hash functions that should be used to hash passwords. The primary 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 when it is hashed for the first time and then stored together with the password hash and the username. Each time the password is re-entered, the salt is added to the input and only this combination can produce the correct hash for authentication. The salt does not have to remain secret. In order to be able to successfully attack such a password with a rainbow table, the tables would have to be precalculated for every single possible salt value. With a sufficiently complex salt, this is not possible because the computational effort and memory requirements are too great to be able 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 hashing time is hardly noticeable to the user. However, if you scale the effort for the pre-calculation 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 can take to counteract a rainbow table attack is choosing 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 a random combination of 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, training should be provided on how to use them and the tools that can be used when using them. 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 hashing and key derivation functions are now standard, rainbow tables still have utility.
NTLM hashes are still used today for Windows authentication, through which the password for Windows access is hashed. These hashes can be intercepted by hackers, for example, if a company network is compromised.
Because these hashes are based on outdated hashing methods, they can be cracked using rainbow tables. Even MD5 hashes without a salt can be cracked by rainbow tables.
