In cryptography, key stretching refers to techniques used to make a possibly
weak key, typically a password or passphrase, more secure against a brute
force attack by increasing the time it takes to test each possible key.
Passwords or passphrases created by humans are often short or predictable
enough to allow password cracking. Key stretching makes such attacks more
difficult. Key stretching is sometimes referred to
as "key strengthening", although the latter term originally referred to
another technique with significantly different security and performance
properties. 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 unfeasible to
break by brute force. 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 in less time 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, 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 time on
each attempt. If the attacker uses the same class of
hardware as the user, each guess will take the same amount of time to process
as it took the user. Even if the attacker has much greater computing
resources than the user, the key stretching will still slow the attacker
down, 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. A cryptographic hash function or a block cipher may be
repeatedly applied in a loop. In applications where the key is used for a
cipher, the key schedule in the cipher may be modified so that it takes one
second to perform. A related technique, salting, protects
against time-memory tradeoff attacks and is often used in conjunction with key
stretching. Hash based key stretching
Many libraries provide functions which perform key stretching as part of their
function; see crypt(3) for an example. Note that 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 or
used as an encryption key to encrypt static data.
Strength and time For these examples assume that the
slowest personal computers in use today can do about 65000 SHA-1 hashes in one
second using compiled code. Thus a program that uses key stretching can use
65000 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 65000 hashes to compute per test.
This increases the attacker's workload by a factor of 65000, approximately 216,
which means the enhanced key is worth about 16 additional bits in key
strength. The commonly accepted Moore's law
implies that computer speed doubles about 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. CPU-bound hash functions are still
vulnerable to hardware implementations. Such implementations of SHA-1 exist
using as few as 5000 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 $5000. 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 $2500. It's worth
noting that the key stretching still slows down the attacker in such a
situation; a $5000 design attacking a straight SHA-1 hash at a rate of 300,000
keys/second would only be producing enhanced keys at a rate of 300,000 / 216
= 4.6 keys/second. To defend against the hardware approach,
memory bound cryptographic functions have been proposed. 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. There exists a known weakness in the
hash based key stretching algorithms that use an iterative hash function.
This attack is known as a transferable state attack. The attack entails
transferring the state from the previous hash in the iterated hashes directly
into the transform method of the next iteration. This method can decrease the
time it takes to stretch the key to 80%-90% of the original stretching time.
This attack has been implemented for SHA256.
History 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. Passwords were limited to
a maximum of eight ASCII characters. While it seemed a great advance at the
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.
Modern password-based key derivation functions, such as PBKDF2, use a
cryptographic hash, such as MD5 or SHA1, a longer salt and a high iteration
count. In 2009, a memory-intensive key
strengthening algorithm, scrypt, was introduced with the intention of
limiting the use of custom, highly parallel hardware to speed up key
testing. Some systems that use key stretching
Some but not all disk encryption software:
Apache .htpasswd "APR1" and OpenSSL "passwd" use 1000 rounds of MD5 key
stretching. KeePass & KeePassX, open-source password
manager utilities. Password Safe open-source password
manager. PGP, GPG encryption software.
Wi-Fi Protected Access wireless encryption protocol in personal mode.
See also Key derivation function - often uses key
stretching PBKDF2, bcrypt, scrypt - widely used key
stretching algorithms Hashcash - A somewhat related method.
Hash chain References
External links PHP implementation to get a strong hash
from a weak password