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


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/