PGP ATTACKS


--[Abstract]--
PGP is the most widely used hybrid cryptosystem around today. There have been MANY rumours regarding its security (or lack there of). These have ranged from one that PRZ was coerced by the Gov't into placing backdoors into PGP, to one the NSA has the ability to break RSA or IDEA in a reasonable amount of time, and so on. While I cannot confirm or deny these rumours with 100% certainty, I really doubt that either is true. This FAQ, while not in the 'traditional FAQ format', answers some questions about the security of PGP and should clear up some rumours...

[ The Feasibility of Breaking PGP ]

[ The PGP attack FAQ ]

2/96 v.50 [beta]
by infiNity [daemon9@netcom.com /route@infonexus.com]

-- [Brief introduction] --

This FAQ is a small side project I have decided to undertake. It was originally just going to be a rather lengthy spur-of-the moment post to alt.2600 in order to clear up some incorrect assumptions and perceptions people had about the security of PGP. It has grown well beyond that...

There are a great many misconceptions out there about how vulnerable Pretty Good Privacy is to attack. This FAQ is designed to shed some light on the subject. It is not an introduction to PGP or cryptography. If you are not at least conversationally versed in either topic, readers are directed to The Infinity Concept issue 1, and the sci.crypt FAQ. Both documents are available via ftp from infonexus.com. This document can be found there as well.

PGP is a hybrid cryptosystem. It is made up of 4 cryptographic elements: It contains a symmetric cipher (IDEA), an asymmetric cipher (RSA), a one-way hash (MD5), and a random number generator (Which is two-headed, actually: it samples entropy from the user and then uses that to seed a PRNG). Each is subject to a different form of attack.


1 -- [The Symmetric Cipher] -- 1

IDEA, finalized in 1992 by Lai and Massey is a block cipher that operates on 64-bit blocks of data. There have be no advances in the cryptanalysis of standard IDEA that are publicly known. (I know nothing of what the NSA has done, nor does most anyone.) The only method of attack, therefore, is brute force.


2 -- [The Asymmetric Cipher] -- 2

RSA, the first full fledged public key cryptosystem was designed by Rivest, Shamir, and Adleman in 1977. RSA gets it's security from the apparent difficulty in factoring very large composites. However, nothing has been proven with RSA. It is not proved that factoring the public modulus is the only (best) way to break RSA. There may be an as yet undiscovered way to break it. It is also not proven that factoring *has* to be as hard as it is. There exists the possibility that an advance in number theory may lead to the discovery of a polynomial time factoring algorithm. But, none of these things has happened, and no current research points in that direction. However, 3 things that are happening and will continue to happen that take away from the security of RSA are: the advances in factoring technique, computing power and the decrease in the cost of computing hardware. These things, especially the first one, work against the security of RSA. However, as computing power increases, so does the ability to generate larger keys. It is *much* easier to multiply very large primes than it is to factor the resulting composite (given today's understanding of number theory).


3 -- [The one-way hash] -- 3

MD5 is the one-way hash used to hash the passphrase into the IDEA key and to sign documents. Message Digest 5 was designed by Rivest as a successor to MD4 (which was found to be weakened with reduced rounds). It is slower but more secure. Like all one-way hash functions, MD5 takes an arbitrary-length input and generates a unique output.


4 -- [The PRNG] -- 4

PGP employs 2 PRNG's to generate and manipulate (pseudo) random data. The ANSI X9.17 generator and a function which measures the entropy from the latency in a user's keystrokes. The random pool (which is the randseed.bin file) is used to seed the ANSI X9.17 PRNG (which uses IDEA, not 3DES). Randseed.bin is initially generated from trueRand which is the keystroke timer. The X9.17 generator is pre-washed with an MD5 hash of the plaintext and postwashed with some random data which is used to generate the next randseed.bin file. The process is broken up and discussed below.


5 -- [Practical Attacks] -- 5

Most of the attacks outlined above are either not possible or not feasible by the average adversary. So, what can the average cracker do to subvert the otherwise stalwart security of PGP? As it turns out, there are several "doable" attacks that can be launched by the typical cracker. They do not attack the cryptosystem protocols themselves, (which have shown to be secure) but rather system specific implementations of PGP.


-- [Closing Comments] --

I have presented factual data, statistical data, and projected data. Form your own conclusions. Perhaps the NSA has found a polynomial-time (read: *fast*) factoring algorithm. But we cannot dismiss an otherwise secure cryptosystem due to paranoia. Of course, on the same token, we cannot trust cryptosystems on hearsay or assumptions of security. Bottom line is this: in the field of computer security, it pays to be cautious. But it doesn't pay to be un-informed or needlessly paranoid. Know the facts.

-- [Thank You's (in no particular order)] --

PRZ, Collin Plumb, Paul Kocher, Bruce Schneier, Paul Rubin, Stephen McCluskey, Adam Back, Bill Unruh, Ben Cantrick and the readers of sci.crypt and the comp.security.* groups,


Return to Cryptography Page

Comments to W. Unruh