Bruce, an independent software developer and author of Applied Cryptography: Protocols, Algorithms, and Source Code in C (John Wiley & Sons, 1994), presented a paper at the Cambridge workshop. Bruce can be contacted at 708-524-9461 or [email protected].
In December 1993, the Cambridge Algorithms Workshop, hosted by the Cambridge University Computer Laboratory, brought together leading figures in the field of encryption who presented, examined, and challenged new encryption algorithms designed to run quickly in software. The reasoning behind the focus on encryption is that constructing algorithms which are both fast and secure is the core problem of classical cryptology. However, recent developments, such as differential attacks on block ciphers and correlation attacks on stream ciphers, have forced cryptanalysts to rethink classic encryption algorithms such as those in Table 1. At the same time, the need for fast, efficient, and safe encryption at the application level has increased--DES (even triple-DES) may be fast enough for e-mail, but it's too slow for emerging high-bandwidth applications.
The goal of the conference, therefore, was to propose new algorithms capable of encrypting data at a dozen or so clock cycles per byte for the emerging class of high data-rate applications.
In this article, I'll cover the conference highlights and examine the current state of encryption technology in general. For specifics on the workshop, the proceedings will be published later this year by Springer-Verlag as part of their Lecture Notes in Computer Science series. (Call 201-348-4033 for availability.) Additionally, many of the topics and algorithms touched upon in this article are discussed in my book, Applied Cryptography (John Wiley & Sons, 1994).
The Algorithms
In all, ten complete algorithms were presented at the Cambridge Algorithms Workshop, all secret-key, not public-key algorithms like Diffie-Hellman, RSA, and the U.S. Government's Digital Signature Standard (DSS). (For more on public keys, see "Untangling Public-Key Cryptography," DDJ, May 1992.)
Jim Massey presented SAFER, a 64-bit block cipher with a 64-bit key. It is designed for implementation on simple processors on smart cards and only uses addition and multiplication mod 256, and exponentiation and logarithms in the multiplicative group of GF(257). Although Massey originally developed SAFER for Cylink Inc., the company has decided to place this algorithm in the public domain in the hope that it will become the new standard for software encryption. This algorithm will probably be important. In fact, former Soviet cryptanalysts in Yerevan, Armenia have been--without success--trying to break SAFER for over a year.
Matt Robshaw of RSA Data Security presented a fast block cipher based on the same principles as the MD5 one-way hash function (see my article, "One-Way Hash Functions," DDJ, September 1991). Robshaw's algorithm, designed jointly with Burt Kaliski, operates on large blocks--1024 bytes--but the principles can be used to design ciphers with smaller block sizes. It is also likely to be important, as RSA Data Security provides encryption technology to companies such as Microsoft, Lotus, IBM, Novell, and Apple.
Phil Rogaway presented SEAL, a new stream cipher developed jointly with Don Coppersmith, IBM's top cryptographer. This algorithm will be used by IBM for software encryption of disk files in PC-based network software. The algorithm is based on repeated lookup of large tables of pseudorandom numbers.
Hugo Krawczyk of IBM presented implementation and performance details of the Shrinking Generator, which he also designed with Don Coppersmith and first presented at Crypto '93. (See "The Shrinking Generator," Advances in Cryptology: CRYPTO '93 Proceedings, Springer-Verlag, in preparation.) The Shrinking Generator is a simple stream cipher which uses the output of a linear-feedback shift register to decimate the output of another linear-feedback shift register.
Markus Dichtl of Siemens presented a derivative of the Shrinking Generator which combines the output of linear-congruential generators rather than linear-feedback shift registers.
Ross Anderson of Cambridge University presented a modern rotor machine. Rotor machines were all the rage in cryptography before algorithms moved to computers. The German Enigma was a rotor machine, as were several U.S. cryptography machines. They have fallen out of fashion recently, but this algorithm is an attempt to show that they can still be secure in the face of massive computing power. Anderson's proposal is for a rotor machine driven by a linear-feedback shift register; it is simple to describe and to implement, and yet seems to be very secure.
David Wheeler, also of Cambridge, proposed a bulk-encryption algorithm based on experience designing algorithms for secure digital telephones. It is based on iterating functions defined by large lookup tables of random permutations, and can perform ultra-fast encryption of large amounts of data.
My own Blowfish algorithm is a 64-bit block algorithm with a variable-length key. (See "Blowfish: A New Encryption Algorithm," on page 38 of this issue.)
William Wolfowicz (of the Italian telephone company's research lab) presented a 64-bit block algorithm with a 128-bit key which was designed jointly with Adina di Porto. The algorithm makes use of a novel permutation property pointed out by the Russian number theorist Vinogradov.
Joan Daemen presented 3-WAY, a new block cipher he's been developing with colleagues at Leuven, Belgium for two years. It is designed to be fast in both hardware and software, and to resist both differential and linear cryptanalysis attacks.
The fastest algorithm appears to be either Wheeler's or Rogaway-Coppersmith's. Both use about 20 instructions (including four table lookups) to encrypt a 32-bit word: about five clock cycles per byte. On a SparcStation, they had throughput of about 20 Mbytes/second; on a DEC Alpha, about 100 Mbytes/second. However, many of the other algorithms are not far behind.
It is too early to tell if any of these algorithms are secure. The important thing is that they are out there and that cryptanalysts are starting to examine them. I expect at least two of them to fall before the end of the year. (It would be unfair to divulge which I think are insecure.) The techniques used to break them will be recycled into the design of new encryption algorithms, which may then be broken using new techniques. And so the cycle of research will continue.
Hopefully, in five or six years there will be a few algorithms that are still considered secure. These may then be proposed as standards to replace DES and then used to encrypt data far into the next century.
Designing Secure Algorithms
If nothing else, the Cambridge workshop proved that fast, efficient, and safe encryption algorithms are as difficult and challenging to design as ever. The rules of algorithm design are simple. An encryption algorithm should be secure under the following conditions:
- The cryptanalyst (that's the guy trying to break the algorithm) knows all the details of the algorithm. He has some ciphertext, and his job is to deduce the plaintext. (This is called a "ciphertext-only" attack.)
- The cryptanalyst not only has the algorithm and some encrypted ciphertext, but also the unencrypted plaintext. His job is to deduce the key. (This is called a "known-plaintext" attack.)
- The cryptanalyst not only has the algorithm, some ciphertext, and the unencrypted plaintext, but he gets to choose what it is. If there is a particular plaintext sequence that, if encrypted, will easily yield the key, he gets to encrypt that sequence. (This is called a "chosen-plaintext" attack.)
The Skipjack algorithm remains classified and is implemented in the supposedly tamper-resistant Clipper chip. When Intel came up with a new reverse-engineering technique which they thought might beat the tamper protection, the NSA promptly classified it. Even so, the algorithm is probably resistant to analysis even if its details become known. (The primary reason that NSA does not want to release the inner workings of Skipjack is probably because they don't want their secret techniques used to design other high-security algorithms.)
Cryptographers also have to assume that analysts have access to enormous amounts of computing power--more computing time than can be optimistically expected during the next 100 years or so. In the face of all these conditions, the algorithm should still be unbreakable.
Key Length
Key length is a poor measure of the security of an algorithm, but it's a good place to start. Algorithms with long keys are not necessarily secure, but algorithms with short keys are definitely insecure.
For instance, earlier this year Michael Weiner presented a design for a brute-force DES cracker (see "Efficient DES Key Search," Advances in Cryptology: CRYPTO '93 Proceedings, Springer-Verlag, in preparation). He didn't just do some theoretical calculations, but went through the entire design process. He designed a custom cracking chip down to the gate level and had his in-house fabrication department estimate fabrication costs. He designed a controller board, had its cost estimated, and designed and priced peripheral hardware (power supplies, racks, and a complete mechanical housing). What Weiner determined was that with a $1 million machine, he could break DES in three-and-a-half hours. This is cheap enough to hide in the budget of several different government agencies. It's even cheap enough to be considered by large corporations or organized-crime syndicates. (His employer, Bell Northern Research, claims to have no interest in building a working model.)
This work has important implications for algorithm design. There's nothing special about DES; the analysis will be similar for all algorithms. 56 bits is too small for a key; even 64 bits is too small. Even 80 key bits is marginal--only enough for short-term security. Any algorithm proposed today should have a key length of at least 128 bits; see Table 2.
These calculations are based on present-day computers. For future projections, plan on computing power doubling every 18 months. Each of the above numbers becomes an order of magnitude smaller every five years: A $1 billion machine that takes 6.7 years to break a key today will take 0.67 years (8 months) with 1999 technology and 0.067 years (24 days) with 2004 technology. What is secure now might not be in 50 years. In light of these calculations, Skipjack's 80-bit key seems woefully inadequate.
Key length is also critical for export. The U.S. Government does not permit the export of algorithms with key lengths greater than 40 bits. (Yes, some exportable algorithms appear to have longer key lengths, but the effective key length is 40 bits or less.) Various computer-privacy advocates are trying to change this.
Some of the algorithms presented at the Cambridge workshop had variable-length keys. This is especially desirable because it allows the implementor to define his own level of security. If he has to export the algorithm, the implementor can set the key length at 40 bits. For low-grade security (information that only has to remain secret for a few minutes), you can use 64 bits. If you need long-term security, you can use key lengths of 128 or even 256 bits.
Variable-length keys were generally constructed during a "key-expansion phase" of the algorithm. Generally, there was an initial bit of computation required before the algorithm could encrypt any data. During this computation, the key typed in by the user would be expanded into a large set of subkeys used for encryption. DES does this to some degree; the 56-bit key is expanded into an array of subkeys totaling 768 bits. Some algorithms at the Cambridge workshop took this to an extreme, expanding a key into subkey arrays totaling 1 Kbyte of data or even more.
Differential and Linear Cryptanalysis
Of course, the trick to algorithm design is to make sure that a brute-force attack is the most efficient way of getting the key, although for most encryption algorithms, there are other ways. These methods, generally very complex and mathematical, involve exploiting the structure of the algorithm.
Differential cryptanalysis and linear cryptanalysis are two new attacks that have been successfully used against DES and other algorithms. Differential cryptanalysis was invented by Biham and Shamir in 1991 (see Differential Cryptanalysis of the Data Encryption Standard, by E. Biham and A. Shamir, Springer-Verlag, 1993), while linear cryptanalysis was invented by Mitsuru Matsui in 1993 (refer to "Linear Cryptanalysis Method for DES," Advances in Cryptology: CRYPTO '93 Proceedings, Springer-Verlag, in preparation). Differential cryptanalysis is a chosen-plaintext attack: It looks at differences between pairs of plaintexts and corresponding pairs of ciphertexts. These differences, along with information about the structure of the underlying algorithm, give an analyst clues about the key. Collect enough of these differences, and you can find the key more efficiently than you would with brute force.
Don't get too excited, though. The best chosen-plaintext differential cryptanalysis attack against DES has a complexity of 247. This is better than the 256 required for brute force, but requires on the order of 10 terrabytes of chosen-plaintext data. Although interesting, it is still more theoretical than practical. The best way to attack DES is still brute force.
Linear cryptanalysis is similar to differential cryptanalysis, but looks for linear relationships between selected bits of the plaintext, ciphertext, and key. Against DES, this attack has a complexity of 243. Even better, it is a known-plaintext attack. However, it still requires much too much data to be practical.
Now that these attacks are known, there are techniques for optimizing encryption algorithms so that they are resistant to them. Most of the algorithms presented at the workshop took these attacks into account during the design process; see Table 3.
Cascading Multiple Algorithms
One way to increase the security of your system is to chain multiple algorithms together. For example, first encrypt your file with DES and one key, and then with IDEA (see "The IDEA Encryption Algorithm," by Bruce Schneier, DDJ, December 1993) and another key. The result will be much stronger than using either of the two algorithms individually.
Cascading multiple algorithms might also be the best way to negotiate security with algorithms that some people don't trust. If Alice and Bob want to communicate with each other and don't trust each other's algorithms, they can use both--first her algorithm, and then his. This idea, suggested by Whitfield Diffie, was discussed at the Cambridge workshop.
This sounds good, but there is a problem: Massey and Maurer proved that a cascade of multiple algorithms is at least as strong as the first or, with stream ciphers, at least as strong as the best (see "Cascade Ciphers: The Importance of Being First" by Maurer and Massey, Journal of Cryptology, 1993). The difficulty with proving anything more than this is that a bad guy might provide you with a first algorithm which twisted your plaintext around so as to provide a chosen-plaintext attack on the second algorithm which you supplied.
This applies not just to encryption algorithms, but to any process designed by someone else which you incorporate into your system. In fact, the widely used CELP code (which compresses digital speech to modem speeds) was designed by the NSA, and for all anyone knows it could be acting as a cryptanalyst's helper in some subtle way. It does seem though, that a cascade of algorithms is better than individual algorithms, provided that the second and subsequent algorithms are secure against chosen-ciphertext attacks, and provided all the algorithms' keys are independent.
The real benefit of cascading algorithms is in design diversity; it makes the overall system less vulnerable to a cryptanalytic attack. Both triple-DES and IDEA seem secure today, but there is always the possibility that some clever mathematician might come up with a good attack against one of them tomorrow. Using triple-DES, then a fast stream cipher such as Wheeler's algorithm, and then IDEA, would be immune to new attacks against any one of the three algorithms. Successful attacks against all three would be required to break the cascaded system.
Conclusion
Encryption algorithms are like airplanes. It's easy to design one, but it's hard to design one that flies. To make matters worse, it's hard to tell if any one of them is any good. The only real way to test the security of an algorithm is to let other programmers try breaking it. But even if the algorithm survives years of intense analysis by many different people, you can still only hope that it is really secure.
Table 1: Block-encryption algorithms. IDEA is used for message encryption in Pretty Good Privacy; PGP. RC2 was developed by RSA Data Security and is used in a variety of commercial software packages. Skipjack is the NSA-developed algorithm in the Clipper chip. GOST is an algorithm developed in the Soviet Union and only recently made public.
Key Block
Length Length Problems
------------------------------------------------------------
DES 56 bits 64 bits Key too small
Triple-DES 112 bits 64 bits Slow
Khufu 64 bits 64 bits Patented; key too small
FEAL 32 64 bits 64 bits Patented; key too small
LOKI-91 64 bits 64 bits Weaknesses; key too small
REDOC II 160 bits 80 bits Patented
REDOC III variable 64 bits Patented
IDEA 128 bits 64 bits Patented
RC2 variable 64 bits Proprietary
Skipjack 80 bits 64 bits Secret algorithm
GOST 256 bits 64 bits Not completely specified
MMB 128 bits 128 bits Insecure
Table 2: Key length and security in 1994.
Key Time for a $1M Time for a $1B Length Machine to Break Machine to Break --------------------------------------------------- 40 bits 0.2 seconds 0.0002 seconds 56 bits 3.5 hours 13 seconds 64 bits 37 days 54 minutes 80 bits 2000 years 6.7 years 100 bits 7 billion years 7 million years 128 bits 1E+18 years 1E+15 years 192 bits 1E+37 years 1E+34 years 256 bits 1E+56 years 1E+53 years
Table 3: Cryptanalysis of DES.
Attack Type Complexity Brute-force Known-plaintext 2^55 Differential Known-plaintext 2^55 Differential Chosen-plaintext 2^47 Linear Known-plaintext 2^43
Copyright © 1994, Dr. Dobb's Journal