Subject: Re: PGP, the end is near?

From: [email-masked] (Andrew Haley)
Date: 21 Apr 93 16:36:42 GMT

Vesselin Bontchev ([email-masked]) wrote:
: [email-masked] (Uri Blumenthal) writes:

: > Well, it's certainly well known HOW the S-boxes were designed.
: > It was in the open from the beginning. What's still hidden is 
: > WHY they were designed this way...

: Well, maybe that's a quirk in my English, but I meant that it is known
: why probably they have been designed this way (to withstand
: differential cryptanalysis), but it is not known how they have been
: designed (i.e., what criteria exactly have been used).

In the interests of accurate information, I repeat the following,
which has been transmitted on the net several times before.  This is
about the best information you will get about the design of the DES:

: From: [email-masked] (Markus Kempf [Physik])
: Newsgroups: sci.crypt
: Subject: DES designed to withstand differential cryptanalysis
: Summary: It was known in 1974
: Keywords: DES, cryptanalysis
: Message-ID: <[email-masked]>
: Date: 23 Mar 92 17:13:11 GMT
: Organization: University of Kaiserslautern, Germany
: Lines: 69
: 
: The following statement appeared in an IBM Internal newsgroup (CRYPTAN FORUM)
: and is reproduced here with the approval of the author.
: -----------------------------------------------------------------------------
: 
: Subject: DES and differential cryptanalysis
: 
: We have kept quiet about the following for 18 years,
: and decided it's time to break the silence.
: 
: We (IBM crypto group) knew about differential cryptanalysis in 1974.
: This is why DES stood up to this line of attack; we designed the
: S-boxes and the permutation in such a way as to defeat it.
: 
: (The following assumes some knowledge of DES and the Biham-Shamir
: attack. "delta" is the difference between two intermediate messages.)
: 
: The fact that a 1-bit input delta leads to at least a 2-bit output
: delta (and that an input delta of 001100 also leads to at least a
: 2-bit output delta) helps to insure that any pattern is going to
: involve a large number of S-boxes over the course of 16 rounds.  The
: fact that an input delta of 11xx00 (xx are "don't care") must lead to
: a nonzero output delta, insures that any input delta for the entire
: round which can lead to an output delta of 0 for the whole round, must
: involve at least three S-boxes.  Couple this with the demand that any
: nonzero input delta to a single S-box gives rise to a particular
: output delta with probability at most 1/4, and with somewhat reduced
: probabilities for the deltas that can give rise to 3-box attacks such
: as '19600000', and you have a defense against differential
: cryptanalysis.
: 
: During the summer of 1974 we kept coming up with different classes
: of patterns that might be used against the DES (whose design was
: still fluid at that point), and part of my job (I was working here
: that summer) was in designing criteria for the S-boxes and the
: permutation that would insure that no such pattern could have too
: large a probability of success.
: 
: By contrast, the designers of FEAL obviously did not know about
: this class of attacks.  It is a pity that the FEAL fell prey to
: these attacks, because it apparently acted as a catalyst for the
: rediscovery of the attacks by the outside world.
: 
: I don't recall (and the documentation that survives from that era
: doesn't help) whether at that time we knew the trick of sending a
: block of messages to get past the first round.  We certainly knew
: it later, and were applying it (privately) to FEAL and a couple of
: others.
: 
: My contention is that, even though (2^47) < (2^56), still
: (2^47 chosen plaintext) is *more* than (2^56 on my own machine),
: and (2^47 chosen plaintext) is not a practical threat.
: I say this not to belittle the Biham-Shamir work (which was very well
: executed) but to assert that what we have created (DES) is still viable.
: 
: We kept quiet about this for all these years because we knew that
: differential cryptanalysis was such a potent form of cryptanalysis,
: and we wished to avoid its discovery and use (either for designing
: or for attacking) on the outside.  Now the techniques are known,
: and we felt it is time to tell our side of the story.
: 
: Don Coppersmith
: -----------------------------------------------------------------------------
: 
: 
: -- 
: _______________________________________________________________________________
: | Markus Kempf, Department of Physics/SAGA e.V., University of Kaiserslautern |
: | Germany, [email-masked]                                               |
: |-----------------------------------------------------------------------------|
: 
: