How should I choose a difficulty factor for my password hashing function?

Question

Assuming that I'm doing password hashing properly and using bcrypt, scrypt or PBKDF2, how should I go about choosing an appropriate difficulty factor? i.e rounds for bcrypt, iterations for PBKDF2 and maxtime, maxmem or maxmemfrac for scrypt.

Also assume that the worst-case scenario will happen and my user's hashes and salt (and any application-salt or pepper. You know... worst-case.) will be leaked, either accidentally or deliberately.

I need to choose a value that is:

1. Easy enough for me.
2. Too hard for an attacker.

The first part is relatively easy. If I choose enough rounds to cause bcrypt to take 0.5 seconds, I can be sure that my users won't see a significant slowdown when they login. (In a web app anyway, 0.5 seconds is not very a long time.) I also know by testing a loop over that function that I can handle many more logins per minute than I am currently seeing. If the rate of logins I get increases, I can lower the number of rounds and migrate users over as each one logs in or I can wait for better, cheaper hardware. When I naturally get better, cheaper hardware in my upgrade cycle I can increase the rounds to compensate.

The question that's more difficult to answer is how hard is too hard for an attacker. Of course it depends on the value of the passwords to a particular attacker but for this question, assume no special value beyond the fact that most of these user/password combinations will work on other sites that actually have value.

If I change the number of bcrypt rounds so that it now takes 0.01 seconds instead of 0.5, has this changed the equation for the attacker so that the brute-forced password is now worth more than the cost to brute-force it? How can I know whether it has or not?

It seems this is fairly easy to calculate based on knowing the following:

1. How much a generic username/password pair is worth.
2. How much it costs to brute-force a hash of $hash_function with $difficulty_factor.

Since scrypt was designed to be memory-hard rather than CPU-hard, the answer to 2. will vary differently depending on algorithm. It's not a linear speedup as CPU/GPU speeds increase or RAM prices decrease.

Is there a place where can I find out the above information that is updated as new hardware becomes available?

The best resource I have found so far for the value of a password is blog posts by Brian Krebs such as this one and this one. For hashes cracked per second, it's the "Crack me if you can" contest at DEFCON. Hashes cracked per dollar would be nice.

Please ignore in your answers any algorithmic flaws in these algorithms. If one of those is found I would simply switch to one of the other alternative algorithms. I assume that if a flaw is found in any of these it will be all over the security news.

---

Just found over on Crypto.SE this table from the paper defining scrypt:

All I need is for that table to be updated every year.

Answer 1

Unfortunately, the wide variety of hardware prevents building tables like the one you want unless you first make a survey of all existing hardware architectures and the best bcrypt/scrypt/PBKDF2 implementations for that architecture. Even the table in the scrypt article is not what you want: it does not tell you how much it would cost for an attacker; it tells how how much it would cost for an attacker with the hardware and software the scrypt designer thought of when writing the article.

Such estimates do not scale up well, by the way. If I was an attacker faced with an attack cost estimated at 10 billions of dollars with available hardware, I would first invest one billion dollars into building a custom ASIC-based system which would be faster for that job. A PC is good at making pseudorandom RAM accesses, but not the best possible hardware for that, if only because there are a lot of other components in a PC, which are useless for an attack.

At least, for PBKDF2, since the computation maps to the underlying hash function with no memory access issues, you can use existing hash function benchmarks to get an idea (e.g. these ones).

---

That being said, all is not lost. You will not get accurate estimates of attack costs, but that does not mean that all you can do is wail, shrivel up and die. A first pragmatic method is to set up the iteration count as high as you can: set it to the highest value which does not make the normal login process intolerably slow. That way, you will not know if your security is good, but it will be as good as it can get. Which is a consolation.

The rest of the work will be on the users' side. After all, the difficulty factor in the password hashing is there to counteract Moore's law. However, at best, this is a match between the password entropy and the attacker's patience:

• The attacker's advantage is that he is richer, can buy dedicated hardware, and is patient: he can afford to spend one hour, maybe one day on cracking a high-value password; whereas the user will not tolerate waiting for more than one second when logging in.
• The defender's advantage is the password entropy.

Accounting for an efficiency factor of 1000 for the attacker (dedicated hardware, more dollars thrown at it) and a patience factor of 86400 (the attacker wants to succeed within a day, the user will not wait more than one second), then the password entropy must exceed 86 millions (aka a bit more than 26 bits) if the defender is to win the game. To raise the password entropy, there's only one way: educate, educate, and educate again. Don't try to enforce "password rules", they antagonize users rather instead of making strong passwords. Instead, provide a non mandatory password generator button, which produces passwords with, say, 40 bits of entropy, and explain to the users that using the button would be a very good idea.

Answer 2

Using your target hardware, I would select a cost that causes the algorithm to take about 1/10th of a second. Implement a delay after failed login attempts. It won't be cost-effective to brute force any password that isn't awfully chosen (e.g. the username, site name, "password"). The actual value you choose will depend on your target hardware.

Answer 3

1. algorithm speed doesn't matter if the passwords are weak.
2. if the password is in a dictionary, you're nearly instantly screwed
3. if the password is generated by a rule that's included with JtR or Hashcat, you're screwed a bit later ;)

Other than that, how many user/passwords are you storing? If you're only protecting one account (think a server with only the root account on it), then salting is moot.

How often are you forced to change passwords? If the difficulty of the password will force the attacker into a full character set, long password bruteforce, then you can make a decent approximation: NumberOfCombos/CrackSpeed=TimeToCrack

So if you have a 6 char long, completely random printable ASCII (95 symbols) that you can crack 100 per second of, then you have 95^6/100=233 years to rip through the entire keyspace.

However if you're using some algo that's fast (my GPU cracks a single, single round, unsalted MD5 at 8 billion/sec), and throwing some decent hardware at it, then you can crack that entire 6-char keyspace in about 90 seconds. Going to length 7 at the same charset extends the time to crack to >2hrs, and length 8 extends it to 9 days. So if you change your passwords every 90 days, that gives the attacker plenty of time to crack and use that length 8, charset 95 password.

The rule is simple, the bigger you make the charset and the longer you make the password, keyspace will grow at a ridiculous rate. Modern hardware and software makes cracking very fast, but you can mitigate the threat with salts/algos. The real killer is when you did not force the attacker into a bruteforce scenario. Dictionaries/rules/permutations/multi-word combination attacks are extremely efficient at finding non-random passwords.