Public Comments Regarding The Advanced Encryption Standard (AES) Development Effort Round 2 Comments [in response to a notice in the September 15, 1999 Federal Register (Volume 64, Number 178; pages 50058-50061)] Updated comments will be posted at http://csrc.nist.gov/encryption/aes/round2/pubcmnts.htm. Commenter (#) (MM/DD/YYYY) Page (If a comment was submitted on behalf of an organization, the organization’s name is listed first; otherwise, the individual commenter’s name is listed first.) John Savard (1) (08/10/1999) 3 John Savard (2) (08/10/1999) 5 Casey Sybrandy (08/18/1999) 6 John Macdonald (09/01/1999) 7 David Oshel (1) (09/23/1999) 8 John Eichler, CertifyIt, Inc. (1) (09/27/1999) 9 Cornelius Sybrandy, Concurrent Technologies Corp. (1) (09/28/1999) 10 Cornelius Sybrandy, Concurrent Technologies Corp. (2) (09/28/1999) 11 JP, Patterson Programming (1) (09/29/1999) 12 John Eichler, CertifyIt, Inc. (2) (09/27/1999) 14 JP, Patterson Programming (2) (09/30/1999) 16 JP, Patterson Programming (3) (10/1/1999) 17 Doug Whiting, Hi/fn (1) (10/05/1999) 18 Don Johnson, Certicom (1) (10/15/1999) 20 Matthew Fisher (10/26/1999) 21 Lars Knudsen, University of Bergen, Norway (10/27/1999) 26 Albert Yang (11/01/1999) 27 Ted Goldstein, Brodia.com (11/16/1999) 28 Ron Rivest, Matt Robshaw, Lisa Yin (11/29/1999) 29 Jeffrey Streifling (1) (12/05/1999) 31 Eva Bozoki, PATCO (12/26/1999) 34 Eric Boesch (12/27/1999) 35 Roger Schlafly (01/11/2000) 36 Lily Chen, Motorola (01/14/2000) 38 Yasuyoshi Kaneko, Telecom. Advancement Org. of Japan (01/17/2000) 39 Frank Constantini, L-3 Communications (01/26/2000) 41 Chip McGrogan, L-3 Communications (01/26/2000) 42 Nick Weaver (1) (02/18/2000) 43 Craig Partridge, BBN Technologies (1) (03/14/2000) 45 Craig Partridge, BBN Technologies (2) (03/14/2000) 46 August Zajonc (03/16/2000) 48 Manfred Spraul (03/20/2000) 49 Simon Esmaili (03/21/2000) 50 Gideon Samid, D&G Sciences (04/09/2000) 51 Storage Technology Corp., Jim Hughes (04/15/2000) 52 Robin Lee Powell (04/17/2000) 53 Nick Weaver (2) (04/17/2000) 54 Mark Atwood (04/17/2000) 58 Hironobu Suzuki (04/18/2000) 59 Frank Burkhardt (04/18/2000) 60 Rob Neal (04/18/2000) 61 Anne Anderson (04/18/2000) 62 Rob Gerlach (04/18/2000) 63 Patrick Gardella, Whetstone Logic, Inc. (04/18/2000) 64 Kevin Bealer (04/19/2000) 65 Simson Garfinkel (04/18/2000) 66 Keyur Mithawala (04/19/2000) 67 Jim Gopinathan, ATMEL Smart Card ICs (04/19/2000) 68 Dr. Tom Holroyd (04/20/2000) 69 Ray Van De Walker, R.G. Van De Walker, Inc. (04/20/2000) 70 Dave-aes@bfnet.com (04/20/2000) 71 Douglas Gwyn, U.S. Army Research Laboratory (04/21/2000) 72 Kenneth Broll, MyProof.com (04/23/2000) 73 Sid Sidner, ACI Worldwide (04/24/2000) 74 Dan Stromberg (04/25/2000) 75 Brent Kelly, Computer Sciences Corp. (04/26/2000) 76 Nick Weaver (3) (04/27/2000) 77 David Eppstein, UC Irvine Dept. of Info. & Comp. Sci. (04/29/2000) 79 Anping Li (05/02/2000) 80 Mike Lake, Wordcraft Int’l Ltd. (05/04/2000) 81 Jeffrey Streifling (2) (05/04/2000) 82 Greg Rose, Qualcomm Australia (05/07/2000) 85 Gideon Yuval, Microsoft (05/08/2000) 86 David Oshel (2) (05/09/2000) 87 Joan Daemen, Vincent Rijmen (05/10/2000) 88 Carlisle Adams, Entrust Technologies Ltd. (05/11/2000) 89 Ross Anderson, Eli Biham, Lars Knudsen (05/11/2000) 90 Sam Simpson, MIA Ltd. (05/12/2000) 91 R. Venkatesh, Tata Infotech Ltd. (05/12/2000) 95 Hĺvard Raddum, University of Bergen, Norway (05/12/2000) 97 Simon Wigzell, Orc Software (05/12/2000) 98 David Oshel (3) (05/12/2000) 99 Paulo Barreto (1) (05/14/2000) 100 Paulo Barreto (2) (05/14/2000) 102 Niels Ferguson, Bruce Schneier, David Wagner, Doug Whiting (05/14/2000) 104 Brian Wong (05/14/2000) 106 Tom Phinney (U.S. Tech. Advisor for IEC/SC65C), Honeywell (05/14/2000) 107 David Crick (05/14/2000) 110 Yaro Charnot, Identikey (Australia) Pty Ltd (05/15/2000) 113 Ali Selcuk, Univ. MD Baltimore County (05/14/2000) 116 Ken Tindell (05/15/2000) 117 Scott Contini (05/16/2000) 118 Intel Corp. Network Communications Group, Jesse Walker (05/15/2000) 119 Doug Whiting, Hi/fn (2) (05/15/2000) 124 Don Johnson, Certicom (2) (05/15/2000) 125 RSA Laboratories, Burt Kaliski (05/15/2000) 127 Rich Schroeppel (05/15/2000) 128 John Worley, Hewlett Packard Labs (05/15/2000) 150 Mattias Lenartsson (05/15/2000) 151 Ralph Hoefelmeyer, Next Generation Network Security Services (05/15/2000) 152 Dag Arne Osvik, University of Bergen, Norway (05/16/2000) 153 Don Johnson, Certicom (3) (05/16/2000) 155 From: "John Savard" To: Subject: Comments on MARS Date: Tue, 10 Aug 1999 13:53:39 -0600 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.72.3155.0 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3155.0 10245-151st Street Edmonton, Alberta CANADA T5P 1T6 (780) 444-3599 The choice of MARS as one of the five candidate ciphers to proceed to Round 2 of the AES process has surprised a number of people, as they have viewed that particular block cipher as inelegant or unwieldy. I do not find the choice of MARS as a finalist surprising, as I consider security to be the most important characteristic that the block cipher chosen as the AES must have, and I think the unique design of MARS, with its unkeyed forward mixing and unkeyed reverse mixing stages will indeed help to protect MARS against future attacks. I also note that several candidates, of which MARS is the only one to proceed to Round 2, had minor changes proposed for them. The changes proposed to MARS are claimed to make it harder to invert the key schedule and determine the original key from the subkeys. This will be useful in connection with what follows. An obvious naive criticism of MARS is that, since the forward mixing and reverse mixing stages of MARS are unkeyed, they do not seem to contribute as much to its security as they should for the amount of processing they involve. The rationale behind these stages being unkeyed, is, of course, a reasonable and understandable one. If the subkeys used for keying these stages contain information about the subkeys used for the cryptographic core stages of MARS, they could, however unlikely it may seem, provide a basis for an attack on MARS. At least, the presence of such subkeys would make the analysis of MARS much more complicated, creating uncertainty about its security. If the mixing stages were keyed, I envisage that they would be keyed as follows: the copy of the 32-bit subblock used to index into the four S-boxes, before being used for that purpose, would be replaced by itself XOR a subkey. This would require 16 additional subkeys. Let us designate them as subkeys 40 through 55, with subkey 40 used in the first forwards mixing round, and so on (i.e., subkey 48 would be used in the first reverse mixing round). To remove the concerns associated with placing the mixing stages under the control of the key, it would be sufficient to ensure that there is no way to determine the other 40 subkeys from the 16 subkeys used for that purpose. I propose that the subkey generation process of MARS (as it now stands, after the "tweak") be modified as follows to achieve this. After the generation of subkeys 30 through 39, the elements of the temporary array with 15 elements (T[0] through T[14]) are to be modified as follows: T[0] = T[0] xor subkey 6 T[1] = T[1] xor subkey 8 . . . T[11] = T[11] xor subkey 28 and T[12] = T[12] xor subkey 1 T[13] = T[13] xor subkey 2 T[14] = T[14] xor subkey 3 This uses only subkeys generated in iterations preceding the final one, and excludes the subkeys modified for use in multiplication, and provides additional non-invertibility. (This is only one of several possible alternatives. One could perform no extra step, and rely on the non-invertibility existing in the present key generation algorithm, or one could seek to achieve greater non-invertibility through more elaborate measures, for example involving performing a MARS encryption of a constant with the subkeys generated so far, the other new subkeys being zero.) Then, two additional iterations of the process used to generate subkeys in groups of 10 will be performed (the first one with j=4, the second with j=5; it may be advisable to change "4i+j" to "8i+j" in the description of the key generation process to accomodate this) but each time only the first 8 additional subkeys will be used. If this key schedule is seen as adequate to avoid introducing additional attacks, this modification of MARS would ensure that all the steps in a MARS encryption make their full contribution to its security. John J. G. Savard From: "John Savard" To: Subject: MARS Date: Tue, 10 Aug 1999 16:22:03 -0600 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.72.3155.0 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3155.0 10245-151st Street Edmonton, Alberta CANADA T5P 1T6 (780) 444-3599 In a previous communication, I suggested the following: (begin quote) I propose that the subkey generation process of MARS (as it now stands, after the "tweak") be modified as follows to achieve this. After the generation of subkeys 30 through 39, the elements of the temporary array with 15 elements (T[0] through T[14]) are to be modified as follows: T[0] = T[0] xor subkey 6 T[1] = T[1] xor subkey 8 To: AESround2@nist.gov Date: Wed, 18 Aug 1999 05:19:42 -0700 From: " " X-Sent-Mail: off X-Mailer: MailCity Service Subject: AES Algorithm Selection X-Sender-Ip: 147.160.10.21 Organization: My Deja Email (http://www.my-deja.com:80) One thing that should be considered is how well an algorithm is suited for Palm Pilots and such. One question could be which is cheaper, memory or hardware multipliers? If memory is cheaper, Rijndeal or Twofish may be very suitable. If hardware multipliers are cheaper, then RC6 is your best bet. As for MARS and Serpent, I am not sure about either along these lines. I have not looked at Serpent in depth and MARS requires both a multiplier and memory. Casey Sybrandy --== Sent via Deja.com http://www.deja.com/ ==-- Share what you know. Learn what you don't. From: jmm@elegant.com (John Macdonald) Subject: AES criteria To: AESround2@nist.gov Date: Wed, 1 Sep 1999 18:52:42 -0400 (EDT) Cc: jmm@elegant.com X-Mailer: ELM [version 2.4 PL23] It has been suggested by Bruce Schneier in his Crypto-Gram newsletter that comments on cryptographic requirements from users is as important for your consideration as the mathematical analysis of the particular algorithms that are being considered. I work for a small company (<20 people, < $10M annual sales) that licenses distributed system adminstration programs. This is a natural for using cryptography: - protect info in transit that deals with security repated issues - authorize remote control and update of the distributed facets For our purposes, there are 3 criteria that are important. The first two are relevant to your contest: (1) encryption must be in software: our code runs on many different Unix platforms, we don't want to deal with providing hardware interfaces to those many different platforms and we can't be requiring customers to be adding and maintaining hardware to their systems (2) it must be reasonably efficient on workstation-class machines These two requirements are ones that you are seem to be targetting well with your current process. Please continue to treat them as important. Our third criteria is unfortunately outside your mandate: (3) we can't afford to treat foreign sales differently, or to have any extra paperwork. Export controls mean that we use trivial encryption instead of any serious encryption. We cannot afford to have a secure US/Canada release of our software and a separate unsecured release for the rest of the world. Applying for export licenses for each foreign sale would be even worse. While this final requirement is not within your mandate, it means that we, like most other small companies, will be unable to make use of the winning candidate. -- objects: | John Macdonald Think of them as data with an attitude. | jmm@elegant.com X-Sender: doshel@soli.inav.net Date: Thu, 23 Sep 1999 22:01:28 -0500 To: AESRound2@nist.gov From: "David C. Oshel" Subject: I am pro-Rijndael -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I tend to be pro-Rijndael because it is royalty-free, Belgian (i.e., it has a politically neutral provenance, unlike the U.S. and Euro corporate or U.S., English, Israeli, etc. national contributions), appears extremely competent and is frankly very easy to implement. I intend to consider Rijndael seriously in those few applications I may work on that benefit from competent obfuscation, regardless of how the AES competition turns out. Although the competition is interesting, I feel the practice will tend to be based on less formal, indeed, even irrelevant, considerations than the cryptology has been so far. David C. Oshel dcoshel@pobox.com Cedar Rapids, Iowa http://pobox.com/~dcoshel/ ``Tension, apprehension and dissension have begun.'' - Duffy Wyg& in Alfred Bester's _The Demolished Man_ -----BEGIN PGP SIGNATURE----- Version: PGPfreeware 6.0.2i for non-commercial use iQA+AwUBN+rplvxWvgP9KeXyEQLsaQCRAWejb9yWlTAXzWbgYSk5ttVecACcDl9Z occpqPJFGEZcxwrNBgLuv2U= =fCeo -----END PGP SIGNATURE----- From: certifyit@alltel.net Date: Mon, 27 Sep 1999 09:37:34 -0500 X-Mailer: Mozilla 4.61 [en] (WinNT; U) X-Accept-Language: en To: AESround2@nist.gov Subject: Intellectual property concerns with AES To: NIST I recently went to look at some software concerning one of the finalist candidates for the AES. From reading what was on the NIST web site, I assumed that such software would be in the public domain. What I found was that the software I downloaded contained copyright notices. I sent an e-mail message asking about this to an author of the algorithm and got back a one sentence response saying simply "I don't know". This did not seem to me to be a very adequate response to my inquiry. What concerns me is that the finally decided upon algorithm, while itself might be free of patent/copyright constraints as per NIST requirements, might have "efficient"/"optimal" software/hardware implementations still protected by such patent/copyright holders. I believe this should be of concern to NIST also. What I suggest is that NIST formulates an approach similar to the GNU copyleft concept which is covering more and more software these days. (See http://www.fsf.org/ and more specifically http://www.fsf.org/copyleft/copyleft.html for more information on this type of protection.) This type of protection basically says that any implementation derived from any other implementation is still under the constraint of being fully open software. It seems to me that it would be beneficial for NIST to look into this matter more carefully to insure that after an AES algorithm is decided upon, it still remains free in all implementations for anyone to use. Sincerely, John Eichler CertifyIt@Alltel.net From: "Sybrandy, Cornelius" To: "'AESround2@nist.gov'" Subject: Adding additional rounds to make a cipher more secure Date: Tue, 28 Sep 1999 16:21:35 -0400 X-Mailer: Internet Mail Service (5.5.2448.0) There are circumstances where the addition of an extra round within a cipher is necessary for it's security. For example, if rc6 were suceptable to an attack that could break all 20 rounds, the addition of a 21st or 22nd round may be an option. However, because of the different designs of the algorithms, some have more rounds than others. Let's say that two algorithms, A and B run at the same speed. Algorithm A uses 20 rounds, while Algorithm B uses 8. Overall they run at the same speed, however each round of B takes much longer than a round of A. This means that if an extra round were added to B, it would have a more significant effect on the speed of the cipher than if one round were added to A. Since this is a simple way to make a cipher a bit more secure, this may be a point of consideration when deciding on an AES finalist. Cornelius A Sybrandy Concurrent Technologies Corporation 100 CTC Drive Johnstown, PA 15904 Phone: (814) 269-6587 "Imagination is more important than knowledge. Knowledge is limited. Imagination encircles the world." Albert Einstein From: "Sybrandy, Cornelius" To: "'AESround2@nist.gov'" Subject: AES and Palm Pilots or hardware Date: Tue, 28 Sep 1999 16:35:11 -0400 X-Mailer: Internet Mail Service (5.5.2448.0) One of the criteria for AES is that the selected algorithm performs well in smart-cards and other hardware solutions. One aspect of this is the cost of the hardware to accomodate the cipher. One example could be RC6 vs. Twofish. RC6 relies heavily on multiplications, which require relatively expensive multipliers. Twofish, on the other hand, uses two tables. If memory is more expensive, than RC6 should be used. If a multiplier is more expensive, than Twofish is used. Simply put, it's nice to see which algorithm is the fastest in hardware, but which one is the cheapest to implement in hardware or in products such as Palm Pilots. Cornelius A Sybrandy Concurrent Technologies Corporation 100 CTC Drive Johnstown, PA 15904 Phone: (814) 269-6587 "Imagination is more important than knowledge. Knowledge is limited. Imagination encircles the world." Albert Einstein From: "Patterson Programming" To: Subject: Re: Twofish Date: Wed, 29 Sep 1999 09:33:05 -0400 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.72.3110.1 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 To whom it may concern, I write to inform you of an issue regarding Twofish, one of the AES candidates. Having reviewed the paper by Counterpane Systems, I find that the key element used in the algorithm Twofish is virtually identical to the one I used in an algorithm of my own design. It is relevant to me because I provided a paper copy of a reference implementation of my algorithm LeapFrog to Mr. Schneier in the Fall of 1996. Note that the said algorithm was provided to him prior to the AES call for papers. The algorithm is not patented, but the reference implementation is registered with the U.S. Copyright Office. Ref: http://lcweb.loc.gov/copyright Registration numbers: TXu 763-698 and TXu 796-545. Reputable people would attest to the fact that deposits were sent to Counterpane Systems prior to the call for papers. As stated, the algorithm is not patented, I object to the fact that any reference to my design was, I believe, intentionally omitted from his papers. Note that while the two algorithms are not identical, and Twofish uses some elements not employed in my design, an unbiased look at the two designs (knowing that my design was seen by the designers of Twofish) should lead to questions. A simple example follows: From the S-box function in Twofish: y0 = q1[q0[q0[y2;0] Xor l1;0] Xor l0;0] y1 = q0[q0[q1[y2;1] Xor l1;1] Xor l0;1] y2 = q1[q1[q0[y2;2] Xor l1;2] Xor l0;2] y3 = q0[q1[q1[y2;3] Xor l1;3] Xor l0;3] (q0 and q1 are fixed permutations on 8-bit values) Ref: http://www.counterpane.com/twofish-paper.html From the main function in LeapFrog: * get the T variables T1 = A1(p1), T2 = A2(p2), T3 = A3(p3), T4 = A4(p4) * note the T variable order p5 = p5 Xor A1(A1(T2 Xor T3) Xor T4) p6 = p6 Xor A2(A2(T1 Xor T4) Xor T3) p7 = p7 Xor A3(A3(T4 Xor T2) Xor T1) p8 = p8 Xor A4(A4(T3 Xor T1) Xor T2) p5 = (p5 + T1) And FF p6 = (p6 + T2) And FF p7 = (p7 + T3) And FF p8 = (p8 + T4) And FF I find it interesting that the significant element of my design was employed in Twofish for both the key-expansion code and the main function. Also, the Twofish paper notes that using only random S-boxes would be about as secure as optimized boxes. And there are other references that lead me to believe that he was mentally trying to distinguish Twofish from LeapFrog. I may inform many individuals in the cryptographic community of my concerns and let them judge for themselves. I guess I should rename my algorithm Onefish, as it looks more like Twofish than Blowfish does. Please reply if you have any questions. Regards, jp Patterson Programming From: certifyit@alltel.net Date: Wed, 29 Sep 1999 13:21:30 -0500 X-Mailer: Mozilla 4.61 [en] (WinNT; U) X-Accept-Language: en To: AESround2@nist.gov Subject: Follow-up to Intellectual property concerns with AES To NIST, The following scenarios might indicate possible problems that could arise in the future. Scenario 1: A new Motorola microprocessor comes out with a feature that permits microprogramming an instruction which combines the exclusive OR operation with a shift such that I can effectively make a new "custom" instruction which then my software can take advantage of. I copyright my new "more efficient" code for the AES and offer to license it to anyone (for a fee, of course) who is interested in doing the job faster using that processor. Scenario 2: Philips introduces a new programmable logic array that is an eight-pin DIP chip which permits me to implement the AES algorithm in such a manner that I can process over 500,000,000 bytes per second. The chip sells for $1.95 in quantities of 100. Being astute, I want to patent my implementation and then sell the chip for $50.00 each to makers of all computers to incorporate on their motherboards. Scenario 3: The year is 2020 and the patent on the AES algorithm has long since run out. Two years ago the new quanta/quantum (i.e., light combined with certain a quantum-mechanic effects) process had been perfected. The new technology allows, depending on how many parallel units on the chip that are utilized, up to 5 trillion operations per second with a theoretical of 87.6 trillion operations per second possible. (Moore's Law just flew south!) NIST has openly admitted that the original AES algorithm is likely to fall with 2 years or sooner. People have started turning to "quad-AES" as an alternative that is predicted to last for at least another 25 years. The corporation that came up with the quad-AES scheme has patented their new scheme because of a unique twist (in a "stroke of genius") in the technique they use but under the covers, it still uses the old original AES encryption method just done multiple times. In scenarios like the above, the approach to just put the AES algorithm into the public domain may not cover the future use(s) of this algorithm properly. It is rather suggested that NIST licenses its use under something similar to the GNU licensing agreement where any further developments must, because they are based upon a licensing agreement, be done with making such developments available to everyone else under the same licensing agreement. The main point here is that either a patent and/or copyright may be used advantageously via the proper licensing agreement to insure the openness of use of the AES algorithm. Therefore it is suggested that NIST actually license this technology (in a similar manner to how NASA licenses its technology) to anyone who desires to utilize it. This approach, it is believed, better fulfills the "spirit" of what NIST is trying to accomplish. Sincerely, John Eichler CertifyIt, Inc. From: "Patterson Programming" To: Subject: Clarification of previous message. Date: Thu, 30 Sep 1999 09:46:26 -0400 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.72.3110.1 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Hello, I am writing to clarify one item regarding the message I sent you on 9/29/99 in reference to Twofish. Clarification: the only implementation of LeapFrog that was published was in: TXu 876-599. The original implementation (identified in my previous message) was used only to test the round function. The one listed in this message employs alterations to the key-expansion routine, as well as whitening. (to create a secure implementation) I am sure Counterpane Systems was sent a copy of the original papers, but I cannot verify that the revised implementation was sent. However, it is not relevant because the round function from LeapFrog that may have been generalized to Twofish has not been revised since 1996. It may not be important, but I wanted to advise you. Regards, JP Patterson Programming From: "Patterson Programming" To: Subject: Twofish Date: Fri, 1 Oct 1999 08:29:59 -0400 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.72.3110.1 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 X-MIME-Autoconverted: from 8bit to quoted-printable by email.nist.gov id IAA08950 Regarding Twofish and LeapFrog: Re-reading my posts regarding this issue, I suspect that some could make incorrect inferences from my statements. I may have reacted too strongly. I only wanted to point out that Twofish’s substitution stage using a parity function and compound look-ups is *not* a novel idea. (If that is what they meant in the Twofish paper) Cryptography is not my main interest, so please take my comments for what they are worth. Regards, JP Patterson Programming X-Sender: foti@csmes.ncsl.nist.gov X-Mailer: QUALCOMM Windows Eudora Pro Version 3.0.5 (32) Date: Tue, 05 Oct 1999 12:23:35 -0400 To: AESround2@nist.gov From: DWHITING@hifn.com (by way of Jim Foti ) Subject: RE: Twofish Jim, could you please add this to the AES public comments for Twofish? Bruce, could you post it on sci.crypt? ----------- As a member of the Twofish design team, I (Doug Whiting) wanted to respond to a recent postings on sci.crypt about similarities between Twofish and "Leapfrog" (from JP of Patterson Programming). I am not trying to comment at all on whether Leapfrog is a good or bad idea: indeed, I have far too little information (or time) to make such a determination. However, it did not have any influence on the design of Twofish. The Twofish design borrowed several ideas from previous ciphers. In each case, where it was done consciously, we openly gave credit to the previous inventors. Most advances in the field of cryptology come by building on the previous work of others. In fact, I was the one who came up with the 8-bit S-box construction in Twofish. Bruce Schneier was an important part of the team, but he had no influence in that part of the design. Until I saw learned of the posting last week, I had never heard of Leapfrog nor seen any of its design elements. Thus, while there may be similarities (and I will show below that there are very significant differences) between this Twofish element and the Leapfrog construction, they are totally coincidental at most. Last week, after seeing the sci.crypt posting, I queried Bruce about the Leapfrog paper that was sent to him several years ago. He has no recollection of it at all. Bruce routinely receives such unsolicited cipher descriptions, and he almost always discards them unread. This fact is not a criticism of Leapfrog, merely as a measure of how busy Bruce is with "paying customers". Even if he had read it, he never told me anything about it, so it could not have influenced my design. Further, let's look at the elements in question. Here is the equation for an 8-bit Twofish S-box, in the 128-bit key case: y0 = q1[q0[q0[y[2,0]] Xor L[1,0]] Xor L[0,0]] The L[i,j] values are key material bytes that DO NOT CHANGE for a given key. Thus, this mapping from a single byte of y2 to y0 is an 8-bit to 8-bit nonlinear mapping (S-box), fixed for a given key. In other words, this mapping can be precomputed as a small (256- byte) lookup table for each key. This S-box precomputation is used to speed up certain Twofish implementations. Now, contrast this with the Leapfrog excerpts provided: * get the T variables T1 = A1(p1), T2 = A2(p2), T3 = A3(p3), T4 = A4(p4) * note the T variable order p5 = p5 Xor A1(A1(T2 Xor T3) Xor T4) p6 = p6 Xor A2(A2(T1 Xor T4) Xor T3) p7 = p7 Xor A3(A3(T4 Xor T2) Xor T1) p8 = p8 Xor A4(A4(T3 Xor T1) Xor T2) p5 = (p5 + T1) And FF p6 = (p6 + T2) And FF p7 = (p7 + T3) And FF p8 = (p8 + T4) And FF This is a Feistel-like structure, in which p1..p4 are used to modify p5..p8. Note that the chained table lookup in question is data dependent, not key dependent. This is an inference I draw from the usage, since, if p1..p4 were instead fixed key material, the equation reduces to a simple xor/add of a key-dependent constant. Thus, the modification to p5..p8 cannot be precomputed in any reasonably sized table (unless 16MBytes is reasonable). The change to p5..p8 is very linear, as is common in Feistel structures. In other words, Leapfrog apparently uses this construction as a diffusion mechanism. This may be a very nice idea, but it is dramatically different construction than Twofish, which uses the S-box and the MDS matrix for diffusion. More abstractly, Twofish uses chained S-boxes as follows: y = f(x,Key) // x,y are 8 bits each while Leapfrog does y = y ^ F(p1,p2,p3,p4). // y, p1..p4 are 8 bits each That f and F are somewhat similar is not surprising -- block ciphers are almost always built out of running things through S-boxes and then combining with xor or add. SAFER+ does something very similar, as do E2 and LOKI97. In fact, looking across rounds (as opposed to within a round), almost every block cipher looks something like this, including DES. The fact is that Twofish uses 8x8 key-dependent S-boxes. The Leapfrog construction is nothing of the sort. Key-dependent S-boxes are a crucial design element to add security to Twofish. Chaining a fixed S-box with key material xors is a very simple way to achieve this, although there may be other or better methods. In any case, as noted in the sci.crypt posting, there is no patent involved, so Twofish is still available as a public domain cipher. Further, since I never had access to any information about Leapfrog, there is no possible copyright issue either. We are happy to give credit where credit is due, but it seems like the inventor of Leapfrog has dramatically misinterpreted both Twofish and its design team. Sincerely, Doug Whiting, CTO, Hi/fn dwhiting@hifn.com From: DJohn37050@aol.com Date: Fri, 15 Oct 1999 14:49:33 EDT Subject: AES, ANSI X9F1, and future resiliency To: AESround2@nist.gov X-Mailer: Windows AOL sub 41 NIST, When I presented my submission on "Future Resiliency: A Possible New AES Criterion" to ANSI X9F1, there was a general consensus (we took an informal vote) that NIST should include this criterion in its selection process. Participants include representatives from banks, auditors, vendors and government. Don Johnson From: matthew.fisher@convergys.com X-Lotus-FromDomain: CVG To: vincent.rijmen@esat.kuleuven.ac.be, daemen.j@protonworld.com, rja14@cl.cam.ac.uk, biham@cs.technion.ac.il, lars.knudsen@ii.uib.no, kelsey@counterpane.com, schneier@counterpane.com, daw@cs.berkeley.edu cc: aesround2@nist.gov Date: Tue, 26 Oct 1999 12:40:05 -0400 Subject: Weakness in Rijndael/Serpent key schedule? Sirs, Is the fact that a Rijndael key can be recovered via the XOR of two Cipher Keys and the XOR of the Round Keys important? 'Serpent' also seems to have this property. Given the XOR of two keys K1,K2 then the XOR of the prekeys w[0..131] could be determined. Now if an attacker knows the XOR of {k0,k1, ...,k131 } for the round keys, it is straight forward to determine K1 and K2. This property doesn't seem relevant to DES. This property seems to violate the 'Prudent Rules of Thumb for Key-Schedule Design' in 'Related Key Cryptanalysis of 3-WAY, Biham-DES,CSA,DES-X, NEWDES, RC2 and TEA' by Kelsey, Schneier and Wagner. That paper states that 'Key schedules should be specifically designed to resist differential related-key attacks.' I have not been able to create a practical attack based on this analysis. How an attacker could get the XOR of the round keys but not the keys themselves is certainly a mystery. thanks, --Matthew I posted the following to sci.crypt. I was hoping for commets on the idea. A comment on the key schedule for Rijndael. Hello sci.crypt, I believe I have found a weakness in the key schedule for Rijndael. I turn to this august body for confirmation or harsh refutation of my theory. A quick note on my credentials; I am only an amateur cryptographer but a long time professional computer scientist. This post is a follow up to the ‘Curious Keys in Rijndael’ post. Abstract In this paper the block cipher Rijndael is analyzed. Rijndael is submitted as a candidate for the Advanced Encryption Standard. The cipher has variable key and block length. This paper focuses on the key length of 128 bits with the block length of 128 bits. The Rijndael cipher is an iterated ten round block cipher for this case. Here it is shown, the Cipher Key can be recovered if an attacker has the ‘exclusive or’ of several Round Keys. Moreover, one byte of key recovery can be mounted on Rijndael for certain key relationships and strange chosen cipher texts. This note is just the beginning of the full paper I am working on. If it turns out that I goofed up then this posting will save me the work I will use the notation adopted in ‘The Rijndael Block Cipher’ by Joan Daemen and Vincent Rijmen. To understand the attack, you will have to read ‘The Rijndael Block Cipher.’ To begin with, it can be easily shown that if an attacker can gain the XOR of several Round Keys the Cipher Key may be obtained for many cases. Here is an example of recovering a Cipher Key by knowing the XOR of the Round Keys. I have abbreviated the example to the last four bytes of the Cipher Key. The rest may be obtained by having a more Round Key XOR. A total of four sequential Round Key XOR is enough to obtain the entire Cipher Key. Here are the keys and Round Key 0 and the first four bytes of Round Key 1. The Round Keys are stored in a structure called W. W has four bytes per entry. The W[0..3] structure would be the first Round Key for Nk =4 and Nb = 4. Key K1 = c6 81 4b e2 54 bd 7c e1 01 31 56 0f 67 87 aa 3c Key K2 = 7e 6b fb fb f6 df 1c 87 bf de 72 47 66 59 88 59 W Byte K1 K2 Xor 00 00 198 126 184 00 01 084 246 162 00 02 001 191 190 00 03 103 102 001 01 00 129 107 234 01 01 189 223 098 01 02 049 222 239 01 03 135 089 222 02 00 075 251 176 02 01 124 028 096 02 02 086 114 036 02 03 170 136 034 03 00 226 251 025 03 01 225 135 102 03 02 015 071 072 03 03 060 089 101 04 00 063 104 087 04 01 034 086 116 04 02 234 116 158 04 03 255 105 150 It can be seen from the Rijndael key schedule that the bytes of W[4] are a combination of the bytes of W[0] and bytes of W[3]. The formula is: W[4] = W[0] ^ SubByte(RotByte(W[3]) ^ Rcon[1] Where ^ is XOR and Rcon is a fixed set of round constants. Thus due to the RotByte the formula for the first byte of W[4][0] is W[4][0] = W[0][0] ^ SubByte(W[3][1]) ^ Rcon[1] Now for two keys K1 and K2 the XOR of W[4][0] is W1[4][0] ^ W2[4][0] = W1[0][0] ^ W2[0][0] ^ SubByte(W1[3][1]) ^ SubByte(W2[3][1]) The Rcon is canceled by the XOR. In our example, the attacker knows W1[0][0] ^ W2[0][0] = 184 And W1[4][0] ^ W2[4][0] = 87 And thus W1[0][0] ^ W2[0][0] ^ W1[4][0] ^ W2[4][0] = 184 ^ 87 = 239 And thus 239 = SubByte(W1[3][1]) ^ SubByte(W2[3][1]) Also the attacker know W1[3][1] ^ W2[3][1] = 102 Given the XOR of the inputs, 102, and the XOR of the outputs, 239, into a bijective S- box, it is trivial to calculate the possible inputs. For the example, the only possible inputs for the Rijndael S-box are 225 and 135 225 ^ 135 = 102 S(225) ^ S(135) = 248 ^ 23 = 239 Now the attacker knows that the W1[3][1] must be a 225 or a 135. Since, the Cipher Key is copied into W[0..3], the attack knows one of the key bytes. All of the other bytes can be obtained in a similar manor. To get W[0..2], more Round Key XOR are needed. This proves that given only the XOR of the Round Keys an attacker can recover the entire Cipher Key. How an attacker would gain such information is unknown. A possible method is that power or time analysis would reveal some relative measure but not an actual key. This relative measure might somehow be combined for two keys to create an XOR of the Round Keys without revealing the actual values. Here we go with the byte recovery attack. For a chosen cipher text, related key attack the conditions are: 1. An implementation using Nb = 4 and Nk =4 i.e. 128 bit key and 128 bit block 2. Two Cipher Keys in Rijndael such that K1 == K2 except for the first byte i.e. K1[0] != K2[0] 3. A relationship between K and K1 such that the Round Key (RK) W1[36][3] == W2[36][3] 4. Two cipher text, C1, C2 such that C1 XOR RK1(11) == C2 XOR RK2(11). RKy(x) is Round Key number x for key y. C1 will be generated under K1 and C2 will be generated under K2. This requirement is that the cipher texts must be equal before the last round key application in the tenth round of Rijndael. If the above conditions are met, one byte of the tenth Round Key can be found with high probability usually one half. Since, the Cipher Key can be constructed from any Round Key, the remaining bytes of the tenth Round Key can be guessed. Once a full Round Key is guessed, the Cipher Key can be generated and tested against one known plain text cipher text pair. The guessing and testing process will have to be done on about 2^120 Round Keys. 2^120 is obviously must faster than 2^128 thus the attack is faster than exhaustive search. The relationship between the keys is quite awkward but is certainly possible. I written a simple program to generated keys matching the above criteria. Here is the attack on Cipher Key K1. 1. Given the two cipher texts C1 and C2 from above. XOR C1 and C2. The result will be the RK1(11) XOR RK2(11) 2. Due to the awkward relationship between the keys and the key schedule for Nk = 4, information about the RK1(10) can be gained from RK1(11) XOR RK2(11). 3. The Round Key sub structure W1[40] will contain four bytes. The first, A, and fourth, D, bytes of W1[40] are related by the Rijndael S-Box. 4. The relationship is that A is the XOR of inputs into the S box and D is the XOR of the outputs. 5. Typically, only one pair of inputs/outputs meets the criteria. Thus byte one of W1[39] must be one of the pair. This gives a 50% chance of guessing the byte. W1[39] is in RK1(10). 6. Guessing the other 2^120 bits can be done by exhaustive search. How an attacker could gain the required information is unknown. The above attack appears to be entirely theoretical. It is interesting none the less. Several possible extensions exist for this attack. Here is one possible extension. It appears that a given XOR input has a limited set of output XOR for the eleventh Round Key. If the set of output XOR is small in comparison to 2^128 then a table look up attack could be mounted. The table would contain all possible XOR outputs and the corresponding keys for a particular input XOR, K1 ^ K2. An attack would then randomly XOR cipher text from two related keys. The results of the cipher text XOR would be looked up in the table and the keys tried. When two cipher texts were equal in the last round before the key XOR, the proper entry would be found and thus the Cipher Key would be found in the table. Got all that? ;-) --Matt Matthew E Fisher mfisher@magicnet.net -- NOTICE: The information contained in this electronic mail transmission is intended by Convergys Corporation for the use of the named individual or entity to which it is directed and may contain information that is privileged or otherwise confidential. If you have received this electronic mail transmission in error, please delete it from your system without copying or forwarding it, and notify the sender of the error by reply email or by telephone (collect), so that the sender's address records can be corrected. X-Authentication-Warning: apal.ii.uib.no: larsr owned process doing -bs Date: Wed, 27 Oct 1999 00:02:30 +0200 (MET DST) From: Lars Ramkilde Knudsen To: matthew.fisher@convergys.com cc: vincent.rijmen@esat.kuleuven.ac.be, daemen.j@protonworld.com, rja14@cl.cam.ac.uk, biham@cs.technion.ac.il, lars.knudsen@ii.uib.no, kelsey@counterpane.com, schneier@counterpane.com, daw@cs.berkeley.edu, aesround2@nist.gov Subject: Re: Weakness in Rijndael/Serpent key schedule? > Is the fact that a Rijndael key can be recovered via the XOR of two Cipher > Keys and the XOR of the Round Keys important? I don't think so, no. > 'Serpent' also seems to have this property. Given the XOR of two keys > K1,K2 then the XOR of the prekeys w[0..131] could be determined. Now if an > attacker knows the XOR of {k0,k1, ...,k131 } for the round keys, it is > straight forward to determine K1 and K2. > This property doesn't seem relevant to DES. No, but on the other hand, the exor of two DES cipher keys gives immediately the exor of all round keys, which is probably worse. This is not the case for Rijndael and Serpent. > I have not been able to create a practical attack based on this analysis. > How an attacker could get the XOR of the round keys but not the keys > themselves is certainly a mystery. Assume you find an algorithm which on input a number of plaintext-ciphertext pairs encrypted under two randomly chosen and unknown keys, returns the exor of the round keys (and/or the master keys). This algorithm can be used to find a single key. Run the algorithm but where you choose one of the keys yourself at random. You can then compute plaintext-ciphertext pairs using the key you know and feed these to your algorithm together with pairs encrypted under a secret key K. Then you get the round keys of key K, and you have broken the cipher. -Lars From: "Albert Yang" To: AESround2@nist.gov Date: Mon, 1 Nov 1999 16:55:59 -0800 Subject: Home made tweaks Priority: normal X-mailer: Pegasus Mail for Win32 (v3.12a) First, I think you guys are doing a great job. I don't usually say that to any group with a .gov... As for the multi-algorithm vs. single debate, here's an offshoot of it. I like Serpent, it's slow but like a vault, if it doesn't get picked, I still will probably use it in most of my personally developed applications. If Mars or Twofish got picked, they are great, but I can't remember all that, and I am afraid that I would screw up the implementation of it. I seriously doubt that any of the 5 are going to be broken, that's not where the weaknesses are going to be. It's going to be implementation, and that's where I screw up. So for that reason, I like RC6. I can fit it on a napkin, and still wipe my mouth. Easy to remember, and it has a good family history so I'm a bit more confident in it. Here's the thing though; I'm thinking, if I need a bit more security, I might just use RC6 and make it 384 bits, and up the number of rounds. It's a cipher I know, it's a cipher I trust, and I can just up the rounds and the key size. Same with Rijndael. 10 rounds is not enough to make me sleep well at night, so if it got picked, I'd crank it up to 16 or 20 rounds. Double like Lars says is good for me. So is that something you guys are addressing or considered addressing? The homebrewed stuff. I take AES algorithms, and tweak it up myself? I think comparison of speed is not fair for this reason alone. What if the designers of Serpent had picked only 8 rounds? Then it would be fast. But they picked 32, so it's slow. What if Rijndael was 32 rounds? Right now, I'm thinking, it doesn't matter which one wins, I will probably use Serpent straight out of the bottle, or RC6 with 32 rounds and maybe a beefed up key, or Rijndael with 20 or 32 rounds. I can't be alone on this line of thinking I suspect... Regards, Albert Date: Tue, 16 Nov 1999 00:34:37 -0800 From: Ted Goldstein Reply-To: tedg@transactor.net X-Mailer: Mozilla 4.07 [en] (Win95; I) To: AESround2@nist.gov, tgoldstein@brodia.com Subject: Issues for AES One of the interesting issues regarding AES is multiple utilitiy. DES has been used for many years in authentication schemes as well as encryption schemes. This becomes especially important in smartcards, where the multiple utility is a necessity. Ted Goldstein CTO, Brodia.com X-Originating-IP: [152.163.204.201] From: "Matt Robshaw" To: AESround2@nist.gov Subject: comment Date: Mon, 29 Nov 1999 01:21:34 PST Dear NIST AES team, As you will no doubt be aware, Lars Knudsen and Willi Meier have written a paper entitled "Correlations in RC6". Since the posting of this paper to the AES discussion forum there appears to have been little discussion on the implications of this excellent work. We would therefore like to take this opportunity to let you know our own thoughts on this paper. In our report "The Security of RC6" (which was published on August 20, 1998 and is available via www.rsa.com) we provide a thorough investigation of the security of RC6. We primarily used the techniques of differential and linear cryptanalysis, and while we also considered some other techniques, we felt that linear cryptanalysis would likely provide the most successful avenue for the attacker. In particular we gave a clearly reasoned and conservative estimate that an attack on 16 rounds of RC6 using around 2^{119} known plaintexts should be expected. (See Table 15, on page 51 of the report cited above.) By vulnerable we assumed that not only could RC6 be distinguished from a random permutation using this amount of plaintext but in fact we followed established cryptanalytic practice in assuming that the full encryption key (or its equivalent) could be recovered! Taking this into account, and feeling that the simplicity of RC6 had allowed us to establish a good intuitive and empirical understanding of the cipher during the design phase, we fixed the number of rounds of RC6 to be 20. What is very interesting to us is that the results of Knudsen and Meier so closely match our own expectations for the security of RC6. Their innovative extension and generalization of the earlier results of Vaudenay et al. give a remarkably similar result to our own: they have concluded that around 2^{119} plaintexts can be used to attack 15 rounds of RC6. While the attack they outline may not be quite as effective as the attack on RC6 that we already believe exists, it does seem to provide excellent confirmation that our own analysis is broadly in line with that conducted independently by other researchers. We think that there are still some unanswered questions about the style of statistical analysis used for the estimates in their attack, particularly in its extrapolation from very few rounds to a large number of rounds. We hope that this will be an area for continued research. Indeed, many of the same questions are open for the closely-related technique of linear cryptanalysis on which we based our own estimates for the security of RC6. However we are encouraged that, independently, the two techniques give very similar results and they increase our confidence that both sets of estimates for the strength of RC6 are as accurate as current analytical techniques allow. We look forward to hearing of any more results on the security of RC6 and we encourage others to explore and analyze the cipher. Certainly we believe that we have been successful with our secondary design rationale after security - that of keeping the cipher simple. Only in this way is it possible to encourage independent research, to facilitate analysis by cryptographers other than the designers, and to provide an accurate estimate of the security offered by a cipher. We feel that this is vitally important when the time allowed for such independent analysis during the second round of the AES schedule is so limited. Yours sincerely, Ron Rivest Matt Robshaw Lisa Yin ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com From: Jeffrey Streifling To: AESround2@nist.gov Subject: Consideration of RC6 Date: 5 Dec 1999 15:02 -0700 Disclaimer: I have just been investigating RC6; I have no special interest in it. I've been looking at RC6 as one of the most interesting of the AES candidates. It has rather a peculiar set of advantages and disadvantages in regards to implementation issues. It is an extremely concise algorithm and avoids lookup tables and special cases. It makes use of common instructions in most processors. However, it does use multiplication instructions which are hard to emulate in microcontroller environments. If there is to be only one AES algorithm, the use of the multiply would probably mean that it would have to go based on performance and implementation issues in small environments. (As an engineer familiar with the instruction sets on several microcontrollers, I know I would hate the job of producing a small implementation of this.) Here I assume that all remaining algorithms are reasonably sound cryptographically and that the remaining selection procedure will be based on implementation issues. RC6 turns out to be very useful, almost uniquely useful, though in several environments where none of the other algorithms can apply. - Suppose I am given the job of producing a small wrapper program for a security sensitive application. The wrapper is going to be put through a very heavy security audit, and as such, needs to keep the number of lines of code to a minimum. RC6 can be embedded in very small programs, facilitating easy audit ("It's obviously correct!") and testing. Other algorithms will need more lines of code to implement specialized logic and lookup tables. It takes a considerable amount of effort to verify the correctness of implementations of the other algorithms as their correctness is not always obvious. - Suppose I want to implement a one-time password calculator in a programmable calculator (e.g., an HP 48) to take on the road to access home office facilities through untrusted network terminals (think of "Internet Cafes", truck stop facilities, airport "web booths", libraries, and the like). RC6 can be implemented fairly easily in anything that supports multi-base arithmetic; I don't even want to think about trying to squeeze TWOFISH or SERPENT into these environments, even as much as I like them. - Suppose I want to implement a quick mechanism for disguising some critical piece of information like a credit card number in a script/interpreted program on a machine that doesn't already have a library for that purpose. RC6 is the natural winner: 10 lines of code will encrypt, another 10 will decrypt, and another 10 will schedule the key if necessary. It all just goes in line and I'm done. I don't want to think of the tedium of keying a kilobyte worth of hexidecimal constants from a book somewhere. - Suppose I need to verify my implementation quickly in the presence of some new bug that gets discovered down the road. With RC6, I can quickly check any part of the action by hand. The other algorithms require a bit of fiddling -- quick on a computer, but messy by hand. - In general, any application where the algorithm needs to be implemented quickly or at low cost, or where the code needs to be heavily scrutinized, or where the expense of maintaining security sensitive lines of code is high will benefit greatly from RC6. I think that if at all possible, algorithm simplicity should be one of the factors in the AES decision. I personally think that RC6 is a hands-down winner in this arena, and if it is posssible to choose more than one AES candidate for the standard, RC6 should definately be one of the chosen algorithms (assuming that some new theoretical result doesn't break it in the interim...) (Even if there was only to be one algorithm, I would still vote for RC6 for the above reasons, but I could understand why it would face opposition from smart-card software authors.) As for how the requirements for AES compliance should be stated in the presence of multiple approved algorithms, I think that a distinction should be made between "client compliance" and "server compliance" (change the terminology to suit). Servers (things to whom people need to authenticate, messaging hubs, and any kind of software package where it might be possible to implement multiple algorithms) should be required to implement all algorithms; clients (smart cards, hand-held computers/palmtops, calculators, etc) should have their choice of implementing any one algorithm. Then clients and servers could reliably communicate, as well as two servers. (Any kind node in a messaging system where full-mesh connectivity is desired would automatically be subject to the server requirement, including applications for the Internet). I would like to be able to implement the algorithms in question on a programmable calculator (e.g., for testing or maybe to reduce the number of items in my pocket) while a smart card author would like to be able to cram basic functionality into a 50 cent controller. Different algorithms will be suited to our purposes, and it would be nice to permit as wide a variety of implementations as possible. I think that at this point, with only five candidates left, that the only reason candidates should be eliminated is for cryptographic weakness. It would be straightforward to implement all five algorithms in any loadable computer software (witness today's multigigabyte hard drives!), which would provide the most flexibility for small devices which need to interact with them. Perhaps algorithms could be eliminated if it could be shown that there could be no environment to which they would be uniquely best suited (i.e., they are redundant). RC6 should definately not be eliminated. Multiple standardized algorithms will provide insurance against future theoretical breakthroughs which might compromise the security of one, maybe two, but not all algorithms. Once again, if at all possible, please include RC6 in the final AES standard. A simple cipher that can be implemented almost anywhere would provide valuable future flexibility! Thank you Jeffrey Streifling Date: Sun, 26 Dec 1999 21:20:58 -0500 From: Eva Bozoki X-Mailer: Mozilla 4.5 [en] (Win95; U) X-Accept-Language: en To: AESRound2@nist.gov CC: aharon , dennis Subject: Comments on Round 2 White Paper This is a vendor-oriented response on the question of "How many AES algorithms?" Jim Foti raised in his recent email and which is discussed in the Round-2 Issues White Paper. I assume that out of the final AES candidates there will be more then one that meets the requirements. More then likely, beyond satisfying the basic security requirements, they will have different advantages making them equally good candidates under different circumstances (efficiency, security, margin tradeoff, hardware/software implementability, etc). For that reason, probably the votes of the committee can not be and will not be unanimous. Rather then choosing 1 out of 2 or more almost equally good candidates, why not allow vendors and their customers to make the choice from a pool of approved algorithms according to how they perceive their needs and preferences? (Naturally, if only one algorithm would satisfy all the requirements, my arguments are not valid.) I don't think that the use of different algorithm would necessarily cause interoperability problems. There are three scenarios: 1. Each encryption product is manufactured to use one and only one algorithm out of the pool. It is ordered and manufactured for a given need and Network, where all the used crypto products has the same communication protocol and the same encryption algorithm. 2. The User of the encryption product (in the role of the Crypto Officer?) is allowed and able to switch between algorithms, thus the same product is portable from one Network, using algorithm-1, to another Network that uses algorithm-2. Also, it makes it possible and easy for a Company that purchased encryption products to switch from one algorithm to another if their need or their confidence changes. 3. The encryption product can automatically recognize the algorithm in the incoming messages and use the same algorithm, much like the IPSEC protocol does. In none of the above scenarios is the same message encrypted with more then 1 algorithm, thus approving multiple AES algorithm will not increase the probability of breaking any one of them. Finally, saying that public confidence would be shaken if any of the approved AES algorithms would be broken sounds silly. What if the single AES algorithm is broken? In that case not only the public confidence, but also much more would be broken. .Eva Bozoki PATCO Scientific Advisor to Fortress Technologies Date: Mon, 27 Dec 1999 16:54:12 +0100 From: Eric Boesch X-Mailer: Mozilla 4.7 [en] (WinNT; I) X-Accept-Language: en To: AESround2@nist.gov Subject: Modes of operation 1. PCBC is desirable for fast verification of ciphertext integrity. The need for checksums to verify message integrity is commonplace, even in unencrypted network applications. CBC and CFB MACs authenticate their plaintext only -- they do not authenticate their ciphertext. Using PCBC allows you to simultaneously generate ciphertext and a MAC that can be applied to the ciphertext, at little extra cost. PCBC's behavior is simple, unforgiving, and often desirable: all errors propagate forward indefinitely. 2. Why output feedback mode instead of counter mode? Output feedback involves XORing the plaintext with an independent codestream E(IV),E(E(IV)),E(E(E(IV))),.... If the block size is 128 bits and E() is a random one-to-one mapping, then you can expect, by the birthday paradox rules, to have your codestream repeat after about 2^64 blocks on average. If the encryption function is secure, then under no circumstances does output feedback appear to offer significant advantages over an appropriate use of counter mode, where the plaintext is XORed with E(IV),E(IV+1),E(IV+2),.... X-Sender: schlafly@pop.mindspring.com X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.6 (32) Date: Tue, 11 Jan 2000 04:37:20 -0800 To: AESround2@nist.gov From: Roger Schlafly Subject: AES round 2 comment Comment on NIST AES process There have been rumors that NIST is considering multiple winners for the AES. I think this is a very bad idea. When NIST announced the DES about 25 years ago, it was radical. It introduced to the public the idea that a cipher algorithm could be public and standardized, while all the secrecy was in the keys. While DES has been intensely attacked over the years, it has held up rather well. It delivers the security it promises, more or less. NIST and IBM are to be congratulated for their outstanding contribution to the science of cryptology, for convincing both academics and the public that cryptography can be an open process, and for a huge positive impact on computer security. Now that DES needs to be replaced with AES, NIST has taken the process one step farther by using an open competition to find a state-of-the-art cipher. This is admirable. The five finalists are all outstanding, and any one of them should make for a great AES (provided the various concerns are addressed, of course). But now I am troubled by the possibility that NIST may weaken in its resolve in the face of political pressure. Some people seem to have ideological or business reasons for opposing a standard. Or maybe they still have not accepted the fact a cipher can have an open specification and still be secure. If NIST chooses multiple winners, then it will be a failure of the AES process. People will assume that no cipher was fully satisfactory, or that NIST could not make a decision. If that happens, a lot of people will continue to use DES or triple-DES. Interoperability will become difficult or impossible. Many resources will be wasted by people who want to implement each algorithm in order to get full compliance. Others will find full compliance too expensive, and end up not complying at all. Some people will think that they have to implement some sort of algorithm selection protocol in order to make full use of AES. While there are some theoretical arguments that such a selection protocol can increase security, it is much more likely that flawed protocols will decrease security. Others will be encouraged to iterate or nest the ciphers on the theory that if one cipher is not good enough for NIST then it is not good enough for them either. The ANSI X9F1 committee had a resolution in favor of NIST considering future resilience in the AES process, whatever that means. Attempts to gain support for a motion to recommend multiple AES winners apparently failed. I would not assume that the ANSI X9F1 committee wants multiple AES winners unless it actually passes a motion that recommends multiple AES winners. I would have voted in favor of considering future resiliency, but against adopting multiple standards. So why would there be resistance to a single AES winner? Here is the opposition that comes to mind. 1. Those who naively think that more ciphers means more security. 2. Those who are ideologically opposed to standards. 3. Those with business interests contrary to a single AES standard. 4. Those who think having both US and foreign designed winners would be more politically acceptable. It is the large key space that gives the diversity of ciphers. If we needed more ciphers, then you could add a couple of key bits. But 256 key bits is plenty already. If political considerations warrant the choice of a second cipher, then perhaps one could be designated a "runner-up" so that it will be available but not obligatory. Therefore I strongly recommend sticking to the vision of an encryption standard, and resisting efforts to dilute and weaken it with wishy-washy decisions. Roger Schlafly From: Chen Lidong-LCHEN1 To: "'AESRound2@nist.gov'" Subject: Re: Request related to FIPS 140-1 and the AES Date: Fri, 14 Jan 2000 15:26:46 -0600 X-Mailer: Internet Mail Service (5.5.2650.21) Jim: We prefer that one algorithm be selected as the final AES algorithm for the following reasons: 1. It would be best to put efforts into evaluating the security of one algorithm. If more than one algorithm is selected, then the analysis efforts would not be as focused. 2. If multiple AES algorithms are selected, then security issues related to algorithm negotiation protocols will need to be considered. 3. It is more cost-effective to implement a single encryption algorithm than to implement multiple algorithms. Multiple algorithms would require larger, more costly circuits to support multiple algorithms. These circuits would also be more complex, thus reducing production yields and increasing testing requirements. Complex circuits are also more prone to bugs, which can potentially lead to other security issues. 4. Multiple AES algorithms will lead to interoperability issues between different systems. These issues will require further standardization efforts, which may lead to relatively long product deployment delays. 5. Customer confidence will be diminished by choosing multiple AES algorithms. It will be difficult to explain why there are multiple AES algorithms. Also, customers will be bothered to decide which algorithm is better. 6. Choosing multiple AES algorithms, might increase the possibility of intellectual property issues. The more algorithms that are selected, the more likely one of them will have intellectual property issues that will surface at a later date. Based on the above noted issues, we recommend that NIST select a single algorithm for the AES algorithm. Regards, Lily Chen Motorola Inc. 1501 W. Shure Dr. Arlington Heights, IL 60004 (847) 632- 3033 Date: Mon, 17 Jan 2000 16:51:36 +0900 (JST) From: Kaneko Yasuyoshi Reply-To: Kaneko Yasuyoshi Subject: Some comment To: AESRound2@nist.gov X-Mailer: dtmail 1.2.1 CDE Version 1.2.1 SunOS 5.6 sun4u sparc Dear AES officers I am Yasuyoshi Kaneko belonging to TAO in Japan. May I congratulate on the third AES conference, and I hope the final AES algorithm will be selected without accident. I also have watched the AES selecting process as many participants in the world and now I feel there are some points which NIST had better reconsider and make respond. 1. Estimating Process The estimating process of AES seems to be more complicated compared with other contests or other engineering. Because cipher designers and cryptanalysts are not so completely distinguished that a person may be sometimes a good or bud designer but other times a bad or good cryptanalyst. Thus the estimation results, which were gotten by, many cryptanalyst seems to be a jumble of wheat and tares. After all judging and deciding is due to NIST, so I ask NIST to continue to be open to present his judging process and conclusion. 2. Simple design criteria This simple design criterion was presented before the first AES conference by NIST, and most of all designers of AES candidate seem to try to satisfy these criteria. However this idea of simple is against the security because a simple design structure of cipher may give many chance of cryptanalysis and this cryptanalysis results give a weak image to these ciphers without breaking. The idea of simple is difficult to define and it is difficult to judge which cipher is simple or not (With this reason simple design criteria has been not excitedly discussed during AES estimating process). A correct expression may be that clear and united design principle AES algorithm should have. If final selected AES will seem to be not simple what kind of explanation will NIST give? 3. Lifetime criteria I think, as many people think, the lifetime of AES is the most important thing, which NIST consider and take the responsibility to. NIST seems to consider that the lifetime of AES is 20-30 years, without any clear comment on the maintenance plan of AES specification. Maybe there are many threats, which force AES to change itself. Simple examples are given as follows. a. Someone finds a week point, which seems to give a chance to break the AES by a new attack. b. Someone finds new computing processor or technique, which give an enough ability to break AES by ciphertext-only attack. c. Someone finds new design technique for keeping security and which technique seems to be enough attractive that many engineers abandon to use AES. Anyway, when the reliability of AES is fallen the most damage is given to users and many companies. Maybe royalty free sounds good for every engineer who consider the design of security system, however if there is no guarantee for long-time using or some guidance for using the specification of AES, using AES seems to be very risky selecting for engineers and his companies. I think that there are 2 things, which NIST should consider and officially announce the guidance of coping with. 1) Making a usual maintenance plane about key-length and block-size to present guidance for using the many kind of key-length and block-size. 2) Making an unusual maintenance plane especially considering the cases a. The most important thing is 2), because the specification of AES may be dramatically changed and users of AES may also change the security system as soon as possible. Maybe one practical method of solving risky status is offering some AES algorithms as some people said, however I think many cipher algorithms will give much pleasure to cryptanalyst and attacker so that the results of cryptanalysis contribute to shorten the lifetime of these AES. Moreover if many kind of standard algorithms are used in each security system, interface of each system becomes to be more complicated and user-interface also becomes to be no good. I think other method is increasing the number of round with an expectation that the speed of hardware and software will be enough faster than now. Maybe this method of increasing the round number does not seem to be attractive way but this method is the most certain way to keep security of ciphers. Because almost all cryptanalysis depend on the round number and if the round number increases enough anyone fail to attack any more. (I think that if trying to use a block cipher for a long period, as an old proverb says, There is no royal road to block ciphers. The only thing that we can ask is not "Is AES secure enough?" but "How many round of AES is secure enough for now?" The only problem is changing also the algorithm of key scheduling, so the specification of key scheduling which makes it possible to increase the number of rounds should be given. Fortunately the five finalists of Round2 seems to satisfy the flexibility of changing the round number and the key-scheduling, so anyway my idea is possible to realize. Moreover it is desirable that the method of this changing specification is parameterized to easily implement and change its algorithm. It is also need that the number of round should be periodically (every several years) reexamined to judge whether the round-number of AES should be changed or not. I hope that NIST will consider and investigate these three points and will make a public of his decision at the third AES conference. With every best wish for success for AES3. Yasuyoshi Kaneko, Telecommunications Advancement Organization of Japan, E-mail: kaneko@yokohama.tao.go.jp From: "Costantini, Frank @ CSE" To: "'AESround2@nist.gov'" Cc: "Carter, Matthew @ CSE" , "Kozak, Taras @ CSE" , "McGrogan, Chip @ CSE" , "Holland, Robert @ CSE" Subject: AES modes of operation Date: Wed, 26 Jan 2000 16:01:32 -0500 X-Mailer: Internet Mail Service (5.5.2650.21) AES Evaluation Group: While I do not have any specific comments on any of the particular AES candidates, I would like to propose that NIST evaluate the security of the proposed algorithms when employed using counter-mode cryptographic operation. Counter-mode has advantages over OFB, CBC, and ECB modes for high-speed packet-based applications (like ATM), and as well as packet based communications over bandwidth-restricted channels. This mode requires little synchronization overhead and allows the keystream to be calculated in advance of the plaintext (for transmit) and ciphertext (for receive) becoming available. Furthermore, I would like to propose that the counter mode of operation be included in any "modes of operation" standard that is produced as part of the AES process. Thank you for your consideration. Respectfully, Frank Costantini L-3 Communications Communication Systems-East 1 Federal Street, AE-3C, Camden, NJ 08103 *856-338-3480 Fax: 856-338-3150 email: frank.costantini@L-3COM.com Reply-To: From: "Chip McGrogan" To: "'Costantini, Frank @ CSE'" , Cc: "'Carter, Matthew @ CSE'" , "'Kozak, Taras @ CSE'" , "'McGrogan, Chip @ CSE'" , "'Holland, Robert @ CSE'" Subject: RE: AES modes of operation Date: Wed, 26 Jan 2000 19:03:53 -0500 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook 8.5, Build 4.71.2377.0 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 Frank: Great! Keep me up to date on how NIST reacts. BTW you forgot to mention one big advantage of Counter Mode, particularly for high data rate applications like ATM - - Since there is no feedback of previous information, parallel (concurrent) engines can be used to increase the data rate above that of a single engine. A 48-byte ATM cell payload can be encrypted by three parallel engines, each encrypting a 16-byte portion of the cell payload in a manner that is interoperable with an implementation using a single engine. Keep up the initiative! Chip From: "Nicholas C. Weaver" Subject: Importance of subkey generation time... To: aesround2@nist.gov Date: Fri, 18 Feb 2000 14:48:47 -0800 (PST) X-Mailer: ELM [version 2.5 PL0] For hardware implementations, subkey generation structures may make a huge difference. There are several applications which would use cryptographic hardware (such as an encrypted backbone packet router, or an encrypting server which may service hundreds or thousands of simultaneous, independently keyed connections) where the key may be different on almost a block-by-block basis. Furthermore, depending on the application, the memory bandwidth requirements for storing and accessing expanded subkeys may be prohibitive, so subkeys would have to be generated on the fly. The ability to do fast subkey setup really varies from cipher to cipher. MARS and RC6 both have loop carried dependencies and need to traverse the loop multiple times, which implies that one can't build a pipeline to generate subkeys. This also makes it expensive/difficult to do subkey setup concurrent with encryption, as a pipeline capable of encrypting N independent blocks simultaneously would require N copies of the subkey generation hardware to encrypt each block with a unique key. Rijndael and Serpent are pipelineable but the whole set of subkeys will need to be buffered for decryption because of the reverse order required for decryption subkeys. Thus, for a N block pipeline, this would require the subkey storage * N buffer space, but only a single copy of the subkey generation hardware to do decryption. For encryption, such significant buffering is not required. Twofish, from a hardware implementor's viewpoint, has the nicest key schedule, since it can be quickly pipelined and, with the subkeys for each round being independently generateable, allows both encryption and decryption pipelines to quickly change subkeys. One would have a pipeline to generate the S-box subkeys, and a second to generate each round's subkeys. This would allow a single copy of the subkey generation hardware to support almost full rate encryption OR decryption, with each block using an independent key. On another note, as a potential hardware designer, I'd be highly reluctant to support the idea of multiple "winners". Although I defiantly prefer some implementations (Twofish, Rijndael) over others (RC6, Serpent, MARS), there is a significant cost in hardware in having to support multiple ciphers. As a designer, I'd rather support a single, less elegant cipher over two or three different algorithms. Undoubtedly multiple final selections will result in protocols which involve supporting all candidates. Although not a significant problem from a software point of view, this represents a doubling of the cost from a hardware implementers view if he wishes to support such protocols. Even if a single winner is less amenable to hardware then one of a group of winners, the extra cost of having to support multiple winners could instead be spent on doubling the hardware available (and doubling the hardware performance) of a single winner. AES shouldn't suffer from the problem inherent in multiple standards of: "That's the wonderful thing about standards, there are so many to choose from" -- Nicholas C. Weaver nweaver@cs.berkeley.edu To: aesround2@nist.gov cc: craigc@pictel.com Subject: Comment on VLIW & Instruction Level Parallelism Reply-To: Craig Partridge From: Craig Partridge Date: Tue, 14 Mar 2000 10:20:43 -0500 Sender: craig@aland.bbn.com Hi: I read Craig Clapp's paper on Instruction-Level Parallelism with interest and had a few comments. First, I think the Instruction characteristics, while valid for today's slower processors, will not be true soon. Faster VLIW CPUs are leading to more variable load delays and often multi-instruction cycle latencies for more classes of instructions. For instance, on the DEC Alpha a LOAD can take between 2 and 40 some cycles depending on where the data is located and the speed of the external memory. Integer multiply cycles are also growing (as long as 10 to 20 cycles). And, interestingly enough, barrel roller operations (BYTE Extract and shifts) sometimes take more than one cycle. This suggests that we should think less in terms of particular cycle counts and more in terms of sums of instruction types along critical paths. Craig Partridge Chief Scientist, BBN Technologies E-mail: craig@aland.bbn.com or craig@bbn.com To: aesround2@nist.gov cc: Ross.Anderson@cl.cam.ac.uk cc: biham@cs.technion.ac.il cc: lars@knudsen.ii.uib.no cc: brian.gladman@btinternet.com Subject: comment on Serpent optimized code Reply-To: Craig Partridge From: Craig Partridge Date: Tue, 14 Mar 2000 10:39:06 -0500 Sender: craig@aland.bbn.com Hi folks: I've been perusing the various AES "optimized" C code solutions and noting that several of them appear to be under-optimized -- that there's space to make them run faster. This note is to report on some limited success with the Serpent implementation. Note that Serpent appears to be very hard to optimize because it is pretty simple -- a series of simple operations. Very little room for instruction level parallelism or pre-computation. But I've gotten what appears to be a 15% to 20% per-round improvement in performance in Round 0 (which is enough to report on and the results would appear to apply to other rounds). There are two issues: - The optimized implementation submitted to NIST uses a huge number of temporary registers and at least some compilers aren't smart enough to realize when the temporaries can be recycled. The code is also not written to minimize register usage. It uses 14 registers when I've been able to rewrite the code to use only 5 registers for round 0. I've also taken Brian Gladman's optimized round 0 code and tuned it to use 6 registers. You get improved performance on the Pentium and the DEC Alpha. The utility of this improvement is not just fewer registers in software -- it can mean less data carried along the pipeline in harder. - The optimized implementation treats three parts of a round, namely the round (RND macros), the transform (another macro) and keying (another macro) as distinct phases. For instance, you don't do the transform until the round is finished. However, you can get a lot of instruction level parallelism by merging the transform and round. Typically some results of the round are available only halfway through a round and they're often enough for the transform stage to start doing useful computation. RND00 appears particularly amenable to this optimization but other rounds should benefit too. For Round 0, this optimization gets a modest win on the Pentium (subject to register interactions) and a big win on the Alpha (which has far more available registers). Again, this is not just a software issue -- if you're building hardware the logical thing to do is treat the round and transform as one combined process. I hope this is useful, Craig Partridge Chief Scientist, BBN Technologies E-mail: craig@aland.bbn.com or craig@bbn.com Date: Thu, 16 Mar 2000 14:41:26 -0800 From: August Zajonc Subject: Twofish To: AESround2@nist.gov X-MIMEOLE: Produced By Microsoft MimeOLE V5.00.2919.6700 X-Mailer: Microsoft Outlook Express 5.00.2919.6700 X-MSMail-priority: Normal Developed with care, usable anywhere. From: "Manfred Spraul" To: Subject: public comment Date: Mon, 20 Mar 2000 13:45:30 +0100 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2919.6700 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6700 a few short notes from a non-cryptographer: - AES supports key sizes of 128 and 192 bits, but SHA-1 and RIPE-MD 160 produce 160 bit keys. Could you define a standard way how to fold/expand the 160-bits into 128/192 bits? Please remember that many non-cryptographers will use AES. - I would prefer if one algorithm is choosen as the AES [except as below]: This should increase interoperability and reduce costs. - Even if Moore's law remains valid for the complete century, 256 bit keys won't be broken during this century by brute force. And there is no guarantee that throwing more bits at an alogorithm actually increases the security. Please consider a Double-AES for the 256-bit key length [e.g split the key into 2 128-bit blocks, and encrypt with 2 different algorithms] Noone will use 256-bit in smart-cards, so memory/size constraints will be less important. -- Manfred Spraul From: sesmail@neptune.calstatela.edu Date: Tue, 21 Mar 2000 20:50:21 -0800 (PST) X-Authentication-Warning: webmail2.calstatela.edu: nobody set sender to sesmail@neptune using -f To: webmaster@ams.org, webmaster@entropia.com, info@perfsci.com, webmaster@eff.org, AESround2@nist.gov Reply-To: sesmail@neptune.calstatela.edu User-Agent: IMP/PHP3 Imap webMail Program 2.0.11 Sender: sesmail@neptune.calstatela.edu X-Originating-IP: 208.149.1.14 Hi this is Simon Esmaili. I recently read on the internet that quantum computers might make encryption techniques based on the multiplication of two huge prime numbers obsolete. I know of a simple huge number encryption technique. It may or may not be adequate though. I wouldn't know because I'm fairly ignorant when it comes to encryption. Step 1: Pick a code. Step 2: Encode the message. Step 3: Divide the encoded message into pieces of length n. If the length of the last piece is less than n, then add encoded random characters until the last piece is also of length n (it's probably not a good idea to add encoded blank characters in lieu of encoded random characters). Step 4: Pick an n by n matrix where each entry in the matrix is a natural number. Step 5: Multiply each piece/vector of length n by the matrix. For example, if encoded message = "a b c d e f" n = 3 first row of matrix = "g h i" second row of matrix = "j k l" third row of matrix = "m o p" then matrix-multiplied encoded message = "ag+bh+ci aj+bk+cl am+bo+cp dg+eh+fi dj+ek+fl dm+eo+fp". The matrix acts like a combination lock. If n = 20 and each entry in the matrix is a natural number between 1 and 10^4 inclusive, then there are (10^4)^(20^2) = 10^1600 such matrices. For each matrix, the inverse must be found and multiplied with the intercepted message. Reply-To: From: "Gideon" To: Subject: Formalizing a Response to Allegation and Eventuality of breakdown. Date: Sun, 9 Apr 2000 14:15:59 -0400 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 Dear Comments Collectors: Please add the following comments to the pile: AES should address both the allegation and the eventuality of any attack which would considerably accelerate the brute force key search. Allegation: How to handle raised allegations that the AES has been "broken". What procedure should be in place to check out those allegations. Who will check it out, how fast should a response come, and how and where to announce the finding. Eventuality: In the event that it becomes clear that a productive attack has been substantiated, it is necessary to invoke a damage audit procedure, damage control, if possible, and a credible backup plan. Thank you for taking these points into account. Gideon Samid gideon@dgsciences.com =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- D&G Sciences -- Virginia Technology Corporation P.O.Box 1022; 6867 Elm St. Suite 200 McLean Virginia 22101-1022 * U.S.A. info@dgsciences.com Ph: 703.385.4144 * Fax: 703.591.0847 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- From: "Hughes, James P. (SNBG)" To: "'AESround2@nist.gov'" Subject: AES Comments. Date: Sat, 15 Apr 2000 21:16:52 -0500 X-Mailer: Internet Mail Service (5.5.2650.21) NIST AES Evaluation comments from Storage Technology Corporation. Jim Hughes, StorageTek Fellow Please consider my comments on the following areas: A single winner, FPGA implementation, and a Modes. - Single winner I would like to suggest that primary and backup winners will effectively result both algorithms being required by the market, and once implemented will double the vendor's liability from a "patent attack". 1. Because customers will perceive the implementation of both the primary and backup algorithms as a differentiator among competitors, implementing both algorithms will become mandatory. I believe this will be the case that no matter how the standard states that the backup is not mandatory. (I agree that all standards that implement AES should implement algorithm negotiation, and that algorithm agility should be mandated and part of the certification.) 2. Since vendors will be forced by the market to manufacture both the primary and backup algorithms, they will be twice as vulnerable to a patent attack. - FPGA StorageTek makes extensive use of Field Programmable Gate Arrays and wishes that the standard algorithm provides the ability to be implemented in a key agile registered pipeline mode. That is, that the algorithm can be effectively implemented in the largest currently available FPGA as a registered pipeline and that the key be changed at least at every 3 blocks without requiring draining the pipe (a requirement to run ATM traffic). - Modes To allow use of high performance encryption, StorageTek would like NIST to acknowledge "Counter Mode" as a valid method for AES. In addition, StorageTek would like to highlight security concerns of both Counter mode and CBC-n (n>1) if cryptographic data integrity is not also present. Thanks Jim Hughes StorageTek Fellow Storage Technology Corporation Jim@network.com To: AESround2@nist.gov Subject: My criterion... Date: Mon, 17 Apr 2000 20:51:49 -0400 From: Robin Lee Powell My sole criterion that I would like to see in the AES standard (besides basic security considerations, of course, but I trust NIST can handle those) is that the algorithm be available for public use free of charge. No patents, no licensing, no nothing. I don't think that's too much to ask, and it's all I really want. -Robin -- http://www.csclub.uwaterloo.ca/~rlpowell/ BTW, I'm male, honest. As a member of the Hans Solo School of Action Before Thought, Welcome, You've Got Male. From: "Nicholas C. Weaver" Subject: Followups to AES conference and my paper To: aesround2@nist.gov Date: Mon, 17 Apr 2000 18:13:02 -0700 (PDT) X-Mailer: ELM [version 2.5 PL0] This is designed as an addendum, clarification, correction, and expansion on my paper in AES3 ("An analysis of the AES candidates ameniability to FPGA implementation") and other issues from the AES 3 conference. My opinion has changed slightly. I can now comfortably endorse Serpent as well as Rijndael and Twofish. Although there are some tradeoffs between the three, they are significantly superior to RC6 and FAR superior to MARS from a hardware viewpoint. A three sided fair coin to decide between Rijndael, Serpent, and Twofish would produce an excellent AES winner. Only a single winner (and possible backup) should be chosen. Now for more detailed comments: When considering hardware performance, one should not care about bandwidth (ECB mode). No matter what algorithm is involved, ANY desirable ECB bandwidth can be achieved by simply devoting suitable hardware resources to the problem at hand. Instead, the three factors which should be considered are encryption latency, subkey agility, and the ability to construct compact implementations. Latency, the time to encrypt a single block, dominates performance in CFB encryption. If a paper doesn't discuss latency, CFB encryption bandwidth numbers can be used to classify the algorithms. For the candidates, Rijndael has an excellent latency, followed closely by Serpent and then Twofish. Even with doubling the number of rounds, Rijndael would still be in the same class, just on the other end of the scale. RC6 is significantly higher latency, as shown in all the hardware papers presented. This is because multiplication and rotation are comparatively expensive in hardware when compared to the fixed S-boxes of Rijndael and Serpent, and the logic to implement the variable S-box in Twofish. Finally, all AES hardware papers showed that MARS has an unacceptably high latency. Even the best MARS implementation, by IBM, in a .18uM process, has worst case CFB encryption bandwidth of <500 Mb/s. An FPGA implementation of Rijndael or Serpent should easily reach worst case CFB bandwidth of > 250 Mb/s in a .25 uM process! Using a $150 part (Virtex 300) available today. Similarly, there appears to be a consensus that subkey agility (the ability to quickly generate both encryption and decryption subkeys) is necessary for at least some important applications (IPsec and other encrypted-packet routers). Note that subkey agility also affects smartcard implementations, as an agile subkey setup allows for subkey generation to occur concurrently with encryption without taking a large amount of memory to compute the subkeys into. Twofish obviously has a completely agile subkey generation scheme, since the subkeys are generated independently. Serpent, as it was pointed out by the creators, can have the subkey generation run in reverse, by starting with the last two elements and running though a reverse pipeline. Generating the last elements could be done directly, but this computation is probably too complicated in hardware. Instead, the last two elements could be generated once and then stored. This imposes the subkey generation cost once, but thereafter it can be hidden from the application time. It increases storage requirements by 256b per subkey, but does not increase the bandwidth required, because the endpoints would be fetched when decryption is desired, instead of the normal encryption key. Rijndael has an identical property, although the storage increase is the size of the key used, (128b, 192b, or 256b). I don't believe the 3 pass trick (store the A and B states for the 2nd and 3rd pass through the array) for RC6 actually works unless the L array has the same number of elements as the S array. MARS subkey generation is atrocious from a agility viewpoint. Also, the implementation complexity is absurdly difficult. Although serpent does have the highest initial requirements if performance is desired, it was pointed out to me that it has the lowest cost if performance is NOT a concern, by using one copy of each S-box, a selectable XOR tree, and 4 nibble-loadable shift registers. Overall, Rijndael, Serpent, and Twofish are all excellent candidates from a hardware perspective. RC6 is a poor candidate, due to its intrinsic latency and lack of subkey agility. MARS is simply atrocious, due to latency and subkey generation issues. Other Issues: Number of winners. The general cost of implementing multiple algorithms can best be described as the square of the number of algorithms, due to additional design complexity, verification, silicon costs, and the potential of a successful IP attack. Furthermore, it does not increase the security of the system. If any of the winners is broken, this would be a significant disaster. Instead, the better solution is "put all your eggs in one bank vault and GUARD THAT VAULT". We should be confident in our choice, confident to choose a single winner. Finally, the "Space Probe" Scenario is facetious. We have a long history of flexible software and field updates (Voyager had a bad bit in memory which was programmed around, and the OS of the Mars Rover was updated on mars). With current high density, radiation hard FPGAs, one can design hardware for such environments which is field updatable if necessary. A winner and a backup is acceptable, as the backup will undoubtedly only be implemented if it is activated. The panel session of the finalists brought up the recommendation of a 256b standard key length, with 128 and 192b keys being in the spec but "use at your own peril". Although this increases the cost of key storage and management, it does not affect subkey cost and is an idea I would endorse as a potential implementer. Also, the suggestion was made of having Rijndael's number of rounds increased. Although this would hurt performance, it would still be acceptable in hardware. Aside: This is a note for those who may be implementing the AES winner in hardware, and an element to consider when evaluating the hardware reports on the candidates. (Keywords: AES hardware implementation techniques) When implementing a hardware design for one of the AES candidates, one should follow this technique for implementing any candidate. This will maximize the bandwidth, give nearly minimal latency, and the minimum area required to get to the "best" area/performance point. One should implement a single round (single super round for serpent) and pipeline it internally to run at the desired cycle time. (Formally, this is a C-slow technique, also called inner round pipelining). This only adds a small amount of latency when compared to an unpipelined single round (limited solely to partitioning effects and the setup and hold time of the flip-flops) a small amount of area (the pipeline registers, which may be free depending on the implementation technology), while greatly improving bandwidth. If CFB is essential and the only concern, then simply remove the internal pipeline registers. If greater bandwidth is needed, simply duplicate this unit. This gives a linear increase in bandwidth, and the ability to match the desired bandwidth to the optimal silicon area. NEVER produce an unrolled pipeline. It offers negligible performance benefits (the only improvement would be a slightly lower latency for a fully unrolled but unpipelined approach) and only a very small area benefit (a little less control logic and subkey storage logic). Furthermore, you lose the ability to produce an exact match to the system requirements. Finally, for evaluation purposes, it offers an increase in performance which is essentially an exact multiple of the increased area requirement, so it conveys no additional information for the evaluation process. Summary: Single winner. Rijndael, Serpent, Twofish good. RC6 bad. MARS horrible. And hardware implementers: pipeline within a round if you want bandwidth! -- Nicholas C. Weaver nweaver@cs.berkeley.edu To: AESround2@nist.gov Subject: Why I feel Twofish should be the AES From: Mark Atwood Date: 17 Apr 2000 18:31:46 -0700 Lines: 17 X-Mailer: Gnus v5.5/Emacs 20.3 I support TwoFish to be selected as the AES. It's flexablity in implementation, in software, hardware, and in CHEAP hardware is key, I feel, to making the AES truely ubiquious, in all communication applications. We are about to enter an era of both exceptionally cheap lowpower wireless devices, and wireless communications *demands* good encryption, and much much faster "landline" bit pipes, which demands *fast* encryption. I feel the Twofish fills those two niches very well, and while the other contenders may be good at one or the other, they are not good at both, and at software based implementations as well. -- Mark Atwood Seattle, WA 206-781-8048 From: Hironobu SUZUKI To: AESRound2@nist.gov Reply-To: hironobu@h2np.net Subject: My comment for AES round 2 Date: Tue, 18 Apr 2000 10:56:47 +0900 Sender: hironobu@mail.h2np.net In AES3, there were many discussions about "performance" of various algorithms on various CPUs. Some AES developers emphasized good performance on Pentium(pro). Some paper shows performance on specific CPU, sort of 64bit RISC. Aoki and Lipmaa showed how to write fast code with MMX instruction set. It is true that Serpent which is one of AES finalist is slow on today's 32bit CPU. RC6 and MARS are fast on Pentium Pro. It seems that those algorithm developers target on Penrium Pro. Now, we must understand that those CPU are today's CPU, not for after days of AES is selected. Remember why MMX was appeared in CPU market. As far as I knew, what reason of MMX was added to CPU was developed for accelerating multimedia applications and game on desktop computer. Pentium III has some extensions for streaming data like as jpeg, mp3, mpeg and so on. Apple/Motorola developed G4 velocity engine a.k.a AltiVec technology for same reason. AMD's "3D! NOW" also. Those CPU instruction set and CPU structure was added by market requirement. After days of AES is selected, each CPU companies will develop and add new instruction for AES algorithm by market requirement, a matter of security. They must say "AES ready!", "AES NOW!" , "AES Velocity!". Also AES algorithm will be integrated into chipset like a Intel 810 chipset. I'd like say that we DO NOT overemphasize about performance on today's CPU and must focus on security for next century because AES must be selected for 21st century. Thus, from my point of view, SERPENT is a reasonable algorithm for AES. --hironobu Hironobu SUZUKI Independent Software Consultant hironobu@h2np.net URL http://h2np.net Date: Tue, 18 Apr 2000 07:47:37 -0500 From: Frank Reply-To: fhburkha@blue-bird.com Organization: Blue Bird Body Company X-Mailer: Mozilla 3.01 (Win95; I) To: AESRound2@nist.gov CC: fhburkha@blue-bird.com Subject: AES I have been following the search for the new AES for several years, and feel it is time to put in my two cents worth. While I am not very knowledgeable in the area of cryptography, I do use it in several of my programs. I must trust that all 5 candidates are cryptographically secure. I am writing to you to express my concern about the implementation of AES. Whatever algorithm you choose needs to be fairly fast on all platforms, in hardware and software. To elevate either hardware or software over the other would unduly restrict the choices available to developers. There are (and will continue to be) legitimate needs for both implementations. In hardware, I am speaking not only about smart cards that can be produced (profitably) in the 10 cent range, but about highly specialized plugin cards for computers. You must choose one and only one AES. To take the easy way out, and choose multiple winners would cause severe fragmentation in the implementation. Interoperability would become difficult or impossible. Lots of money and time would be spent trying to insure that all the AES algorithms are implemented correctly by the developers. This is something you can not waffle on. I also believe the code for the complete optimal instillation of AES for all common platforms should be patent and royalty free. I would like to see it distributed with a GNU copyleft license, if at all possible. -- Frank Burkhardt The above comments are mine, and mine alone. They may or may not be supported by the company I work for. Date: Tue, 18 Apr 2000 06:08:59 -0600 From: Rob Neal Subject: AES round 2 finalist comments To: AESround2@nist.gov Reply-to: rob.neal@lmco.com X-Mailer: Mozilla 4.7 [en] (WinNT; U) X-Accept-Language: en Hello, I understand this is the e-mail address to send comments on the algorithms being considered for selection as the AES. I would like to recommend that the algorithm known as 'TWOFISH' be selected. It would seem to present the best balance between performance and security, and be the best suited for the intended use. Thank you, Rob Neal rob.neal@lmco.com Sender: Anne.Anderson@East.Sun.COM Date: Tue, 18 Apr 2000 10:26:04 -0400 From: ANNE ANDERSON Reply-To: aha@acm.org Organization: Sun Microsystems Laboratories X-Mailer: Mozilla 4.7 [en] (X11; U; SunOS 5.7 sun4u) X-Accept-Language: en To: AESround2@nist.gov CC: aha@acm.org Subject: Comment on AES Round 2 Speaking for myself as an implementor of protocols that use cryptography (PKIX, IPSec), and not as an employee of Sun Microsystems: Interoperability is very important to internet security. If two platforms need to communicate over the internet, but have no cryptographic algorithm in common, they will not be able to communicate securely. Many platforms (smart cards, small devices) do not have room for more than one algorithm, and I expect such devices to be a larger part of the market for security as time passes. For these reasons, I highly recommend choosing ONE AES algorithm. It should be one that does not have unacceptable performance on smart cards, in software, or in hardware, but need not be the very fastest. Anne Anderson -- Anne H. Anderson Email: aha@acm.org Sun Microsystems Laboratories 1 Network Drive,UBUR02-311 Tel: 781/442-0928 Burlington, MA 01803-0902 USA Fax: 781/442-1692 Date: Tue, 18 Apr 2000 11:19:54 -0400 From: Rob Gerlach Subject: AES Comments... To: AESround2@nist.gov Cc: Bruce Schneier Reply-to: Rob Gerlach Organization: RIT/NTID X-MIMEOLE: Produced By Microsoft MimeOLE V5.00.2615.200 X-Mailer: Microsoft Outlook Express 5.00.2615.200 X-MSMail-priority: High Dear Sir/Madam, I have a comment I'd like to share with you, in regards to the AES Development Effort. I feel that Twofish, given its speed and currently unbreakable security status, would best suit my needs as both an end-user and a consumer; at least when compared to the other AES candidates. I sure hope you'll agree. The capacity in which I am telling you this is as a 19-year old Information Technology (IT) Major at Rochester Institute of Technology (RIT), a person interested in Data Security & Encryption, and as a consumer who often purchases items online. Please feel free to contact me with any comments or questions you may have. Many thanks, -Rob Gerlach :-) http://www.rit.edu/~rmg4048/resume/ (Please note that the above page is somewhat outdated, and is undergoing a move. There is only one "broken" link as far as I can tell. I apologize any inconvenience.) Sender: patrick@green.wl.vg Date: Tue, 18 Apr 2000 12:14:21 -0400 From: Patrick Gardella Organization: Whetstone Logic, Inc. X-Mailer: Mozilla 4.7 [en] (X11; U; FreeBSD 5.0-CURRENT i386) X-Accept-Language: en To: AESround2@nist.gov Subject: Comments I have always felt that the biggest detriment to adequate security is the speed of the implementation and the system that it takes to run it. I would like to see that AES work on all systems from the cheapest smart card, to the highest powered system. Patrick ---------- Patrick Gardella patrick@whetstonelogic.com VP-Technology patrick@freebsd.org Whetstone Logic, Inc. This space intentionally left blank. Date: Wed, 19 Apr 2000 02:10:34 -0400 From: Kevin Bealer X-Mailer: Mozilla 4.5 [en] (Win98; I) X-Accept-Language: en,zh,zh-CN,zh-TW,ca To: AESround2@nist.gov Subject: comment regarding AES (unofficial) I would recommend TwoFish, admittedly influenced by having read Schneier's book, and newsletter. I would rate the following as the critical important factors in how choice of AES will affect me (and those like me): 1. Fast internet usable software. This means hardware-feasable for high speed. By the time the technology reaches users, it will have influenced PC hardware enough... Hardware solutions will be available before a significant user base is there to "populate" them. 2. Personal hardware - signatures, financial, and security applications. In a few years, this will provide the security that signatures, credit card numbers supposedly provide now. This may be the most sensitive to the choice made here. Personal financial and identity security is the requirement that prevents most savvy users from stepping up their reliance on technology. 3. High security will be extremely important to me, not just on personal paranoia, but also because errors here will be extremely costly. We need to assume enormous resources, fantasticly high stakes, (NASDAQ is already almost all tech stocks..) DES was immune to media ignorance effects via semi-obscurity, but today the least "bad tech news" can create lots of badly written but influential panic stories in the non-trade press. Crypto/security will be the last technology issue the media/public ever "understands", but they already fret over it. 4. Patriotic reasons. Although I am not a "conspiracy theorist", there is something fundamentally American about these people: only in radically democratic societies is this on the "fiction" shelf. In geek politics, Twofish makes better political sense - it's author "looks" less conspiratorial. Thanks for your time, Kevin Bealer From: "Simson L. Garfinkel" To: Subject: Comments on Round 2 encryption candidates Date: Tue, 18 Apr 2000 23:47:44 -0400 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2615.200 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2615.200 To: NIST AES Round 2 Committee Subject: Comments on Round 2 encryption candidates From: Simson L. Garfinkel To the Selection Committee, My name is Simson Garfinkel. I am the author and co-author of nine books, most of which are on computer security and/or system design. Most recently, I am the author of the book "Database Nation" (O'Reilly, 2000). I am also notably the co-author of the books "Practical UNIX and Internet Security" (O'Reilly, 1996) and "Web Security and Commerce" (O'Reilly, 1997.) Although I am not a cryptographer, I do use encryption on a regular basis in my work. I also do a fair amount of consulting for software designers, telling them how they can use encryption in their programs. I am currently engaged as a consultant by a company that is attempting to build strong encryption into a device that uses the Motorola MC68HC705JB4 microprocessor. This microprocessor has just 176 bytes of RAM and 4672 bytes of ROM. Even though the 6805 architecture is more than 25 years old, it is still a strong force in the industry today. The microprocessor is popular because it can be purchased for less than $2 in relatively small quantities. The application that has been created for this microprocessor leaves just 64 bytes of RAM available and roughly 1000 bytes of ROM. I do not believe that our restrictions are unique. Indeed, there are many smart card applications that could benefit from strong encryption. It is my experience that system designers usually develop their systems without encryption and then seek to add it as an afterthought. Therefore, it is likely that many other designers will find themselves in the situation that I am now in --- trying to fit relatively large algorithms into a relatively tiny space. Based on Geoffrey Keating's paper, it would appear that the Rijndael algorithm is the only AES candidate that will fit in our application. We urge you to strongly consider either the Rijndael algorithm as it is or else a strengthened version of this algorithm. Failing that, we would urge you to adopt a standard that supports multiple algorithms. Thank you for your time. Simson Garfinkel X-EM-Version: 4, 0, 0, 0 X-EM-Registration: #31E3420614450303B930 X-Mailer: My Own Email v3.5 From: "Keyur Mithawala" To: AESround2@nist.gov Subject: Suggestion... Date: Wed, 19 Apr 2000 10:40:48 -0600 Hello, I am working on a Kerberos based security system for networks. As it is evident, we all will be using AES standard for our future developments. I will like to explain my viewpoint for chosing AES algo. 1>> Well, the most important part for an encryption algorithm is SECURITY. Its hardware demands dont matter much. The hardware will catch up in one or two years, but this standard will be there atleast for 5 years. 2>> SPEED for LOW AMOUNT DATA. Large level data encryption is useful only for large corporations. Most users use encryption to encrypt small amounts of data like passwords, etc. Smart cards also encrypt tiny amounts of data. As a kerberos programmer, I use encryption to encrypt authentication data. Thank you, Keyur _____________________________________________ Free email with personality! Over 200 domains! http://www.MyOwnEmail.com Date: Wed, 19 Apr 2000 17:20:59 +0100 From: "Jim Gopinathan" Organization: ATMEL Smart Card ICs X-Mailer: Mozilla 4.7 [en] (WinNT; I) X-Accept-Language: en To: AESRound2@nist.gov Subject: Re: AES and Smart Cards In smartcard applications speed as well as ROM, RAM and EEPROM requirements are important. Table 8 in AES3 paper titled "Performance Evaluation of AES Finalists on High-End Smart Card", provides a summary of the memory and processing requirements on Toshiba's 8-bit T6N55 smartcard. The information provided is for algorithm implementations not modified for protection against power analysis, timing attacks and other similar forms of attack. Modifying code on 8-bit smartcards for protection against these forms of attack will significantly increase ROM, RAM and EEPROM requirements. When DES code on 8-bit HC05 smartcard was modified to be resistant to both timing and DPA attacks, both the code size and RAM requirement approximately doubled. No doubt a similar increase in code size will occur when the AES candidates are modified to be resistant against these forms of attacks on 8-bit smartcards. The AES candidate eventually selected, when implemented in software on 8-bit smartcards to be resistant against power analysis and other forms of attacks, must not occupy a significant portion of the ROM and throughput must meet the current and future requirements of smartcard applications. Jim Gopinathan, ATMEL Smart Card ICs, East Kilbride, Scotland. X-Authentication-Warning: ns1.crl.go.jp: Host crlgw1 [133.243.18.250] claimed to be crlgw1.crl.go.jp Date: Thu, 20 Apr 2000 13:19:13 +0900 (JST) From: Tom Holroyd X-Sender: tomh@holly.crl.go.jp To: AESround2@nist.gov Subject: comment from the public Multiple algorithms. Aside from the political feuding that will be avoided by not picking a single algorithm, multiple algorithms means that implementors will have to create a mechanism whereby new algorithms can be swapped in, allowing for easy upgrades in the future when all of the current AES candidates start showing their age. Mandate flexibility. IMO, Dr. Tom Holroyd "I am, as I said, inspired by the biological phenomena in which chemical forces are used in repetitious fashion to produce all kinds of weird effects (one of which is the author)." -- Richard Feynman, _There's Plenty of Room at the Bottom_ Date: Thu, 20 Apr 2000 09:35:01 -0700 (PDT) From: Ray Van De Walker Subject: Embedded Systems Criteria To: AESround2@nist.gov I've designed embedded computer systems for 17 years. My priority for AES would be: 1. Software efficiency. Processors are now cheap, and in most applications, AES will be a software-only option. I think this is more important than security, as long as the algorithms are not total push-overs. 2. Minimal conforming implementations will include at least two standard algorithms, and all standard algorithms of any previous AES. Security concerns should be addressed, but encryption is a communication technique. Old software often does not advance. 3. Conforming communication implementations should have a notification and negotiation function, so that the most secure mutually available algorithm is selected. The later implementation should notify the earlier of broken algorithms. 4. I strongly favor use of a GNU-style license. Derivative designs will thereby become public, which aids the public good by reducing costs. 5. The license should explicitly permit reverse engineering and cryptanalysis of any application, provided that successful attempts are published. Ray Van De Walker R.G. Van De Walker Inc. 9181 Crawford Circle Huntington Beach, CA, USA, 92646 __________________________________________________ Do You Yahoo!? Send online invitations with Yahoo! Invites. http://invites.yahoo.com From: dave-aes@bfnet.com Sender: dave@bfnet.com To: AESround2@nist.gov Subject: Comment regarding the AES competition Date: 20 Apr 2000 15:14:35 -0700 Lines: 7 User-Agent: Gnus/5.070099 (Pterodactyl Gnus v0.99) Emacs/20.4 I am a software designer specializing in custom network server systems. I have many customers who require real-time encryption in software. I have thoroughly examined the submissions to AES and believe that Twofish is the most suited to my applications due to its great software performance. I think that Twofish gives the best security to performance trade-off of the submissions, and has the most implementation flexibility. So I support Twofish for AES. Sender: gwyn@ridley.nist.gov Date: Fri, 21 Apr 2000 10:08:39 -0400 From: "Douglas A. Gwyn" Organization: U.S. Army Research Laboratory X-Mailer: Mozilla 4.72 [en] (X11; U; SunOS 5.7 sun4u) X-Accept-Language: en To: AESround2@nist.gov Subject: AES public comment X-MIMETrack: Itemize by SMTP Server on mail/arl(Release 5.0.3 |March 21, 2000) at 04/21/2000 10:10:51 AM, Serialize by Router on mail/arl(Release 5.0.3 |March 21, 2000) at 04/21/2000 10:11:57 AM, Serialize complete at 04/21/2000 10:11:57 AM My only comment at this stage is that the final standard should specify only *one* of the algorithms, not multiple algorithms. One reason is that that was the original impression some entrants had when agreeing to waive patent rights etc. Another reason is the added expense and operational hassle of selecting and indicating a choice of algorithm. There is no apparent security benefit to multiple algorithms; they are sufficiently similar that any efficient method of cryptanalysis for one of them is likely to apply to another. From: keb@smrn.com X-Sender: keb@mail.smrn.com X-Mailer: QUALCOMM Windows Eudora Version 4.3.1 Date: Sun, 23 Apr 2000 11:12:34 -0800 To: AESround2@nist.gov Subject: AES candidates Sirs: I'm CTO of MyProof.com, a small e-commerce startup with products built upon strong cryptography. I strongly support TwoFish for the final AES choice. Sincerely, Kenneth Broll From: sidners@tsainc.com To: AESround2@nist.gov Subject: AES Round 2 public comments X-Mailer: Lotus Notes Release 5.0.2b (Intl) 16 December 1999 Date: Mon, 24 Apr 2000 13:56:46 -0500 X-MIMETrack: Serialize by Router on lnm002/TSA(Release 5.0.2b (Intl)|16 December 1999) at 24/04/2000 13:56:51, Serialize complete at 24/04/2000 13:56:51 I am no cryptographer, but my company is a major software vendor in the international banking community. We are the leading vendor of computer systems to process electronic payments. It has been estimated that 40% of the credit and debit card transactions in the world pass through our systems. Cryptography is becoming more important in electronic payments - witness the success of SSL in Internet communications. We see the next major thrust in payments to be mobile phones, replacing both plastic and cash as the preferred payment mechanism, first outside the US and then domestically. We expect this to happen over the next 3 to 5 years. Therefore we are looking for a symmetric key algorithm that is 1) easily implemented in mobile phones 2) fast when encrypting 512 to 4096 byte messages 3) exportable 4) with increasing strength based on key size 5) standard - that is, we would like a single algorithm, to which the industry can build optimized, provably secure implementations, that will interoperate globally as well as DES and Triple-DES have. Like I said, I am no cryptographer, so I am unable to recommend any of the five submittals. However, Bruce Schneier indicated that you would appreciate comments as to what criteria are important. Thank you for your consideration, Sid Sidner Senior Engineer, Internet Division ACI Worldwide, 330 South 108 Avenue, Omaha, NE 68154-2684 Mobile: 402-850-7092 (new!), Other work: 402-778-1851, Fax: 402-778-1840, sidners@tsainc.com, www.aciworldwide.com A TSA Company "Rationality is the servant of intuition." To: AESround2@nist.gov dcc: Subject: comment on AES candidates Date: Tue, 25 Apr 2000 08:49:57 -0700 From: Dan Stromberg - OAC-DCS So far, I think twofish should become the AES. I personally am primarily concerned with speed of encryption in software, but an all- around candidate is best I think. Sender: bkelly@odo.edwards.af.mil Date: Wed, 26 Apr 2000 11:10:34 -0700 From: Brent Kelly X-Mailer: Mozilla 4.51C-SGI [en] (X11; I; IRIX 6.5 IP22) X-Accept-Language: en To: AESround2@nist.gov Subject: AES Finalist Comments Gentlemen: I support Twofish for the AES, I believe it's combination of security and relative ease of implementation in either hardwaror software make Twofish the optimum choice. I do not think there should be multiple standards, as may have been suggested. Thank You, Brent -- Cedric Brent Kelly Computer Sciences Corp. 805-277-7677 voice Ridley Mission Control 805-277-5377 fax Edwards A.F.B., Ca. 93523 Clear Skies... EMAIL: bkelly@odo.edwards.af.mil Date: Thu, 27 Apr 2000 08:54:31 -0700 (PDT) From: "Nicholas C. Weaver" To: AESround2@nist.gov Subject: My last comments Cc: nweaver@cs.berkeley.edu This is my LAST feedback note (this time I really mean it). RC6 keyschedule "hack". It was pointed out to me that the trick is to not just store and fetch the states of A and B, but copies of the L array, for the second and third pass through the S array. This does considerably increase the storage and fetching required (112B instead of 32B for 256b keys), but is still better than fetching all 176B of fully expanded subkeys. Thus, the savings exist but it is still "not that much". One could also use this for a smartcard where key setup and encryption are done concurrently to save memory, but once again, the savings are "not that much" for a 256b key. Subkey agaility isn't just for hardware, but for smartcards which lack the resources to store the fully expanded keys. Also, this is a response of mine on the MARS key schedule, describing how if one is willing to leave the key schedule potentially open to power and timing attacks, one can do the string matching & correction of the multiplicative subkeys without requiring too much resources or time. I use FPGA terms, but ASICs and custom logic also apply. (Hopefully it will be a moot point, my bias against MARS is clear, but Just in Case): For hardware, although I didn't consider the stringmatching portion in detail, I believe the cost should be fairly minor if performance is not an issue, and even if performance is a moderate concern. Here is why: It takes 1 lut to determine if four inputs are all 0 or all 1. (Output is 1 if they are all the same, otherwise 0). If you AND the results together from several of these, this will be a 1 if you have an overlap of one input between two luts. (EG, bits 0, 1, 2, 3 into lut A. 3, 4, 5, 6 into lut B, etc, and then and the outputs all together). Thus, it would only take 6 LUTs to evaluate a 12 bit run. If one wants fine information on when a run ends, it takes 1 lut/bit, which isn't that large. The slow approach would just be to load the key into a shift register and do a shift & match approach. If faster performance is required, have a couple of additional outputs which would show where the currently examined run ends, so you could skip 4 for each shift. EG, if first 4 don't match, skip to the last unique one in that 4. If the first 4 do but the next 3 don't, skip 4. If the first 7 do but the next one doesn't, skip 7. The additional logic for this would be very small. Since the MARS hardware requires a barrel rotator, if you are not doing subkey generation and encryption in the same cycle, you could reuse the block to skip through the keys. This does leave the subkey generation potentially open to power or timing attacks, however, as the work and time are vastly different based on the bit pattern in the multiplicative keys. However, the MARS subkey generation in general, even without the string matching step, poses serious problems if fast subkey generation is desired in hardware, due to the sequential dependancies. -- Nicholas C. Weaver nweaver@cs.berkeley.edu It is a tale, told by an idiot, full of sound and fury, .signifying nothing Date: Sat, 29 Apr 2000 11:44:20 -0700 From: David Eppstein To: AESround2@nist.gov Subject: Comment on selection of the algorithm for AES X-Mailer: Mulberry/2.0.0 (MacOS) Over the expected lifetime of AES, improvements in technology and algorithms will surely make performance considerations less of a concern, and security considerations more of a concern. Therefore, I strongly agree with AES's original charter "The security provided by an algorithm is the most important factor in the evaluation." To me this means that, since RC6, Rijndael, Serpent, and Twofish all appear to have adequate and roughly similar performance, we should choose one that has been more conservatively overengineered for security, rather than one that has trimmed the number of rounds to the minimum believed-secure level. I.e., Serpent and Twofish should be preferred over Rijndael and RC6. Also, to minimize the possibility that any AES cipher is broken, we should have one and only one algorithm chosen. Taking into account the requirements of simplicity and key agility, I would be mildly in favor of Serpent over Twofish. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ From: "apli" To: Subject: AES Date: Tue, 2 May 2000 07:47:16 +0800 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.72.3110.5 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Dear Sir: I have known AES for only a few months since my major in mathematics. As we seen, the five candidate algorithms selected for AES have made further endeavors on the security and implements over DES. The progresses as they made, it seems that the design ideas adopted in the most of these algorithms are yet mainly as one in DES. The structure of DES have been intensive studied recent years,and is relatively easy to be attacked. For this it can be seen in the late cryptanalyses papers on these algorithms. So, the best in the finalist there should be some more new ideas and new structures. If you intend to call for additional new algorithms in the future some time, I would like to submit one. Besides, I have an opinion that as the knowledge and technology for computer have been developing very rapidly the servive period drawn up for one algorithm of AES should not be too long. The best maybe NIST should make up one research group to keep research on the algorithms of AES. Sincerely yours Anping Li X-Sender: mike@mail.pcfax.com X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Thu, 04 May 2000 08:58:08 +0100 To: AESround2@nist.gov From: Mike Lake Subject: AES comments I hope that comments from overseas users are acceptable. My company is involved with encryption usage in software, firmware and hardware and for test purposes we have implemented a number of the candidate algorithms. Our primary desire would be a standard that can be implemented across a wide range of platforms rather than having multiple standards optimised for each platform. Obviously we would like to see a high level of security, tight code and fast throughput. For these reasons we are strongly in favour of the Twofish algorithm - primarily because of its suitability in the widest range of applications Best regards Mike Lake Chairman: Wordcraft International Limited Web site: http://www.wordcraft.co.uk Office: 01283-731400 (International: +44-1283-731400) Mobile: 07973-432085 (International: +44-7973-432085) From: Jeffrey Streifling To: AESround2@nist.gov Subject: Last minute notes Date: 4 May 2000 18:20 -0600 I sent a message earlier suggesting that simplicity be a deciding factor in the AES selection process; my choice for simplest candidate was RC6. After reading the AES papers and comments, it looks like it will probably be discarded along with MARS due to the inefficiency of the multiply in some environments. If there is a secondary AES pick, it would make a good choice (due to the fact that its structure is very different from everything else, and thus unlikely to break simultaneously with the primary pick), but the idea of a secondary AES pick motivated by security reasons seems a bit costly compared to the alternative of requiring compliant implementations to parameterize the number of rounds. Observe that virtually all modern cryptanalysis of non-linear ciphers breaks at some number of rounds. When we do differential cryptanalysis, we are able to break up to n rounds using a particular technique, whereupon our technique becomes more expensive than brute-force, or otherwise runs out of theoretical gas. Similarly, more rounds disguise linear bias, causing linear cryptanalysis to require more plaintext. Other kinds of cryptanalysis run out of gas after a particular number of rounds; it is exceedingly rare to find a break of a cipher that can simultaneously solve any number rounds of said cipher in general with equal ease. The point to note is that security in all cases has hinged on the number of rounds. Therefore, a simple way to future proof an AES selection is to require implementations to parameterize the number of rounds. If somebody breaks 100 rounds of AES, we give 'em 200. If somebody breaks 150 rounds, crank it to 300! It may be disconcerting and dog slow, but guaranteed to be interoperable with smart-cards and other limited environments where in practice only one AES candidate will be implemented regardless of how many are chosen. (If the plan is to switch to a backup cipher, then we suddenly have the huge problem of redeployiny hardware, smart-cards, etc, that only actually implemented the primary candidate.) Furthermore, compliance would have already been tested; there would be no need to wait through overhead of getting new products out when time may be of the essence (supposing some future break of N rounds proves dangerously practical). Cranking Rijndael or RC6 to thousands of rounds might possibly seem ugly compared to having a backup, but it would be able to function for a few years while a new standard was created. The advantanges would be (1) guaranteed instant switchover -- just poke in the new desired number of rounds and (2) guaranteed ubiquitous availability -- it is reusing the machinery already deployed. Furthermore, creating the replacement cipher after the hypothetical lethal break would permit it to take advantage of the new crypographic techniques suggested by the break, which would make it a better solution than any backup we can propose now. Therefore, implementations to be certified AES-compliant should be required to let users change the number of rounds (along with the key -- configuration is already required), although it clearly should default to the standard value. Note that this would recommend choosing RC6, Rijndael, or Serpent since MARS and Twofish do not have parameterized round count. Then again, MARS and Twofish are already the two ciphers which suffer from excessive complexity. My personal order of preferences for the AES2 candidates based on complexity is (1) RC6 (2) Rijndael (3) Serpent (4) Twofish (5) MARS (and therefore don't be surprised that I think that at least one of RC6 and Rijndael should be in the standard). Reflecting on the possibilities, then, of various single or multiple candidate choices, it occurs to me that the reasons the NIST should choose a possible secondary candidate for the AES is not security, which would better be accomplished with a larger number of rounds (to allow instant, ubiquitous switch-over as described above), but rather implementation flexibility to allow AES to exist in some form on more environments that could be addressed by a single cipher and to permit a wider variety of security/performance tradeoffs. The secondary cipher, if chosen, should be RC6 because it tends to excel in the environments that make the other ciphers flop (consider the Java performance, for example). I can't see it becoming the primary AES due to its difficulty working in low-end microcontrollers and the hardware overhead of the multiplier (and possibly the poor performance once the number of rounds are increased as may be indicated by recent cryptanalytic results). Or, if the flexibility argument merits no consideration, mandate just one cipher for the advantage of maximum interoperability . . . What then, of the primary AES choice? The multiplier required by RC6 and MARS makes them inefficient in a lot of environments; they can probably be dismissed out of hand (particularly MARS, which was practically ignored in the hardware papers). Further, the complexity required for the Twofish key schedule makes it a lousy cipher key agility is required (such as encrypting ATM cells, or hash function constructions), where the code must be kept simple and easy-to-understand (where the cipher is part of a larger program that spans a security boundary and thus must be subjected to extensive, expensive code audits) or where it is otherwise desired to produce a simple implementation for academic or "one-shot" purposes. Should Twofish be chosen as the sole AES standard, its key schedule would raise an annoying if surmountable barrier to simple implementations: you either port existing code from somewhere else, or sit down and do a fair amount of thinking . . . As for Rijndael versus Serpent, my preference would be for Rijndael given my bias toward simple ciphers, although the number of rounds probably needs to be increased a little bit based on recent cryptanalytic results. I would not say the decision is obvious from performance considerations, though. More rounds will slow Rijndael, and Dag Arne Osvik as significantly sped up Serpent and provided directions for future speed-ups. Furthermore, I think that the AES algorithm, once widely implemented, will be come a sort of benchmark of computer speed (rather than the other way around), and that chip manufacturers will focus on making Serpent run fast on their processors as a marketing tool. For example, if Serpent is chosen as an AES candidate, Biham's bitslice would probably be added to new processors, significantly speeding up Serpent with respect to other candidates. Furthermore, Serpent scales marvelously to 64 bit architectures (and in general, to n-bit architectures in bit-slice implementations), thereby allowing it to improve with age (it is already second-fastest on current 64-bit benchmarks, and seeing it come out fastest once chipmakers tune their architectures for AES would not surprise me). It would be useful to increase the number of rounds of other ciphers to approximately match the security of serpent, whereupon Serpent would prove quite fast. Serpent has the potential to significantly contribute to the design of modern microprocessors should it become the chosen standard. If the NIST chooses a single cipher for the AES, it should probably be Rijndael (an opinion that I think was mirrored in the conference response papers); my reason for choosing it would be simplicity. If the NIST chooses two ciphers for AES, it should choose Serpent as the primary and RC6 as the secondary. It should in any case parameterize the chosen ciphers with respect to round counts so they can easily be changed in the field; or, failing that, choose 32-round Serpent as the singular standard for security reasons. Actually, any combination of the simpler, round-parameterizable, would be useful -- even providing Rijndael as a secondary for Serpent would admit some reasonably simple implementations. Failing all else, it is sufficient to require that the ciphers chosen be round-parameterizable to function as a life-boat cipher in the event of a break (before a new cipher is created); all such ciphers are secure given sufficient rounds, and all AES2 ciphers that meet this criterion happen to be simple enough to admit complexity-cheap implementations. Jeffrey Streifling Subject: Suitability of Rijndael without extra rounds Cc: ggr@qualcomm.com At the recent AES3 conference, there was much discussion about the number of rounds of the candidates, particularly Rijndael. There seemed to be a general feeling that Rijndael had too few rounds for an adequate safety margin. I disagree with that sentiment. To put it more clearly, I think Rijndael's safety margin is perfectly adequate against publicly known or hypothesised attacks. Of course it is possible that some newly discovered or revealed attack might apply to any of the candidates (and perhaps MARS has a slight advantage in this eventuality). If that happens, I find it hard to believe that increasing the number of rounds from, say, 10 to 14 in the 128-bit case, will save Rijndael from a devastating new attack. As support for my opinion, I offer the following three examples: DES, in which the resistance to differential cryptanalysis is very close to its key-limited strength, and yet is the most widely deployed and respected encryption algorithm ever. SKIPJACK, where attacks such as Biham's go right to the edge (31 out of 32 rounds), and yet it is another apparently successful algorithm. FEAL, which was designed before differential cryptanalysis was publicly known, had to have the number of rounds quadrupled before it approached a level of real security against that "unknown" attack. Personally, I'd like to see Rijndael, as submitted, adopted as the AES algorithm, although there's very little between the candidates. I don't think committee-based micromanagement, about the number of rounds, should be applied to any of the candidate algorithms (in either direction). sincerely, Greg. Greg Rose INTERNET: ggr@Qualcomm.com Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470 Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/ Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C From: Gideon Yuval To: "'AESround2@nist.gov'" Subject: protocol stuff Date: Mon, 8 May 2000 16:18:42 -0700 X-Mailer: Internet Mail Service (5.5.2651.58) Brian Snow suggested having AES and double-AES specifiable in protocol negotiations. I would like to add one thing: have the bit-code for AES be 00000..., and the bit-code for double-AES be 11111...; all codes in the middle should crash _before_ shipping any bits out. The codes for AES and 2AES should work all the way (& thus be testable all the way). Delivered-To: fixup-AESround2@nist.gov@fixme User-Agent: Microsoft Outlook Express Macintosh Edition - 5.01 (1630) Date: Tue, 09 May 2000 21:50:17 -0500 Subject: Comments on Rijndael, Serpent, Twofish software implementation From: "David C. Oshel" To: I have incorporated Rijndael, Serpent and Twofish in a small file encryption grinder for Macintosh. This little utility includes a Test routine designed to exhibit simple characteristics of the program's keystream – produced using the algorithms in question. While not especially interesting as analysis, the routine does give the algorithms a workout. The default, "Lite," routine -- basically a species of PrngXor -- completes the Test routine in about 15 seconds on a Macintosh Powerbook G3 (Bronze). Rijndael typically concludes the task in 21 seconds, compared to 23 seconds for Serpent, and 1 minute 19 seconds for Twofish. IMHO, this clearly argues against Twofish in purely software implementations. The code I used was Brian Gladman's as he had it posted near the end of Round 1, in other words, the source which #includes "../std_defs.h", pretty nearly straight "out of the box" and compiled with Metrowerks' C++ compiler. I did not bother testing RC6 or Mars because there seemed little practical point in using candidates with reservations about their intellectual property status. -- David C. Oshel mailto:obsidian@kagi.com Cedar Rapids, IA http://homepage.mac.com/dcoshel/Obsidian.html ``Tension, apprehension and dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_ From: DAEMEN.J@protonworld.com To: AESround2@nist.gov Subject: Royalty Statement of the Rijndael Team Date: Wed, 10 May 2000 13:58:07 +0200 X-Mailer: Internet Mail Service (5.5.2650.21) At the request of the NIST AES Team, here is an updated Royalty Statement for Rijndael: In the case that NIST decides to adopt as AES an algorithm that can be considered as a variant of Rijndael, the Rijndael team will make no royalty claims whatsoever. Joan Daemen & Vincent Rijmen From: Carlisle Adams To: "'AESRound2@nist.gov'" Subject: For inclusion in the Round 2 public comments... Date: Thu, 11 May 2000 12:10:46 -0400 X-Mailer: Internet Mail Service (5.5.2650.21) Dear NIST AES Selection Committee, >From reading NIST's Round 1 report, from looking at the public comments received so far in Round 2, and especially from attending the 3rd AES Conference last month, one thing in particular strikes me as relatively clear: Rijndael appears to have the fewest drawbacks of the 5 finalists. There seem to be concerns associated with MARS, RC6, Serpent, and Twofish. Whether the difficulties involve complexity, performance, overall design, key agility, suitability for very constrained environments, suitability for tomorrow's 64-bit (or higher) processors, or some other reason, it seems that the choice of any of these four finalists will end up causing some level of dismay for some group of implementers. Rijndael, by contrast, appears to have very many "plusses" and very few "minuses"; it seems to place at least in the middle-of-the-pack (and often places first or second) on every criterion considered and on every platform proposed. Furthermore - and to me this is significant - it is the algorithm most often chosen as a favorite by the submitters when they are asked to pick a candidate other than their own. As far as I can tell (from both public and private discussions at last month's FSE/AES conferences), the only minor concern with respect to Rijndael is that its margin of security may not be high enough for the 50 or 100 years that Ross Anderson proposes will be the actual lifetime of the AES cipher. Consequently, I recommend adding 4-6 rounds to this algorithm for each of its three sizes (i.e., going from {10, 12, 14} rounds to {14, 16, 18} or {16, 18, 20} rounds). This should allay any fears regarding security margin without destroying its substantial performance characteristics on known or anticipated platforms (that is, it might no longer be the fastest of the candidates, but neither would it be among the slowest because of its current impressive speed). In my reading and conversations thus far, I have yet to come across a significant number of people that would seriously object to Rijndael being selected as the AES cipher, especially with the addition of a small number of rounds. I have not found this same level of general acceptance for any of the other candidates. Given that the people following the AES process are evaluating the ciphers from a multitude of different (and sometimes opposing) perspectives, with a wide variety of skill sets, backgrounds, and biases, in my opinion this speaks volumes. Carlisle Adams X-Authentication-Warning: korkeik.ii.uib.no: larsr owned process doing -bs Date: Thu, 11 May 2000 23:37:53 +0200 (MET DST) From: Lars Ramkilde Knudsen To: Jim Foti cc: AESround2@nist.gov Subject: Re: AES - RE: a question at AES3 Jim, Serpent is completely royalty-free. We let the patent lapse. Whether you decree 16 rounds or 64, we can't charge anyone a penny. Neither can anybody else, as far as we can see. Since Serpent resuses the DES technology (recall that the first version of Serpent even used the DES S-boxes) and since IBM's patent on DES expired a long time ago, it's unlikely in the extreme that some third party will come up with a subterranean patent. This wasn't a deliberate design feature, just a side effect of our decision to stick to tried and tested primitives. So we believe that our algorithm is not just the most able to resist attacks involving cryptanalysis, but also attacks involving IPR. Best regards Ross Anderson Eli Biham Lars Knudsen From: "Simpson, Sam" To: aesround2@nist.gov Subject: Round 2 AES Comments X-Mailer: Internet Mail Service (5.5.2650.21) Date: Fri, 12 May 2000 09:46:39 +0100 Dear Selection Committee, I have watched the AES process with great interest for two years and have finally decided to write to share my thoughts on the selection of the final algorithm(s). I am a user & implementor of encryption and have assisted Dr B.Gladman in significantly improving the original Serpent S-BOX performance [1]. At this late stage I believe that decisions can be made in three key areas, as the previous round appears to have removed all clearly inappropriate ciphers. I believe any of the 5 remaining ciphers will make an adequate AES cipher, but it is my belief that NIST has the opportunity to select an excellent cipher from a choice of two or three. Security Security *must* be the primary concern when evaluating these ciphers. An "over- engineered" cipher will merely be slow until hardware is sufficient for the application, but an "under-engineered" cipher would render the cipher obsolete (or at a minimum be subject to the same kind of mistrust as per DES). NIST has declared AES [2]: 'A crypto algorithm for the 21st century' and security will certainly be the metric by which this statement is evaluated. 1) AES should rely on tried and tested security constructs. Several ciphers employ relatively new constructs (MARS & RC6 with data dependent rotations, Twofish & Rijndael with MDS) which will not be adequately assessed in the two-year time frame. The strength of RC6 seems to depend solely on DDR and RC6 should therefore be dropped from further consideration. 2) Algorithms should be clean and easy to evaluate. Again, in the two-year timeframe it is unlikely that the inner workings of a complex algorithm will be fully assessed (see for example [3]). From a cryptanalytic perspective both MARS & Twofish are significantly more complex than the other three algorithms and this should count substantially against the algorithms. 3) Number of rounds should be over-engineered (as per [4]). RC6 appears to be significantly under-engineered whilst MARS & Rijndael are slightly under-engineered. Twofish is over engineered, but Serpent is by far the most over-engineered design. 4) The successful algorithm should not be prohibitively expensive to secure against "operational" attacks on smartcards. 5) The argument that the heterogeneous structure of MARS adds some security is plausible, but the benefit seems relatively small compared to 2) above. Platform Applicability Another important concern when selecting an algorithm is whether it runs on all necessary platforms. Clearly, an ideal situation is the selection of an AES cipher that is fully compatible across the full range of potential platforms: 1) My understanding is that MARS & RC6 cannot be implemented on very low-end smart cards [5]. I assert that neither MARS nor RC6 offer anything particularly special over the other 3 candidates (RC6 has a very clean design and MARS has the benefit of heterogeneous structure, but I don't think these benefits are compelling) and should therefore not be considered for AES. 2) The remaining three ciphers appear to be applicable to all platforms. Rijndael appears to have the most uniform speed across all hardware and software platforms (discussed next). Performance I believe performance should be used as a metre after the two previous criteria have been suitably satisfied - without either security or pervasiveness the standard will not be widely accepted and deployed. 1) Need to consider the whole range of applicable software and hardware implementations, not just results that suit specific ciphers. Rijndael performs very well across all platforms; Twofish works well across all platforms apart from Java [6]. It should also be noted that Twofish is very slow in software when only encrypting one or two blocks due to the large key-setup overhead. 2) MARS & RC6 require specific support for variable rotations & mod 2^32 multiply and therefore performance is severely impeded on platforms not providing these instructions (not only smartcards but also current platforms such as Sun UltraSPARC [7] and forthcoming platforms such as Intel's IA64 [8]). 3) Does the speed of any of the 5 candidate ciphers prevent it from reasonably being used across platforms? A Pentium Pro 200Mhz "reference platform" can run the slowest candidate at 34Mbits/s (approximately the same as DES [1]), whilst a Pentium II running at 200Mhz obtains 45Mbits/s. 4) Arguably, hardware throughput is most important (for highspeed systems such as IPSEC and ATM for example). Smartcard operations will usually be low bandwidth (e.g. challenge response / passphrase encryption and so on) and will therefore not be unduly affected by a slow cipher. 5) Scope for speed optimisation. Most of the ciphers submitted appear to be near optimal on the NIST test platform, but one cipher Serpent has shown significant and continuing improvement due to S-Box optimisation [1], [9]. It is likely that Serpents' performance could be similarly improved by: a) Producing more S-Box representations with fewer terms. This would probably improve the performance across most if not all platforms. b) Rearranging S-Box terms to better exploit both processor level parallelism and "streaming" parallelism (e.g. MMX, SSE, 3Dnow, Altivec and other SIMD units) - see [1] for example. 6) We can't predict how CPU architectures will look in the future, but the current trend is the support for multiple pipelines and streaming (e.g. SIMD) instruction sets (see for example, Pentium III, AMD Athlon and PowerPC Altivec). These types of architectures would appear to benefit Twofish, Rijndael & Serpent more than RC6 and MARS [8]. 7) The MARS and Twofish designers have implemented cipher components that are available at little or no cost on the specified test platform but may be expensive on other platforms. 8) Algorithms won't always be implemented in hand optimised assembly code - high- level language speed is also very important. I note [10] that Serpent has the best high- level language to assembly ratio. AES was always going to be a trade-off between security and speed. I believe NIST correctly laid down the criteria in [11]: "...with a strength equal to or better than that of Triple DES and significantly improved efficiency". The Twofish teams' comments also seemed prudent [12]: "While it is impossible to optimize a cipher design for resisting attacks that are unknown, conservative design and over-engineering can instil some confidence". We need to recall that even the slowest performing R2 AES candidate, Serpent, is approximately three times faster than Triple-DES and (is widely believed to be...) significantly stronger than Triple-DES and the other AES candidate ciphers. The 5 remaining teams whom submitted AES candidates (predictably...) continue to assert their own algorithms' security benefits and, whilst they are unable to arrive at a modus vivendi, they do all appear to agree that Serpent is the most secure candidate, but then move on to knock it for speed. I suggest, therefore that if NIST is now tied to picking one of the unamended algorithms then Serpent *has* to be the algorithm of choice. If NIST is allowing cipher modifications at this point then Rijndael + 3r is also a strong consideration. Finally, I must applaud NIST for their openness in selecting AES - this will no doubt ensure that the successful algorithm will not be subjected to the same mistrust as DES. Regards, Sam Simpson B.Sc. (Hons.) IT Operations Manager MIA Ltd (UK) Phone : +44 (0)1438 735478 Fax : +44 (0)1438 726069 e-mail : s.simpson@mia.co.uk References: [1] B.Gladman, "Serpent", available at http://www.btinternet.com/~brian.gladman/cryptography_technology/serpent/ind ex.html [2] M.E.Smid, "AES - A Crypto Algorithm for the Twentyfirst century", FSE Workshop, 1998. [3] M.J.B.Robshaw, Y.L.Yin, "Potential Flaws in the Conjectured Resistance of MARS to Linear Cryptanalysis", 2000. [4] E.Biham, "A Note on Comparing the AES Candidates", 1999. [5] B.Schneier, D.Whiting, "A Performance Comparison of the Five AES Finalists", 2000. [6] J.Dray, "NIST performance Analysis of the final round JAVA AES candidates", 2000. [7] L.E.Bassham, "Efficiency Testing of ANSI C Implementations of Round 2 Candidate Algorithms for the Advanced Encryption Standard", 2000. [8] J.Worley, B.Worley, T.Christian, C.Worley, "AES Finalists on PA-RISC and IA-64: Implementations & Performance". [9] D.A.Osvik, "Speeding up Serpent", 2000. [10] B.Gladman, Personal communication, 2000. [11] "ANNOUNCING REQUEST FOR CANDIDATE ALGORITHM NOMINATIONS FOR THE ADVANCED ENCRYPTION STANDARD (AES)", Federal Register, Friday, September 12, 1997. [12] B.Schneier, J.Kelsey, D.Whiting, D.Wagner, C.Hall, N.Ferguson, "Twofish: A 128-Bit Block Cipher", 1998. Date: Fri, 12 May 2000 15:46:33 +0530 (IST) From: "R.Venkatesh" To: AESround2@nist.gov Subject: AES Comment. Hello: I am R.Venkatesh and I research on cryptographic techniques with Tata Infotech Ltd, India. I attended the AES Round 3 Conference held in New York City. In my position as Senior Research Associate with the said Company, I enclose herewith my comments on the Advanced Encryption Standard. Thank you. With warm regards, for Tata Infotech Ltd., (R.VENKATESH) Script follows ==>> =================================================================== Comments on the Advanced Encryption Standard Author : R.Venkatesh Date : May 09,2000 Standardization of the cipherstream To obtain a cipherstream from a given plaintext stream, the following steps are carried out. - Divide the plaintext stream into a number of fixed-size blocks. Each block forms the basic unit of encryption. In case the last block is not filled completely, perform appropriate padding at the end of the plaintext stream to ensure that. - Encrypt each fixed-size block using the encryption core. - Concatenate the encrypted block to the previously encrypted block to form the cipherstream. Suppose the cipherstream alone is received by a decryptor. Then the decryptor will not be in a position to determine the parameters necessary for successful decryption. Specifically, some of the additional information needed by the decryptor may be: - The algorithm identifier that specifies which algorithm was used in encryption - The block length used in encryption (this could be fixed in certain ciphers such as RC-6 or user-defined in others such as Rijndael). - The number of rounds (this could be fixed in certain ciphers such as Serpent or user- defined in others such as RC-6). - The size of the underlying plaintext. This is necessary to find out the amount of padding done at the end of the plaintext before encryption; this padded string can be discarded accordingly after decryption. - The initialization vector, incase other modes of encryption are used (such as Cipher Block Chain, Cipher Feedback, Output Feedback). This information is therefore common to the encryption and decryption processes and could be typically be stored by an encryption process in a descriptor. This descriptor will be made available to the decryptor in addition to the cipherstream. It is suggested that a standard be evolved in storing and possibly encoding such descriptor content. As a consequence, interoperability of different implementations of the same cipher is ensured. RSA Laboratories has already taken a step in ensuring this at the level of the cipherblock and the public and private keys by enforcing the Public Key Cryptography Standard (PKCS). RSA has also specified encodings by relating the ASN.1 object members for the cipherblock and the keys against their corresponding PKCS formats. Even in public key cryptography, no such standard has been enforced on the ElGamal public-key cryptosystem. And the standardization of the Elliptic Curve Cryptosystem is under way via the PKCS #13. This standard should be as universal as possible. Then users/developers need not have to write specific interface functions to fill data members in the objects of other application standards such as S/MIME, etc. This evolution need not be done during the decision-making process of the AES algorithm(s); that process only deals with the encryption core and the basic unit of information to be encrypted. However as mention was made during the introductory session, additional modes of encryption would be taken up for the AES algorithm(s). This could mean one or both of the following: - New modes similar to the chaining and feedback modes. - The new standardization scheme suggested above. (This last suggestion has evolved due to the advice of Dr.Brian Gladman who specifically mentioned that taking up standardization issues during decision-making of the AES core(s) could result in a lot of confusion. Instead this should be put forward as another mode while deciding the AES encryption modes later. Moreover although the encryption core may be very strong, more often it is an implementation of it that could pose security loopholes. Consequently the standard has to be designed and security- audited very carefully before it is put forward). (Dr.Bruce Schneier has mentioned the suggestion on standardization as an excellent one when put forward during the concluding stages of the AES Round 3 Conference). Date: Fri, 12 May 2000 13:33:51 +0100 (WEST) From: Hĺvard Raddum Reply-To: Hĺvard Raddum Subject: Something to keep in mind when selecting the AES algorithm To: AESRound2@nist.gov X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4_32 SunOS 5.8 sun4u sparc X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by email.nist.gov id HAA02846 In NIST's call for candidates it is pointed out that security will be more important than performance when judging the candidates. I would like to stress the point that once the AES algorithm is selected, its security will start getting weaker, and its performance will start getting better. We already saw several examples of this at AES3, with new and improved attacks on some candidates and how to speed up the slower candidates. In other words, the AES standard should be the one with the largest safety margin as long as it's useable in practice. In my opinion Serpent is the safest AES candidate. Serpent is also faster than 3DES (NIST's benchmark), and should therefore be selected as the AES standard. Hĺvard Raddum To: AESRound2@nist.gov Subject: Why we chose Rijndael Date: Fri, 12 May 2000 14:00:05 +0200 From: Simon Wigzell Reply-To: simon@orcsoftware.com X-Mailer: by Apple MailViewer (2.106) A short note from one developer concerning why our company chose Rijndael when we needed encryption Our program suite, a rather complex one with a server/client environment, uses encryption for all communication. What we needed was something which was as speedy as possible for encrypting small chunks of data (typically a couple of hundred bytes), with no state whatsoever. There is a lot of connections going on; a typical server recieves maybe a thousand of these packages every minute. This implied that the encryption had to be really fast to initialize (setting up keys, since we don't have a state leading to every package having it's own key as far as the server is concerned) and also being more secure than DES since the financial institutes using our product are very concerned about security. As the situation is right now the only candidate that is good enough for us is Rijndael. It is just fast enough and using little enough memory to be possible for our use (though we don't have much margin). Some of the speakers at the AES conference said we should disregard the speed issue (or at the least not concern ourselves too much with it) since in a few years all computers will be that much speedier, but the problem is that we need something that is good today, not tomorrow. For our purposes Rijndael was a given, but that might not be true for others. Irregardless of whether NIST chooses Rijndael for AES we will continue using it since it is, without doubt, our best option. Yours Sincerely, Simon Wigzell ________________________________ Simon Wigzell Cryptologist Orc Software http://www.orcsoftware.com Delivered-To: fixup-AESround2@nist.gov@fixme User-Agent: Microsoft Outlook Express Macintosh Edition - 5.01 (1630) Date: Fri, 12 May 2000 16:41:20 -0500 Subject: Re: Comments on Rijndael, Serpent, Twofish software implementation From: "David C. Oshel" To: This is a followup on my earlier comment. What I perceived as a problem with Twofish appears to be a mere documentation issue. Twofish does not like frequent key changes (in common with Blowfish), at least in my naďve implementation. When I revised my code following hints from D. Whiting, the performance discrepancies vis-a-vis Rijndael and Serpent essentially disappeared. Thanks for your patience, Dave Oshel ---------- From: David C. Oshel Date: Tue, 09 May 2000 21:50:17 -0500 To: Subject: Comments on Rijndael, Serpent, Twofish software implementation I have incorporated Rijndael, Serpent and Twofish in a small file encryption grinder for Macintosh. This little utility includes a Test routine designed to exhibit simple characteristics of the program's keystream – produced using the algorithms in question. While not especially interesting as analysis, the routine does give the algorithms a workout. The default, "Lite," routine -- basically a species of PrngXor -- completes the Test routine in about 15 seconds on a Macintosh Powerbook G3 (Bronze). Rijndael typically concludes the task in 21 seconds, compared to 23 seconds for Serpent, and 1 minute 19 seconds for Twofish. IMHO, this clearly argues against Twofish in purely software implementations. The code I used was Brian Gladman's as he had it posted near the end of Round 1, in other words, the source which #includes "../std_defs.h", pretty nearly straight "out of the box" and compiled with Metrowerks' C++ compiler. I did not bother testing RC6 or Mars because there seemed little practical point in using candidates with reservations about their intellectual property status. -- David C. Oshel mailto:obsidian@kagi.com Cedar Rapids, IA http://homepage.mac.com/dcoshel/Obsidian.html ``Tension, apprehension and dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_ From: "Paulo S. L. M. Barreto" To: Subject: Are the existing AES comparisons fair? Date: Sun, 14 May 2000 10:01:44 -0300 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2615.200 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2615.200 Are the existing AES comparisons fair? We argue on the contrary. 1. Some criteria presented by the finalist submitters are obviously subjective, and hence hardly relevant. For instance, comparing the relative cipher complexities on basis of lines of code, as the MARS submitters propose, is subjected to the characteristics of the notation or programming language in use. Indeed, a simple-looking line containing a 32-bit integer multiplication easily becomes a bunch of hacking on platforms that lack multiplication instructions. Another example of subjective criterion is the "difficulty to analyze the cipher". The MARS team states, for instance, that the round function of Rijndael is difficult to analyze. This assertion is totally irrelevant, as it only reveals that some cryptanalysts could not find any way to attack the cipher (while others were able to find new results, as is the case for the Twofish team). In fact, should any of the AES finalists be considered "easy" to analyze, it would probably be broken by now. 2. Benchmarks were abused in cipher comparisons. It's surprising to find that some submitters still claim that their proposal is the fastest on this or that platform, even though the evidence in contrary from all benchmarks available. Most times, such claims do only hold on a very specific platform and for a very specific implementation. This is the case, for instance, for the MARS team claim that MARS is the fastest cipher when implemented in Java. However, the source of this information is not mentioned. Which implementation was used for the other ciphers? On which underlying hardware were the measurements performed for each cipher? (the bytecode may be portable, but it will certainly execute differently on a Java ring and on a Pentium III). A curious example is the comparison presented by the Twofish team. Not surprisingly, Twofish is argued to be faster than the other finalists; however, an implementation tailored for a particular key (hardwired into the self-modifying code) is quite unusual to say the least, certainly impractical, and absolutely insecure, as now the security resides in the code itself. Perhaps this should be considered a variant of Twofish over a keyspace of cardinality one, not Twofish itself. 3. Some arguments put forward against candidate ciphers lack any reasonable foundation. This is the case of the MARS team statement that Rijndael's has "a key schedule that makes it easier to mount power attacks", while no such attack is presented. On the other hand, this very issue is analyzed in detail elsewhere, and no such weakness is reported. Also, the same team makes assertions on security margins without clearly defining the criteria they used to assess these margins. This contrasts, for instance, with the procedure adopted by the Twofish team, whose criteria are not only precisely stated, but also quite reasonable. 4. Sometimes, truncated or out of context statements are advanced. This is quite misleading. For instace, the RC6 team agrees that analyses on reduced- round variants are flawed - after quoting a related key attack on reduced-round Rijndael, and omitting the very fact that this weakness is absent from the full cipher. 5. Other issues. An argument advanced by the RC6 team as a response to the criticism that RC6 is not suitable for implementation on cheap smart cards is that such processors will be obsolete on the long term, so that only more powerful processors should be considered when comparing the AES candidates. Hopely this would put RC6 on an advantageous position. However, existing evidence suggests the contrary: RC6 has the worst performance on the IA64 platform, and is equally bad on the PA-RISC. The strategy adopted by NIST -- namely, taking *all* existing analyses into account -- is likely to be the only viable way of correcting these problems, and compare the finalists with regard to their intrinsic (as opposed to their advertised) merits. Best regards, Paulo S. L. M. Barreto. From: "Paulo S. L. M. Barreto" To: Subject: On the multiplicity of AES algorithms Date: Sun, 14 May 2000 10:23:25 -0300 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2615.200 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2615.200 On the multiplicity of AES algorithms. It hardly makes any sense to speak of a "standard" if several highly dissimilar algorithms are chosen. It's mere illusion to expect that industry might afford the costly effort of implementing a second algorithm just in case something happens to the primary cipher. If the primary cipher is considered effectively strong by all accumulated evidence, there's no need for a backup cipher. If it's *not* considered strong enough, the psychological effect is devastating (who can expect any level of confidence in such an algorithm?). Furthermore, should the primary algorithm be broken there would again be just one AES cipher, unless three or more algorithm are chosen, making full AES compliance even more expensive (if viable at all). In practice, industrial applications are most likely to implement only one of the AES ciphers (interoperability issues dictate that this be the primary one), making the existence of alternative ciphers a theoretical fact irrelevant to ensure protection in the realm of those applications. The suggestion to define the backup as the *same* algorithm with a larger number of rounds is a far superior idea. It's quickly, easily and cheaply achievable; in fact, it closely relates to the present industrial solution to the obsolescence of DES, namely, using 3- DES instead (with the advantage of doubling rather than tripling the processing time). As a side note, it's interesting that many people recommended using Serpent as secondary cipher because of its allegedly higher security level compared to the other AES finalists. However, this level derives precisely from its large number of rounds: 16- round Serpent is as secure as any other finalist. This provides clear evidence that a backup cipher consisting of the *same* algorithm with *twice* as many rounds would be felt as a good choice. For the sake of comparison, the recent DSS revision is based on a totally different situation. First, RSA is too widely spread to be ignored; it's a de facto worldwide standard; including it in the revised document is mere acceptance of this. Second, ECDSA has clear advantages over conventional DSA; ideally, it should be a full replacement. But (this is the third point) this is obviously impossible to be achieved except in the very long term, so DSA should be preserved in the standard. Finally, there are not many choices for public key algorithms (as opposed to the proliferation of symmetrical ones), which makes the two standardization processes entirely different. In conclusion, NIST should select a *single* AES algorithm. If a "backup" cipher is needed, just double the default number of rounds. On this light, I would like to manifest my opinion that Rijndael seems to be the only cipher that performs consistently well on all platforms for which implementations exist (hardware, smart cards, 32- and 64-bit processors, JVM). Needless to say, its estimated security seems to at least match that of any other finalist, and it's completely in the public domain. Best regards, Paulo S. L. M. Barreto. Posted-Date: Sun, 14 May 2000 10:34:56 -0500 (CDT) X-Sender: schneier@mail.visi.,com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.2.0.58 Date: Sun, 14 May 2000 10:33:32 -0500 To: AESround2@nist.gov From: Bruce Schneier Subject: AES Comment: The Hitachi patent Hitachi has two U.S. patents, numbers 4,982,429 and 5,103,479, each of which is purported to cover "any" encryption system using rotations. These patents were filed in 1988. All of the five AES candidates use some kind of rotation, including Rijndael's ShiftRow operation. However, for what it's worth, it should be noted that Twofish can be implemented as a "straight Feistel cipher plus a final permutation, with rotations applied only within the round function, not in the Feistel XOR path. The authors of Twofish were unaware of these patents until recently, but the notion that such a broad claim could be valid seems quite ludicrous. he following well-known pieces of prior art would seem to at least dramatically limit the scope (if not completely invalidate) any such claims. 1) FEAL (1987) uses a rotation in its round function. 2) Madryga (1984) uses a variable rotation in its round function. 3) DES (1977) uses a rotation in each round of its key schedule. 4) DES (1977) uses a bit permutation (of which rotations are a special case) in every round. 5) GOST (1989) applies a bit permutation (that is a rotation) in each round after performing its S-box lookup 6) The very words "rotor" and encryption have been linked for a long time (e.g., the Caesar cipher, and Enigma) The concept of rotation in encryption was clearly neither novel nor unobvious at time these patents were filed. The fact is that EVERY microprocessor opcode has been considered for use in encryption, with rotation being just one example. This particular example is a counter to the "IP attack" argument espoused by some as a reason to select multiple AES algorithms instead of a single one. It is most likely that IP attacks, if any, will be based on very broad and ambiguous claims (like those of Hitachi) that the patent holder attempts to apply to all encryption systems. Niels Ferguson Bruce Schneier David Wagner Doug Whiting ************************************************************************** Bruce Schneier, CTO, Counterpane Internet Security, Inc. Ph: 408-556-2401 3031 Tisch Way, 100 Plaza East, San Jose, CA 95128 Fax: 408-556-0889 Free Internet security newsletter. See: http://www.counterpane.com From: "Brian Wong" To: Subject: NIST AES Round 2 Comment Date: Sun, 14 May 2000 16:31:10 -0400 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 Comment on NIST AES Process: While I agree almost entirely with Bruce Schneier's comment regarding Hitachi's asserted patent coverage of the AES candidates, I would like to comment on one specific statment made in that document, that being: >All of the five AES candidates use some kind of >rotation, including Rijndael's ShiftRow operation. Rijndael's ShiftRow operation is more accurately described as a byte-wise permutation on the internal state of the algorithm rather than a rotation or "barrel shift." In most computer architecture contexts, the term rotation is usually used to denote an operation working on the individual bits of a machine word or smaller component thereof. No such operation appears in the specification of the Rijndael algorithm. Brian Wong _____________________________________________ NetZero - Defenders of the Free World Click here for FREE Internet Access and Email http://www.netzero.net/download/index.html From: "Tom Phinney" To: Subject: Use of AES in Industrial Field Communications Date: Sun, 14 May 2000 13:45:46 -0700 Organization: X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2314.1300 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 Background ========== I am the current U.S. Technical Advisor for IEC/SC 65C, whose scope is Industrial Communications. I have been involved in the standardization of industrial communications since 1980, in IEEE 802 and in IEC/SC 65C, both as an editor and as a significant contributor. I am a mathematician by training, have considerable experience in design of software, hardware and low-power digital ICs, and have been peripherally involved in the cypherpunk community. My comments are with respect to AES use in the context of industrial automation and process control. Industrial networking in the discrete manufacturing, batch and continuous process industries is characterized by large numbers of sensors and actuators (know as "field devices") connected through a hierarchy of concentrators (bridges, switches and intermediary controllers) to centralized control systems supervised by human operators. The number of sensors and actuators in a large system frequently exceeds 10^4, and sometimes 10^5 devices. Many of these devices are conceptually very simple, such as limit switches, relays and temperature transmitters. Networking considerations include multi-device failure modes and cost of connection; in many cases this is complicated by a potentially hazardous (i.e., explosive) environment which imposes absolute limits on available power and stored charge. In the most hazardous environment, which is the market-required design-point for most process control equipment, the available device power is on the order of 200 - 300 mW during periods of network transmission, and 30 - 100 mW during the majority of the time when a networked device is not transmitting. This power budget includes that required for the sensor or, less frequently, the actuator as well as any connected microcomputer, memory, communications circuitry, etc. Typical microcomputers in today's devices are 8-bit and 16-bit CPUs with some EEPROM, such as various models of the 6805 and 8051 and related and derivative 16-bit families. Before the advent of digital networking in this environment, most field devices used pneumatic or near-DC analog point-to-point communications, with the device interconnections on physically-secured premises (e.g. a fenced access-controlled oil refinery). The advent of networked digital communications has led to higher bit-rate transmissions, either wired or now wireless, where eavesdropping from "outside the fence" is feasible. Indeed, one European refiner has reported discovering that arbitrageurs were eavesdropping on the signaled levels of its petroleum storage tanks and were playing the local spot market against the company. Implications for AES ================ The following comments are relative to current wired industrial field device networks and their likely extension to wireless regimes. Industrial field devices use combinations of point-to-point client-server and point-to- multipoint publisher-subscriber connections, as well as point-to-point (unicast) and point- to-multipoint (multicast) multi-source to multi-sink connectionless communications. Most such messages are relatively short, consisting of approximately 10 – 40 bytes. In a wired environment, critical messaging should use source authentication and message integrity checking; in a wireless environment both authentication and MACs are a requirement. Whether wired or wireless, business-critical information such as inventory levels and critical process measurements requires confidentiality. This is best applied on a presentation layer (field content) basis, with the data values encrypted and the remainder (communications protocol portion) of the message in the clear. Different connections may require different session confidentiality keys, so a single device may be encrypting and decrypting concurrently under many keys. However, the existence of long-lived connections and associations makes precomputation of round- keys feasible, up to the amount of available RAM in the field device. Most such field devices can be expected to have at least a few kB of unused RAM (today, typically in a separate RAM chip), so this need not be a severe constraint on key setup. Thus key agility has some value in this environment, but less than it would have in a transactional environment where long-term relationships among communicating nodes is not the norm. Field devices are both clients and servers. Thus assumptions that simple devices are not servers are incorrect . (Cf. letter to NIST on AES by Jeffrey Streifling, "Consideration of RC6", 1999.12.05) Unlike most commercial battery-operated devices, which have limited energy storage but few restrictions on instantaneous power use, field devices designed for hazardous-area use have a strictly limited power supply. Software design strategies try to average power consumption and minimize peak usage. Encryption modes where the keystream material can be precomputed are a good fit for this power regime. The AES security timeframe of 20 years would be considered short in the industrial environment. Many industrial systems operating today are well over 20 years old; some are in their 30s. For example, a large percentage of the electric power generation in the U.S. falls into this aged category. Typically, these systems undergo a substantial upgrade every few years, but wholesale replacement or discard of working devices is a seldom occurrence. The multiple key lengths currently specified for AES are a reasonable fit to the spectrum of threats envisaged for such long-lived systems. Increasingly, field devices have a downloadable code store (e.g., flash PEROM) to handle issues of software protocol upgrade. This was not possible in the days of 12 - 18 V flash programming voltages, but new devices use such low voltages and energies that they can meet design requirements for hazardous areas (a field known as intrinsic safety). Therefore, if a usable attack on the chosen AES algorithm were to be discovered, such devices could be upgraded with a replacement algorithm. Other comments ============= I recommend that NIST use a self-administering FSF-like CopyLeft licensing procedure for the AES to preclude restrictive derivative-use patents. I see this as partly an issue of "internet years" versus human years. We as humans cannot predict the specifics of the hot encryption uses over the next few decades, but the "wired economy" will suffer substantial harm if this public process is coopted for private gain, e.g., by the first person to claim the use of AES for digital cash or micro-payments or E-mail or something else which the patent examiners consider "non-obvious to one skilled in the art." Some of the letters to NIST indicate concern about implementation errors. This seems unlikely to be a problem for the AES core algorithm, assuming that multiple reference implementations and an adequate set of test vectors both exist (as they do or will). Of much greater concern is the implementation of key management, which is outside the scope of the AES effort. In this latter area all five candidates are equal. I believe that NIST should choose only one AES algorithm. A backup algorithm should not be specified now. Rather, defer such selection from the other four current candidates, or more likely run a new selection process, only if and when cracks (pun intended) start to appear in the strength of the selected algorithm. This deferral permits the selection of the backup to be informed by continuing research, and motivates that research, without imposing the inevitable "consider implementing the backup algorithm now" debates and security risks which an actual choice would engender. Specifying a backup candidate now may actually increase the security risks if it is ever employed, because in many cases the implementation will already be in place if it becomes required, but will not have been tested adequately because of the backup algorithm's irrelevance at the time the code or hardware was developed. My own preferences for the AES selection are TwoFish or Rijndael. The per-byte power requirements for multi-precision software multiplication and shifting of MARS and RC6 seem excessive for the above-described field device environment. Serpent seems excessively cautious. In closing I would like to applaud the submitters of the 15 initial AES candidates, and the tremendous investment of the participating crypto community in their analysis and in continuing analysis of the five semifinalists. For this we should all be grateful. The above comments are my own, and do not represent an opinion of my employer or of the U.S. industrial networking standards community. Tom Phinney Principal Engineering Fellow Honeywell Industrial Automation and Control Phoenix, AZ USA Date: Sun, 14 May 2000 23:47:27 +0100 From: David Crick X-Mailer: Mozilla 4.61 [en] (Win95; U) X-Accept-Language: en To: AESround2@nist.gov Subject: AES Round 2 Comments -----BEGIN PGP SIGNED MESSAGE----- My views are: * Rijndael should be selected as the one and only AES algorithm. - it is the only finalist that performs exceptionally well in all environments. Fast key setup, support for larger block sizes (essential for hashing), and an inherently parallel nature further mark it out as an exemplary modern block cipher. - safety margin aside (the authors still feel it is adequate), the cipher has remained secure throughout the evaluation period. Many people have expressed the view that the simple, "clean" and indeed elegant structure of Rijndael has proven advantageous in analysis and understanding. - multiple algorithms introduce complications. Ian Harvey's paper concludes that a primary algorithm with optional secondaries is the most acceptable of the multiple scenarios. Yet there is little difference between this and a single cipher when resources only permit one to be implemented, and multiple ciphers (to choose from) would in any case be likely in suitable environments. (If Rijndael does win, I expect to see Serpent and Twofish used in such circumstances.) If NIST and the community (who in the AES2 questionnaire were in favour of a single winner, with Rijndael and Serpent rating highly) cannot decide on a single algorithm, then how are the public supposed to? Not to mention all the implementation uncertainties that would arise in such a scenario. * Addressing Rijndael's safety margin, if NIST feels that there is enough call to increase it, then they should do so now. I feel that an increase to 16/18/20 rounds for 128/192/256-bit key and block lengths respectively should satisfy such concerns, while still retaining adequate performance. For those still not satisfied (and also to counter breaks if they occur), perhaps the best situation is to have the number of rounds as a parameter, so that higher figures still could be used which could nevertheless be decoded by all implementations. (A hard- coded lower limit is crucial here, to stop someone [maliciously] requesting lower than 10 rounds - or even zero!) * Implementations should use 256-bit keys unless there are serious reasons why this is not possible. Conceivably, technology such as quantum brute-force key searches could come into play during the lifetime of AES. * Triple-DES should be promoted and run concurrently with AES as a FIPS, so that organisations and individuals who do not feel confident with a relatively new algorithm can go for a more established and trusted one. * Similarly, 3DES could be used as an emergency replacement should AES be totally broken. This makes most sense as 3DES is already fielded, and implementation expertise, etc. already exists. * NIST should use the (estimated) one year period between the selection of the AES winner and the FIPS certification to encourage further analysis. The reduction of the fifteen Round 1 candidates to the five for Round 2 facilitated much more detailed analysis on those that were left. Some people have commented that another year's study is needed for the finalists. This year of "dead" time could therefore be used highly profitably in a concentrated effort on a single algorithm, further boosting confidence. * If AES suffers a critical break (one where data is actually at risk, or if a valid "academic" attack seems like it may become practical in the future lifetime of AES), then NIST obviously needs to take action. Some options I suggest are: - increasing the number of rounds if this will stop the break (with Rijndael this is easy to do). - patching the cipher if possible, although this will need to be done with care and with further analysis (the move from SHA to SHA-1 is an example of this). - replacing the algorithm with one of the other finalists if they are immune (intellectual property is crucial here). - replace with a more up-to-date cipher (ideally one that has already been analysed for some time). - initiate another call for candidates for a new standard (the AES process was initiated when DES was recognised as being inadequate/vulnerable). * For NIST's Round 2 Status Report, a summary table of attacks for each finalist should be given. This would detail for every attack currently known: - the number of rounds broken - the key size it relates to - the complexity of the attack (in terms of time, data, etc.) - the type of attack (e.g. Square, partial sums, related key) Such information would need to be compiled from the original candidate submission documents, Round 1 / Round 2 papers and comments, plus other "outside" sources (eg FSE, SCIS2000). An example of the type of table I am referring to can be seen in Table 1 of "Improved Cryptanalysis of Rijndael" by the Counterpane team. * NIST should adopt the GNU copyleft licensing for AES. This would ensure that all implementations, optimisations, etc. are free for anybody and everybody to use, which I believe is the true spirit of AES. * For the record, my ranking of the finalists, best to worst, is: Rijndael (outstanding); Serpent, Twofish (both very good); RC6, MARS (both have poor performance off the reference platform, and also design concerns). -----BEGIN PGP SIGNATURE----- Version: 2.6.3ia Charset: cp850 iQEVAwUBOR8q+4VnnSUi1cepAQFmVwf5Aa9bRQpkr9tlhDuIH6eOp4HlaoB6MUll DoJtozW6u2MvkijZF1gQCUpkIGt5ia+cvWoCTIAhMAS3pTyhKBPzCvzrC+ajjEQk /FlYkcWr53wxNCyTk6zL1fPabSh4KrPVnheYOckVxQWWsMR/glNZ7R4zVmbIy4i4 FliMaaj1Zp+8dzimICSPOYySCYK19hZDe2hSh0h9h0RIBzdtPBEmVdTSDmCd+81Y eoqgUTqUcQgyx0rYqThwVethktBscvu1wtZaOlkd+usrw2IdETkr0zKNVzZ0zG/u prqgw3jG1QJBH/eeWJ863H0FynGopitjwrY50ZxGl9Skg0H6T/JbhA== =wFcs -----END PGP SIGNATURE----- From: "Yaro Charnot" To: Subject: AES Round 2 Finalists Date: Mon, 15 May 2000 01:08:53 +0100 X-MSMail-Priority: High X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: High Sensitivity: Company-Confidential X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 As a computer security expert, software engineer, software reverse engineer, Master of Cryptology, former computer cracker and hacker with many years of experience, I want to use my opportunity to influence your decision on the next Advanced Encryption Standard. My points are: 1. The security of the products I have been cracking for years lied mainly on the implementation, not on the number of rounds or possible theoretical attacks on the cipher. After personally evaluating all AES candidates, I can report that only two ciphers qualify as simplest to implement not leaving much room for mistakes: Twofish and RC6, with RC6 being amazingly simple and requiring the least IQ of the programmer to implement it, debug it and deal with it. 2. My personal never published (company's internal) analysis of R1 AES candidates in June 99 using personally designed and publicly available randomness testing tools (like DIEHARD tests) showed that two algorithms stand off the rest. Those are again Twofish and RC6, with Twofish leading in speed on most of the processors. They offer the lowest price (speed and memory requirements) for the same level of security. 3. All AES candidates have different properties, but in software implementation (in 95% of the cases performed by programmers with very little understanding of cryptography) one characteristic plays the second most important role: flexibility of the key size. RC6- like algorithms offer it allowing the entire large output of public key algorithms like 4096- bit Diffie-Hellman to be used as a key without a need to design an extra special "compression" function for this purpose leaving poor software developers on their own in that design. They will most probably use the lower 128 or 256 bit of the common key, which are the least secure as PK cryptographers know. But in some cases this flexibility is irrelevant and other characteristics play more important role: 4. Hardware implementations? Again, Twofish wins, RC6 follows, the rest of the algorithms is behind only confusing developers with their complexity. 5. Pick a 15 y.o. student, show him all the algorithms and ask him which ones he likes the best and would use? He'll point at RC6. Why? It's naturally and geniusly simple and easy to understand, one can hardly make a mistake implementing it. 6. Pick an experienced Unix software developer, show him all the algorithms and ask him which one he likes the best? He'll point at Twofish. He trusts its predecessor Blowfish and his main concern is inter-platform effectiveness and compatibility. Problems like byte order, absence of rotation functions on different processors, differences in register size, memory alignment requirements, etc. Twofish is fastest on 8- bit processors as it is on 32-bit or 64-bit processors regardless of byte ordering or instruction set. 7. Even if you pick only one algorithm as AES, all the software developers will still want to support both RC6 and Twofish because they are already doing it. Why are they doing it? Because they had a choice and they choose the algorithms easiest to implement, the algorithms most effective, the algorithms most flexible, the algorithms most trusted. Trust is the key to the success of their software. They trust RC5 and they trust Blowfish, so they all trust RC6 and Twofish more than all the other algorithms combined together. I do too. 8. In some countries in the world people will not trust Twofish or RC6 because they are a US product. An encryption algorithm from a country that has been imposing bans on strong encryption for years. On contrary in the US people will most likely favour a US product not trusting much a foreign algorithm to protect their most valuable assets. The USA is the world's leader no matter how good or bad it is or its products are. It's rich and strong. The whole world is watching and is trying to follow. Give the world a choice and they will love you for that. Serpent suits well for it although it lacks the flexibility and simplicity RC6 and Twofish offer. 9. I myself don't have a preference in any of the algorithms. They are all secure enough to protect from a street hacker or even a small or large business trying to hack a network or a financial software. I can implement even DES in such a way that it will be uncrackable for NSA. The security of the algorithms is my least concern. The beauty and ease of implementation and flexibility of the algorithm is. Only two algorithms qualify: RC6 and Twofish. Although if I was to choose a HASH function, I'd stick to Tiger due to its natural simplicity and my trust to Eli Biham's and his colleagues with Russian names cryptanalytic skills. So Serpent would be my next trusted choice. 10. There are other less significant points like one round of RC6 can be and will be used as a beautiful non-linear chaining function replacing simple easy-to-attack XOR, like both algorithms can be and will be combined together. Paranoid programmers will want to encrypt their data first with Twofish and then with RC6 or something else on top just in case one of the algorithms is broken. And they will be right. The skills of the majority of them are very low. Unfortunately cryptographers and cryptanalysts do not develop security software. I represent the rare 0.001% of those developers and while I personally don't care what the next AES will be (my products will still be more secure than everything else around), the rest 99.999% might get stuck with a big pain for years. Please be careful. The conclusion is I ask, demand and beg to include both Twofish and RC6 (maybe Serpent as well) in AES for all the software and hardware developers, copy- protectionists, information security advisors, software reverse engineers, white hat hackers and beginners, as someone who is qualified enough to see and exploit the real insecurity of all so-called security software every day of his life, someone from the battlefield. - Yaro Charnot --------------------------------------------------------- Identikey - The Key To Internet Security --------------------------------------------------------- Yaro Charnot Chief Security Advisor Identikey (Australia) Pty Ltd 143 Coronation Drive Milton QLD 4064 Phone: +61 7 3236 5050 Fax: +61 7 3236 5850 E-mail: ycharnot@identikey.com https://www.identikey.com --------------------------------------------------------- The views expressed in this message are those of the individual sender, except where the sender specifically states them to be the views of Identikey (Australia) Pty Ltd. --------------------------------------------------------- X-Authentication-Warning: everest.cs.umbc.edu: aselcu1 owned process doing -bs Date: Sun, 14 May 2000 22:58:35 -0400 (EDT) From: Ali Aydin Selcuk Reply-To: Ali Aydin Selcuk To: AESround2@nist.gov Subject: comment on RC6 A general comment on RC6: I think RC6 is the best publicly analyzed algorithm after DES, considering the amount of public analysis received by RC6 and RC5. Having so much analysis done on such a small piece of code, and still having no significant weakness found, I think, is an important plus for RC6. Regards, Ali X-Lotus-FromDomain: NRTA From: "Ken Tindell" To: AESround2@nist.gov Date: Mon, 15 May 2000 09:41:42 +0100 Subject: Comment on round 2 AES algorithm selection I wish to comment on the criteria for selecting the AES algorithm. Aside from the issues already well covered and understood, I would like to emphasize a key area: The efficiency in terms of code space and working RAM must be very high. The smartcard market has been discussed already, but there are other domains that require high memory efficiency: mass-produced embedded devices. It is quite common now for embedded computing in mass-produced devices to be sophisticated, and yet to be implemented in small, low-cost microcontrollers. I give the example of automobiles: there are several new automobiles with more than 20 microcontrollers on-board, each with Flash memory and hence able to be re-programmed. Several manufacturers of components (e.g. engine management systems) wish to keep their software secret when downloading and programming devices, and to ensure that certain data is protected against tampering (e.g. engine calibration tables). This has led to the use of customized low-resource encryption. However, there are considerable risks in adopting proprietary encryption algorithms, which would be avoided by adopting a memory-efficient AES algorithm. >From an examination of the candidate algorithms it would seem that Twofish is best placed to be implemented in low-resource micros. Best regards, Ken Tindell Sender: contini@maths.usyd.edu.au Date: Tue, 16 May 2000 01:01:11 +1000 From: Scott Contini X-Mailer: Mozilla 4.7 [en] (X11; I; SunOS 5.5.1 sun4u) X-Accept-Language: en To: AESround2@nist.gov Subject: AES comments Dear NIST, I am writing to make my recommendations for the choice of the AES. My recommendations are entirely from a security analyst perspective. I am most supportive of RC6 being chosen for the AES. It is quite clear that RC6 is the easiest cipher to analyze. This analysis is aided by 6 years of public research on RC5. I think many people have overlooked the value of this, and many others just do not have the experience with analyzing algorithms to appreciate how important such results are. For instance, the analysis of RC6 had the results of Biryukov and Kushilevitz to build upon, which are the best results today for attacking RC5. Their results were based upon earlier work of Knudsen and Meier which was based upon earlier research by Kaliski and Yin. Biryukov and Kushilevitz were able to mount very enlightening attacks against RC5 by using a more general notion of difference than the earlier researchers. The security analysis of RC6 considers their general notion of difference with respect to both subtraction and exclusive or. Similar experience was gained from linear cryptanalysis and other attacks against RC5. I have not seen any other AES submissions with such general analyses as RC6, nor any analyses that are based upon so much public research. RC6 is a cipher that is so simple that it is inviting to analyze. However, the most significant new result by Knudsen and Meier closely agrees with the security analysis originally submitted by the RC6 design team and myself. The lack of results on such an easy to analyze cipher should be strongly considered, since it suggests that RC6 is the most well understood and has the most accurate security analysis. I recommend to NIST to avoid new ciphers that are not well understood and are difficult to analyze. The two ciphers that come to mind are MARS and Twofish. While these ciphers may (or may not) appear to offer good security at first, it is important to realize that analyzing such ciphers takes many years (even analyzing a simple cipher like RC5 took a couple years to get strong results) and thus we cannot be confident of the true security that the ciphers offer. It will likely take several years before the research community has a good feeling for how secure these ciphers really are. Ciphers that are based upon years of cryptanalysis experience should weigh more than newly designed, complex ciphers when choosing the AES. Thank you for taking the time to read my comments, Scott Contini From: "Walker, Jesse" To: "'AESround2@nist.gov'" Subject: Feedback to NIST AES Questionaire Date: Mon, 15 May 2000 08:04:52 -0700 X-Mailer: Internet Mail Service (5.5.2448.0) This provides feedback from Intel's Network Communication Group to NIST's AES questionaire. Our focus is on the impact of the AES standard on mass-deployment networking markets. If you need any clarification of any of our points, please contact me. Jesse Walker Intel Corporation Network Communications Group 2111 N.E. 25th Avenue JF3-448 Hillsboro, OR 97214 (503) 712-1849 jesse.walker@intel.com 1. NIST has stated its goal that the AES should specify an algorithm(s) that will provide strong security for protecting sensitive data for 20-30+ years. How would the selection of one versus multiple algorithms affect the likelihood of achieving this goal? The selection of a single algorithm would contribute far more to the goal than multiple algorithms. The reasons are sociological, not technical. The first reason is market psychology. If NIST were to select more than one algorithm, the market would ask what's wrong with the lot of them. The public would incorrectly conclude that NIST sufficiently trusts none of the algorithms, or they would have chosen the one most trusted as the winner. This is the "every contest has to have one winner" syndrome, and it is a real phenomenon. The second reason is the criteria to select which algorithm to employ in a particular circumstance are too arcane for even cryptographers. Compelling a choice would overwhelm most people; ask your great Aunt Nellie when she intends to protect her data with Rijndael and when with Serpent. This is not just rhetoric, because cryptographic tools have flooded far beyond the province of security professionals. And we in private industry have demonstrated limited ability in automating the selection process to the degree needed to win wide-spread acceptance of any security standard with multiple algorithms; for instance, almost all IPsec GUIs ask users to select between HMAC-SHA-1 and HMAC-MD5. However absurd this situation might be, it is likely to be repeated with a multi-algorithm AES standard. Finally, multiple algorithms would increase security costs. Multiple algorithms would marginally increase hardware, software, and testing costs for equipment vendors. More importantly, the deployment costs for multiple algorithms would also be higher than for equipment based on a single algorithm, because the deploying organization has to elaborate and configure policies selecting the appropriate algorithm, and then debug and maintain their configuration. None of these costs are trivial for deploying organizations, and they are likely to become only more of a burden as the shortage of IT personnel continues to accelerate each year. This reasoning leads us to believe that, whatever its technical merits, a multiple algorithm standard would delay AES acceptance and deployment, thus extending the widespread usage of 40-bit RC4 and 56-bit DES. Data protected in this way are far more vulnerable to recovery and compromise than data protected by any of the AES candidates. Neither the standard grade school cirriculum nor the lessons from everyday life include an education in cryptography, and so we cannot expect the public to reason correctly or even be equipped to make informed choices in this arena. The technologically elite will use multiple algorithms, regardless of what NIST does, because they can, and everyone else will use one algorithm or nothing at all, because they aren't prepared to do anything else. 2. If only one algorithm is selected, how will sensitive data be protected (with AES- comparable security) in the event that the AES algorithm is broken? History suggests this depends completely on the technical sophistication of the individuals and organizations affected. In the eventuality of a break, the overwhelming majority of people would continue to use the compromised algorithm, and they would resist change until forced to do otherwise (e.g., by an insurance provider refusing to renew a policy without an upgrade). Everyone has known for years that 40-bit RC4 and 56-bit DES do not provide any substantive privacy, but both still enjoy widespread use. On the other hand, the cryptographic literati routinely employ many algorithms, and promptly migrate from old favorites to newer ones with any hint of compromise. Compromise thus leads to interoperability failures and islands governed by competing algorithms, not to needed behavioral change in the user community. Making multiple algorithms available will do nothing for most already encrypted data, because most people will not re-encrypt. Multiple algorithms only make sense in a context of a properly trained and motivated user community, and the larger community is neither so trained nor properly motivated. There are lots and lots and lots of good symmetric key algorithms. The people and organizations who really care about their data being compromised by cryptanalysis will protect their data by a new algorithm when their first choice might be broken. Most people won't. Selecting two or two thousand algorithms for AES will not change this fact. 3. What type of attack on an AES algorithm would be sufficient to "break" the algorithm? A practical attack or a purely theoretical one? That is, when is an algorithm considered to be broken? Another way to think of this is to consider what sort of attack would cause users to lose confidence in the AES algorithm(s). Given the continued wide-spread acceptance of 40-bit RC4 and 56-bit DES, it is difficult to imagine a scenario powerful, practical, imminent, disarming, and threatening enough to even make a blip on the public's radar. The cryptographically sophisticated always respond when a potential for liability threatens, but few other members of society care or even notice. In a world where insurers underwrite losses accrued by organizations attaching today's commercial operating systems to the Internet, raising the question of what will constitute a break in the public's eye seems to miss the real threats. 40-bit RC4 is still in wide-spread use not because it is safe, but because hackers need not bother breaking its keys; simple buffer overrun attacks, not cryptanalysis, are their preferred route. Commercial operating systems cannot become more secure, for the simple reason they are getting more complex, so it seems unlikely the present balance between hackers and their prey will soon change. Thus, while practical attacks are easy against the weak cryptographic algorithms deployed today, by and large this is a concern only to a very narrow portion of the public, because almost all systems offer so many much easier attacks. Those who understand the issues already know lots of algorithms to fall back to in case of a compromise. Why force everyone to choose among different bank vault doors to install on their yurts? The few people who actually possess vaults already know plenty of vault door suppliers. With the exception of this tiny minority, the community cannot and will not use a standard that makes them choose among options they cannot readily distinguish. 4. If multiple algorithms are selected, what effect would this have on interoperability? Note that there are currently multiple algorithms available which may provide confidentiality and other security services. Multiple algorithms have always undermined interoperability. History amply testifies to this. The success of the original single algorithm DES standard is evident. The success of TLS was likewise forged by its reliance on a single weak algorithm, 40-bit RC4. IPsec's comparative lack of success may be attributed in part to its explicit embrace of multiple algorithms. Even though there are many good reasons to promote DSA and EC-DSA as equal partners with RSA, so far the market has adamantly rejected the new-comers, more because of the confusion their deployment would engender than for any apparent cryptographic concerns: RSA got there first. The market overwhelmingly and emphatically tells us over and over again its wants a simple choice: encryption, YES or NO. People want this whether or not it is the ideal choice cryptographically. People without deep professional training and experience in security realize they are incapable of dealing responsibly with the choices a more complex standard would impose. With the advent of PCs and the Web, cryptography is no longer the exclusive sandbox of security professionals. As reiterated before, those who are so inclined will use multiple algorithms regardless of whether NIST selects 1 or 1 million algorithms as the AES standard, while even two algorithms will be a deployment barrier for everyone else. Selecting a single algorithm will maximize interoperability by giving the newly enfranchised a tool with which to push back against the small cadre of experts demanding more. 5. If multiple algorithms are selected, how many should there be? This is the wrong question; there should not be more than one. The availability of two algorithms is no different than ten thousand for the vast majority of the users, because they have no relevant means to distinguish among more than one. Indeed, a multi-algorithm standard presupposes both well-defined criteria specifying when to use one algorithm over another, and that the community relying on the standard is trained in the criteria. Neither presupposition is valid. Without a mechanism analogous to the driver's license testing, an applicable common school cirriculum, or the like, correct application of the criteria by the wider community is impossible. Many security professionals will dismiss this kind of argument as specious, because it ignores any examination of "real" security needs. That is exactly the point, however. The diffusion of cryptographic tools to a vast cross section of the public relegates technical arguments to secondary importance. The cryptographic community seems convinced most of the AES finalists are essentially sound, and that any one of them probably provides vastly greater security than any encryption algorithm used commercially today. All the technical arguments needed have thus already been made to winnow the field to five and then rank them. This has resulted in the best judgement technical consideration can render now. Given this situation, arguments maximizing deployment and use have to become the overwhelming test of acceptability, and this argues for selecting just one algorithm. 6. If multiple algorithms are selected, what sort of guidance or standards would be useful? The assumption behind the question-that it is technically feasible to assemble reasonable guidelines-is questionable at best; the cryptographic community itself hasn't even reached rough consensus on when to use one of the candidate algorithms instead of another. The nearest thing to a consensus is that the people who attended the AES conferences tend to rank their preferences for algorithms as Rijndael first, then Serpent, followed by Twofish, RC6, and MARS. If professionals cannot agree on a finer scale, what are the amateurs supposed to do? With the present state of knowledge, it is infeasible to issue meaningful guidelines for selecting among the algorithms. Lacking meaningful guidelines that crisply and easily divide one usage from another, selecting more than one algorithm can do nothing but sow confusion, degrade interoperability, and delay the adoption of AES. Someone always finds a way to break every algorithm, and we don't know when that will happen with any of the AES algorithms. But none of this will matter if people don't adopt and use AES. Multiple algorithms are a deployment barrier for that vast majority of potential users. The threat of a break remains a theoretical attack in the future. The threat of confusion and misapplication that multiple algorithms engender is real today. Those sophisticated enough to weigh the technical tradeoffs for themselves can and will employ multiple algorithms, regardless of the number of algorithms NIST incorporates into AES. The broader market lacks this sophistication. Indeed, it is implausible that any guidance NIST or anyone else can develop for selecting among multiple algorithms based on existing knowledge would have any practical value or utility outside a narrow community of security professionals. 7. What about the speed versus security margin tradeoff? We would be more comfortable with four more rounds for Rijndael, or doubling the number of rounds for RC6, but then those of us who bother to encrypt our personal data or use a VPN still employ 3DES and IDEA for these functions, so there is some hypocrisy in our response. Even unchanged, all the candidates already appear stronger than what we use. As time goes on, however, the candidates will only become weaker as they undergo further cryptanalysis, so extra security probably wouldn't hurt. At least in the networking arena, customer first want to know if we implement a standards-based algorithm, so they know our solutions are interoperable and have undergone adequate technical review. After receiving a satisfying answer, their next three questions are how fast is the solution, when we will make it faster, and when we will deliver something even faster. The market is very clear and precise: speed wins over security margin. We don't agree with that tradeoff, but that's what the market is saying, and it speaks emphatically with its dollars. The one area where the speed-over-security contingent argument is compelling is in the usability arena. Slow implementations detract from usability as the user community has broadened. Most people are simply not willing to wait on "poor" performance. It does not appear AES will present any problems in this arena, however, except perhaps for some software implementations of Serpent or MARS. 8. How important are low-end smart cards and related environments when selecting the AES algorithm(s)? We offer no opinions on this topic. 9. What is the relative importance of hardware vs. software performance in the selection of the AES algorithm(s)? This question misses the point. There will always be a mix of both, so both will be important, and it is difficult to credulously assign a relatively importance of one over the other. If you talk with end users and the vendors who build for them, the answer will be software, because processor performance is growing faster than the demands placed on end-user systems, and end-user performance is a driving usability concern. If you talk to vendors of choke point devices like servers and network plumbing, the answer will be hardware, because network line rates are growing faster than processor speeds. We have to build all the parts of the system, so the answer has to be both are equally important. 10. What modes of operation should be available for the AES algorithm(s)? The four DES modes should be support, as doing so will simplify the migration from DES to AES. Counter mode is appealing in that it appears to provide marginally better security than CBC, and it is obvious how to parallelize this. A mode combining encryption with data authentication, like Gligor's PCBC mode, would also be attractive. From: DWHITING@hifn.com To: AESRound2@nist.gov Subject: Comments on email from David Oshel Date: Mon, 15 May 2000 09:35:58 -0700 X-Mailer: Internet Mail Service (5.5.2650.21) Mr. Oshel has posted a comment noting that Twofish was very slow on his Macintosh PowerPC machine. His numbers made no sense to me, since Twofish was FAR slower even than Serpent in software, which has not been the case on any other platform (even Eli's machine ). After corresponding with him, it was determined that his test application encrypts exactly ONE block before re-keying. However, his initial numbers we taken using the Twofish "full keying" option implemented in Brian Gladman's code. I recommended that he use instead the "zero keying" option of Twofish, which was intended for just such "non-bulk" applications. Within a few hours, he responded to me as follows: "Thanks for your help on this! After the relevant code changes, Rijndael, Serpent and Twofish all clocked in on the same test with the same start (seed = today's Julian date) at 13 seconds. If I'd been checking 0.1s I might have seen a difference." Thus, the problem was not a Twofish algorithm problem, but how he was attempting to use it, in a somewhat unrealistic environment. Since he apparently has not yet posted a clarification on this issue, I wanted to make it clear that the issue was resolved to his satisfaction. X-Lotus-FromDomain: CERTICOM From: "Don Johnson" To: AESround2@nist.gov Date: Mon, 15 May 2000 14:22:39 -0400 Subject: Don Johnson's Final Thoughts on AES NIST, Here are my final thoughts on AES, contributed to NIST as grist for the mill: 1. In the AES3 summary poll, many voters indicated they wanted a single winner or possibly a single winner with a backup if patent concerns or security concerns surfaced later. It is essential that NIST listen to all potential users of AES and attempt to make the best decision that meets the needs of ALL members of its constituency. Sometimes a decision needs to be made that is NOT the most currently popular decision; this is the essence of leadership and often takes courage. It is important that NIST not let any (admittedly unscientific) polls be a large determining factor in its decision. Rather, I suggest the best use of the results of the polls is in recognizing that NIST must explain the rationale behind its final decision as much as possible. Inquiring minds want to know! 2. Each of the summary papers by the inventors of each finalist algorithm give advantages of the algorithm according to certain criteria and tries to put their algorithm in the best light possible. Each paper tries to give good reasons for selecting their algorithm as the finalist. In effect, each summary paper can be seen as contending that the author's rationale should be used by NIST to decide the AES contest. This means that NIST could justify the selection of ANY finalist simply by adopting the criteria and rationale of the corresponding summary paper as its own. One problem with accepting any particular criterion as critical is that often the best choice under one criterion is not so good under another criterion. Using performance as examples: RC6 seems to be fastest on a modern PC but seems slowest on some processors without support for multiplication. SERPENT seems to be fastest in hardware but is often slowest in software. As another example, for some applications, key agility is very important; for others, the effect of key agility is negligible. How is NIST to make a choice regarding which criteria are more important that others? Rather than NIST attempting to choose which optimality criterion/criteria is/are MOST important, NIST could instead choose to adopt the anti-pessimal criterion, which says to pick an algorithm which is not bad anywhere. According to the anti-pessimal criterion, RIJNDAEL is a suitable AES winner. This was noted at the conference by Vincent Rijmen using somewhat different words. It is important that the many advantages of NIST adopting the anti-pessimal criterion not be overlooked, hence I am restating it here. 3. If NIST believes that it needs to choose some optimality criteria, my perspective is that suitability for use on constrained devices should be THE critical criterion. This is where the AES decision can make or break the potential for new functionality in a future product or solution. To be specific, on a modern PC acting as a client, it appears that any finalist would be acceptable. On a server, one can add more hardware if performance is a concern. On a constrained device, the requirement to use an algorithm that is not as suitable as another can make or break the feasibility of an application for the device, raise the price point, etc. Some say that future advances and Moore's law will overcome any current limitations on processors, but Moore's law has historically manifested itself in two ways (A) faster computation for a fixed price as newer chip designs pack more power and (B) cheaper computation for a fixed time as older chip designs become cheaper. It is important to note that the crypto engine will not be the only code running on a constrained device, applications will also. My concern is that selection of a less suitable algorithm will have a cascading ripple effect in two ways: (A) Internal: The constrained device will need to be larger, more costly and/or less flexible. (B) External: Constrained devices are expected to proliferate and become ubiquitous. As a first approximation, essentially all crypto engines will be on constrained devices. This simply means that any negative consequences of NIST's AES decision in regards to constrained devices packs a double whammy. >From a constrained device viewpoint, the selection of at least one algorithm from the set of (RIJNDAEL, SERPENT, TWOFISH) as an AES winner seems advantageous for the following reasons: A) MARS and RC6 appear to require more RAM for initialization. B) MARS and RC6 require support for multiplication to fun fast. On cheaper processors, this function may not exist and will need to be emulated. C) MARS and RC6 appear to be less key agile. This becomes of greater relative importance as shorter messages are encrypted or when the cipher algorithm is used for hash purposes. 4. Adi Shamir made the suggestion at AES3 that it would be acceptable to him for NIST to flip a 5-sided coin to determine the winner. This does not seem to me to be the best way for NIST to proceed. However, I suggest that Adi's idea can be used with merit in the following way: NIST (in its collective mind) can PRETEND to flip a coin and contemplate the likely results if any of the five finalists were selected as the/a winner. If, while the coin is in the air (so to speak) NIST discovers that it wants the coin to fall in a certain way, then this can be a way to tap into subconscious and unconscious thoughts that may not at first be apparent to the conscious mind. In other words, if while the coin is in the air, NIST hopes it would come down in a certain way (or at least not come down in a certain way) then I suggest it would be fruitful to explore further why this is so. When I personally conduct the pretend coin flip exercise above, my results are as follows: A) At the minimum, NIST should select a primary algorithm and a secondary algorithm. B) RIJNDAEL becomes the primary algorithm, being the anti-pessimal choice and suitable for constrained devices. As such, it would become the default FIPS symmetric algorithm and used unless there is a GOOD reason for it not to used. C) SERPENT becomes the secondary algorithm, able to be used by choice for a specific reason, such as super AES (multiple algorithm encryption) or hot backup (if RIJNDAEL should be discovered to have a flaw), speed for hardware link encrypters (as they only talk to themselves), etc. The point is that there would need to be a GOOD reason to use SERPENT; but if there was an explicitly-stated good reason, it would be allowed. Don B. Johnson, Certicom From: "Kaliski, Burt" To: "'AESround2@nist.gov'" Cc: "'mrobshaw'" Subject: Patent waiver for modifications to RC6 Date: Mon, 15 May 2000 16:12:19 -0400 X-Mailer: Internet Mail Service (5.5.2448.0) RSA Security has already waived any license or royalty payments, no matter which algorithm is chosen as the AES. See http://www.rsasecurity.com/rsalabs/aes/rc6_patent.html. As requested by NIST, we can therefore confirm that this policy would also apply if a version of RC6 were selected with different parameters to those recommended in the AES submission. -- Burt Kaliski Burt Kaliski, Chief Scientist and Director RSA Laboratories - http://www.rsasecurity.com 20 Crosby Drive, Bedford, MA 01730 USA +1 781 687 7057; fax: +1 781 687 7213; bkaliski@rsasecurity.com X-Server-Uuid: 7edb479a-fd89-11d2-9a77-0090273cd58c From: "Schroeppel, Richard" To: "'aesround2@nist.gov'" cc: "Schroeppel, Richard" , "'rcs@cs.arizona.edu'" Subject: comment for AES cipher selection Date: Mon, 15 May 2000 14:18:37 -0600 X-Mailer: Internet Mail Service (5.5.2650.21) X-WSS-ID: 153E8415129311-01-01 Here's my analysis of the AES cipher selection. There are some equations near the end of Appendix D which look best in a fixed-width font. Rich Schroeppel rcs@cs.arizona.edu rschroe@sandia.gov ---------- AES Comments May 15, 2000 Rich Schroeppel Sandia National Laboratory University of Arizona rschroe@sandia.gov Disclaimers: As should be abundantly clear, the opinions expressed in this letter are mine alone, and are unlikely to be official positions of any organization. I submitted a cipher to Round 1 of the AES process; it was not selected for Round 2. Abstract: I discuss the five AES candidates, and suggest various improvements. NIST should send all five ciphers back for rework, and hold another conference in six months to analyze the revised ciphers. Failing that, I reluctantly recommend Twofish as primary AES and Serpent as backup AES. Summary of Most Important Recommendations: None of the AES candidates is completely satisfactory. NIST should return all five candidates for curing of deficiencies, with a two month deadline. Another conference should be held in six months to review the revised candidates. Deficiencies are listed in Appendix A. No cipher should be selected with a modified number of rounds or other revisions, without further public review. Among the present unmodified candidates, Twofish is the best choice as primary AES. Serpent should be an optional backup. CBC mode must be replaced. I suggest LFSR-counter mode, described in Appendix C. A full list of recommendations precedes Appendix A. 1. Introduction NIST is searching for a block cipher to replace DES. [1] Three conferences have been held to evaluate the candidates. Fifteen candidate ciphers have been winnowed down to five. Many algorithms have been attacked, defended, implemented on multiple platforms, and measured and simulated in mushware and hardware. Public comments have been solicited and offered. The time is at hand for a final decision. This note argues that we now understand the problem better, and should give the cipher teams suggestions for improvements. The final decision should be deferred six months. Section 2 addresses the question of appropriate security margins, concluding that RC6 and Rijndael have insufficient margin. Section 3 argues that hardware cost has been neglected by most of the teams. Multiplication as an inner loop operation is unacceptable. Key expansion is too difficult for some ciphers, and hard to run in the decryption direction for most candidates. Cipher Block Chaining mode should be replaced. Section 4 discusses other issues, including the AES process. Section 5 contains a list of recommendations. Appendix A lists recommendations for each candidate. Appendix B contains my guesses about future computing power. Appendix C explains an idea for replacing CBC mode. Appendix D discusses my concerns with Rijndael, and offers some suggestions for strengthening it. 2. Security "Prediction is difficult, especially of the future." -- Niels Bohr The most important criterion in cipher selection is security. All the candidates claim to be "secure enough", so that secondary considerations such as speed and implementation cost become tie- breaking factors. None of the ciphers has been broken, in the sense that someone using one today would have reason to fear for the privacy of his traffic. The arguments center around appropriate security margins, and how much weight to give to infeasible academic attacks against reduced-round versions of the candidates. The Importance of Academic Attacks An attack is academic when it represents no real threat to traffic encrypted with the cipher. Examples are attacks that require 2^100 plaintext-ciphertext pairs, or an attack that distinguishes the cipher from a random permutation, or demonstrates a failure of some other theoretical criterion. Most attacks against ciphers are academic. All the reported attacks against the AES candidates are against weakened versions of the ciphers, usually with the number of rounds reduced. Academic attacks are the best predictors we have of real-world attacks. The history of cryptography confirms that attacks improve. Progress is so erratic that it's impossible to forecast improvements. When DES was announced, the best attacks could break four rounds. There are now practical attacks on eight rounds, and two different academic attacks on the full sixteen rounds. One of the academic sixteen round attacks has been demonstrated. Progress continues; recently the amount of material required for Matsui's linear attack was reduced by a factor of four. The most important discovery about DES was a structural weakness of Feistel ciphers -- half the rounds could be ignored. Three of the five AES candidates use modified Feistel structures. The AES is expected to last twenty years, and may be with us for a century. If it's good enough, it may well be permanent. (In spite of known attacks, movement away from DES has been glacial. Even the existence of a key-search machine has not discouraged some folks for proposing DES in new network protocols!) A successful AES will be a very tempting target, attracting the attention of the best and brightest cryptographers. Appropriate Security Margins Briefly review the drawbacks of a busted AES cipher: (a) A new cipher must be adopted in haste. (b) Old software that can't be adapted to the new cipher must be abandoned. (c) Old hardware is toast. (d) Old data that was thought to be safe is at risk. (e) People will continue to use the old cipher. Some of their traffic will be broken. (f) Bad guys may have been secretly reading traffic for years. (g) New software must use the new cipher, but maintain compatibility to read old encrypted records. (h) New hardware is in the same boat. (i) The actual transition time for new software and hardware is several years. Some hardware, such as satellite electronics, has a much longer lifetime. Now examine the costs of selecting a cipher with extra security margin: (j) It runs slower in hardware and software, or needs extra area in hardware. (k) The maximum bandwidth achievable with given amount of logic is less. (l) A few applications become infeasible or uneconomic because the cost of the encryption becomes too large, or the cipher won't fit on the chip, or crowds out some other functionality. (m) Some applications that would have used encryption will omit it because it's too slow. As part of deciding how much security margin is appropriate, we must balance factors a-i against factors j-m. Since the cost of recovering from an insecure cipher is pretty high, it's prudent to add some security margin beyond that required for "can't be broken in the near term". I agree with Lars Knudsen's suggestion: An AES cipher should use twice as many rounds as the most effective attack that's better than exhaustive key search. This protects against the most likely catastrophe, discovery of a structural weakness such as happened to DES. It also protects against incremental improvements in the attacks that we see every year. It offers some protection against quantum computing, although this is probably a fool's errand. (Appendix C has my guesses about the future of computing.) This is a conservative criterion -- if we were not trying to plan for an uncertain long term future, we could accept more risk. If we were designing a single application for a short lifetime, we could accept more risk. But the AES will be the world's major cipher for quite a while, and we can't accept more risk. By this criterion, RC6 and Rijndael have insufficient safety margin while Serpent is overbuilt. Other Security Issues Ross Anderson argues that we should routinely use 256-bit keys, and skimp with 192 or 128 only when absolutely necessary. I'll disagree somewhat, and say that we should use 256 bits when it doesn't increase cost much. The current situation is that we don't have infinite hardware, so an application that stores a large number of keys will prefer to use keys that are as short as possible. Some of the ciphers are slower with longer keys. Most seriously, our key exchange algorithms take unpleasantly long when matched with a 256-bit symmetric key. A Diffie-Hellman key exchange matched to 128-bit security will use a prime modulus of 3000 bits; matching 256-bit security requires a modulus of 15000 bits, and the key exchange will take twenty-five times as long to compute as the 128-bit case. The situation is somewhat better if elliptic curves are used, since the curves need only use 250-bit or 500-bit fields; but 128-bit matched security will run six times as fast as the 256-bit case. This suggests an additional requirement for the AES ciphers: Truncated key spaces should still have exhaustive-search complexity. Legacy systems will be using keys of 40, 56, 64, 80, 112, and 168 bits: A standard way of converting such keys to 128 bits (or more) is needed. If I extend an 80-bit key to 128 bits by padding with 0s, and the attacker knows this, breaking the cipher should still require roughly 2^80 effort. Ditto if I extend the key by copying 48 bits, or by xoring two overlapping copies. This requirement is related to the notion of weak keys, but has a different complexion. Weak keys are a lesser concern if they are unlikely to occur in practice; the "truncated key" problem is to show that particular sets of keys which are likely to occur in practice aren't weak. Except for RC6 and perhaps Mars, all the ciphers have the property that recovering the expanded key will translate into recovering the primary key. More seriously, the key schedules of Rijndael, and to some extent Serpent, allow an attacker who recovers (or guesses) some of the expanded key to compute additional bits of the expanded key. Recall that both differential and linear attacks on DES benefited from replicated subkey bits -- as soon as an attack finds a few subkey bits, the game is over. Most ciphers execute the same length of time regardless of key length. Rijndael and Twofish vary their encryption effort with the key size, Rijndael by adding rounds, Twofish by complicating the sboxes. The other ciphers might benefit by adjusting the number of rounds to match the security level implied by the key length. Some effort has been devoted to seeing which ciphers best resist power measurement attacks. Attempting to protect cheap smart cards from their possessors is a losing battle. Fancy test equipment always wins, so any secret worth stealing will be stolen. Protecting the smart card with the holder's cooperation is more reasonable, and benefits from prevention of timing attacks, power attacks, RF leakage, etc. However, some smart cards will be stolen, and their secrets extracted. This should be recognized at the system design stage. I give no weight whatsoever to the difficulty of implementing a block cipher in software: The criterion is silly. Any serious implementer will test his code against the NIST-required test values, which are sufficient to guarantee good faith code against bugs. Most folks will simply download a certified implementation, or buy software containing a tested implementation. An additional argument was made at the AES3 conference, that we don't want to see headlines such as "AES broken" whenever someone discovers how to lower the number of chosen ciphertexts to break Rijndael-256 from 2^254 to 2^253. I don't put a lot of stock in this argument: People will get headlines however they can, and it doesn't much matter what we do. Security of the AES Candidates Mars Mars has adequate margin against the attacks presented so far. The idea of using different kinds of rounds is a good one. The symmetrically reduced twelve round attack from AES3, with three of each type of round, is less than half of the actual eight cipher rounds of each type. The full wrapper plus five core round attack (also from AES3) is only one third of the keyed cryptographic core, so again the margin seems adequate. The eleven round attack [2] on the Mars core is more than half of the actual sixteen round core, but it isn't a threat because it omits a feature (the sixteen round unkeyed wrapper) specifically included to vitiate the attack. The Mars key setup is subject to a timing attack, to determine the number of long-bit-block fixups that occurred. This information doesn't seem to help an attacker: even knowing some of the extended key bits doesn't help to learn others, and the extended key is much larger than the primary key. RC6 There is a fourteen round attack [2] on RC6. There is also a fifteen round attack on RC6-256. Since the actual RC6 has only twenty rounds, the margin is insufficient. Rijndael Rijndael has inadequate security margin. Rijndael-128 (with ten rounds) had a six round break included with its submission, and the FSE2000 and AES3 conferences showed a break of seven round Rijndael-192 (which uses twelve rounds). AES3 also included a break of seven round Rijndael-128 that is "marginally faster than exhaustive search". Appendix D addresses some of my concerns with the Rijndael sbox, and suggests a way to defeat the Square attack, which might allow ten round Rijndael to be secure. Papers at AES3 and FSE2000 pointed out minor weaknesses in the key schedule. Rijndael varies the number of rounds depending on key length, so a simple timing measurement will determine the key length. Although important, this information is usually available to an attacker from other sources. Serpent Serpent (32 rounds) is overengineered; the best attack in only eight rounds, although the Serpent team conjectured the existence of longer differentials. The overengineering comes at a cost: Serpent is typically twice as slow as the other ciphers in software. Twofish The best attack against Twofish only gets six rounds, versus sixteen in the actual cipher. More time is needed to see if Knudsen's unsuccessful attack on nine round Twofish can be salvaged. Some implementations of Twofish have execution time that depends on key length, so a simple timing measurement will determine the key length. Although important, this information is usually available to an attacker from other sources. Security Summary RC6 and Rijndael-(128,192) have insufficient security margin. Mars and Twofish have adequate margin. Serpent has too much margin, and pays a speed penalty for it. 3. Hardware Considerations Of the AES candidates, hardware folks prefer Rijndael and Serpent. AES is a big step backward for hardware encryption. Measured by throughput/area, no candidate has a clear advantage over 3DES, and several are worse. It's not impossible that high-speed hardware will go its own way if any of the current candidates is adopted without modification. DES was designed for hardware implementation: The original standard explicitly forbade software implementations. DES uses primitives that are hardware friendly, such as random-looking permutations, shift registers with random-looking taps, tiny fixed sboxes, and nary a carry in sight. The key schedule is simple, based on a stuttering shift register, which rotates back to the original key after each encryption or decryption, and shifts one way for encryption and the other way for decryption. The cipher hardware is nearly the same for both directions. Perhaps in reaction, the present AES ciphers are software oriented, and somewhat hardware unfriendly. The ciphers have larger storage requirements, and rampant additions and multiplications. Hardware folks barf at multiplication, and would prefer not to have the long carry chains in 32-bit addition. There is no use in the present candidates of random-looking bit permutations; this is a powerful primitive in DES, but software doesn't support it. Key schedules are more software oriented, with some of the encryption effort being in the key setup, rather than simply moving the bits around as DES does. None of the ciphers has a cycle-back key schedule to ease decryption. Reading through the AES3 hardware implementation papers, I compiled an implied Hardware Wish/Unwish List: Key schedule computable from either end, a round at a time, in parallel with encryption/decryption. Constant time key setup. No variable rotations. No additions. No multiplications. Small sboxes. Random looking bit permutations are good. Encryption and decryption should be virtually identical. CBC mode must go! Sandia's high-speed DES board uses a pipeline stage for each round, and can have 16 different encryptions/decryptions in progress with 16 different keys, and freedom to select encryption or decryption for each datum. This is the highest-throughput implementation strategy I know of. Translating the technology to an AES cipher will run into significant problems: Of course, the circuit complexity (area or gate-count) must increase because of the longer blocksize and keysize. But that's recovered in extra throughput. However: The decryption key schedule is a problem for every cipher except Twofish. The sbox area is much larger for all the ciphers except RC6, which needs a squarer. The round functions are more complicated. Decryption Key Schedules Only Twofish has a key schedule that's easy to compute in both directions. The Serpent and Rijndael key schedules can be run backward, if the final state is first computed. This seems to require computing the full key schedule in the forward direction, or equivalent work. Mars and RC6 are worse: the full key schedule must be computed and stored, and most of the work must be completed before the first round key is ready to use. Two simple key schedules that are easy to compute in both directions: (a) Step the key forward with some invertible transformation. Apply a simple map such as Serpent does to generate each round subkey from the stepped key. Arrange for the key to return to the starting state after R (the number of rounds) steps. DES did this with a stuttering shift register, but there are also linear transforms available for any period. If the number of rounds is variable, then some steps are stuttered. Including a stutter in the key schedule is a good idea anyway. (b) Another way is to use a "tent" pattern: The key is stepped forward for half the rounds, and then stepped backward to return to start. The first half and second half subkey-generation maps must differ so that the subkeys are different in the second half. Some care is required to avoid the DES weak key problem with 0 keys. One interesting option for using a cipher with unequal encryption and decryption costs is role reversal: Use decryption as the encipherment and encryption as the decipherment. Unfortunately, this cannot be recommended without further analysis. Most of the analysis done so far would carry over to the inverse cipher, but it's unwise to use a cipher in an unintended mode: Something may have been overlooked that would be apparent if the mode had been examined closely from the beginning. CBC MUST GO! CBC mode encryption is a problem for any parallel or pipelined hardware system. The fixup is to use lagged CBC, with a lag greater than or equal to the number of pipeline stages. This requires an unreasonable amount of IV, and forces even non-pipelined hardware to remember the intermediate IVs. There are proposals for two or three pipeline stages per cipher round. That's a lot of lag. Many folks suggested Counter Mode as an alternative. I propose LFSR- Counter Mode. It's as easy to implement as Counter Mode, and allows arbitrary lookahead and so arbitrary parallelism or pipeline depth. The details are in Appendix C. The ATM Forum has a Counter Mode standard. Other modes are also possible; almost anything is better than CBC. Multiplication in Block Ciphers Considered Harmful I was very surprised that Mars and RC6 were advanced to the final AES round, since they require a 32-bit multiplier (32x32->low32) and a 30-bit squarer (30^2->low31). This is too much of a hardship for a high-speed hardware implementation, and also a burden on low end smart cards. It also guarantees that when new processor architectures appear, they will be slow on these ciphers, since integer multiplication speed is never as good as simpler instructions. (An architecture is mature (senescent?) when multiply is nearly as fast as add.) Multiplication circuits are (1) slow (2) area hogs (3) power hungry (4) hard to test and (5) full of possible patent potholes. IBM-Japan had a good paper at AES3 about minimizing carry-chain propagation delay in the Mars multiplications. There was no mention of patentable circuit optimization techniques in their paper. IBM is a reputable company, and I'm sure they are planning to donate their best Mars circuits to the public domain. But anyone else could have filed a submarine patent we won't hear about for years. On the bright side, if Mars or RC6 is selected, we will probably see a flowering of new circuit design talent, since there's so much scope for clever optimization. Perhaps our goal of the fastest and best cipher is less important than encouraging this design talent. Other Hardware Issues Although Twofish has the most decryption-friendly key schedule, it compensates for this in other ways. Twofish uses key-dependent sboxes. This gives the hardware designer a Hobson's Choice for pipelined encryption with differing keys: Either use substantial real estate to precompute the sboxes and pass them along at each stage of the pipeline, or apply three-to-five levels of sbox at each round. Having an adjustable number of rounds will cause trouble for pipelined systems. If a cipher with less than the recommended number of rounds is adopted, such as Rijndael-128 with 10 rounds, hardware designers may want to provide for an increase by including a few extra pipeline stages, and a bypass for current operation. Another possibility is to provide contingency circuits for double and triple encryption. One objection to having a backup cipher in the Standard is that hardware implementations will waste area for the backup cipher. One answer to the "idle hardware" objection is to use both ciphers, with some traffic in each cipher. This changes the backup cipher from a hot spare into extra capacity. 4. Other Issues The AES Process There is some sentiment for negotiating changes privately with the developers -- for example, Rijndael has been suggested with 14-18 rounds. This is a bad idea for several reasons: (a) From the public process viewpoint, it stinks like a three day old fish, no matter how innocent the purpose. One important goal of the public development process is to avoid the controversy that surrounded DES; this isn't the time to abandon openness to speed up the selection process. (b) It means the actual selected standard will not have been publicly reviewed. The speed estimates for a revised cipher are simply estimates, as are the area estimates for pipelined chips -- the highest speed chips. In most cases NIST is not particularly qualified to do the estimating: The proper folks to ask are the ones who did the original work. (c) There's been only desultory discussion of questions such as "How many rounds of Rijndael or RC6 would be secure?" and people haven't had a proper debate with the issues lined up to do battle. (d) Finally, I suggest revised key schedules for the ciphers to help out the hardware folks, and these must be reviewed if adopted. There won't be a chance to do it over; let's get it right the first time. I contend that sending the ciphers back for rework will give us a better crop to choose from, resulting in a better, more widely adopted, standard. The argument against delay can be summed up as "It's late and getting later; we should have done this five years ago". It comes down to standing still while the meter is running: we'd rather get started designing our hardware and software. Fortunately, encryption is modular; most software can be created with dummy encryption, and the actual AES cipher inserted near the end of the creation phase. (Testing must be done with the actual cipher in place.) Users of DES-based systems are concerned, since processing power and clock speeds continue to increase, and DES becomes more vulnerable each month. However, DES is not yet breakable without serious resources, either special chips or a thousand PC-years. This will remain true for a couple of more years. Triple DES is not threatened, and is merely slow; there's no urgency to switch, and another six months delay won't hurt. There are two other timetable related considerations: (a) The time for analysis has been insufficient. There aren't enough public cryptographers to give full scrutiny to all the ciphers. If NIST feels they must choose a cipher now, then they should designate a provisional candidate(s), to focus further evaluation and criticism. If nothing damaging emerges in a year, the provisional standard can be adopted. (b) This also reduces the threat of an "IP-attack" with a submarine patent, since such patents can only remain submerged for a limited length of time. Miscellaneous Comments CBC mode must be phased out, and replaced with counter mode or some alternative. NIST (or the cipher developers) should recommend standard method(s) of key extension. There will be folks using 64-bit and other short keys. The two obvious fast methods of key extension to 128 bits, padding with 0s and doubling the key, need significant security analysis for some of the ciphers. Extending a key by "hashing up" (feeding it through SHA), is secure but slows down encryption and requires extra hardware. Longer keys (192 and 256 bits) require two calls to SHA. There's been no testing of other block sizes; NIST has no basis to recommend any blocksize other than 128 bits or any keysize other than the standard three (128, 192, and 256). This means that the various ciphers' advertised flexibility for other block and key sizes is merely show: It's not safe to use the flexibility without more adverse attention being directed at the variations. Most ciphers execute for the same length of time regardless of key length. This may indicate an opportunity for optimization. If encryption and decryption aren't equal time, decryption should be chosen to be faster. This will optimize the situation where an encrypted message is broadcast and decrypted separately by multiple receivers. It's been pointed out that planning for a cipher transition is cheaper than doing it unplanned; having a backup handy is good sense. Naturally, in the case of cryptographic surprise, the cipher will be abandoned with all deliberate speed, regardless of any official NIST pronouncement. The benefit of "only one standard" is that the hardware and software can assume that the encryption method is known, with no header bits or protocol negotiations required. But this benefit becomes a liability when the inevitable upgrade to the new system happens, and the application is stuck in the past and cannot even in principle handle the new traffic. Mars should receive a "certificate of apparent security" so that those who wish to use it have a formal document to cite. It should not be in the standard, becasue it contains a multiplication in its inner loop. 5. Conclusions & Recommendations (You Asked!) None of the AES candidates is fully satisfactory. Most can be improved significantly with modest changes. NIST should return all five candidates for curing of deficiencies, with a two month deadline. (A list of deficiencies is in Appendix A.) Another conference should be held in six months to review the revised candidates. This will push the final decision date back to summer 2001, but we will have a better cipher. In particular, hardware will be faster, and possibly software as well. In the interim, NIST could designate a front-runner to focus cryptographic attention. No revised cipher should be considered without several months for public analysis and discussion of the revisions. NIST should explicitly not endorse any blocksize other than 128 or keysize other than 128, 192, and 256, regardless of a cipher's advertised flexibility. NIST (or perhaps the cipher developers) should designate a standard method of padding or extending short keys (such as 40, 56, 64, 80, or 112 bits) to 128 bits for use with the selected AES ciphers. Applications are encouraged to include capability for changing algorithms, or at least, switching to the backup cipher. The closer the backup comes to being a hot spare, or extra capacity, the better. CBC mode should be replaced with LFSR-counter mode, described in Appendix C, or some alternative mode. If this process is ever repeated, more consideration should be given to hardware from the start. If we are doing this again in twenty years, add the criterion that the inverse cipher, using decryption as the cipher, also be secure. Since there hasn't been sufficient time for adequate cryptographic review, any standard should be considered provisional for a year, and subject to recall if significant adverse information develops. My choice among the present candidates is Twofish as primary AES, with Serpent as optional but strongly encouraged backup. Mars should receive a "Certificate of Apparent Security" but not be part of the Standard. Acknowledgments I would like to thank Tom Cabe, Ed Witzke, Anna Johnston, Susan Landau, Lyndon Pierson, and Craig Wilcox for helpful discussions. References [1] Proceedings of the 1st, 2nd, and 3rd AES Conferences. http://www.nist.gov/~aes AES CDroms 1, 2, and 3 [2] Preproceedings of FSE2000. Appendix A: Defect List Mars Mars should replace the inner loop multiplication operation with some alternative. The key schedule should be computable on the fly from either direction. The variable key setup time, to check for and fix long blocks of 0s and 1s in the round subkeys, is a minor blemish, but it slows down a pipeline implementation. RC6 RC6 has insufficient security margin. Since 14 rounds have been broken, 28 is the minimum acceptable. RC6 should replace the inner loop squaring operations with some alternative. The key schedule should be computable on the fly from either direction. Rijndael Rijndael-128 and Rijndael-192 have too few rounds. Since 7 rounds of each has been broken, the minimum should be raised to 14 rounds. (This might cause Rijndael to lose its speed advantage.) Change the Shift-Row operation to break up the bytes, to counter the Square attack. The sbox should be replaced with a non-algebraic sbox. Encryption is faster than decryption: they should be exchanged. Papers from FSE2000 and AES3 noted minor weaknesses in the key schedule. The key schedule should be computable on the fly from either direction. (The encryption direction is ok now. The decryption direction can be computed backward, if first computed forward, but this requires substantial additional time in hardware, or a software assist.) See Appendix D for discussion. Serpent Serpent has too many rounds, and is consequently slower than it needs to be. The key schedule should be computable on the fly from both directions. (The encryption direction is ok, but the decryption direction requires a special setup circuit, or software help.) Twofish There's nothing wrong with Twofish, but small hardware implementations will be slow. The key-dependent sboxes make fast pipelined hardware expensive. Since the other ciphers are being returned for rework, the Twofish team may as well have a chance to improve Twofish. If Knudsen's nine-round attack fails, the number of rounds in Twofish could be reduced. Appendix B: The Future of Computing Power -- Speculations One conspicuous absense in the AES discussions has been the phrase "threat model". The assumption is that a good cipher can trump all threat models with the magic words "128-bit key". During the coffee break, we backtrack to discount academic attacks, insinuating that an attack that requires 2^100 P/C pairs can be safely ignored. One of the benefits of a powerful cipher is that it can be used and forgotten about: Whatever security problems may occur in our widget or protocol, the cipher won't be the weak point. On the other hand, it never hurts to look around a bit. How powerful might an adversary be in the near future? Current limits on world computer power are 2^70-75 encryptions/year and storage around 2^60-70 bits of memory. (Some attacks require real-time available memory, but others can be carried out with massive tape libraries.) For available enciphered material, it's possible that someone has encrypted as much as 2^55 bits (2^48 blocks) of data under one key. This would be a 1GHz channel for a year, or a million backup tapes. It's reasonable to project another 20-30 bits of computing power from "Moore's Law" and further market penetration of computers. Bandwidth will grow by another 10-30 bits. Presumably demand for processing power and bandwidth will saturate when each of us has a real-time synthetic video channel. In the far future? Restricting ourselves to conventional physics, assume every atom in the top kilometer of Earth's crust is a gate, and switching occurs at the speed of light traveling the length of a chemical bond. We are limited to about 2^156 gates (or memory) and 2^61 gate transitions/second. Assume about 15000 gate transitions to encrypt. This translates to about 2^228 encryptions/year. Any attack using more than these resources will remain academic until we can build brains the size of a small planet. It's too early to tell if Quantum Computing will develop into anything real. There's a QC algorithm for searching N^2 things in time N; if this can be applied to exhaustive key searching, it would mean that key lengths should be doubled to resist quantum attacks. There's no proof as yet that NP-complete problems require exponential times with conventional computers, although the betting is that they do. It's possible that QC will permit "full parallelism", allowing searches of 2^N things with N qubits. This would make NP-complete problems practically solvable, and destroy conventional cryptography. No such general QC algorithm is known. There are QC algorithms known with exponential speedup for solving factoring and discrete logs, but these don't seem to be NP-complete problems. Appendix C: Replacing Cipher Block Chaining (CBC) Mode CBC MUST GO! CBC mode encryption is a problem for any parallel or pipelined hardware system. The fixup is to use lagged CBC, with a lag greater than or equal to the number of pipeline stages. This requires an unreasonable amount of IV, and forces even non-pipelined hardware to remember the lagged IVs. Counter Mode has been suggested as an alternative. I propose LFSRC (Linear Feedback Shift Register Counter) Mode. It's as easy to implement as Counter Mode, but allows arbitrary lookahead and arbitrary parallelism or pipeline depth. LFSRC copes with the two main problems of Counter Mode: (1) It's a little too likely that two adjacent plaintext blocks have consecutive values that become equal when the counter is xored with the plaintext, and hence encrypt to the same ciphertext; and (2) CM encrypts a long plaintext block of 0s as the encryption of a sequence of consecutive integers, a worrisome practice if our cipher has an unknown weakness. In LSFRC Mode, a 128-bit linear feedback shift register is initialized from an IV. The register is xored into the plaintext before each encryption, and is stepped after each block. The step function is to shift the register one bit to the left; if the bit that fell off the end was a 1, we xor 0x87 into the low byte. This corresponds to the polynomial u^128 + u^7 + u^2 + u + 1, the first (mod 2) irreducible polynomial of degree 128. It has maximal period, 2^128-1. The register can be initialized from a full 128 bit IV, or by a shorter IV of length 32 or 64 bits. The shorter IVs are replicated to make up the full register length. An IV of 0 means ECB Mode. Appendix D: Problems with Rijndael (Notation: In this appendix, + is used to mean addition in the GF[256] field used by Rijndael. This is done by xoring the bits representing the field elements. For single bits, this is just xoring the bits. This frees up the symbol ^ to represent powers. I use the letter u to represent the field basis generator. The Rijndael field polynomial is u^8 + u^4 + u^3 + u + 1.) Rijndael has several properties that I find worrisome. These could be easily fixed, with minimal impact on code execution time and circuit size. Rijndael is a Byte Cipher Rijndael is really a cipher on bytes, rather than bits. All of the manipulations treat the bytes as whole objects, and Rijndael does nothing to break up the byte structure. This weakness is what allows the Square attack to work. Fortunately, it's easy to fix, by changing the Shift-Row operation to rotate the rows a non-integral number of bytes. The Fearful Symmetry of the byte movements bothers me. If the Round Constants used in the key expansion were missing, then encryption would be compatible with rotating each word of the plaintext and key by a byte. The Round Constants for the first eight rounds are single bits. Rijndael is Mostly Linear A second Rijndael design decision is "not to mix groups". The cipher contains no ordinary arithmetic additions. The only non-linear function in Rijndael is the sbox; the rest of the cipher is pure xors. One amusing consequence is that the cipher has a number of "alternative implementations" available. Any linear map can be applied to the bits within a byte, with the same map applied to every byte, and other parts of the cipher adjusted, to get the same cipher. Example: Suppose we map bytes by xoring the low order bit of each byte into the adjacent bit. B1 += B0 (Recall that I'm using + to mean xor, so that ^ is free for exponents.) The necessary compensating internal changes are: Plaintext and ciphertext are adjusted to match, as a wrapper around the revised cipher. The input of the sbox is adjusted by conceptually xoring the address lines: A1 += A0. This is equivalent to exchanging two quarters of the sbox table. The output of the sbox is adjusted by xoring S0 into S1. The Mix-Column operation is modified slightly: Two of the mixed copies of a byte are multiplied by u and u+1, which requires changing two of the three low order bits of the "multiplication by u" circuit. The circuit is still linear. C7...C0 = u * B7...B0 is originally implemented as C7 = B6, C6 = B5, C5 = B4, C4 = B3+B7, C3 = B2+B7, C2 = B1, C1 = B0+B7, C0 = B7. This is changed to C7 = B6, C6 = B5, C5 = B4, C4 = B3+B7, C3 = B2+B7, C2 = B1+B0, C1 = B0, C0 = B7. Only C1 and C2 are changed. Multiplication by u+1 is done by xoring B with C. Finally, the expanded key must be adjusted to match, by xoring in every byte's low order bit into the adjacent bit. It looks like this can be done by adjusting the actual key, and using the modified sbox. The round constants used for the key schedule stutters are also adjusted to match. Any nonsingular linear map can be built from similar single-bit-xor primitives. I'm not actually proposing this as an implementation optimization, but it provides an attacker with some interesting working material: He can do a series of manipulations to the sbox, looking for more favorable cryptographic properties such as single-bit-change bytes, or bit-swap bytes. He can even change to one of the other 29 eighth- degree irreducible finite-field defining polynomials, or switch the basis of the finite field from polynomial to normal. None of the other candidate ciphers has this linearity property. The property is a deliberate design decision. It would be easy to remove, say by combining the round keys and middletext using plain 32-bit addition instead of xoring. Rijndael's Sbox is Based on Finite Field Reciprocals Rijndael's algebraic sbox is a terrible idea. The sbox is defined as the finite field reciprocal, followed by an affine linear transformation. [Math majors, please forgive the recapitulation of finite fields.] Finite fields have automorphisms, they often have non-trivial subfields, and they have maps to other finite fields of the same degree. The automorphism x -> x^2 exists in any finite field of characteristic 2. In GF[256] the map is of order 8; x -> x^2 -> x^4 -> ... -> x^256 = x. If x is any finite field element, then the sum of all its morphic images is simple: Trace(x) = x + x^2 + x^4 + x^8 + x^16 + x^32 + x^64 + x^128 = 0 or 1. The automorphism commutes with polynomials and reciprocals, the inner function in the Rijndael sbox. So if a,b,c satisfy some equation such as a^3 = b^2 + b/c, and the automorphism maps a->A,b->B,c->C, then A,B,C will satisfy the same equation: A^3 = B^2 + B/C. (Constants in the field must also be mapped, but 0 and 1 always map to themselves.) The Rijndael reciprocal operator is just x->x^254, and is compatible with the automorphism. The affine transform following the inner map is NOT compatible with the morphism, but it is linear in the field basis, so there's some other matrix that's equivalent to the morphism applied to the sbox. We might try the approach used in the Square attack: Apply the morphism eight times to a plaintext byte, and examine the results. The morphs of x are {x,x^2,x^4,...,x^128}. Applying the first half of the sbox, the reciprocal operator, and summing the results gives 1/x + 1/x^2 + 1/x^4 + 1/x^8 + 1/x^16 + 1/x^32 + 1/x^64 + 1/x^128 = 0 or 1. The second part of the sbox, the affine transform will prevent these values from continuing to be a set of automorphic images, but will preserve the property that the sum is one of two values, 0 or 63. [The value x=0 may cause some of the equations with reciprocals to be invalid, but many encryptions will never use that sbox entry. A ten round encryption with a sixteen byte data block will touch the sbox 160 times, with 48% probability of touching the 0 entry.] GF[256] has unique subfields of order 16, 4, and 2 that are fixed by the morphism. Elements of GF[2] are fixed by the morphism; elements of GF[4] are fixed by any even power of the morphism; and elements of GF[16] are fixed by the fourth power of the morphism. For any x in the field, x + x^4 + x^16 + x^64 is in the GF[4] subfield, and = either 0, 1, u^7+u^5+u^4+u^3+u^2, or u^7+u^5+u^4+u^3+u^2+1. The same is of course true for 1/x + 1/x^4 + 1/x^16 + 1/x^64; after the affine map is applied, there will be only four possible values. Similarly, x+x^16 has one of the values in GF[16]. This subfield is (additively) generated by 1, u^3+u^2, u^6+u^4, and u^7+u^6+u^5. The reciprocal of a subfield member is of course in the subfield. Complementing the low-order bit of a byte keeps it in the same subfield, so its reciprocal remains in the subfield. Rijndael's Sbox has a Relatively Simple Algebraic Formula The Rijndael documentation notes that the full sbox map is equivalent to the algebraic expresion S(x) = 63 + 8f x^127 + b5 x^191 + 01 x^223 + f4 x^239 + 25 x^247 + f9 x^251 + 09 x^253 + 05 x^254 (Coefficients are hex representations of GF[256] field elements. Calculations are done in the field, so "+" is the xor of the elements.) A typical random sbox would have 250 terms instead of 9. Although S(x) looks daunting, it isn't quite as bad as it seems: If x is not 0, then x^255 = 1, so we can rewrite the right-hand-side as 8f b5 01 f4 25 f9 09 05 S(x) = 63 + ----- + ---- + ---- + ---- + --- + --- + --- + -- x^128 x^64 x^32 x^16 x^8 x^4 x^2 x Then the individual denominators are linear in x, allowing relatively simple rational expressions for S(a+b): 8f b5 05 S(a+b) = 63 + ------------- + ----------- + ... + ----- a^128 + b^128 a^64 + b^64 a + b and 8f 05 S(a+b+c) = 63 + --------------------- + ... + --------- a^128 + b^128 + c^128 a + b + c and 8f b5 01 05 S(a^2) = 63 + -- + ----- + ---- + ... + --- a a^128 a^64 a^2 and 8f + 25 b5 + f9 01 + 09 f4 + 05 S(a+a^16) = 63 + ----------- + ---------- + ---------- + -------- a^128 + a^8 a^64 + a^4 a^32 + a^2 a^16 + a The iteration of several rounds of the cipher will create more complex expressions, but random sboxes would have much more complex expressions. There is a natural tendency to regard these expressions as much too complex to solve, but we have seen no detailed analysis of the growth of expression size as a function of the number of rounds. If breaking ten round Rijndael-128 merely requires writing the meet-in-the-middle equation R5(plaintext,ExpandedKeyBeg) = R5inv(ciphertext,ExpandedKeyEnd) and substituting in known plaintext-ciphertext pairs reduces the two sides to polynomials with only a million terms, we have trouble. An attacker can collect two million P/C pairs and solve the equations as a large system of LINEAR equations. There may also be an advantage in using a normal basis representation for the field elements. A normal basis representation uses a field element v and its successive squares v^2, v^4, v^8, v^16, v^32, v^64, and v^128 as the basis instead of 1, u, u^2, u^3, u^4, u^5, u^6, u^7. We require Trace(v) = 1; for the Rijndael polynomial, this means v must have either u^5 xor u^7 as a component. A good choice for v is v = u^5; then the basis is u^5, u^10, u^20, u^40, u^80, u^160, u^320, and u^640. There's a linear transformation on the bits to convert between the field representations, so the "alternative implementation" offered above works. The advantage of NB representation is that squaring is a rotation of the bits. Suppose that [hgfedcba] is a field element, with each letter representing one bit: [hgfedcba]^2 = (h u^640 + g u^320 + ... + b u^10 + a u^5)^2 = h u^5 + g u^640 + f u^320 + ... + b u^20 + a u^10 = [gfedcbah] Reciprocals of rotated values are rotated by the same amount in the same direction, so in the equation for S(x) as a sum of fractions, the denominators will all be rotations of x, and all the reciprocals will be rotations of 1/x. It's possible that all these sbox speculations will lead to nothing, and that no attack on Rijndael can be built from these ideas. However, Rijndael is the only AES finalist that's subject to algebraic attack, and the risk can be completely removed by using a new sbox. There's no extra cost in either hardware or software, since no implementation calculates the sbox fom the definition; all use table lookup. There's even a potential benefit: the substituted sbox can be an involution, which will simplify decryption hardware and make decryption software smaller. There's no need for the Rijndael sbox to have the reciprocal property. As the authors themselves state, a random sbox with good crypto properies would suffice. Recommendations for Rijndael Add more rounds, unless other changes reduce the number of breakable rounds to five or fewer. Change Shift-Row to break up the bytes and spoil the Square attack, by rotating the rows a non-integral number of bytes. Replace the sbox with a non-algebraic random sbox having the usual properties of balance, diffusion, etc. This sbox can safely be an involution, which will simplify life for the hardware folks. Change the key schedule to be easily computable from either end. [Papers at FSE2000 and AES3 noted weaknesses in the Rijndael key schedule which should be addressed.] Exchange the roles of decryption and encryption, so that decryption is not slower than encryption. Sender: jworley@hpfctwc.fc.hp.com Date: Mon, 15 May 2000 15:12:56 -0600 From: John Worley Organization: Hewlett Packard Labs, Denver X-Mailer: Mozilla 4.7 [en] (X11; U; HP-UX B.10.20 9000/785) X-Accept-Language: en To: AESround2@nist.gov Cc: Tom Christian , Bill Worley , Ross Anderson , Dag Arne Osvik Subject: New Serpent Timings for IA-64 By carrying a duplicate of the low 32 bits of the data block in the high 32-bits, it is possible to greatly improve Serpent performance on the IA-64. The advantage is that the fixed rotations can now be accomplished in one cycle. Equally important is the contribution of Dag Arne Osvik's equations tailored to the IA-64 architecture. These provide 4- and 5-cycle software solutions for the s-boxes. This solution requires a doubled-size key table (1056 bytes), but the keying time decreased from 490 to 340 cycles, while the encryption time decreases from 565 cycles to 419. I think this should be considered more than acceptable software performance for almost any application. Regards, John Worley jworley@fc.hp.com From: "Mattias Lennartsson" To: Subject: AES Date: Mon, 15 May 2000 23:24:09 +0200 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 4.72.3110.5 X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 X-MIME-Autoconverted: from quoted-printable to 8bit by email.nist.gov id RAA08781 I think that the best selection for AES is the safest algorithm, so far I think that it's many that agrees. But witch is than the safest one. As I see it there are two big threats to new algorithms. Either a improvement of the cryptoanalytic methods used today or the discovery of a totoal different way of attacking block chiffers. So the chiffer should be a chiffer that stands greate aganst todays differential attack and also be safe against new ones. First we need a big security margin on the differentials, this could be found on either Serpent or Twofish. And if you add more ronds to Rijndael witch probably should hav had more ronds allready from the begining, a good security margin is found also here. But it should allso be safe against future attacks. I think that this is achived by a komplex algorithm structure. If you add several different and safe components it seemed resonible to me that it would stop a future attack better. If you use a small number of components and one or more of those component is found less effective it may crack the hole algorithm. But this is not hapening if the chiffer is more complex. So therefore i think that Twofish would be the best algorithm for AES. And I don't like the idea of selecting two algorithms for AES. It would just be to confusing, I think that selecting one algorithm will do just fine. What is hapening if two AES standards i selected and one is broken. Wouldn't this affect the trust of AES, how do you know witch of the AES you're program is using. I think that we should concentrate on finding the most securest one instead of argumenting. Mattias Lenartsson (Sweden) Date: Mon, 15 May 2000 16:34:42 -0600 From: "Ralph S. Hoefelmeyer" Subject: Twofish To: AESround2@nist.gov X-MIMEOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MSMail-priority: Normal Based on my analysis of the options, I support Twofish for AES. It is flexible enough to support the myriad platforms we are going to see in the future, from Java-enable cell phones and PDAs, to smart cards and tokens. It has a reasonable level of assurance of confidentiality for the things one would use it for, such as financial transactions. This is my opinion, not that of MCI WorldCom. Ralph S. Hoefelmeyer Senior Engineer Team Lead, Next Generation Network Security Services Date: Tue, 16 May 2000 02:31:16 +0200 (MET DST) From: Dag Arne Osvik To: AESround2@nist.gov I have some comments on two of the AES finalists Serpent - In "The AES second round Comments of the Rijndael", the Rijndael team claims that Serpent needs 80 bytes for encryption, even for 128 bit keys. Now consider the minimum RAM requirements of Serpent: - Text block, 16 bytes - Key setup state, 32 bytes (independent of key size) - Temporary storage, 1 byte (for s-boxes/rotations) - Loop counter, 1 byte The loop counter and temporary storage might be kept in registers where available. Total RAM requirement is thus 48-50 bytes. Note that this requires application of both forward and inverse s-boxes in the key schedule, increasing code size (inverse s-boxes are required). - S-boxes can exploit parallelism in processors, as demonstrated by my S-boxes optimized for IA-64 (3 cycles critical path, 4-5 cycles total). John Worley just reported timings using these. Other processors should see similar figures for the s-boxes, depending on their number of ALUs. Twofish - There is a tradeoff between key agility and encryption speed, i.e. if an implementation should be optimal for all numbers of blocks, it will have to choose in run time which key setup/encryption combo to use. And of course, all chosen combos must be implemented. - In "Comments on Twofish as an AES Candidate", the Twofish team claim that "Twofish far surpasses the other four finalists" in terms of security/performance ratio, "normalizing to the largest number of rounds cryptanalyzed". The NSA ASIC implementations indicated that Serpent was nearly 4 times faster than Twofish, and from the cryptanalysis I've seen so far, Serpent seems far more secure than Twofish. Also I expect S-box optimizations to benefit Serpent hardware implementations significantly. Regarding my personal preferences for the AES, here is my list: 1. Serpent 2. Rijndael (with extra rounds) 3. Twofish 4. RC6 5. MARS And choose only one. Regards, ------------------------------------------------------------------------ Dag Arne Osvik http://www.ii.uib.no/~osvik X-Lotus-FromDomain: CERTICOM From: "Don Johnson" To: AESround2@nist.gov Date: Tue, 16 May 2000 16:07:37 -0400 Subject: ANSI X9F1 vote on Future Resiliency NIST, I have just reviewed the AES round 2 notes/text comments (the big combined file). Early in the file I mention that I presented "Future Resiliency" to ANSI X9F1 and that they "voted for it" in some sense. For some reason or another, Roger Schlafly, who was not there, deemed it necessary to claim that this vote was meaningless. This was simply not true, so let me clarify. I presented the paper "Future Resiliency: A Possible New AES Criterion" to ANSI X9F1, which I had submitted to the first AES conference. The presentation took the better part of an hour, it was not a truncated summary presentation. After I was done, there was some discussion as to what to do, if anything, about the ideas in it. I suggested an official vote, as follows: A) NIST should incorporate the ideas of "Future Resiliency" in the AES criteria. This passed with a good majority, there were a few no votes. Allen Roginsky, IBM, later proposed another official vote, as follows: B) NIST should consider adding the ideas of "Future Resiliency" to the AES criteria. This passed with more yes votes, being stated in a weaker form. These were official ANSI X9F1 votes and were specifically based on the idea that multiple algorithms were a way to address as much as possible the potential for a disastrous crack in one algorithm. I wanted to let NIST know for the record how the ANSI X9F1 vote should be interpreted. Don Johnson 1 155