You might remember the LinkedIn hack of 2012. Their password encryption was extremely poor, and it was easy for anyone who obtained the leaked password files to retrieve the original passwords. At the time it was announced that 6.5 million accounts had been compromised.
Actually, passwords are rarely encrypted (which implies they can be decrypted) – instead they are passed to a one-way mathematical function called a hash function, which produces a unique fixed-length set of characters called a hash or a digest. You can’t unhash a password from its hash – that’s why it is called a one-way function. The only way to work out the original password is to try different ones until you find one with a matching hash.
How does this work for authentication? When a user logs in, their password is hashed, and this hash is compared to the user’s stored hash (which was calculated when their password was first set up).
This sounds ideal – the actual passwords are never stored, and so if an attacker manages to obtain the password file containing all the details, they don’t have user passwords.
Unfortunately, it isn’t quite that simple. Tables of pre-calculated hashes for millions of common passwords can be used to retrieve passwords if the file containing the hashes can be obtained. These tables are known as rainbow tables. It is relatively trivial to run through the tables, and so simply hashing passwords is completely inadequate.
For this reason a salt – a random, non-secret value – is usually concatenated with the password before the hash is calculated. Because every user has a different salt, it is not feasible to use pre-calculated tables – there would need to be a table for every possible salt value. For salts to be effective, they must be as random as possible, and of adequate size – preferably at least 32 bits.
In the case of LinkedIn, salts had apparently not been used, and so passwords were easily retrieved. This was poor security practice indeed.
Data never dies
Since that time, LinkedIn improved its practices and claimed to have salted all its passwords. Unfortunately, on the Internet data lives on, and it has recently been announced that a further 100 million account details have been leaked from the original hack in 2012! LinkedIn has invalidated the accounts of affected users who have not changed their passwords since the 2012 breach.
This certainly protects (somewhat belatedly) the LinkedIn data of affected users, but given that most people re-use their passwords, any other account that uses the same password is at risk.
Key derivation functions
Hashing with salts is not the end of the story for securing passwords, however. Salts are helpful in slowing down the process of retrieving passwords from a password file, but they aren’t enough given the immense computing power of cheap hardware.
Instead, key derivation functions (KDF) should be used. KDFs use multiple iterations of a hash function (or similar) with a salt. Each salt is calculated from the previous iteration, and there may be thousands of iterations. To retrieve a password from the end result requires retrieving the result of each iteration sequentially. This means cracking an entire password file is orders of magnitude more difficult than cracking one that uses salted and hashed passwords.
Password encryption best practice
The terminology can be confusing. When people talk about hashed passwords, it might mean they are hashed without salts, hashed with salts, or they are using a KDF.
Hashing without salts is little different to no hashing at all, and is unacceptable. But hashing with salts, while making it more difficult for attackers, is still inadequate. KDFs are the only acceptable (i.e. relatively secure) way of storing passwords.