[292] in cryptography@c2.net mail archive
Advanced Encryption Standard
daemon@ATHENA.MIT.EDU (Bruce Schneier)
Mon Feb 24 13:11:08 1997
Date: Mon, 24 Feb 1997 11:07:03 -0500
To: cryptography@c2.net
From: Bruce Schneier <schneier@counterpane.com>
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. Steam 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 cocks 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.
=46inally, 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 steam 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 analys=01=00-P=00=00=00=00=00=00=140=
=01=01CPour efforts
=00=9CT evelop a new encryption standard, and I look forward to attending yo=
ur
AES Criteria Workshop on 15 April 97 to futher discuss these issues.
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
************************************************************************
