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.

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) recommend 10 000 iterations. NIST’s own guide (Appendix A.2.2) recommends that the iteration count be “as high as can be tolerated while still allowing acceptable server performance”.

*Update August 2016* New NIST guidelines now also recommend a minimum of **10 000 iterations** (sec 5.1.1).

### Cracking Stuff

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 |

### 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.

In a future blog post, we’ll cover other password hashing functions like bcrypt, scrypt, and the winner of the recent password hashing competition, ARGON-2.