MadSci Network: Computer Science |
The strength of an encryption algorithm is limited by the size of its key, for the simple reason that an attacker can always decrypt a message by trying all possible keys. If the number of possible keys is very large, this kind of attack (known as exhaustive search) takes a long time; so cipher designers try to create ciphers with very large key spaces.
The key for a typical, modern, "symmetric-key" cipher (further described below) is a bunch of random binary digits, or bits, each of which can take the value 0 or 1. If there are k bits in the key, then the number of possible keys is 2^{k}. Here is a table showing how the number of possible keys and the corresponding difficulty of exhaustively searching the key space increase as k gets larger:
k | # keys | Difficulty |
---|---|---|
40 | 2^{40}= 1 trillion | A key space of this size has been exhaustively
searched in a few hours on about 100 networked
computers.
This key length achieved notoriety as the longest key length allowed by the US federal government in mass-market software that could be sold to foreigners. |
56 | 2^{56}= 72 million billion | A key space of this size has been exhaustively
searched in a period of months using a large
number of networked computers. It has also been
exhaustively searched in a few days using a
special-purpose machine specifically designed
for high-speed key guessing.
This key length achieved notoriety as the length of the keys in the Data Encryption Standard (DES) algorithm. |
80 | 2^{80}= 1 trillion trillion | Exhaustive search of this key space will take
2^{24} = 16 million times as long as a 56-bit
key space. This key length will probably remain
immune to exhaustive search for another 10 years.
This key length achieved notoriety as the length of keys used in the "clipper chip" promoted by the US federal government. |
128 | 2^{128} = 3 x 10^{38} | If you built a key-search chip that tried 100 billion (10^{11}) keys per second, and assembled a billion (10^{9}) such chips into a gigantic key-searching machine, that machine would be able to search the entire key space in 100 billion years. |
Note that while a short key always means that a cipher is weak, a long key does not guarantee that a cipher is strong. It often happens that some unfortunate weakness in a cipher allows an attacker to learn something in far less time than is needed to exhaustively search the key space. In fact, newly proposed ciphers almost invariably have such weaknesses, and it is only after a cipher has received stern scrutiny from many cryptologists for many years that cryptographers begin to trust it. The DES algorithm had been history's most heavily studied cipher for about 15 years before its limitations (aside from its too-short key) started coming to light. So don't trust a cipher just because it has a long key.
The above table of key lengths applies to "symmetric-key" ciphers, in which the encryption process and the decryption process both use the same key. Symmetric-key ciphers tend to use random-looking hodge-podges of logical and arithmetic operations (my apologies to cipher designers) to mush data into incomprehensibility. In contrast, "public-key" ciphers use precisely defined mathematical operations to mush data into incomprehensibility, and by clever exploitation of mathematical properties it is possible to design these ciphers so that the "decryption" key is not only different from the "encryption" key, but underivable from it. As a general rule, public-key keys have to be longer to provide the same level of security as symmetric-key keys. For example, a 512-bit public-key key was broken just a few days ago. For the next 10 years, 1024-bit public keys look safe, but some serious paranoids are already moving to 2048-bit public keys.
There is one well-known cipher that is unbreakable regardless of the computing power of the attacker, and that cipher is called the One-Time Pad. The One-Time Pad uses as many bits of key as there are bits of message to be encrypted, and the key may be used only once. The strength of the One-Time Pad derives from the fact that an attacker who tries all possible keys will find not only your secret message, but all possible secret messages with the same length. One-time pads are sometimes used in situations where the volume of data to be sent is limited and can be known beforehand.
For more information:
Try the links in the MadSci Library for more information on Computer Science.