PBKDF2

Last updated

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]

Contents

PBKDF2 is part of RSA Laboratories' Public-Key Cryptography Standards (PKCS) series, specifically PKCS #5 v2.0, also published as Internet 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]

Purpose and operation

PBKDF2 applies a pseudorandom function, such as hash-based message authentication code (HMAC), to the input password or passphrase along with a salt value and repeats the process many times to produce a derived key, which can then be used as a cryptographic key in subsequent operations. The added computational work makes password cracking much more difficult, and is known as key stretching.

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 Kerberos standard in 2005 recommended 4,096 iterations; [1] Apple reportedly used 2,000 for iOS 3, and 10,000 for iOS 4; [4] while LastPass in 2011 used 5,000 iterations for JavaScript 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]

Algorithmic representation of the iterative process of the Password-Based Key Derivation Function 2. Pbkdf2 nist.png
Algorithmic representation of the iterative process of the Password-Based Key Derivation Function 2.

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 US National Institute of Standards and Technology recommends a salt length of at least 128 bits. [8]

Key derivation process

The PBKDF2 key derivation function has five input parameters: [9]

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

where:

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 xor (^) of c iterations of chained PRFs. The first iteration of PRF uses Password as the PRF key and Salt concatenated with i encoded as a big-endian 32-bit integer as the input. (Note that i is a 1-based index.) Subsequent iterations of PRF use Password as the PRF key and the output of the previous PRF computation as the input:

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, WPA2 uses:

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:

therefore, when using HMAC-SHA1, it is pre-hashed using SHA-1 into:

Which can be represented in ASCII as:

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 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 brute-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 an Oblivious Pseudorandom Function to perform password-hardening. [16] This can be done as alternative to, or as an additional step in, a PBKDF.

See also

Related Research Articles

<span class="mw-page-title-main">HMAC</span> Computer communications hash algorithm

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.

In computing, Internet Protocol Security (IPsec) is a secure network protocol suite that authenticates and encrypts packets of data to provide secure encrypted communication between two computers over an Internet Protocol network. It is used in virtual private networks (VPNs).

A passphrase is a sequence of words or other text used to control access to a computer system, program or data. It is similar to a password in usage, but a passphrase is generally longer for added security. Passphrases are often used to control both access to, and the operation of, cryptographic programs and systems, especially those that derive an encryption key from a passphrase. The origin of the term is by analogy with password. The modern concept of passphrases is believed to have been invented by Sigmund N. Porter in 1982.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

<span class="mw-page-title-main">Key derivation function</span> Function that derives secret keys from a secret value

In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES. Keyed cryptographic hash functions are popular examples of pseudorandom functions used for key derivation.

There are a number of standards related to cryptography. Standard algorithms and protocols provide a focus for study; standards for popular applications attract a large amount of cryptanalysis.

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

The Secure Real-time Transport Protocol (SRTP) is a profile for Real-time Transport Protocol (RTP) intended to provide encryption, message authentication and integrity, and replay attack protection to the RTP data in both unicast and multicast applications. It was developed by a small team of Internet Protocol and cryptographic experts from Cisco and Ericsson. It was first published by the IETF in March 2004 as RFC 3711.

HMAC-based one-time password (HOTP) is a one-time password (OTP) algorithm based on HMAC. It is a cornerstone of the Initiative for Open Authentication (OATH).

In cryptography, CRAM-MD5 is a challenge–response authentication mechanism (CRAM) based on the HMAC-MD5 algorithm. As one of the mechanisms supported by the Simple Authentication and Security Layer (SASL), it is often used in email software as part of SMTP Authentication and for the authentication of POP and IMAP users, as well as in applications implementing LDAP, XMPP, BEEP, and other protocols.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.

The following outline is provided as an overview of and topical guide to cryptography:

BLAKE is a cryptographic hash function based on Daniel J. Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with round constants, is added before each ChaCha round. Like SHA-2, there are two variants differing in the word size. ChaCha operates on a 4×4 array of words. BLAKE repeatedly combines an 8-word hash value with 16 message words, truncating the ChaCha result to obtain the next hash value. BLAKE-256 and BLAKE-224 use 32-bit words and produce digest sizes of 256 bits and 224 bits, respectively, while BLAKE-512 and BLAKE-384 use 64-bit words and produce digest sizes of 512 bits and 384 bits, respectively.

