28 March 1999. Thanks to Tim Skorick.
Tim Skorick
This is a draft of a letter to be sent to the AES Round One Committee. Comments, criticisms, and unsolicited adulation are welcome at tskorick@hotmail.com
Introduction
It has come to my attention that some in AES selection circles are pondering the notion of selecting multiple ciphers for implementation as an Advanced Encryption Standard. In this little missive I will contend that a) the problems giving rise to this suggestion are hardly problems (or can hardly be effectively dealt with), b) that the means thus far suggested to achieve a multiple algorithmic AES must necessarily weaken and dilute the strength of the AES, and c) there are several very good reason why a multiple cipher AES is a very bad idea.
Some of the more commonly expressed problems with a unique AES (and why they are unjustified fears or fears that can't be adequately dealt with):
1. A single AES selection stands more of a chance of being cryptanalyzed in the future than multiple choices (the "future resiliency" argument).
This is a valid point in certain respects. While I'm not certain how realistic this fear of imminent cryptanalysis really is (based on the effort toward same that has created the strongest candidate ciphers), more importantly, none of the methods for achieving "future resiliency" really accomplish anything save to dilute the "Standard" in AES. I will explain why I believe this later.
2. Along the same lines as (1), several AES winners of the same type would be useless if the type was later found to have a fundamental flaw.
This is just "what-iffing" the situation to death. The example that Don Johnson brings up is Feistel networks. Considering that several of the strongest candidates are based on Feistel networks, the discovery of a fundamental flaw in same would negate all this work. But according to this "what-if" fear, several ciphers might equally probably be found to be based on weaknesses in the distant future. The NIST must choose a cipher based on what it *currently* understands its strength to be (Feistel networks can be very sound cryptographic foundations, hence their popping up everywhere).
3. Programmers need more ciphers in their crypto toolkit to use for different purposes, including hybrid algorithm solutions. The "one size fits all" may not fit everyone's needs.
This is in no way related to what's going on here. I can't even imagine why this was brought up. The selection of a single AES might promote the use of it exclusively by some, but in no way is this exclusive use mandated. I can't think of a single cryptographic toolkit that only uses DES. Also, a multiple-algorithm AES foists this rather unusual implementation on all programmers who want to use AES. This point is essentially pointless.
4. Malicious cryptanalysts (?) would be less encouraged to attack several algorithms than just one since diffusion of targets makes their cost/benefit ratio less attractive.
Again, I find no basis for this in reality. But more to the point, this suggestion begs the question as to why we are doing this in the first place. The whole point of this process is to choose a standard algorithm which is strong enough to function in this role as "the standard" for a long time and to be widely distributed for use as such. The people who select this cipher are charged with the duty of weeding out those ciphers whose weaknesses are exploitable on a level more efficient than a brute force attack. If they do their job correctly, fear of what cryptanalysts will do is not a factor. This point suggests more a lack of trust in the selection body than anything else.
More succinctly, if NIST decides it has to select a few different algorithms to discourage malicious cryptanalysts rather than just one, replace those in the selection body with people who can discern just one *strong* one.
The commonly expressed ways in which multiple AES selections would solve the above "problems:"
1. Multiple AES selections would promote "future resiliency" by way of selecting cipher finalists based on diversity rather than merit alone. NIST would a) choose only a few ciphers from each type to fill a certain finalist quota and b) select ciphers from each type based on strong performance in a designated function to avoid weeding out already cryptanalyzed algorithms who are strong in the designated areas (?).
This is nothing more than thinly-disguised cryptographic affirmative action. This AES standards committee exists for the purpose of selecting an algorithm based on merit alone. "A" would negate this purpose by forcing the discard of algorithms in favor of others based on their diversity rather than merit. This is fundamentally bad judgement. "B" makes it even worse by tossing aside strong algorithms and allowing *flawed* algorithms to stay in the contest just because they are different from the others, and even then ensure only the possibility of future resiliency through diversity.
Regardless whether or not a candidate cipher performs up to par in a certain area, the responsibility of the selection committee remains to choose the cipher that is strongest in all areas. The folly of NIST tolerating bad cryptography in its Advanced Encryption Standard is self explanatory no matter what the situation.
2. Multiple AES selections would allow programmers to have more algorithms to choose from in their crypto toolkit.
Again, I doubt that there is even one proficient cryptography programmer who has only DES in his toolkit. The criteria that the algorithm submissions had to meet in order to be selected as candidates was stringent enough that the winner will be selected because it is strongest in all areas. We are looking for an Advanced Encryption Standard, not a list of Advanced Encryption Suggestions.
3. Multiple AES selections would discourage malicious cryptanalysis by creating target diffusion, making it more expensive to build AES cracker machines because they would have to deal with several algorithms.
Any cracking machine designed to brute force an AES algorithm is going to have the same amount of key space to work on despite the algorithm chosen. Again, avoid settling on a weak algorithm, and cryptanalysts can be invited to do their worst.
Some specific arguments against multiple AES selections:
1. The implementation costs. It is doubtful that distributed multiple AES standards will be used as such since they will cost more to implement than is acceptable (esp. considering the improbability of the dangers that the multiplicity is supposed to guard against). The risk factor doesn't seem to call for that kind of expense, although to be fair this judgement is more accurately made by those doing the implementing. While, as I will reiterate soon, programmers are free to use whatever algorithm they see fit, one of the goals of selecting a standard is to encourage its use on a broad level. Making this too costly a task for most programmers will encourage them to rather fall back on ciphers with a less expensive implementation scheme.
2. Implementation complexity. Another self explanatory point. I believe that the complexity of implementing multiple standard algorithms might possibly be an even greater deterrent to their acceptance than cost. While, as I said before, programmers are free to use whatever algorithm they see fit, one of the goals of selecting a standard is to encourage its use on a broad level. Making this too complicated a task for most programmers will encourage them to rather fall back on ciphers with a simpler implementation scheme.
3. The probability of using the less secure cipher. Schneier, in his Rome comments on day two, is quoted by Georgoudis as saying that "if there were two AES ciphers and you used one bit of the key to chose one of them, then half the time you would use a less powerful cipher." Georgoudis, ever the optimist, points out that then half the time the more secure cipher would also be used. I would contend that, in the selection of a standard algorithm, 50% probability of weakening encryption is unacceptable in the extreme. This is just another reason why the AES will fall into disuse if it foists multiple ciphers (and possibly weak ones) on programmers.
4. Diminished trust in multiple ciphers. When due discussion, analysis and cryptanalytic effort is divided amongst multiple winning ciphers rather than one, confidence will lessen in the ciphers accordingly. One naturally has more confidence in one algorithm unsuccessfully attacked by three cryptanalysts than in three algorithms unsuccessfully attacked by one cryptanalyst each. Again, this is bound to diminish the widespread acceptance and use of the AES.
Conclusion
I understand the nature of the future resiliency problem and how it might apply the selection of the AES. However, I don't believe it is a realistic enough problem to warrant the dilutive and weakening multiple AES measures proposed thus far. Furthermore, I believe that multiple AES selections will increase the complexity and cost of use while diminishing the security and trust in them, short-circuiting the desired width and breadth of potential use.