Re: 2047 bit keys in PGP
From: owner-cypherpunks To: cypherpunks Subject: Re: 2047 bit keys in PGP Date: Thursday, January 04, 1996 11:29AM
In article <v02130503ad119cbfdece@[205.231.67.43]>, netdog <netdog@dog.net> wrote:
nobody will ever need more than 640K or RAM? i wouldn't underestimate
the
ability of technology to grow at a pace that is beyond our wildest dreams-especially with this network serving as a virtual office/lab. of course, ymmv.
Order of magnitude check:
There is a very well-defined limit to the size of key that can be broken by brute force, independent of your "wildest dreams" as to the growth of technology. It's the Laws of Thermodynamics.
[snip] No law says the attack has to be brute force. What about the birthday attack, differential cryptanalysis, etc? True, I believe neither of those examples are applicable to RSA, but factoring is, and it's _much_ more efficient than brute force searches. There might be other algorithems out there (or as yet undiscovered) that are more efficient than current factoring algorithms are (or ever hope to be). If your attacker has an algorithm whereby he has to search less than the full keyspace, he has effectively reduced the size of your key. Essentially, his attack is the same order of magnitude as a brute force search of this new reduced keyspace (call it "effective" keyspace for convenience). The greater difference between the effective keyspace and the real keyspace (determined by his cracking algorithm), the larger I need to make my real key to compensate. If his algorithm effectively cuts my keyspace in half, I need to make it twice as large as I would need if my attacker's best algorithm were brute force.
And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space."
Hmmm... Well, the 384-bit Blacknet PGP key was cracked in just a few months. How? Certainly parallelism helped, but the main reason is that they were factoring keys rather than searching the full keyspace by brute force. I don't know about you, but I'm certainly not going to stop increasing the size of my key simply because it can't be cracked by brute force. - Cedric
From: Cedric Tefft <CedricT@datastorm.com> Date: Thu, 04 Jan 96 14:12:00 PST >And they strongly imply that brute-force attacks against 256-bit >keys will be infeasible until computers are built from something >other than matter and occupy something other than space." Hmmm... Well, the 384-bit Blacknet PGP key was cracked in just a few months. How? Factoring a 384-bit number is not equivalent to searching a 384-bit keyspace. Consider that there are 78498 primes less than 1000000. This means that you can do a brute force search of a keyspace of under 17-bits to find a prime factor of any composite number less than 1000000000000 -- a bit under 40 bits. I've done this to verify the results of an implementation of the Rabin-Miller primality test on relatively small numbers. I'm not sure how many primes there are with 192 or fewer bits, but it's far fewer than 2^384. There are better techniques around for factoring large numbers than this sort of brute force testing. While I didn't follow the thread very closely, they probably used the quadratic sieve or number field sieve algorithm. See Schneier's _Applied_Cryptography_ for more on factoring, including references to more detailed works. -- Rick Busdiecker Please do not send electronic junk mail! net: rfb@lehman.com or rfb@cmu.edu PGP Public Key: 0xDBD9994D www: http://www.cs.cmu.edu/afs/cs.cmu.edu/user/rfb/http/home.html send mail, subject "send index" for mailbot info, "send pgp key" gets my key A `hacker' is one who writes code. Breaking into systems is `cracking'.
participants (2)
-
Cedric Tefft -
Rick Busdiecker