From: Eric Cordian <emc@wire.insync.net>
Date: Tue, 15 Sep 1998 00:18:56 +0800
To: cypherpunks@cyberpass.net
Subject: The DES Analytic Crack Project
Message-ID: <199809150520.AAA13045@wire.insync.net>
MIME-Version: 1.0
Content-Type: text/plain



As some of you may have noticed, a new attempt to crack the Data
Encryption Standard has been started, with a descriptive FAQ located
at the following URL
 
        http://www.cyberspace.org/~enoch/crakfaq.html
 
A while back, after the first DES challenge was announced, a number of
us made the observation that a known plaintext attack on DES,
expressed as a system of a few thousand boolean variables with
constraints in 3-conjunctive normal form, was not too far from the
size and complexity of problems that could be directly solved by
bleeding edge combinatorial algorithms, albeit with signficant CPU and
memory consumption.
 
We thought this would be an interesting result, and generated a number
of problems of various numbers of DES rounds based on the DES
Challenge data, and some not particularly optimized S-Box
representations, and set about the task of solving them, smaller
problems first.  We wrote a lot of code, learned a lot about arbitrary
systems of boolean variables, and after breaking 2-round and 4-round
problems, the first almost instantly, and the second with very
reasonable amounts of resources, set about the task of seeing if we
could break the higher round problems, and immortalize ourselves by
beating DESCHALL to the key.
 
To our very great regret, we did not manage to do this, and once the
$10k prize was claimed, we figured the game was over and returned to
working on other things.  We still thought DES was a problem of
approximately the right size to demonstrate the existence of an
analytical solution which would beat a well-tuned exhaustive search on
a problem of practical interest.
 
Since that time, DES has been broken twice more by exhaustive search,
once by distributed.net, and again by a hardware DES cracking machine
designed by Net legend John Gilmore and the EFF for a non-trivial
amount of money.
 
Remarkably, although most agree DES is dead for new applications, with
Moore's Law and additional hardware crackers being possible today for
much less than the cost of the prototype, it still seems to enjoy a
reputation amongst the public as a cipher that takes 20,000 pentiums
running for half a month or a hardware box with $100k of chips running
for several days to break, neither of which seems to have thrown the
Fear of God into its current users, most notably the Banking Industry.
 
With other analytic attacks like differential and linear cryptanalysis
being really practical only for reduced round DES, and all current
high-profile cracks on production ciphers employing key trial, the
press has latched onto keysize as a synonym for strength, and has made
numerous statements which have reinforced this questionable paradigm
in the minds of the public.
 
We have therefore been taking another look at our idea of a
combinatorial crack of DES, and decided that even with DES having been
cracked three times by key trial, it is definitely a project worth
doing.  This time, rather than working frantically in an unsuccessful
attempt to beat other teams on a public challenge, we wish to finish
up our original efforts, and repeat the three cracks previously done,
this time using our algorithms, and distribute working code
continuously as the project progresses, to sponsors who have donated
some money to defray our costs.  This will offer people the
opportunity to participate vicariously in a fun project which has the
potential to be a genuine paradigm shift in the way the world thinks
about codebreaking.
 
Sometimes, promising areas of research are not followed because of
knowlege of some well-known result which suggests that such
exploration will be unfruitful.  Years ago, for instance, suggestions
that programs could be checked by software for proper behavior, and
run without using protected memory regions, were usually met with
snide comments about the "computer halting problem" and various
adjunct results.  Today, there are many variants of "safe execution"
technology, from prove and carry schemes, to Java bytecode, with a
sound theoretical basis behind them.  None of these is a violation of
the "computer halting problem" results, of course.
 
Similarly, after a large burst of activity decades ago, which resulted
in the notion of NP-Completeness, and various results in computational
complexity theory, suggestions that an analytic solution exists for
some large combinatorial problem of practical interest conjure up
visions of exponential resource utilization, speaker cluenessless, and
the lack of progress on NP=P.
 
For this reason, we feel this project is definitely a Schnelling
Point.  If it works, even badly, people will begin to look at lots of
problems in ways they would not have considered before, and much new
code which improves upon what we have done will be created.  This will
be an irreversible change in the Order of Things.
 
In the several days since we put up our FAQ, we have gotten quite a
few comments, and some concerns.
 
The comments have mostly been along the lines that it is an
interesting, even intriguing project.  The concerns are generally that
we will experience an unexpected "combinatoric explosion" in the
higher round problems, and that no one in their right mind would send
money to a nym, because it might just vanish and be used by the nym to
live in perpetual ecstasy in some place warm and tropical, without the
possiblility of the nym being sued for fraud.
 
We hope the close coupling between the sponsors and the project
members will eliminate this latter concern, with weekly progress
reports and working code being distributed to permit the sponsors to
reproduce our results as they occur.  If three people are willing to
sponsor and give us the go-ahead to begin, without wanting their money
back if other sponsors do not join, we can probably get through the
minimal S-Box representations and their proof-of-correctness as well
as some cleaned up code for the 2-round problem.  Hopefully we will
then have a reputation with these people which will encourage others
to join in the effort.
 
Clearly, we're after speculative capital, rather than widow and orphan
money, and hope a few of the wealthy older retired (and perhaps even
crusty) engineer types might find this a productive thing to support.
After all, if you've just blown $220,000 on a DES Cracker, making it
$220,500 and getting your very own Schnelling Point in return is
probably a reasonable amount of fun for your money.
 
I'll stop ranting now. :)

--
Sponsor the DES Analytic Crack Project
http://www.cyberspace.org/~enoch/crakfaq.html