1998-09-15 - Re: The DES Analytic Crack Project

Header Data

From: Anonymous <nobody@replay.com>
To: cypherpunks@cyberpass.net
Message Hash: cc714d77a3f4c1894f3d35d658f598ac02e8f5dc37ee8e3427a7a0f8c1698be0
Message ID: <199809151500.RAA31305@replay.com>
Reply To: N/A
UTC Datetime: 1998-09-15 01:59:32 UTC
Raw Date: Tue, 15 Sep 1998 09:59:32 +0800

Raw message

From: Anonymous <nobody@replay.com>
Date: Tue, 15 Sep 1998 09:59:32 +0800
To: cypherpunks@cyberpass.net
Subject: Re: The DES Analytic Crack Project
Message-ID: <199809151500.RAA31305@replay.com>
MIME-Version: 1.0
Content-Type: text/plain



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.  (You can artificially suppress this by
introducing new variables for each round, but that doesn't change the
underlying complexity of the problem.)

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.

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).





Thread