Meeting Report:

"Developing the Advanced Encryption Standard" Workshop

15 April 1997
by Bruce Schneier

NIST held a workshop to discuss the proposed Advanced Encryption Standard (AES) today. About 70 people, from government and industry, attended. Specifically, the workshop was convened to discuss the minimum acceptability requirements, evaluation criteria, and submission requirements for the AES. First my report, and then some opinion.

Miles Smid presented NIST's goals for AES. They wanted a strong encryption block encryption algorithm for government and commercial use, one that would support "standard codebook modes" of encryption, "significantly more efficient than triple DES," and with a variable key size.

Smid then summarized the comments and their proposed responses. Thirty-three comments (via paper and e-mail) were received in response to the 2 January 1997 Federal Register. These comments were all distributed at the workshop.

Responses to comments on the "Minimum Acceptability Requirements and Evaluation Criteria." (Please note that these responses are only "proposed responses," and are not the official responses of NIST.)

1. NIST agrees that all unclassified analyses will be made public, and encourages that the mathematical rationale behind algorithms be presented along with the algorithms.
2. NIST prefers a block cipher to a stream cipher because it would be compatible with DES, and because existing standards specify block modes. Still, they are open to a discussion on stream ciphers. (They got a lot of discussion, but seemed to ignore it.) They are also open to block sizes larger than 64 bits. (The general consensus was 128 bits.) They would prefer to have a single algorithm in AES, as opposed to a family of algorithms (this prompted discussion as well).
3. NIST is open to a discussion on key length: whether it should be a single large keylength or a variable keylength. NIST also "intends to recognize triple-DES when it becomes an ANSI standard." NIST wants the AES to offer significant advantages over triple-DES. (They said this over and over. Their opinion was that if the process just recognized triple-DES, then it wasn't really worth bothering.)
4. NIST pointed out that requiring both hardware and software implementations precluded the submission of algorithms that could be implemented only in hardware. (Remember the security restrictions imposed on Skipjack.)
5. Regarding patent-free implementations, NIST strongly prefers a royalty-free world-wide implementation. They will accept patented algorithms, but will heavily favor royalty-free algorithms.
6. Comments on the judging criteria: Regarding security, NIST strongly encourages a public explanation of the rationale behind any constants or tables, and a statement of the work factor required to attack the algorithm; they will judge all attacks below the work factor for practicality. Regarding computational efficiency, NIST will favor efficiency on 32-bit processors and short key-setup time, will test efficiency on a little endian processor, and will publish the specs of the test system. They also encourage two submissions: reference (possibly in Java) and optimized (in C). Regarding memory requirements, NIST will measure memory requirements for C implementation on a single reference platform (presumably a Pentium Pro), although submitters are welcome to provide results for other platforms. Regarding hardware and software suitability, NIST believes that the primary applications for the AES are for large processors (although they would "value" flexibility to run on 8-bit processors), and do not believe that they can require hardware gate-count values from submission. Regarding simplicity, NIST intends to evaluate algorithms on their simplicity of design (is there a rationale, or is the algorithm just a hodge-podge?) and implementation. Regarding flexibility, NIST received many conflicting comments on the value of flexibility versus the value of fixing parameters. NIST intends to evaluate algorithms on their ability to implement on differing platforms for various applications. They will consider defining a standard interface for testing. Regarding variant algorithms, they worry about the difficulty of analysis and the loss of compatibility; they assume the number of rounds would be fixed for any given key size.
7. NIST agrees that AES will be used for 20-30 years, that security is more important than efficiency or flexibility, and that efficiency is of equal importance to flexibility. They have no control over export control laws, and will comply with any export control laws. The design should be for a strong algorithm, regardless of the legal climate. NIST reiterated that the AES should be at least as secure as triple-DES.

Jim Foti provided proposed responses to comments on the "Proposed Draft Submission Requirements." NIST will specify block and key sizes, and will encourage submitters to include design rationale. They will ask for a reference implementation as well as an optimized implementation (suitable for a IBM-compatible Pentium PC running Windows 95 with 16MB of RAM). They will ask for efficiency estimates for various platforms, including bytes/sec for encryption, decryption, and key setup, as well as gate counts and memory requirements for hardware implementations. They would like a graph with a plot of speed versus memory. They will require a suite of test vectors to ensure all implementations of the algorithm are correct, and a statement regarding possible patent issues (legal issues may be appropriate). They will require a list of any known weak or equivalent keys, complementation properties, etc., a mathematical rationale for any items that could hide a trap door, and a reference list of any publications that discuss cryptanalysis of the algorithm. NIST will not accept proprietary submissions (with the possible exception of the optimized implementation). The submitter must agree to waive copyright on submitted materials (again, with the possible exception of the optimized implementation). And the submitter must provide a statement of expected strength of the algorithm, with supporting rationale. Of course submissions from outside the U.S. would be welcome.

Ed Roback discussed the selection process. We've had the draft criteria and submission requirements (1/2/97), the public comment process (closed on 4/2/97), and the workshop on criteria and submission requirements (today). NIST estimates that it will take three months to prepare a public call for submissions, which they will publish in the Federal Register. The call for submissions would be closed after four to six months. Then, they would take about two months to review submissions for completeness and correctness (not security), and then they would publish everything and invite the public to review and analyze the algorithms. There would be some workshop early on in the process where the submitters could campaign for their particular algorithm. After about 6 months, though would be an interim workshop where people could comment on the algorithms. (NIST doesn't plan on funding cryptanalysis, or offering prizes our bounties for successful cryptanalysis.) NIST would think about this for a while (three months), and would then publish a list of narrowed candidates (exactly how narrowed is unknown). After another six to nine months of public comments, there would be a final workshop. Then, NIST would review everything (about two months) and publish a draft FIPS. Another three months for comments on the draft FIPS, a month to revise the draft, and then the Secretary of Commerce approves the FIPS. Times are approximate (of course), but NIST expects the process to take "well over two years." It was pretty much universally thought that this schedule is wildly optimistic.

