Key strengthening

From Wikipedia, the free encyclopedia

You have new messages (last change).

In cryptography, key strengthening or key stretching refer to techniques used to make a weak key such as a password or passphrase stronger, i.e. more costly to test combinations through brute force or a dictionary attack. They operate by increasing the time it takes to test each possible key.

Weak keys are used in many systems. Human memorable passwords or passphrases are examples of such weak keys. Another example is that restrictions on the export of cryptography can require the use of short keys.

Key strengthening techniques generally work as follows: First, the weak key is fed through an algorithm that takes a known constant time to apply. (typically about one second on a typical personal computer of today.) The result is the stronger key. The stronger key should be of sufficient size to make it be unfeasible to break it by brute force, (i.e. at least 128 bits). The 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 stronger key in less time or with less processor power.

The process leaves the attacker with two options: Either to try every possible combination of the stronger key, but since the stronger key is at least 128 bits this is not doable. Or try every combination of the weaker key, which normally would be much easier. If the weak 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 and then try all character combinations for longer and longer passwords. This usually yields the correct result in many fewer combinations than a 128-bit "random" key. The weak key might also be a key of say 56-bits due to export-restrictions, which of course means many fewer combinations than the stronger 128-bit key. But, to make the stronger key from the weak key the attacker has to spend about one second on each try. This makes it much more costly than trying weak keys on a system that does not use key strengthening.

There are several ways to do 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.

Contents

[edit] Hash based key strengthening

Simple but pretty good 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( salt + key )

The salt is a system or user specific "unique" value. It can be either a random number or the user name or both combined through concatenation or some other means, such as a hash function. The purpose of the salt is to make it harder for an attacker to perform a dictionary attack.

[edit] Strength and time

The slowest personal computers still in use today (2006) can do about 65000 SHA-1 hashes in one second if using compiled code.

In crypto reasoning it is considered to take one "operation" to test if a key is the correct one. But with key strengthening the attacker first has to make the strong key to test, which with 65000 rounds in the hash loop means that each test takes 65001 operations. That is 65000 times longer time.

And yet another way to view it is: Say the attacker has 100 times faster processors then the slowest users have today, then it will take an attacker about 0.01 seconds to try each weak key. But if the weak key is a 56-bit key this means 256 such tries. That corresponds to about 1 million such fast processors working for about 20 years.

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 (2006) about as hard to crack as a non-strengthened password was in 1982. And since the systems can increase the number of key strengthening rounds as computers get faster it will keep the strong keys as strong as non-strengthened passwords were in 1982 even in the future.

[edit] History

The first deliberately-slow password-based key derivation function was called "CRYPT(3)" 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.

[edit] List of security software that uses key strengthening

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../k/e/y/Key_strengthening.html"