Assume a password storage scheme using a computationally-expensive hash algorithm and a CSPRNG salt. User ID, salt, and hash value are stored in a table; if the table is compromised, all three values are available to an adversary.

Is there any value in computing a new salt when a user changes his password? (I think this question only makes sense if the adversary has before and after copies of the password table, but I could be very wrong about that.)

-
Independent of the rest of the question, salts should always change when a password is changed. –  Stephen Touset Sep 4 '14 at 21:32

If the attacker had already begun creating a rainbow table or is engaged in some other attack which requires knowledge of the salt, then a password change with a salt change will require the attacker to start from scratch.

Always assume the attacker has before and after copies of the password hash and salt.

If the salt is not changed, any work the attacker has done may still be applicable to the new password. It may even mean the new password is already in the rainbow table or has been cracked in some other way.

-
And vice versa: attacking the new password shouldn't allow the adversary to simultaneously attack the old one, which in the real world may still be used for other accounts. –  otus Sep 4 '14 at 10:49
If a different salt is used for each account, creating a rainbow table would be stupid: it won't work, and it'll be inferior to straightforward exhaustive search. Basically, rainbow tables already don't work (they don't provide any speed-up over exhaustive search) if you use random salts, even if you don't change them. So the purported advantages listed in this answer are not actually advantages of changing the salt... –  D.W. Sep 4 '14 at 17:36
@D.W.: supposing that it's feasible to store a rainbow table, and supposing further that a full exhaustive search takes time T, and I change my password every time T/100, it seems to me like if I change the salt at the same time then the rainbow table is useless and I have a 1% chance of each password getting cracked. If I don't change the salt at the same time then the rainbow table is useful and I have a 1% of the first password being cracked, 2% the second, and so to 100% the 100th since after that time the attacker has a full table for my salt. Whether this is a practical attack... –  Steve Jessop Sep 4 '14 at 18:12
A rainbow table may also be made to target one specific high value target account, especially if the attacker knows the salt doesnt change... –  Richie Frame Sep 4 '14 at 19:38
@SteveJessop, if the account has a high-quality salt, a rainbow table is useless regardless. (I've noticed there's a lot of misconceptions out there about rainbow tables... They are cool, but they are not magic -- they do have limitations.) It's not correct to say that if you don't change the salt the rainbow table is useful. If your salt is unique there is absolutely no point in using a rainbow table. If the attacker knows the salt, the attacker might as well do exhaustive search; that's strictly better than a rainbow table. If the attacker doesn't know the salt, he has no hope. –  D.W. Sep 4 '14 at 20:14

If the existing salt is random (and chosen from a large enough space), there is little or no benefit to changing the salt each time the user changes their password. There's no downside -- you might as well change the salt each time the user changes their password; that is probably good practice -- but if you don't change the salt, it's unlikely that anything terrible will happen.

Changing the salt doesn't help stop rainbow table attacks, because there's nothing to stop. Rainbow tables already don't work if you have a random salt for each account (assuming the salt is chosen from a large enough space). Rainbow table attacks are about amortizing work across many different accounts; they're also about precomputation, where you do some work in advance before you know any of the password hashes. If you have a random salt for each account, it is likely that each account has a different salt, so there is no opportunity to amortize work across multiple accounts; thus, if each account has a different salt, rainbow attacks are useless -- they are no better than exhaustive search.

The scenario that password hashing is designed to mitigate is where the password database is breached and the attackers learn everything stored in it (all the salts, all the password hashes). Normally this happens once, at a single point in time. In this answer, I am assuming we are talking about mitigating that kind of threat; the threat of multiple password breaches is a mostly theoretical concern that's largely irrelevant. So, all that matters is what the value of the salt and password hashes at that point in time are. Past values don't matter, because the attacker won't get to see them (assuming the password database is breached once).

So, assuming you chose salts properly in the first place, there is not much reason to change the salt each time the user logs on. For any attack that can be done if you don't change the salt, there is a variant of that attack that's at least as fast and that can be done if you do change the salt.