NIST doesn't know if this algorithm will be a replacement for DES, or an alternative to DES with higher security. With DES and triple-DES so entrenched, it will be impossible to migrate to AES quickly. (Remember that the NIST standard only applies to U.S. Government systems, although they are often used in broader contexts.)

Discussion followed. All the pre-lunch arguments were about block and key size. Block sizes of 64 bits and 80 bits were quickly eliminated, as was a 64-bit keysize. People wanted variable keysizes of some subset of 128, 192, 256, or even 512 bits, and block sizes of either 128 bits or 128 and 256 bits. There was no discussion of stream ciphers, or using block ciphers as hash functions.

NIST has a hard time figuring out how to measure hardware efficiency. They'd like to have definitive metrics (like there will be for software) but are unwilling to force submitters to provide VHDL code, or gate counts, or whatever.

NIST talked about what to do about "tweaking" algorithms after submission. What if a break is found, but a simple fix prevents the attack? What if someone submits an algorithm and someone else proposes a tweak? These questions were not answered.

They also debated whether or not the optimized implementation of the algorithm could be proprietary. Pros are that it encourages clever implementations, and implementations from people other than the inventor. Cons are that it withholds information from the public, and that it doesn't allow independent verification of proprietary implementations. One halfway proposal was to make optimized implementations public, but allow owners to retain copyright. The audience seemed to prefer that optimized implementations be kept secret by NIST.

There were further discussions on the legal issues. When do the inventors give up their rights to the algorithm? What rights, exactly, do they give up? What about patents that an inventor might unknowingly infringe upon? What is an inventor submits an algorithm and then, a year and a half later, tries to pull it out of the process? It was almost universally agreed that these are hard questions.

And in a final show of hands, ten people admitted that they were "thinking of submitting an algorithm."

Editorialization time....

Before I showed up, the major question in my mind was whether this was a serious attempt to develop a secure encryption algorithm to replace DES, or just another red herring by the government to keep us busy while they go on eavesdropping. Now I believe that the NIST representatives at the meeting are sincere, but I still don't know how they fit in a larger context

This is serious business. Any algorithm proposed in 1997 won't be approved until at least 2000. It will be a standard for 20-30 years, in legacy systems for at least another ten, securing data that might need to be secured for another 20. This means we are trying to estimate security in the year 2060. I can't estimate security ten years from now, let alone 60. The only wise option is to be very conservative.

I'm not sure that NIST knows what it wants. Technically, a FIPS is only for government use, but NIST would like everyone to use it. Communities like banking are likely to adopt a FIPS right out of the box; other organizations will view a U.S. Government standard with suspicion. Still, NIST needs to decide if they want this AES to be all things to all people, or a specific encryption algorithm to satisfy a specific set of requirements. Everyone in the audience had different ideas about this.

The audience was a mix of government agents, corporate representatives, academics, and random yahoos. Of course, the random yahoos talked for more than their share. My worry is that NIST will get many more submissions than they bargained for; I think that every random yahoo is going to submit his pet algorithm. NIST hopes the community will be able to quickly separate the random stupid algorithms from the serious submissions, but I am less sure that politics will allow NIST to. Assuming a 128-bit block requirement doesn't preclude everything already done, I urge companies with patented or patent-pending algorithms to give up royalties and submit their algorithms. I assume CAST (royalty-free from Northern Telcom), SAFER (royalty free from Cylink), Blowfish (unpatented), and Square (unpatented) will be submitted; I would also like to see RC5 from RSADSI, IDEA from Ascom-Systec, and Khufu from Xerox. Failing that, I would like to see new submissions out of the various cryptographic research institutions. The yahoos are going to submit regardless; we need at least a small pile of quality algorithms.

But is there enough time for people to invent strong 128-bit block ciphers? Probably not. One alternative is to take existing 64-bit block ciphers, and then use a 4-round Luby-Rackoff construction to create a 128-bit block variant. Another is to give people more time. Both were talked about. I would like them to approve triple-DES as an interim standard, and then take all the time they need for a secure 128-bit block cipher.

So now we wait for the call for submissions.

Schneier's 27 March 97 letter to NIST
Schneier's 26 April 97 letter to NIST
Why NSA Should Submit an AES Candidate
Twofish (Counterpane's AES candidate)

Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.