Would re-salting passwords regularly in-/decrease security?

Question

What are the (dis)advantages of re-salting a user's password regularly, e.g. weekly (or at their next login once week since the last re-salting)?

The basic idea would be that users who regularly log in would suffer a lower risk of someone exploiting a hash collision after somehow obtaining the salt and hash, since most likely only the actual password would still work after re-salting; however I wonder if re-salting would actually make life easier for an intruder who manages to regularly obtain the new salt and hash and, assuming the actual password was not modified, could somehow use that history to reduce the keyspace.

Answer 1

Hash function collisions are not relevant to password hashing. All the password hashing works on preimage resistance, not collisions. You can forget everything about collisions when talking about password hashing.

Salt "collisions" may matter but are better called "salt reuse". You avoid salt reuse by using big enough random salts (16 bytes are enough; GUID are good salts).

You cannot change the salt without having access to the password. If you could do it, then the attacker could do it too, and nullify the benefits of the salts. This would be a serious weakness of the hashing function.

There is no point in changing the salt. The salt unique added value is how it is different from other salt values. There is no gain in replacing a salt value with another value; there can be a net loss if the new value happens to be equal to another salt value, leading to salt reuse.

Namely, when you use random salts, you are ensuring absence of salt reuse heuristically: if you ever generate s salts, in a space of size n (e.g. n = 2¹²⁸ for random 16-byte salts), then risk of a salt reuse remains low as long as s² is small with regards to n. Basically, with 16-byte salts, chosen randomly from a good PRNG, you have room for about 2⁶⁴ salt generation instances. If you change salts regularly, more often than strictly required, then you are increasing s, i.e. diminishing your breathing room. Fortunately, 2⁶⁴ is a huge number, so assuming that you do everything else properly, then replacing salts every week (when the user logs in, because you cannot do that without the password itself) will not imply a significant extra risk. It will be useless, but harmless.

If, from multiple hash values with various salts and the same password, the attacker can work out the password itself or reduce its key space (with better success than the simple risk of salt reuse explained above), then this is a cryptographic weakness of the password hashing function. No such weakness is known for usual password hashing functions (bcrypt, PBKDF2...).

Answer 2

As pointed out by Tom Leek above, there is no point in resalting if you use a "simple" salted hash.
Which you shouldn't do, given that rigs with a dozen or so GPUs can brute force in the tens to hundreds of billions [1] of hashes per second nowadays, and you can't expect a user password to have much more than 30-40 bits of entropy (if you are really lucky). 40 bits is 10.9 seconds at 100 G/s.

However, you can actually increase security by "resalting", if you (hopefully) use a slow key derivation/stretching scheme such as scrypt or PBKDF2 rather than simple salted hash.

Instead of (for example) 1,000 iterations, you would do 1,000+N iterations, and increment N after a successful login, with a rate limit (say, once per day at most).
That way, you need to keep track of one extra value (N) per user, but you can update ("resalt") the hashed password for almost free, using a single additional iteration, and without having to know the original password!
Note that the salt is technically not changed (though you could if you wanted, e.g. if you appended N to the salt) but it's the same net result as using a different salt, since the number of iterations is different.

It would be possible to increment N by the number of days since last login, too (if you keep track of that), so users who only log in once every week or once every two weeks will on the average have the same security margin.

The computional effort of the key derivation function thus adapts over time, accounting for faster cracking hardware becoming cheaper with time. 1,000 iterations become 1730 iterations after two years. The cost of updating all the hashes in the database is amortized over logins and is very low (practically zero).