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?