Protecting the weak (passwords)

From @marshway:

Salting a fast hash function is like issuing life vests to the passengers of the Titanic.

This is an apt simile. I guess it requires some explanation for people less knowledgeable in the area of password security.

If a server uses passwords to authenticate users the server needs to store some value for each user with which to validate the password entered by the user.

Servers can be hacked - in which case this database of password values could fall into the wrong hands. Due to this servers don't store the password itself - they store a one-way cryptographic hash function of the password. So a hacker who obtains a password hash from the database can't figure out the actual password.

In theory that should be enough. The problem is that most actual passwords aren't random strings - they are chosen by humans, usually in a way that is easy to remember. Because of this crackers can (and have) produced relatively small dictionaries (with maybe a few million passwords) that contain the great majority of actual passwords used by people.

The crackers can also create a dictionary of hashed passwords of these most common passwords hashed with popular hash algorithms. So if a cracker gets a hashed password from a server they can simply look it up in this dictionary and find the password itself, thus overcoming the hash.

To prevent this servers "salt" the hashed passwords. Instead of a simply hashing each password with a single hash algorithm, which the crackers can then create a dictionary of hashed password for, the server uses a different hash function per password  This is done by hashing a few random bytes, called "salt", together with the password. This makes it impossible to prepare a single dictionary of hashed passwords that could be used to reveal many passwords in the server's database.

Sounds great. So why does @marshway say that "salting a fast hash function is like issuing life vests to the passengers of the Titanic"? Because these days computers are so fast that crackers can crack password hashes without creating a dictionary of hashed passwords. Instead they perform a "brute force" attack. For each hashed password in the database they take each password in the dictionary of most common passwords, hash it together with its "salt" and compare it to the hashed password in the database. When they find a match - they've found the password.

To prevent this kind of attack robust systems use a slow hash function such as PBKDF2, bcrypt or scrypt. These are hash functions that take such a long time to run that if the cracker needs to repeat the operation for each password in his dictionary it will make the attack so slow as to be infeasible. This technique is also known as key stretching.

Salting and key stretching are complementary solutions. Salting prevents crackers from producing a single dictionary of hashed password to crack all the passwords in a database. Key stretching makes it more difficult to crack specific hashed passwords.

So let's go back to @marshway's Titanic simile. If you use a very weak password (say one of the 100 most popular passwords - for example "password") then the fact that the server does salting and key stretching won't help you much. The cracker can go through all the hashed passwords in the database, hash each one of the top 50 passwords with the salt and compare to the hashed password. You're the Titanic passenger who was so weak you got a heart attack just from seeing the iceberg.

To the other extreme, if you use a very strong password (say a completely random 30 character string) you're safe even if the server doesn't use neither salt nor key stretching  As long as the passwords are hashed, no one is going to build a dictionary that will include your password. You're like Johnny Weissmuller on the Titanic - you can swim ashore without a life vest or a life boat.

If you use a fairly strong password, say a password that isn't on the top ten million passwords list but is on the top billion list, then salt will probably be enough to protect you, since the cracker is unlikely to try hashing a billion possible passwords with the hash to compare to your hashed password. Unless the cracker is specifically targeting you, in which case you're in deep trouble. This is like the extremely healthy Titanic passenger who could survive in the freezing water for hours as long as a life vest would keep them afloat.

But the great majority of people are in a fourth group - they use passwords that are in the top 10 million list but not the top 10 thousand list. For these people salt isn't enough - if the server uses a fast hashing function, the crackers can simply try each one of these most popular passwords with each of the salts in the database. These are the majority of the Titanic passengers who couldn't survive in the freezing water and needed a life boat - or key stretching.

The extremely strong don't need protection - the extremely weak can't be saved. Security systems, like boats, are designed to protect the great majority of the people who are somewhere in the middle.