Bugtraq mailing list archives
Re: PGP Distributed Attack
From: pcl () FOO OUCS OX AC UK (Paul C Leyland)
Date: Tue, 15 Apr 1997 09:33:58 +0100
Perry wrote:
1) The largest key thus cracked is perhaps one third that size. Factoring is an *exponential problem* in the size of the number being factored. Cracking a 1024 bit key right now would require far more compute power than is conceivably available.
I'll expand on each of those three sentences. The largest PGP key known to have been broken was the 384-bit BlackNet key which I and 3 colleagues finished almost two years ago. The largest RSA key broken was RSA-129, 426 bits, which we finished three years ago. State of the art is probably 512 bits. IMO, it's only that the principal players in this game are busy with other things that a 512-bit effort isn't underway now. The best factoring algorithms are *not* exponential in the bit length of the integer. They are subexponential. They are, however, superpolynomial. The growth rate of the best known, the number field sieve, is exp((1.9 + O(1)) (log N)^1/3 (log log N) 2^3)) and so, in some sense, is two thirds the way towards being polynomial from exponential. With current hardware and algorithms available to the open world, I estimate that 512-bit factorizations are straightforward to a project similar in magnitude to the current DES and 56-bit RC4 challenges. 768-bit keys might be vulnerable to an effort similar in magnitude to the Manhattan or Apollo projects. 1024 is *right* out. Paul
Current thread:
- Re: [ANNOUNCE]: ipfilter for FreeBSD2.2.x + FreeBSD3.0-current, (continued)
- Re: [ANNOUNCE]: ipfilter for FreeBSD2.2.x + FreeBSD3.0-current Perry E. Metzger (Apr 13)
- 2nd Linux kernel patch to remove stack exec Solar Designer (Apr 13)
- Re: 2nd Linux kernel patch to remove stack exec Systemkennung Linux (Apr 13)
- Re: 2nd Linux kernel patch to remove stack exec Solar Designer (Apr 13)
- Re: 2nd Linux kernel patch to remove stack exec Systemkennung Linux (Apr 13)
- Re: 2nd Linux kernel patch to remove stack exec David S. Miller (Apr 13)
- Re: 2nd Linux kernel patch to remove stack exec Systemkennung Linux (Apr 13)
- Re: 2nd Linux kernel patch to remove stack exec Systemkennung Linux (Apr 13)
- more l0phtcrack errata Systemkennung Linux (Apr 13)
- PGP Distributed Attack Aleph One (Apr 14)
- Re: PGP Distributed Attack Perry E. Metzger (Apr 14)
- Re: PGP Distributed Attack Paul C Leyland (Apr 15)
- Juggernaut 1.1 patch G P R (Apr 15)
- Re: PGP Distributed Attack Ubermensch (Apr 14)
- Re: PGP Distributed Attack Tom Guptill (Apr 14)
- Re: 2nd Linux kernel patch to remove stack exec Bernd Schmidt (Apr 14)
- mail bombing ;-) Alain Mellan (Apr 14)
- Re: 2nd Linux kernel patch to remove stack exec Andreas Borchert (Apr 14)