28 January 1999. Thanks to Sam Simpson.
Source: http://www.hertreg.ac.uk/ss/pgpfaq.html

Archive-name: PGP-DH-RSA
Version: 1.1
Last-modified: Wednesday, 27th January 1999

Copyright © 1999 S.Simpson - All Rights Reserved
Sam Simpson - http://www.hertreg.ac.uk/ss/

All information contained in this work is provided "as is." All warranties, expressed, implied or statutory, concerning the accuracy of the information of the suitability for any particular use are hereby specifically disclaimed. While every effort has been taken to ensure the accuracy of the information contained in this work, the author assume(s) no responsibility for errors or omissions or for damages resulting from the use of the information contained herein. This work may be copied in any printed or electronic form for non-commercial, personal, or educational purposes if the work is not modified in any way, provided that the copyright notice, the notices of any other author included in this work, and this copyright agreement appear on all copies.

Sam Simpson also grants permission to distribute this work in electronic form over computer networks for other purposes, provided that, in addition to the terms and restrictions set forth above, Sam Simpson and/or other cited authors are notified and that no fees are charged for access to the information in excess of normal online charges that are required for such distribution.

This work may also be mentioned, cited, referred to or described (but not copied or distributed, except as authorised above) in printed publications, on-line services, other electronic communications media, and otherwise, provided that Sam Simpson receives appropriate attribution.

IDEA(tm) is a trademark of Ascom-Tech AG. PGP and Pretty Good Privacy are trademarks of Network Associates, Inc. All other products mentioned are registered trademarks or trademarks of their respective companies.

Comments about, suggestions about or corrections to this document are welcomed.

Recent Changes

v1.1 - 27th Jan 1999
      Added section "In respect of RSA, what are strong primes?"
      Added section "The PGP implementation of DH is based on Galois Fields, aren't they broken?"
      Added section "How 'computationally hard' are symmetric keys?"
      Added section "How does multiple encryption affect security?"
      Added section "Why perform signing before message encryption?"
      Added section "Get the threat in perspective!"
      Added detail to "What is DH / ElGamal?"
      Added detail to "Which is stronger, RSA or DH/DSS? "
      Added detail to "What is 3DES?"

v1.01 - 15th Jan 1999
      Minor grammar / spelling related changes
      Some technical changes - mainly to notes.

Table of Contents

1. Introduction

2. Public Key Algorithms in PGP

3. Hash Function Algorithms in PGP

4. Conventional Encryption Algorithms in PGP

5. Key Revocation Certificate issues

6. What would it take to "break" PGP?

7. Other issues

8. Conclusion

9. Further Reading

10. Notes

11. Acronyms

12. References


Primarily, sincere thanks to Kurt Mueller for providing the Key Revocation Certificate section. Also, many thanks to Dan "the" Horne & Andy Jeffries for proof reading this document while it was rough-and-ready.

Thanks to the following people who have helped (unwittingly in some cases) in the production or revision of this FAQ:

1. Introduction

"Documentation is like sex: when it is good, it is very, very good; and when it is bad, it is better than nothing."
-- Dick Brandon

This document aims to answer several of the most common PGP related questions posed in comp.security.pgp.discuss, alt.security.pgp, sci.crypt etc:

  1. Has PGP been broken?

  2. Which version of PGP is stronger, RSA or DSS/DH?

  3. Why doesn't PGP support RSA as standard anymore?

  4. Is PGP cryptographically less secure than S/MIME?

  5. Why does PGP use 3DES? DES is broken, right?

The move from PGP v2.x to v5+ has brought about several major advances. The primary change has to be the User Interface (UI) improvements. The other major change is the move from RSA to DH/DSS keys. This has been a contentious issue, but one that I subjectively believe has been made with good reason. Hopefully this document will help to explain the rationale for certain changes and put concerned users' minds at rest.

In fact, by the end of the FAQ it should be clear that PGP / NAI had to change the implementation of PGP in ways that would have necessarily retired existing RSA keys.

This FAQ tries to remain objective in its approach and offers copious references to material authored by the most eminent cryptographers. Some may argue that this FAQ exhibits an excessive number of references, but I believe this is necessary to allow users to substantiate the claims I have made. After all, why should you trust what I say ;-)

This FAQ assumes that you have previously read (and understood!) the PGP v6.02 User Manual, especially the section "Phil Zimmermann on PGP". I would also recommend that the reader downloads the RSA FAQ [RSA98], but be aware that RSA has a commercial interest in PK cryptography.

About the author

Sam Simpson is a Computer Science graduate of the University of Hertfordshire and has also attended postgraduate Information Security / Cryptography courses at the University of London.

He is heavily involved with the freeware ScramDisk project and also with improving the implementation efficiency of Serpent, an AES candidate. He had the "honour" of being the first to distribute PGP v6.0 outside of the US, after the program was anonymously mailed to him [WIR98].

Sam is an ardent privacy advocate and, as such, considers himself "vendor neutral" towards this goal. He is currently employed as a Communications Analyst specialising in Internet security and has previously been an application / systems developer.

2. Public Key Algorithms in PGP

2.1. What is RSA?

RSA was announced in 1978 [RSA78]. The security of the RSA system is based upon the RSA Problem (RSAP). This problem is conjectured (but not proven) to be equivalent to the Integer Factorisation Problem (IFP) [MOV96], [Sti95].

From [MOV96] the RSAP is: "given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e,(p-1)(q-1))=1, and an integer c, find an m such that me is congruent to c (mod n)." Basically RSAP involves finding eth roots modulo a composite integer.

There is not a lot to be said about the RSA algorithm that hasn't been said in the PGP manual or in the RSA FAQ. [Bon98] summarises nicely the security of the RSA system after twenty years of use.

Recently, RSA has been diminished as the algorithm of choice in PGP. It is no longer supported in the freeware version of PGP, due to a number of issues (see later sections).

Note 2 contains a brief overview of how RSA is actually performed in PGP. An observant reader will note that PGP keeps more parameters in the private key than is strictly necessary, this is to speed up computation via the Chinese remainder theorem [Sch96a].

2.2. What is DH / ElGamal?

Diffie-Hellman (DH) was the first publicly published public key system [DH76] (more correctly Diffie-Hellman is a key-exchange mechanism) and as such has received extensive analysis by eminent cryptographers.

PGP actually implements ElGamal [ElG85], which is a public-key encryption variant of the Diffie-Hellman Problem (DHP). It has been proven that the ElGamal encryption scheme is equivalent to the DHP [MOV96], [TY98], [Sti95] - that is to say that if one can break either ElGamal or DH then you also break the other (see Note 1).

The security of the DH system is based upon the DH Problem (DHP). This problem is conjectured (but not proven) to be equivalent to the Discrete Logarithm Problem (DLP) [MOV96], [Sti95], [Odl83].

DHP is equivalent to the Discrete Logarithm Problem (DLP) under the "Diffie-Hellman assumption" [Kob94]. This assumes that it is unfeasible to compute gab knowing only ga and gb. To quote [Kob94] "...no one can imagine a way of passing from ga and gb to gab without first being able to determine a or b; but it is conceivable that such a way might exist".

There are several downsides to using DH compared to using RSA:

  1. The requirement for a secure Random Number Generaton (RNG). A cryptographically secure RNG is already available (See section 7.7).

  2. Major message expansion. The size of the message doubles once encrypted. This however is not an issue as ElGamal is only used to encrypt the session key to each recipient.

  3. Speed. Encryption using ElGamal is slower than RSA. See section 2.11 for further details.

The other side of the coin is that there are several benefits to using DH/DSS over RSA:

  1. ElGamal is totally unencumbered by copyright and patents. This means that ElGamal can be used globally without the need for licensing. RSA, however, needs licensing from RSA Labs for use in commercial products. RSA does provide free licenses for RSA, but there are some prohibitive licensing issues (see section 7.3).

  2. Using RSA, someone could generate a fake prime or one of a special form that facilitates factoring. Without access to the private key it is simply impossible to check. [Sch96a] describes a method of checking that the numbers used in DSA/DH are computed randomly and are indeed prime.

  3. RSA is not appropriate for use in situations where key generation occurs regularly (e.g. for each message), such as in systems that employ ephemeral keys [SH97].

Some have complained that calling the implementation of ElGamal used in PGP Diffie-Hellman is somehow misleading, the facts certainly don't support this view. Recall that ElGamal is in fact a Diffie-Hellman variant and that the two systems are proven cryptographically & mathematically equivalent.

Note 3 contains a brief overview of how DH is actually performed in PGP.

2.3. What is DSS?

DSS stands for Digital Signature Standard and is formally defined in [FIPS186] & [ANSI930-1].

DSS employs the ElGamal and Schnorr PK systems to produce a fixed width signature (irrespective of the public/private key size). In contrast, RSA signature length is a function of the key length employed.

The DSS uses discrete exponentiation modulo a prime p, the exponents are computed modulo a prime q. A signature produced with DSS is likely to remain safe for at least 20 years [Odl95]. Time stamping and "paper trail" mechanisms can be used with DSA if longer-term signature verification is required.

DSS is thought to be secure assuming that a good RNG is used. Serge Vaudeny has an interesting attack on DSS that allows a Birthday Attack in only 274 steps, rather than the expected 280 when using "weak keys" [Vau96]. This attack is of no practical concern, and the weak keys are easily detected.

2.4. What is the chance of producing a composite instead of a prime with PGP?

Slim. Very slim indeed.

From [PGP97], the chances of the prime number generation routines in PGP v5.0 producing a composite instead of a prime (that is to say, a number that passes the probabilistic tests) for a 1024-bit key (e.g. a 512-bit candidate prime) are 10-44.

To put things in perspective, the chances of another "Dinosaur Killer asteroid" hitting the earth TODAY are 2-36.

2.5. How big should my asymmetric key be?

NOTE: According to current mathematical & cryptographic knowledge, this section applies approximately equally to DH & RSA keys. (If anything, DH keys are more secure, but the difference currently appears marginal).

When choosing an asymmetric key size, we are constrained by two principles:

  1. Security. One of key factors of the strength of systems like PGP is the size of the public / private key pairs.

  2. Speed. The longer a key, the slower the public key operations.

For the majority of users, the main factor in the selection of PK size will be security. Speed is very rarely a determining factor, due to the following reasons:

  1. The public key algorithm is not actually used for bulk encryption, instead it is just used to encrypt the session key to each recipient.

  2. Computers are so fast these days that the difference in signing or encrypting with a 4096-bit key has only a negligible performance hit compared with a 512-bit key.

The following table, from [Sch96a] lists the recommended public key length to protect against attack by a single corporation (keys should be substantially bigger to protect against intelligence agencies!):
Year Recommended Key Length
1995 1280
2000 1280
2005 1536
2010 1536
2015 2048

Table 1: Recommended assymetric key lengths

Schneier has since commented on these figures [Sch98e]: "In PGP, for example, breaking the symmetric algorithm yields one message. Breaking the public-key algorithm yields all messages."

You really need to consider how important your messages are, the "lifetime" of the messages (e.g. how long will the data need to be protected for) and your likely adversary.

Key lengths of 10,000 bits or more can sometimes be necessary, for example for protecting key-signing keys owned by a CA, or for storing data that will remain sensitive for a very long period [Odl95].

We know that 512-bit keys have been insecure for some time now [Sch96a], [Odl95], [Rob95]; a well-funded adversary could certainly break these size keys (even if it does take a month or two). In reality, an adversary wouldn't even need to be well funded - they would just need access to a large network of computers. The adversary could thus be a computer manufacturer, a large corporation (using idle time on computers) or a co-ordinated effort.

PGP allows only the creation of keys >= 768-bits, so the naïve user is afforded some protection from creating an excessively weak key. The question still remains however, what is a "reasonable" size key?

