Key strengthening

In cryptography, key strengthening or key stretching refer 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 strengthening makes such attacks more difficult.

Key strengthening techniques generally work as follows: The initial key is fed through an algorithm that takes a known constant time to apply. The algorithm is constructed so that the delay introduced is acceptable to most users, say one second on a typical personal computer. The output is the "enhanced key". The enhanced key should be of sufficient size to make it unfeasible to break by brute force (e.g. at least 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 in less time (less processor work) than by using the key stretching algorithm itself. The key strengthening process leaves the attacker with two options: Either to try every possible combination of the enhanced key, infeasible if the enhanced key is long enough, or try likely combinations of the initial key, which normally would be much easier. If the initial key is a password or a passphrase then the normal way to brute force it would be to first try every word in the dictionary or common password list and then try all character combinations for longer and longer passwords. This often yields the correct result in a reasonable amount of time. Key strengthening does not prevent this approach, but the attacker has to spend much more time on each try.

If the attacker uses the same class of hardware as the user, each guess will take the same amount of time it took the user (for example, one second). Even if the attacker might have much greater computing resources than the user, the key strengthening will still slow him down. The user only has to compute the strengthening function once to use his known password, but the attacker must compute it for each guess in his attack.

There are several ways to perform key strengthening. For instance to apply a cryptographic hash function or a block cipher in a loop (see pseudo code below). Or in some cases if the key is used for a cipher to modify the key schedule (key set-up) in the cipher so it takes one second.

A related technique, salting, protects against time-memory tradeoff attacks and is often used in conjunction with key strengthening.

Hash based key strengthening

Simple key strengthening method:

key = hash( password ) for 1 to 65000 do key = hash( key )

Even better method with a salt. ("+" here means concatenation):

key = hash( password + salt ) for 1 to 65000 do key = hash( key )

Or even:

key = hash( password + salt ) for 1 to 65000 do key = hash( key + salt )

Strength and time

For these examples let us assume that that the slowest personal computers still in use today (2008) can do about 65000 SHA-1 hashes in one second if using compiled code. Thus a program that uses key strengthening can use 65000 hash rounds and then it will take max one second for the slowest users to use their password or key.

Testing a trial password or passphrase typically requires one hash operation. But with key strengthening the attacker first has to make the stronger key to test, which with 65000 rounds in the hash loop means that each test takes 65001 operations. That is 65000 times more work, i.e. about 2¹⁶ operations, which means the enhanced key is "worth" about 16 bits more in key strength.

Note that when strengthening a weak key, the intermediate key used in the hash loop and the final stronger key must be big enough to hold the additional strength.

So far computer speed has doubled about once per 1.5 years. (See Moore's law.) This means that each 1.5 years one more bit of key strength is possible to crack. This means that the 16 extra bits of strength is worth about 16×1.5 = 24 years later cracking. But it also means that the number of key strengthening rounds a system uses should and can be doubled about once every 1.5 years. Still it will only cost about 1 second to do the key strengthening on the computers available then. Thus key strengthening can make the same size weak keys just as hard to crack also in the future.

For passwords and passphrases, the situation is unfortunately not as good, since they are usually worth much less than 56 bits of strength. But since 16 bits means 24 years it makes a key strengthened password today (2008) about as hard to crack as a non-strengthened password was in 1984. And since the systems can increase the number of key strengthening rounds as computers get faster it will keep the stronger keys as strong as non-strengthened passwords were in 1984 even in the future.

History

The first deliberately-slow password-based key derivation function was called "CRYPT" and was invented by Robert Morris 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. (DES proper was avoided in an attempt to frustrate attacks using standard DES hardware.) It also limited passwords 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 inconvenience but do 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 (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.

Some systems that use key strengthening

*PGP, GPG encryption software.
*Wi-Fi Protected Access (WPA and WPA2) wireless encryption protocol in personal mode.
*Some but not all disk encryption software: (See comparison of disk encryption software)

See also

* PBKDF2 - a widely used key strengthening algorithm
* Key derivation function - Often uses key strengthening.
* Hashcash - A somewhat related method.

References

* [http://www.schneier.com/paper-low-entropy.html Secure Applications of Low-Entropy Keys] by J. Kelsey, B. Schneier, C. Hall, and D. Wagner (1997)
* [http://www2007.org/poster855.php A Password Stretching Method with User Specific Salts] by ChangHee Lee and Heejo Lee (2007)
* RFC 2898

External links

* [http://www.php-einfach.de/improved_hash_algorithm_en.php PHP implementation to get a strong hash from a weak password]