PBKDF2
In cryptography, PBKDF1 and PBKDF2 (Password-Based Key Derivation Function 1 and 2) are key derivation functions with a sliding computational cost, used to reduce vulnerability to brute-force attacks.[1]
PBKDF2 is part of
Purpose and operation
PBKDF2 applies a
When the standard was written in the year 2000 the recommended minimum number of iterations was 1,000, but the parameter is intended to be increased over time as CPU speeds increase. A
Having a salt added to the password reduces the ability to use precomputed hashes (
Key derivation process
The PBKDF2 key derivation function has five input parameters:[9]
- DK = PBKDF2(PRF, Password, Salt, c, dkLen)
where:
- PRF is a pseudorandom function of two parameters with output length hLen (e.g., a keyed HMAC)
- Password is the master password from which a derived key is generated
- Salt is a sequence of bits, known as a cryptographic salt
- c is the number of iterations desired
- dkLen is the desired bit-length of the derived key
- DK is the generated derived key
Each hLen-bit block Ti of derived key DK, is computed as follows (with + marking string concatenation):
- DK = T1 + T2 + ⋯ + Tdklen/hlen
- Ti = F(Password, Salt, c, i)
The function F is the
- F(Password, Salt, c, i) = U1 ^ U2 ^ ⋯ ^ Uc
where:
- U1 = PRF(Password, Salt + INT_32_BE(i))
- U2 = PRF(Password, U1)
- ⋮
- Uc = PRF(Password, Uc−1)
For example,
- DK = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)
PBKDF1 had a simpler process: the initial U (called T in this version) is created by PRF(Password + Salt), and the following ones are simply PRF(Uprevious). The key is extracted as the first dkLen bits of the final hash, which is why there is a size limit.[9]
HMAC collisions
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:
- Password:
plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd
therefore, when using HMAC-SHA1, it is pre-hashed using SHA-1 into:
- SHA1 (hex):
65426b585154667542717027635463617226672a
Which can be represented in ASCII as:
- SHA1 (ASCII):
eBkXQTfuBqp'cTcar&g*
This means regardless of the salt or iterations, PBKDF2-HMAC-SHA1 will generate the same key bytes for the passwords:
- "plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd"
- "eBkXQTfuBqp'cTcar&g*"
For example, using:
- PRF: HMAC-SHA1
- Salt: A009C1A485912C6AE630D3E744240B04
- Iterations: 1,000
- Derived key length: 16 bytes
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 the hash of the password.[11]
Alternatives to PBKDF2
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 using application-specific integrated circuits or graphics processing units relatively cheap.[12] The bcrypt 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 slightly stronger against such attacks,[13] while the more modern scrypt key derivation function can use arbitrarily large amounts of memory and is therefore more resistant to ASIC and GPU attacks.[12]
In 2013, the Password Hashing Competition (PHC) was held to develop a more resistant approach. On 20 July 2015 Argon2 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 is Balloon hashing, which is recommended in NIST password guidelines.[15]
To limit a
See also
References
- ^ doi:10.17487/RFC3962. RFC 3962. Retrieved October 23, 2015.
- doi:10.17487/RFC2898. RFC 2898. Retrieved October 23, 2015.
- doi:10.17487/RFC8018. RFC 8018.
- ^ "Smartphone Forensics: Cracking BlackBerry Backup Passwords". Advanced Password Cracking – Insight. ElcomSoft. September 30, 2010. Retrieved October 23, 2015.
- ^ "LastPass Security Notification". The LastPass Blog. May 5, 2011. Retrieved January 31, 2023.
- ^ "Password Storage Cheat Sheet". OWASP Cheat Sheet Series. August 15, 2021. Archived from the original on January 23, 2023. Retrieved January 23, 2023.
- doi:10.17487/RFC8018. RFC 8018. Retrieved January 24, 2018.
- ^ Sönmez Turan, Meltem; Barker, Elaine; Burr, William; Chen, Lily. "Recommendation for Password-Based Key Derivation Part 1: Storage Applications" (PDF). NIST. SP 800-132. Retrieved December 20, 2018.
- ^ RFC 2898
- ^ Bynens, Mathias. "PBKDF2+HMAC hash collisions explained". mathiasbynens.be.
- ^ "Collision resistance - Why is HMAC-SHA1 still considered secure?". crypto.stackexchange.com.
- ^ a b Colin Percival. scrypt. As presented in "Stronger Key Derivation via Sequential Memory-Hard Functions". presented at BSDCan'09, May 2009.
- ^ "New 25 GPU Monster Devours Passwords In Seconds". The Security Ledger. December 4, 2012. Retrieved September 7, 2013.
- ^ "Password Hashing Competition"
- ^ "Digital Identity Guidelines Authentication and Lifecycle Management Section 5.1.1.2" (PDF). NIST. SP 800-63B. Retrieved June 18, 2021.
- S2CID 1977743.
External links
- "PKCS #5 v2.1" (PDF). RSA Laboratories. Archived from the original (PDF) on April 11, 2017.
- RFC 2898 – Specification of PKCS #5 v2.0.
- RFC 6070 – Test vectors for PBKDF2 with HMAC-SHA1.
- NIST Special Publication 800-132 Recommendation for Password-Based Key Derivation