Salting passwords compared to slow password hashing

October 24, 2011

When you're storing encrypted passwords, you can do two different things to ruin the life of an attacker who got your password hashes, or at least annoy them; you can salt your passwords in various ways and you can use a slow password hashing function. These two have different but complementary effects.

(I've talked about the effects of the various ways of salting passwords back in SaltingPasswords.)

Salting passwords reduces the payoff an attacker gets for making a single password guess. They slow down how fast an attacker can compromise a bunch of your accounts, but salts do not slow down how fast an attacker can compromise a specific account. Individually salted passwords with a fast hash function increase the time to mass compromises but do not necessarily increase the time to the first account compromise.

Using a slow password hashing function slows down how fast an attacker can make password guesses but by itself does nothing to reduce the payoff the attacker gets for making those guesses. If you have no salts you're vulnerable to rainbow tables, and if you just have a single site-wide salt every (slow) password guess can be checked against all of your users at once.

If you want to delay the time to the first account compromise, the worst situation is a fast password hash (like SHA1 or MD5) with at most a single site wide salt; an attacker can make very fast hash checks and all they need is some person to have a reasonably weak password. If you have per user salts with a fast hash, the attacker needs to get lucky by picking a user that used a weak password. How much luck they need depends on the password practices of your users; if most users choose weak passwords, the time to first compromise will barely budge between a site-wide salt and a per-user salt.

(If you want scary figures on how fast this can be done today, see How To Safely Store A Password.)

It's tempting to summarize this as that having good salting means that the attacker can't rapidly break lots of your users at once while having slow hashing means that they can't rapidly break any of your users, but it's not quite that simple. Even with slow password hashing, if you don't have per user salts and you have users who pick (very) weak passwords the attacker won't need to make very many slow password guesses in order to find a vulnerable account.

(Even with a slow hashing function it doesn't take too much time to try 20,000 to 30,000 guesses. That's almost certainly enough to find most seriously weak common passwords.)

(This entry was sparked by reading On cryptography and dogmas (via Hacker News). I wanted to fix some of this in my own head.)


Comments on this page:

From 92.24.4.157 at 2011-10-24 05:09:38:

#correction: complementary not complimentary -- mjray

By cks at 2011-10-24 08:22:13:

Oops. Thanks for noticing, and fixed now.

From 69.158.18.227 at 2011-10-24 19:07:15:

What people really should be doing is storing the SRP verifier (v)

   http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol

For a given username (u), you take the password (p) and a random salt (s):

   x = SHA1(s,p)
   v = g^x

Store u, s, and v. If someone gets your password file they'll basically have to break Diffie-Hellman public key exchange to get the value of "x", which isn't even the password. Breaking DH would be quite the accomplishment. :)

You don't even have to use the rest of the SRP protocol either; just have the code in your backend to do the verification to make sure that given a the salt, the entered password matches 'v'.

Written on 24 October 2011.
« Boiling frogs and PC performance
A reason not to automate: policy flexibility »

Page tools: View Source, View Normal, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Mon Oct 24 01:12:56 2011
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.