Personally, I would suggest creating asymmetric encryption keys no smaller than 2048-bits. Why so large? Well, assuming "reasonable" advances in number theory and computing power, along with the growth of distributed computing via the Internet, a 1024-key will only offer guaranteed security (assuming the RSAP / DLP is indeed intractable) for a period of around 5-years [Odl95]. No demonstration of breaking a 768-bit key has been performed, but one must assume that it is now feasible [Sil97].

Any major advance in factoring algorithms, computer speed, computational power available in a distributed effort etc would adversely affect the security both DH / RSA. Remember that the fastest algorithms for factoring and computing discrete logs are now sub-exponential - so any increase in computing power affects to a large degree the security afforded by public keys.

We would do well to remember one of the basic maxims of information security: "Cryptography is about making the cost of retrieving a message much higher than the value of the message itself."

For further details of recommended key sizes, refer to [Sch96a], [Sch96b]. For a great paper discussing the future prospects for integer factorisation see [Odl95].

2.6. The huge key debate.

Cyber-Knights Templar has produced an amended version of PGP v5.5 that supports the following enhancements:

  1. Support for RSA keys up to 16,384 bits in length. Signatures using keys of this size take around 2.5Kb :-)

  2. Support for DH keys up to 8192 bits and DSS keys up to 2048.

There are some arguments about the use of these gigantic keys. Some argue (including Phil Zimmermann [Zim98b]), that keys of this size are of absolutely no use.

I don't particularly agree with the day to day use of keys which are this large as they are tediously slow, but I do partially disagree with Phil's argument...If an adversary breaks a PGP symmetric key, then the adversary can read a single message. If the adversary breaks an asymmetric key, then they can read all messages, past, present and future (and forge signatures if an RSA key is being used).

There is therefore a reasonable argument for using asymmetric keys that offer security in excess of that provided by the underlying symmetric cipher [Sch98e], [Sim98].

Still, if an adversary manages to break a > 3000-bit PGP key (either RSA or DH) today, then it is likely to have occurred either due to a mathematical breakthrough or through a broken implementation which would thus render any size asymmetric keys ineffectual.

Future versions of PGP will support the AES block cipher standard with a keysize of 256-bits - then users will justifiably be able to use larger keys. For now, I would suggest only using very large keys under extreme circumstances.

Users should also be reminded that DSS keys greater than 1024 are no longer compliant with the official DSS standard [FIPS186] and thus should be called something else.

Users should be warned that the "official flavours" of PGP v5+ will not support DSS keys in excess of 1024-bits and DH keys in excess of 4096-bits.

2.7. Why does PGP use precomputed primes for DSS/DH?!?

One worry when PGP v5 was first released was the use of precomputed or "canned" primes for the values of the finite field and the generator of this field (p & g respectively) in DH, and p & q for DSS.

This fear is totally unfounded, it is quite acceptable to use public, precomputed values for these values [Sch96a], [FIPS186], [MOV96], [Kob94], [Sti95]. I would also recommend that the concerned user reads [Sch97a].

The truly paranoid user can choose to switch off the "Faster key generation" if desired (and be prepared to wait far longer for the production of keys). I am however, yet to find any literature that supports this paranoid view!

2.8. In respect of RSA, what are strong primes?

Historically, it was desirable to select strong primes (p & q) for use in the RSA system. These strong primes helped defend against Pollard's p-1 factoring algorithm. More recently however faster factoring algorithms have been discovered that work just as well against strong primes, so there isn't any real advantage to using these strong primes.

PGP doesn't use "strong" primes...

I would currently recommend against the use of strong primes:

  1. They don't offer any additional security against modern factoring algorithms.

  2. These "strong" primes may actually be more susceptible to modern attacks. For example the ANSI standard X9.31-1997 details a number of criteria which should be used to create the primes used to make up the RSA modulus. One of the criteria actually makes the modulus easier to factor via the SNFS [Sil97]!

It may be necessary in the future to once again rely on "strong" parameters when using the RSA system - but at the moment prime length is far more important than structure [Sil97], [Sch96a], [MOV96].

2.9. The PGP implementation of DH is based on Galois Fields, aren't they broken?

No. There are two general types of Galois Fields with cryptographic significance, GF(p) with p prime, and GF(2n).

When first introduced, GF(2n) was the preferred implementation, basically because it is easier to implement in hardware [Sch96a], [Odl83]. However, this was shown to be relatively insecure. The field GF(p) where p is around 2750 and is prime is thought to offer roughly the same security as GF(2n) where n is around 2000. Clearly, the Galois Field GF(p) offers better security for the same parameter size.

It is unfortunate that these two systems, though related, are both often discussed in the same breath - theory in one field isn't necessarily applicable in the other field.

Anyway, PGP implements Diffie-Helmman over GF(p) which, as we'll see later, is still secure.

If you are still interested in the relation between GF(p) and GF(2n) then I most highly recommend [Odl83].

2.10. Which is stronger, RSA or DH/DSS?

Both of these algorithms are based on supposedly intractable problems that have been subjected to scrutiny by the world's finest mathematicians and cryptographers. The asymptotics of RSA and DH based systems are similar but in practice RSA keys appear more vulnerable [Sch98f].

It is, in fact, slightly harder to compute discrete logs modulo an appropriate prime than to factor a "hard" integer of the same size - so RSA would appear slightly weaker than DHP [Odl95].

It is thought possible, though unlikely, that there is a polynomial way to generally factor large numbers or compute discrete logarithms. There is also the chance that the RSAP or DHP could be broken without having to solve the underlying "hard" problem (IFP / DLP respectively).

Discussing the DLP & IFP, [RSA96a] states: "This suggests that the degrees of difficulty of both problems are closely linked, and that any breakthrough, either positive or negative, will affect both problems equally."

And to quote [Sch96a]: "Computing discrete logarithms is closely related to factoring. If you can solve the DLP then you can factor."

Another relevant quote [Wie98]: "The most important factor in choosing a public-key technology is security. Based on the best attacks known, RSA at 1024 bits, DSA and Diffie-Hellman at 1024 bits, and elliptic curves at about 170 bits give comparable levels of security."

One notes the interesting statement in [Odl83]: "In general, while there are algorithms for factorization that do not generalize to give discrete logarithm algorithms (the Schnorr-Lenstra algorithm, for example), the converse is not the case. Therefore it seems fairly safe to say that discrete logarithms are at least as hard as factoring and likely to remain so." Or, in English, all currently known algorithm for solving the DLP can be applied to the IFP, whereas the reverse is not always the case.

