Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!ames!ucbcad!ucbvax!ernie.Berkeley.EDU!rotondo
From: rotondo@ernie.Berkeley.EDU.UUCP
Newsgroups: sci.crypt
Subject: Re: DES info wanted
Message-ID: <18771@ucbvax.BERKELEY.EDU>
Date: Thu, 7-May-87 14:17:54 EDT
Article-I.D.: ucbvax.18771
Posted: Thu May  7 14:17:54 1987
Date-Received: Sat, 9-May-87 06:23:59 EDT
References: <2071@hoptoad.uucp> <599@umnd-cs.D.UMN.EDU> <18742@ucbvax.BERKELEY.EDU> <5841@brl-smoke.ARPA>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: rotondo@ernie.Berkeley.EDU.UUCP (Scott Rotondo)
Distribution: world
Organization: University of California, Berkeley
Lines: 48
Keywords: DES

In article <5841@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn) writes:

> Although I haven't studied DES very hard and don't have any inside
> (i.e. classified) information about DES, from a previous life as a
> part-time cryppy I don't see how DES could be considered unbreakable,
> in the absence of sufficiently frequent key changes.  This follows
> from very general information-theoretical considerations.  Because of
> the complexity of the encryption algorithm, the unicity distance is
> probably rather large, but it wouldn't be infinite.  
[ ... ]
> I would bet that NSA can break DES any time they so choose, if they
> have a large enough contiguous sample of the cipher stream; "trap
> doors" shouldn't be necessary.

Let me start with the disclaimer that I have access only to the open
literature on the subject, so your information may be more reliable
than mine.  

My understanding of the information theoretic argument is that the
unicity distance indicates the approximate amount of ciphertext
needed to break the cipher using infinite computational resources.
As is the case with all systems except one-time pads, the unicity
distance for DES is quite finite (about 18 chars).  However, actually
doing the computation seems to require an exhaustive search of 2^55
keys (not 2^56 because of a known symmetry in the S-boxes).  The
only apparent way to reduce this search is to know about a trap door
in the S-boxes (or elsewhere, but I don't see where).

I probably should have pointed out in my previous posting that a
perfectly valid reason for the NSA to be pushing for a new 
standard is that the old one just isn't secure enough.  A search
of 2^55 keys isn't as prohibitive as it once was [see several papers
by Martin Hellman].  Still, if I had to choose, I'd prefer that
we use DES with longer keys or multiple encryption rather than
trusting the NSA to hold the keys.  This is probably their main
reason for wanting the new system, but being able to read everyone's
mail is a nice fringe benefit.

> (So-called "public key" systems attempt to make [protecting keys]
> unnecessary, but I wouldn't place reliance on the opposition's
> lack of sufficient cleverness or dumb luck to protect anything of
> very great value.)

Does "sufficient cleverness or dumb luck" mean finding a way to factor
large numbers or something else?  My main objection to public key
systems is that they are just too slow.

				-- Scott