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
participants (3)
-
Eric Cordian -
jimg＠mentat.com -
Mok-Kong Shen