From: Ryan Lackey <rdl@mit.edu>
Date: Mon, 20 Jul 1998 10:32:50 -0700 (PDT)
To: rdl@mit.edu
Subject: 3DES weak because DES falls to brute-force? (was Re: John Gilmore...)
Message-ID: <199807201732.NAA25239@denmark-vesey.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


[recipients list trimmed somewhat]

I think it is always reasonable to be cautious, but there is a point where
overcautiousness is counterproductive.  Believing 3DES weak because DES is 
so strong that it has thusfar withstood more analysis than any other
cipher and only falls to brute force is, I believe, one of these cases 
of excessive paranoia.

Assumptions:
* Brute forcing DES with a 56-bit key took $50k in materials in today's money.
* 3DES with 3 keys is strong enough to resist everything weaker than
a 112-bit brute force attack (due to the meet-in-the-middle attack)
* Physics, as you say, is not optional.
* The notation 2**56 is two raised to the fifty sixth power.

At first approximation, doing the same thing to a 112bit 3DES problem would
require 2**56 more chips. and thus 2**56 more money, to do in the same amount 
of time.  My copy of gnu bc tells me this is "3602879701896396800000", or
three and a half sextillion dollars.  This is more than a billion times the
current world industrial output.

This is somewhat of a naive calculation, though.  Those chips were not
ideal.  There's a general rule about chips doubling in transistor count (and
for this application, performance) every 1.8 years.  Assuming this
rate of improvement, and let's say a random factor of a million for better
design, and a fabrication improvement rate (due to buying all your
raw-materials suppliers, them becoming more efficient, etc.) which together
with Moore's law doubles performance every year (mostly for ease of 
calculation).

Let's assume the target is to be able to complete the calculation within
ten centuries.  It is better to wait until this is possible before
starting than to start and run a calculation for a billion years waiting for
it to catch up, as few things are of value that far in the future, and also
there is the time value of money to worry about.

Let's also place a budget cap of $20t US today's money on the problem at
the start of calculation.

(2**56)*50000/1000000 	== 3602879701896396 dollars today
1000*365/3 		== 121660 gilmore-kocher periods in a 1000 years
3602879701896396/121660 == 2961433258175568 dollars today to crack in 1000 
years
log(2,2961433258175568) == slightly more than 51 years

So, this *highly* optimistic calculation says that even if we are willing to
assume an *incredible* performance speedup due to better technology and
vertical integration that continues unabated (and exceeds reality), *and*
we're willing to wait 1000 years for our answer, *and* are willing to spend
$20t to build the machine, it is at least 51 years before you should start.

This also doesn't take into account the incredible power consumption of
such a machine -- about half a million times more than the gilmore-kocher
machine.  I assume their chips drew 5 watts each -- it would need 3 GW, which
is a major nuclear facility with multiple reactors.  Cost of power is *not*
going down, so it's about $250 billion dollars a year in electricity, for
1000 years.

This doesn't take into account the potential for a "technology refresh"
throughout the 1000 year calculation period.  It's a long enough period of
time to make this significant.

I'd say the odds of an analytic attack against DES or a fundamental 
breakthrough
in quantum computing or something in 50 years, let alone 1050 years, are
far higher than the chances anyone would go through this much trouble.

While I agree that data intended to remain secure should be secured with
something other than 3DES, it is for the potential of a breakthrough in 
algorithms, not speedup in brute force techniques, which is worrisome.  Brute
force techniques are basically public knowledge.  A secret analytic 
breakthrough, however, could be completely black.  The solution some people
have come up with is multiple ciphers used in such a way as to be as strong
as the strongest link.  The increase in keysize is not a major issue for 
something intended to last this long.

If you can get a cipher which has as its weakest point a brute force attack,
you have won.  If you can get a *system* which has as its weakest point a brute
force attack on a 112 bit key, you've probably killed everyone in the world 
already several times over in a preemptive strike, especially everyone who 
ever had any knowledge of the keys or data.  Humint, monitoring hardware, etc. 
are
far more appealing than a brute force attack against any real system.
-- 
Ryan Lackey
rdl@mit.edu
http://sof.mit.edu/rdl/