Bruce Schneier's 27 March 1997 Letter to NIST

27 March 1997

Director, Computer Systems Laboratory
Attn: FIPS for AES Comments
Technology Building, Room A231
National Institute of Standards and Technology
Gaithersburg, MD 20899

RE: Advanced Encryption Standard

Dear Mr. Director:

This letter is in response to your request for comments on the proposal to develop a FIPS for an Advanced Encryption Standard (AES). As author of Applied Cryptography and cryptography consultant to dozens of different hardware and software companies, I feel I have a good inkling of what the commercial community needs from an AES.

In general, I think it is an excellent idea for NIST to oversee the development and adoption of a standard enryption algorithm to replace DES. While DES is an excellent encryption algorithm, its key length is clearly too small for today's security needs. The commercial security community is unlikely to converge on a single replacement algorithm on their own, and a new NIST standard will go far to increase public confidence in cryptography.

I agree that the AES should be a publicly defined algorithm, but I hesitiate to require it to be a block cipher. I find that most of my clients are satisfied with triple-DES if they need a block cipher. The biggest hole in my array of good algorithms is a fast stream cipher with a low gate count. Stream ciphers can probably run about ten times faster than comparible block ciphers; it makes more sense for triple-DES to continue to be used for applications where a block cipher is required, and that the AES address the bulk-encryption problem with a suitable stream cipher.

If a block algorithm is required, I suggest requiring a 128-bit block. The current generation of 64-bit block ciphers are becomming more and more vulnerable to attacks based on the block size.

I agree that the AES should have a variable key length and implementable in both software and hardware. However, I strongly feel that any government-endorsed algorithm should be available free for all uses, like DES is. Patented algorithms should not be considered, unless the patent-holder is willing to grant free world wide rights as IBM did with DES.

With regards to your factors for judging, the issues are far more subtle than your list indicates. "Computational efficiency" and "hardware and software suitability" are very complex metrics. You have to differentiate between the time required to set up a key with the time required to encrypt an amount of plaintext after key setup. Some algorithms have very efficient key-setup routines; others are very slow. This efficiency and suitability also depends strongly on the type of processor. An AES will be used on platforms ranging from 8-bit microprocessors on smart cards to 64 bit Alpha workstations, as well as platforms that haven't been developed yet. On hardware, speed is often a function of gate count. Algorithms can often run very quickly if they are implemented in a large number of gates, and slowly if they are implemented in a small number of gates.

I feel that efficiency should be judged on slow 8-bit platforms. The desktop machines are getting faster every year; almost any algorithm is efficient on those platforms. I recently wrote a paper on fast implementations of algorithms on Pentium machines; the number of clock cycles required for encrypting a single block of plaintext (20 clocks per byte encrypted for Blowfish; 24 clocks per byte encrypted for CAST) were remarkably close. A factor of 4 or 5 is not very much when processor speeds double every 18 months. The low end, however, will always be with us, and it is constrained both in processor power and available RAM. And as cryptography becomes more of a consumer item, it will find its way more into the low end.

Hardware efficiency should be judged on the basis of flexibility: the algorithm should be implementable in both small-gate-count and large-gate-count variants, with appropriate variances in speed.

In any case, there should be clearly-defined minimum acceptability requirements for efficiency. I suggest the following:

  • Encryption no slower than DES on any platform (e.g. at most 360 clock cycles per block on a Pentium).
  • Key setup no more than 5 times the speed to encrypt one block.
  • Encryption and decryption speeds within 10% of each other.
  • Implementable in hardware with a total table size of less than 256 bytes.
  • Hardware enryption throughput of one block per clock cycle (given enough gates), with a maximum encryption/decryption 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.
  • Software implementation should favor little-endian machines.

With regards to your draft submission requirements, I suggest that you provide standard function calls in ANSI C that the software implementation should conform to. This will greatly simplify comparison testing, by providing a standard interface for comparison. These calls should test bulk encryption as well as key-setup.

You should also require test vectors (possibly a standard suite) that can be used to verify any implementation of the algorithm, as well as a copyright-free reference implementation. And in addition to a cryptanalysis of the algorithm, you should require an explanation of the design rationale.

Finally, I think we need to think more about the process of evaluation. Assuming you are looking to choose an algorithm in 1998, any set of candidates will only get a year or so of analysis before a choice is made. Unless you are sure that an existing block cipher with more than a couple-years' analysis (i.e. triple-DES, IDEA, Blowfish, RC5, Khufu, CAST, and SAFER) meets your requirements, this is far too short a time to develop and analyze a new algorithm. Perhaps it might be smarter to adopt triple-DES as a short-term fix, and spend the next few years developing a completely new algorithm for long-term use.

The benefits of this approach is that we can then develop an algorithm with all sorts of useful features not generally present in the list of algorithm suggested above:

  • Both block modes and a stream modes, with the stream modes at least five times faster than the block modes.
  • A standard hash-function mode. (While I understand that SHA-I is NIST's standard for hashing, many hardware modules cannot afford the silicon necessay to implement SHA-1. If they are already using AES, they will want to use it for hashing as well.)
  • A standard MAC (Message Authentication Code) mode.
  • A mechanism for improving the algorithm, in the field, in the event that an unforseen weakness is discovered after approval.
  • Variablility in the algorithm to provide a family key for different applications. (Sometimes companies want their algorithm to be proprietary in some way; it makes sense to give them a harmless way to do this.)

In any case, you should consider finding a panel of cryptanalytic experts to quickly weed out bad candidates, spending money on public cryptanalysis of the top contenders, and offering bounties for successful cryptanalyses of top contenders. I suspect you will get many algorithms that are not worthy of serious consideration, and eliminating them quickly will allow the serious contenders to receive more analysis.

I applaud your efforts to develop a new encryption standard, and I look forward to attending your AES Criteria Workshop on 15 April 97 to futher discuss these issues.

Sincerely,

Bruce Schneier

Report and commentary on the 15 April 97 NIST meeting
Schneier's 26 April 97 letter to NIST
Why NSA Should Submit an AES Candidate
Twofish (Counterpane's AES candidate)

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..