Using hashes and variable salts to protect passwords from fairly determined attackers

To make it even harder to recover passwords from hashes, we're going to force the attacker to create a brand new dictionary for every single password he wants to attack. We do this by using a variable salt instead of a fixed salt. We simply choose some property of the user whose password we want to protect and use that as the salt. For example, we might use the user's numeric primary key, or perhaps the username.

You can see that with this scheme there is no single dictionary that will support the attack. The attacker has to create a new dictionary for each password. The attacker has to have much more patience and be much more determined in order for this attack to work, because now the work is linear in the number of users instead of constant. Of course, the attacker can make his job easier by attacking only a subset of the users or else by focusing on some subset of the dictionary words, but in general the computing problem is more intensive (even though no more difficult logically speaking).

When choosing a property to use as the salt, take care not to choose something that might change. If, for example, you were to choose the user's e-mail address and the user subsequently changed the e-mail address, then the user would suddenly lose the ability to log in.

Our defenses are getting beefier and beefier, but still it's not entirely unlikely that somebody with enough patience and determination could crack our passwords. Can we make it even harder?

Using key strengthening to protect passwords from strongly determined attackers

There's a trick we can use called key strengthening or key stretching. The idea is to increase the time associated with recovering any given password so as to increase the amount of patience and determination required on the part of the attacker. It's simple to implement. Take the initial password + variable-salt combination (you could use a fixed salt too, but as we saw above, variable salts turn a constant-time problem into a linear-time problem), hash it iteratively some large number of times—say 1,000 times—and store the final result in the password database. The exact number of iterations is strongly dependent on the environment; you want the number of iterations to be small enough that it doesn't impact legitimate end users in a meaningful way when they try to log in (they shouldn't have to wait more than a second or two), but large enough that if you try to hash an entire dictionary, you're going to be waiting an awful long time. If you have lots of end users and logins, you also have to be careful that you don't introduce too much CPU load on your system since hashing is compute-intensive. (It's easy enough to imagine building out a compute farm if you really intend to get this serious about storing passwords securely.)

Can this scheme be broken? Yes, of course. But once again we've narrowed the circle of folks who are going to attempt it. Most attackers are going to look for a much easier target. Bad for the easier targets but good for you.

Summary

In this article we've considered a series of increasingly sophisticated techniques for protecting your user passwords from attackers. As often happens with engineering, it's important to recognize that there's a tradeoff you're confronting here—you have to decide how to balance simplicity against security. If you're trying to protect passwords for an academic department's website, it's probably overkill to use key stretching. If on the other hand you're trying to protect financial data, key stretching may be only the starting point for you.

It's important to recognize that security isn't a black-or-white affair. As it does in this case, it usually involves understanding where your likely threats are and then taking measures to protect against those, and perhaps even against threats that are even a little less likely but still plausible.

Good luck!

Post a comment