DES designed to withstand differential cryptanalysis

[Markus Kempf [Physik]]

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, ke...@rhrk.uni-kl.de |
|-----------------------------------------------------------------------------|

[Stanley T.H. Chow]

In article <1992Mar23....@rhrk.uni-kl.de> ke...@rhrk.uni-kl.de (Markus Kempf [Physik]) writes:
>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 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

The more interesting question (to paraphrase a famous line):

What did the NSA know, and when did they know it?

Some follow on questions:

- did knowing differential analysis lead NSA to half the key?
(Presumably the IBM cryto group picked 128 for good reasons).

- did NSA know anything more powerfull?

- what motivated the S-box changes? (Since IBM already knew
and defended against d.a. in Lucifer).

I know these questions are unlikely to ever be answered in the
open, but they are even more interesting in like of the
statement from Coppersmith.

--
Stanley Chow InterNet: sc...@BNR.CA
Bell Northern Research UUCP: ..!uunet!bnrgate!bqneh3!schow
(613) 763-2831
Me? Represent other people? Don't make them laugh so hard.