A rainbow table is a precomputed table used to reverse cryptographic hash functions, primarily for the purpose of cracking password hashes.
Cryptographic hash functions are designed to take an input (like a password) and transform it into a fixed-length string of characters, known as a hash. These hashes are one-way functions, meaning that it’s computationally difficult to reverse the process and retrieve the original input from the hash. Rainbow tables offer a way to speed up this process by essentially “pre-calculating” many possible hashes and storing them in a table for quick lookup.
The concept behind a rainbow table was introduced by Philippe Oechslin in 2003 as a way to optimize the process of reversing hashes. Oechslin’s innovation was to use a technique called “chain reduction,” which involves reducing hashes into new potential inputs through a series of steps, creating a chain of hash-input pairs. This method significantly reduces the size of the table required to cover a larger number of possible password hashes, making it more efficient and practical to use.
Rainbow tables work by storing precomputed hash values for a range of inputs (such as common passwords or character combinations) and their corresponding hash values. Instead of calculating the hash of every possible password guess during an attack, the attacker can simply look up the hash in the rainbow table. However, generating and storing these tables requires significant computational resources.
To defend against rainbow table attacks, techniques like salting, where a random value is added to the password before hashing, are used to ensure that each hash is unique, rendering the rainbow table ineffective.
What is a Rainbow Table Attack?
A rainbow table attack is a password cracking method that uses rainbow tables to crack the password hashes in a database. Cybercriminals adopted the rainbow table compilation as an easy way to decrypt passwords to enable them to gain unauthorized access to systems, rather than relying on the dictionary attack method (which consumes more memory space) or brute force attack (which consumes more computing power). All the attacker needs to do is just check the rainbow table to find the password’s hash. Rainbow tables are deliberately designed to consume less computing power at the cost of using more space. As a result, it usually produces results quicker than a dictionary or brute force attacks, often taking minutes to crack where other methods may take much longer.
But these benefits come at a price. Rainbow tables take a considerable amount of time to compile from the ground up. This is because all the hashes and the computing work that goes with them must be calculated and stored beforehand, although precompiled ones can also be downloaded online. But once you get all that sorted, you have a rainbow table that you can always reuse whenever you need to crack a password.
How does a Rainbow Table Attack work?
Before a rainbow table attack can take place, attackers must first gain access to leaked hashes. For instance, an attacker may find a vulnerability in a company’s Active Directory or web application with a poorly secured password database. The attacker steals the password hashes and, using a rainbow table, the attacker can decrypt the passwords of every user of the system or application into plaintext passwords.
Let’s say you have 1500 leaked passwords to decrypt; in a brute force attack, you would have to calculate all possible word combinations, compare them with the password’s hash, and do this for every password. Whereas in the rainbow table attack, you calculated all hashes once, and now you just need to find the right one that matches.
In addition to these techniques, millions of leaked password hashes on the dark web are available to criminals. Once they get hold of these password dumps, the rainbow table can help decrypt the password hashes. This, in a nutshell, is how a rainbow table attack works.
How do you prevent Rainbow Table Attacks?
Preventing your system or application from rainbow table attacks is relatively straightforward. The following are simple steps you can use:
- Use password salting: The primary antidote to the rainbow table attack is password salting. Salts are simply a way of introducing randomness into the resultant hashes. A salt allows one password to hash multiple ways. In the absence of salts, the same password will yield the same hash every single time. Therefore, hashed passwords should never be stored without salting. Instead of compiling one rainbow table for a system that does not use salts, thousands or more rainbow tables would be required for systems using salts, depending on the salt length. This makes the password more difficult to decrypt.
- Use MFA: Using multi-factor (MFA) or two-factor authentication (2FA) that involves what you are (biometrics) and what you have (token), for example, makes it difficult for anyone to access your account with just a password. This makes it impossible for an attacker to use a rainbow table attack effectively.
- Avoid outdated hashing algorithms: Attackers look for applications and servers using obsolete password hashing algorithms such as MD5 and SHA1; or hashes that don’t include salts. Notably, Windows’ LM and NT hashes do not include salts, making them particularly vulnerable to rainbow attacks. If your application uses those weak algorithms, your risk for rainbow table attacks substantially increases.
- Go passwordless: If there are no password hashes to steal, there will be no rainbow attacks in the first place. Unfortunately, users will always find ways to use weak passwords. They struggle to remember strong passwords and end up writing them down and reusing them. Weak passwords are easy to crack and leave the organization vulnerable to data breaches. Going passwordless is a sure way to eliminate the threat of a rainbow attack.
Are Rainbow Table Attacks still a threat?
Some security experts argue that rainbow tables have been rendered obsolete by modern password cracking methodologies. Instead, most attackers now use the more advanced Graphics Processor Unit (GPU) based password cracking methods.
A moderately-sized GPU farm can easily recreate a rainbow table within a few seconds. This means that encoding those passwords into a rainbow table would not make that much sense. Moreover, most passwords are salted anyway, meaning we would need rainbow tables for each salt value, and for larger salts, this is entirely impractical. Bitcoin and other cryptocurrency miners have been tapping GPU technology to calculate hashes for bitcoin farming. There are existing tools that can leverage GPU technology to decrypt password hashes potentially. For example, the Linux-based GPU cluster was used to crack 90 percent of the 6.5 million leaked LinkedIn password hashes in 2012.
Nonetheless, rainbow tables may not be the biggest threat to organizations today. Still, they are certainly a threat and should be considered and accounted for as part of an overall security strategy.