Of course, if you were worried that your password database might get breached multiple times, the answer would be different: then re-using the same salt for the same account could help the attacker a bit, if the user has changed their password in between the two breaches. But if you think there is a significant likelihood that your password database might get breached, you probably have more serious problems, and maybe you need to do a lot more than tweak how you generate salts.

There is a good reason to change the password salts every time that the password database is breached. One way to accomplish this is to force users to change their password any time that the password database is breached, and write your code to change the salt each time a user changes their password. So, in some sense this is an indirect argument for changing the salt each time the user changes their password. But it's really only relevant if you think your password database might be breached multiple times.

Bottom line: if you are writing code to handle password changes, it would be reasonable to pick a new salt every time, because it's easy to do. But if you run across code that doesn't change the salt every time the user changes their password, don't panic; at worst, that's a low severity issue, and in practice, it probably doesn't matter much.

-
Suppose a user is known to switch passwords once a week, but choose them with only $k$ bits of entropy. An attacker with read only access to the database can create a hash table of all the $2^k$ $k$-bit passwords. Even if they don't have enough time to crack one password a week, they'll eventually break them all if the salt stays the same. If a new salt is used, they will have to start anew each week. –  otus Sep 4 '14 at 17:53
Suppose Alice has password "azerty" and an adversary compromises the password table. Adversary is focused on Alice for some reason and hashes the top 10,000 passwords with Alice's salt. If, while that is going on, Alice changes her password to "monkey" but the salt stays the same, the new hash will be in adversary's already-computed table. If the salt changes, adversary must start over. (I think that's what otus said, but without the superscripts, eh?) –  Bob Brown Sep 4 '14 at 19:30
@otus, I suggest you clarify the attack model. The normal attack model is: at some point in time, the password database is breached. At that point in time, the attacker learns the salt and the password hash at that single point in time. Normally the salts and password hashes are not public and so the attacker cannot observe their values before or after that point in time. So even if the user changes their password many times, the attacker won't get to see more than one password hash -- the password hash at the time when the database was breached. So this doesn't help the attacker. –  D.W. Sep 4 '14 at 20:17
@BobBrown, are you assuming the password database is breached twice, at two different points in time? That is very rare. –  D.W. Sep 4 '14 at 20:18
I don't suppose there are any good estimates out there of how often a password file is lost and the owner doesn't realise? I'm not sure how one would even start to research that, but it probably isn't orders of magnitude rarer than password files being lost and the owner does find out. So anything that should be done every time your password file is lost, should be done somewhat more frequently than every time you notice it's lost! Especially when, as you say at the start, there's no downside to omitting the assumption that there's only a single loss of the file. –  Steve Jessop Sep 4 '14 at 20:50

To sum up and expand on the previous answers and comments, if everything goes to plan salts may only need to be distinct, but in practice there are attacks that can be avoided by always generating a new salt whenever the password is changed.

1. If an attacker gets access to multiple different password hashes with the same salt (due to multiple compromises or e.g. the old hash still being in backups), they can attack those simultaneously in less time than otherwise expected. There are multiple reasons this is a bad thing:

• The old passwords may still have value. They may have been used by the user on other accounts, even if that's not good practice.
• Some users reuse parts of a password (or include a semi-secret "pepper"). Cracking the earlier password could then allow a faster attack on the new one.
2. If the attacker knows the salt, they can start a targeted attack before the user has even picked the password. This could come about due to an earlier compromise and a subsequent password change, or the salt could be public information (e.g. in some PAKE protocols). The attacker could then have done most of the work by the time they manage to compromise the password hash. By having the salt change on each password change you force the attacker to restart the attack whenever the user changes passwords.

Of course, these attacks are not possible with truly secure passwords of e.g. 100 bits of entropy. However, if you assumed that, you wouldn't need to use a slow password hash either. In practice many users will choose poor passwords and even those should be protected as far as practical.

-