Re: The DES Analytic Crack Project

nobody said:
> 
> Eric Michael Cordian, emc@wire.insync.net, writes:
> 
> > The concerns are generally that
> > we will experience an unexpected "combinatoric explosion" in the
> > higher round problems
> 
> Unexpected by you, perhaps, but expected by everyone else.  The complexity
> of the expressions should increase exponentially with the number of
> rounds.  Extrapolating from two and four round results to eight and
> sixteen is the wrong model. ...
> 
> Can't you come up with a back-of-the-envelope estimate for the number of
> terms in your sixteen round expression?  Even without fully optimized
> S-box expressions this information would be useful.  If it is greater than
> the number of atoms on Earth then it would be a strong hint that this
> approach won't work.

In the early 1980's I started trying this approach.  I did the
back-of-the-envelope estimate and realized it was too big, but
I thought it worth trying, since if there were a back door in
DES it might manifest itself by a massive collapse in the complexity
of these expressions.  I didn't get far enough into it to decide one
way or the other, since I didn't have a good tool for reducing the
expressions to minimal form.

	Jim Gillogly

Jim Gillogly wrote:
> 
> In the early 1980's I started trying this approach.  I did the
> back-of-the-envelope estimate and realized it was too big, but
> I thought it worth trying, since if there were a back door in
> DES it might manifest itself by a massive collapse in the complexity
> of these expressions.  I didn't get far enough into it to decide one
> way or the other, since I didn't have a good tool for reducing the
> expressions to minimal form.

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.

M. K. Shen

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