AES Comments

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

At 12:27 PM 4/26/97 -0500, Bruce Schneier wrote to NIST about their
proposals for an Advanced Encryption Standard (AES) FIPS:

>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 .
One of Bruce's comments is that any algorithm picked today will
probably be around until 2040-50; if computer speeds double every year,
then the marginally useful strength by then will be about 110-120 bits.
While it's nice to have an expandable key structure that will let you
increase the strength by then, 128 bits is really still strong enough,
and a fixed-keylength algorithm that's still workable in triple-mode 
should work just fine.
>		No more than double with a 256-bit key on any platform.
Allowing triple opens the field a lot, and by the time you need >128-bit keys,
machines will be so blazingly fast that a 50% difference won't matter much;
you'll still be able to encrypt that 1Gbps 3D video in real time.

>	Encryption speeds (in clock cycles per byte encrypted):
>		No more than 64 on an 8-bit smart card with a 128-bit key.

How fast do you really need, in seconds, for typical smart-card apps?
64 cycles at 1MHz is 16000 bytes/second; 128 cycles is 8000 bytes/second.
How fast are most smartcards?  1MHz?  2MHz?  500kHz?
The main uses I can see for 8-bit crypto processing are
- cheap, large-volume crypto for uncompressed voice (needs 8000 bytes/sec)
- adding crypto to digital phones ( ~800-1660 bytes/sec )
- money cards (if you're not using public-key, maybe you need 100 bytes,
	so 8000 bytes/sec is 1/80 sec transaction?)
- ATM machines (which typically have 4800-bits/sec data connections,
	== 600 bytes/sec, and often have 16-bit processors.  Even DES works.)

>		No more than 16 on a Pentium, Pentium Pro, PowerPC, or DEC
>		Alpha with a 128-bit key.
Which interestingly knocks out Blowfish (18 cycles), Khufu (20), and RC5 (23),
and the only things faster are SEAL and RC4 stream-only cyphers.
It's a tradeoff between forcing the development and testing of
cutting-edge speed, which may cost you in strength, vs. supporting a
bunch of existing algorithms we're starting to understand.
If it takes an extra 2 years to develop new algorithms,
you've doubled computer speed, so you could use the 17-32-cycle algorithms
you're rejecting today.....

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

If this is the ulterior motive for requiring faster-than-current algorithms,
I'm all for it (:-)  Triple-DES is boring, slow, and just fine for most
applications.

#			Thanks;  Bill
# Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
# You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp
#     (If this is a mailing list, please Cc: me on replies.  Thanks.)