[109000] in Cypherpunks
Re: Is PGP crackable
daemon@ATHENA.MIT.EDU (Steve Bryan)
Mon Mar 8 12:13:47 1999
In-Reply-To:
<BEE0F00F81B5D21194A300A0C96CE83DC3282E@exchange01.digifone.com>
Date: Mon, 8 Mar 1999 10:41:03 -0600
To: "Edwards, Benjamin ()" <Benjamin.Edwards@DIGIFONE.COM>
From: Steve Bryan <sbryan@vendorsystems.com>
Cc: cypherpunks@toad.com
Reply-To: Steve Bryan <sbryan@vendorsystems.com>
>I am writing an article about PGP and have one simple question. Can PGP
>keys be cracked. Someone I worked for used to (allegedly) work for the US
>army. He (allegedly) says the army got comms equipment 6 years before it
>was commercially available. If this was the case with computer hardware I
>guess the question would be 'Would it be possible to crack a 4k key if we
>had the computer equipment that would be available in 6 years from now?'
By brute force search of the keyspace (like the EFF key cracker machine for
DES), no. Six years would by conventional estimates produce about four
speed doublings or a factor of 16. The keyspace for a 4K key is simply
mind-boggling. Even the lowly 56 bit keys used by DES constitute a set of
about 72 quadrillion keys. Each time you add a bit you double the keyspace.
The only real vulnerablities would come from more subtle attacks. For
instance there could be an error in the implementation details. This is
much less likely for PGP than other security products because the source
code is publicly available (www.pgpi.com) and faces the possible scrutiny
of thousands of cryptographers. Does anyone actually study it? I don't know
but considerable reputation capital would accrue to anyone who finds a
weakness. Personally, I compile it to verify its correspondence to the
shipping binaries.
Another possibility is a fundamental theoretical breakthrough. For instance
there appears to be work showing that breaking RSA is not equivalent to the
factoring problem. Ignoring that possibility there is no guarantee that the
mathematics of factoring could not experience a breakthrough. Don't forget
that for centuries Fermat's Last Theorem seemed intractable.
Finally, the theoretical foundations of quantum computers appear solid and
imply the possibility (see the work of Shor) of solving the factoring
problem. At this time practical construction of a quantum computer appear
beyond our abilities and certainly not on any engineering timetable.
All of this does not mean use of PGP guarantees security. If your
particular communications represent an important target a black bag job or
"social engineering" will often (usually?) circumvent any technological
measures you casually adopt. On the other hand if you just want privacy
from indiscriminate snooping PGP is wonderful.
Steve Bryan
Vendorsystems International
email: sbryan@vendorsystems.com
icq: 5263678
pgp fingerprint: D758 183C 8B79 B28E 6D4C 2653 E476 82E6 DA7C 9AC5
