Incryptography,PBKDF1 andPBKDF2 (Password-Based Key Derivation Function 1 and2) arekey derivation functions with a sliding computational cost, used to reduce vulnerability tobrute-force attacks.[1]
PBKDF2 is part ofRSA Laboratories'Public-Key Cryptography Standards (PKCS) series, specifically PKCS #5 v2.0, also published asInternet Engineering Task Force's RFC 2898. It supersedes PBKDF1, which could only produce derived keys up to 160 bits long.[2] RFC 8018 (PKCS #5 v2.1), published in 2017, recommends PBKDF2 for password hashing.[3]
PBKDF2 applies apseudorandom function, such ashash-based message authentication code (HMAC), to the inputpassword orpassphrase along with asalt value and repeats the process many times to produce aderived key, which can then be used as acryptographic key in subsequent operations. The added computational work makespassword cracking much more difficult, and is known askey stretching.
While the recommended minimum number of iterations was 1,000 when the standard was written in the year 2000, the parameter is intended to be increased over time as CPU speeds increase. AKerberos standard in 2005 recommended 4,096 iterations;[1]Apple reportedly used 2,000 foriOS 3, and 10,000 foriOS 4;[4] whileLastPass in 2011 used 5,000 iterations forJavaScript clients and 100,000 iterations for server-side hashing.[5] In 2023,OWASP recommended to use 600,000 iterations for PBKDF2-HMAC-SHA256 and 210,000 for PBKDF2-HMAC-SHA512.[6]
Having a salt added to the password reduces the ability to use precomputed hashes (rainbow tables) for attacks, and means that multiple passwords have to be tested individually, not all at once. The public key cryptography standard recommends a salt length of at least 64 bits.[7] The USNational Institute of Standards and Technology recommends a salt length of at least 128 bits.[8]
PBKDF2 has five input parameters:[9]
where:
EachhLen-bit blockTi of derived keyDK, is computed as follows (with+ marking string concatenation):
The functionF is thexor (^) ofc iterations of chained PRFs. The first iteration of PRF usesPassword as the PRF key andSalt concatenated withi encoded as a big-endian 32-bit integer as the input. (Note thati is a 1-based index.) Subsequent iterations of PRF usePassword as the PRF key and the output of the previous PRF computation as the input:
where:
For example,WPA2 uses:
PBKDF1 had a simpler process: the initialU (calledT in this version) is created byPRF(Password +Salt), and the following ones are simplyPRF(Uprevious). The key is extracted as the firstdkLen bits of the final hash, which is why there is a size limit.[9]
PBKDF2 has an interesting property when using HMAC as its pseudo-random function. It is possible to trivially construct any number of different password pairs with collisions within each pair.[10] If a supplied password is longer than the block size of the underlying HMAC hash function, the password is first pre-hashed into a digest, and that digest is instead used as the password. For example, the following password is too long:
plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmdtherefore, when using HMAC-SHA1, it is pre-hashed using SHA-1 into:
65426b585154667542717027635463617226672aWhich can be represented in ASCII as:
eBkXQTfuBqp'cTcar&g*This means regardless of the salt or iterations, PBKDF2-HMAC-SHA1 will generate the same key bytes for the passwords:
For example, using:
The following two function calls:
PBKDF2-HMAC-SHA1("plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd",...)PBKDF2-HMAC-SHA1("eBkXQTfuBqp'cTcar&g*",...)
will generate the same derived key bytes (17EB4014C8C461C300E9B61518B9A18B). These derived key collisions do not represent a security vulnerability – as one still must know the original password in order to generate thehash of the password.[11]
One weakness of PBKDF2 is that while its number of iterations can be adjusted to make it take an arbitrarily large amount of computing time, it can be implemented with a small circuit and very little RAM, which makes brute-force attacks usingapplication-specific integrated circuits orgraphics processing units relatively cheap.[12] Thebcrypt password hashing function requires a larger amount of RAM (but still not tunable separately, i.e. fixed for a given amount of CPU time) and is significantly stronger against such attacks,[13] while the more modernscrypt key derivation function can use arbitrarily large amounts of memory and is therefore more resistant to ASIC and GPU attacks.[12]
In 2013, thePassword Hashing Competition (PHC) was held to develop a more resistant approach. On 20 July 2015Argon2 was selected as the final PHC winner, with special recognition given to four other password hashing schemes: Catena,Lyra2,yescrypt and Makwa.[14] Another alternative isBalloon hashing, which is recommended inNIST password guidelines.[15]
To limit abrute-force attack, it is possible to make each password attempt require an online interaction, without harming the confidentiality of the password. This can be done using anoblivious pseudorandom function to performpassword hardening.[16] This can be done as alternative to, or as an additional step in, a PBKDF.
