Encryption Options Beyond DES
DES is no longer a viable choice for encryption. However, a number of
alternative algorithms have been implemented and deployed in various commercial applications.
By William Stallings
The most widely used conventional encryption algorithm is the Data Encryption Standard (DES), first issued as a US standard in 1977. For DES, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same steps, with the same key, are used to reverse the encryption.
The most straightforward approach to
trying to break an encryption algorithm is by using a brute force approach. Given an encrypted message, try every possible key to decrypt it until the right one is found. With a key length of 56 bits, there are 2
56
possible keys, which is approximately 7.2 x 10
16
keys. Thus, on the face of it, a brute-force attack appears impractical. Assuming that, on average, half the key space has to be searched, a single machine performing one DES encryption per µs would take more than a
thousand years to break the cipher. However, the assumption of one encryption per µs is overly conservative. As far back as 1977, Diffie and Hellman postulated that the technology existed to build a parallel machine with one million encryption devices, each of which could perform one encryption per µs. This would bring the average search time down to about ten hours. The authors estimated that the cost of building such a machine would be about $20 million in 1977 dollars.
Since that time, numerous
experts have warned that the days of DES as a secure algorithm are numbered, it being only a matter of time before rising processor speed and falling hardware costs make it a simple matter to quickly break DES.
A dramatic demonstration of the vulnerability of DES was the “secret-key” challenge issued by RSA Laboratories. The challenge, which offered a $10,000 reward, was to find a DES key given a ciphertext for a plaintext consisting of an un-known plaintext message preceded by three known
blocks of text containing the 24-character phrase, “the unknown message is:” RSA issued the challenge on January 29, 1997. In response to the challenge, Rocke Verser, an independent consultant, developed a brute-force program and distributed it over the Internet. The project linked numerous machines over the Internet, growing eventually to over 70,000 systems. As each computer volunteer signed on, the project team created new portions of the DES key space for the machine to test. The project began on
February 18, 1997 and ended 96 days later when the correct key was found after examining about one-quarter of all possible keys. This challenge demonstrated the power of distributed personal computers to attack hard cryptographic problems.
DES was finally declared dead on July 1998, when the Electronic Frontier Foundation (EFF) ann-ounced that they had broken a new DES challenge using a special-purpose “DES cracker” machine that was built for $250,000. The attack took just 3 days. The EFF have
published a detailed description of the machine, enabling others to build their own cracker. And, of course, hardware prices will continue to drop as speeds increase, making DES worthless.
Fortunately, there are a number of alternatives available in the marketplace. Before looking at these, let’s examine the general structure of encryption algorithms and how they are attacked.
Cryptanalysis
If brute force is the only form of attack that can be made on an encryption algorithm, then the
way to counter such attacks is obvious: use longer keys.
Figure 1
shows how long it would take to crack a DES-style algorithm using the EFF cracker as a function of key size. For example, for a 128-bit key, which is common, it would take over 10
19
years to break the code using the EFF cracker. Even if we managed to speed up the cracker by a factor of 1 trillion, it would still take over 10 million years to break the code. So a 128-bit key is guaranteed to result in an
algorithm that is unbreakable by brute force.
But there is another line of attack, namely cryptanalysis. Cryptanalysis attempts to exploit the internal structure of an encryption algorithm to mathematically deduce the encryption key given some number of plaintext-ciphertext pairs. This is a lively area of research, and it turns out to be quite difficult to design an algorithm that is highly resistant to cryptanalysis. The bottom line is that not all encryption algorithms of equal key length are equal. A few
algorithms have emerged with no known weaknesses, and the more popular of these are discussed later in this article.
Structure of an encryption algorithm
Virtually all conventional block encryption algorithms, including DES, have a structure first described by Horst Feistel of IBM in 1973, and is shown schematically in
Figure 2
. The inputs to the encryption algorithm are a plaintext block of length
2w
bits and a key
K
. The
plaintext block is divided into two halves,
L0
and
R0
. The two halves of the data pass through
n
rounds of processing and then combine to produce the ciphertext block. Each round has as inputs
Li-1
and
Ri-1
, derived from the previous round, as well as a subkey
Ki
, derived from the overall
K
. In general, the subkeys
Ki
are different from
K
and from each other, and are generated from the key by a subkey generation algorithm.
All rounds have the
same structure. A substitution is performed on the left half of the data. This is done by applying a round function
F
to the right half of the data and then taking the exclusive
-OR (XOR)
of the output of that function and the left half of the data. The round function has the same general structure for each round, but is parameterized by the round subkey
Ki
. Following this substitution, a permutation is performed that consists of the interchange of the two halves of the data.
The exact realization of a Feistel network depends on the choice of the following parameters and design features:
•
Block size.
Larger block sizes mean greater security (all other things being equal), but reduced encryption/decryption speed. A block size of 64 bits is a reasonable trade-off and is nearly universal in block cipher design.
•
Key size
. Larger key sizes mean greater security but may cause a decrease in encryption/decryption speed. The most
common key length in modern algorithms is 128 bits.
•
Number of rounds.
The essence of the Feistel cipher is that a single round offers inadequate security but that multiple rounds offer increasing security. A typical size is 16 rounds.
•
Subkey generation algorithm.
A greater complexity in this algorithm should lead to greater difficulty of cryptanalysis.
•
Round function.
Again, greater complexity generally means greater resistance to cryptanalysis.
There are
two other considerations in the design of a Feistel cipher:
•
Fast software encryption/decryption
. In many cases, encryption is embedded in applications or utility functions in such a way as to preclude a hardware implementation. Accord-ingly, the execution speed of the algorithm becomes a concern.
•
Ease of analysis.
Although we would like to make our algorithm as difficult as possible to cryptanalyze, there is one great benefit in making the algorithm easy to analyze. That is,
if the algorithm can be concisely and clearly explained, it is easier to analyze that algorithm for cryptanalytic vulnerabilities and therefore develop a higher level of strength. DES, for example, does not have an easily analyzed functionality.
In the case of DES, the subkey generation algorithm involves a simple circular shift of the key bits followed by a permutation. For the round function, DES relies on the use of the XOR function and a series of small S-boxes. An S-box, in essence, is a table
that maps a pattern of input bits into another pattern of output bits; thus, the S-box performs a substitution function. DES is not particularly fast in terms of execution speed, because of the complexity of the algorithm.
Feistel cipher decryption is essentially the same as the encryption process. The rule is as follows: Use the ciphertext as input to the algorithm, but use the subkeys
Ki
in reverse order. That is, use
Kn
in the first round,
Kn-1
in the second round, and so on until
K1
is used in the last round. This is a nice feature because it means we need not implement two different algorithms for encryption and decryption.
Given the potential vulnerability of DES to a brute-force attack, there has been considerable interest in finding an alternative that uses longer keys and that is resistant to cryptanalysis. Several algorithms have emerged as popular choices and are being widely implemented.
Rather than totally re-inventing the wheel, virtually all contemporary
conventional-block encryption algorithms use the basic Feistel block structure. This structure is well understood and it is therefore easier to determine the cryptographic strength of a new algorithm. If an entirely different structure were used, the new structure could have subtle weaknesses not immediately apparent to the designer.
Triple DES
The most widely-used alternative to DES is a variant of DES known as triple DES. DES is highly resistant to the known forms of cryptanalysis, so it makes sense
to use DES as a building block for longer-key algorithms. Triple DES preserves the existing investment in software and equipment, and operates by passing the data to be encrypted through three stages of DES
(Figure 3)
. The data is first encrypted with one key by passing it through the DES encryption algorithm. Then, the data is passed through the DES decryption algorithm using a second key. Finally, the output of the second stage is passed through DES encryption again using either a
third key or a repetition of the first key. In the former case, the total key length is 168 bits, and in the latter, the key length is 112 bits.
Triple DES with two keys is a relatively popular alternative to DES and has been adopted for use in the financial key management standards ANS X9.17 and ISO 8732. A number of Internet-based applications have adopted three-key triple DES, including PGP and S/MIME, both of which are popular e-mail security applications.
IDEA
The International Data Encryption Algorithm (IDEA) is a symmetric block cipher developed by Xuejia Lai and James Massey of the Swiss Federal Institute of Technology in 1991. IDEA uses a 128-bit key and differs markedly from DES both in the round function and in the subkey generation function. For the round function, IDEA does not use S-boxes. Rather, IDEA relies on three different mathematical operations: XOR, binary addition of 16-bit integers, and binary multiplication of 16-bit integers. These
functions are combined to produce a complex transformation that is very difficult to analyze and hence very difficult to cryptanalyze. The subkey generation algorithm relies solely on the use of circular shifts, but uses these in a complex way to generate a total of six subkeys for each of the eight rounds of IDEA.
Because IDEA was one of the earliest of the proposed 128-bit replacements for DES, it has undergone considerable scrutiny and, so far, appears to be highly resistant to cryptanalysis. IDEA is
used in PGP (as one alternative) and is also used in a number of commercial products.
Blowfish
Blowfish was developed in 1993 by Bruce Schneier, an independent consultant and cryptographer, and quickly became one of the most popular alternatives to DES. Blow-fish was designed to be easy to implement and to have a high execution speed. It is also a very compact algorithm that can run in less than 5k bytes of memory. An interesting feature of Blowfish is that the key length is variable and can be
as long as 448 bits. Blowfish uses 128-bit keys and sixteen rounds.
Blowfish uses S-boxes and the XOR function, as does DES, but also uses binary addition. Unlike DES, which uses fixed S-boxes, Blowfish uses dynamic S-boxes that are generated as a function of the key. The subkeys and the S-boxes are generated by repeated application of the Blowfish algorithm itself to the key. A total of 521 executions of the Blowfish encryption algorithm are required to produce the subkeys and S-boxes. Accordingly,
Blowfish is not suitable for applications in which the secret key changes frequently.
Blowfish is one of the most formidable conventional encryption algorithms implemented so far. Both the subkeys and the S-boxes are produced by a process of repeated Blowfish applications. This thoroughly mangles the bits and makes cryptanalysis very difficult. So far, there have been a few papers published on Blowfish cryptanalysis, but no practical weaknesses have yet been found. Blowfish is used in a number of commercial
applications.
RC5
RC5 was developed in 1994 by Ron Rivest, one of the inventors of the public-key algorithm RSA. RC5 was designed to have the following characteristics:
•
Suitable for hardware or software.
RC5 only uses primitive computational operations commonly found on microprocessors.
•
Speed.
To achieve this, RC5 is a simple algorithm and is word oriented. The basic operations work on full words of data at a time.
•
Adaptable to processors of
different word lengths
. The number of bits in a word is a parameter of RC5. Diff-erent word lengths yield different algorithms.
•
Variable number of rounds.
The number of rounds is a second parameter of RC5. This parameter allows a trade-off between higher speed and higher security.
•
Variable-length key.
The key length is a third parameter of RC5. Again, this flexibility allows a trade-off between speed and security.
•
Simplicity.
RC5’s simple structure is
easy to implement and lightens the task of determining the algorithm strength.
•
Low memory requirement.
A low memory requirement makes RC5 suitable for smart cards and other devices with restricted memory.
•
High security.
RC5 is intended to provide high security with suitable parameters.
•
Data-dependent rotations.
RC5 incorporates rotations (circular bit shifts) whose amount is data dependent. This appears to strengthen the algorithm against cryptanalysis.
CAST-128
CAST is a design procedure for symmetric encryption algorithms developed in 1997 by Carlisle Adams and Stafford Tavares of Entrust Technologies. One specific algorithm developed as part of the CAST project is CAST-128, which makes use of a key size that varies from 40 bits to 128 bits in 8-bit increments. CAST is the result of a long process of research and development and has benefited from extensive review by cryptologists. It is beginning to be used in a number of products, including PGP.
CAST uses fixed S-boxes, but ones that are considerably larger than those used in DES. These S-boxes were carefully designed to be nonlinear and resistant to cryptanalysis. The subkey-generation process used in CAST-128 is different from that employed in other conventional block encryption algorithms. The CAST designers made the subkeys as resistant to known cryptanalytic attacks as possible and felt that the use of highly nonlinear S-boxes to generate the subkeys from the main key provided this
strength. Another interesting feature of CAST-128 is that the round function,
F
, differs from round to round, again adding to cryptanalytic strength.
DES is no longer a viable choice for encryption. The 56-bit key can be found in a matter of days with a relatively inexpensive cracker machine. A number of alternative algorithms have been implemented and deployed in various applications. All of these appear to have good cryptanalytic strength and remain invulnerable to brute-force attack.
William
Stallings is a consultant, lecturer, and author of over a dozen books on data communication and computer networking. This article is based on material in the author’s latest book,
Cryptography and Network Security
, Second Edition (Prentice-Hall, 1998). His home in cyberspace is http://www.shore.net/~ws and he can be reached at ws@shore.net.
Puzzled by a network processing design issue?
