225

I'm curious if anyone has any advice or points of reference when it comes to determining how many iterations is 'good enough' when using PBKDF2 (specifically with SHA-256). Certainly, 'good enough' is subjective and hard to define, varies by application & risk profile, and what's 'good enough' today is likely not 'good enough' tomorrow...

But the question remains, what does the industry currently think 'good enough' is? What reference points are available for comparison?

Some references I've located:

  • Sept 2000 - 1000+ rounds recommended (source: RFC 2898)
  • Feb 2005 - AES in Kerberos 5 'defaults' to 4096 rounds of SHA-1. (source: RFC 3962)
  • Sept 2010 - ElcomSoft claims iOS 3.x uses 2,000 iterations, iOS 4.x uses 10,000 iterations, shows BlackBerry uses 1 (exact hash algorithm is not stated) (source: ElcomSoft)
  • May 2011 - LastPass uses 100,000 iterations of SHA-256 (source: LastPass)
  • Jun 2015 - StableBit uses 200,000 iterations of SHA-512 (source: StableBit CloudDrive Nuts & Bolts)
  • Aug 2015 - CloudBerry uses 1,000 iterations of SHA-1 (source: CloudBerry Lab Security Consideration (pdf))

I'd appreciate any additional references or feedback about how you determined how many iterations was 'good enough' for your application.

As additional background, I'm considering PBKDF2-SHA256 as the method used to hash user passwords for storage for a security conscious web site. My planned PBKDF2 salt is: a per-user random salt (stored in the clear with each user record) XOR'ed with a global salt. The objective is to increase the cost of brute forcing passwords and to avoid revealing pairs of users with identical passwords.

References:

  • RFC 2898: PKCS #5: Password-Based Cryptography Specification v2.0
  • RFC 3962: Advanced Encryption Standard (AES) Encryption for Kerberos 5
  • PBKDF2: Password Based Key Derivation Function v2
Antonio
  • 113
  • 4
