How were the AES key and block length subsets of Rijndael selected?

Question

My intuition tells me it's a trade off between speed and security, but how did the standardisation process select these three seemingly arbitrary key lengths (namely, AES-128, AES-192, AES-256).

Answer 1

Prompted by Paŭlo's comment, I took a look at the original requirements set out for the AES candidates. A useful page for that turns out to be AES - The Early Years (1997-98) on the NIST web site (and surprisingly hard to find there; the internal links are broken and Google doesn't find it either).

The AES key lengths were specified in the original Request for Candidate Algorithm Nominations for the AES published in the Federal Register on September 12, 1997, in section 3, Minimum Acceptability Requirements (emphasis original):

"The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits. A submitted algorithm may support other key-block sizes and combinations, and such features will be taken into consideration during analysis and evaluation."

So where did those key/block size combinations come from? In the earlier notice Announcing Development of a Federal Information Processing Standard For Advanced Encryption Standard, posted in the Federal Register on January 2, 1997, the "proposed draft minimum acceptability requirements and evaluation criteria" include:

"A.3 AES shall be designed so that the key length may be increased as needed."

This proposed requirement received many comments, and was discussed in the AES workshop on April 15, 1997. Bruce Schneier, in his notes on the workshop, writes:

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

Apparently, the three key sizes and one block size specified in the NIST minimum requirements, and later in the AES standard, were selected at least in part based on those discussions.

Ps. I've seen it claimed, e.g. by Thomas Pornin in this answer, that the three key lengths "exist mostly to satisfy some US military regulations which call for the existence of several distinct 'security levels'". The notes and comments cited above strongly suggest to me that this probably wasn't the only reason for the decision to require multiple key lengths, although it could certainly have been one reason. In any case, if anyone can actually point to the specific regulations that require these distinct security levels (assuming they're publicly available), I'd be interested in seeing them.