A Rainbow Table is a set of precomputed passwords and their corresponding hash values that can be used to find out what plaintext password matches a particular hash
Think of it as a table containing two columns. The first column contains hashes, while the second column contains plaintext for the hashes. As you may well know, the passwords in a computer system are not stored directly as plain texts but are hashed (scrambled) values using one-way encryption (hash function). This means that the hash values cannot be decrypted. So whenever a user enters a password for authentication, that password is converted into a hash value and is compared with the already stored hash value. If the values match, the user is authenticated.
The term “Rainbow Tables” was first used by Philippe Oechslin in his research paper titled “Making a Faster Cryptanalytic Time-Memory Trade-Off“, which explored the performance trade-offs between processing time and the memory needed for cryptanalysis. The paper itself is based on an earlier research work by Martin Hellman and Ronald Rivest. The term “Rainbow Tables” was used to refer to the way colors were used to represent different reduction functions and steps. This created a colorful rainbow with a corresponding number of iterations, hence the name rainbow table.
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.
