From: Bruce Schneier <schneier@counterpane.com>
Date: Sat, 26 Apr 1997 10:28:12 -0700 (PDT)
To: cypherpunks@toad.com
Subject: AES Comments
Message-ID: <v03007802af87eb708bce@[206.11.192.175]>
MIME-Version: 1.0
Content-Type: text/plain


26 April 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 (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.


				     Clock Cycles per
		Algorithm	     Byte Encrypted
		Name		     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.  Therefor, 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

************************************************************************
* 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
************************************************************************