MadSci Network: Computer Science Query:

### Re: Will 128-bit encryption always be secure?

Date: Mon Sep 6 23:18:53 1999
Posted By: Peter Pearson, Cryptologist
Area of science: Computer Science
ID: 936409853.Cs
Message:

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 2k. 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# keysDifficulty
40 240= 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 256= 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 280= 1 trillion trillion Exhaustive search of this key space will take 224 = 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 2128 = 3 x 1038 If you built a key-search chip that tried 100 billion (1011) keys per second, and assembled a billion (109) 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.

• The Codebreakers, by David Kahn, reviews the history of cryptography, and includes many interesting stories. About half of today's cryptologists were drawn into cryptology by this book.
• Applied Cryptography, by Bruce Schneier, is a very readable description of modern cryptographic methods.
• John Savard's cryptology page has a lot of interesting cryptological stuff.
• RSA Data Security Inc's challenges page tracks progress in breaking ciphers with various key lengths.

Current Queue | Current Queue for Computer Science | Computer Science archives