24 March 1999. Thanks to Dianelos, Vin and Dan.

See report of Day 1: http://jya.com/aes2-day1.htm

        This is a second bulletin from the Rome AES2 conference, 
as posted to the sci.crypt newsgroup by the perceptive Dianelos
Georgoudis, one of the designers of FROG, an AES candidate.
The NIST website offers most of the AES2 papers at:
Subject: Re: Live from the Second AES Conference Date:  Wed, 24 Mar 1999 14:18:38 GMT From: dianelos@tecapro.com Newsgroups: sci.crypt     Here is my report on the second and last day of AES2.     First came five papers with analysis of several algorithms (in     general it was felt that the analytic results of the first round     were relatively few):     Sean Murphy described properties of Twofish pertaining to its key     schedule. First it was shown that the whitening keys (XORed with     the data before and after the main cipher) are not uniformly     distributed, i.e. take not all possible values. In a similar vain,     each 8-byte round subkey also cannot take all possible values.     Ideally, of course, all key material within a cipher should be as     close to random as possible, otherwise an attacker gains some     predictive power. Later in the afternoon workers from the Twofish     team explained exactly how much entropy was lost: the whitening     key has 117 bits of entropy (instead of the optimal 128) and each     round key has 63.2 bits of entropy (instead of 64). They claimed     this is not a useful cryptanalytic property which does seems     reasonable.     John Kelsey, also from the Twofish design team, described a     weakness in Safer+'s key schedule (256 bit key variant) that led     to a possible attack requiring 2^200 encryptions - clearly a very     theoretical attack. He finished suggesting an improvement to the     cipher's key schedule. Later in the afternoon, Safer+'s designer,     James Massey, conceded that his main attention was invested in the     128 bit variant and described a similar fix.     Vincent Rijmen, one of Rijndael's designers, explained the attack     on LOKI97, the first serious published attack against an AES     candidate: a differential attack that needs 2^56 chosen plaintexts     and a lineal attack that need 2^56 known plaintexts but works only     on 2^(-25) of the keys.     Then came David Wagner's exposition of the attack on Frog. David,     by the way is still only a student in California. I liked his     description of Frog as a cipher where the "wires" are parametrized     to the key. This means that Frog looks like a large collection of     individual ciphers with different internal wiring. The basic point     is that the attacker can search and choose the instances where     this wiring defines a weaker cipher, and then mount an attack on     the weak key that gave rise to this configuration. (For those     familiar with Frog the weak wiring happens when the bombpermu     pointer addresses the previous byte.) It turns out that 2^(-33) of     the keys are now weak and that in these cases the key can be     broken with 2^58 chosen plaintexts. The decryption function of     Frog has much slower diffusion (something first noticed by John     Savard, a frequent participant in sci.crypt) which allows for a     more successful attack that requires 2^36 chosen ciphertexts and     works for 2^(-29.3) of the keyspace. A linear attack on Frog was     also described.     Frog-like ciphers do have this kind of problem: by putting some or     most of the functional definition of the cipher within the key,     the possibility exists that some of these functions will be weak.     I suppose there are ways to fix Frog in order to strengthen it     against the differential and lineal characteristics discovered by     Wagner and achieve a much lower or zero number of weak keys,     trivially: suppress the weak wiring configurations. (I did ask him     to propose a fix but he was not forthcoming - I wonder whether     using ADDs instead of XORs for diffusion would cut it). The really     interesting question though is to find out if a generalized     version of Frog that just follows its design principles to a     higher degree would increase or decrease the frequency of Wagner     weak keys. The whole idea in Frog is to do nothing designed     specifically as a defense against a particular attack. So if     Generalized Frog turns out to be weaker against Wagner's attack     then it is bad news for the basic idea. But, if it turns out that     "purer" (even less structured) forms of Frog are more resistant,     then confidence in Frog's design principle will increase. So     Wagner's attack can be used as a platform to evaluate the design     methodology, something even more important than the candidate     cipher itself.     Finally Eli Biham described the attack against Magenta. The attack     works with 2^64 chosen plaintexts and 2^64 complexity or 2^33     known plaintexts but 2^97 complexity. In the afternoon, Magenta's     Klaus Huber gave a very short rebuttal, explaining that this     weakness can easily be fixed and that Magenta does have some     interesting theoretical and implementational properties. In     software it is relatively slow though.     Next came a series of theoretical papers about various candidates:     Jaques Stern of DFC described an update of the cipher that is     faster and can be made scalable to allow for different block sizes     (a useful property of several other candidates). The DFC team     worked really hard to have decorrelation theory serve as the     theoretical underpinning of their cipher. (Also it seems that     decorrelation modules can be inserted into other ciphers such as     E2.) He explained that the proofs apply to an idealized version of     the cipher that DFCs approximates. By the way, later this     afternoon somebody asked whether "proofs" are really important in     cipher design. Bruce Schneier's reasonable comment was that any     proven property in a cipher increases the quality of its analysis     and hence its security. He also made clear that proofs discuss a     specific thread model and that general proofs for all possible     threats are not really possible. Well, I tried to go the other way     and asked Jaques whether DFC's designers had put any thought in     defending against unknown attacks (the proofs on DFC pertain only     to first order differential attacks). He clearly disliked the     question and his answer was somehow patronizing in the sense that     it is meaningless to discuss unknowns. There was laughter around     the room but I really think this is no laughing matter: Every ten     years or so a new powerful cryptanalytic technique is discovered.     In AES's life span maybe five new types of attack will be     published. Only in the last year unforeseen and extremely powerful     attacks against smart cards were demonstrated. Also, several     ciphers including Mars, E2 and Twofish (not to mention Frog) did     include in their documentation at least some reasoning about their     strength against unknown attacks. I understand that mathematicians     prefer to work with well defined problems and consider vague     problems as problems not worth thinking about, but ciphers are     machines to be used in the real world where the givens are not     always clear-cut.     Kazukuni Kobara next discussed a very theoretical paper on     pseudorandomness. After her talk somebody had to ask her how this     work relates to E2, to which she answered, as if just remembering,     that E2 does indeed achieve optimal pseudorandomness after two     rounds. It is interesting to observe how cultural characteristics     have an impact in this international process. The designers of the     Asian candidates (E2 and Crypton) are really far too modest and     this, I think, hurts their chances. American designers, of course,     are the most crass, and I think this is a winning strategy.     Next, James Massey explained why Safer+ diffusion is optimal.     Safer+ is a mathematician's kind of cipher and its weakness were     discovered in the key scheduler, precisely the place where math     does not help a lot.     RSA's Scott Contini quantified the differential properties of     data-depending rotations followed by multiplications as used in     MARS and RC6 - a technique that appears to be powerful and is also     under the cloud of a RSA patent. In general, I am in favor of     patents but not in favor of being able to patent such broad and     obvious ideas as using data-depending rotations in ciphers; after     all this is an available machine instruction. My very first cipher     design done several years ago, GodSave, uses data-depending     rotations like crazy and I had no idea that RSA was using them     too.     Finally, Dough Whiting described some new results on Twofish. Even     better speeds and better implementation flexibility (even though     it appears that the very fastest code is self-modifying - this may     look "unpure" to some but I think that it is a valid optimization     technique). Even more carefully crafted cryptanalytic results were     given.     Next came lunch. Today I sat with a guy who works with a large     organization that builds encryption hardware for the government!     Sorry, not NSA; I never met any of these guys even though they     were there - they appeared to be playing No Such Agency. I     certainly would have enjoyed talking to somebody from the NSA. No,     my table companion worked for a private company and the government     in question is UK's. I asked him why government ciphers are still     implemented in hardware and not in software working in dedicated     one chip computers. Apparently speed is not the answer - very high     security communication is really low bandwidth. I didn't find his     answers very convincing: He said that an alpha particle from space     can knock out a transistor in the chip and modify the cipher. Then     again it is a trivial matter to have not one but many CPUs     computing the same cipher in parallel to account for such type of     events. Also he claimed that software correctness was more costly     to verify than a hardware design. Anyhow, I suspect that for all     the mathematical image of cryptography, tradition and the inertia     of ideas does play an important role.     Later, I happened to speak to one of the top cryptographers of the     world and I asked him one of my favourite questions: First assume     two very good ciphers A and B, say two of the better AES     candidates. If your life depended on it and you had to choose     between A.A (doubling A's rounds), B.B (doubling B's rounds) or     A.B (sequentially executing both ciphers), what would you do? The     standard answer is that mixing ciphers is a bad idea because the     resulting cipher could be weaker than each individual one, that     the resulting cipher would be a completely new cipher which would     require fresh analysis which is the only way to gain trust, etc.     Well my companion's answer was "A.B", and he gave precisely the     reasons I expected: a future attack that may work against A could     very well stop at B's gate.     After lunch came a long session with open discussions. Supposedly     candidates would slug it out between themselves while seated in     front of the audience - you know the Christians and lions metaphor     that NIST's Miles had used to explain the choice of Rome for the     second AES conference. Well, to play it safe I sat at the very     back of the room close to the exit. Thankfully, nothing dramatic     happened. A few designers talked for a few minutes defending their     ciphers and that was it. By the way all candidate ciphers, with     the exception of HPC and LOKI97, were represented at this     conference.     Then came a long discussion about intellectual rights (IP) issues.     Miles really seemed unhappy about the whole situation. Here is the     problem: All candidates have renounced their property rights on     their own ciphers if they are declared winners. This was a     condition to enter the competition. So far so good, but even in     the first conference the issue was raised about what would happen     if a looser candidate claimed IP rights on some parts of the     winner algorithm: this certainly could result in a very messy     litigious situation that would defeat one of the basic ideas     behind the AES: that it should be a global royalty-free algorithm.     A few weeks back NIST sent to all candidates an informal question     trying to measure how they stood in this matter. Several of them     (CAST-256, Crypton, Deal, Frog, LOKI97, Rijndael, Serpent and     Twofish) gave a clear positive answer. The others (DFC, E2, HPC,     Magenta, MARS, RC6 and Safer) were not that forthcoming. The     situation is not as bad as it looks. For example, one of the     favorite ciphers, RC6, in only asking for some kind of honorific     recognition if some of its IP is used by the AES winner. Another     favorite, IBM's MARS, had a more convoluted position. They     claimed the NIST's clarification question was not very clear     itself and that it literally said something very different -     therefore their convoluted answer which striked me also as somehow     ambiguous. Overall, my feeling is that NIST will apply gentle arm     twisting behind the scenes before announcing the finalists for the     second round and that it will succeed in getting all the important     designers to agree to play it clean.     After that a lively discussion followed with the participation of     many people from the audience. The main themes:     Smart cards. Several people expressed that the importance that was     given to implementation issues of the AES on a low end smart card     was not reasonable. The standard argument in favor of very tight     implementations on smart cards was that there are cases where     millions of smart cards are needed where even a small price     difference has a large impact. Against that, somebody from the     audience presented the following strong argument: cases where the     AES is going to be used in a smart card are cases where you want     to protect information that is valuable - otherwise you don't     really need a 128 bit key and can use any of well known medium     range ciphers. If you are protecting information that is valuable,     then spending one dollar more for each card is a reasonable     investment. Miles explained that originally NIST had not intended     to require implementations on 8-bit platforms but that the initial     comments supplied by the public were strongly in favor that NIST     should add smart card flexibility to the AES. So, even though it     will be judged positively if a candidate does operate efficiently     on a smart card, he felt that the whole issue was becoming     overrated. My feeling is that the PDA attacks against smart cards     have really confused the situation here - possibly security for     smart cards will have to follow completely novel design paradigms,     maybe even hardware designs. (At the coffee break I approached a     small group of people that included Adi Shamir who had talked     about power analysis attacks the previous day. The normal     implementation of Generalized Frog takes the secret key and     compiles it to actual code that can then be loaded in a smart     card. So I asked Adi if a situation where each smart card actually     holds a different program processing only data would be an     improvement. As expected the answer is no, because one of the     easiest things to read from a card is the "signature" of the     instructions being executed. My other idea, to have a card hold a     string of keys that will be used only once might work with some     applications, such as high security home banking. On the whole     though the situation with smart cards is considered hopeless).     Another big theme was to have not one but several candidates     declared AES. The previous day Miles had explained the main ideas     of Don Johnson's paper (who unfortunately was not present) and     Bruce Schneier had presented a passionate case in favor of a     unique AES. Today several participants spoke in favor of more than     one AES (the main arguments were insurance against a weakness     being found in the main winner and allowing for more specialized     ciphers); I think these arguments won the day. Miles said that     NIST would very carefully consider the advantages that more than     one winner would represent. Having more than one NIST approved     cipher does have another advantage nobody mentioned: it would     quiet those paranoid minds that might suspect that the AES winner     could be a NSA implanted mole.     The question of number of rounds came up. NIST said it would     consider a cipher secure if it could not be broken with 2^64     chosen texts. A thoughtful counter-argument was that different     amounts of analysis result in different apparent minimal secure     rounds. For example, complicated ciphers have an advantage here,     because simpler ciphers allow for more elegant analysis and     therefore attract more cryptanalysis. This gave me the idea that     instead of trying to normalize security (a difficult proposition)     and then comparing speeds, a better methodology could be to     normalize speed (best assembly implementation on one or two     reference platforms) and then compare security. After all,     optimized speed on a given platform gives a good idea about an     algorithm's workload. Also, speed could be normalized at such a     high level that ALL competing ciphers would be pushed into     insecurity which would then allow more or less reasonable     quantitative comparisons to be made about their relative     "structural" strenght. It is clearly too late to use this     methodology in the first round but maybe it could be used in the     second. I feel like sending NIST an official comment in this     sense. I wonder what the reader thinks about this?     At the very end of the session Miles explained what the future of     the AES competition looks like:     Comment period for Round I ends April 15. So if the reader wants     to influence the process, the time to send in a comment is now.     The email address for that is aesfirstround@nist.gov     April 19, the official comments will be published.     May 15, NIST will accept "tweaks" on the algorithms. NIST is the     final judge about what qualifies for a tweak.     Mid-summer, probably by July 99 the finalists will be announced     (probably no more than five but possibly more). At the same time     the justification will be given for their choice. In this point of     time, Round 2 begins.     Now the finalists may submit new optimized code for any platforms     the feel like.     CD-ROMs will be distributed 2-3 months after the start of Round 2     with the new code and most relevant information about the AES     process.     Miles expressed the hope that in Round 2 more serious     cryptanalytic work will be presented.     Efficiency will now be tested also for the 192 and 256 bit     variants.     Hardware performance estimation for all finalists will by supplied     by NSA.     IP issues will be clarified.     January 15, 2000 is closing day for presenting papers for AES3.     Week of April 10, 2000, AES3 will be held in New York.     May 15, 2000 comment period of Round 2 closes.     Approximately August 2000 the winner(s) are announced. The "(s)"     was on NIST's slide.     So who will the winner(s) be? No idea. Many people expressed the     opinion that this may indeed not be a fully technical choice. For     example, it is difficult to imagine the main AES chosen by NIST     for the US government could be a foreign cipher. (By the way, this     makes another point in favor of more than one winner. Jaques Stern     did mention something rather cryptical about a possible European     cipher competition.)     Who will make to the second round? I do feel there is some general     consensus. Here are my choices:        RC6 and MARS will make it for their pedigree not to mention the        fact that they are fine ciphers with probably a lot of work        invested in them.        Rijndael should make on merit alone.     After that, things become somehow less clear.        Serpent is a favorite. It is considered a very conservative        design and everybody agrees that security is indeed the        preeminent concern. Its designers have some of the sharpest        minds in the field and I think NIST will choose Serpent just        for keeping Shamir and Biham in the competition, not to mention        motivate them to attack everybody else.        Twofish is all over the place; it would be cruel to kill it off        so soon. Also it is a very valiant effort and certainly it is a        fine cipher. Extracting the full key out a smart card with        Twofish is widely considered an implementation issue rather        than a weakness of the cipher itself. If you really want to be        logical here, this makes no sense. On the other hand if you        would kick Twofish out for this reason alone then there would a        blood bath with most of the well considered candidates being        thrown overboard too. Twofish does have some good pedigree (it        came out of Blowfish), is fast and flexible on many platforms        and appears to be strong (results to date are not really        significant).        Finally, as a nod to Asia, I think NIST will pick E2 too. It is        certainly a very fine cipher considering its analysis, its        theoretical underpinning and its speed. The Japanese presenters        are probably the most sympathetic and choosing E2 would include        some ladies in the finalist makeup. Also nobody wants to miss        the nice accents.     So here is my guess: MARS, RC6, Serpent and Twofish from the US,     Rijndael from the EU and E2 from Japan. -30- -------------------------- <First Response on sci.crypt> Subject: Re: Live from the Second AES Conference Date: 24 Mar 1999 16:14:17 +0000 From:  Alan Braggins <armb@ncipher.com> Organization: nCipher Corporation Newsgroups:sci.crypt dianelos@tecapro.com writes: >     it appears that the very fastest code is self-modifying - this may >     look "unpure" to some but I think that it is a valid optimization >     technique). [...] >     improvement. As expected the answer is no, because one of the >     easiest things to read from a card is the "signature" of the >     instructions being executed. Any ideas whether self-modifying code would make reading instruction signatures easier or more difficult? -----       Vin McLellan + The Privacy Guild + <vin@shore.net>   53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548                          -- <@><@> --