Tails
  • 2,438
  • 3
  • 14
  • 10
  • 3
    A global salt doesn't add any extra protection against rainbow tables. If you're using the global salt to prevent offline cracking attempts, you may want to [consider using an HMAC](http://security.stackexchange.com/questions/19243/should-password-hashes-be-encrypted-or-hmaced) instead. Also, consider using bcrypt or scrypt instead of PBKDF2-SHA256, since they are designed with the explicit purpose of slowly hashing passwords. – Stephen Touset Aug 26 '12 at 07:34
  • 1
    Obligatory note for everyone coming here: Nowadays you should seriously consider using better key stretching algorithms than PKBDF2 as it is highly parralisable. Consider [Argon2](https://en.wikipedia.org/wiki/Argon2) as the latest thing (winner from 2015), or scrypt or so. – rugk Nov 02 '18 at 18:46
  • 1
    The per user salt already protects against revealing identical passwords, as well as protecting against rainbow table attacks. Using a global salt is pointless. Using ONLY a global salt does not protect against revealing identical passwords, but would provide some level of protection against a rainbow table attack. The table could be rebuilt using the global salt, but it's a space and time tradeoff that probably isn't worth the effort. I agree with using bcrypt or scrypt instead of pbkdf2, because they're slower. – Craig Tullis Apr 12 '21 at 06:37
  • A modern machine kitted out with 8 current generation GPU's will calculate on the order of 9 billion SHA-256 hashes per second, or about 777 Trillion hashes per day, and those GPU's can perform rules based dictionary attacks. – ModernMachine Jun 19 '12 at 15:48

4 Answers4

264

You should use the maximum number of rounds which is tolerable, performance-wise, in your application. The number of rounds is a slowdown factor, which you use on the basis that under normal usage conditions, such a slowdown has negligible impact for you (the user will not see it, the extra CPU cost does not imply buying a bigger server, and so on). This heavily depends on the operational context: what machines are involved, how many user authentications per second... so there is no one-size-fits-all response.

The wide picture goes thus:

  • The time to verify a single password is v on your system. You can adjust this time by selecting the number of rounds in PBKDF2.
  • A potential attacker can gather f times more CPU power than you (e.g. you have a single server, and the attacker has 100 big PCs, each being twice faster than your server: this leads to f=200).
  • The average user has a password of entropy n bits (this means that trying to guess a user password, with a dictionary of "plausible passwords", will take on average 2n-1 tries).
  • The attacker will find your system worth attacking if the average password can be cracked in time less than p (that's the attacker's "patience").

Your goal is to make the average cost to break a single password exceed the attacker's patience, so that they do not even try. With the notations detailed above, this means that you want:

v·2n-1 > f·p

p is beyond your control; it can be estimated with regards to the value of the data and systems protected by the user passwords. Let's say that p is one month (if it takes more than one month, the attacker will not bother trying). You can make f smaller by buying a bigger server; on the other hand, the attacker will try to make f bigger by buying bigger machines. An aggravating point is that password cracking is an embarrassingly parallel task, so the attacker will get a large boost by using a GPU which supports general programming; so a typical f will still range in the order of a few hundreds.

n relates to the quality of the passwords, which you can somehow influence through a strict password-selection policy, but realistically you will have a hard time getting a value of n beyond, say, 32 bits. If you try to enforce stronger passwords, users will begin to actively fight you, with workarounds such as reusing passwords from elsewhere, writing passwords on sticky notes, and so on.

So the remaining parameter is v. With f = 200 (an attacker with a dozen good GPU), a patience of one month, and n = 32, you need v to be at least 241 milliseconds (note: I initially wrote "8 milliseconds" here, which is wrong -- this is the figure for a patience of one day instead of one month). So you should set the number of rounds in PBKDF2 such that computing it over a single password takes at least that much time on your server. You will still be able to verify four passwords per second with a single core, so the CPU impact is probably negligible(*). Actually, it is safer to use more rounds than that, because, let's face it, getting 32 bits worth of entropy out of the average user password is a bit optimistic; on the other hand, not many attacks will devote dozens of PC for one full month to the task of cracking a single password, so maybe an "attacker's patience" of one day is more realistic, leading to a password verification cost of 8 milliseconds.

So you need to make a few benchmarks. Also, the above works as long as your PBKDF2/SHA-256 implementation is fast. For instance, if you use a fully C#/Java-based implementation, you will get the typical 2 to 3 slowdown factor (compared to C or assembly) for CPU-intensive tasks; in the notations above, this is equivalent to multiplying f by 2 or 3. As a comparison baseline, a 2.4 GHz Core2 CPU can perform about 2.3 millions of elementary SHA-256 computations per second (with a single core), so this would imply, on that CPU, about 20000 rounds to achieve the "8 milliseconds" goal.


(*) Take care that making password verification more expensive also makes your server more vulnerable to Denial-of-Service attacks. You should apply some basic countermeasures, such as temporarily blacklisting client IP addresses that send too many requests per second. You need to do that anyway, to thwart online dictionary attacks.

gps
  • 103
  • 3
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 1
    Just an idea: Could one do like ~20k rounds on the client PC and than 1k on the server? If an attacker would start by guessing "normal passwords", he would still have to do 21k rounds. And if he'd start with keys, he'd only need to do 1k rounds, but the entropy should be much higher. Am I missing something? Seems like a good solution to me. – cooky451 Dec 04 '12 at 17:16
  • @cooky451: you can do that, but that can be hard to configure. Clients can use a wide variety of hardware, some of which very feeble when it comes to computing. Also, in a Web context, this means Javascript, and you will not get a lot of iterations out of a _Javascript_ implementation of PBKDF2 (it _would_ work much better with a Java applet, but that's yet another can of worms). – Thomas Pornin Dec 04 '12 at 17:24
  • 2
    I don't understand how you got to 8ms in your example. If f=200, p=30 * 24 * 60 * 60 * 1000?, n=32 . Then v is 241ms? I transformed 1 month to millis. Not sure what I am doing wrong. Thanks for the answer – José F. Romaniello Aug 26 '14 at 21:12
  • It does come out to 241ms. In fact, if you plug 8ms into the formula, you get approximately 23 hours out as "attacker patience". Which is a whole lot less than a month (for a single 32 bit entropy password)... And low enough where the recommended value of 8ms should likely be raised. – ircmaxell Sep 10 '14 at 15:20
  • Here's a quick script for benchmarking PBKDF2 (note: time is reported in seconds): https://gist.github.com/sarciszewski/a3b1cf19caab3f408bf8 – Scott Arciszewski Jan 16 '15 at 01:14
  • I agree with your assessment, with one clarification: the number of iterations should not be based upon how long it takes *your* hardware to perform the operation. It needs to be based upon the amount of time an *attacker's* hardware can perform the operation. If you have weak hardware, that's not a good excuse for choosing `iterations=1`. Your long explanation goes on to describe this in a reasonable way, but your up-front conclusion is "as much as you think is okay in your environment". It really should be "whatever it takes to thwart an attacker in his environment." – Christopher Schultz Oct 04 '16 at 20:39
  • We're upgrading the encryption in our existing app. However, having a high iteration will cause a massive performance hit as our system sometimes has to deal with encrypting/decrypting thousands of entries. So it seems as if we will have to use a very low iteration value -- probably no more than 1,000. So the question I have is should we even bother with a value that low? Why not just go with '1'? – Jake Shakesworth Aug 26 '19 at 19:28
  • @JakeShakesworth, you could scale wide by dedicating a machine (or VM, or cluster) on the server side to passwords, and making async calls. – Craig Tullis Apr 12 '21 at 06:39
38

Run openssl speed on the command line to get an idea of how fast message digest functions are. I can calculate about 1.6 million sha256 hashes a second or about 145 Billion guesses per day on my quad core 2.2ghz sandy bridge. If someone has a password that is in the English dictionary and used one round of sha256 then it would take longer to load the word list off the disk than to iterate over the list to break the hash. If you did PKBDF2-SHA256 with a a few hundred thousand rounds it would take a few few minutes to break. Enforcing a strong password policy helps, a lot.

The real answer: How much time do you have to burn?

rook
  • 46,916
  • 10
  • 92
  • 181
20

Thomas' answer provides a helpful baseline model and data. But the goal that he posits doesn't make sense to me. A typical attacker won't know your iteration count until after actually hacking the site and grabbing the database of hashes. Having done that, they won't move on just because you use a large iteration count. They'll try to crack as many as they can, and quite possibly publicize the hashes so others will continue trying to crack them for years to come with more and more powerful hardware. So "p" and "f" will both continue to increase long after the hack.

Also, real user passwords aren't well modeled by a complexity measure like 32 bits of entropy. The article Reusable Security: New Paper on Password Security Metrics is helpful in this regard, and documents what we've long known: many users pick easy-to-guess passwords, and there is a long tail. This also means attackers will always find some if they try hard enough.

I'd say that a more likely goal would be to protect as large a percentage of your users as possible from having their passwords cracked. E.g. table 4.2.1 of the PDF shows that if you managed to limit your attacker during some attack campaign from an average of 1 million attempts per hash down to 500,000 attempts, you might protect the passwords of 5% of your users (assuming a mix with more 7-character passwords than 8+ character passwords, thus reducing the cracked percentage from 35% to 30%). Of course the exact shape of the curve and where they are on it will vary widely.

So I'd just go for the maximum iteration count that you can budget for, so long as it doesn't delay real users doing normal logins. And you should increase the value as your compute capacity grows over the years.

nealmcb
  • 20,544
  • 6
  • 69
  • 116
-1

Build a simple calibration function that will calculate how much it takes to calculate X iterations, run it during app startup if that's feasible and set iteration count accordingly but not smaller than X (minimum count - a safe margin).

This works really well for on-premise web applications where you can set the target execution time to be 30 or 50ms. This will future-proof your app, but be aware of the safe margin - when app is started on a busy server, it can go down to this number so set it accordingly. Also keep in mind you will end up with passwords hashed with different iterations (so you need to store iteration count too).

Also one big warning: PKBDF2 does not use SHA-256 it uses HMAC-SHA-256 and that is a bit different. Do your testing, these numbers can be misleading!

lzap
  • 99
  • 2
  • 1
    This doesn't answer the question. The whole point of the question centers around what the "minimum count" might be. And why a dynamic calculation? That's a weird optimization to make when the iterations are there to make *offline* hashes slow. – schroeder Jan 27 '22 at 21:40
  • The point is to calculate it dynamically, that is the answer to the problem. This is actually the only good enough way to do it. – lzap Feb 02 '22 at 13:08
  • Remember that the number of iterations can only be chosen at hashing time - if your hardware frequently changes, you can re-hash the password each login, but that starts to turn into a lot of effort & complexity just to keep the number of iterations dynamically tuned. – Dev May 04 '22 at 19:42