Why Rainbow Tables Aren't the Pot of Gold They Once Were

Today I’m presenting a SANS workshop on password cracking for OSINT and digital forensics. The workshop will require no previous knowledge and will progress from explaining how things work to how you can effectively crack passwords for file formats such as Office, Zip, RAR and PDF.

There are a few topics that I won’t be covering that I expect to get some questions on. That’s the purpose of this blog post. Those topics are salt and rainbow tables. It’s not that these topics aren’t interesting or worth talking about; they’re just not as relevant to password cracking as many people think they are. Let’s explain!

When I mention password cracking, many people instantly respond with “rainbow tables!!”. I try to avoid speaking in absolutes so I won’t say rainbow tables are useless, but I will say they aren’t much of a thing anymore.

In the workshop, we cover how to acquire password hashes from files and how to crack them. Let’s place that aside for a second and instead talk about a book.

Imagine someone handed you a 2,000-page book on world history and asked you to find every page that mentioned Napoleon. That request could easily take a full week if you need to read every page, or 5 minutes if the book has an index at the back we can use to instantly identify pages that mention Napolean.

Think of what an index does. The publisher, thankfully for us, decided to trade effort back then when they were making the book and storage space (an index takes up a lot of pages) in exchange for much faster lookups in the future.

Now let’s go back to password cracking. Imagine a company asks me to fly to Orlando next month to try to capture Wi-Fi traffic from a network called “Orlando Widgets Inc” and try to crack the Wi-Fi password. We know what hashing algorithm is used for Wi-Fi passwords, so imagine I take the massive word lists I use for password cracking, and figure out what the Wi-Fi hash would be for every one of them. I then save all of those as a giant list that I can search. It takes me a lot of effort now, plus storage space, to store the massive list, but now when I fly to Orlando and capture some Wi-Fi traffic, instead of having to “Crack” the hash live, I can just search for the hash in my table and hopefully have an answer in minutes instead of hours or days. It’s the exact same concept as the index in the book. When you hear the term “rainbow table”, think of a giant list of potential passwords and their hashes that we can quickly search. Underneath the hood, they’re a bit more complicated than that to try to save space, but that’s not important for us right now.

So, rainbow tables sound awesome, and no wonder so many people talk about them. But most modern systems introduce a huge problem for them: salt.

From a password security perspective, rainbow tables were obviously a huge threat, but what could be done about it? Turn’s out theirs an easy solution.

Imagine we have a database for users of our website that contains our user’s usernames, password hashes, and a timestamp of when the account was created.

From looking at this database, you don’t know what any of the passwords are, but you notice that Matt and Sarah have identical password hashes, so they must have the same passwords. If an attacker steals this and cracks Matt’s password, they’ll instantly know Sarah’s as well.  In addition, the attacker will recognize that these hashes were created using the MD5 algorithm, and if they have a rainbow table for MD5 hashes, they may be able to crack these hashes very quickly. Now, let’s see what we can do to render the rainbow table nearly useless.

In this example, Lisa’s plain text password is “password” which computes to a hash of “5f4dcc3b5aa765d61d8327deb882cf99”. But what if when the Lisa user created their account, the system appended the timestamp onto the very end of the plaintext before it calculated the hash. The result would be a “password” of “password6445586576” which would have a hash of “91992da8dda226a12089034bad623af6”. Now anytime the Lisa user logged in, the system would automatically add the created timestamp onto what was typed into the password field, compute the hash, see they match, and allow access. In this case that timestamp that was added onto the password before the hash was calculated is referred to as a “salt”.

Let’s take a look at what adding in a salt accomplished:

First, even though Matt and Sarah still have the same password, they now have different hashes since they have different salts (in this case, the timestamps). But even more powerful, Lisa’s password is “password” which is assuredly going to be in any attacker’s dictionary of things to try, but what about ““password6445586576”?? Probably not. Adding in these salts just made the attacker’s MD5 rainbow table obsolete. 

That’s what a salt is, why most modern systems use them, and why outside of a few exceptions, rainbow tables aren’t terribly useful for password cracking.

Let’s go back to the scenario where I have to fly to Orlando to crack the Wi-Fi password for the network “Orlando Widgets Inc”. In this case the name of a Wi-Fi network matters because the name of the network is the salt used for the password hash! So if I knew the name of the Wi-Fi network in advance, I still could create a rainbow table, but it would only be useful on Wi-Fi networks with that same name. Really doesn’t seem worth the effort, right?

To further reduce the need for rainbow tables, modern Graphics Cards (GPUs) can crack many hashing algorithms at a very high rate of speed. I have a midrange GPU (Nvidia 2070) on the computer I’m typing this on, and even that card can crack Wi-Fi WPA2 passwords at over 460,000 guesses per second!

I can still try to crack the password since Hashcat will automatically calculate the salt from the captured Wi-Fi traffic, but a rainbow table just really doesn’t make sense.

This is a somewhat simplistic explanation of what salt is and why it’s a rainbow table killer. If you’re curious what the exceptions are, the most common use of rainbow tables by pen testers is for hashes obtained from users on a Windows system. Attackers who gain access to a Windows system can attempt to obtain the hashes for other users on the system. If they get these hashes, they can use Hashcat to crack them at a very fast rate, but Windows doesn’t salt these login hashes, so rainbow tables can be used by pen-testers and attackers to quickly crack some passwords.

Is this a huge security issue for Windows?? In my opinion, it’s pretty meh. Even my mid-range GPU can crack an NTLM (Windows login) password at a rate of millions of guesses a second. With quality dictionaries and useful rule files, I like my chances to crack a few hashes.

Hopefully these examples were clear, but I’m planning on recording a YouTube video as well to help explain these concepts. As always, if you have any questions, please feel free to reach out!