Password-based key derivation↑

A password-based key-derivation function (PBKDF) accepts a password as input and generates a cryptographic key for use in encryption, authentication, or other cryptographic purposes. It is specifically designed to compensate for the typically low entropy of passwords. NIST recommends PBKDF2, standardized in RFC 2898 and PKCS#5.

Detailed description↑

Passwords or passphrases are often used as a convenient means of deriving cryptographic keys. However, using a passphrase as a cryptographic key is risky because passwords usually are not sufficiently random. In practice, this means passwords are vulnerable to dictionary attacks, where attackers systematically try passwords based on their frequency of use. Additionally, cryptographic primitives typically guarantee security only when used with random keys, meaning using passwords as cryptographic keys can compromise the entire cryptographic protocol.

To mitigate these risks, a password needs to be passed through a dedicated PBKDF before being fed into any other cryptographic algorithm. In addition, PBKDFs need to be used to store passwords. Instead of storing passwords in plain text, the PBKDF output should be stored and compared during authentication.

PBKDFs are essentially slow, salted hash functions. That means, a salt—a random string—is added to the password input of the hash function to slow down brute-force search attacks enough to make them uneconomical. More concretely, it forces an attacker to target each password with a dedicated brute-force attack instead of simply pre-computing common (password, PBKDF output) pairs and checking against this table. The salt provides domain separation between users and does not need to be kept secret. Given that PBKDFs take in user passwords, it is often not critical that they run as fast as possible. Put differently, if a PBKDF runs for 100 milliseconds, this slowdown is barely notable to a user, but slows down a brute force attack considerably. Of course, this comparison is premised on the assumption that the PBKDF implementation relied upon by a server and by an adversary run in a comparable amount of time.

A common design principle used for PBKDF is to repeatedly apply a so-called “pseudorandom function” (PRF) for many iterations using the password as the key.
A PRF is a function that takes a random key and an arbitrary other input and outputs a string that is indistinguishable from random.

PBKDF choices and alternatives↑

The only PBKDF currently approved by NIST is PBKDF2, standardized in RFC 2898 and PKCS#5. 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 RFC 2898 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 bound, we would expect a collision after a bit more than 4 billion passwords. It is advisable to pick a larger salt of at least 128 bits, which has very little additional computational cost but prevents this potential attack vector effectively.

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

The current NIST Guidelines suggest a minimum of 10,000 iterations of the PRF. As of May 2023, OWASP’s Password Storage Cheat Sheet recommends 600,000 iterations and the use of HMAC-SHA-256.

A modern PBKDF is the Argon2 family of password-hashing functions. As of May 2023, OWASP’s Password Storage Cheat Sheet recommends the use of “Argon2id with a minimum configuration of 19 MiB of memory, an iteration count of 2, and 1 degree of parallelism.”

In some settings, “peppering” may be used to enhance password security. Refer to the OWASP guide for details.

The strongest protection for applications relying on passwords is provided by deploying an oblivious PRF.¹ Refer to RFC 9497 for an introduction. However, the use of OPRFs introduces additional interaction between a server and a client, are not yet standardized by the IETF and efficient instantiations are only known from assumptions that are not secure against quantum computers.²