From: Jim Gillogly <jim@rand.org>
Date: Tue, 29 Mar 94 14:39:08 PST
To: cypherpunks@toad.com
Subject: Re: Ames/ clipper compromised?
In-Reply-To: <199403292157.QAA18896@freud.bwh.harvard.edu>
Message-ID: <9403292238.AA13080@mycroft.rand.org>
MIME-Version: 1.0
Content-Type: text/plain



> Adam Shostack <adam@bwh.harvard.edu> writes:
> The skipjack review committe wrote:
> | second.  At that rate, it would take more than 400 billion years to
> | try all keys. Assuming the use of all 8 processors and aggressive
> | vectorization, the time would be reduced to about a billion years
> 
> Could someone explain why jumping to 8 processors knocks the
> time down by a factor of 400, instead of a factor of 8?  Is the 400
> billion years a load of crap, intended to sound more impressive than
> 8?

Without seeing the algorithm we can't be sure, but that could be OK for
ballpark: the 8 processors gives you 50 billion years, and the aggressive
vectorization gives you the other factor of 50.  Since they've said there
are 32 rounds of <something> in there, I assume the point is to run those
rounds in parallel... or overlap the output of that round of one key with
the next round of a previous key, or some such dramatic stuff, and 32 is
close enough to 50 for this level of estimate.  Sounds aggressive to <me>,
anyway -- how about you?

But it's meaningless to ask how long today's hardware would take to solve
this stuff.  Extrapolations aren't much better, but at least they give a
convenient exponential benchmark.  Let's take Wiener's proposed design for
3.5-hour cracks on a $1M machine as the benchmark of solving a single key
at acceptable expense.  Note that the speed or power of machines has been
doubling about once every 12-18 months.  Wiener's machine brute-forces a
56-bit key in reasonable time, so if your bang/buck ratio keeps going at
the current rate, in 24-36 years something equivalent would be able to
brute-force an 80-bit key.  That might explain why they chose 80 bits
instead of 128... if the algorithm escapes, they don't lose contact with
its product forever.

Note that the Skipjack Review committee was not in fact using the billion
years "load of crap" mode.  In the executive summary, they say:

  1. Under an assumption that the cost of processing power is halved
     every eighteen months, it will be 36 years before the cost of
     breaking SKIPJACK by exhaustive search will be equal to the cost
     of breaking DES today.

I located and cut&pasted this after writing my previous paragraph, so we
can call these independent findings. :)  Note that they produced this
before Wiener presented his design, so the cost of a break was not
(publically) known at that point.

	Jim Gillogly
	Highday, 7 Astron S.R. 1994, 22:34