🚀 go-pugleaf

mrosing@igc.org (Mike Rosing) writes:
: 
: Howdy,
: 	I'm totally new to this topic so please bear with me.  I've
: read several Springer-Verlag "lecture notes in computer science"
: including "Modern Cryptology A Tutorial" and a few of the Crypto' and
: Eurocrypt articles.  Crypto '89 has an article called "Good S-Boxes
: are Easy to Find" by C. Adams and S. Tavares.  I'd like to improve the
: DES routine I've got working already by substituting the s-boxes with
: some of the ideas described in this article.
: 
: 	The article states that there are 60 s-boxes which meet
: the criteria of 1) bijection, 2) nonlinearity, 3) strict avalanche,
: and 4) independance of output bits.  Only 3 of these are listed in
: the article and I don't have access to the J. of Cryptology to
: see if the authors actually got to publish a more detailed description.
: Does anyone have a listing of these 60 "perfect" s-boxes?

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.

: 	Also, the article states "A simple way to extend DES in
: the short term might be to standardize a list of good s-boxes and have
: as part of the key the choice of s-boxes to use."  Has anyone done
: this and would you mind telling me how you used the key to pick
: the s-boxes?

This is a bad idea; see the above article.  In general, DES is very
well designed.  Any minor perturbation, even reordering the S-boxes
without changing them in any way, greatly weakens DES.  It's worth
looking at more recent CRYPTO and EUROCRYPT proceedings, as there is
much more on this subject.

: 	Finally, does anyone know how to get email to the above
: authors?  They are listed as being from Queen's University in
: Kingston Ontario.  Thanks for any replies!
: 
: 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

Andrew.

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