From: smb@research.att.com (Steven Bellovin)
Subject: DES (Was: Re: 800MHz Trunked Radio System Signals)
Date: Wed, 30 Dec 1992 18:50:29 GMT
Organization: AT&T Bell Laboratories
Followup-To: sci.crypto

In article <1992Dec30.121120.736@uoft02.utoledo.edu>, cscon0151@uoft02.utoledo.edu writes:
> I've heard the designers of DES made the code too difficult.  The NSA, which
> apparently has to approve the encryption format,  thought that code was too
> difficult, and purposely flawed the encryption standard.  That's what the
> people in sci.crypt told me (I think it was them).  Anyways, the sci.crypt
> newsgroup has some good info about DES and DVP,  at least they did a couple
> months ago.

Yup, sci.crypt is the right newsgroup for this question, and I've redirected
followups to that group.  But since the question keeps coming up...

(a) No one in the civilian sector, with the possible (and I think likely)
exception of the cryptography group at IBM that designed DES, knows
just how strong it is.

(b) There have been persistent rumors that NSA sabotaged DES.  No one
has ever produced any *evidence*, as opposed to likelihood theories.
(I.e., something like ``NSA would like to read your traffic, and they
did review the design, so it stands to reason that they weakened it''.)
Yes, the key size was reduced from 112 bits to 56 bits.  See below...

(c) For years, the most curious feature of DES was the design of the S-boxes,
A few years ago, two Israeli mathematicians (Biham and Shamir) invented
a technique called differential cryptanalysis.  Lo and behold, the
S-boxes in DES are *much* more resistant to that attack than are random
S-boxes or even trivially-modified versions of the standard ones.  In
other words, the designers were really telling the truth all along when
they said that they tried to make a strong cipher, not a sabotaged one.
(Also, Don Coppersmith of IBM has since confirmed that they knew of
differential cryptanalysis, and did, in fact, design DES to resist it.)

Differential cryptanalysis can crack DES in 2^47 operations.  But it's
a chosen plaintext attack, i.e., you have to get the enemy to encrypt
your data under his/her own secret key.  And using something like cipher
block chaining -- the normal method for encrypting messages -- will
defeat the attack.

(d) Biham and Shamir also found that the strength of DES under their attack
is on the close order of 56 bits of key.  A longer key would not add
significantly to the security of DES.  I can make a very good case that
generating the 768 subkey bits from a longer key would actually be weaker
against other kinds of attack.

(e) Shamir -- arguably the foremost civilian cryptologist in the world --
has said that he thinks that DES is about as strong as it could be, given
its general structure.  My interpretation, based on some conversations
with him, is that attempts to tweak it by changing one or two things here
and there will have side-effects that would result in a weaker cipher
overall.

(f) That said, I personally believe that NSA can read DES if they want to.
What is unclear to me is how expensive the attack is, and therefore
how many DES messages they can attack per unit time.  I tend to suspect
that their attack combines an analytic approach with brute force, but
that's just a WAG.  Btw, exhaustive search works not so much because of the
speed of a CPU, but because that sort of attack is decomposable -- you
can throw a million chips at it, and cut your search time down by a like
factor.

		--Steve Bellovin