IF DH is broken by solving the DLP then RSA will also fall, since if you know how to take discrete logs then you can factor (that is the basis of Shor's quantum factoring algorithm [Sho94]). Thus, DLP would seem stronger than the IFP, since factoring does not allow you to solve discrete logs [MOV96]. More rigorously; "the Diffie-Hellman problem in Z *n is at least as difficult as the problem of factoring n."

I am unaware of any literature that states or predicts that either DH or RSA are, in operation, more or less secure than the other given correct implementation and parameter selection.

From a security perspective, one good argument for using DH/DSS keys is the fact that the encryption and signature keys are now autonomous. Thus if someone manages to obtain your DH private key (for example by brute forcing the key or by court order) they will be able to read all mail sent to you. They will not be able forge signatures however. Compare this to RSA, where divulging a key allows someone to both read all mail and forge signatures. See the further discussion in section 7.4, which covers the compelled production of keys.

PGP Version 6.0 provides the ability to create and revoke new encryption keys without sacrificing your master signing key and the signatures collected on it. This feature would not have been possible with the old style RSA keys.

In the words of Cylink [CYL98b]: "Diffie-Hellman based systems can be used in place of RSA in any application requiring public-key cryptography."

2.11. Any recent developments?

Number theory is a fast changing topic. Recently, several developments and proofs have affected the problems that both DH & RSA keys are based upon.

Obviously, proof that either DH or RSA is computationally equivalent to the underlying problem (DLP and IFP respectively) drastically enhances the confidence that should be placed in the public key system.

I briefly highlight relevant papers and try to identify how they affect the security of the asymmetric algorithms utilised in PGP.

"Generalized Diffie-Hellman modulo a composite is not weaker than factoring" [BBR98]
Implications: Some classes of the DHP are not computationally weaker than the IFP.

"Breaking RSA may not be equivalent to factoring" [BV98]
Implications: Provides evidence that certain instances of RSA cannot be equivalent to the IFP. This is contrary to the belief by some that RSA and IFP are equivalent.

"On the Complexity of Breaking the Diffie-Hellman Protocol" [MW96]
Implications: Provides a proof that some classes of the DHP are equivalent to the underlying DLP.

Basically, there have been some significant steps to prove the security of DHP is equivalent to DLP, while no such proof may be available for showing the equivalence between RSA and IFP. This may have long term security ramifications for RSA based keys.

2.12. What are the performance differences for encryption between RSA & ElGamal?

Encryption timings (in milliseconds on a Sparc II) from [Sch96a]:
(1024-bits, 160-bit exp)
Encrypt 8 109
Decrypt 93 77

Table 2: Assymetric encryption speed comparison

Messages are enciphered once but may be decrypted many more times - thus ElGamal is considered better in terms of performance.

Note that the asymmetric cipher is only used to encrypt the random session key - so performance hit is negligible. These figures may impact low cost (e.g. smart cards) or high throughput environments.

2.13. What are the performance differences for signing between RSA & DSS?

Digital signature timings (in milliseconds on a 200 MHz Pentium Pro) from [Wie98]:
RSA-1024 (e=3) DSA-1024
Sign 43 7
Verify .6 27
Key Gen 1100 7
Param Gen 0 6,500

Table 3: Assymetric signature speed comparison

One can see that producing digital signatures using the DSA scheme is much faster than under RSA, assuming identical key lengths. Signature verification is far faster under RSA.

Signatures are created once but may be verified many more times - thus RSA is considered better in terms of performance.

In real world use, the performance difference between these two systems will go unnoticed. It is more likely to be an issue in low cost (e.g. smart cards) or high throughput environments.

3. Hash Function Algorithms in PGP

3.1. What is a Hash Function?

A cryptographic hash function takes an arbitrary length message as input and produces a fixed length output. The input is typically a file or a message. The output of the hash function is called a Message Digest, hash value or message fingerprint.

By their very nature, hash functions are many to one - that is to say there will certainly be more than one input message that produces a given hash value. The purpose of the hash function is to make the job of finding such "collisions" computationally unfeasible.

Being able to produce collisions for a hash function in reasonable time renders a hash function ineffectual.

Most modern hash functions are built from a compression function, which is iterated on the input stream. Like a complete hash function, a compression function can suffer from collisions. The precise design of the hash function dictates how detrimental compression function collisions are to the security of the overall hash function - but a collision free compression function is necessary for an overall secure iterated hash function [MOV96].

3.2. What is a "checksum"?

A checksum or CRC function etc is a non-cryptographic mechanism for detecting transmission errors [MOV96], [RSA98].

PGP uses a checksum value to:

  1. Produce non-cryptographically secure pseudo-random numbers. A strong PRNG exists for the production on numbers that need cryptographic security.

  2. Checking whether a message has been corrupted during transit. Note that this is in addition to any cryptographically secure method of error detection.

Note that the checksum function is only used in areas that don't require cryptographic strength. When cryptographic strength is required, PGP uses a hash function.

3.3. What function does a hash algorithm perform in PGP?

The hash function is responsible for two primary tasks in PGP:

  1. Creation of Digital Signatures. The message is passed through the hash function and the resulting hash value is signed with the users private key.

  2. Obfuscation of the passphrase. Passphrases are passed through the hash algorithm to produce a "fingerprint" which is then used by the symmetric cipher to decrypt the private keyring.

It is therefore important that the hash function has the following two characteristics:

  1. The function is One Way - that is to say it should be "hard" to find a message that hashes to a pre-specified value.

  2. The function is Collision Resistant - that is to say it should be "hard" to find two messages that hash to the same value.

3.4. What is MD5?

MD5 is a hash function by Ron Rivest [RFC1321]. It is an enhanced version of the MD4 hash function (MD4 has been totally broken [RSA98]).

MD5 has been included in PGP since inception, but has recently been deprecated due to several security concerns (see section 3.7). MD5 seems to have been a catalyst for the changes that we have seen post PGP v2.x.

MD5 is supported in S/MIME (v3) only for [IETF98]: "providing backward compatibility".

3.5. What is SHA-1?

SHA-1 is the current hash function of choice as implemented in both the PGP and S/MIME standards. SHA-1 is formally defined in [FIPS180-1], [ANSI930-2] & [ISOIEC10118-3].

SHA-1 is based upon the MD4 algorithm, but was enhanced by NIST / NSA. The output of SHA-1 is 160-bits.

SHA-1 has been extensively analysed but to date there have been no successful attacks.

3.6. What is RIPE-MD?

RIPE-MD is another hash function derived from MD4. It is formally defined in [DBP96].

To date there have been no successful cryptanalysis of RIPE-MD. PGP implements RIPE-MD160, which produces an output of 160-bits.

3.7. Has MD5 been broken?

Not totally. First, pseudo-collisions in the compression function were found by den Boer and Bosselaers [BB94] then collisions in the compression function were found by Dobbertin [Dob96].

This doesn't mean that collisions have been found in the full hash function, but it does mean that MD5 shouldn't be used in situations where collision resistance is required [Dob96], for example in the creation of digital signatures (the main application of a hash function in PGP). To quote Hans Dobbertin directly [Dob96]: "Therefore we suggest that in the future MD5 should no longer be implemented in applications like signature schemes, where a collision-resistant hash function is required. According to our present knowledge, the best recommendations for alternatives to MD5 are SHA-1 and RIPEMD-160."

One should be reminded that the design goal of MD5 was to build a CRHF from a collision resistant compression function [Sch96a], [MOV96], this design goal has now been violated.

In the words of RSA Labs [RSA96b]: "With regards to existing applications which use MD2 and MD5, collisions for these hash functions have not yet been discovered but this advance should be expected...RSA Laboratories currently recommends that in general, the hash function SHA-1 be used instead but RIPEMD-160 would also be a good alternative."

[MOV96] says: "An iterated hash function is thus in this regard at most as strong as its compression function".

A further complaint about MD5 is the 128-bit output. This is insufficient for long term security [PBD97] & [Sch96a].

Overall, Schneier says [Sch96a] "I am wary of using MD5".

One also notes that MD5 is supported in S/MIME (v3) only for [IETF98]: "providing backward compatibility". It would seem foolish to continue to use technology that is so dubious when far superior unencumbered algorithms are available.

To summarise, there are three main concerns about the use of MD5:

  1. Pseudo-collisions have been found in the compression function.

  2. Collisions have been found in the compression function. This violates the design goals of MD5.

  3. The hash function only returns 128-bits, which is insufficient for long term security.

An ignorant view is that "MD5 is secure until someone demonstrates a break" - this is just not true. For example, we knew that DES was ineffectual against a determined adversary even before the Internet and later the EFF broke the cipher. I think Schneier has the right idea on this subject [Sch96b]: "History has taught us: never underestimate the amount of money, time, and effort someone will expend to thwart a security system. It's always better to assume the worst. Assume your adversaries are better than they are. Assume science and technology will soon be able to do things they cannot yet. Give yourself a margin for error. Give yourself more security than you need today. When the unexpected happens, you'll be glad you did."

3.8. Was the original SHA broken?

The only difference between SHA-1 and SHA is the inclusion of a one-bit rotation in the block expansion from 16 to 80 words - something to do with "linear error correction codes", apparently [MOV96]. The interested reader is referred to [CJ98] for an in-depth analysis of attacks against the original SHA.

To answer the question, it would appear that SHA was not broken, but may have been susceptible to an advanced attack.

Anyway, it's nice to see that the faceless NSA cryptographers are only human too!

3.9. Which is stronger, MD5, SHA-1 or RIPE-MD?

Certainly not MD5 (see section 3.7).

The choice would therefore appear to be between SHA-1 and RIPE-MD. Neither of these has succumbed to any known attacks and the finest cryptographers in the field produced both.

SHA-1 is the standard used in PGP v5+ and there is absolutely no reason to doubt this choice [Sch96a], [PGP98], [RSA96b], [MOV96], [Dob96]. The PGP manual [PGP98] summarises the cryptographic communities feelings on SHA-1: "SHA has been published in the open literature and has been extensively peer-reviewed by most of the best cryptographers in the world who specialise in hash functions, and the unanimous opinion is that SHA is extremely well designed."

I am yet to find a single quote that casts doubt on the cryptographic security of SHA-1.

3.10. What are the performance differences between MD5, SHA-1 & RIPE-MD?

Hash function timings (in Mbit/s on an unspecified platform) from [PBD97]:
Assembly 136.2 54.9 45.3
C 59.7 21.2 19.3

Table 4: Hash function speed comparison

MD5 may be fast, but remember that it is relatively insecure.

4. Conventional Encryption Algorithms in PGP

4.1. What is a conventional encryption algorithm?

A conventional encryption algorithm is a function that maps an n-bit plaintext block to an n-bit ciphertext block where n is the blocksize. Typically, n is equal to 64 or 128-bits.

The function takes a parameter, the "key" which specifies which mapping between the plaintext and ciphertext is used.

Block ciphers are, given the same key, invertible.

4.2. What function does a conventional encryption algorithm perform in PGP?

Block ciphers are used in numerous areas of PGP:

  1. Bulk encryption of data. Session keys are encrypted with the public key algorithm, and then the bulk of data is encrypted with a conventional block cipher. This is done for reasons of security and speed.

  2. Maintaining the pool of random data.

  3. Encrypting the private keyring. This keyring holds the private decryption key(s) and it is imperative that this file is encrypted in a "secure" manner.

4.3. What is IDEA?

IDEA is a strong block cipher by Xuejia Lai and is formally defined in [Lai91].

IDEA is an 8-round cipher with a 64-bit block size and uses keys of 128-bits. The strength of the cipher is provided by "mixing operations from different algebraic groups". IDEA is resistant to both differential [LMM91] and linear cryptanalysis [Sch96a]. Currently, there is no known way of breaking IDEA short of brute force [Sch96a].

From [RSA96a]: "IDEA is generally considered secure and both the cipher development and its theoretical basis have been openly and widely discussed."

The best known attacks on IDEA are:

  1. Chosen-key differential attack on a very much weakened version of the cipher with 3-rounds [KSW96].

  2. Chosen-key ciphertext-only timing attack on the full cipher that requires 5x217 related key queries, each used to perform 220 random unnamed plaintext blocks [KSW96].

  3. A combination of both differential and linear cryptanalysis which requires 229 chosen plaintext pairs and a workload of 249 additions modulo 216+1 on a very much weakened version of the cipher with 3-rounds [Bor96].

  4. An impossible cryptanalysis attack by Biham and Shamir - details are sketchy (to say the least!) but this is the best attack on IDEA to date [Sch98h].

None of these attacks are useful in breaking practical implementations of IDEA. Full IDEA is strong against differential, linear, and related- and chosen-key attacks, though there is an interesting side channel attack that can be undertaken on an implementation of IDEA that allows high-resolution timing [KSWH98b].

IDEA is no longer the default cipher of choice in PGP due to patents issues (IDEA requires a license for commercial use).

4.4. What is CAST?

CAST is a family of block ciphers by Carlisle Adams and Stafford Tavares. PGP v5 implements a version of CAST known as CAST5, or CAST-128. This version of CAST is the most standard cipher that people usually mean when they say "CAST". CAST is formally specified in [RFC2144].

This version of CAST has a blocksize of 64-bits and a key length of 128-bits. It is resistant to both linear and differential cryptanalysis [Sch96a]. Currently, there is no known way of breaking CAST short of brute force [Sch96a].

There are no known attacks on CAST with reduced rounds- it looks incredibly secure.

CAST is now the default cipher in PGP.

4.5. What is 3DES?

DES is formally defined in [FIPS46-2] and Triple-DES (3DES) in [ANSI952].

Recently, NIST has suggested that FIPS46-2 should be superceded by the Triple-DES alogrithm, which we expect to be formally approved as [FIPS46-3]. This is primarily due to the cracking of DES keys in under a day by the EFF.

3DES consists of three applications of the DES cipher in EDE configuration with independent keys. Encryption is executed as follows:

CipherText = DESk1(DES-1k2(DESk3(PlainText)))

And decipherments is:

PlainText = DES-1k3(DESk2(DES-1k1(CipherText)))

3DES has a block size of 64-bits and a key length of 168 (3×56). Because of the construction of 3DES, it is thought to offer strength equivalent to a 112-bit block cipher [BK98].

The best known attacks on 3DES are:

  1. Meet In The Middle (MITM) attack. This kind of attack can be theoretically be used against any multiple encryption. In the case of DES this attack requires 524,288 Terabytes of storage, 2112 encryptions and 2112 table lookups [MOV96], [Luc98].

  2. Optimised MITM attacks. Time / memory tradeoffs applied to the standard MITM attack that can make the MITM slightly more feasible [Luc98]. 2108 operations are still required for the "feasible" (in terms of memory) attacks.

  3. Related key attack. Needs one chosen related-key query, one chosen-ciphertext query and 256 to 272 offline trial encryptions [KSW96].

These attack are not useful in breaking practical implementations of 3DES.

4.6. Has 3DES been broken?

No. "Single" DES has been successfully brute forced by the EFF using a custom built cracking machine in just 56 hours [EFF98]. Brute force basically involves trying all possible 256 keys until the correct one is found. Brute force takes, on average, 2KeyLen-1 operations - so in the case of DES the machine has to try approximately 255 trial decryptions before being rewarded with the correct plaintext.

More recently, the third DES challenge posed by RSA was cracked in under a day by the EFF machine [EFF99]!

Triple-DES is at least 256 (approx. 1017) times harder to break than single DES [CYL98a] and as such can be considered very secure. An adversary would have to try on average 2111 keys in order to break a single 3DES message (and would need a large amount of storage space to keep intermediate values). It is important in multiple encryption schemes that the underlying cipher is not a group; fortunately Campbell & Wiener have shown that DES is not a group [CW93].

Properly implemented 3DES is still thought to be very strong [Wag94], [Sch96a], [MOV96], [RSA96a], [RSA98], [Sch98f]. In fact, I have not been able to find a single cryptographer who has cast doubt upon the strength of 3DES.

In the words of [CYL98a]: "Since triple-DES is 1017 stronger than single-DES, we do a little arithmetic and find that this $300M computer can break a triple-DES key in about 4x1010 years, or about the age of the universe."

In the words of Bruce Schneier [Sch98f]: "Certainly triple-DES is a better choice than AES, in some applications. Triple-DES will probably be the algorithm of choice for many banking applications even after AES is approved as a standard."

Finally, in the words of Dorothy Denning [Den98]: "Triple DES has not been broken and its security has not been compromised."

4.7. Has CAST been broken?

As previously mentioned, CAST is a family of ciphers. Some of the other "CAST" ciphers have succumbed to advanced attack (Rijmen and Preneel have attacked some CAST designs and so have Kelsey, Schneier & Wagner [KSW97]). The same attacks have been tried against the implementation of CAST used in PGP and have, thus far, failed.

4.8. Which is stronger, IDEA, CAST or 3DES?

This is a contentious and subjective issue. None of these algorithms has either been broken or had any serious doubts cast upon their strength.

Some people don't trust 3DES because it is based upon DES, which is produced by the NSA. However, respected cryptographers hold 3DES in very high regard.

CAST5, as implemented in PGP, has not been subjected to any successful analysis, but Bruce Schneier has said the following [Sch98a] "I give a big yuk to CAST-128" and [Sch98c] "I don't buy the design process.".

IDEA is possibly the second most widely known cipher (after DES). This is mainly due two to influences:

  1. The good write-up in Applied Cryptography [Sch96a].

  2. Its inclusion as part of PGP.

IDEA appears to have been held back due to patent issues. Without these, I don't doubt that IDEA would now be the de facto standard. [RSA96a] says the following about IDEA: "IDEA is generally considered secure and both the cipher development and its theoretical basis have been openly and widely discussed."

More recently IDEA seems to have fallen out of favour (possibly due to the small block size compared to the AES candidates). Recently Bruce Schneier has said the following about IDEA [Sch98d]: "For the record, I am less enamoured of IDEA these days. It is still secure, in that there are no published attacks, but I like other algorithms a lot better."

When recently posed with the question "Which among the following is considered to be the most difficult algorithm to crack; RC6, IDEA, CAST, 3DES, Blowfish" Bruce replied [Sch98b] "Triple-DES. Without any doubt. Nothing else has had anywhere near the analysis." He has also said [Sch98a] "If you want to be conservative, use Triple-DES."

The NSA objected to the 3DES algorithm becoming an ANSI X9 standard with the comment [Fro95]:

So, it can't be all bad!

I am personally reassured by the presence of three strong algorithms in PGP. If any of these algorithms were broken, even though this development appears unlikely at the moment, then PGP users could simply disable the broken algorithm and use one of the still secure algorithms. Compare this to users of standards (e.g. S/MIME) that are forsaken with only one secure cipher.

In summary, none of the algorithms implemented in PGP v5+ are broken, or anywhere near broken. PGP will certainly add the AES cipher once selected and this should then be adopted as the symmetric algorithm of choice. For now, it would appear that 3DES is the symmetric algorithm of choice for pessimists [Wag94], [Sch96a], [Sch98f].

4.9. How "computationally hard" are symmetric keys?

To be honest, I wasn't looking forward to writing this section. Whatever I write is bound to be wrong one way or the other, and may be subject to serious misinterpretation.

The first thing to say is that all these figures assume that brute force is the best attack (or in the case of 3DES MITM). If an adversary manages to find a practical cryptanalytic method of bettering the workload required, then these figures can be reduced accordingly.

Secondly, if QCs or DNA computing become a reality, or if Moore's law is a gross underestimate of the growth in computer power, then again this section is useless.

So, back to the question... To brute force the symmetric ciphers now under a number of assumptions:

  1. Every single computer (estimated at 3×108) on the earth is used full time.

  2. Every computer has the processing power of a PII 450Mhz.

Then a single key can be brute forced in an average of 1011 (more precisely 457,351,814,728) years. This assumption is from some perspectives very optimistic (from an adversaries perspective); can all computers be harnessed in one go and are they all running at the speed of a PII 450? No.

This figure is worked out by: 2(KeyLen-1) / (NumComputers) / NumOpsPerYear or: 2111 / 3×108 / 18,921,600,000,000

These figures are "a little" pessimistic from another angle:

  1. It is assumed that computing power will remain constant.

  2. It is assumed that the number of computers remains constant.

To try and take all of the above factors into account is difficult. Table 5 tries to show how long the various types of keys remain secure for. A number of assumptions are made:

  1. The number of computers in the world is equal to 10 Billion (that’s ten for every single person on earth in the year 2014 - there are expected to be 1 billion people (1010) alive in 2014).

  2. Each of the computers obey Moore's law for the entire period of cracking. (NOTE: this assumption may break current theories on speed of light, quantum physics etc). In reality, Moore's Law is predicted to become unfeasible within 10 years or so.

  3. We still assume that no attack better than brute force is found - which seems unlikely in light of the last decade of improvements in cryptanalysis.

Here goes...
Cipher Effective Key Size Years until break feasible with different HW1
500 Supercomputers2 10 Billion computers (PII 450)3 100,000 Deep Crack machines4
3DES 112 61 44 45
CAST 128 85 65 69
IDEA 128 85 66 69

Table 5: Block cipher strength against a very well funded adversary.

1 Calculated using 'LOG((2KeySize-1)/((KeysPerSecond×60×60×24×365)×NumberOfMachines×YearsSafetyMargin))×YearsToDoubleComputerSpeed)/LOG(2)' as published [Pet97]. Basically this column indicates the number of years until we will need to be concerned about a brute force attack using the assumptions mentioned above. More precisely, this figure shows how many years until a brute force attack is feasible with 10 years effort on the stated hardware.
2 It is assumed that each supercomputer can manage 10 Billion keys per second, regardless of the cipher employed.
3 Figures based on 10 processors per person [Odl95], CAST & 3DES implementation by A. Bosselaers ASM implementations, IDEA implementation by H. Lipmaa, timings from [Lip99].
4 Figures from [EFF98]. BIG assumption - each key test takes the same time as a DES test.

I'll take a figure and explain exactly what it means - it isn't immediately obvious. If an adversary has 10 Billion "state of the art" consumer level processor (analogous to a PII 450) to use solely for cracking a 3DES key, then we would need to be looking to changing cipher system in 44 years - the adversary could break the cipher in 10 years from this point. Remember that this only breaks a single key!

Another example; if an adversary takes 500 state of the art supercomputers, each capable of cracking 1 billion keys a second (these are serious computers!) and to use solely for cracking a 3DES key, then we would need to be looking to changing cipher system in 61 years - the adversary could break the cipher in 10 years from this point. Again, this only breaks a single key.

Another example; if an adversary takes 100,000 "Deep Crack" machines, each capable of cracking 92,625,000,000 keys per second to use solely for cracking a 3DES key, then we would need to be looking to changing cipher system in 74 years - the adversary could break the cipher in 10 years from this point. Again, this only breaks a single key.

In all honestly, this section was "produced under duress" - lots of people requested it. I'm not sure it helps prove a single thing other than that 3DES, IDEA & CAST keys are safe for 50 years as long as the best way to break the ciphers is by brute force.

I personally think that the asymmetric cipher will prove to be the "weak link" in the chain - e.g. factoring / computing discrete logs will become more feasible whilst attacking symmetric keys remains less feasible. Even worse, either the DLP or IFP could turn out to be "computationally easy".

If there is a moral of this story, it's "The sooner you start computing, the longer it will take to finish." [Sil98].

One has to ask one's self whether an intelligence agency would really bother to spend billions of pounds worth of effort to read one message...If the message were that important, wouldn't they just kidnap you (and murder you as appropriate)?

4.10. What are the performance differences between IDEA, CAST, 3DES?

Symmetric cipher timings (in Mbit/s on a 200Mhz Pentium) from [Lip99]:
Assembly 13.8 58.2 35.8

Table 6: Block cipher speed comparison

NOTE: These figures are not from the PGP implementation of the ciphers, but are indicative of the underlying cipher performance.

5. Key Revocation Certificate issues

5.1. What is a KRC?

All too often, someone posts to a *.pgp news groups with a question resembling "I have lost my private key, how can I revoke my key?". All too often, the members of those news groups have to let those people know that they cannot revoke their key.

You need two things to revoke your key: your private key and your passphrase. What if the passphrase you so easily remember now you forget some day? Or what if you accidentally delete your private key ring? Both happen, and either way, except for disabling your key or hacking the hex of your key, there is no way to signify that your key cannot be used.

Also, both of the ways just mentioned do not prevent people from using your key, while a KRC does. Bottom line, it is just plain wise to generate a KRC immediately after your make your key - it may be impossible to create the KRC when you actually need it.

5.2. What concerns relate to producing a KRC?

If someone gets a hold of your KRC, they can revoke your key. Take care to store the KRC securely enough that no one who is not supposed to can get to it. Also make sure that your KRC isn't so securely stored that you can't get to it!

In PGP v6.0+ and Business versions of v5.x, in the preferences, you can set PGP to automatically synchronise with the Key Servers upon certain operations. Make sure that the preference to automatically synchronise upon revoking a key is disabled or your KRC will be sent to the servers!!!

Also, by creating your KRC, you have made a backup copy of your private key. You may want to wipe that file. Also note that since Windows uses a swap file, and your private key information may have wound up in there. Heck, your private key may have even been burned on your RAM or something. Take whatever precautions you believe to be prudent to protect your private key info.

5.3. What is the procedure for creating a KRC?

The following procedure covers the creation of a KRC under recent (e.g. Business version of v5.x and all versions of v6.x) version of PGP:

  1. Create your new key.

  2. Back up your new key. Select the key that you wish to create the KRC for. Go to "Keys | Export...". A new screen will come up, asking you to specify a file name. Make the file name something obvious that this is the good copy of your key. Also, at the bottom of this screen there is a box that reads "Export private key(s)". Click it. Now, when you select ok, a copy of your keys will be saved in the location you specified.

  3. Verify that your backups are good. You can do this by going to "Keys | Import..." in PGP keys. You should see a double key icon. If it is just a single key, it means that in the previous step you did not check the box reading "Export private key(s)". If you do get a double key icon and there isn't a red line through the icon, you did fine.

  4. Revoke your key on your key ring. To do this, select the key that you wish to revoke. PGP will ask you if you are sure. Say yes. Type in your private key password. You will now notice that your key on your key ring has a red line through it. If you have description of key enabled in your preferences (keys: select columns), you will see that the description reads "Revoked DH/DSS public key" or "Revoked RSA public key", dependent on whether your key is RSA or DH/DSS. If it just says "Disabled", then you did it wrong.

  5. Now, backup your now revoked key. Do not export your private key this time. Make sure to export your now revoked key to a different file name then your good key that we saved in step one. You also may want to print out a copy of your revoke certificate in case your copy on disk gets messed up. To do this, select your now revoked key on your key ring, go to "Edit | Copy", launch notepad or some other word processor and paste your revoked key. You can now print it out if you wish.

  6. Delete your revoked key off your key ring ("Edit | Delete"), and import your good pgp key from step 1 ("Keys | Import...").

  7. Verify that your key works properly for signing, encrypting, and decrypting.

  8. Place your revoked key (also known as KRC) on a diskette or another safe place. This is your lifeline! Note - if an adversary (or prankster!) obtains your KRC then they can immediately revoke your key on your behalf. You have been warned!

  9. If and only if you need to actually revoke your key, re-import your KRC and upload it to the servers.

6. What would it take to "break" PGP?

This is really a quick answer to the above question. For a more detailed explanation (relating to RSA versions only though :-() see the excellent "The PGP attack FAQ" [Inf96].

Any of the following would affect the security afforded by PGP:

  1. Most likely, a flawed implementation of any of the cryptographic primitives.

  2. A thoroughly broken hash-function (e.g. where collisions can be found in computationally feasible time). This would allow an adversary to create second messages that hash to the same value as a first message, which implies that signatures can be forged.

  3. A new method of cryptanalysis that "breaks" the symmetric cipher used in PGP. This would allow an adversary to read encrypted traffic that was encrypted with that cipher.

  4. A way of breaking the RSAP, either by solving the IFP, or by other means.

  5. A way of breaking the DHP, either by solving the DLP, or by other means.

  6. A way of breaking DSS, either by solving the DLP, or by other means.

  7. Exploiting the RNG somehow. This may allow an adversary to guess the session keys, IVs and new keys.

The NSA may have done any of the above. It's a funny world.

7. Other issues

7.1. Private Keyring file - what does it contain and why does it need protecting?

The Private keyring (called "Secring.skr" by default) contains your private key(s). If someone obtains access to your private keyring then they can:

  1. Decrypt any messages sent to keys contained on your keyring. This includes past messages, current messages and any future messages.

  2. Create digital signatures using any of your private keys.

Basically, if someone obtains your private keys then the entire security of PGP is lost. It is therefore important to protect PGP private key rings stringently. PGP provides some protection; it encrypts the keyring with a passphrase - without the passphrase the private key(s) are inaccessible.

If you provide a good passphrase (see [Sch96a]), then your private keyring should be safe from any adversary. Still, you would be well advised to take some simple steps to protect the secret keyring file:

  1. Don't store the file on a network or shared drive. I, for example, store my keyring file on a ZIP disk.

  2. Store the file on an encrypted drive (as provided by PGPDisk, ScramDisk, Bestcrypt, EFS etc). This adds another layer of security above the passphrase required by PGP.

Combining the above two procedures (e.g. storing the files on a removable disk, which is also encrypted) will certainly improve security.

7.2. OpenPGP

PGP has recently been submitted as an IETF standard. It is very unlikely that OpenPGP would be accepted as a standard if it mandated encumbered algorithms [IMC98], [WIR97b], [CNET97]. This explains why RSA & IDEA have been deprecated in the latest versions of PGP.

The standard has now been accepted by the IETF and can be found in [RFC2440].

One can see a similar transition in cognate standards (e.g. S/MIME).

7.3. RSAREF License issues

PGP / NAI were in an interesting position when deciding whether to support RSA in the Freeware version of PGP v5+. The most recent version of the RSA Reference library, which has to be used to prevent patent infringement, has some interesting stipulations [RSA94]:

  1. provide complete application source code to RSADSI;
  2. grant RSADSI the right to redistribute such application
  3. distribute source of the application with each binary
  4. obtain express written acknowledgement of the end user that the Program will not be used in connection with any revenue-generating activity of the end user.

PGP would also have been in the position of having to use a library that is inferior in terms of speed to the unencumbered MPILIB library.

Of course, PGP / NAI could have continued to use the legacy version of RSAREF (e.g. RSAREF v1), but this also has an onerous clause [RSA93]:

"...incorporate the Program into other computer programs for your own personal or internal use, provided that you provide RSA with a copy of any such modification or Application Program by electronic mail, and grant RSA a perpetual, royalty-free license to use and distribute such modifications and Application Programs on the terms set forth in this Agreement."

Basically, PGP/NAI would have to grant RSA a "royalty-free license to use and distribute PGP". This is certainly counter to NAI/PGP's commercial interests, and as such would appear to be prohibitive to distributing a free version of PGP that incorporates RSAREF. Which is the only current way of providing RSA support in a manner complicit with patent law.

Users, of course, are free to use the legacy versions of PGP if they absolutely must have RSA support. One also notes that International versions of PGP v5+ support RSA as standard (as there are no patent issues regarding the support of RSA outside of the United States).

It can be seen that, in the domestic version of PGP v6.02, NAI have made an honest attempt to provide maximum RSA functionality available under "reasonable terms" - this version of PGP uses the RSA functionality provided by CAPI (licensed by Microsoft).

Maybe someone can see a commercially viable way of NAI/PGP to continue to support RSA in the freeware version of PGP? I unfortunately can't.

7.4. "Compelled production" of encryption keys

Note: This is a "grey area" in legal terms, there is very little legal precedent and as such users are warned to consult expert legal advice before acting upon comments in this section.

It is thought possible (at least in some countries) that Courts have the ability to compel the production of keys necessary to decrypt communications. In terms of PGP this means that a Court could compel the user to provide their passphrase that enables the Court to access the private key used for decryption.

It is generally accepted [EC98] that "a key escrow system is not intended for access private keys used only for integrity functions." Compelling production or, even worse, the escrow of signature only keys would not allow for non-repudiation or "assured" authentication. To my knowledge, no countries are entertaining the idea of either compelling production of or escrowing signature keys.

In previous versions of PGP (e.g. v2.x), divulging the RSA key meant that:

  1. All messages past, present & future could be decrypted.

  2. Digital signatures could be forged.

Obviously, these two points are disastrous so PGP now offers solutions to both of these issues:

  1. Signature and Encrypt keys are now separate entities. Each key generated with PGP consists of two parts:
    1. An encryption key (Diffie-Hellman)
    2. A signature key (Digital Signature Standard)
  2. The ability to revoke an encryption key without revoking the key in its entirety. You are able to create & revoke encryption keys without sacrificing your master signing key and the signatures collected on it.

These facilities just weren't available using RSA keys. True, PGP could have built a similar feature for RSA keys but these new keys would necessarily be incompatible with existing keys.

From a cryptographic design viewpoint, it is also sound practice to avoid using the same key for multiple purposes [MOV96].

7.5. DH "breaks" the existing web of trust?

An early and unfounded complaint about PGP DH was that the new keys "break the web of trust". People thought that all their existing signatures, which construct the web of trust, would now be defunct.

A simple way to sustain the existing "RSA web of trust" is to simply sign new DH/DSS keys with legacy RSA keys.

7.6. Why should I trust Zimmermann? He's not a cryptographer!

There are three answers to this frequently asked question:

  1. Phil Zimmermann hasn't coded a single line of code since at least '92 [Zim96]. Instead professional cryptographers and programmers have developed PGP.

  2. Even if Phil were doing all the coding, he need not be a cryptographer! PGP just reuses the well-documented cryptographic primitives (e.g. Hash functions, symmetric & asymmetric ciphers, secure RNGs) that are well specified in the cryptographic literature. The primitives used within PGP can be checked against published test vectors to ensure compliance.

  3. Phil would actually appear to be a very good programmer! For example, [PGP96] his MPILIB implementation of RSA functions is faster than RSA's own RSAREF!

Dozens, if not hundreds of trained cryptographers and programmers have reviewed the various of implementations of PGP (I know at least 5 personally!). There is no doubt that breaking an implementation of PGP would make a cryptographer (recall that Matt Blaze was "made" by breaking a popular cryptographic standard). See section 7.10 for further details.

7.7. How secure is the RNG in PGP?

The security of the PGP system relies quite heavily on the Random Number Generator (RNG).

The RNG is used in the following situations:

  1. Production of long-term asymmetric keys.

  2. Production of random session (symmetric) keys.

  3. Production of Initialisation Vectors (IV).

  4. Production of random values used by DSS.

Fortunately, PGP v5+ implements a RNG according to ANSI X9.17, which is in conformance to the standard outlined in [FIPS186].

As a matter of personal interest, I abstracted the RNG functionality from PGP v6.02 and produced 50x 30Mb files of "random" data which were then tested with DieHard [Mar98], a popular program for testing data for non-randomness. According to DieHard the output of the RNG used in PGP exhibits no bias, correlation or other obvious statistical weakness. A couple of the tests failed, but this is to be expected [Rit98].

The PGP RNG also passes the statistical tests specified in [FIPS140-1].

NOTE: the RNG cannot be declared "secure" just upon my empirical testing.

If you are interested in testing the RNG in PGP then I recommend the excellent book by Knuth [Knu98], or the paper by Kelsey, Schneier, Wagner, Hall [KSWH98a]. Further particularly good sources information on RNG tests are available in [MOV96].

7.8. Hasn't the trust model in recent versions of PGP changed?

Yes. The new versions of PGP are based on a much more rigorous treatment of trust by Ueli Maurer [Mau96].

7.9. So there are no intellectual property issues relating to PGP v5+?

Not exactly. There are two possible patent issues relating to algorithms implemented in PGP (and in dozens of other pieces of software!):

  1. Relating to SHA-1, Hitachi has informed the IEEE that they believe SHA & SHA-1 infringe upon patents 4,982,429 and 5,103,479.

  2. Relating to DSS, Schnorr has implied that DSS infringes on Claim 6 of his US patent 4,995,082.

[FIPS186] states decisively "The Department of Commerce is not aware of any patents that would be infringed by this standard."

All programs that implement DSS or SHA may potentially infringe on these two claims. One would assume that according to US patent law, which states that if you hold a patent and fail to prosecute an infringement you may lose the patent [Sch96a], any valid claims would have been made by now.

NOTE: I would suggest consulting a patent lawyer if the above causes concern!

7.10. Does anybody really bother checking the PGP source code?

Yes! I have personally tested (in PGP v5.0i) the implementation of DES, CAST, IDEA, MD5, SHA-1, RIPE-MD against test vectors. I have also tested the code used for DSS signature generation against the test vectors provided in [FIPS186] which testifies that the Big Number library code is working correctly.

I have tested the output from the RNG used within PGP as detailed in section 7.7.

I would, of course, conduct the above tests on other similar security packages (S/MIME implementations for example) - but it just isn't possible.

From personal experience, more people compile, inspect and test the source code than one might naïvely believe. From my involvement with ScramDisk, I note that out of the user base (which we estimate to be around 20,000), I have received e-mails from in excess of 40 individuals asking sometimes very technical questions about the source code. PGP is used by many more people than ScramDisk, so one can predict that the number who inspect the source code of PGP is correspondingly higher.

7.11. Often, encrypted & encrypted/signed messages are smaller than the original! Why?

Before encryption, messages are compressed using a standard compression algorithm [RFC1951]. Compressing data prior to encryption helps remove redundancy from the plaintext. Redundancy in the plaintext may aid cryptanalysis [Sch96a], [MOV96], [Pfl97], [Bau97].

7.12. Would the development of practical Quantum Computers or DNA computers break PGP?

Interesting question! Actually, this is two separate questions as DNA and Quantum computing affect the security of PGP in different ways.

First, Quantum Computers (QC). If (and it's a big "if" [Sch96a], [RSA96a]) QCs become practical then it is likely to have several implications in cryptography:

  1. All practical PK systems can be broken in polynomial time [RSA96a] (e.g. QCs can factor and compute discrete logs of any size in polynomial time.)

  2. Symmetric algorithms that support keys of insufficient length will be broken. Keys of 128-bit will be broken with the ease that 64-bit keys are broken today. It is thought that QC cannot break symmetric keys of 256-bits. (See Note 5 and [Dif98]). Of course, this comment also applies to hash functions.

Secondly, DNA computing, which appears to be more practical than QC. DNA computers can used to solve any problem that reduces to the Hamiltonian path problem [RSA96a], [Bea95], [Sch96a]. Essentially, DNA computing is like classical computing, just highly parallelized. DNA computing can be thwarted by using keys of sufficient size (e.g. 4096-bit asymmetric keys are certainly secure against DNA computers. It is not yet known whether a 128-bit symmetric key is safe against attacks by DNA computers - a pessimists would certainly consider moving to 256-bit keys (e.g. AES) when practicable. [Bea95] notes that, according to current DNA computing theory, 10120 litres of DNA would be necessary to factor a single 1000-bit RSA key.

I highly recommend the papers [Bea95] & [Sho94] as an overview of DNA and QC respectively, and in particular their practical application to factoring.

All of the comments in this section reflect on both PGP and other similar programs that exploit public key cryptography.

7.13. PGP must be weak! The USG allows its export!

Totally untrue. PGP has recently been exported via the following method:

  1. Printing the PGP source code.

  2. Exporting the (protected speech) source code books. EAR, the export regulations, do not cover the export of written material. See EAR § 734.3(b)(2) for reference.

  3. Rescanning the books in a foreign country and then compiling the code there.

You lucky Americans have a great constitution! Try living in the dark ages UK sometime...

7.14. Doesn't distributing the source code decrease security?

Absolutely not. A reasonably determined adversary can simply reverse engineer the machine code that comprises the program and analyse this [GW96]. University students are capable of undertaking this task, so it is extremely naïve to believe that the intelligence agencies can't.

As an example, Netscape and Microsoft refuse to release the source code of their security related software for peer review [GW96]. As a result of this lack of peer review, two of the most popular implementations of SSL were totally insecure against a determined adversary. One notes that even the "secure" versions of the browsers (e.g. the domestic US versions of the software) suffered from this security hole.

Quoting directly from the paper: "Peer review is essential to the development of any secure software. Netscape did not encourage outside auditing or peer review of its software - and that goes against everything the security industry has learned from past mistakes. By extension, without peer review and intense outside scrutiny of Netscape's software at the source-code level, there is simply no way consumers can know where there will be future security problems with Netscape's products."
"We are concerned that companies are hiding information about their security modules and shunning peer review"

It is a standard assumption in information security (referred to as the Kerckhoff principle, also paraphrased by Shannon "The enemy knows the system being used") that an adversary has access to the methods used in the process of encryption [Sch96a], [MOV96], [Sti95], [Bau97] - the strength must thus lie in the secrecy of the key. Trying to obtain "security by obscurity" seems imprudent in light of the Goldberg and Wagner paper.

7.15. What is "government certification"?

The government has a certification program for cryptographic modules [FIPS140-1].

NAI have confirmed that they are in the process of obtaining FIPS140-1 certification for the primitives used within PGP. In fact, they have already received certification for DES & SHA-1.

The process of certification involves the submittal of the source code to a NIST approved testing lab and may require changes to the primitive used in the software. As such, it can be considered an iterative process. One of the problems with certification is that it only relates to the certified version. Thus then next release of the software needs to be resubmitted for certification.

In practice, the certification means that PGP can be purchased and used by government departments. It also provides a "base-line" level of security in the algorithms used.

For completeness, I note that some of the cryptographic primitives used within Netscape (DES, DSA, SHA-1) have already been certified to level 2 when run on "Sun Sparc 5 w/ Sun Solaris version 2.4SE" and level 1 when run on Windows NT Workstation.

The observant reader will note that the implementation of the public key algorithm (RSA / DH or whatever) is not checked as part of the standards evaluation.

One problem with the certification process is that it can give naïve users a false sense of security in the evaluated product. A program's implementation of cryptographic primitives could, for example, be evaluated and certified in accordance with Federal standards, but be used in a setting that contains serious security flaws that affect the overall security of the package. These flaws may be neither easy to find or self-evident. Only a review of the complete package can "prove" the security of the package.

It is more than the core cryptographic code that needs checking, the code around the periphery of the implementation also needs to be checked, which FIPS140-1 doesn't provide. For further information read any good textbook on information security or applied cryptography, for example [Sch96a] or [Pfl97].

7.16. Why was there such a delay in the production of PGP v5?

Some have complained about the delay in the production of v5 of PGP. Remember that Phil Zimmermann was under a three-year criminal investigation, which ended early in 1996. I would suggest that PRZ had limited time and financial backing to conduct much development work during this period.

Also, one notes the large "feature-jump" between version 2.x and 5.x. PGP now has very strong hash functions, two additional ciphers, a new PK encryption scheme, a signature scheme that conforms to the USG standard [FIPS186], integration with key servers etc.

7.17. Who trusts PGP?

From [Zim96]:

"PGP is used all over the world by human rights groups, human rights activists who are documenting the atrocities of death squads, interviewing witnesses and using that to keep track of human rights abuses, and they encrypt that stuff with PGP, and they tell me that if the government there could get their hands on it they would round up all the witnesses and kill them, after torturing them first.

That's in Central America, and I talked to somebody working down there on it. The resistance groups in Burma are using it. Burma has a really horrible government, and there's resistance groups using PGP in jungle training camps. They're being trained to use it on portable computers. Then they are taking them to other jungle training camps and teaching them.

They've said that it's helped morale there because before PGP was introduced there, captured documents would lead to the arrest, torture, and execution of entire families. The government in exile in Tibet uses PGP. There's several other examples of third world countries where brutal dictatorships are, where human rights activists are using PGP.

From [Hof94]:

From [Zim98a]:

It would appear people readily trust trade secrets, client confidentiality and their lives with PGP. This certainly puts my use of it to encrypt personal communication in perspective!

7.18. How does multiple encryption affect security?

This question can be interpreted in a number of ways:

  1. How does encrypting messages to multiple recipients affect the security of the message?

  2. Does encrypting an already encrypted message (common when using chained remailers) increase security?

I'll answer both of these questions in order.

Encrypting a message to multiple recipients is as easy to break as the weakest asymmetric key. For example, if a message was encrypted to a 768-bit and a 1024-bit key then an adversary would obviously be able to read the message if they broke the smaller key.

If a message is encrypted to recipients with different asymmetric or symmetric key types - e.g. to both RSA and DH keys or with both 3DES and IDEA, then reading the message is clearly as hard as breaking any of the asymmetric or symmetric ciphers employed.

This necessarily introduces a theoretical weakness, as an adversary can attack multiple cipher schemes in order to get at the protected message. All of the ciphers in PGP are thought to be secure, so this theoretical weakness doesn't transfer to a practical weakness.

The ultra-paranoid could thus make a tenuous argument for only using one key type (both asymmetric and symmetric). For example, a user could refuse to accept RSA encrypted traffic (by not creating an RSA key I would suggest) and refuse to accept or send messages using any cipher other than CAST. This would minimise the theoretical weakness but I would suggest is totally unnecessary.

On to the second question...Encrypting an already encrypted message again is certainly practically more secure than a single encryption. In order to read the plaintext message an adversary would have to decrypt two levels of military grade encryption - which is totally unfeasible. But hang on - breaking a single level of military grade encryption is totally unfeasible anyway, so we haven't gained anything practically.

Actually, there is a subtle theoretical weakness when nesting PGP messages; PGP encrypted messages have a standard heading, so breaking the outer layers of encryption may be equivalent to a known plaintext attack - which is far easier than just performing a brute force without knowing about the underlying message content. PGP compresses data before encryption - this may reduce the feasability of the plaintext attack against the outer layers.

If you use chained remailers and nest encryption to these remailers, then be assured that the message is at least as hard to break as the plaintext encrypted once - and may be practically far more secure depending on the resources of the adversary.

[Sch96a] contains a nice description of multiple encryption schemes.

One worry when nesting encryption schemes (especially multiple applications of the same underlying primitives) is that the multiple applications will be a "group" - e.g. encrypting a message with any two keys Key1 and Key2 is equivalent to encrypting the message once with a single Key3. I can see no way that a applying PGP encryption multiple times could form a group - but I also haven't seen evidence that it couldn't happen (compressing the ASCII armoured text before encryption should help to "disfigure" any structure).

7.19. Why perform signing before message encryption?

When a user requests PGP encrypt and signs a message, it (and all other PK systems that I am aware of) first signs a message and then encrypts the concatenation of the signature and the data.

It is possible to implement this another way; first encrypt the data and then sign the cipher text. Transmit both the encrypted data and the signature.

Two reasons for not applying the signature algorithm (either RSA or DSS) after the encryption:

  1. Primarily because signing ciphertext allows an adversary to strip the correct signature off of a transmission and then replace this signature with another signature (produced with another key). This allows an adversary to sign a message (even though they don't know the contents) and the naive recipient may believe that the message contents originated from the adversary [Sti95]. Sneaky, huh?

  2. Information about both the originator and the intended recipient is leaked. By having the signature outside of the encrypted section it is possible for an adversary to tell the KeyID of both the sender (by looking at the signature header) and the receiver (by looking at the encryption header.) By signing first, then encrypting the concatenation of message and the signature, only information about the receivers key details is disclosed.

I can imagine obscure situations whereby you would like message authentication / verification outside of encryption. To implement this, simply encrypt (and optionally sign) a message with PGP and then sign the resulting encrypted message. Simple.

7.20. How does the cryptographic security of the OpenPGP & S/MIME standards compare?

The following table identifies the algorithms mandated (as "MUST" algorithms) in S/MIME (v3) [IETF98] and OpenPGP [RFC2440]:
OpenPGP v1 S/MIME v3
Symmetric Algorithm 3DES (CFB) 3DES (CBC) & RC2/40
PK Algorithm (encryption) ElGamal (4096) Diffie-Hellman (1024)
Signature Algorithm DSS DSS
Hash Function SHA-1 SHA-1

Table 7: S/MIME / OpenPGP comparison

Of course, it is the implementation of the standard that dictates the security, not the "theoretical" standard. (Note that ElGamal & DH are equivalent - see Note 1). Readers who are confused by the significance of "MUST" in IETF documents are referred to [RFC2119].

Asymmetric key size is of great importance in PGP and S/MIME. Table 1 (section 2.5) lists the recommended public key length to protect against attack by a single corporation (keys should be substantially bigger to protect against intelligence agencies!). So...The S/MIME standard specifies a maximum public key length of 1024-bits, which according to the table above doesn't offer sufficient long-term protection against a determined corporation! The OpenPGP standard, and the NAI implementation of the standard, allows public keys of up to 4096 bits, which should protect data for the foreseeable future.

ANSI X9F1 mandates 1024-bit minimum key-length for RSA and DH, but S/MIME only supports keys sizes of up to 1024-bits.

Some would argue that future versions of the S/MIME standard could possibly mandate keys greater than 1024-bits. That means that a determined and well-funded adversary could read your current private communications within 5 years or so.

One of the S/MIME periphery documents [PKIX98] describes a feature of S/MIME called "Proof of Possession of Private Key (PoP)". This is a mechanism whereby end user's private keys may be deposited with the CA when certification is requested. This is a very worrying inclusion and makes the implementation of mandatory key escrow a trivial matter [Gut99]. The PGP draft standard contains no such references to key recovery technology.

It is believed that the inclusion of PoP was added to the S/MIME standard at the request of the USG. Personally I believe that there should be a clear statement on whether the S/MIME standard requires unconditionally or functionally trusted TTPs (as per [MOV96]) - not some fuzzy standard that is subject to political pressure.

For completeness, I note that PGP specifies the CFB chaining mode whilst S/MIME mandates CBC mode. Both of these modes are equivalent in terms of strength [Sch96a], [MOV96] assuming that a unique IV (or random data to attach to the front of the message) can be provided in CFB mode. PGP already implements a random number generator (RNG); so supplying this random value is not a concern.

Of course, one can apply simple statistical theory to the implementations of PGP and S/MIME. Independent programmers and cryptographers have subjected PGP source code to literally thousands of hours of analysis. No such analysis can be made of S/MIME implementations since the source code is not distributed.

Since we can't prove there are no weaknesses in either implementation, the probability of there being such weakness is a straightforward function of the expert man-hours spent searching for them. One doesn't have to assert there ARE such weaknesses to make this argument. Thus the risk in using PGP is less than the risk in using S/MIME implementations that are not available with source. It's straightforward applied statistical decision theory.

How many expert man-hours have been spent searching for bugs in PGP? See section 7.10. How many expert man-hours have been spent searching for bugs in S/MIME? Who can tell? One could possibly argue that the "core" S/MIME code has been checked extensively by those implementing the system (but note that different implementations of S/MIME use different cryptographic libraries), but remember that, in the context of security, code on the periphery (e.g. not just the cryptographic core) can have a direct impact on security. So we revert back to the "lack of peer review" issue, as presented in [GW96].

Importantly, non US S/MIME users are provided with the RC2/40 symmetric cipher which has a key length of 40-bits and asymmetric ciphers <=512-bits which is clearly insecure. From [IETF98]: "40-bit encryption is considered weak by most cryptographers. Using weak cryptography in S/MIME offers little actual security over sending plaintext." Bruce Schneier offers a screen saver which brute forces 40-bit keys using the idle time on a standard PC.

It's worse than that actually...Many implementations of stronger ciphers (3DES) do not interoperate above 40-bit RC2 [Sch97b], [WIR97a]. This is bad news for end users.

PGP uses symmetric keys of 128-bits and asymmetric keys of up to 4096-bits irrespective of the locale. Thus users of PGP can communicate securely globally whereas S/MIME users currently can't.

From a security perspective, PGP can rightfully be considered more secure than S/MIME for the following reasons:

  1. S/MIME is limited to 1024-bit public keys; PGP can accommodate keys of up to 4096-bits.

  2. The S/MIME certification standard contains facilities that can be used easily for mandatory escrow. No such feature is present in the PGP standard.

  3. PGP implementations are open to and are subjected to extensive peer review. Users of S/MIME have to trust the implementation. To quote the NSA [Sch96a] "...most security failures in its area of interest are due to failures in implementation, not failure in algorithms or protocols" & [And93] "the vast majority of security failures occur at the level of implementation detail". So, as part of the export licensing procedure, the NSA can review the S/MIME implementation and thus exploit any weaknesses, but the end users aren't afforded this privilege [GW96].

  4. Non-US users of S/MIME can only use 40-bit symmetric keys which, according to the S/MIME documentation [IETF98]: "offers little actual security over sending plaintext."

An article written by a well known cryptographer [GW96] has claimed that "Until they learn their lesson and open their security programming to public evaluation, many security experts will remain justifiably sceptical of the company's security claims." in respect of Netscape Navigator (a well known program that purports to implement the S/MIME standard).

8. Conclusion

"No one shall be subjected to arbitrary interference with his privacy, family, home or correspondence, nor to attacks upon his honour and reputation. Everyone has the right to the protection of the law against such interference or attacks."
-- Article 12 Universal Declaration of Human Rights

"Takes a man to suffer ignorance and smile."
-- Sting

It would appear that there are several reasons for the changes seen between v2.x and v5+, primarily:

  1. Serious doubts being cast over the long-term strength offered by MD5. The hash Algorithm used by PGP is central to its security - a broken hash function could make PGP implementations totally insecure.

  2. The move towards PGP as an open, public standard for e-mail security. The inclusion of RSA & IDEA as "MUST" algorithms would certainly have negatively impacted PGPs adoption as an Internet standard (a similar transition can be seen in the S/MIME standard). One is also reminded of the RSA library issues as outlined in section 7.3.

  3. In a bid to continue offering a commercially viable Freeware version of PGP it has been necessary to drop RSA support, due to RSAREF licensing issues.

  4. The adoption of the Digital Signature Standard as the signature algorithm used in PGP. This is now both the government, and the de facto standard algorithm for providing digital signatures.

  5. The splitting of the encryption and signature keys - this allows compelled production of keys used for encryption without also divulging signature keys, which would necessarily invalidate non-repudiation.

  6. Fixing two other (non MD5 related) problems with pre-v5 versions of PGP: create an arbitrary ID & create a key with the same fingerprint as another (See Note 6). These changes would have necessarily invalidated existing keys.

PGP had to change the implementation of PGP in ways that would have made previous keys invalid, it is therefore not unreasonable that they also change the asymmetric cipher used in PGP. Users can still use RSA keys (though this may mean using an International version of PGP or paying for the RSA version) if they have a requirement to continue using old keys. In view of the MD5 issue however, this would appear imprudent.

One argument has been that ElGamal as implemented in PGP could be flawed - that is to say there could be a subtle weakness in the implementation. The user should be reminded that ElGamal relies on the same mathematical operations and functions as RSA, namely: general large integer arithmetic, modulo exponentiation, inverses modulo, GCD, extended Euclidean algorithm, Chinese remainder theorem, reciprocal etc [Dif98] (also see Note 4), all of which have, by now, been extensively tested.

In summary, PGP v5+ is certainly cryptographically stronger than previous versions of PGP. There also seem to be other influences, primarily the list above, that have necessitated the changes seen between these versions.

The only valid reason I can find for continuing to use RSA keys in preference to the new DH/DSS keys is to communicate with a recipient who only has the deprecated keys

8.1. Get the threat in perspective!

The NSA (probably!) aren't specifically interested in you. They aren't going to break into your house to install bugs, or monitor your screen from a block away. They will however collect all of your messages sent over public networks.

PGP protects you from one form of monitoring - Echelon or other passive network sniffing. When your messages are captured by this global monitoring system, along with millions of other messages a day, the NSA can possibly decide to try and decode your message. Why would they bother?

The most significant threat to PGP comes from user slopiness. It is far easier to install a keylogger on your computer, install a trojan version of PGP, or bruteforce your passphrase than to break any of the cryptographic mechanisms employed by PGP.

If you are seriously worried about Intelligence Agencies actively monitoring you then the last thing you should be worried about is them cryptographically attacking your PGP crypto implementation!

8.2. What now? I'm still not convinced!

If, having read all of the above, you are still not convinced about the benefits of DH over RSA keys then you still have the option of:

  1. Inspecting the source code and satisfying yourself that it functions correctly.

  2. Using an older version of PGP.

  3. Moving to another encryption system (S/MIME for example - and put up with the inevitable severe security limitations).

  4. Using the International version of PGP. (NOTE: use of the international "RSA-enabled" version of PGP within the US may be subject to patent issues).

  5. Using PGP v6.02 (without RSA support) under the 128-bit version of IE v4 which offers some limited RSA support via CAPI.

  6. Paying for the program that you so dearly need! (PGP for Business Security still offers legacy RSA support).

8.3. Final Words

Why should I offer my subjective opinion on PGP as a summary? I won't. Instead I shall use 3 quotes (I like quotes!):

[Sch96a] on PGP:

"Assuming you trust IDEA, PGP is the closest you're likely to get to military-grade encryption".

[PGP98] sums up the security of PGP v5+ perfectly:

"If your situation justifies worrying about very formidable attacks of this caliber, then perhaps you should contact a data security consultant for some customized data security approaches tailored to your special needs."

The closing words of this FAQ have to be from Whitfield Diffie, distinguished progenitor of Public Key cryptography [DL98]:

"In writing PGP, Phil Zimmermann did something for cryptography that no technical paper could do: he gave people who were concerned with privacy but were not cryptographers (and not necessarily even programmers) a tool they could use to protect their communications".

9. Further Reading

I'm only going to make three recommendations:

Applied Cryptography (2nd ed.) by Schneier - A comprehensive and definitive introduction to cryptography.

Handbook of Applied Cryptography by Menezes, van Oorschot & Vanstone - a very rigorous, "landmark" book.

Privacy on the Line by Diffie and Landau, 1998 - the father of PK reviews the politics surrounding the crypto debate.

10. Notes

(1) To break DH, one needs to be able to find gab knowing only ga and gb. To break ElGamal, one needs to determine P, knowing gk and Pgak, with ga being public also. But then breaking ElGamal is equivalent to finding gak, knowing only ga and gk --the same problem needed to be solved to crack DH. (All of the above is of course over a 'large' finite field, the size of which is public.) So cracking one cracks the other, whether you solve the DLP or not. However, it's conjectured that there is no way to solve the above problem without essentially solving the DLP.

(2) From the source code of PGP v5.0:
Public key components:
        n The public modulus
        e The public exponent
Private key components:
        d Decryption exponent (which is equal to e-1 mod ((p-1)(q-1)))
        p The smaller factor of n
        q The larger factor of n
        u 1/p (mod q)

Encryption is (pseudo-code!):
        EncMsg = DecMsge mod n

Decryption is (pseudo-code!):
        DecMsg = EncMsgd mod n

(3) Taken directly from the source code of PGP v5.0:
Public key components:
        p Public prime
        g Public generator
        y Public key, gx mod p

Private key component:
        x Secret key, discrete log of y

ElGamal encryption is a simple variant on non-interactive Diffie-Hellman. The recipient publishes g, p, and y = gx mod p. The sender picks a random xx, computes yy = gxx mod p, and the shared secret z = yxx mod p = yyx mod p = gx*xx mod p, then sends z*m mod p, where m is the message.

(4) From the source code of 2.6.3i MPILIB.H:
"These routines implement all of the multi-precision arithmetic necessary for number-theoretic cryptographic algorithms such as ElGamal, Diffie-Hellman, Rabin, or factoring studies for large composite numbers, as well as Rivest-Shamir-Adleman (RSA) public key cryptography."

(5) "While quantum computation can make problems such as factoring and discrete logarithms (which public-key cryptography are based on) easy, they can only reduce the complexity of any arbitrary computation by a square root. So, for example, if a 128-bit key length was long enough pre quantum computation, then a 256-bit key will be long enough post quantum computation."
-- B.Schneier, 10th Oct 1998 posting to soc.history.what-if USENET group

(6) "How can we with good conscience allow users to generate keys which we don't feel meet our security standards? We can't. Case closed. If you're unfamiliar with why RSA keys are not as secure as we'd like, you should check archives of the newsgroups for the past few years.

The weaknesses of MD5 and the KeyID attacks were the two primary security issues we felt absolutely had to be addressed in 5.0. The development team couldn't have cared less about RSA licensing issues.

The only issue was security. Fixing those required a new key format. As long as we were changing the key format, we decided to switch to unencumbered algorithms at the same time since the hit was the same either way -- everyone would need new keys. If a particular user doesn't mind the security issues with RSA keys, they should feel free to continue using them although the number of versions supporting those keys available from us will undoubtedly continue to dwindle, and at the same time the number of versions and platforms supporting DH/DSS keys will continue to grow dramatically."
-- W.Price, Nov 97 posting to ietf-open-pgp mailing list

11. Acronyms

AES Advanced Encryption Standard
DES Data Encryption Standard
CA Certification Authority
CRHF Collision Resistant Hash Function
DH Diffie-Hellman. The PK system, named after the creators
DHP Diffie-Hellman Problem
DLP Discrete Logarithm Problem
DNA Deoxyribonucleic Acid
DSA Digital Signature Algorithm
DSS Digital Signature Standard
EES Escrowed Encryption Standard
IETF Internet Engineering Task Force
IESG Internet Engineering Steering Group
IFP Integer Factorisation Problem
IV Initialisation Vector
FIPS Federal Information Processing Standards
KRC Key Revocation Certificate
MITM Meet In The Middle
NIST National Institute of Science and Technology
NSA National Security Agency
OWHF One Way Hash Function
PK Public Key
PRNG Pseudo-Random Number Generator
PRZ Philip R Zimmermann, original author of PGP
QC Quantum Computing
RNG Random Number Generator
RSA Rivest, Shamir, Adleman. The PK system, named after the creators
RSAP RSA Problem
SHA Secure Hash Algorithm
TTP Trusted Third Party
USG United States Government

12. References

"I must've seen it in a USENET posting; that's sort of like hearsay evidence from Richard Nixon..."
-- Blair Houghton
[And93] R.Anderson, "Why Cryptosystems Fail", Cambridge University, 1993.
[ANSI930-1] ANSI X9.30 (Part 1), "...Part 1: The Digital Signature Algorithm (DSA)", ASC X9 Secretariat - American Bankers Association, 1995.
[ANSI930-2] ANSI X9.30 (Part 2), "...Part 2: The Secure Hash Algorithm (SHA)", ASC X9 Secretariat - American Bankers Association, 1993.
[ANSI952] ANSI X9.52, "Triple data encryption modes of operation", draft, 1996.
[Bal98] R.W.Baldwin, "Preliminary Analysis of the BSAFE 3.x Pseudorandom Number Generators", RSA Labs Bulletin - Number 8, Sept 1998.
[Bau97] F.L.Bauer, "Decrypted Secrets; Methods and Maxims of Cryptology", Springer, 1997.
[BB94] B.den Boer and A.Bosselaers. "Collisions for the compression function of MD5", Advances in Cryptology Eurocrypt '93, Springer-Verlag, 1994.
[BBR98] E.Biham, D.Boneh, O.Reingold "Generalized Diffie-Hellman modulo a composite is not weaker than factoring", 1998.
[Bea95] D.Beaver, "Computing With DNA", Journal of Computational Biology, Spring 1995.
[BK98] E.Biham, L.R.Knudsen, "DES, Triple-DES and AES", RSA CryptoBytes - Volume4, Number1, Summer 98.
[Bon98] D.Boneh, "Twenty years of Attacks on the RSA Cryptosystem", Stanford University, 1998.
[Bor96] J.Borst, "Differential-Linear Cryptanalysis of IDEA", ESAT-COSIC Technical Report 96-2, 1996.
[BV98] D.Boneh, R.Venkatesan, "Breaking RSA may not be equivalent to factoring", Eurocrypt '98, Lecture Notes in Computer Science, Vol. 1233, Springer-Verlag, 1998.
[CJ98] F.Chabaud, A.Joux, "Differential Collisions in SHA-0", Crypto '98 Proceedings, 1998.
[CW93] K.W.Campbell, M.J.Wiener, "DES is not a group", Crypto '92, 1993.
[CYL98a] "What's all of the fuss about triple-DES? How strong is it anyway?", Cylink Corporation, 1998.
[CYL98b] "Alternatives To RSA Using Diffie-Hellman With DSS", Cylink Corporation, Aug 1998.
[DBP96] H.Dobbertin, A.Bosselaers, B.Preneel. "RIPEMD-160: A strengthened version of RIPEMD." Fast Software Encryption, 1996.
[Den98] D.Denning, message beginning "Eli Biham and Lars Knudsen have exposed a...", 3rd Apr 98.
[Dif98] W.Diffie, "Whitfield Diffie interview", Lem Bingley interview with W.Diffie, Ziff-Davis, Nov 1998.
[DH76] W.Diffie, M.E.Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory", Nov 1976.
[DL98] W.Diffie, S.Landau "Privacy on the Line", MIT Press, 1998.
[Dob96] H.Dobbertin, "The Status of MD5 After a Recent Attack", RSA CryptoBytes - Volume2, Number2, Summer 96.
[EC98] "Legal and Regulatory Issues for the European Trusted Services Infrastructure" Final Report, ISTEV, European Commission.
[EFF98] "Cracking DES", EFF, 1998.
[EFF99] "RSA Code-Breaking Contest Again Won by Distributed.Net and Electronic Frontier Foundation (EFF) - DES Challenge III Broken in Record 22 Hours", Press Release, EFF, 19th Jan 1999.
[ElG85] T.ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," IEEE Transactions on Information Theory, v.IT-31, n. 4, 1985.
[FIPS46-2] "DATA ENCRYPTION STANDARD (DES)", NIST Federal Information Processing Standards Publication 46-2, 1993.
[FIPS46-3] "DATA ENCRYPTION STANDARD (DES)", NIST Federal Information Processing Standards Publication 46-3, Draft, 1999.
[FIPS140-1] "SECURITY REQUIREMENTS FOR CRYPTOGRAPHIC MODULES", NIST Federal Information Processing Standards Publication 140-1, 1994.
[FIPS180-1] "SECURE HASH STANDARD", NIST Federal Information Processing Standards Publication 180-1, 1995.
[FIPS186] "DIGITAL SIGNATURE STANDARD (DSS)", NIST Federal Information Processing Standards Publication 186, 1994.
[Gut99] P.Gutmann, "Re: Opinions on S/MIME" sci.crypt USENET posting, 1st Jan 1999.
[GW96] I.Goldberg, D.Wagner, "Randomness and the Netscape Browser - How secure is the World Wide Web?", Dr Dobbs Journal, 1996.
[Hof94] L.J.Hoffman, "Building in Big Brother", Springer, 1994.
[IETF98] B.Ramsdell, "S/MIME Version 3 Message Specification", Aug 1998.
[IMC98] Internet Mail Consortium, "S/MIME and OpenPGP", http://www.imc.org/, 1998.
[INF96] "infiNity", "The PGP attack FAQ", http://axion.physics.ubc.ca/pgp-attack.html
[ISOIEC10118-3] ISO/IEC 10118-3, "Information Technology - Security Techniques - Hash Functions - Part3: Dedicated hash functions", draft, 1996.
[Knu98] D.Knuth, "The Art of Computer Programming Volume 2: Seminumerical Algorithms, 3rd Ed.", 1998.
[KSW96] J.Kelsey, B.Schneier, D.Wagner, "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, Triple-DES", Advances in Cryptology - CRYPT'96, 1996.
[KSW97] J.Kelsey, B.Schneier, D.Wagner, "Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA", 1997.
[KSWH98a] J.Kelsey, B.Schneier, D.Wagner, C.Hall, "Cryptanalytic Attacks on Pseudorandom Number Generators", 1998.
[KSWH98b] J.Kelsey, B.Schneier, D.Wagner, C.Hall, "Cryptanalytic Attacks on Pseudorandom Number Generators", 1998.
[Kob94] N.Koblitz, "Graduate Texts in Mathematics: A course in number theory and cryptography", Springer, 1994.
[Lai91] X.Lai, "Detailed Description and a Software Implementation of the IPES Cipher", Institute for Signal and Information Processing, ETH-Zentrum, Zurich, Switzerland, 1991.
[Lip99] H.Lipmaa, "AES Ciphers: speed" - available at http://home.cyber.ee/helger/aes/ , 1999.
[LMM91] X.Lai, J.L.Massey, S.Murphy, "Markov Ciphers and Differential Cryptanalysis", Advances in Cryptology - EUROCRYPT'91.
[Luc98] S.Lucks, "Attacking Triple Encryption", Fast Software Encryption, 1998.
[Mar98] G.Marsaglia. Diehard Statistical Tests. http://stat.fsu.edu/~geo/ , 1998.
[Mau96] U.Maurer, "Modelling a Public-Key Infrastructure", Proceedings 1996 European Symposium on Research in Computer Security (ESORICS '96), E.Bertino (Ed.), Lecture Notes in Computer Science, Berlin: Springer-Verlag, Rome, Italy, Sept 1996.
[MOV96] A.J.Menezes, P.C.van Oorschot, S.A.Vanstone "Handbook of Applied Cryptography", CRC Press, 1996.
[MW96] U.M.Maurer, S.Wolf, "On the Complexity of Breaking the Diffie-Hellman Protocol", Institute of Theoretical Computer Science, Switzerland, Apr 1996.
[CNET97] "RSA under fire from IETF", CNet News.com Article, 3rd Nov 1997.
[Odl83] A.M.Odlyzko, "Discrete Logarithms in finite fields and their cryptographic significance", 1993.
[Odl87] A.M.Odlyzko, "On the Complexity of Computing Discrete Logarithms and Factoring Integers", Bell Laboratories, 1998.
[Odl95] A.M.Odlyzko, "The Future of Integer Factorization", RSA CryptoBytes, Volume 1, Number 2, Summer 1995.
[PBD97] B.Preneel, A.Bosselaers, H.Dobbertin, "The Cryptographic Hash Function RIPEMD-160", RSA CryptoBytes - Volume2, Number2, Autumn 97.
[Pet97] S.Peterson, "Re: Why is IDEA only 128 bits " sci.crypt USENET posting, 18 Jul 1997.
[Pfl97] C.P.Pfleeger, "Security in Computing", 1997.
[PGP96] S.Schumacher, "Pretty Good Privacy version 2.6.3i - READ ME FIRST", 1996.
[PGP97] PGP v5.00i, source code, 1997.
[PGP98] NAI, "An Introduction to Cryptography", (as distributed with PGP v6.02), 1998.
[PKIX98] M.Myers, C.Adams, D.Solo, D.Kemp, "Internet X.509 Certificate Request Message Format", May 1998.
[RFC1321] R.Rivest, "The MD5 Message Digest Algorithm", RFC 1321, April 92.
[RFC1951] P.Deutsch, "DEFLATE Compressed Data Format Specification version 1.3.", RFC 1951, May 1996.
[RFC2119] S.Bradner, "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, Mar 1997.
[RFC2144] C.Adams, "The CAST-128 Encryption Algorithm", May 1997.
[RFC2440] J.Callas, L.Donnerhacke, H.Finney, R.Thayer, "OpenPGP Message Format", RFC 2440, Nov 1998.
[Rit98] T.Ritter, "Re: Need help evaluating output from a PRNG" sci.crypt USENET posting, 10 Jan 1998.
[Rob95] M.J.B.Robshaw, "Security Estimates for 512-bit RSA", RSA Labs, June 29.
[RSA78] R.L.Rivest, A.Shamir, L.M.Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, Feb 1978.
[RSA93] "RSAREF License from RSA Data Security", RSA LABORATORIES, 5th January 1993.
[RSA94] "RSAREF(TM) 2.0: A Free Cryptographic Toolkit General Information", Apr 1994.
[RSA96a] RSA FAQ v3, 1996.
[RSA96b] Bulletin 4, RSA Labs, Nov 1996.
[RSA98] RSA FAQ v4, 1998. Available at http://www.rsa.com/
[Sch96a] B.Schneier, "Applied Cryptography, Second Edition", Wiley, 1996.
[Sch96b] B.Schneier, "Why Cryptography Is Harder Than It Looks", 1996.
[Sch97a] J.Schiller, "Re: Question about the 'Freeware Version'" alt.security.pgp USENET posting, 19th June 1997.
[Sch97b] B.Schneier, "S/MIME Crack? Beware press bearing incomplete stories more options" sci.crypt USENET posting, 26th Sept 1997.
[Sch98a] B.Schneier, "Re: linux kernel loopback encryption", ailab.coderpunks mailing list, 16th July 1998.
[Sch98b] B.Schneier, "Re: Candidates for AES" sci.crypt USENET posting, 26th October 1998.
[Sch98c] B.Schneier, "CAST" ailab.coderpunks mailing list, 16th July 1998.
[Sch98d] B.Schneier, "Re: Why CAST as default in PGP?" sci.crypt USENET posting, 20th October 1998.
[Sch98e] B.Schneier, "Re: AES and Symmetric vs Asymmetric key length more options" sci.crypt USENET posting, 11th November 1998.
[Sch98f] R.Schlafly, "Re: Opinions on S/MIME" sci.crypt USENET posting, 30th December 1998.
[Sch98g] B.Schneier, "Re: DES better than AES?" sci.crypt USENET posting, 26th September 1998.
[Sch98h] B.Schneier, "Re: DES better than AES?" sci.crypt USENET posting, 26th September 1998.
[SH97] B.Schneier, C.Hall "An Improved E-Mail Security Protocol", 1997.
[Sho94] P.W.Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1994.
[Sil97] B.Silverman, "Fast Generation of Random, Strong RSA Primes", RSA Labs, 17th May 1997.
[Sil98] B.Silverman, "Re: Primes" sci.crypt USENET posting, 2nd October 1998.
[Sim98] S.Simpson, "Re: To All Morons Using Greater That 3000 Bit RSA Keys!!!! READ!!!", alt.security.pgp USENET posting, 29th November 1998.
[Sti95] D.R.Stinson, "Cryptography - Theory and Practice", CRC Press, 1995.
[Tuc79] W.Tuchman, "Hellman Presents No Shortcut Solutions To DES,", IEEE Spectrum, v. 16, n. 7, July 1979.
[TY98] Y.Tsiounis, M.Yung, "On the Security of ElGamal based Encryption", 1998.
[Vau96] S.Vaudenay "Hidden Collisions on DSS", June 1996.
[Wag94] D.Wagner, "Re: Algorithms" sci.crypt USENET posting, 15th November 1994.
[Wie98] M.J.Wiener, "Performance Comparison of Public-Key Cryptosystems", RSA CryptoBytes, Volume 4, Number 1, Summer 1998.
[WIR97a] "S/MIME Cracked by a Screensaver", Wired News Article, 26th Sept 1997.
[WIR97b] "RSA Blows Standards Smoke", Wired News Article, 31st Oct 1997.
[WIR98] "PGP's 6.0: Cat Out of the Bag", Wired News Article, 3rd Sept 1998.
[Zim96] "Interview with author of PGP (Pretty Good Privacy)", R.D.Hoffman interview with P.R.Zimmermann, Feb 1998.
[Zim98a] "Letters to Phil", NAI Web site, http://www.pgp.com/, Dec 1998.
[Zim98b] P.R.Zimmermann, message beginning "There is no advantage for using the keys larger than about 3000 bits.", 31st July 1998.

Last Modified 27 January 99. Copyright S.Simpson, 1999.