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.
Process Key stretching algorithms depend on an algorithm which receives an input key and then expends considerable effort to generate a stretched cipher (called an enhanced key) mimicking randomness and longer key length. The algorithm must have no known shortcut, so the most efficient way to relate the input and cipher is to repeat the key stretching algorithm itself. This compels brute-force attackers to expend the same effort for each attempt. If this added effort compares to a brute-force key search of all keys with a certain key length, then the input key may be described as stretched by that same length. Key stretching leaves an attacker with two options:
Attempt possible combinations of the enhanced key, but this is infeasible if the enhanced key is sufficiently long and unpredictable (i.e., the algorithm mimics randomness well enough that the attacker must trial the entire stretched key space) Attempt possible combinations of the weaker initial key, potentially commencing with a dictionary attack if the initial key is a password or passphrase, but the attacker's added effort for each trial could render the attack uneconomic should the costlier computation and memory consumption outweigh the expected profit If the attacker uses the same class of hardware as the user, each guess will take the similar 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 while not seriously affecting the usability of the system for any legitimate user. This is because the user's computer only has to compute the stretching function once upon the user entering their password, whereas the attacker must compute it for every guess in the attack. This process does not alter the original key-space entropy. The key stretching algorithm is deterministic, allowing a weak input to always generate the same enhanced key, but therefore limiting the enhanced key to no more possible combinations than the input key space. Consequently, this attack remains vulnerable if unprotected against certain time-memory tradeoffs such as developing rainbow tables to target multiple instances of the enhanced key space in parallel (effectively a shortcut to repeating the algorithm). For this reason, key stretching is often combined with salting.
Hash-based Many libraries provide functions which perform key stretching as part of their function; see crypt(3) for an example. 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-2 (up to 512 bits), or used as an encryption key to encrypt static data.
… excerpt ends here. Continue reading the full article.
