From: Eric Cordian <emc@wire.insync.net>
Date: Wed, 16 Sep 1998 12:05:44 +0800
To: cypherpunks@cyberpass.net
Subject: Re: The DES Analytic Crack Project
In-Reply-To: <35FF6B68.41B863BB@stud.uni-muenchen.de>
Message-ID: <199809161706.MAA16662@wire.insync.net>
MIME-Version: 1.0
Content-Type: text/plain



Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> writes:
 
> As far as I know Boolean minimization has been one of the central
> themes of people doing circuit design from the beginning. I should be
> surprised if there are spectacular breakthroughs recently.
 
The general boolean minimization problem is hard.  A specific boolean
minimization problem may or may not be difficult to solve.
 
Going back to our "safe execution" analogy; determining the runtime
properties of an arbitrary computer program by examination of the code
is impossible.  Determining whether Bob's page of assembler will write
all over the OS may be easy or hard, depending upon the code in
question.
 
Knapsack with power of two integers is trivial, general knapsack is
NP-Complete, and random knapsack is not secure enough to be used as a
strong cryptosystem.
 
So given a specific problem, like DES, it is wrong to say that DES is
combinatorially intractable because general satisfiability is hard or
general boolean minimization is hard and DES has a polynomial
reduction into such a problem, or that DES cannot be broken
analytically because there have been no "spectacular breakthroughs" in
the general case of these other problems.
 
DES is a single instance, not a class of problems.  It is of some
constant degree of difficulty, and solving it, even under the image of
a transformation into an instance of some other well-known problem,
implies things only about the strength of DES, and not about the
general case of other classes of problems which might be used to
represent it.
 
Breaking N-Round DES tells us only about the resistance of N-Round DES
to whatever attack we are using, and does not imply intractable
problems do not exist, or disclose some new sneak attack against all
problems in NP.
 
After this project is done, hard problems will still be hard.
 
Hopefully what will have been demonstrated is that a small simple
block cipher designed in the mid-70's is algebraically crunchable in a
lot less time than an exhaustive search would take.  An interesting
result, but one which has no huge implications for the larger scheme
of things.

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