HKDF is a simple key derivation function (KDF) based on the HMAC message authentication code. It was initially proposed by its authors as a building block in various protocols and applications, as well as to discourage the proliferation of multiple KDF mechanisms. The main approach HKDF follows is the "extract-then-expand" paradigm, where the KDF logically consists of two modules: the first stage takes the input keying material and "extracts" from it a fixed-length pseudorandom key, and then the second stage "expands" this key into several additional pseudorandom keys.

In cryptography, scrypt is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914. A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after.

In cryptography, PKCS #8 is a standard syntax for storing private key information. PKCS #8 is one of the family of standards called Public-Key Cryptography Standards (PKCS) created by RSA Laboratories. The latest version, 1.2, is available as RFC 5208.

In cryptography, the Salted Challenge Response Authentication Mechanism (SCRAM) is a family of modern, password-based challenge–response authentication mechanisms providing authentication of a user to a server. As it is specified for Simple Authentication and Security Layer (SASL), it can be used for password-based logins to services like LDAP, HTTP, SMTP, POP3, IMAP and JMAP (e-mail), XMPP (chat), or MongoDB and PostgreSQL (databases). For XMPP, supporting it is mandatory.

In cryptography, a pepper is a secret added to an input such as a password during hashing with a cryptographic hash function. This value differs from a salt in that it is not stored alongside a password hash, but rather the pepper is kept separate in some other medium, such as a Hardware Security Module. Note that the National Institute of Standards and Technology refers to this value as a secret key rather than a pepper. A pepper is similar in concept to a salt or an encryption key. It is like a salt in that it is a randomized value that is added to a password hash, and it is similar to an encryption key in that it should be kept secret.

Argon2 is a key derivation function that was selected as the winner of the 2015 Password Hashing Competition. It was designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich from the University of Luxembourg. The reference implementation of Argon2 is released under a Creative Commons CC0 license or the Apache License 2.0, and provides three related versions:

References

  1. 1 2 Raeburn, Kenneth (2005). "Advanced Encryption Standard (AES) Encryption for Kerberos 5". tools.ietf.org. doi: 10.17487/RFC3962 . RFC 3962. Retrieved October 23, 2015.
  2. ↑ Kaliski, Burt (2000). "PKCS #5: Password-Based Cryptography Specification, Version 2.0". tools.ietf.org. doi: 10.17487/RFC2898 . RFC 2898. Retrieved October 23, 2015.
  3. ↑ Moriarty, Kathleen; et al. (2017). Moriarty, K (ed.). "PKCS #5: Password-Based Cryptography Specification, Version 2.1". tools.ietf.org. doi:10.17487/RFC8018. RFC 8018.
  4. ↑ "Smartphone Forensics: Cracking BlackBerry Backup Passwords". Advanced Password Cracking – Insight. ElcomSoft. September 30, 2010. Retrieved October 23, 2015.
  5. ↑ "LastPass Security Notification". The LastPass Blog. May 5, 2011. Retrieved January 31, 2023.
  6. ↑ "Password Storage Cheat Sheet". OWASP Cheat Sheet Series. August 15, 2021. Archived from the original on January 23, 2023. Retrieved January 23, 2023.
  7. ↑ Moriarty, Kathleen; et al. (2017). Moriarty, K (ed.). "PKCS #5: Password-Based Cryptography Specification, Version 2.1: Section 4. Salt and Iteration Count". tools.ietf.org. doi:10.17487/RFC8018. RFC 8018. Retrieved January 24, 2018.
  8. ↑ 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.
  9. 1 2 Password-Based Cryptography Specification RFC   2898
  10. ↑ Bynens, Mathias. "PBKDF2+HMAC hash collisions explained". mathiasbynens.be.
  11. ↑ "Collision resistance - Why is HMAC-SHA1 still considered secure?". crypto.stackexchange.com.
  12. 1 2 Colin Percival. scrypt. As presented in "Stronger Key Derivation via Sequential Memory-Hard Functions". presented at BSDCan'09, May 2009.
  13. ↑ "New 25 GPU Monster Devours Passwords In Seconds". The Security Ledger. December 4, 2012. Retrieved September 7, 2013.
  14. ↑ "Password Hashing Competition"
  15. ↑ "Digital Identity Guidelines Authentication and Lifecycle Management Section 5.1.1.2" (PDF). NIST. SP 800-63B. Retrieved June 18, 2021.
  16. ↑ Ford, W.; Kaliski, B. S. (2000). "Server-assisted generation of a strong secret from a password". Proceedings IEEE 9th International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET ICE 2000). pp. 176–180. doi:10.1109/ENABL.2000.883724. ISBN   0-7695-0798-0. S2CID   1977743.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.