Salting passwords compared to slow password hashing
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.)