Bruce Schneier's 26 April 1997 Letter to NIST
26 April 1997
Director, Computer Systems Laboratory<br/Attn: FIPS for AES Comments
Technology Building, Room A231
National Institute of Standards and Technology
Gaithersburg, MD 20899
RE: Advanced Encryption Standard (AES)
Dear Mr. Director:
This letter is to offer additional advice subsequent to the 15 April 1997 meeting at NIST, “Developing the Advanced Encryption Workshop.” I appreciate your institute’s efforts to develop an AES, and am pleased that you recognize the importance of this task.
Much of the discussion at the 15 April meeting centered around the “Minimum Acceptability Requirements” and the “Evaluation Criteria” for the AES. These are important metrics: good Evaluation Criteria will ensure that the best algorithm is selected as the AES, while good Minimum Acceptability Requirements will limit the submissions to high-quality ones.
At the meeting you repeatedly stated that you intend that AES will be a standard for 20-30 years. To me, this means that the algorithm will be used in legacy applications for at least another ten, securing information that may be required to be confidential for yet another ten. Assuming we have a standard approved by the year 2000, the AES must be secure through the year 2050.
We need to look at AES requirements with this in mind.
Clearly, any algorithm approved for the AES must be secure. The difficulty will be choosing among several secure algorithms. In this letter, I would like to ignore the important problem of deciding if an algorithm is secure (and if it will remain secure through the year 2050), and concentrate on the non-cryptographic requirements.
At the meeting we discussed both flexibility and efficiency: what they mean, how important they are, and how to compare.
Evaluating encryption algorithms on 32-bit processors such as the Pentium seems short-sighted for such a long-lasting standard. Just as the DES, designed for dedicated hardware in the mid 1970s, is inefficient on any modern processor, any AES designed for today’s computer architectures will be inefficient on whatever is used 20 years from now.
That isn’t much of a problem, though. Programmers have spent long hours optimizing DES for different architectures. And computing power still doubles every eighteen months: any algorithm becomes ten times faster just by waiting five years. Everything is fast on the 64-bit DEC Alpha.
The difficulty is in the low end: embedded systems, smart cards. The lesson of the past 20 years of computing seems to be that while the high end always gets better, the low end never goes away. We’re still programming tiny 8-bit microprocessors; instead of being used in desktop computers, they’re in cellular phones, automobiles, electrical meters, and smart cards. These processors will be around for a long time to come, in Dick-Tracy-like wristwatch communicators, small affixable processors (Micron is building the technology), and who knows what else (nanotechnology?).
The AES should be efficient on the low-end processors that are around today, and be scalable to 16-, 32-, and 64-bit processors. And think fast; almost anything written today is faster than triple-DES (see table below). Encryption at 16 clock cycles per byte; that takes real work.
| Algorithm Name | Clock Cycles per Byte Encrypted on a Pentium |
|---|---|
| SEAL (stream) | 4 |
| RC4 (stream) | 7 |
| Blowfish | 18 |
| Khufu | 20 |
| RC5 (16 rounds) | 23 |
| DES | 45 |
| IDEA | 50 |
| Triple-DES | 108 |
With this in mind, I propose a set of Minimum Acceptability Criteria that pushes the envelope of current encryption algorithms:
- A variable key, supporting (at least) a 128- and 256-bit key .
- Both block modes and a stream modes, with the steam modes at least five times faster than the block modes.
- Block modes with a 128-bit block.
- A standard hash-function mode.
- A standard MAC (Message Authentication Code) mode.
- Variability in the algorithm to provide a family key for different applications.
- Encryption speeds (in clock cycles per byte encrypted):
- No more than 64 on an 8-bit smart card with a 128-bit key.
- No more than 32 on a 16-bit processor with a 128-bit key.
- No more than 16 on a Pentium, Pentium Pro, PowerPC, or DEC Alpha with a 128-bit key.
- No more than double with a 256-bit key on any platform.
- Encryption and decryption speeds within 10% of each other.
- Key setup no more than 5 times the speed to encrypt one block for a 128-bit key, and no more than 10 times encryption speed for a 256-bit key.
- Implementable in hardware with a total table size of less than 256 bytes.
- Hardware encryption throughput of one block per clock cycle (given enough gates), with a maximum latency of 16 clock cycles.
- Minimum RAM requirements (RAM only, not code or tables) of no more than 64 bytes on an 8-bit smart-card processor.
- Minimum table size of no more than 256 bytes on an 8-bit smart-card processor.
These requirements are not easy to meet. As far as I know, no published block cipher meets them all (although some come close in many areas). But requirements such as these will challenge the world’s cryptographic research organizations to create something useful.
I know you realize that the selection process will take several years to complete. Therefore, I urge you to approve triple-DES as an interim standard. This will satisfy users who need a 64-bit block cipher for compatibility reasons, while allowing you the time required to choose and approve the best AES you can.
I applaud your efforts in this matter, and I look forward seeing your call for submissions in the Federal Register
Sincerely,
Bruce Schneier
up to Advanced Encryption Standard (AES)
Sidebar photo of Bruce Schneier by Joe MacInnis.