🚀 go-pugleaf

ahaley@eoe.co.uk (Andrew.) replies:

>It is now known that the S boxes in standard DES are about the best
>that can be done.  Biham and Shamir's article "Differential
>Cryptanalysis of the full DES" explains this in more detail.  As far
>as I can remember, the "perfect" S boxes have other weaknesses.

I've found "Differential Cryptanalysis of DES-like Cryptosystems" by
Biham and Shamir on page 2 of Crypto '90.  What they actually say is:

"the replacement of the order of the eight DES S boxes (without
changing their values) can make DES much weaker: DES with 16 rounds
with a particular replaced order is breakable in about 2^46 steps
[2^58 as is].  The replacement of the XOR operation by the more
complex addition operation makes this cryptosystem much weaker.  DES
with random S boxes is shown to be very easy to break.  Even a minimal
change of one entry in one of the DES S boxes can make DES easier to
break."

In Eurocrypt '91, Dawson and Tavares have an article "An expanded set
of S-box Design Criteria Based on Information Theory and its Relation
to Differential-Like Attacks".  What they open the article with is:

"Biham and Shamir ... showed that DES could be broken if poor S-boxes
were used.  Thge design of good S-boxes is therefore an important part
of designing a DES-like crytosystem.
     In this work we present an expanded set of design criteria for
creating good S-boxes based on information theoretic concepts and show 
that an S-Box that meets these criteria is immune to differential
cryptanalysis."

I don't see any incompatability here.  It is unlikely that Biham and
Shamir chose good s-boxes at random and also unlikely that minimal
changes to the s-boxes in even one entry would result in an ideal
result.

Thanks to those who sent e-mail addresses.  I'll try to get Webster's,
Adams', and Dawson's thesies' and attempt to coax out some perfect
s-boxes. I have to admit I still don't understand a few things.  Can
anyone explain the difference between nonlinearity, Strict Avalance
Criterion, and correlation immunity?  It all seems like the same thing
to me.

Patience, persistence, truth,         reality:       mgr@anhep2.hep.anl.gov
Dr. mike                                 UUCP:    uunet!pyramid!cdp!mrosing
IMI, P.O. BOX 2242, Darien IL 60559    bitnet:              mrosing@igc.org