Storing passwords: why you should flavour your hash with salt
A cryptographic hash function is widely used to ‘encrypt’ stored passwords. Strictly speaking, it is not encryption: encryption is something you can scramble and then unscramble mathematically – it is two-way. A hash is one-way: it generates a meaningless output (often called a digest) that bears no relation to the input, and cannot mathematically be used to recreate that input. Other characteristics are that it always produces a constant length output regardless of the size of the input, and that no two different inputs will produce the same output.
These characteristics make the cryptographic hash ideal for the secure storage of passwords:
- the plaintext user password is neither stored nor can be recovered mathematically from the hash
- no two different passwords will create the same hash
- the fixed size makes storage simple.
So, when a user account is created, a user password is either created or selected by the user. It is run through the hash function, and a hash is generated and stored with the user name as part of the user account. The plaintext password is not stored and cannot be recovered from the hash.
The next time the user logs on to the account, he or she has to re-present the password. That password is run through the hash function again, and the hash output is compared to the one stored in the user’s account. If they match, access is granted. If they don’t match, access is refused.
If the server is breached and the password database is stolen, no matter, the passwords are securely and irreversibly scrambled. Right? Wrong.
The problem is that attackers have become adept at cracking hashes. It can’t be done mathematically, but it can be done by brute force. In fact any password can be cracked by brute force – brute force simply means that every possible combination of characters and symbols is tried until the correct one is found.
Generally speaking, this is a theoretical possibility rather than a practical reality: even with modern computing power, brute forcing all the possible combinations would take too long to be of any use.
But the attackers have adapted brute force into the so-called ‘dictionary attack’. Here, hashes for millions of the most likely passwords such as names, dates, places, combinations of them, l33t speak variants (h3110_w0R1d), and everyday words in multiple languages are pre-computed and stored in a table or dictionary. Now, instead of having to try every possible output against every possible input, the attacker merely has to take the output and compare it to the dictionary in order to locate the plaintext password. With a good dictionary attack, most passwords can be recovered from the hash in just a few seconds or minutes.
And this, finally, is why you should flavour your hash with salt.
Salt is a unique random string prepended to each plaintext password before the hash is generated and stored. “What the salt does,” Robin Wood, aka security researcher and pentester DigiNinja, told me, “is prevent an attacker generating a pre-computed list of the hashes.” Robin developed the widely used Pipal password analyser – and knows a thing or two about passwords.
The characteristics of the salt should be a reasonable length, and genuine randomness. Any old pseudo-random number generator isn’t good enough – it should be a cryptographically secure random number generator. (If you want to consider the effort that goes into a good random number generator, have a look at the independent report produced for Intel by Cryptography Research Inc on the Intel Ivy Bridge RNG.)
(Not everyone believes the salt needs to be truly random, just truly unique to each password. However, if it isn’t generated randomly, there is a danger that it becomes predictable.)
This salt is then added to the plaintext password and the hash generated by the combination. Ultimately it does nothing to prevent a brute force attack, so in this way doesn’t make the security stronger. But what it does do is defeat the dictionary attack. The dictionaries cannot contain all of the hashed standard passwords plus all of the possible hashes of each of those passwords with a large random number (or salt) included. Provided that the salt for each password is unique, it needs no security in itself – on its own it can tell you nothing about the plaintext password that is included in the stored, combined hash.
Unique salts also have the added advantage of creating unique hashes for every user, regardless of their plaintext password. In a Pipal analysis of “the list of passwords from the phpBB leak which I grabbed from the SkullSecurity site,” DigiNinja shows that the top two passwords are ‘123456’ and ‘password’ – and these are likely to figure highly in any list of passwords. Without a unique salt, it would be statistically likely that the most frequently occurring hashes have been generated from one or other of these passwords, even without the use of a dictionary. With unique salts, however, every single stored hash will also be unique, and no statistical analysis will be possible. A long and unique salt is thus important to prevent a standard salt being guessed or discovered by statistical analysis. If the attacker knows a standard salt, he could just precompute an additional dictionary with that added salt.
What this tells us is that the user must do two things: choose long, strong passwords to defeat dictionary attacks where the website doesn’t use salting; and never to reuse the same password on multiple accounts. Using the same password means that it is only as safe as the weakest account we use; and the simple fact is we do not know which websites are storing our passwords safely. It is also sobering to realise that the strength of the password we choose is meaningless if the website stores it in plaintext, and then gets breached.
For the website, it tells us that hashing passwords is essential; but on its own, hashing will not protect the majority of passwords from a dictionary attack.
The addition of a unique, long and genuinely random string appended to the password before hashing will provide a far greater defence against password cracking, without requiring any additional effort to secure or hide the salt itself.
Jeremi Gosney has demonstrated dramatically improved brute forcing with a cluster of GPUs running Hashcat: see GPU cluster can crack any NTLM 8-character hashed password in 5.5 hours