The Importance Of Salted Hashes

After the security breach that resulted in LinkedIn, eHarmony and Yahoo Voices users having their password hashes being published, there has been talk about storing passwords with salts. What does this mean?

We have to understand how passwords are stored. Let's look at how the passwords were stored in the LinkedIn system. When user Alice created her account, she entered a password. This password was not directly stored in the database, which would be very insecure. Instead, first the servers at LinkedIn ran it through a hashing algorithm. This is a mathematical function that is very easy to compute in one direction, and theoretically impossible to compute in the opposite direction. Hashes are also known as "one way functions". Let's say Alice chose the password 'alice123'. The system would take that text and hash it and the output would look like this: 1d7f38a7d716ccf48a9bf9fbb76d67d5. The system would then store that result in the database. The next day, when Alice tries to log in, she will type in her password, and the system will then hash her password attempt to get a hashed output. The system will then take the stored password hash and compare that hash to the attempted password hash. If they match, then Alice is allowed. The purpose of hashing the password is to keep the password safe while it is stored in the database. If the database was stolen, the clear text version of the users password would not be known.

So if that is the case, then why is the LinkedIn situation such a large problem? Well, there is a technique called brute forcing which can be used to discover what the actual password is. This technique involves hashing lots of potential words and phrases and then comparing that output to the hashes that one might have on hand. In this case, 6.5 million hashes. Current computing power allows an individual to generate 100,000 hashes per second. So each attempted hash can be compared to the database of published hashes and if the is a match, you then know the password.

While we can't stop brute forcing, we can make it harder. That's where the salt comes in. Just like with French fries, salt makes a good thing better. When Alice creates her account in a salted password system, the system generates some random data we call "salt". It takes the salt at adds it to the password ( salt + Alice123 ) and hashes that. When it stores the hash, it puts the salt in front of the hash. Now, the next day when Alice attempts to log in, she puts her password in, and the system looks up her hashed password and separates the salt from it, and adds it to the attempted password, then hashes it. At that point, it compares the stored salted hash, with the attempted salad hash. If they match, then Alice is authenticated and allowed in.

How is this different? Well for one individual user there is no difference. A brute force attack against one salted hash is no different than the previous brute force description. The brute force program would extract the salt, and use that salt in the process of hash generation. Where the gain in security comes from is in situations like LinkedIn. Without salt, one hash generated can be used to compare against the entire database of users. With a salted hash, it can only be compared to a hash with an identical salt. This increases the number of hashes that need to be generated exponentially. As an example, to brute force a 7 character password with a possible 69 characters, one would potentially need to generate 7.5 * 10^12 hashes. With the addition of salt to the password, this grows exponentially by the amount of salt added.

As you look at your security systems, you should be looking at how you store your passwords. If you can add salt, you should. At some point, that might not be enough. Computing power will only increase. At one point in time hashing was enough, and we felt safe. We can learn from this. We should always be evaluating our security on a regular basis and checking to make sure that it is not gotten out of date with the technology that is available.