Key derivation function
Encyclopedia
In cryptography
, a key derivation function (or KDF) derives one or more secret key
s from a secret value such as a master key or other known information such as a password
or passphrase
using a pseudo-random function. Keyed cryptographic hash function
s are popular examples of pseudo-random functions used for key derivation.
Key derivation functions are often used as components of multiparty key-agreement protocol
s.
Examples of such key derivation functions include KDF1, defined in IEEE Std 1363-2000
, and similar functions in ANSI X9.42.
Key derivation functions are also used to derive keys from secret passwords or passphrases.
on the password or passphrase input value.
Such use may be expressed as
where 
is the derived key, 
is the key derivation function
,
is the original key or password, 
is a random number which acts as cryptographic salt
, and
refers to the number of iteration
s of a sub-function. The derived key is used instead of the original key or password as the key to the system. The values of the salt and the number of iterations (if it isn't fixed) are stored with the hashed password or sent as plaintext with an encrypted message.
The difficulty of a brute force attack
increases with the number of iterations. A practical limit on the iteration count is the unwillingness of users to tolerate a perceptible delay in logging in to a computer or seeing a decrypted message. The use of salt
prevents the attackers from precomputing a dictionary of derived keys.
An alternative approach, called key strengthening, extends the key with a random salt, but then (unlike in key stretching) securely deletes the salt. This forces both the attacker and legitimate users to perform a brute-force search for the salt value. Although the paper that introduced key stretching referred to this earlier technique and intentionally chose a different name, the term "key strengthening" is now often (arguably incorrectly) used to refer to key stretching.
The first deliberately-slow (key stretching) password-based key derivation function was called "crypt" (or "crypt(3)" after its man page
), and was invented by Robert Morris
in 1978 to encrypt Unix
passwords.
While it was a great advance at the time, increases in processor speeds since the PDP-11
era have made brute-force attacks
against crypt feasible, and advances in storage have rendered the 12-bit salt inadequate. The crypt function's design also limits the user password to 8 characters, which limits the keyspace and makes strong passphrase
s impossible.
Modern password-based key derivation functions, such as PBKDF2
(specified in RFC 2898), use a cryptographic hash, such as MD5
or SHA1, more salt (e.g. 64 bits) and a high iteration count (often 1000 or more). There have been proposals to use algorithms that require large amounts of computer memory and other computing resources to make custom hardware attack
s more difficult to mount. One concrete instance of such an algorithm is the
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a key derivation function (or KDF) derives one or more secret key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
s from a secret value such as a master key or other known information such as a password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
or passphrase
Passphrase
A passphrase is a sequence of words or other text used to control access to a computer system, program or data. A passphrase is similar to a password in usage, but is generally longer for added security. Passphrases are often used to control both access to, and operation of, cryptographic programs...
using a pseudo-random function. Keyed cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s are popular examples of pseudo-random functions used for key derivation.
Uses of KDFs
Key derivation functions are often used in conjunction with non-secret parameters to derive one or more keys from a common secret value (which is sometimes also referred to as "key diversification"). Such use may prevent an attacker who obtains a derived key from learning useful information about either the input secret value or any of the other derived keys. A KDF may also be used to ensure that derived keys have other desirable properties, such as avoiding "weak keys" in some specific encryption systems.Key derivation functions are often used as components of multiparty key-agreement protocol
Key-agreement protocol
In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a key in such a way that both influence the outcome. If properly done, this precludes undesired third-parties from forcing a key choice on the agreeing parties...
s.
Examples of such key derivation functions include KDF1, defined in IEEE Std 1363-2000
IEEE P1363
IEEE P1363 is an Institute of Electrical and Electronics Engineers standardization project for public-key cryptography. It includes specifications for:* Traditional public-key cryptography...
, and similar functions in ANSI X9.42.
Key derivation functions are also used to derive keys from secret passwords or passphrases.
Key stretching
Key derivation functions are also used in applications to derive keys from secret passwords or passphrases, which typically do not have the desired properties to be used directly as cryptographic keys. In such applications, it is generally recommended that the key derivation function be made deliberately slow so as to frustrate brute-force attack or dictionary attackDictionary attack
In cryptanalysis and computer security, a dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities.-Technique:...
on the password or passphrase input value.
Such use may be expressed as
where is the derived key, is the key derivation functionSubroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
,
is the original key or password, is a random number which acts as cryptographic saltSalt (cryptography)
In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function...
, and
refers to the number of iterationIteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
s of a sub-function. The derived key is used instead of the original key or password as the key to the system. The values of the salt and the number of iterations (if it isn't fixed) are stored with the hashed password or sent as plaintext with an encrypted message.
The difficulty of a brute force attack
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
increases with the number of iterations. A practical limit on the iteration count is the unwillingness of users to tolerate a perceptible delay in logging in to a computer or seeing a decrypted message. The use of salt
Salt (cryptography)
In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function...
prevents the attackers from precomputing a dictionary of derived keys.
An alternative approach, called key strengthening, extends the key with a random salt, but then (unlike in key stretching) securely deletes the salt. This forces both the attacker and legitimate users to perform a brute-force search for the salt value. Although the paper that introduced key stretching referred to this earlier technique and intentionally chose a different name, the term "key strengthening" is now often (arguably incorrectly) used to refer to key stretching.
The first deliberately-slow (key stretching) password-based key derivation function was called "crypt" (or "crypt(3)" after its man page
Manual page (Unix)
Man pages are the extensive documentation that comes preinstalled with almost all substantial Unix and Unix-like operating systems. The Unix command used to display them is man. Each page is a self-contained document.- Usage :...
), and was invented by Robert Morris
Robert Morris (cryptographer)
Robert Morris , was an American cryptographer and computer scientist. -Family and Education:Morris was born in Boston, Massachusetts. His parents were Walter W. Morris, a salesman, and Helen Kelly Morris...
in 1978 to encrypt Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
passwords.
While it was a great advance at the time, increases in processor speeds since the PDP-11
PDP-11
The PDP-11 was a series of 16-bit minicomputers sold by Digital Equipment Corporation from 1970 into the 1990s, one of a succession of products in the PDP series. The PDP-11 replaced the PDP-8 in many real-time applications, although both product lines lived in parallel for more than 10 years...
era have made brute-force attacks
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
against crypt feasible, and advances in storage have rendered the 12-bit salt inadequate. The crypt function's design also limits the user password to 8 characters, which limits the keyspace and makes strong passphrase
Passphrase
A passphrase is a sequence of words or other text used to control access to a computer system, program or data. A passphrase is similar to a password in usage, but is generally longer for added security. Passphrases are often used to control both access to, and operation of, cryptographic programs...
s impossible.
Modern password-based key derivation functions, such as PBKDF2
PBKDF2
PBKDF2 is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force's RFC 2898...
(specified in RFC 2898), use a cryptographic hash, such as MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
or SHA1, more salt (e.g. 64 bits) and a high iteration count (often 1000 or more). There have been proposals to use algorithms that require large amounts of computer memory and other computing resources to make custom hardware attack
Custom hardware attack
In cryptography, a custom hardware attack uses specifically designed application-specific integrated circuits to decipher encrypted messages....
s more difficult to mount. One concrete instance of such an algorithm is the
scrypt function, based on the concept of sequential memory-hard functions, which is used for additional securing private keys by passphrase in the tarsnap backup system.