From: DAVESPARKS@delphi.com
Date: Thu, 21 Jul 94 22:55:33 PDT
To: cypherpunks@toad.com
Subject: Double DES calculations
Message-ID: <01HEZL9H8PSO95MU4U@delphi.com>
MIME-Version: 1.0
Content-Type: text/plain


norm@netcom.com (Norman Hardy) wrote:

> >Anyone care to estimate what the cost of the RAM alone for the
> >"MITM interface" machine would be?  Let's see, for two 56 bit beys, you'd
> >need storage for 2^57 blocks of 8 bytes each, or 2^60 bytes.  At $40 per
> >Mb, or so, that would come to ... let's see ... $4 * 10^51 for memory
> >alone.  And once the list of blocks started growing as the attack
> >progressed, could the interface processor keep up with the other two, in
> >real time?  Massively parallel processors might speed both ends of the
> >attack, but the "database comparison phase" would be the real bottleneck,
> >IMHO.
> ...
> DAT tape, not RAM, I think. At $5 per GB I get $5*10^11 to hold the info.
> MITM requires a sort of this which requires roughly log(10^20) passes with
> a favorable constant. This will wear out a bunch of DAT drives but that is
> relatively minor. This is about an order of magnitude bigger than a
> project that I considered once to find the optimal solution to the Rubics
> cube.

"Only" $500 Billion, huh (for tapes and drives alone)?  Let's see how the
logistics work out on that.  If each tape drive measured 2"X4"X6", and if
they were mounted in racks, back-to-back, five feet high, with three feet
wide aisleways between them, they would require 3.2 million square feet of
floor space.  (How big is the entire Pentagon, BTW?)  Assuming each of the
300 million tape drives consumed 25 watts of power, the total power
consumption would be 7500 megawatts!  At $0.10 per kwh., it would cost $1
million/hour in power costs alone, assuming a 33% overhead for removing all
they heat they generated.

Assuming it took an average of five seconds to load a tape into a drive,
loading 300 million tapes would take 16,680 man hours, or roughly 10
man-years assuming a normal 40 hr./week work schedule.  A set of replacement
tapes alone would cost $3 Billion.

It has been estimated that breaking single-DES would take 1.35 hours on a
hypothetical "super-DES-breaker" machine, searching half the total keyspace,
with a 50% probability of finding the key in that time.  You yield the same
probability on double-DES would require searching 71% of the keyspace, which
would take roughly two hours, using TWO such machines.  During that two
hours, each of the 300 million tapes would be filled with data, but no
actual MITM comparisons would have occurred yet.  Thus far, we've spent $2
million on electricity alone.

Now let's assume that each block of data generated was at least pre-sorted
onto one of the 150 million available drives during the initial phase,
according to its MSBs, or whatever.  Now it remains to check for matches for
the data on each of the 150 million drives on the ENcryption side with the
corresponding drive on the DEcryption side.  Let's further assume 150
million processors each assigned to handle a pair of drives, one on each
side.  Assume that a complete pass through the tape would require the same
two hours as it took to write the data there in the first place, with
buffered I/O so that at least half of the drives are running at full speed,
and ignoring any rewind time between passes.

Assuming a fast enough processor, the number of passes required would vary
according to the ratio of the total data on each tape, divided by the total
RAM, with the available RAM available for searching equalling four times the
search block size to allow double buffering on both sides.  With that in
mind, the number of passes required would equal to ( 4 * 4 Gb / RAM ).  If
64 Mb of RAM is available per processor, then a total of 256 passes would be
required, for a total search time of 512 hours.  The sum total of all the
RAM on all 150 million processors would be 2 * 10^16 bytes.  At $40/Mb, the
RAM alone would cost $800 Billion, bringing the total cost of this machine
to $1.3 TRILLION!  The time required to crack a double-DES key is over 200
times that of a single-DES key, at a cost in excess of half a BILLION
dollars per 112 bit key.

While that *MIGHT* be technologically feasible, it probably wouldn't be
politically feasible.  That is probably more than the sum total of all US
defense spending in out 120 year history, and probably more than "Star Wars"
was projected to cost.  That'd be a bit hard to hide in a "black" budget.

Of course, there are various ways of trading dollars for time in designing
such a system.  Speed is virtually proportional to cost.

Nevertheless ... if you've got the time to do TRIPLE-DES, it's probably
still wise, "Justin Case"...

 /--------------+------------------------------------\
 |              |  Internet: davesparks@delphi.com   |
 | Dave Sparks  |  Fidonet:  Dave Sparks @ 1:207/212 |
 |              |  BBS:      (909) 353-9821 - 14.4K  |
 \--------------+------------------------------------/-/