Symmetric Key Length

Symmetric key encryption is subject to key search attacks (also called brute force attacks). In these attacks, the attacker tries each possible key until the right key is found to decrypt the message. Most attacks are successful before all possible keys are tried.

In general, you can minimize the risk of key search attacks by choosing shorter key lifetimes and longer key lengths. A shorter key lifetime means that each key encrypts less information, which reduces the potential damage if one of the keys is compromised.

Longer key lengths decrease the possibility of successful attacks by increasing the number of combinations that are possible. For example, for a 40-bit key, there are 2⁴⁰ possible values. By using a personal computer that can try 1 million keys per second, an attacker can try all possible keys in about 13 days. However, an 128-bit key has 2¹²⁸ possible values. If you could use a computer that would allow you to try 100 billion keys a second and you used 10 million of these computers, it would take about 10¹³ years to try every possible 128-bit key value. This is nearly 1000 times longer than the estimated age of the universe (15 billion to 20 billion years). Therefore, the longer the key, the more protection you have from attacks. For symmetric key encryption, increasing the key size by one bit doubles the effort that is required for an exhaustive key search attack. Doubling the key size squares the amount of effort required.

However, the time that is required to launch a successful key search attack (that is, the time that is required to discover a symmetric key) has diminished as the computing power that is available to attackers has increased. In addition, as the price of powerful computers has decreased, successful key search attacks have become more common. With the fastest off-the-shelf personal computers that are available today, an attacker now can break 40-bit encryption in hours rather than days. Some leading cryptography experts had previously estimated the cost of building a computer that could crack the widely implemented 56-bit Data Encryption Standard (DES) algorithm to be several million dollars or more. But in July 1998, Electronic Frontier Foundation in San Francisco, California, used a supercomputer that they built from off-the-shelf components at a cost of less than $250,000 to launch a key search attack on a message that had been encrypted with this algorithm. The computer searched 92 billion keys per second and decrypted the message in 56 hours after trying about 25 percent of the possible keys. In January 1999, the same organization used an improved version of its off-the-shelf supercomputer to break a 56-bit DES encrypted message in about 22 hours — less than half the time it took to break a 56-bit DES encrypted message only 6 months earlier.

Symmetric keys that are at least 64 bits long generally provide strong protection against brute force attacks. Today, symmetric keys that are 128 bits or longer are considered unbreakable by brute force attacks. However, the power of personal computers has historically doubled approximately every 18 months. In addition, attackers often develop new techniques and algorithms to improve the efficacy of key search attacks. Therefore, estimates of the time required for successful key search attacks must be revised downward as the computing power and resources available to attackers increases.

© 1985-2000 Microsoft Corporation. All rights reserved.