Meeting Report: "Developing the Advanced Encryption Standard"

[Bruce Schneier <schneier@counterpane.com>]

                           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.

/s/  Bruce Schneier

************************************************************************
* Bruce Schneier            2,000,000,000,000,000,000,000,000,002,000,
* Counterpane Systems       000,000,000,000,000,000,002,000,000,002,293
* schneier@counterpane.com  The last prime number...alphabetically!
* (612) 823-1098            Two vigintillion, two undecillion, two
* 101 E Minnehaha Pkwy      trillion, two thousand, two hundred and
* Minneapolis, MN  55419    ninety three.
* http://www.counterpane.com
************************************************************************