World Library  
Flag as Inappropriate
Email this Article

Key stretching

Article Id: WHEBN0004266286
Reproduction Date:

Title: Key stretching  
Author: World Heritage Encyclopedia
Language: English
Subject: Bcrypt, Password strength, Dictionary attack, Dm-crypt, Blowfish (cipher)
Collection: Articles with Example Pseudocode, Key Management
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Key stretching

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[1] for a comparison).

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 (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. 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.

Contents

  • Hash based key stretching 1
  • Strength and time 2
  • History 3
  • Some systems that use key stretching 4
  • See also 5
  • References 6
  • External links 7

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 (160 bits) 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 (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.)

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.[2] With multi-million gate FPGAs costing less than $100,[3] 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.[4] This attack has been implemented for SHA256.[5]

History

The first deliberately slow password-based key derivation function "CRYPT" was described in 1978 by Robert Morris for encrypting Unix passwords.[6] 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.) 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 (e.g. 64 bits) and a high iteration count (often 1000 or more).

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.[7][8]

Some systems that use key stretching

See also

References

  1. ^ Secure Applications of Low-Entropy Keys, J. Kelsey, B. Schneier, C. Hall, and D. Wagner (1997)
  2. ^ http://events.iaik.tugraz.at/RFIDSec08/Papers/Publication/04%20-%20ONeill%20-%20Low%20Cost%20SHA-1%20-%20Slides.pdf
  3. ^ http://www.xilinx.com/prs_rls/silicon_spart/0333spartan3.htm
  4. ^ https://firebwall.com/research/TransferableStateAttackonIteratedHashingFunctions.pdf
  5. ^ https://github.com/bwall/SafeCracker/blob/master/CrackPwSafe/src/SHA256.cpp
  6. ^ Morris, Robert; Thompson, Ken (1978-04-03). "Password Security: A Case History.". Bell Laboratories. Retrieved 2011-05-09. 
  7. ^ Scrypt http://www.tarsnap.com/scrypt/scrypt.pdf
  8. ^ scrypt: A new key derivation function, Colin Percival, BSDCan 2009, accessed 2011-2-1

External links

  • PHP implementation to get a strong hash from a weak password
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.