1

Scenario:

  • Cannot use previous 15 passwords
  • Using PBKDF2 with iterations targeting 1 second execution time

In this scenario, when a user wishes to create a new password, the server must combine that password with up to 15 salts from the previously used passwords. This means, worst case scenario, a user's password change would take about 16 seconds, significantly burdening the server.

How do I mitigate this stress? Reduce PBKDF2 execution time to something like 0.1s? Reduce the previously used password list?

2

From where is the "previous 15" requirement coming from? That seems unlikely to actually improve security much - my first step would be to reduce that if it's not coming from a legal, regulatory, industry, or auditing requirement.

  • An attacker doing an online attack won't notice at all
  • An attacker with your PW database doing an offline attack against just the current passwords won't care during the attack
  • More complex pattern-noticing analysis on the attackers part is too complex to go into here, but imagine a user who uses football1, then football10, football100, etc. The pattern's obvious if you have a few passwords, even if football100000000 might not be tried until until a very late stage of password guess (if at all, given how many hundreds of thousands of iterations you must be using)

Also note that trying N different PBKDF2 values at once means you can use multiple cores; i.e. for 15 PBKDF2 runs at 1s each, if you had 10 cores, this could take as little as 2 seconds (10 in the first second, 5 in the second second). You will be using the same (or slightly more) CPU time, though - watch out.

Reducing PBKDF2 execution time decreases security significantly, since at attacker has to do less work in the same proportion you do less work. If you can afford to target 1s of CPU time (presumably for fairly infrequent logins, or for a very hoss server farm), keep it! That will dramatically increase an attacker's workload at the same level it reduces yours; I don't recommend it.

If you're targetting one second of PBKDF2 work per login, then 15 users logging in at about the same time is exactly the same workload as any 15 other unique salt PBKDF2 operations - make sure you can afford your current target times under your expected peak load for the next 2-3 years. Also, how often will users be changing their passwords?

One other alternative:

  • Don't change a user's salt every time.
    • This is not a great idea, but can be done, and will solve your performance issue. However, offline attackers with the full password list will have 16x the chances to guess passwords for each try.
    • Only changing the salt every 2 to 6 password changes would strike a middle ground - it would be less bad if you have very, very frequent password changes.

P.S. You know you're going to get users using P@$$w0rd1, P@$$w0rd2, P@$$w0rd3, P@$$w0rd..., P@$$w0rd999, don't you?

  • Audit req's 10 previously used; we go 15 just to exceed audit req's. PBKDF2 + 1s target is IT decision, so those are more negotiable. The constant user salt is actually not a bad idea. I like the tradeoff. You have 16x chance to get a password; if it's old, you still have to get lucky with a forward transform to current password. – Travis Mar 4 '14 at 16:52
0

How about this: when you change passwords, ask for the old password (you do that anyway, right?) and then in addition to testing to see if the old password matches, ALSO re-hash the old password using a single iteration. Since it's no longer valid you don't care so much about how easy it is to crack (because cracking it doesn't help the attacker much). And then store the fast hash version in your history.

Sometimes you might not get the old password (say if changed by an admin) so you may want to put a marker in your old password field to indicate how it was hashed, that way your system is compatible with both variations.

  • 1
    This is dangerous if users use password patterns (which many will), because cracking the old passwords will hint at the current one. – Gordon Davisson Mar 4 '14 at 4:18
  • @GordonDavisson That danger is in inherent in the storing of old passwords. You're just tweaking the cost/benefit dial to suit your circumstances. Presumably though if you were the attacker and were going to decide how to allocate your thousands of CPU hours, you'd pick the target that wasn't guaranteed to be expired. – tylerl Mar 4 '14 at 6:04
  • I like this idea. We would definitely still use iterations.... maybe just 5k instead of 100k. So still slow, just not as slow. The only down side here is password resets -- in that case, we can't re-store the old password, so we'll still end up with many calculations that still run at our higher iteration count. – Travis Mar 4 '14 at 16:54
  • Note that what the attacker goes for depends on what they want. If they're actively trying to get into your network, then expired passwords are useful for finding patterns, but that's it. If they're simply finding passwords (for research, fun, to better their wordlist, or to publish the analysis of your password leak or breach), then the expired passwords are just as good any any other. In either case, at a 20:1 ratio a day and a half spent on the expired passwords is worth 30 days of current passwords, so it'd be valuable to spend at least some time on the expired ones to make a wordlist. – Anti-weakpasswords Mar 5 '14 at 2:02
0

What Travis did not say was what the overall purpose was of using the old passwords in the first place. I mean, audit might require it but nobody is saying WHY it is required. It's probably a bad idea. In general, it isn't going to increase security, and even aside from performance issues it runs the risk of significantly decreasing security if it isn't done right. It is far more likely to be done improperly than properly.

If the purpose is to ensure a "chain of possession" of the account, there are other ways you can do this, with very little performance loss.

Here's a simple example: if your pseudo-random number generator is any good in the first place, an XOR of any number of salts should be just exactly as random as any single salt. No difference cryptographically whatsoever.

So you could take all the salts for that user (including the current one), XOR them all together, and use that as the actual salt when generating or authenticating the current password.

That establishes a clear and required history, it should not reduce your security any, XOR is extremely fast, and you still only have one call to PBKDF2.

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.