Key stretching
In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources (time and possibly space) it takes to test each…
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources (time and possibly space) it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate.
Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker. There are several ways to perform key stretching. One way is to apply a cryptographic hash function or a block cipher repeatedly in a loop.
For example, in applications where the key is used for a cipher, the key schedule in the cipher may be modified so that it takes a specific length of time to perform. Another way is to use cryptographic hash functions that have large memory requirements – these can be effective in frustrating attacks by memory-bound adversaries.
Moore's law asserts that computer speed doubles roughly every 2 years. Under this assumption, every 2 years one more bit of key strength is plausibly brute-forcible.
This implies that 16 extra bits of strength is worth about 16×2 = 32 years later cracking, but it also means that the number of key stretching rounds a system uses should be doubled about every 2 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 5,000 gates, and 400 clock cycles. With multi-million gate FPGAs costing less than $100, an attacker can build a fully unrolled hardware cracker for about $5,000.
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 $2,500. The key stretching still slows down the attacker in such a situation; a $5,000 design attacking a straight SHA-1 hash would be able to try 300,000÷2 16 ≈ 4.578 keys/second.
Similarly, modern consumer GPUs can speed up hashing considerably. For example, in a benchmark, a Nvidia RTX 2080 SUPER FE computes over 10 billion SHA1 hashes per second. To defend against the hardware approach, memory-bound cryptographic functions have been developed.
These functions access a lot of memory in a way that makes caching ineffective. Since large amounts of low latency memory are expensive, potential attackers are discouraged from pursuing such attacks.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1356459600 under CC BY-SA 4.0; modifications have been made.