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 (time and possibly space) 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. Because a key generation function must be deterministic so that the weak key always generates the same stretched key (called an enhanced key), the stretching of the key does not alter the entropy of the key-space, only complicates the method of computing the enhanced key. Attacks on unsalted key stretching functions exist called rainbow tables. Salting the key is the process of appending a long, random string to the weak key. This is done so that precomputed hashes of either short keys or password lists cannot be used in authentication schemes that require the hash to be presented or to reverse hashes into their original pass-phrases which may be used to compromise users on other services using the same pass-phrase.
Key stretching techniques generally work as follows. The initial key is fed into an algorithm that outputs an enhanced key. The enhanced key should be of sufficient size to make it infeasible to break by brute force (e.g. 128 bits). The overall algorithm used should be secure in the sense that there should be no known way of taking a shortcut that would make it possible to calculate the enhanced key with less processor work and memory used than by using the key stretching algorithm itself.
The key stretching process leaves the attacker with two options: either try every possible combination of the enhanced key (infeasible if the enhanced key is long enough), or else try likely combinations of the initial key. In the latter approach, if the initial key is a password or a passphrase, then the attacker would first try every word in a dictionary or common password list and then try all character combinations for longer passwords. Key stretching does not prevent this approach, but the attacker has to spend much more resources (time and/or memory used) on each attempt, which may easily make this approach infeasible as well.
If the attacker uses the same class of hardware as the user, each guess will take the similar amount of time to process as it took the user (for example, one second). Even if the attacker has much greater computing resources than the user, the key stretching will still slow the attacker down while not seriously affecting the usability of the system for any legitimate user, since the user's computer only has to compute the stretching function once upon the user entering their password, whereas the attacker must compute it for every guess in the attack.
There are several ways to perform key stretching. One way is to apply a cryptographic hash function or a block cipher repeatedly in a loop. E.g., in applications where the key is used for a cipher, the key schedule in the cipher may be modified so that it takes a specific length of time to perform. Another way is to use cryptographic hash functions that have large memory requirements – these can be effective in frustrating attacks by memory-bound adversaries.
A related technique, salting, protects against attacks that take advantage of certain time–memory tradeoffs (which often utilize some variation of rainbow tables) and is often used in conjunction with key stretching.
Many libraries provide functions which perform key stretching as part of their function; see crypt(3) for an example. PBKDF2 is for generating an encryption key from a password, and not necessarily for password authentication. PBKDF2 can be used for both if the number of output bits is less than or equal to the internal hashing algorithm used in PBKDF2 which is usually SHA-1 (160 bits) or used as an encryption key to encrypt static data.
Strength and time
These examples assume that a personal computer can do about 65,000 SHA-1 hashes in one second. Thus a program that uses key stretching can use 65,000 rounds of hashes and delay the user for at most one second.
Testing a trial password or passphrase typically requires one hash operation. But if key stretching was used, the attacker must compute a strengthened key for each key they test, meaning there are 65,000 hashes to compute per test. This increases the attacker's workload by a factor of 65,000, approximately 216, which means the enhanced key is worth about 16 additional bits in key strength.
Moore's law asserts that computer speed doubles roughly every 1.5 years. Under this assumption, every 1.5 years one more bit of key strength is plausibly brute-forcible. This implies that 16 extra bits of strength is worth about 16×1.5 = 24 years later cracking, but it also means that the number of key stretching rounds a system uses should be doubled about every 1.5 years to maintain the same level of security (since most keys are more secure than necessary, systems that require consistent deterministic key generation will likely not update the number of iterations used in key stretching. In such a case, the designer should take into consideration how long they wish for the key derivation system to go unaltered and should choose an appropriate number of hashes for the lifespan of the system).
CPU-bound hash functions are still vulnerable to hardware implementations. Such implementations of SHA-1 exist using as few as 5,000 gates, and 400 clock cycles. With multi-million gate FPGAs costing less than $100, an attacker can build a fully unrolled hardware cracker for about $5,000. Such a design, clocked at 100 MHz can test about 300,000 keys/second. The attacker is free to choose a good price/speed compromise, for example a 150,000 keys/second design for $2,500. The key stretching still slows down the attacker in such a situation; a $5,000 design attacking a straight SHA-1 hash would be able to try 300,000÷216 ≈ 4.578 keys/second.
To defend against the hardware approach, memory-bound cryptographic functions have been developed. These access large amounts of memory in an unpredictable fashion such that caches are ineffective. Since large amounts of low latency memory are expensive, a would-be attacker is significantly deterred.
The first deliberately slow password-based key derivation function "CRYPT" was described in 1978 by Robert Morris for encrypting Unix passwords. It used an iteration count of 25, a 12-bit salt and a variant of DES as the sub-function. (DES proper was avoided in an attempt to frustrate attacks using standard DES hardware.) Passwords were limited to a maximum of eight ASCII characters. While it was a great advancement for its time, CRYPT(3) is now considered inadequate. The iteration count, designed for the PDP-11 era, is too low, 12 bits of salt is an inconvenience but does not stop precomputed dictionary attacks, and the 8 character limit prevents the use of stronger passphrases.
In 2013, a Password Hashing Competition was held to select an improved key stretching standard that would resist attacks from graphics processors and special purpose hardware. The winner, Argon2, was selected on July 1, 2015.
Some systems that use key stretching
- Some but not all disk encryption software: (See comparison of disk encryption software)
- Apache .htpasswd "APR1" and OpenSSL "passwd" use 1000 rounds of MD5 key stretching.
- KeePass and KeePassX, open-source password manager utilities.
- Password Safe open-source password manager.
- PGP, GPG encryption software.
- Wi-Fi Protected Access (WPA and WPA2) wireless encryption protocol in personal mode.
- Key derivation function – often uses key stretching
- Hashcash – a somewhat related method.
- Hash chain
- Morris, Robert; Thompson, Ken (1978-04-03). "Password Security: A Case History". Bell Laboratories. Archived from the original on 2003-03-22. Retrieved 2011-05-09.
- scrypt: A new key derivation function, Colin Percival, BSDCan 2009, accessed 2011-2-1
- Password Hashing Competition