24 March 1999: See report on Day 2: http://jya.com/aes2-day2.htm

23 March 1999

    To: cryptography@C2.net
    From: Vin McLellan <vin@shore.net>
    Subject: Georgoudis on AES2, Day 1, Rome (FW)
    Cc: cypherpunks@algebra.com
    Date: Tue, 23 Mar 1999 03:56:53 -0500

            This is an intriguing first-person account of the first day of AES2,
    the Rome Conference on the candidates to replace DES as the Advance
    Encryption Algorithm (AES)that was posted to sci.crypt by Dianelos
    Georgoudis, one of the designers of FROG, one of the AES prospects. Full of
    interesting information and thought-provoking asides.  The NIST website
    offers most of the (often fascinating!) AES2 papers at:
    <http://csrc.ncsl.nist.gov/encryption/aes/round1/conf2/aes2conf.htm>.

          _Vin

    PS. Unfortunately, there doesn't seem to be any further info about Ron
    Rivest's RC6(a) cipher on NIST's AES2 website. According to Geogoudis,
    RC6(a) is apparently a variation on his RC6 block cipher, another AES
    candidate, that Rivest presented at the AES2 Conference.  RC6(a) uses a
    different key scheduler that requires only 25 bytes of RAM, but it is also
    reported to be twice as fast as RC6 in assembler, and five times as fast in
    C. There's nothing about RC6(a) on Rivest's home page at MIT or on the RSA
    website.

    -------------------------------------------------

    Subject:  Live from the Second AES Conference
    Date:  Tue, 23 Mar 1999 01:19:57 GMT
    From: dianelos@tecapro.com
    Organization: Deja News - The Leader in Internet Discussion
    Newsgroups:sci.crypt

        Here is my report on the first day of the AES2 in Rome. Lots of
        participants, 180+ people from (according to NIST) 23 countries.
        About half the speakers today were not native English speakers, so
        this is indeed an international process. 28 papers were submitted
        (all are at NIST's site: aes.nist.gov) and 21 will be presented
        here.

        First some general observations about today: A very full schedule
        with 13 presentations and a rump session with another 15 or so
        short themes, that was finally concluded at 9pm. Many surprises
        and, frankly, some confusion right now. Almost all candidates
        ciphers were stained one way or the other - and a surprising
        strong showing of Rijndael (in the negative sense that very little
        negative was said against it). Certainly many of the speakers were
        frankly biased, but this is normal in a competition. Please keep
        in mind that I am biased too. Here I express what I understood
        from the proceedings as well as my personal opinions, both of
        which may not be correct. Also, sometimes I only mention
        approximate numbers. If you are really interested, read the papers
        on NIST's site.

        In the morning we had 8 presentations with surveys of the ciphers
        - actually lots of measurements mainly about speed. Speed numbers
        can be bewildering because there are so many parameters beyond the
        cipher itself: hardware platform, OS, compiler, quality of
        implementation, memory/speed trade-offs, key scheduling versus
        encryption. Speed may be easy to measure, but I think its
        significance is overrated (the advance of hardware technology will
        double AES's effective speed every 18 months or so, and I don't
        believe that world wide speed requirements will grow that fast
        too). Even worse: different designers chose different margins of
        security and an evaluation process that is obsessed with speed
        would penalize those, who probably wisely, chose to be more
        conservative. Thus, Eli Biham proposed a normalization of the
        candidate algorithms depending on the number of rounds that are
        known not to be secure. This view has also its detractors.

        In the afternoon smart card implementations were discussed. First
        efficiency estimates (both speed and space) were shown. After that
        came three very interesting presentations about attacks against
        smart card implementations. These are real world, practical
        attacks. IBM's Pankaj Rohatgi explained how he got all 128 bits of
        a Twofish key after only 50 (that is 50 not 2^50) uses of a smart
        card!

        Now some more information about the presentations:

        First, NIST's Jim Foti explained that they did a lot of speed
        measurements on different platforms. On the reference platform the
        fastest algorithms were Crypton, Rijndael, RC6, MARS, Twofish, and
        E2. The algorithms with the fastest key scheduling are: Crypton,
        Magenta, Safer+, E2, RC6, Rijndael. Dead last, by three orders of
        magnitude, is Frog, which is my own candidate. (I wanted to have a
        complex scheduler and on my Pentium it used "only" one hundredth
        of a second, so I thought that was good enough!) There is much
        change in ranking depending on the survey of speed, but in general
        the "fast" algorithms are Crypton, Mars, RC6, Rijndael, Twofish
        and Mars.

        The next paper was by Brian Gladman, the Briton who singlehandedly
        coded in C all 15 algorithms based only on their description, but
        he was not present. His basic result is that for small, medium and
        large blocks RC6, Rijndael, Mars, Twofish and Crypton are the
        fastest.

        Then came Bruce Schneier's presentation about speed. Again Bruce's
        exposition was interesting and clear. He made a good point that
        only assembly code speeds should be compared because otherwise you
        measure a particular compiler's efficiency rather than the
        cipher's. This is true, but in a networked world pure Java is
        going to be used too as a platform independent solution. He
        mentioned that the CPU also affects relative speeds, especially
        with ciphers like RC6 and MARS that use data depending rotations
        and multiplications. (RC6 in particular took some beating for its
        relative inefficiency both with 8-bit smart cards and later,
        surprisingly, with next generation CPUs.) Bruce mentioned that 8
        bit processors with little RAM will stay with us forever, because
        they will be used more and more for embedded systems. Less
        convincingly, he claimed that also 32 bit processors will stay
        with us for a long time. I think the prevalent view is that in the
        future 64 bits CPUs and beyond will be prevalent for high-end
        personal applications. His final ranking: Twofish, Rijndael,
        Crypton, E2, Mars for Pentiums; Rijndael, Crypton, E2, RC6,
        Twofish for hashing.

        Then came SUN's Alan Folmsbee who compared ciphers from the Java
        perspective. He used two platforms: Ultrasparc and "MicroJava" a
        new processor that directly executes Java source code. He measured
        "excess avalanche", RAM size, ROM size and speed. Excess avalanche
        tries to measure how conservative the choice of number of rounds
        is. According to his particular weights (and at the very least he
        is considered impartial) the five best algorithms are: RC6, Mars,
        Safer+, Serpent and Crypton. Guess who number six is? Frog.
        Trouble is he did not even pretend to measure security as such and
        only used the avalanche criterion - which is not supposed to be
        synonymous with security. By the way, here Rijndael did not fare
        very well being one of the slower algorithms.

        Serve Vaudenay was another designer presenting a survey. His
        recommendation is Mars, RC6, Serpent, ... and DFC. He criticized
        NIST on the choice of ANSI-C for their reference platform. I tend
        to agree: assembler and then Java for interoperability probably
        makes more sense. His criteria were speed, transparency in the
        design of the S-boxes (with some criticism for Serpent in that
        respect) and simplicity. I liked his emphasis on simplicity in
        algorithm design. He stated that a complicated (but insecure)
        algorithm only increases the latency delay before somebody finds a
        practical attack. His last criterion was "state of the art
        research". HPC and Frog were deemed "empirical" with no reference
        to any research results and were un-ceremoniously thrown off board
        (I wonder what happened to Frog's splendid simplicity?) Deal and
        DFC were judged to be based on a theoretical design, everybody
        else on a mere heuristic design.

        Then came Craig Clapp (who I believe participates in sci.crypt)
        with a rather interesting paper on instruction level parallelism
        of the candidates. He tried to measure what would happen in highly
        parallel processors that are projected in the future. For this he
        actually used a compiler that produces code for hypothetical
        processors with between one and ten pipelines. As expected, with
        hypothetical processors that are similar to current designs RC6,
        Mars and Twofish came out best. With higher levels of parallelism
        though, Rijndael and Crypton were faster. By the way, in these
        measurements he used Biham's notion of ciphers with "normalized"
        security, i.e. sometimes less rounds than the standard
        implementation.

        After that, Eli Biham made his case for normalizing the algorithms
        to en equal level of security before making speed measurements. So
        he cut down the number of rounds to an "insecure" number depending
        either on their authors' estimates or on his own estimate - and
        then added two rounds. By "insecure" here is meant that an attack
        is known of roughly less complexity than exhaustive key search.
        Now, of course, this is a lower limit; nobody really knows at what
        number of rounds any of these ciphers become insecure in that
        sense. Even so it is a good method because none of the candidates
        should be allowed to be faster than that. If somebody finds a
        better attack, then this would move up the minimum number of
        rounds resulting in a slower cipher. Now, he was criticized for
        adding two rounds instead of increasing the number of rounds by a
        constant factor. Anyway, in his final analysis (surprise!) Serpent
        becomes the fastest normalized cipher. With all that, Eli Biham's
        experience in cryptography is really huge and his basic point is
        undoubtedly sound. I think it useful to copy here his estimates:

                          originally                                now
            Cipher     rounds   cycles    minimal secure rounds    cycles
            Serpent     32       1800             17                 956
            Mars        32       1600             20                1000
            Rijndael    10       1276              8                1021
            Twofish     16       1254             14                1097
            Crypton     12       1282             11                1175
            E2          12       1808             10                1507
            RC6         20       1436             21                1508
            CAST-256    48       2088             40                1740
            DES (with NIST API would be more or less here)
            Safer+       8       4424              7                3871
            DFC          8       5874              9                6608
            Deal         6       8950             10               14917
            LOKI97      16       6376             38               15143
            Magenta      6      23186             11               42508
            Frog         8       2182              ?
            HPC          8       2602              ?

        (He does not try to estimate Frog's and HPC's minimal secure
        rounds - a pity - but Wagner's paper on Frog estimates double the
        number of rounds, which would put me in the 10th place)

        Next, Jim Foti explained some preliminary results of NIST's round
        1 randomness testing. For that battery of tests he used NIST's own
        statistical tools, Crypt-XB (which I had never heard before) and
        Diehard. In general everybody made this grade, even though they
        were some quirks with RC6 and HPC that are interpreted as
        statistical illusions while more testing is being done.

        Next, thankfully, came lunch. One amazing piece of information I
        picked at the table (while eating pasta al-dente and a literally
        bleeding piece of meat). As it happens, I sat at the table with a
        guy from the Federal Reserve. So I asked him if it was true that
        every day more than a hundred billion dollars is transmitted by
        wire. I explained that I had read this somewhere but that it
        seemed an incredible amount. Well, he answered that every day more
        than three trillion dollars are transferred by electronic means -
        in other words, every five days an amount compared to USA's one
        year economic output is translated into electrons.

        After lunch, Prof. Koeune from Belgium, also a sometime
        participant in sci.crypt, presented a paper on the implementation
        of several AES candidates on smart cards. He chose two instances:
        the low cost, 8-bit Intel 8051 and the advanced, 32-bit ARM with
        1kB of RAM. The approximate results are as follows:

                             8051    ARM
            Cipher   RAM     cycles  cycles
            E2       344      9K      2K
            RC6      205     14K      1K
            Rijndael  49      4K      2K
            Twofish   49      ?      10K

        For more and up to date information visit the page of cEASer
        project: http://www.dice.ucl.ac.be/crypto/CAESAR/caesar.html

        Geoffrey Keating presented a similar paper for the Motorola 6805,
        also a 8-bit CPU. Best algorithms: Rijndael, Twofish, Crypton and
        RC6. RC6 does need a lot of RAM (170-200 bytes) and later in the
        evening River [ed- Rivest?] presented RC6a with a different key
        scheduler that requires only 25 bytes of RAM and also is twice as
        fast in assembler and five times as fast in C - Rivest's middle
        name of course is Merlin).

        Then came three presentations about attacks against smart cards,
        no doubt orchestrated by NIST so that each paper made an even more
        powerful impression than the one before.

        The first paper was presented by Adi Shamir. I don't know whether
        Shamir is a teacher, but if he is then he must be a very good one
        indeed. First he explained about Paul Kocher's power attacks
        against smart cards (explained in Kocher's home page
        www.cryptography.com). The basic idea is to observe how much power
        a smart card consumes while executing a cipher (this can be done
        down to the level of microcode!). So, every instruction has a
        footprint and also the "Hamming weight" of the data processed
        (i.e. the number of bits with value 1) affects the power
        consumption as you need more power to charge up a register or
        memory bit to one than to flush it down. So, if you write a value
        with a lot of ones you will require more power. This attack, by
        the way, is a noninvading attack. Say you use a smart card and its
        reader has been doctored by an attacker and transmits details
        about the power consumption. Now Shamir showed that it is not
        necessary to have known texts encrypted. By using data from many
        different encryptions (different data but with the same key) and
        comparing their power graphs you will find that there are places
        where the power consumption strongly correlates. These are the
        times when the cipher is doing work that is not dependent on the
        variable data streams - i.e. when the cipher is doing its key
        scheduling. The technique explained is slightly more complex, but
        the point made was that DES could easily (actually especially
        easily) be broken in this way. On the other hand, Skipjack, a
        modern cipher produced by the US government, would be especially
        hard to attack in this way.

        Next, Joan Daemen, one of the authors of Rijndael, presented
        another comparative study about attacks against smart cards. He
        differentiated between timing attacks (useful mainly against older
        implementations of public key smart cards), power analysis
        attacks, and Differential Power Analysis (DPA) attacks. The latter
        is based on the fact that for some instructions the average power
        consumption correlates with the value of one input bit. As
        possible defense mechanisms he mentioned artificially produced
        noise but this can be cancelled out using a larger sample of
        cases. Another possibility is "balancing", an expensive
        proposition where, for example, you use 4 bit arithmetic on an 8
        bit smart card, taking care that the other 4 bits are always the
        complement of the "true" 4 bits, i.e. maintaining a constant
        Hamming weight. According to his analysis the algorithms which are
        easiest to protect against such attacks are Crypton, DEAL,
        Magenta, Rijndael and Serpent. The worse would be CAST-256, DFC,
        E2, HPC, Mars and RC6. His conclusion was that these kind of
        implementation attacks are really much more relevant than the
        academic attacks often discussed, because they can be implemented
        in practice and do some real harm.

        This point was made dramatically clear by the next speaker, IBM's
        Pankaj Rohatgi, who actually implemented the Twofish 6805
        reference code on a ST16 smart card and was able to recover the
        full 128-bit secret key using only about 50 independent block
        encryptions. He showed how noise can be cancelled out in these
        attacks and how he guessed the bits of the whitening. Whitening
        XORs data bits with constant key bits, ie: D <- D xor K. Using DPA
        it can be found out if D retains its value (in which case K=0) or
        is inverted (in which case K=1). In this way all of the whitening
        keys' bits can be found. In the case of Twofish the recovery of
        the whitening key allows the definition of a small number (10^6)
        of candidate master keys, from which the correct key can be
        derived. He surveyed all 15 candidates declaring them all unfit.
        The easiest to attack were judged to be Crypton, Deal, Loki-97,
        Magenta, Rijndael, Safer+, Serpent and Twofish, where DPA needs to
        be done only on very few rounds. Slightly harder would be ciphers
        like CAST-256, DFC, E2, Mars and RC6. Hardest to attack would be
        Frog and HPC, but only because they employ large key dependent
        tables - which make them more difficult to implement in smart
        cards in the first place. The moral here may be that availability
        of more RAM can make a smart cart more secure. He mentioned some
        possible defenses that do not work: adding noise or reordering the
        sequence of operations. He made clear that even balancing would
        not work, because this by definition is a technique where two
        physically separate parts of hardware are used; these parts can
        never be identical, so a correlation of bit values can always be
        determined. He rather cryptically mentioned that secret sharing
        techniques where one bit is split in several values might have an
        application here. I asked him whether a capacitor build in the
        smart card and powerful enough to charge several instructions
        wouldn't effectively hide the detailed timing of the power
        consumption. He said that a capacitor can be easily disabled, but
        that this defense might work in an noninvading threat model (this
        is the most dangerous kind where a smart-card's key can be stolen
        while the user is using the card in the normal manner).

        After that came the rump session. A few highlights:

        Doug Whiting described some efficiency estimates on Merced
        (supposedly a secret future Intel CPU). Here are the results:

            cipher      Pentium II        Merced
            RC6            250             620
            Rijndael       283             170
            Serpent        900             800
            Twofish        258             230

        RC6 (as mentioned before) actually seems to get worse. The same is
        estimated will happen with Mars too.

        Takeshi Shimoyama claimed that some S-boxes of Serpent were not
        secure against high-order differential cryptanalysis. His
        presentation was laced with a lot of jokes and laughter and I
        cannot judge how serious (if at all) this a problem is for
        Serpent.

        David Wagner showed that there is a large set of equivalent keys
        in HPC that can be found just by flipping 1 bit of the master key
        and then keep trying for about 500 times. This would mean that HPC
        is not a good algorithm for implementing hashes. Wagner, by the
        way, will present tomorrow the paper about weak keys in Frog.

        Rivest presented RC6a with the much more efficient key scheduler
        variant (see above). He claimed that 8-bit chips "will go away",
        but nobody really believed that he really believed it.

        Bruce Schneier made a case against the idea of choosing not one
        but several "approved" AES algorithms. He used the argument that
        cryptanalytic efforts should not be divided between several
        ciphers because then each individual cipher would be less trusted.
        I didn't quite understand this argument: all ciphers that make it
        to the second round will be strongly analyzed anyway no matter
        whether only one or more than one is finally declared the winner.
        He mentioned that if they were two AES ciphers and you used one
        bit of the key to chose one of them, then half the time you would
        use a less powerful cipher. But one could also say that half the
        time one would use the more powerful cipher. (Say, after the
        second round cipher A is deemed the strongest followed by cipher
        B. Now suppose NIST chooses both as a standard and somebody in the
        future finds an attack that works better against A than against B,
        which would make B stronger than A). Also if there should be a
        catastrophic failure with cipher A (a non zero probability),
        cipher B could be easily substituted just by fixing this one bit
        in the key. He argued that multiple standard ciphers would be much
        more expensive to implement. This is probably true but I think
        this measurable cost should be balanced against the risk (a
        non-zero probability) that a single AES may fail catastrophically
        some time in the future when it is already broadly used. If that
        should happen the cost would be extremely large. The possibility
        of a catastrophic failure is really what should keep the NIST
        people awake at night.

        One wonders what is so wrong in declaring several good algorithms
        for specialized environments. Actually, after today's presentation

        about attacks against smart cards, somebody mentioned that a smart
        card is a sufficiently different environment to justify a
        specialized cipher. There is a large class of applications where
        ciphers are implemented in software, where speed is not important,
        and where security is important. In these cases one might choose
        to combine several algorithms in series at no particular additional
        cost.

        So who will make it to the second round? No idea.

    -----------== Posted via Deja News, The Discussion Network ==----------

    http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
    -----
          Vin McLellan + The Privacy Guild + <vin@shore.net>
      53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
                             -- <@><@> --