What Is a Rainbow Table Attack?

A rainbow table attack is an authentication attack where the attacker attempts to identify passwords from their cryptographic hashes. Typically authentication systems store passwords in a hashed format, which is computed by a cryptographic algorithm, rather than keeping them in plaintext. When a user authenticates with a password, the system computes the hash and compares it to the user’s stored hash. 

While they're a better solution than plaintext lists, these hashing algorithms, especially earlier versions, contain a major flaw. When a password is hashed, the hashing function gives each character a value, creating a chain of alphanumeric characters. An attacker can precompute all potential hashes and put them in a table known as a rainbow table. So, when the attacker discovers a list of hashed passwords, they consult this rainbow table to match the hash with what they have already worked out is the corresponding password.

The attack is an example of the time/memory trade-off, as it takes less processing power than a brute force attack, but rainbow tables require a lot of storage space. 

What Does a Rainbow Table Attack Look Like?

Step 1

The first level of the rainbow table attack is creating the table itself. This is done by using the hashing algorithm, such as MD5 or SHA1, to identify the value of each character and string of characters (i.e., potential passwords). For example, the hash for one of the most common passwords in the world (12345678) in the MD5 algorithm is hashMD5(12345678) = 25d55ad283aa400af464c 76d713c07ad. To save space, rainbow tables will not necessarily have every possible hashed function for every potential value (i.e., password). Instead, a reduction function is used, which forms a chain of alternating values and keys.

This is the most time-consuming element of the attack, but since the algorithm stays the same, the table will be reusable for every subsequent attack. It's also possible to purchase pre-populated rainbow tables.

Step 2

The next step is getting the lists of hashed passwords. The attacker can obtain these directly if they manage to gain access to an organization's Active Directory or locate a flaw in a system, such as a recent one at Slack that exposed hashed passwords after users created or revoked an invite link. 

Successful data breaches often come away with millions of hashed passwords, such as the 162 million from Dubsmash in 2018 and the 92 million in an attack on MyHeritage in 2018. These lists appear for purchase on the dark web and are even collected into huge lists containing billions of hashed passwords. 

Step 3

Once in possession of a series of hashed passwords, the attacker searches for matches between the password, its corresponding key, and endpoint values in the rainbow table. The cracking process involves iterating along the chain by finding a matching endpoint until the password's value is reached. Different values may come from the same endpoint; these are false positives. After the attacker ascertains they are not the correct password, they go back to other potential values until the right password is found.

How to Defend Against Rainbow Table Attacks

Multi-Factor Authentication

Traditional multi-factor authentication (MFA) or two-factor authentication (2FA) won’t prevent a rainbow table attack per se, but it means the attacker also needs to breach the additional verification factor.  While this may not stop a determined hacker, it will thwart a standalone rainbow table attack.

Eliminate Passwords

Rainbow table attacks are based entirely on cracking encrypted passwords. Hackers then use the cracked password to access the user's account. Removing passwords from the authentication process disables the rainbow table attack, as there are no hashed passwords to work with. Some solutions call themselves passwordless but actually still use passwords in the process so make sure to choose a FIDO-based passwordless solution. Authentication certified to FIDO standards is recommended by CISA and other regulatory bodies.

Salting

Modern approaches to password hashing and storage often incorporate a method known as salting. Salting adds random data, the salt, to the password before hashing. This means that rather than having the same definite outcome each time a password is hashed, the results are now randomized. Salted hashes can only be cracked by computing power in a brute force attack rather than a rainbow table attack.

Avoid Outdated Algorithms

Certain algorithms, such as MD5 and SHA1, are now considered obsolete, while system processes, including Windows' LM and NT, do not salt stored passwords. Though they may be obsolete, these services can still be widespread, and attackers will search for systems that use them to attempt to crack their password directories and steal their hashed passwords. 

Key Stretching

This involves lengthening the hashed password to make it even more challenging to crack. The process works by adding the salt, some intermediate functions and the password itself and running them through the hashing function again, which means it takes much longer to discover the true key, even with a rainbow table attack.

Eliminate Authentication Attacks With Passwordless 

Rainbow table attacks are a means of cracking encrypted or hashed passwords without needing large amounts of computing power. As hashing functions are widely known, the attacker can calculate the values of all passwords, then store linked sections. When cracking a list of hashed passwords, the attacker must locate the linked section of the hashed value, which greatly narrows down the possible value outcomes. Though salting largely eliminates the viability of rainbow table attacks, the risk still exists as various applications still use just a hash, with no salt. 

The root cause, like many authentication attacks, is the use of passwords. By completely removing passwords from your authentication processes and deploying phishing-resistant MFA, you can stop the most common authentication attacks at their source and significantly strengthen your overall security posture.

Learn more about passwordless authentication in this introductory guide.

To see how HYPR's passwordless MFA can significantly improve enterprise security while reducing costs and user friction, sign up for a free demo.