Geez, Guys, Salt Your Hashes

LinkedIn confirms that they have had a breach, and PC World has a good discussion. Linkedn has certainly not been following best practices, though we've all seen stupider.

• Stupider: storing the user passwords. Any site that can come up with your current password is run by  bozos.

According to the PC World article, LinkedIn lost a file containing 6.5M hashed passwords. They used SHA-1 to hash the passwords. SHA-1 is not a great hash algorithm, with NIST recommending it be phased out, but that is not the problem here. The problem is that the the hashes were unsalted. This means that a brute force password guessing program can guess a password, hash it, and see how many hashed passwords it matches. People are bad at choosing passwords, so many passwords are used by multiple people.

Salting involves generating a random number for each password. Then the random number and password are concatenated, and then hashed. This means that 

1. most likely hashes will be unique, and
2. even if two hashes are the same, they almost certainly do not correspond to the same password.

For this to work, the random value (the salt) for each password must be stored with the hash, and then when a user logs in the hash and the salt are retrieved, the salt is added to the password the user types, and then the result is hashed. If it matches, the login attempt succeeds.

Thanks to NPR for reporting this and to PC World for explaining what happened.