Just add salt

LinkedIn.com recently experienced a security breach that exposed 6.5 million LinkedIn hashed passwords. While the thieves did not publish the user names that correspond to each password hash, there is no reason to doubt they have that information. One commentator claims he was able to crack 2 million of the 6.5 million passwords using an old PC with no graphics processor, and widely available software.  

The stolen hashed passwords were not protected by salt,  technique that stores a random number  (the "salt") with each password hash. The salt is incorporated into the hash along with the user's password. This forces an attacker to crack each password separately, rather than cracking them all at once or using widely-available precomputed tables containing the hashes of common passwords.

Last week Vicente Silveira of LinkedIn posted a blog entitled "An Update On Taking Steps To Protect Our Members." While LinkedIn is to be commended for responding quickly in public, there are some details in that blog that I'd like to comment on.

Silveira says LinkedIn has notified users whose passwords they think may be at risk and says they don't believe others are at risk, but does not say what the basis for that assurance is. More concrete info from LinkedIn would be helpful.

He goes on to advise users who have not been contacted that "it is good practice to change your passwords on any website you log into every few months."  This has to be the silliest "I screwed up,  but it it's your fault" blame shifting ever. Hint: no one does this and no one ever will. It's like telling people whose credit card numbers have been stolen that they should have been getting new credit cards every few months anyway. 

Finally, the blog reports "We have built a world-class security team here at LinkedIn including experts such as Ganesh Krishnan, formerly vice president and chief information security officer at Yahoo!, who joined us in 2010. … Under this team’s leadership, one of our major initiatives was the transition from a password database system that hashed passwords, i.e. provided one layer of encoding, to a system that both hashed and salted the passwords, i.e. provided an extra layer of protection that is a widely recognized best practice within the industry. That transition was completed prior to news of the password theft breaking on Wednesday."

Salt is not "best practice," it's de minimis security these days, but at least the "world-class team" got the importance of salt and made it a "major initiative."

So what took them so long to implement this vital security measure? 

Converting an unsalted hashed password system to a salted system should be an afternoon's work for a good security programmer. Ok, I understand, this is a production system for a major Internet presence. So they'll need design reviews, code reviews, unit testing, some forensic work to make sure no programmer pokes into the password file instead of using the proper authentication calls, full-up tests, etc., etc. So bump that afternoon to a month's work with a small team. But surely not two years?

What to do

For other enterprises that are storing unsalted hashes,  here is a simple way to convert the entire password database:

Let's say the current system has a password file indexed by user name that for each user stores H(userpassword), where H is whatever hash algorithm is currently in use.  This entry is stored at account creation and whenever a user changes their password. 

We create a new file, indexed the same way, with entries: 

           version,  salt, Hnew (salt, H(userpassword)).

* salt is a random number generated for each user. It should be at least a 32,bit value, with 64 bit preferable. While high quality random numbers are generally needed in security applications, salt is one exception. All that is needed is that the value be distributed reasonably uniformly over the size of the salt field, so the likelihood of multiple passwords having the same salt is small. 

* Hnew is a high quality, cryptographic hash, such as a member of the NIST secure hash algorithm family. SHA1 is probably good enough, but since this is a new design, I would suggest SHA512.  If SHA3 is released before you act on this, it should be a good choice. 

*version is just a number (e.g. 2) so you can switch to a different algorithm in the future-- this is just good database practice. 

As long as the original hash, H, produces a wide enough output, 128 bits should be fine, 64 bits so so, the new hash plus salt will eliminate the threat of parallel attacks or rainbow tables. For extra credit, use a key strengthening hash such as PBKDF2 or scrypt.