4

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.

7

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 = 2128 for random 16-byte salts), then risk of a salt reuse remains low as long as s2 is small with regards to n. Basically, with 16-byte salts, chosen randomly from a good PRNG, you have room for about 264 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, 264 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...).

  • With collision I was referring to the (unlikely) situation where an attack on one salt/hash pair yields another string than the password for which this works, but due to the multiple hashing might stem from a different chain of hashes that would no longer happen to end up in the same value if the salt were changed; and the salt could of course only be changed on login / password change. Anyway, your point about salt reuse is spot on I guess – Tobias Kienzler Oct 18 '13 at 14:42
  • As an example to what I mean with collision, take a primitive two round salted hashing. Now the password password might result in the chain CA34 -> DE21 for salt 23, while another string "§$%&a"§ would via 43AC -> DE21 also succeed in login. But now the salt is changed to 42, and the new chain of password is BEEF -> CAFE, while for the previous collision, "§$%&a"§, it is 125C -> DE3A, failing. Is such a scenario thinkable or is it absolutely impossible? – Tobias Kienzler Oct 18 '13 at 14:47
  • 3
    Such "collisions" should occur only with negligible probability, unless your password hashing function is very poor and weak. Moreover, any "salt changing" here would create as many collisions as it removes (in your example, changing the salt from 23 to 42 may remove a collision, but may also add a new one), so this is rather neutral. – Tom Leek Oct 18 '13 at 14:52
  • True, though that would mean an attacker would have unnoticed access to your account only for a limited time with the "wrong" password instead of until you (or they...) change it. And I'm not so sure a sufficiently good password/phrase wouldn't result in a brute-force attack to yield a simpler password that only collides for a specific salt - related: How big is the risk of hash fixed points/cycles? and Should hashing hashed hashes colide or not? – Tobias Kienzler Oct 18 '13 at 15:04
0

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.