Can I dynamically calculate an appropriate number of iterations for PBKDF2 based on the system time, rather than using a fixed value?

Could you choose the number of PBKDF2 iterations based upon the system time?

I've heard a few people recommend that the number of iterations for PBKDF2 should be doubled every two years (starting with the recommended 1000 iterations in the year 2000 when PKCS #5 was released).

Theoretically at least, you could determine the ideal iterations through an equation based upon the current time. Perhaps something like:

year = <current time in years>
exponent = (year - 2000) / 2
iterations = 1000 x (2 ^ exponent)


Which would give a value of about 115,196 iterations at the time of writing.

Assuming that:

• The system clock can be trusted.
• The number of iterations is stored with the hash, so that hash verification is still possible.
• Safeguards are in place to stop the system attempting to hash with a ludicrous number of iterations.
• You continue to monitor the actual time taken to hash passwords on your specific hardware.
• You regularly upgrade hardware to keep up with the increasing performance requirements.
• You choose an appropriate underlying hash algorithm.

Would such a system be safe and practical?

-
One problem with your system is that is assumes performance will double every two years. I think it has already slowed down, and will get even slower in a few years. –  CodesInChaos Sep 12 '13 at 15:25
The typical formula I've seen is $64,000^{\text{today} - \text{2012-01-01}}$. But as I argue in my answer, formulae like this one should be used to calculate the minimum, and the correct approach is to benchmark. –  Stephen Touset Sep 13 '13 at 0:15

Of course you can - but as to whether or not it's a practical or advisable idea, I don't think so. It's not really prudent to implement crypto systems/protocols and assume that they'll be fine in 10 years.

Cryptography is a dynamic field that changes rapidly; algorithms get broken, hardware improves, governments try to undermine the field, and attacks only ever become more sophisticated. The only way to ensure the security of your system is to stay abreast of what's happening in the crypto/security world, and to adjust your system/protocol accordingly. For example, despite the recommendation of doubling PBKDF2 rounds periodically, many people in the community now recommend a memory-hard PBKDF like Scrypt instead, making PBKDF2 more or less redundant (although not quite, as it's used internally in Scrypt, and in systems where memory is not available).

Your proposal does have an upside though: a vast majority of security/crypto protocols get implemented and forgotten about. Look at the linked-in fiasco for example - at the time of designing the system, the architect may have (however erroneously) thought that a saltless sha1 hash of the user's password would be sufficient security. These days, the idea of a prominent website doing this is unthinkable (hopefully). So in this sense, your proposal does at least attempt to stay up-to-date, which in lieu of a static system, is better than nothing. However, I think that continuous scrutiny and a more "hands on" approach is preferable.

-

This is not a good approach.

The correct number of iterations to use for PBKDF2 is "as many as you can tolerate". This number is more or less fixed for a given piece of hardware (assuming it isn't overloaded). The kind of calculation you propose is useful for determining if you are meeting an effective minimum number of iterations.

The appropriate way to choose the number of iterations is to benchmark it. Many slow-hash libraries support this kind of calibration. Essentially, you perform a nominal number of iterations (say 10,000) and calculate how much CPU time (not wall-clock time) the hashing took. Divide the number of iterations by the number of CPU seconds it actually took (say 0.06s) to get a rate of hashes per second (in this case, 166,666Hz). Now multiply by the amount of time in seconds you're willing to tolerate the operation taking (say 0.5s). This gives you the iteration count you should use (in this case, 83,333).

If this number is smaller than the minimum number recommended for the year (I've heard 64,000 in 2012 and doubling every two years), then you may need beefier hardware.

-

Your idea and algorithm look plausible to me. The round number increase according to Moore's Law. Twice the performance every two years is a conservative but good estimation. By the way you should add a comment to the code that explains the rational. Future developers will be very grateful.

You should keep in mind that every extra round makes it harder to crack passwords but makes it also easier to DDoS your service. After all PBKDF2 consumes lots of CPU resources. scrypt is even more problematic. It's designed to require more memory, too.

Almost 120k rounds are a bit excessive, though. I'm using a library that suggests 64k rounds for PBKDF2-SHA-1 and 12k rounds for PBKDF2-SHA512. These days I would start with SHA256 or SHA512 as pseudo-random function. You need fewer rounds for the same CPU time and the key space is large (32 or 64 bytes instead of 20).

Further more I like to suggest two modifications to your code.

1) Instead of a fix and linear growth you could measure the performance of your current hardware. At startup your applications measure the run time of the key derivation function and increase the round count by 5,000 (or so) until you reach a good value. clock_gettime(CLOCK_PROCESS_CPUTIME_ID, res) gives you good resolution. Of course you need to make sure that the round count is within a sane margin.

2) When an user logs into your site, compare her password hash's round count with the current round count. If the value is lower than upgrade the password information with an increased round count. After all it's the only time you have access to the unhashed password.

-
KDF's can be computed client-side (this is not often done, mostly due to lack of web scripting language support for cryptography and in that the authentication protocol is a bit different) so DDoS is a non-issue. 12k rounds is too low these days. Modification 1 is well-intentioned, but this is really a bad idea, you have no control of the hardware (however outdated it may be) and this will probably cause more problems than it will solve. Modification 2 is good (it's the standard way of updating password hashes). –  Thomas Sep 12 '13 at 22:22
Are you seriously suggesting client-side KDF? People invest time and knowledge to implement a side-channel free login verification system with a constant-timing comparison function and you want to give the salt away for free? That doesn't strike me as a good idea. 12k rounds of PKBDF2 with HMAC-SHA-512 take about 30 to 40ms on a recent machine. 100k rounds of SHA-1 finish in about half a second. That's far too much for a busy service. –  Tiran Sep 13 '13 at 12:33
@Tiran: Why not give the salt away? It's not like salts are supposed to be secret, anyway. Or, if you do want to include a "secret salt", you can always have a second KDF pass (which need not be slow) on the server with a different salt. (That's actually a good idea anyway, since you don't want to store password-equivalent tokens, like the client-side KDF output, unhashed in the database.) Really, doing key stretching on the client side is an excellent idea, it's just not very widely used yet. –  Ilmari Karonen Sep 13 '13 at 13:05
It's a good idea to treat the salt value as carefully as the output of the key derivation function. Public knowledge of the salt values make side channel attacks a bit easier. You really want to give away as few information as possible. Even the timing of a database query like "does login exist" can be used against you. –  Tiran Sep 13 '13 at 14:26