From msuinfo!agate!howland.reston.ans.net!pipex!pavo.csi.cam.ac.uk!cam-orl.co.uk!aph Sat Jan 29 16:31:03 1994 Newsgroups: sci.crypt Path: msuinfo!agate!howland.reston.ans.net!pipex!pavo.csi.cam.ac.uk!cam-orl.co.uk!aph From: aph@cam-orl.co.uk (Andrew Haley) Subject: Re: Why not extend DES? Message-ID: <1994Jan20.180737.895@infodev.cam.ac.uk> Sender: news@infodev.cam.ac.uk (USENET news) Nntp-Posting-Host: quince.cam-orl.co.uk Organization: Olivetti Research Ltd, Cambridge, England. X-Newsreader: TIN [version 1.2 PL2] References: <2gpbf5$qte@hymir.ifi.uio.no> <2h47ck$rvh@transfer.stratus.com> <2hjl36$ktm@rand.org> Date: Thu, 20 Jan 1994 18:07:37 GMT Lines: 82 John K. Taber (jktaber@netcom.com) wrote: : Good points. The secrecy intrigues me, it was so disadvantageous to both : IBM and the NSA. Why did they keep their mouths shut, when the obvious : thing to do was to be open. I mean after the initial suspicions. Perhaps this should be in the FAQ. The reason for the secrecy was to prevent differential cryptanalysis from becoming generally known: > From: kempf@rhrk.uni-kl.de (Markus Kempf [Physik]) > Newsgroups: sci.crypt > Subject: DES designed to withstand differential cryptanalysis > Summary: It was known in 1974 > Keywords: DES, cryptanalysis > Message-ID: <1992Mar23.171311.4134@rhrk.uni-kl.de> > 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