Citizendia

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. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" In Cryptography, a key is a piece of information (a Parameter) that determines the functional output of a cryptographic algorithm In computing a password is a Word or string of characters that is entered often along with a user name, in modern times usually into a computer system A passphrase is a sequence of words or other text used to control access to a computer system program or data In Cryptanalysis, a brute force attack is a method of defeating a Cryptographic scheme by trying a large number of possibilities for example possible keys Passwords or passphrases created by humans are often short or predictable enough to allow password cracking. Password cracking is the process of recovering Passwords from data that has been stored in or transmitted by a Computer system. 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). A cryptographic Hash function is a transformation that takes an input (or 'message' and returns a fixed-size string which is called the hash value (sometimes In Cryptography, a block cipher is a symmetric key Cipher which operates on fixed-length groups of Bits termed blocks, with an 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. In Cryptography, the so-called Product ciphers are a certain kind of ciphers where the (de-ciphering of data is done in "rounds"

A related technique, salting, protects against time-memory tradeoff attacks and is often used in conjunction with key strengthening. In Cryptography, a salt comprises random Bits that are used as one of the inputs to a Key derivation function. In Computer science, a space-time or time-memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution or

Contents

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. For concatenation of general lists see Append. In Computer programming, string concatenation is the operation of joining two character A personal computer ( PC) is any Computer whose original sales price size and capabilities make it useful for individuals and which is intended to be operated A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another 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 216 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. Moore's law describes an important trend in the History of computer hardware. ) 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. In Unix computing crypt is the name of both a commonly available utility program and a C programming function Robert "Bob" H Morris is an American Cryptographer. He received a Bachelor's degree in Mathematics from Harvard University The 1980s was the decade spanning from January 1 1980 to December 31 1989. Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer It used an iteration count of 25, a 12-bit salt and a variant of DES as the sub-function. The Data Encryption Standard ( DES) is a Cipher (a method for Encrypting information selected by NBS as an official Federal Information (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. American Standard Code for Information Interchange ( ASCII) 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. The PDP-11 was a series of 16-bit Minicomputers sold by Digital Equipment Corp A passphrase is a sequence of words or other text used to control access to a computer system program or data

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. PBKDF2 (Password-Based Key Derivation Function is a Key derivation function that is part of RSA Laboratories ' Public-Key Cryptography Standards (PKCS series In Cryptography, MD5 ( Message-Digest algorithm 5) is a widely used partially insecure Cryptographic hash function with a 128- Bit hash value 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. In Cryptography, a custom hardware attack uses specially designed electronic circuits to decipher encrypted messages.

Some systems that use key strengthening

See also

References

External links

For the entomologist see David L Wagner David A Wagner ( 1974) is an Associate Professor of Computer Science
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic