Path: utzoo!utgpu!water!watmath!clyde!bellcore!decvax!yale!cmcl2!brl-adm!brl-smoke!gwyn
From: gwyn@brl-smoke.ARPA (Doug Gwyn )
Newsgroups: sci.crypt
Subject: Re: Crypt() hackers
Keywords: DES, des, crypt()
Message-ID: <7242@brl-smoke.ARPA>
Date: 11 Feb 88 02:14:05 GMT
References: <538@ddsw1.UUCP> <8045@eddie.MIT.EDU> <980@sdcc13.ucsd.EDU> <22925@ucbvax.BERKELEY.EDU>
Reply-To: gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>)
Organization: Ballistic Research Lab (BRL), APG, MD.
Lines: 29

In article <22925@ucbvax.BERKELEY.EDU> wallace@degas.Berkeley.EDU.UUCP (David E. Wallace) writes:
>Hence any simplification algorithm you are likely to come up with either
>won't be able to simplify all expressions all the way, or will take an
>exponential amount of time (exponential in the size of the input expression),
>or both.

This is a good example of the difference between the outlook of a real
cryptanalyst and one of the academic theoreticians that publish most of
the "open" literature on the subject.  (This has been noted elsewhere,
for example in an excellent book by Deavours and Kruh on cipher machines,
published by Artech.)  It should be obvious that there is NO NEED to
EXACTLY solve the simplification problem.  A heuristic method that is
"good enough" would suffice, and such a method need not at all be
NP-complete.  (There are good examples of this in the literature; I seem
to recall such an algorithm for the TSP problem by folks at Bell Labs,
for example.)  I sent Keith a fair amount of information about how a
practical Boolean simplification algorithm could be designed.  I don't
particularly want to post it more generally, because if he gets his
technique to work, he deserves the undoubtedly large proceeds from his
invention.  (Just imagine how much you could ask for an effective
automated DES-cracking box!)

There are indeed some problems to be solved in the course of making the
proposed attack work, but there is no real evidence that the problems are
inherently unsolvable by practical means.  "Complexity" arguments are
bogus in cyptography; they have been made many, many times for systems
that in fact were busted wide open in a few hours by competent
cryptanalysts.  Information-theoretic arguments are much more valuable,
but I'm not aware of one that shows the DES to be unduly "hard".