Article: 76276 of sci.crypt
Path: ens.fr!jussieu.fr!ciril.fr!isdnet!news-ge.switch.ch!in2p3.fr!univ-lyon1.fr!unice.fr!news.cma.fr!news-sop.inria.fr!news-rocq.inria.fr!usenet
From: Robert Harley 
Newsgroups: sci.crypt
Subject: Re: Who will win in AES contest ??
Date: 26 Jan 1999 17:25:07 +0100
Organization: I.N.R.I.A Rocquencourt
Lines: 160
Message-ID: 
References: <36a77e8d.2733720@news.tpsa.pl> 
	<87d846nl9e.fsf@hedonism.demon.co.uk> <78h8db$ik7$1@nef.ens.fr>
	<78kbii$gkh$1@whisper.globalserve.net>
NNTP-Posting-Host: corton.inria.fr
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Newsreader: Gnus v5.3/Emacs 19.34
Xref: ens.fr sci.crypt:76276


Serge Vaudenay wrote:
>People says DFC has not enough rounds, which is why it is faster. Then
>increase it from 8 to 12 rounds, and it will be as fast as the popular
>ones!

jerome@mycpu.org () replied:
>i missed something... a dfc with 12 rounds is not faster on 64b cpu and
>looses its speed advantage. 


I think Serge's remark was somewhat tongue-in-cheek!  Twelve rounds
would probably be a bit excessive for DFC.


Presumably we want a code which is:

  1. Possible on the low end.

  2. Fast on the high end.

  3. SECURE!!!


1.  Low end.

Everybody seems to agree that on the low end are smart cards for which
we need something that can get by with at most a few hundred bytes of RAM.

Just a few messages ago, Paul Crowley ruled out DFC and others
claiming that they required "at least 195 bytes", whereas the DFC Web
page links to a several-month-old paper describing an implementation
in 100 bytes.  Being too hasty and getting facts wrong sure won't help
us make a good choice!

Note also that Gemplus (a major smart-card company) is involved in DFC
so it appears that those who know the low-end well think highly of
this particular candidate.


2.  High end.

Here there seems to be some disagreement.  Should the high end be the
latest x86 chip?  Or the latest Alpha?  Or some unknown processor that
will be popular in 2010?  The conclusions are quite different
depending on which you choose.

Many people have x86 machines, obviously, and NIST suggested testing
on a 200 Mhz Pentium Pro.  However some appear far too willing to
dismiss out-of-hand all but the very fastest on that particular chip
with the particular implementations they have at hand.

My machine is an Alpha (the outgoing 21164 generation) so for
me DFC is the fastest candidate.  Amongst the serious contenders it
is fastest by quite a bit.

My personal opinion on this is that more effort should go into
implementations on diverse types of processor.  Bruce has done a very
careful implementation on Pentium Pro, and even posted here recently
to announce shaving 2 cycles off per round, but what about Alpha?
Perhaps Twofish could be sped up there.  Likewise for other codes.

I've implemented DFC myself on Alpha but am incapable of doing a good
job on x86.  Some guys at ENS did an implementation that takes about
750 cycles.  I did one on ARM that takes about 750 cycles too, yet ARM
is a very simple in-order single-issue RISC chip.  Surely a Pentium
Pro could beat it easily!  I wouldn't be surprised if 20 or 200 cycles
could be knocked off by a top-notch x86 programmer.  Where's Terje
Mathisen when you need him?  =:-)



3.  Security.

Don't overlook that security is more important than anything else!
Imagine if some variant of DES had been chosen that was faster on the
chip-du-jour in 1975 but got broken in 1985?  The whole AES landscape
would be very different.

A few candidates are easily ruled out but it would be a mistake to
assume that the rest are all equal.


For now, the various AES teams are involved in guerilla warfare,
trying every avenue to criticize the others.  Read carefully and
separate the wheat from the chaff.  When Bruce Schneier and colleagues
comment on 32-bit performance they criticize DFC as "The modular
multiply does a nice job of diffusing bits, but hurts performance
significantly."  They're praising it with faint criticism!


At heart I'm a bit of a speed-demon but mostly a mathematician.  There
are some fast candidates, but that's not enough.  There's plenty of
advocacy going on, but much of it doesn't really matter.  There are
guys with good reputations involved.  I respect that.  But the
clincher is:

  WHAT CAN YOU PROVE?  WHAT IS HARD, COLD FACT?

  And what's just heuristics, conjectures and such like?


Heuristics and conjectures are important, especially in cryptography,
but pale in comparison to the others.  Take a step back from just DES
and look at what lies behind cryptographic methods that have stood out
since the seventies: you will surely have in mind things like
factoring, discrete logarithms, exponentiation, finite fields and so
on.  When mathematics is brought to bear it really does a good job.


I would argue that DES was the end of an era: an era when cryptography
meant pushing bits around in some complicated fashion, getting smart
people to try to crack the resulting code and declaring it safe when
they fail.  This process produced DES and DES succeeded.  But I think
there was a large amount of luck involved.

The filtering process is of course necessary but it is not sufficient.
Twenty to twenty-five years ago, cryptography came out into the open
and nothing has been done the same since, save doomed attempts like
Clipper, until now that is.  The AES process seems to be swamped by
candidates going back to the old way, submitted by people apparently
blinded by DES's lucky success.

If that's what is wanted then go with triple-DES!


Take a look at the serious candidates from a mathematical point of
view.  There are a lot of similarities: Feistel this, XOR that...
But one stands out.  One says: hey guys here's a proof that
such-and-such attack can't work, nor this other attack nor some entire
classes of attacks.  And they're not "straw-man" attacks that are
being held at bay either, they're genuinely useful against some other
codes.  You may have missed the crucial word so I'll repeat it: proof.


Now you may be wondering why I'm laying down a strong argument which
happens to favour DFC.  Maybe the designers are friends of mine?
No: I just met them for the first time a few days ago.  Maybe its some
primitive nationalism, after all I'm posting from France.  No: I'm Irish.

I'm defending DFC because it melds the best of the old DES era and the
new mathematical one; because it has gone through the AES process to
date with as much distinction as the other good candidates, withstood
attempts to break it, and because on top of that it is backed up by
guarantees, when all the others have to offer is rhetoric.


So forget all the business with "candidate A is bla% slower/faster than
candidate B on processor X, but on Y mumble mumble".


None are perfect.  But one comes with proof.  The others don't.

  WHAT ARE YOU PEOPLE THINKING?

  =:-)


Bye,
  Rob.