Key strengthening
Encyclopedia
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 (see section 6 of for a comparison).
Key stretching techniques generally work as follows. The initial key is fed into an algorithm that, running on a given speed of processor, 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 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 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 (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, since the user's computer only has to compute the stretching function once upon the user entering his/her 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 (see pseudo code below). In applications where the key is used for a cipher
, the key schedule
(key set-up) 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.
key = hash(password)
for 1 to 65536 do
key = hash(key)
A better simple key stretching method. ("+" denotes the operation of concatenation
):
key = hash(password)
for 1 to 65536 do
key = hash(key + password)
Even better method with a salt
:
key = hash(password + salt)
for 1 to 65536 do
key = hash(key + password + salt)
Many libraries provide functions which perform key stretching as part of their function; see crypt(3)
for an example.
Note that PBKDF2
is not for generating a hash of a password, but an encryption key from a password. 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).
s in use today (2011) 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 operations, which means the enhanced key is "worth" about an additional 16 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. (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.)
An important consideration to be made is that CPU-bound hash functions are still vulnerable to hardware implementations
. For example, the literature provides efficient hardware implementations of SHA-1 in as low as 5000 gates, and able to produce a result in less than 400 clock cycles. Since multi-million gate FPGAs can be purchased at less than $100 price points, it follows that an attacker can build a fully unrolled
hardware cracker for about $5000. Such a design, if clocked at 100MHz can try about 300,000 keys/second for the algorithm proposed above. 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, i.e. a $5000 design attacking a straight SHA-1 hash would be able to try 300,000*2^16 = 20 billion keys/second.
To alleviate this problem, the use of memory bound
cryptographic functions has been proposed. These functions access large amounts of memory in an unpredictable fashion such that caches
are ineffective. Since large amounts of low latency memory are very expensive, or downright impossible with current technology, the would-be attacker is significantly deterred.
in 1978 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 is an inconvenience but does not stop precomputed dictionary attacks, and the 8 character limit prevents the use of stronger passphrase
s.
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, such As Scrypt to use algorithms that require large amounts of computer memory and other computing resources to make custom hardware attack
s more difficult to mount.
In 2009, a new key strengthening algorithm, scrypt, was introduced that demands large amounts of memory to evaluate, limiting the use of custom, highly parallel hardware to speed up key testing.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, key stretching refers to techniques used to make a possibly weak key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
, typically a password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
or passphrase
Passphrase
A passphrase is a sequence of words or other text used to control access to a computer system, program or data. A passphrase is similar to a password in usage, but is generally longer for added security. Passphrases are often used to control both access to, and operation of, cryptographic programs...
, more secure against a brute force attack
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
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
Password cracking
Password cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password...
. 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 (see section 6 of for a comparison).
Key stretching techniques generally work as follows. The initial key is fed into an algorithm that, running on a given speed of processor, 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 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 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 (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, since the user's computer only has to compute the stretching function once upon the user entering his/her 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
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
or a block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
may be repeatedly applied in a loop (see pseudo code below). In applications where the key is used for a cipher
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
, the key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
(key set-up) in the cipher may be modified so that it takes one second to perform.
A related technique, salting
Salt (cryptography)
In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function...
, protects against time-memory tradeoff attacks and is often used in conjunction with key stretching.
Hash based key stretching
A collision prone simple key stretching method:key = hash(password)
for 1 to 65536 do
key = hash(key)
A better simple key stretching method. ("+" denotes the operation of concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
):
key = hash(password)
for 1 to 65536 do
key = hash(key + password)
Even better method with a salt
Salt (cryptography)
In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function...
:
key = hash(password + salt)
for 1 to 65536 do
key = hash(key + password + salt)
Many libraries provide functions which perform key stretching as part of their function; see crypt(3)
Crypt (Unix)
In Unix computing, crypt is the name of both a utility program and a C programming function. Though both are used for encrypting data, they are otherwise essentially unrelated...
for an example.
Note that PBKDF2
PBKDF2
PBKDF2 is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force's RFC 2898...
is not for generating a hash of a password, but an encryption key from a password. 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).
Strength and time
For these examples assume that the slowest personal computerPersonal computer
A personal computer is any general-purpose computer whose size, capabilities, and original sales price make it useful for individuals, and which is intended to be operated directly by an end-user with no intervening computer operator...
s in use today (2011) can do about 65000 SHA-1 hashes in one second using compiled
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
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 operations, which means the enhanced key is "worth" about an additional 16 bits in key strength.
The commonly accepted Moore's law
Moore's Law
Moore's law describes a long-term trend in the history of computing hardware: the number of transistors that can be placed inexpensively on an integrated circuit doubles approximately every two years....
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. (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.)
An important consideration to be made is that CPU-bound hash functions are still vulnerable to hardware implementations
Custom hardware attack
In cryptography, a custom hardware attack uses specifically designed application-specific integrated circuits to decipher encrypted messages....
. For example, the literature provides efficient hardware implementations of SHA-1 in as low as 5000 gates, and able to produce a result in less than 400 clock cycles. Since multi-million gate FPGAs can be purchased at less than $100 price points, it follows that an attacker can build a fully unrolled
Loop unwinding
Loop unwinding, also known as loop unrolling, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size...
hardware cracker for about $5000. Such a design, if clocked at 100MHz can try about 300,000 keys/second for the algorithm proposed above. 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, i.e. a $5000 design attacking a straight SHA-1 hash would be able to try 300,000*2^16 = 20 billion keys/second.
To alleviate this problem, the use of memory bound
Memory bound function
Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of available memory to hold data. In other words, the limiting factor of solving a given problem is the memory access speed...
cryptographic functions has been proposed. These functions access large amounts of memory in an unpredictable fashion such that caches
Cache
In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...
are ineffective. Since large amounts of low latency memory are very expensive, or downright impossible with current technology, the would-be attacker is significantly deterred.
History
The first deliberately-slow password-based key derivation function was called "CRYPT" and was published by Robert MorrisRobert Morris (cryptographer)
Robert Morris , was an American cryptographer and computer scientist. -Family and Education:Morris was born in Boston, Massachusetts. His parents were Walter W. Morris, a salesman, and Helen Kelly Morris...
in 1978 for encrypting Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
passwords. It used an iteration count of 25, a 12-bit salt and a variant of DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
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
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
characters. While it seemed a great advance at the time, CRYPT(3) is now considered inadequate. The iteration count, designed for the PDP-11
PDP-11
The PDP-11 was a series of 16-bit minicomputers sold by Digital Equipment Corporation from 1970 into the 1990s, one of a succession of products in the PDP series. The PDP-11 replaced the PDP-8 in many real-time applications, although both product lines lived in parallel for more than 10 years...
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 passphrase
Passphrase
A passphrase is a sequence of words or other text used to control access to a computer system, program or data. A passphrase is similar to a password in usage, but is generally longer for added security. Passphrases are often used to control both access to, and operation of, cryptographic programs...
s.
Modern password-based key derivation functions, such as PBKDF2
PBKDF2
PBKDF2 is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force's RFC 2898...
(specified in RFC 2898), use a cryptographic hash, such as MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
or SHA1, more salt (e.g. 64 bits) and a high iteration count (often 1000 or more). There have been proposals, such As Scrypt to use algorithms that require large amounts of computer memory and other computing resources to make custom hardware attack
Custom hardware attack
In cryptography, a custom hardware attack uses specifically designed application-specific integrated circuits to decipher encrypted messages....
s more difficult to mount.
In 2009, a new key strengthening algorithm, scrypt, was introduced that demands large amounts of memory to evaluate, limiting the use of custom, highly parallel hardware to speed up key testing.
Some systems that use key stretching
- PGPPretty Good PrivacyPretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...
, GPGGNU Privacy GuardGNU Privacy Guard is a GPL Licensed alternative to the PGP suite of cryptographic software. GnuPG is compliant with RFC 4880, which is the current IETF standards track specification of OpenPGP...
encryption software. - Wi-Fi Protected AccessWi-Fi Protected AccessWi-Fi Protected Access and Wi-Fi Protected Access II are two security protocols and security certification programs developed by the Wi-Fi Alliance to secure wireless computer networks...
(WPA and WPA2) wireless encryption protocol in personal mode. - Some but not all disk encryption softwareDisk encryption softwareTo protect confidentiality of the data stored on a computer disk a computer security technique called disk encryption is used. This article discusses software that is used to implement the technique...
: (See comparison of disk encryption softwareComparison of disk encryption software-Background information:-Operating systems:-Features:* Hidden containers: Whether hidden containers can be created for deniable encryption...
) - KeePassKeePassKeePass Password Safe is an open-source password management utility for Microsoft Windows, with unofficial ports for Linux, Mac OS X, and a variety of other systems.-Cryptography:...
, an open sourceOpen sourceThe term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
Password managerPassword managerA password manager is software that helps a user organize passwords and PIN codes. The software typically has a local database or a file that holds the encrypted password data for secure logon onto computers, networks, web sites and application data files. Many password managers also work as a form...
utility. - KeePassX, a cross platform (OSX, Linux, Windows) open source password managerPassword managerA password manager is software that helps a user organize passwords and PIN codes. The software typically has a local database or a file that holds the encrypted password data for secure logon onto computers, networks, web sites and application data files. Many password managers also work as a form...
. - ApacheApache HTTP ServerThe Apache HTTP Server, commonly referred to as Apache , is web server software notable for playing a key role in the initial growth of the World Wide Web. In 2009 it became the first web server software to surpass the 100 million website milestone...
.htpasswd.htpasswd.htpasswd is a flat-file used to store usernames and password for basic authentication of Apache HTTP Server. The name of the file is given by in the .htaccess configuration, and can be anything, but ".htpasswd" is the canonical name. The file name starts with a dot, because most Unix-like...
"APR1" and OpenSSLOpenSSLOpenSSL is an open source implementation of the SSL and TLS protocols. The core library implements the basic cryptographic functions and provides various utility functions...
"passwd" use 1000 rounds of MD5MD5The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
key stretching.
See also
- PBKDF2PBKDF2PBKDF2 is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force's RFC 2898...
- a widely used key stretching algorithm - Key derivation functionKey derivation functionIn cryptography, a key derivation function derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random function...
- Often uses key stretching. - HashcashHashcashHashcash is a proof-of-work system designed to limit email spam and denial-of-service attacks. It was proposed in March 1997 by Adam Back.-How it works:...
- A somewhat related method.