Key-stretching adds additional security to potentially weak keys by requiring an expensive computation to transform the initial key into a derived key.
Key-stretching is a term used to describe several methods of increasing the security of a system that is dependent on a key of low entropy. These systems are vulnerable to a brute-force attack, where an attacker simply tries every possible key value until the correct key is found. If the number of possible inputs is relatively small, such an attack can be executed relatively quickly. Older encryption algorithms with smaller key sizes, and systems based on a user-specified password as the source of entropy, are examples of systems that benefit from key-stretching.
Note that lengthening a key, by taking an input representing a small number of bits of entropy, and passing it through a hash function that produces a digest representing significantly more bits of entropy, does not increase security; because the number of inputs is still limited, the number of possible hash digests is also limited, and most hash functions designed for general cryptographic use (such as verifying digital certificates) are designed to execute quickly, and so the requirement to generate the hash is no real impediment to an attacker.
The primary technique under this umbrella is to increase the length of the key itself, by taking the initial key and performing a computationally expensive transformation on it to produce a larger key that can be used in a secure encryption algorithm. This increased amount of time required to perform the operation on one possible key is relatively small when employed by a legitimate user with the correct input key, but for an attacker attempting to brute force that input key the added time required for each attempt makes the approach unfeasible.
This strategy is commonly used for password strengthening; passwords, typically based on dictionary words or proper names with small modifications, are notoriously low in entropy; a simple dictionary word 8 characters long has only 12 bits of entropy inherent in it. Algorithms performing this function are known as Key Derivation Functions or KDFs, and include PBKDF2, BCrypt, and SCrypt, all of which are typically used to generate hashes or keys based on user passwords for verification, and are capable of varying the amount of complexity required to generate the hash value, thus allowing them to keep pace with increases in computing power over time.
Other techniques target legacy encryption algorithms, which are limited in their maximum key size based on the limited memory of systems in use at the time they were designed. DES is an example; it has a maximum key length of 56 bits, which can be brute-forced in reasonable time given current computing hardware. In 1999, a combination of two distributed network operators colluded to break a DES-encrypted message in 22 hours, 15 minutes. For sensitive information, which may remain so for years or indefinitely, this is unacceptable.
To mitigate this vulnerability, cryptographers developed a variant where the basic DES cipher would be executed three times per block; the plaintext would first be encrypted with one 56-bit key, then that ciphertext would be encrypted with a second key, then that ciphertext would be encrypted with a third key to produce the final output block. The resulting algorithm, Triple-DES, has a total key length of 168 bits, which is long enough to resist brute-force cracking even by large distributed systems. TripleDES is still secure today, although the algorithm has been largely replaced in new systems by the faster and more flexible AES algorithm.
