Key derivation function
|
|
A Key derivation function or key stretcher is a cryptographic hash function which is designed to make a key or password harder to attack using a precomputed dictionary attack or brute force attack.
It is normally expressed as <math>DK=KDF(Key, Salt, Iterations)<math> where <math>DK<math> is the derived key, <math>KDF<math> is the key derivation function, <math>Key<math> is the original key or password, <math>Salt<math> is a random number which acts as cryptographic salt, and <math>Iterations<math> refers to the number of iterations 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.
The first key derivation function was called "CRYPT(3)" and was invented by Robert Tappan Morris, Sr. during the 1980s for encrypting Unix passwords. It used an iteration count of 25, a 12-bit salt and a variant of DES as the sub-function. It also limited passwords to a maximum of eight ASCII characters. While a great advance at the time, CRYPT(3) is now considered inadequate. The iteration count, appropriate in the PDP-11 era, is too low, 12 bits of salt inconvenience but do not stop precomputed dictionary attacks and the 8 character limit prevents the use of stronger passphrases.
Modern 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 attacks more difficult to mount.