On 6 June 2012, LinkedIn confirmed the reports that it had been subject to a large-scale password compromise, with. hackers posting a file online that contained millions of “encrypted” passwords. Why “encrypted” in quotes? This posting explains why and, in doing so, how passwords can be safely stored.
If a password is stored in an encrypted format, then it implies it can be decrypted – so long as you know the key. In fact, the LinkedIn passwords were stored in what is known as a “hashed” format, specifically SHA-1 (which stands for “Secure Hashing Algorithm”). You can think of SHA-1 like a mathematical car crusher in a scrap-yard. Whether you feed in an Aston Martin DB9 or a Citroen CV, what you get out is a mangled blob that looks absolutely nothing like what you put in. And just like a car crusher, hashing is an irreversible process – there’s no way you can take that compacted lump of metal, plastic and electronics and turn it back into a car. The output of SHA-1 if you feed it the word “password” looks like this: 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8. If you make just a small change, by making the first letter a capital P so that the word is now “Password”, SHA-1 produces 8be3c943b1609fffbfc51aad666d0a04adf83c9d, which is wildly different (but the same length). No matter what you feed into SHA-1, the output is always the same length. The LinkedIn database contained millions of these hashes instead of storing the actual passwords in “clear text”.
Now comes a key question: if there’s no way to reverse a hash into its corresponding password, why does the hacker posting matter? To answer this question, consider a more practical question: how does LinkedIn know that you’ve entered the right password when you log in? When you enter your username and password, the clear text password is hashed and compared to the stored hash: if it’s the same, the password is correct. That’s how things work normally. Hackers can attack these hashes in a similar way: they guess a password, hash it and compare that hash to the one they’ve stolen. If it’s the same, the guess is correct; if it’s not, try another guess! Clearly this can be a lengthy process, even with a computer programme working on the problem. But if you think about it, all this guesswork can be done in advance. Just make lots of guesses, hash them and store both parts in a table – what is known as a “rainbow table”. The structure of a rainbow table is too complex for this article but in essence, you simply look up the stolen hash in the table to find the password that generated it.
To date, some 3.5 million of the 6.5 million stolen hashes have been cracked in this way. But this technique will only work for a particular password if that password was one of the guesses made while compiling the table – and that is why LinkedIn users with strong passwords should still be safe. But what is a strong password? From a sample of approximately 160,000 cracked passwords that we have seen, the average length was 8.9 characters, and 21% contained a mixture of uppercase, lowercase and numbers. These statistics suggest a number of passwords might be considered “strong” but, when it comes to rainbow tables, attackers have time on their side: there are computers running right now all across the globe dedicated to producing these tables.
LinkedIn’s response to the breach included “salting” passwords. A typical salt is a large random number chosen when a user sets a password. That number is prefixed to their password before running the whole lot through the hashing algorithm, and both the salt and hash are then stored (ideally, in different places). Rainbow tables depend on the fact that all the hard work can be done in advance. If the hash is partly generated from a random number, rainbow tables can’t be produced because for every password guess the table must take into account every possible value of salt. Game over.
Salting is just one of numerous techniques to defeat rainbow tables and slow down attacks on hashes. It’s important to realise, however, that salting doesn’t make hashes immune to cracking. If the salts are compromised along with the hashes, the attacker can revert to the first technique: guess a password, prefix it with the stolen salt, hash the lot and compare with the stolen hash. For more information on secure password storage, start by visiting: https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet.
To find out how to ensure your data is secure through advanced penetration tests, or for more information about related training courses for your organisation, contact us now.