Key length security (calculations!)

[doug@OpenMind.com (Doug Cutrell)]

Tim Mays writes:

>I refer readers to the sci.crypt FAQ, the RSA FAQ, or books such as
>"Applied Cryptography." (Hint for those who don't want to: one time
>pads (Vernam ciphers) and things like RSA with 1000-digit moduli.)
>
>("Enough effort" can be interpreted in a circular way to ensure the
>answer is 'Yes," as a truism. This is meaningless, if "enough effort"
>is impossible to achieve, as with OTPs, or is beyond the energy in the
>universe. If "enough effort" is interpreted to mean theft or rubber
>hose crytanalysis, all bets are off. But most people who ask the
>question I cited don't mean these loopholes.)

I have seen Tim posting statements to this effect many times, and because
he is one of the more well respected and listened to voices on the list, I
feel it important to examine this in some detail.  While I agree that 1000
bit moduli in RSA is adequate protection *in all probability*, for even
national security secrets, I think it is far from clear that this will
definitely be true 10, or even 5 years from now.  Instead of just waving
vague generalities around, though, let's do some nitty gritty calculations:

The people who cracked RSA-129 themselves have stated that they believe a
1024 bit modulus is at most 20,000 to 2,000,000 times more difficult to
crack than RSA-129.  For example, I recall Derek Atkins posting that he
estimated a 1024 bit key to be 40,000 times harder than a 512 bit key,
although I didn't save the posting.  And Paul Leyland of Oxford posted:

>RSA-129 is 425 bits; rather harder than 384-bit numbers.  We estimate
>that 512-bit keys are about 20 times harder than RSA-129, if a more
>efficient but available algorithm is used.  No-one knows how much
>harder 1024-bit numbers are, but they will be no where near a trillion
>times harder than 384-bit keys.  Best estimates suggest that 1024-bit
>numbers are about 10^4 to 10^5 times harder than 512-bit numbers.

OK, so the people in the civilian world working on this today say it is
possible that a 1024 bit key is only 20,000 times harder than RSA-129
*using known algorithms*.  Now let's really get our hands dirty:  cracking
RSA-129 was estimated to take 5000 mips years.  The  NAL NWT 2/140 computer
installed at the National Aerospace lab in Tokyo is estimated at 357 Cray
YMP equivalents.  I estimate this to be equivalent to 200 Gips for the
purposes of this computation (this is possibly where I am most off).  5000
mips years = 1.58 X 10^17 instructions.  This comes out to 9.13 days on the
NAL NWT 2/140.  If my estimates above are correct, scaling up to the 7400
Cray equivalent computer due to be installed 4Q95, from the 357 Cray
equivalent above, we go down to 10.5 hours.  This is all for the RSA-129,
of course.

Still sounds pretty safe so far... if it really takes at least 20,000 times
as long to crack a 1024 bit modulus, then it would still take the 7400 C.E.
(Cray Equivalent) computer 24 years to crack a 1024 bit number.  BUT, the
biggest worry is that no one knows how good the NSA's factoring algorithms
are.  I read recently that the NSA is the world's largest employer of
mathematicians.  The relative improvement in factoring algorithms since the
introduction of the RSA-129 problem, to its factoring almost 20 years
later, far exceed even the exponential increase in computer speed over that
same period of time.  (5 orders of magnitude?  more?)  We have no way of
knowing how many orders of magnitude leeway we have, because as the moduli
get larger, the factoring algorithm gets more and more important.  Suppose
the NSA has four orders of magnitude on us in the efficiency of their
factoring algorithms.  In that case, they might be able to crack a 1024 bit
key as early as the end of 1995.  (20,000 X 10.5)/10^4 hours = 21 hours
required).  Granted, this may not be likely, but I think we have to take
the possibility seriously.  At this point, 1024 bit keys cease to be secure
for matters of critical national security (but still good for everything
else).  Now let's continue with our worst case scenario... suppose that
computer speed doubles every 3.3 years over the next decade, and that
further algorithmic breakthroughs continue to at least match this rate of
doubling (not likely, perhaps, but *possible*).  Then just one decade
later, in 2005, the computer power of the NSA is 8 times greater, and the
algorithms are 8 times faster, for a total speed increase of 64.  At this
point, they could crack a 1024 bit key in just 20 minutes (using all their
resources), or 72 keys per day.  At this point, I start to be uncomfortable
trusting my security to a 1024 bit key length.

So, it seems *possible*, even if by no means probable, that a 1024 bit key
length is only good for the next decade or so.  My intent is not to foster
paranoia, but cypherpunks, of all people, should take as critical a view of
key length security as possible.

I suggest that people who state that the want 1200 bit or even 2000 bit key
sizes in PGP be no longer ridiculed... the issue is subjective, as we have
no way of knowing what the NSA's factoring algorithms are like.

Doug

___________________________________________________________________
Doug Cutrell                    General Partner
doug@OpenMind.com               Open Mind, Santa Cruz
===================================================================