3DES weak because DES falls to brute-force? (was Re: John Gilmore...)

[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/

Sigh.  One should not do math before coffee.

Let's try this again:
If you assume 2^56 requires $50k and 3 days, and are willing to take
2^8 times longer and spend 2^16 times more, and want to break a 2^112 bit
key, and assume technology doubles in performance for this particular
operation per year, then the calculation is easy to do.

112 - 56 - 16 - 8 = 32

If you wait 32 years, and have *incredible* performance gains in excess of
what we have now (but which I think could be possible for worst-case crypto
breaking chips, since they have relatively little in the way of communication,
and have small units), and have a budget of 16 times what the DES cracker
had (about $3b, which is totally reasonable), and are willing to wait about
2 years, you can brute force 3DES in the year 2030.

There is still very little that is relevant in 32 years, and there is still
a far better chance that some analytic attack will be discovered, a fundamental
breakthrough in computation will happen, etc. before that time.

112 bits is below the "physical impossibility" point as far as key size goes
(I like the calculation based on free energy in the universe in Applied 
Crypto).
Chapter 7 in Applied Crypto is probably a far better analysis than mine,
especially as it includes the caveat emptor section.

Perhaps it is correct, "It's time to bring on those 128, 192, and 256-bit 
keys",
at least for some systems, although I'd definitely prefer multiple ciphers
separately keyed with long keys than n-DES for such long-term use.

Calculating future key lengths really *is* a losing game.
-- 
Ryan Lackey
rdl@mit.edu
http://sof.mit.edu/rdl/

On Mon, 20 Jul 1998, Ryan Lackey wrote:

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

Humrph .. your calculations came in just before I was gonna send mine out
.. bc is a nice utility, ain't it? :)

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

Well, I disagree here.. unless the "something other than 3DES" is an OTP,
of course. I don't see anything that looks better than DES, minus the
key-size issue. DES has had the fiercest analysis done on it for the
longest amount of time. If we are worried about a breakthrough in
the algorithmics, then it seems to me we ought to use DES based on the
fact that it has been analyzed longer, and has proved itself strong.

We've covered the new vs. old algorithm debate here recently, so I'll
shut up.. suffice it to say, I fall in line with the 'old' school.

I don't find it useful to worry about possible new general cryptanalytic
breakthroughs: it is basically impossible to defend against them. In
the face of an attacker who has infinite secret cryptanalytic ability 
(within the bounds of what can be done brute-force wise) only an OTP
would be useful, but we are talking long-term archival here.. I don't
see how an OTP helps us. If we have a secure vault to lock the pads up
in until either a) the heat death of the universe, or b) the Big Crunch
then we may as well just put the plaintext in there and be done with
it. As I see it, OTP are only workable in communications, and then
obviously in a limited manner.


Michael J. Graffam (mgraffam@mhv.net)
http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc
I think that we should be men first, and subjects afterward. It is not
desirable to cultivate a respect for the law, so much as for the right.
			Henry David Thoreau "Civil Disobedience"

>I don't find it useful to worry about possible new general cryptanalytic
>breakthroughs: it is basically impossible to defend against them. In
>the face of an attacker who has infinite secret cryptanalytic ability 
>(within the bounds of what can be done brute-force wise) only an OTP
>would be useful, but we are talking long-term archival here.. I don't
>see how an OTP helps us. If we have a secure vault to lock the pads up
>in until either a) the heat death of the universe, or b) the Big Crunch
>then we may as well just put the plaintext in there and be done with
>it. As I see it, OTP are only workable in communications, and then
>obviously in a limited manner.
>

Are we talking long-term archival?  I'm more concerned about someone
grabbing communications in transit, storing them and throwing chips and
mathematicians at it.

If the government comes with the search warrant, then I should have already
deleted the file if I didn't want it available.  If someone wants to face
security guards or a gun by my bedside they can steal the archive.  It's
the same rules as always. (except the theif must also have the math and
chips).

In the case of archive you have the protection of physical security and in
most cases the knowledge of when it has been breached -- It's a lot
friendlier than in communications where who knows what is going on between
the sender and recipient.

OTP is a pain, and is not effective for archival -- but it is the only way
I've seen to protect communications in excess of ~30 years.

Bryan Waters                                    http://www.ultimateprivacy.com
Director of Marketing                    Voice: 512-305-0505 Fax: 512-305-0506
Ultimate Privacy Corporation       3925 W Braker Ln #305, Austin, TX, 78759