From: tcmay@netcom.com (Timothy C. May)
Date: Thu, 14 Jul 94 12:10:14 PDT
To: doug@OpenMind.com (Doug Cutrell)
Subject: Re: Key length security (calculations!)
In-Reply-To: <1CA23B34695@BlueSky.OpenMind.com>
Message-ID: <199407141909.MAA01482@netcom9.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Doug Cutrells writes:

> Tim Mays writes:

Singular, but no matter.

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

Before going further, let me emphasize my mention in my section above
of one-time pads, or Vernam ciphers. These are
*information-theoretically secure*, which means that no amount of
computer power can *ever* break them. Period.

(In my characteristic way, I included a sidebar mention of stealing
the key and or using rubber hose cryptanalysis, which some may think
finessed my point about not being able to break OTPs. It does not, as
far as "breaking" the cipher has cryptographic meaning.)

As for RSA, that is only computationally secure, and depends on
advances on factoring, as we all know. Many of us think there will not
be "dramatic" advances in factoring, for various reason, but this of
course cannot be proved (can't prove the nonexistence of some clever
approach, logically). Factoring is suspected to be in the class NP (or
even harder, some suspect), but it has not yet been proved to be so.
If factoring is NP-complete, and if P = NP, then fast factoring
methods may be found (fast = polynomial in length). Crypto books deal
with this issue better than I can here.

> 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

Not to attack Doug's point, which has validity here (that we don't
know what factoring advances NSA may have made), but I personally
think the combined capabilities of "public domain mathematicians" are
now far greater than what NSA has. Shamir, Odzylko, Blum, Micali,
Rackoff, Goldwasser, Solovay, Berlenkamp, etc., are top-flight
researchers, publishing many papers a year on these topics. It is
unlikely that some GS-14 mathematicians at the Fort, not able to
publish openly, have made much more progress. I think the resurgence
of crypto in the 70s, triggered by public key methods and fueled by
complexity theory breakthrough, caused a "sea change" in inside
NSA-outside NSA algorithm expertise. 

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

I have never ridiculed them (in fact, I use 1280 bits or somesuch),
and I think the whole recent matter of Phil Zimmermann charging that
"amateur cryptologists" are tainting his reputation and that of PGP to
have some supreme ironies. Seems to me I heard a guy named Bidzos
making the same points.....

(I'm not attacking Phil, just noting the ironies of Phil now
attempting to control the evolution of "his" intellectual property.
The "naming" issue is minor--and that's what digital signatures are
for, anyway.)

A 3000-bit key may very well require more total energy to break than
is available in the universe. Barring P = NP sorts of breakthroughs,
of course. (I did a post on this last week.)

The bottom line is sometimes lost in the debate:

* It is just not true that "any cipher can be broken if the NSA really
wants to." (This was the original point I was responding to.)

* Some ciphers are absolutely unbreakable, and others are effectively
unbreakable, or soon will be. Increased key length is computationally
"cheap" to use, but "expensive" to break. (The current imbroglio about
key lengths of PGP 2.6 is a passing implementation detail, having to
do with how PGP does math. By Version 3.0, speculatively, it will
likely be increased dramatically. No big deal. People should generate
new keys and flush the old ones, anyway.)


--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."