Parameter choice for PBKDF2

Graham Steel
November 10, 2015

How many iterations, what salt and what hash function should I use with PBKDF2?

To answer this, we need to look a little at what password-based key derivation function (PBKDF)2 does, and how it works.

PBKDF2, standardised in RFC 2898 and PKCS#5, is a function for creating a cryptographic key from a password. It is the only such function currently appearing in NIST standards, hence it has seen widespread use.

The aim of the function is to create a key in such a way that dictionary attacks (where the attacker just tries a range of possible passwords) are unfeasible. To do this, PBKDF2 applies a pseudorandom function (PRF) to the password many times. This means that an attacker making a guess at the password will also have to apply the function many times to his guess. This increases the computation time needed to check each guess.

Additionally, the function can be given a "salt" parameter. The idea of this is to make each key derivation operation unique, so that an attacker cannot guess one password and then look for matches against a large number of derived keys. These properties mean PBKDF2 is used not just to produce a key to be used in a cryptographic protocol, but also to store passwords securely (by storing the derived keys).

A developer using PBKDF2 must choose parameter values for the salt, the PRF, and the number of iterations, i.e. the number of times the PRF will be applied to the password when deriving the key.

The specification suggests (in section 4.1) that the salt be (or contain) a 64 bit pseudorandom value. This makes collisions (i.e. occasions that two stored passwords use the same salt) unlikely. By the birthday paradox, we would expect a collision after 2^32 passwords, i.e. a little more than 4 billion.

The PRF mentioned in the specification is SHA-1, and in many libraries this is the only choice. However, using SHA-256 or SHA-512 has the benefit of significantly increasing the memory requirements, which increases the cost for an attacker wishing to attack use hardware-based password crackers based on GPUs or ASICs.

The recommended iteration count in the RFC published in September 2000 was 1000. Computing performance has greatly increased since then. Modern guides such as the OWASP password storage cheat sheet (2015) and the August 2016 NIST guidelines now also recommend a minimum of 10 000 iterations. NIST's detailed guide (Appendix A.2.2) recommends that the iteration count be "as high as can be tolerated while still allowing acceptable server performance".

Real-World Password Cracking

What are the consequences of a low iteration count?

Imagine we are restricted to using SHA-1 as our PRF, as is the case for example in PKCS#11 up to version v2.20. How long would it take a well-resourced attacker (i.e. with access to GPUs) to break an 8-character password?

First we have to estimate how much entropy or "randomness" there is in an 8-character password. An excellent paper by Kelley et al. from IEEE Security and Privacy 2012 found that when users are forced to choose a password following the "Comprehensive8" policy, "Password must have at least 8 characters including an uppercase and lowercase letter, a symbol, and a digit. It may not contain a dictionary word.”, the result is roughly 33 bits of entropy.

If, however, the password is a perfectly random combination of uppercase and lowercase letters, numbers and the 30 symbols on a US keyboard, we would expect 52 bits of entropy. Interestingly, the same result can be obtained by choosing 4 random words from the Diceware list.Second, we need to know how fast GPUs can calculate PBKDF2.

An article from April 2013 reports a rate of 3 million PBKDF2 guesses per second on a typical GPU setup. This includes calculating AES once for each guess (to see if the right key has been derived to decrypt a master key file), and it's now November 2015, so suppose conservatively we can apply Moore's law almost once since then (whether one can apply Moore's "law" to GPUs is doubtful), giving a very rough rule-of-thumb ability of 5 million guesses per second on typical GPU hardware.

The table below shows how long an attacker would take to cover the whole password space of a single salted hashed password.

Password complexity Entropy estimate (bits) 1000 iterations 10000 iterations
Comprehensive8 33 4 hours 46 minutes 47 hours
8 random lowercase letters 37 12 hours 5 days
8 random letters 45 123 days 3 years 5 months
8 letters + numbers + punctuation OR 4 random Diceware words 52 325 years 3250 years

Password complexityEntropy estimate (bits)1000 iterations10000 iterationsComprehensive8334 hours 46 minutes47 hours8 random lowercase letters3712 hours5 days8 random letters45123 days3 years 5 months8 letters + numbers + punctuation OR 4 random Diceware words52325 years3250 years

Conclusions

If you have to use PBKDF2, you should:

  • use a unique 64-bit salt for each password.
  • rather than SHA-1, use SHA-512 or if not SHA-256 if you can.
  • use an iteration count of at least 10000, more if you can do it "while still allowing acceptable server performance".

On this last point, note that execution speeds of PBKDF2 implementations vary widely. Using a faster implementation will allow you to run more iterations without slowing down your server. If you want to check that your developers are using cryptography securely everywhere in your applications, Cryptosense Analyzer can integrate into your CI/CD process and check for bad parameters, key management errors, randomness issues and other cryptographic mistakes.