Hash Tables, Rainbow Table Attacks, and Salts
As we talked about, applications that properly handle passwords don’t actually store the passwords themselves in databases, but instead, store hashes of passwords. That’s why people came up with ways of attacking hash values with hash tables and rainbow table attacks.
In this article, we’ll talk about what those are, how they work, and how we can use salts to effectively defend against password attacks.
A brief introduction to hashing passwords
Once an application has the hashed version of the password stored, any time a user tries to login by typing in their password on the login page, the application will grab the inputted password, convert it to its hashed value, and compare that hash value to the hash value stored in the database.
If they match, that means the user typed in the correct password. If they don’t match, that means the user typed in an incorrect password.
So if you were to gain access to the hash value in the database, again, you can’t reverse engineer it into giving you the original password. You can only try to generate matching hashes, and if you find a password that generates the stored hash value, then you will be able to authenticate.
Trying to crack hashes of passwords, as long as they are strong hashes, would take such a long time (even with the most powerful computers in the world), that it becomes impractical. That’s why cryptography offers protection. If it would take someone 1,000 years to crack a hash (or even encryption, for that matter), then there’s no point at all.
However, people came to realize that they could use something called Hash Tables and Rainbow Table Attacks to try and expedite this process.
By the way, this article is pulled directly from one of our lessons in Cybr’s CompTIA Security+ SY0-601 Course where we provide you with all of the knowledge you need to pass your certification exam.
Hash Tables and Rainbow Table Attacks
Both hash tables and rainbow tables are databases that contain pre-computed hash values of either the most commonly used passwords, or of passwords from dictionary lists. Attackers create or use them to try and crack hash values from leaked databases.
The main difference between hash tables and rainbow tables is that with hash tables, our job is done once hash values have been computed. This means hash tables are less computationally intensive to create and use than rainbow tables, but they require significantly more storage space because they store every possible hash value.
Rainbow tables go further than simply storing all possible hash values. Once hash values are computed, further computing is required to organize similar hashes into chains so that only the first and the last element of each chain is needed.
This requires significantly less storage space than regular hash tables because we are not saving every single hash but at the expense of requiring far more computational power to create the tables and to compare hashes against the tables.
Despite their differences, they both provide benefits over traditional brute force attacks or even dictionary attacks, since they both could crack hash values much faster.
Once the tables are generated, a lot of it is already pre-computed, and your computer only has to search and compare values in the tables.
The downside of rainbow table attacks
The downside of this approach is that computing the rainbow table or hash table is computationally very expensive and takes a very long time. You also need to compute different tables for each various hashing algorithm (SHA1, MD5, etc). Both approaches also require significantly more storage than simply storing dictionary lists.
Rainbow tables and hash tables also have one main weakness: they can work great for hashes that haven’t used something called a salt.
Salting refers to adding an additional string of characters to the password before a hash is calculated. For example, if my password were:
Instead of simply hashing that passphrase, I could use a salt like: salt5396 added in front of the user’s password…so:
That value then runs through the hash function.
This approach is beneficial to preventing attacks like rainbow table attacks for a few reasons:
- Without knowing what the salt values are, an attacker wouldn’t be able to compute a rainbow table
- Even if the attacker were to get their hands on salt values — especially if unique salts are used for each password instead of one main salt — then it would take a massive amount of time to compute rainbow tables, rendering the attack useless
- Salts can produce different hashes even if more than one user chooses the same password — that way, even if a password leaked, the attacker wouldn’t be able to figure out who all has the same password in a single database from the hash, since each hash would look different
Of course, in addition to salting, we need to make sure that we’re using strong hash functions. The current NIST policy (at the time of writing) on hash functions is for federal agencies to use SHA-2 or SHA-3.
Finally, as a recurring theme, we need to encourage our users to create strong passwords, which means longer passwords. Everything else we’ve mentioned can definitely help even with the weakest of passwords from being immediately cracked, but weak passwords can ultimately still be cracked.
If you combine a solid salting strategy with strong hashing and a long password, then you significantly increase the time and complexity required to perform password attacks.
There’s a lot more to learn about hashing, hash attacks, password security, and encryption as a whole, but understanding hash tables, rainbow table attacks, and why salting is a strong defense is important for both passing the Security+ exam, but also for creating more secure applications. Be sure to check out our other blog posts for more information.