From: Eric Cordian <emc@wire.insync.net>
Date: Tue, 15 Sep 1998 11:52:19 +0800
To: cypherpunks@cyberpass.net
Subject: Re: The DES Analytic Crack Project
In-Reply-To: <199809151500.RAA31305@replay.com>
Message-ID: <199809151652.LAA13965@wire.insync.net>
MIME-Version: 1.0
Content-Type: text/plain



Anonymous <nobody@replay.com>
 
>> 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.  (You can artificially suppress
> this by introducing new variables for each round, but that doesn't
> change the underlying complexity of the problem.)
 
The size of the problem scales linearly with the number of rounds, and
of course additional variables are introduced to make sure that terms
in the CNF representation reference three or less variables.
 
The number of such terms is clearly bounded by the cube of the number
of variables, and practical experiments with a wide variety of
problems illustrate that memory usage is generally limited to a small
integer multiple of the original problem size.  Intractability
generally appears as a lack of locality, in that canonicalization of
the problem requires the use of algebraic identities involving large
numbers of terms, such identities becoming statistically more rare
with increasing N.  We anticipate that the set of such identities
required to converge a DES problem will have a small N, and we will
simply augment that set should the algorithm cease to make progress
prior to finding a solution.  We know there will be no memory
explosion, and CPU should remain small enough for us to achieve our
stated goal of less than a day on a $5k workstation.
 
> 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.
 
Back when we were working on the original DES challenge, with naive
S-Box optimization, the size of the input data sets were as follows.
 
            vars   implications   3-CNF terms
            ----   ------------   -----------
 2-round    2015           4046          1959
 4-round    4588           9192          4596
 8-round    9852          19720          9860
16-round   20389          40794         20397
 
> If you really want to attract money you need some kind of numbers to
> show that the approach has a prayer of working.  Show the size of the
> problem you will get, estimate how much improvement you'll get with
> your improved S-box representations, compare it with the problems
> tackled by available combinatorial algorithms.  You should be able to
> do this with a few hours of work, at least to show that the basic
> concept is sound (or unsound).
 
Our original input sets were generated by a very indirect method,
involving an original implementation as switch networks, a conversion
to NANDs, and ultimately, 3-conjunctive normal form, with some simple
local optimization along the way.  We are a lot better at setting up
these problems now than we were the first time we tried, and
anticipate that we can knock down the variable count by at least a
factor of four by precomputing minimal S-Box representations.
 
This will result in a combinatorial problem in 4000 to 5000 variables
for full 16-round DES, and make this problem approximately equal in
size to where the 4-round problem is now.
 
We've run quite a few medium-sized problems through our combinatorial
algorithms, including reduced-round DES, factoring the 32 bit product
of two 16 bit primes written in terms of individual 2-intput logical
functions, and various problems involving minimizing representations
of boolean functions with respect to a specific cost criteria.
 
So far, no huge surprises.
 
Finding the global minimum cost representation of an S-Box in terms of
selected other functions is actually a good-sized combinatorial
problem in and of itself, and should serve to illustrate how our
algorithms work prior to embarking upon the higher round DES cracks.
 
We don't suggest that these algorithms magically solve every
conceivable problem, merely that they seem to do a satisfactory job on
a number of problems of practical interest.

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