From: jimg@mentat.com (Jim Gillogly)
Date: Tue, 15 Sep 1998 12:43:42 +0800
To: cypherpunks@cyberpass.net
Subject: Re: The DES Analytic Crack Project
Message-ID: <199809151742.KAA12178@zendia.mentat.com>
MIME-Version: 1.0
Content-Type: text/plain



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