Salt – Preventing Rainbow Attacks against Password Stores

Introduction

In my article about cryptographic hash functions I mentioned that hash functions often are used to store passwords in the database. Today I would like to spend a little more time on how to store passwords securely.

Password Lists

It has become a common place to read in the news about this or that website being hacked. Such news usually contain the advice to change your password, not only on the hacked site, but on every other site where you might have used a similar password. Why is that the case?

Well, most of us are still humans and therefore have a limited capacity for remembering passwords. However, the number of places we need to authenticate with is ever growing. That leads to most people using the same password in more than one place. Because of that, it is lucrative for criminals to spend some effort on creating a list of email addresses, login names and passwords. With that information, they are able to logon to other services like your bank and cause some real damage.

Many websites still make it very easy for intruders to compile such a list because they do store passwords in clear text. Using a cryptographic hash function to hash the password before storing it makes it a little harder for criminals to compile that list. However even a hashed password list is not a high hurdle to overcome.

Rainbow Tables

With storage prices as low as they are it is easy for an attacker to pre-calculate the hash values of millions of common passwords. A list of password hashes like this is called a rainbow table. (Actually, a rainbow table is a little more complex than just a list of pre-computed hashes to save some storage space, but for the purpose of the article that detail is not relevant.)

Such a pre-computed hash table allows an attacker to quickly scan through the list of stored password hashes to retrieve matching passwords and their account names and email addresses. An attack using this method is called a Rainbow Attack. There is however a simple way to make this type of attack infeasible: Salting your passwords.

Salt for the Password Soup

A Salt is a random string that is appended to the value we want to hash (the password) before the hash function is applied. The salt does not need to be secret. However, it must be unpredictable and reasonable long. Unpredictable means, it is not derived from the password itself and it is different for each stored password. A CSPRNG is a good choice for generating your salt values. The salt must be stored together with the hashed password, as you will need it during authenticating requests.

Because a password now turns into completely different hash values depending on the salt, to still be able to use a rainbow table the attacker would have to create one table for each possible salt value. With 12 bits of salt (used by early Unix systems) that would mean 4096 different tables. That is actually quite achievable on modern storage devices. However, with for example 64 bits of salt this will be impossible for quite a while. Never the less, there are security experts recommending to use a salt at least as long as the resulting hash value, so for example 512 bits for the SHA2_512 algorithm.

Additional Measures

While a salt effectively prevents the use of a rainbow table, it does not make it in any way more difficult to attack a single password hash. To achieve that, the hash function itself has to be made computationally more expensive. While a user will most likely not notice, if the authentication takes an additional half second, an attacker who on average has to test tens of millions of possible passwords before a match is found, can now only test about 173 thousand passwords in a day (on a single thread). Two common passwords hashing methods that are designed to use a salt and be computationally expensive are bcrypt and PBKDF2. PBKDF2 is for example used to store passwords in WPA2 Wi-Fi routers.

Summary

Decrypting large password lists is a very lucrative business for criminals, as most users reuse the same password across many sites. When you have to store passwords, always use a cryptographic hash function on the password concatenated with a random salt, before storing it anywhere. If done correctly, this will effectively prevent large-scale attacks employing rainbow tables against your password list.