Rainbow Tables for Password Breaking

How they work and how to stop them

Passwords remain a critical line of defense against unwanted intrusions into a user’s online accounts or files. Over the years, in the face of surging efforts to crack or steal passwords, a veritable arms race has developed. On the “good” side, a current iteration of password protection comes in the form of hashing. Most repositories of user passwords no longer store them in plain text. Instead, these critical pieces of information are hashed first, and only the hash value is stored. I wrote about this previously as follows:

Hashes essentially work like a cipher, using a mathematical formula to scramble the text (and other characters like numbers or !, @, #, etc.). Hashed passwords cannot be resolved in the reverse. A standard password meeting the usual requirements of upper and lower case letters, numbers, and special characters might look like: Dr23@@aq1a11c)(x. The resulting MD5 hash of that password comes out as: 079CA1D94BD0E41B61C2B3F46EFC9AF6. [Note that there are a variety of hash types, SHA1, SHA 256, SHA512, Blake3, etc., but MD5 remains the most common form used for password security]. Because hackers cannot resolve hashes in the reverse, they enter them into programs to “crack” them. In plain terms, they use software to attempt every possible combination of letters, numbers, and special characters, hash them, then run the hash results against stolen hash value databases for hits. When they find one, they know they possess a viable password.

Even knowing the hashing algorithm, an attacker still cannot resolve the password from the hash value. The simplest form of attack to decipher the password from this hash value is known as a brute force attack. To do so, attackers use software to attempt every possible combination of letters, numbers, and special characters. With the advent of employing GPU processors to perform this attack, an easily obtainable program can calculate up to 164 billion attempts per second. With the assistance of cloud-based GPUs, the calculations-per-second jumps by several orders of magnitude. Nevertheless, reasonably strong passwords (13 or more mixed characters) contain many, many more combinations. Even with extreme computing power, a cloud-based GPU could take up to 47 years to crack a 13-character password. To reduce these calculation times, attackers adopt adjacent methodologies, some based on the psychology of people’s password practices (such as a dictionary attack), or through mathematical means to reduce the overall complexity of the targeted password. That’s where Rainbow tables come into play.

Rainbow tables are (typically huge) files which marry a portion of a password together with its hash value. This provides a dataset to run against when trying to decipher a hashed password in a website database or stolen from a data breach. Many Rainbow tables exist online of varying size and are freely available. Rainbow tables incorporate reduction functions that turn the hash values back into plain text. Note, this is not a reversal of the hash value, rather it is a computation of the hash value into a new, plaintext output value. The lines of the table work in sequence, so the previous line’s output provides the input for the subsequent line. This creates a chain of functions that, if properly followed, allows a user of the table to rebuild the chain merely from the first input and last output. Thus, with a robust enough table, the attacker could eventually “guess” a workable password (in specific circumstances).

In essence, Rainbow tables balance storage with computational speed. Hashing every single plaintext value and storing it in a table requires impossible space. Likewise, calculating every single plaintext possibility in most cases requires unavailable computational capability. Rainbow tables speed up the computational process by providing an effective shortcut. How they work is the attacker hashes pieces of plaintext, reduces the outcome, hashes that outcome, then reduces again. To form the chain, the attacker simply repeats this process over and over, with each link in the chain comprising a hashed value of the previous line’s output. So, it would look like this (here, using an MD5 hash algorithm):

Input: password

Hash value: 5F4DCC3B5AA765D61D8327DEB882CF99

Input: 5F4DCC3B (first 8 characters of the hash output above)

Hash Value: 3D96E56241547CB8CB638EDB31753232

Input: 3D96E562

*repeat*

This process is repeated to create a large volume of outputs which are stored in a table. The known hash of the password the attacker wishes to break is then run against the table to look for a match. If a match is found, the attacker would then apply the same formula as the above with the current password hash, following the chain from the requisite point on the table, until arriving at the same result.

Source: geeksforgeeks

The problem with Rainbow tables is that they target a very narrow password type and a specific hashing algorithm. This means that if the attacker does not know the parameters of the stored password hash, such as the hashing algorithm, a Rainbow table would probably not help. Even if the attacker knows these details, modern password protections employ another defense that effectively renders Rainbow tables useless. Over the last ten years or so, password hashing programs have adopted a “salt.” A password salt is a randomly-generated bit of data added to the password before it is hashed. The user to whom the password belongs does not even know the value of this bit. Adding the salt recalculates the hash value of the password, resulting in an entirely different result. Previously calculated hash tables will not include this value, and the outputs will not align with the Rainbow table values at all, rendering it ineffective.

Sadly, some websites and other online platforms still do not salt hashed passwords making them vulnerable to this method of attack. While attackers now tend to run brute force programs of varying flavors through high-powered GPUs, many wannabe hackers continue to adopt older, less efficient tactics to conduct their attacks. Cybersecurity professionals generally do not need to worry about these archaic methods, so long as they are implementing the most recent security measures. Salting hashes, while not new, remains an effective defense against Rainbow table and other hash-value-derived attack strategies.

***

I am a Certified Forensic Computer Examiner, Certified Crime Analyst, Certified Fraud Examiner, and Certified Financial Crimes Investigator with a Juris Doctor and a master’s degree in history. I spent 10 years working in the New York State Division of Criminal Justice as Senior Analyst and Investigator. Today, I teach Cybersecurity, Ethical Hacking, and Digital Forensics at Softwarica College of IT and E-Commerce in Nepal. In addition, I offer training on Financial Crime Prevention and Investigation. I was a firefighter before I joined law enforcement and now I currently run a non-profit that uses mobile applications and other technologies to create Early Alert Systems for natural disasters for people living in remote or poor areas.

Find more about me on Instagram, Facebook, Twitter, LinkedIn, or Mastodon. Or visit my EALS Global Foundation’s webpage page here.

Visit the new Evidence Files Facebook and YouTube pages; Like, Follow, Subscribe or Share!

For another article on cyberattacks, click below.