Key derivation function: Difference between revisions

Revision as of 01:22, 10 February 2011

Revision as of 02:22, 19 February 2011

Line 12:

Key derivation functions are also used to derive keys from secret passwords or passphrases.

===Key strengtheningstretching===

{{main|Key strengtheningstretching}}

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 attack]] on the password or passphrase input value.

Line 21:

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 (cryptography)|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.<ref>U. Manber, "A Simple Scheme to Make Passwords Based on One-Way Functions Much Harder to Crack," Computers & Security, v.15, n.2, 1996, pp.171-176.</ref> Although the paper that introduced key stretching <ref name="low-entropy">[http://www.schneier.com/paper-low-entropy.html Secure Applications of Low-Entropy Keys], [[John Kelsey (cryptanalyst)|J. Kelsey]], [[Bruce Schneier|B. Schneier]], C. Hall, and [[David A. Wagner|D. Wagner]] (1997)</ref> 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 password-based key derivation function was called "[[Crypt_(Unix)#Library_Function|crypt]]" (or "crypt(3)" after its [[Manual page (Unix)|man page]]), and was invented by [[Robert Morris (cryptographer)|Robert Morris]] in the 1980s 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 attack|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.

The first deliberately-slow (key stretching) password-based key derivation function was called "[[Crypt_(Unix)#Library_Function|crypt]]" (or "crypt(3)" after its [[Manual page (Unix)|man page]]), and was invented by [[Robert Morris (cryptographer)|Robert Morris]] in the 1980s 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 attack|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 <code>scrypt()</code> function, based on the concept of ''sequential memory-hard functions''<ref>http://www.tarsnap.com/scrypt/</ref>, which is used for additional securing private keys by passphrase in the [[tarsnap]] backup system.

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 <code>scrypt()</code> function, based on the concept of ''sequential memory-hard functions''<ref>http://www.tarsnap.com/scrypt/</ref>, which is used for additional securing private keys by passphrase in the [[tarsnap]] backup system.

== Footnotes ==