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