Key Stretching - Strength and Time

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

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 100 MHz 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×216 = 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.

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. This attack has been implemented for SHA256.