Why NSA Should Submit an AES Candidate

The National Institute of Standards and Technology has recently solicited candidate algorithms for the Advanced Encryption Standard (AES), the follow-on algorithm to DES. They have asked for a 128-bit block cipher that accepts key lengths of 128 bits, 192 bits, and 256 bits. Candidates will be judged on security, efficiency, and flexibility, and NIST hopes to have a new standard ready by the end of the century.

There has been a lot of debate, both within the NSA and without, as to what role that organization should play in the standard selection process. I think they should submit a candidate algorithm. Some of my reasons are self-serving—as a cryptographer I’d love to see what they come up with—but others are more pragmatic.

1. We need at least one good candidate.

It seems unlikely that we won’t get any good candidates, but it is possible. NIST is asking for a 128-bit block cipher; all the academic research so far has been on 64-bit ciphers. The deadline is June 15, 1998, just a few months away. It’s possible that none of the candidates will be just what we need.

In the United States government, we keep our cryptographic expertise inside the NSA. The NSA has been spending tax dollars on cryptography research for fifty years; it doesn’t make sense to squander that expertise. The AES process is one where we need all the cryptographic expertise we can get our hands on. Not asking the NSA to submit is just plain wasteful.

If there are no good candidates and the NSA doesn’t submit, we have nothing. If there are good candidates, it doesn’t really matter if the NSA submits one. If there are no good candidates and the NSA does submit, then they did the right thing. Given that we want a good AES, it makes sense for the NSA to submit.

2. The NSA can save money by using AES in their systems.

There is an increasing trend to use commercial-off-the-shelf products for military security, especially for non-battlefield environments. The commercial market will drive economies of scale that the NSA can take advantage of, assuming AES meets their needs. For the AES to suit the NSA, there must be an AES candidate that fulfills those requirements. And because commercial and academic submitters don’t have the same focus as the NSA, if there is to be an AES candidate that will fulfill the NSA’s requirements, only the NSA can design and submit it.

3. The NSA might be the only organization that can give us the AES we need.

The AES will be with us for twenty years and will be used in applications we can’t even imagine. NIST’s decision to compare performance on 32-bit microprocessors will, in a few years, seem as quaint as standards designed for the IBM PC-AT. Anything will look good in five years, as microprocessor speeds increase by a factor of 10 and data widths double at least once. The high end always gets better, but the low end never disappears. Eight-bit microprocessors are still with us: in smart cards and embedded applications. Sure we’ll see 32-bit smart cards in 20 years, but by then the 8-bit machines will be even smaller: smart drug capsules, smart staples, who knows?

And every cryptographic application is different: this one needs fast throughput, this one needs fast key setup, this one needs low gate count. The AES will be used on 8-bit smart cards, on 32-bit computers, on 64- (or even 128-) bit computers. It will encrypt short packets and gigabit data streams, and it will be used as a hash function, MAC, and pseudo-random number generator. If a single algorithm has to suit everybody, it has to be a really good one.

NIST is not asking for a stream-cipher standard because we know how to make a stream cipher out of a block cipher. This is true: we also know how to make a block cipher out of a stream cipher, and a hash function out of either. We can make a larger block cipher out of a smaller one, and a longer key-length block cipher out of a shorter one. If all that matters that we can construct one primitive out of another, we might as well stick with DES.

What none of these constructions are is efficient.

DES was designed in the mid-1970s for 4-bit custom silicon chips. It’s inefficient in software, especially on 32-bit microprocessors. It’s not terrible-current implementations use 64K or more of RAM and cruise along pretty quickly-but nowhere near as fast as algorithms designed Pentium-class machines. DES will work on anything, if you throw enough RAM, enough clock cycles, enough precomputation, or enough gates at it, but it isn’t optimized for anything.

I need bulk encryption at a few clock cycles per byte on high-end microprocessors. I need implementations in a few hundred gates. I need implementations in less than 200 bytes of RAM. I need implementations for switching systems, where encrypting two blocks with two keys is just as fast as encrypting them with the same key.

I’m not convinced that the academic community can design an algorithm as flexible as the AES needs to be. I’d like the NSA to take a crack at it. (Actually, what I’d like is a toolbox full of algorithms, but I’m not going to get that.)

4. The NSA could use the public relations boost.

There are those that won’t trust an NSA submission simply because it is an NSA submission. Point taken, but we shouldn’t be held hostage by those people. The paranoid will not accept anything from the NSA, be it an algorithm or an analysis. They’re also likely to find conspiracies in every submission: Is a British submission secretly from their government? Is the author planning on selling a secret cryptanalysis of his submission to the Russian Mafia? Am I secretly on the NSA payroll?

The rest of us believe that the NSA will not accept a weak algorithm, that they will-like DES-ensure that the algorithm is secure against cryptanalysis that is not yet public. We think that the NSA has capabilities, both in design and analysis, that may be different than what has been published.

If the NSA is going to participate in the AES process at all, the paranoid minority will accuse them of ulterior motives and back-room dealings. The best defense is a good offense. The NSA should participate in the evaluation process. They should participate in the submission process. They should participate in the AES process.

If the NSA submits an algorithm, they are joining the public cryptography world on an equal footing with everyone else. Regardless of the outcome, the NSA’s participation is a plus.

up to Advanced Encryption Standard (AES)

Sidebar photo of Bruce Schneier by Joe MacInnis.