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:

<http://csrc.ncsl.nist.gov/encryption/aes/round1/conf2/aes2conf.htm>.

        _Vin

----------

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
                         -- <@><@> --