Sam Simpson: PGP DH vs. RSA FAQ

Archive-name: PGP-DH-RSA
Version: 1.5
Last-modified: Thursday, 20^th September 1999

PGP DH vs. RSA FAQ
Copyright © 1999 S.Simpson - All Rights Reserved
Sam Simpson - http://www.scramdisk.clara.net/

All information contained in this work is provided "as is." All warranties, expressed, implied or statutory, concerning the accuracy of the information or 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(s) and contributor(s) 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.

Document Changes

v1.5 - 20^th September 1999
Added section "Has RIPEMD been broken?"
Added section "What are the implications of the NSA key in CryptoAPI?"
Added detail to "How big should my asymmetric key be?"
Added detail to "What about Elliptic Curves?"
Added detail to "Which is stronger, RSA or DH/DSS?"
Added detail to "What is IDEA?"
Added detail to "What is "government certification"?"
Added detail to "How does the cryptographic security of the OpenPGP & S/MIME standards compare?"

v1.4 - 18^th August 1999
Minor grammar / spelling related changes
Updated references to FIPS186 to the revised FIPS186-1
USENET references now contain link to deja.com where available
Added section "What is the chance of running out of primes?"
Added section "What about Elliptic Curves?"
Added section "What is AES?"
Added section "What is Twofish?"
Added section "What are the implications of Shamir's TWINKLE device on PGP security?"
Added detail to "The huge key debate."
Added detail to "What is DH / ElGamal?"
Added detail to "So there are no intellectual property issues relating to PGP v5+?"

v1.3 - 16^th March 1999
Minor changes to numerous sections
Added section "What are the implications of the attacks against MD5?"
Added section "Why doesn't PGP use a "provably secure" cipher?"
Added section "Program x offers 200-bit keys, is it better than PGP?"
Added section "So PGP is perfect?"
Added detail to "What is DH / ElGamal?"
Added detail to "Why does PGP use precomputed primes for DSS/DH?!?"
Added detail to "Why are DSS keys significantly smaller than DH keys?"
Added detail to "Which is stronger, RSA or DH/DSS? "

v1.2 - 3^rd March 1999
Minor grammar / spelling related changes
Added section "Why are DSS keys significantly smaller than DH keys?"
Added section "Doesn't the DSS suffer from subliminal channels?"
Added section "Summary of PGP DH versus PGP RSA"
Added detail to "What is DH / ElGamal?"
Added detail to "Why does PGP use precomputed primes for DSS/DH?!?"
Added detail to "The huge key debate."
Added detail to "How does the cryptographic security of the OpenPGP & S/MIME standards compare?"

v1.1 - 27^th 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 - 15^th Jan 1999
Minor grammar / spelling related changes
Some technical changes - mainly to notes.

1. Introduction

2. Public Key Algorithms in PGP

2.1. What is RSA?
2.2. What is DH / ElGamal?
2.3. What is DSS?
2.4. What is the chance of producing a composite instead of a prime with PGP?
2.5. What is the chance of running out of primes?
2.6. How big should my asymmetric key be?
2.7. The huge key debate.
2.8. Why does PGP use precomputed primes for DSS/DH?!?
2.9. In respect of RSA, what are strong primes?
2.10. The PGP implementation of DH is based on Galois Fields, aren't they broken?
2.11. Why are DSS keys significantly smaller than DH keys?
2.12. Doesn't the DSS suffer from subliminal channels?
2.13. What about Elliptic Curves?
2.14. Which is stronger, RSA or DH/DSS?
2.15. Any recent developments?
2.16. What are the performance differences for encryption between RSA & ElGamal?
2.17. What are the performance differences for signing between RSA & DSS?

3. Hash Function Algorithms in PGP

3.1. What is a Hash Function?
3.2. What is a "checksum"?
3.3. What function does a hash algorithm perform in PGP?
3.4. What is MD5?
3.5. What is SHA-1?
3.6. What is RIPEMD-160?
3.7. Has MD5 been broken?
3.8. What are the implications of the attacks against MD5?
3.9. Was the original SHA broken?
3.10. Has RIPEMD been broken?
3.11. Which is stronger, MD5, SHA-1 or RIPEMD-160?
3.12. What are the performance differences between MD5, SHA-1 & RIPEMD-160?

4. Conventional Encryption Algorithms in PGP

4.1. What is a conventional encryption algorithm?
4.2. What function does a conventional encryption algorithm perform in PGP?
4.3. What is IDEA?
4.4. What is CAST?
4.5. What is 3DES?
4.6. What is AES?
4.7. What is Twofish?
4.8. Has 3DES been broken?
4.9. Has CAST been broken?
4.10. Which is stronger, IDEA, CAST, 3DES or Twofish?
4.11. How "computationally hard" are symmetric keys?
4.12. Why doesn't PGP use a "provably secure" cipher?
4.13. What are the performance differences between IDEA, CAST, 3DES & Twofish?

5. Key Revocation Certificate issues

5.1. What is a KRC?
5.2. What concerns relate to producing a KRC?
5.3. What is the procedure for creating a KRC?

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

7. Other issues

7.1. Private Keyring file - what does it contain and why does it need protecting?
7.2. OpenPGP
7.3. RSAREF License issues
7.4. "Compelled production" of encryption keys
7.5. DH "breaks" the existing web of trust?
7.6. Why should I trust Zimmermann? He's not a cryptographer!
7.7. How secure is the RNG in PGP?
7.8. Hasn't the trust model in recent versions of PGP changed?
7.9. So there are no intellectual property issues relating to PGP v5+?
7.10. Does anybody really bother checking the PGP source code?
7.11. Often, encrypted & encrypted/signed messages are smaller than the original! Why?
7.12. Would the development of practical Quantum Computers or DNA computers break PGP?
7.13. PGP must be weak! The USG allows its export!
7.14. Doesn't distributing the source code decrease security?
7.15. What is "government certification"?
7.16. Why was there such a delay in the production of PGP v5?
7.17. Who trusts PGP?
7.18. How does multiple encryption affect security?
7.19. What are the implications of Shamir's TWINKLE device on PGP security?
7.20. What are the implications of the NSA key in CryptoAPI on PGP Security?
7.21. Why perform signing before message encryption?
7.22. How does the cryptographic security of the OpenPGP & S/MIME standards compare?
7.23. Program x offers 200-bit keys, is it better than PGP?
7.24. So PGP is perfect?

8. Conclusion

8.1. Summary of PGP DH versus PGP RSA
8.2. Get the threat in perspective!
8.3. What now? I'm still not convinced!
8.4. Final Words

9. Further Reading

10. Notes

11. Acronyms

12. References

Contributors

Primarily, sincere thanks to Kurt Mueller for providing the Key Revocation Certificate section and Robert Munyer who has scrutinised each release of this FAQ and continues to improve it substantially. Many thanks to Dan "the" Horne & Andy Jeffries for proof reading this document while it was rough-and-ready.

Thanks to John Young for providing the excellent Cryptome web site - without which this FAQ would have taken months longer to research.

Many thanks to Jaime Suarez for converting the FAQ to Spanish.

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

Adam Back
Laszlo Baranyi, NAI
Bob Clements
Dave Del Torto
Imad R. Faiad
Peter Gutmann
Don Johnson
Denning Langston
Neal McBurnett
Tom McCune
Noah Salzman, NAI
John Savard
Roger Schlafly
Bruce Schneier
Bill Unruh

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:

Has PGP been broken?
Which version of PGP is stronger, RSA or DSS/DH?
Why doesn't PGP support RSA as standard anymore?
Is PGP cryptographically less secure than S/MIME?
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 [Scr99], with improving the implementation efficiency of Serpent, an AES candidate [Gla99], and advising on and critically reviewing several cryptographic products.

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], [Len96].

RSA is patented in the United states by Massachusetts Institute of Technology (U.S. patent number 4,405,829), though this expires 20 September 2000.

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 m^e is congruent to c (mod n)." Basically RSAP involves finding e^th 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 openly published public key system [DH76] (more correctly Diffie-Hellman is a key-exchange mechanism) and as such has received extensive analysis by eminent cryptographers.

Diffie-Hellman, along with derivatives such as ElGamal are covered by U.S. patent number 4,200,770, which expired 6^th September 1997.

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 you can break either ElGamal or DH then you can 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 DLP under the "Diffie-Hellman assumption" [Kob94]. This assumes that it is infeasible to compute g^ab knowing only g^a and g^b. To quote [Kob94] "...no one can imagine a way of passing from g^a and g^b to g^ab without first being able to determine a or b; but it is conceivable that such a way might exist". The above assumes that all values are computed over GF(p).

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

Message expansion. The size of the encrypted data doubles once encrypted. This however is not a practical issue as ElGamal is only used to encrypt the session key to each recipient.
Signature Strength. Current implementations of DH only offer DSS as the signature algorithm. This limits key length to 1,024-bits which may, on its own, be insufficient for long term security. RSA signatures utilise a key of up to 2048 or 4096 bits (depending on the implementation).
Computational Intensity. Both DH & DSS are more intensive (in terms of processor time) than RSA. On modern processors this difference is not noticeable, but on very lower power devices (Smart cards / embedded chips), DH / DSS may not be viable. If processor time or key size is at a premium then an elliptic curve based asymmetric system may be a better choice than either RSA or ElGamal.
Need for "good" randomness. The random value "k" in DH/DSS needs to be both unique & unpredictable. If an adversary either obtains 2 messages encrypted with the same "k" or recovers "k" then they can obtain the private key [Sch96a] - this is a really catastrophic failure.

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

ElGamal is totally unencumbered by copyright and patents. This means that ElGamal can be used globally without the need for licensing. Use of RSA in US and Canada however requires licensing from RSA Labs for use in commercial products. RSA does provide free licenses for a specific RSA library, but there are some prohibitive licensing issues (see section "RSAREF Licensing Issues").
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.
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].
RSA offers less "security-per-bit" of key material than both DH/DSS.
DH appears to be based upon more solid mathematical theory (see the section "Any recent developments?" for details).
From [Odl99]. DH sessions keys are evanescent. In the simplest application of RSA to key generation, Alice creates a session key and transmits it to Bob using Bob's public key An eavesdropper who can coerce Bob afterwards into revealing his private key can then recover the full text of the communication exchanged by Alice and Bob. In contrast, if Alice and Bob use DH to generate the session key, destroy it after the session ends, and do not store their communication, then neither coercion nor crytanalysis will enable the eavesdropper to find out what information was exchanged.

DH always requires a secure Random Number Generator (RNG), but so does RSA when used to encrypt random session keys (as in PGP, S/MIME etc). A cryptographically secure RNG is already available (See section "How secure is the RNG in PGP?"). A failure in the RNG under RSA would allow an adversary to recover individual messages, but a failure in the RNG whilst using DH/DSS would allow an adversary to recover both the message text and also the private key.

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

[Odl99] contains an excellent overview on the current state of the art in respect of DH.

2.3. What is DSS?

DSS stands for Digital Signature Standard and is formally defined in [FIPS186-1] & [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 document 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 2⁷⁴ steps, rather than the expected 2⁸⁰ 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 [PGP97].

2.5. What is the chance of running out of primes?

There is no chance we will run out of primes.

For example, there are approximately 3.7 x 10¹⁵¹ 512-bit primes. There are approximately 1.5 x 10²⁹⁸ 1,000-bit primes - how many keys do we need? :-)

2.6. 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:

Security. One of key factors of the strength of systems like PGP is the size of the public / private key pairs.
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:

The public key algorithm is not actually used for bulk encryption, instead it is just used to encrypt the session key to each recipient.
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 asymmetric 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]. It is of interest to note that Rivest (the 'R' in RSA) predicted that a 129-bit factorization would take 40-quadrillion years whereas in reality it took just 8 months using idle cycles on computers around the globe [Len96]. I'd say it pays to be cautious with keylengths.

We know that 512-bit keys have been insecure for some time now [Sch96a], [Odl95], [Odl99], [Len96]; 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.

If doubt exists about the ability to factor a 512-bit key one only has to see that a 465-bit key was broken with just 2000 MIPS-years of effort [Paa99] and very recently a 512-bit key was broken with 8000 MIPS-years of effort [RSA99]. For comparison, breaking a 56-bit DES key is 50 times harder than breaking a 512-bit RSA key [Sch99c]. Even more worrying is the fact that this break was undertaken secretly (e.g. didn't involve thousands of machines working across the internet) - in reality people could be breaking e-commerce (e.g. Compaq's online store) keys NOW. Thank god for export controls on encryption, huh?

A very important point from [Sch99c]: "If 512-bit keys are insecure today, they were just as insecure last month. Anyone implementing RSA should have moved to 1028-bit keys years ago, and should be thinking about 2048-bit keys today. It's tiring when people don't listen to cryptographers when they say that something is insecure, waiting instead for someone to actually demonstrate the insecurity.".

Don Johnson says it best [Joh99b]: "One should assume RSA 512 can be broken by a determined attacker."

Modern version of PGP allow only the creation of keys >= 768-bits, so the naive user is afforded some protection from creating an excessively weak key. It has been said that starting from v6.5.1, PGP will have a minimum key length of 1,024-bits [Pri99b]. The question still remains however, what is a "reasonable" size key?

[Odl99] states that "...keys have to be at least 1024 bit even for moderate security, and a least 2048 for anything that should remain secure for a decade...". ANSI X9.31 mandates a minimum RSA key size of 1024-bits [ANSI931].

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 at least theoretically possible [Sil97], [Ley99]. RSA still recommend 768-bit as a minimum but it is expected that keys of this size will be vulnerable within the next couple of years [Sch99c] - it would appear that RSA's recommendations are far too optimistic.

In view of the fact that PGP uses 128-bit session keys, it would be prudent to use DH/RSA keys of around 3072-bits to ensure "equivalent security" [Cer99b].

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.7. The huge key debate.

Cyber-Knights Templar [Cyb99a] have produced an amended version of PGP v5.5 that supports the following enhancements:

Support for RSA keys up to 16,384 bits in length. Signatures using keys of this size take around 2.5Kb :-)
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] & Will Price [Pri98] of NAI), 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].

A further fact which is often overlooked: there are now sub-exponential algorithms for factoring and computing discrete logs (i.e. increase in computing power greatly affects the feasibility of attacking the keys). Such a growth in computing power affects to a lesser degree the feasibility of breaking symmetric keys (i.e. the problem of brute forcing symmetric keys are exponential). Doesn't it therefore make sense to be more conservative (in terms of security) with respect to asymmetric keys, especially since key bits are "cheap"?

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 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-1] and thus should be called something else.

The following table highlights versions of PGP that are compatible or incompatible with certain key-sizes [Cyb99b]:

Algorithm	PGP Version¹
Algorithm	2.6.x	5.x.x	6.x.x	6.x.xic²	6.0.2ckt
RSA	2048 2048	2048 8192	2048 2048	2048 4096	16384 16384
DSA³	-- --	1024 2048	1024 1024	1024 1024	1024 2048
DH	-- --	4096 4096	4096 4096	4096 4096	8192 8192
MD5 Support?	Yes	Yes	Yes	Yes	Yes
RIPEMD Support?	No	Yes	Yes	Yes	Yes
SHA-1 Support?	No	Yes	Yes	Yes	Yes
SHA-1x Support?⁴	No	Yes	No	No	Yes
IDEA Support?	Yes	Yes	Yes	Yes	Yes
CAST Support?	No	Yes	Yes	Yes	Yes
3DES Support?	No	Yes	Yes	Yes	Yes

Table 2: Algorithm restrictions for various versions of PGP

¹	Blue text indicates the maximum key size (in bits) that can be generated by this version. Red text indicates the maximum key size (in bits) that can be understood by this version.
²	The international commercial version available from www.pgpinternational.com
³	DSA keys greater than 1024-bits should not technically be called "DSA" as they are no longer compliant with the standard. It is thought that these longer keys do not significantly increase the security offered by the signature scheme.
⁴	This is a "double-width" version of SHA-1, as per Hash Algorithm ID 4 in [RFC2440]. This hash function has not been shown to offer significantly more security than SHA-1.

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

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

It is quite acceptable to use public, precomputed values for these values [Sch96a], [FIPS186-1], [MOV96], [Kob94], [Sti95]. I would also recommend that the concerned user reads [Sch97a].

The concerned user can choose to switch off the "Faster key generation" if desired (and be prepared to wait far longer for the production of keys).

The problem with using canned primes is that a table of p values needs only to be computed once for the field. Breaking individual keys in this field is then a relatively fast operation. Of course, computing a database of factor base logarithms for reasonable parameters is still impossible, but it would seem prudent from a security perspective to not use canned primes for long term keys [MOV96].

Or in plain English (from [BB99]): "With ElGamal, for example, the expensive key component to generate is the public prime modulus. A group of keys can share a common public modulus with no negative security implications other than that the key presents a fatter target for pre-computation attacks."

My recommendation: turn off the Fast Key Gen option when creating long term keys...It may take longer, but potentially offers more long term security against a concerted attack.

2.9. 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, which is a decision I agree with for the following reasons:

They don't offer any additional security against modern factoring algorithms.
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], [RSA98].

2.10. 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(2ⁿ).

When first introduced, GF(2ⁿ) 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 2⁷⁵⁰ and is prime is thought to offer roughly the same security as GF(2ⁿ) 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-Hellman 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(2ⁿ) then I most highly recommend [Odl83].

2.11. Why are DSS keys significantly smaller than DH keys?

Clearly, if DH keys can be up to 4,096 bits while DSS keys can only be 1,024-bits then there is a serious disparity between the strength offered by these two types of keys.

An initial thought was that DSS keys may offer more security by combining both ElGamal and Schnorr signature schemes but this is untrue however as breaking ElGamal clearly breaks DSS.

A 1,024-bit DSS key appears far easier to break than a DH key of greater length. This is indeed so; DH and DSS are based on the same underlying mathematical theory - a key of 1,024-bits is inherently easier to break than a 4,096-bit key.

So, why the contrast? Well, firstly, PGP simply implements the Digital Signature Standard as per [FIPS186-1]. DSS is the de facto standard for digital signatures, and PGP implements DSS to the maximum strength possible within the bounds of the standard (e.g. with p up to 1024-bits). An implementation of "DSS" with p greater than 1024-bits would no longer conform to the standard.

Secondly, let's look at the purpose of encryption & signature keys. Encryption is used to hide data - a compromise of the key would clearly make all messages readable and would thus make encryption entirely useless. This is a real problem; it will one day certainly be possible to read messages secured with 1,024-bit keys.

Signature keys are used to offer integrity, authentication and non-repudiation. The ability to "break" a DSS key would allow an adversary to forge digital signatures. DSS keys of 1,024-bits are secure for several years, then what? Well, time stamping and document trail mechanisms can be used to "prove" the genuineness of an old digital signature (which could have been forged using what will be current technology). This assumes that there are no totally unexpected breakthroughs in computing discrete logs.

So, one can see that breaking an encryption key is catastrophic, while breaking a signature key at some date in the future is nowhere near as disastrous.

Still, I would personally like to see the option of a "stronger" signature scheme; ElGamal signatures keys with the same length as the encryption keys would be a good choice. I note that ElGamal signatures keys are in the OpenPGP standard, just not currently implemented.

Interestingly though, making the signature keys longer doesn't necessarily make an overall stronger signature scheme. One notes that the only "generally accepted" hash functions MD5, SHA-1 & RIPEMD only offer security around 160-bits (128-bits for MD5). If one uses a 4096-bit RSA / ElGamal signature key with one of these hash functions, are we really increasing security significantly? I would suggest not; a birthday attack could be undertaken against the hash function in 2⁸⁰ operations (or, worse 2⁶⁴ for MD5) thus, against some attacks, throwing asymmetric key bits at the signature scheme may give the naive user a false impression of security in the signature scheme.

DSS is a "balanced" signature standard; the hash function falls to some attacks in around 2⁸⁰ operations, and the signature key length allows some attacks in around 2⁸⁰ operations. Compare this to deprecated v2.x keys, where the signature scheme falls to some attacks in 2⁶⁴ operations while the RSA key can offer security well in excess of 2¹²⁸. Is this very wide discrepancy useful?

One can, quite rightly, make the point that asymmetric keys should afford more security than the strength provided by the underlying hash function; "brute-forcing" the hash function only allows an adversary to forge one message, while breaking the asymmetric key allows an adversary to fake many signatures, so this "equivalent security" argument is tenuous.

Will Price [Pri98] has pointed out that the cryptographic community need to decide upon (or create as necessary) stronger cryptographic primitives. The AES process is selecting a stronger block encryption algorithm and one assumes NIST/NSA will pull a stronger SHS out of the hat?

If you are interested in reading further on this point then I recommend A.M.Odlyzko, "The Future of Integer Factorization" [Odl95] - which also similarly covers key lengths for DH/ElGamal based systems.

The web of trust is based purely on the use of signature keys, the user signs another users public signature key with his private signature key to create a "certificate". The use of a weak signature scheme would make the web of trust in new versions of PGP untrustworthy [Bac99b]. Is this the case yet? No. Will it be the case? Yes, someday.

[Mun99] offers an interesting argument why signature keys can afford to be smaller than encryption keys: "If a highly secret agency acquired the ability to break 1,024-bit keys, long before the public crypto community believed it would be possible, then they could read lots of encrypted traffic, but only as long as the rest of the world believed 1,024-bit keys were still safe. They could use this technology to read encrypted messages routinely, and no one would ever know. But if they used it to forge signatures routinely, certainly this would be noticed. The word would soon get out that 1,024-bit keys aren't safe, and everyone would switch to 2,048-bit keys for encryption as well as for authentication. In other words, by using their ability to forge, they risk losing their ability to decrypt!"

2.12. Doesn't the DSS suffer from subliminal channels?

A subliminal channel allows the leaking of information or key-data to an adversary. For example, an amended version of PGP could be distributed that allows a third party to collect details of your private key from digital signatures.

Farfetched? No! Such a system has been developed [YY96].

DSS can suffer from subliminal channels, but so can RSA, ElGamal, Diffie-Hellman and even symmetric ciphers [YY96]. If you believe that the software you are using could be exploiting subliminal channels then it is important to check the source code to ensure PK parameters are generated in an acceptable fashion. This is simple with PGP, as source code is available for inspection, but may be impossible with other programs.

One notes that Simmons commented that DSS "...provides the most hospitable setting for subliminal communications discovered to date" (also quoted in [Sch96a]). This has subsequently been disproved in [AVPN96]: "...the design of DSA does not maximise the covert utility of its signatures, but minimises them."

2.13. What about Elliptic Curves?

Elliptic Curve systems are specified in ANSI x9.62 & x9.63 & IEEE P1363.

Elliptic Curves first proposed for use in cryptographic applications in 1985 independently by V.S.Miller & N.Koblitz. Elliptic Curves themselves have been studied for many centuries and are [Kob94] "among the most richly structured and intensively studied objects in number theory".

Elliptic Curves are of interest because they have the following benefits over both DH and RSA:

Key size. An elliptic curve key is usually around 160-bits, whilst DH & RSA keys have to be 1,024-bits to afford the same level of security.
Speed. Elliptic curve systems are significantly faster than both RSA & DH based systems (for the same security - not for the same keylengths).

A sub-exponential algorithm exists for solving one class of elliptic curves known as "supersingular curves", though these curves are easily avoided. For the great majority of curves, the only algorithms applicable run in exponential time. This means that EC keys can be significantly smaller than RSA or DH keys to provide similar expected levels of security.

Even though not all factoring methods can be used to break discrete logarithm systems, it is conceivable that a new factoring or DL algorithm could be produced that breaks both RSA & DH. This creates a need for diversification in the design of PK algorithms [Len96]. Or more simply, if RSA & DH are broken by a mathematical breakthrough, it is highly unlikely that elliptic curve based systems will also break.

OpenPGP [RFC2440] supports the implementation of EC technology. PK algorithm ID 18 is reserved for "Elliptic Curve", whilst ID 19 is reserved for "ECDSA" - which is an implementation of the DSA over elliptic curves.

[Kob94] states that "It is likely that the DLP on elliptic curves will prove to be more intractable than DLP in finite fields". Of course, only time will tell.

It has been shown that ECDHP is fully exponential if ECDLP is. This is a major achievement as such an equivalence has never been shown for RSA / IFP or DHP / DLP [Joh99a].

Recently, NIST have specified a collection of elliptic curves for USG use - which is indicative that they trust elliptic curve crypto to some degree [NIST99a].

B.Schneier had the following to say about elliptic curves [Sch99c]: "Certicom used the event to tout the benefits of elliptic curve public-key cryptography. Elliptic-curve algorithms, unlike algorithms like RSA, ElGamal, and DSA, are not vulnerable to the mathematical techniques that can factor these large numbers. Hence, they reason, elliptic curve algorithms are more secure than RSA and etc. There is some truth here, but only if you accept the premise that elliptic curve algorithms have fundamentally different mathematics. I wrote about this earlier; the short summary is that you should use elliptic curve cryptography if memory considerations demand it, but RSA with long keys is probably safer."

S.Schnell of RSA says [Sch97d] "the current limited expertise and understanding of elliptic curve cryptosystems (ECC) represents a significant risk for today's data security applications" - but lets not forget that he works as VP of Marketing for a direct competitor to EC crypto.

T.Elgamal says [Elg97]: "Elliptic curve technology is interesting, perhaps a little newer than factoring or discrete logs, but needs more study and analysis before it is mature." and L.M.Adleman says [Adl97]: "It is correct that I am suspicious of elliptic curve cryptosystems. I have never heard an argument which persuaded me that there were reasons in principle for believing that the discrete logarithm problem on elliptic curves is strictly exponential. I suspect that the lack of a sub-exponential algorithm is merely a matter of neglect and that intense scrutiny - which a commercial implementation of an elliptic curve cryptosystem might engender - could readily change the situation."

At the moment I see no compelling reason to move towards an elliptic curve asymmetric cipher, though one day there may be such a reason. From a security perspective I feel it is prudent to remain cautious in the use of elliptic curves. When used, it is recommended that keys sizes of at least 300-bits are used even for moderate security [Odl99].

Certicom has issued recommendations on EC vs RSA key sizes (of course, one is reminded that Certicom have a commercial interest in EC technology...) [Cer99b]:

Block Cipher Keylength	RSA Key Length	EC Key Length
80	1024	160
112	2048	224
128	3072	256
192	7680	384
256	15360	512

Table 3: Comparison of EC vs RSA keylengths

I suggest those interested in elliptic curves consult the excellent text by Koblitz [Kob94] or the brief summary in [Odl99].

2.14. 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].

Bob Silverman, who is now Senior Research Scientist with RSA Labs, has said [Sil96a]: "I am smug enough to say that NSA can't break RSA or discrete logs."

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], [Sch97c]. From [Sch99a]: "RSA users have to choose a larger key size those using than DH over GF(p), for equivalent security."

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." More recently [Len96] it has been found that ECM cannot be used against discrete logarithms [Len96]. In English, all currently known algorithms 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, significantly 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 the section "Compelled Production of encryption keys", which covers the compelled production of keys.

Comparing the "largest breaks" of each key type, we see that an 512-bit RSA key has been broken [RSA99] but only a 283-bit DH key has been broken [Web99]. The 512-bit RSA break used around 8,000-MIPS years and it has been predicted that the task is equivalent to a DL in a prime field with a characteristic of 365-bits [Web99].

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.15. 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.16. What are the performance differences for encryption between RSA & ElGamal?

Encryption timings (in milliseconds on a Sparc II) from [Sch96a]:

	RSA-1024 (1024-bits)	ElGamal (1024-bits, 160-bit exp)
Encrypt	8	109
Decrypt	93	77

Table 4: Asymmetric 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.17. 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 5: Asymmetric 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 infeasible.

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 is a non-cryptographic mechanism for detecting transmission errors [MOV96], [RSA98].

PGP uses a checksum value to:

Produce non-cryptographically secure pseudo-random numbers. A strong PRNG exists for the production on numbers that need cryptographic security.
Checking whether a message has been corrupted during transit. Note that this is in addition to any cryptographically secure method of error detection. (Interesting aside: OpenPGP (v1) doesn't mandate that conventionally encrypted non-signed messages are error checked - so errors may exist without warning [Bac99a]).

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:

Creation of Digital Signatures. The message is passed through the hash function and the resulting hash value is signed with the users private key.
Whitening 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:

The function is One Way - that is to say it should be "hard" to find a message that hashes to a pre-specified value.
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 "Has MD5 been broken?"). 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 RIPEMD-160?

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

To date there have been no successful cryptanalysis of RIPEMD-160 which produces an output of 160-bits.

There are versions of RIPEMD hash function offering hash lengths of greater than 160-bit security (256-bit and 320-bit to be precise) but these hash functions are, according to the authors [DBP99]: "RIPEMD-256 and RIPEMD-320 are optional extensions of, respectively, RIPEMD-128 and RIPEMD-160, and are intended for applications of hash functions that require a longer hash result without needing a larger security level."

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 [Dob96a].

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 [Dob96a], for example in the creation of digital signatures (the main application of a hash function in PGP). To quote Hans Dobbertin directly [Dob96a]: "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:

Pseudo-collisions have been found in the compression function.
Collisions have been found in the compression function. This violates the design goals of MD5.
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. What are the implications of the attacks against MD5?

The MD5 attack was first detailed in [Dob96a].

The attack does not currently allow an adversary to create a slightly altered message given an arbitrary message that will match hash values. That is to say given a message A, an adversary cannot feasibly find a message B that hashes to the same hash M.

What it does potentially allow an adversary to do is create a message A with a related, but different message B, that hashes to the same M. Practically, you should sign message only when a third party does not have influence over the message being signed.

The long and the short of it: MD5 should no longer be used universally without forethought. Users have to be careful when considering which documents to notarise or sign with MD5. Compare this with SHA-1 & RIPEMD with which no such forethought is necessary (because no B can be found that hashes to the same M with these two alternative algorithms).

If you are interested then I recommend [Dob96b] for a (slightly outdated) description of the status of MD5. The paper says in conclusion "...might indicate that there is a serious security problem with MD5...but in future implementations better move away from MD5".

3.9. 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, and as yet unknown, attack.

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

3.10. Has RIPEMD been broken?

The original RIPEMD was released in 1992 but was subsequently found to have some significant weaknesses [Dob95], [MOV96]. Subsequently a modified version was created, called RIPEMD-160 which does not suffer from the deficiencies of the previous version. The new version of RIPEMD is approximately half as fast as the previous version - which gives some idea of the significant security improvements made between versions.

RIPEMD-160 as implemented in PGP has no known weaknesses.

3.11. Which is stronger, MD5, SHA-1 or RIPEMD-160?

Certainly not MD5 (see section "Has MD5 been broken?").

The choice would therefore appear to be between SHA-1 and RIPEMD-160. 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], [Dob96a]. 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 either SHA-1 or RIPEMD.

3.12. What are the performance differences between MD5, SHA-1 & RIPEMD-160?

Hash function timings (in Mbit/s on an unspecified platform) from [PBD97]:

	MD5	SHA-1	RIPEMD-160
Assembly	136.2	54.9	45.3
C	59.7	21.2	19.3

Table 6: Hash function speed comparison

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

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, invertable.

An excellent (and free!) introduction to block ciphers is the paper [Mir98].

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

Block ciphers are used in numerous areas of PGP:

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.
Maintaining the pool of random data.
Encrypting the keys stored in the private keyring. This keyring holds the private decryption key(s) and it is imperative that this file is encrypted in a "secure" manner. It is interesting to note that the whole of private keyring is not encrypted - but only the actual private key data. Thus someone obtaining a private keyring would obtain details of all 'nym userids and public parameters [Bac99a].

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:

Truncated differential attack, effective up to 3.5 rounds of IDEA [KR97].
Chosen-key differential attack on a very much weakened version of the cipher with 3-rounds [KSW96].
Chosen-key ciphertext-only timing attack on the full cipher that requires 5x2¹⁷ related key queries, each used to perform 2²⁰ random unnamed plaintext blocks [KSW96].
A combination of both differential and linear cryptanalysis which requires 2²⁹ chosen plaintext pairs and a workload of 2⁴⁹ additions modulo 2¹⁶+1 on a very much weakened version of the cipher with 3-rounds [Bor96].
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].

IDEA also has a large (2⁵¹) class of weak keys, as outlined in [DGV93]. This is not a major concern as the chances of picking a weak key is 2^-77 [MOV96].

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 superseded by the Triple-DES algorithm, 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 Encrypt-Decrypt-Encrypt (EDE) configuration with independent keys. Encryption is executed as follows:

CipherText = DES_k1(DES^-1_k2(DES_k3(PlainText)))

And decipherment is:

PlainText = DES^-1_k3(DES_k2(DES^-1_k1(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:

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, 2¹¹² encryptions and 2¹¹² table lookups [MOV96], [Luc98].
Optimised MITM attacks. Time / memory trade-offs applied to the standard MITM attack that can make the MITM slightly more feasible [Luc98]. 2¹⁰⁸ operations are still required for the "feasible" (in terms of memory) attacks.
Related key attack. Needs one chosen related-key query, one chosen-ciphertext query and 2⁵⁶ to 2⁷² offline trial encryptions [KSW96].

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

4.6. What is AES?

Advanced Encryption Standard (AES) is the US Governments search for a replacement to the ageing DES standard(or Data Encryption Standard).

The National Institute of Standards and Technology (NIST), first called for algorithms 12^th Sept 1997 [NIST97]. Several very well known cryptographers (Rivest, Schneier, Knudsen, Biham, Rijmen, Coppersmith etc) developed AES candidate algorithms that met the criteria. Of the 15 initial algorithms meeting the criteria, 5 (Mars, RC6, Rijndael, Serpent & Twofish) have been selected to enter round 2. An eventual candidate is expected to be named as 'AES' sometime in year 2000.

Although this selection process only selects a cipher for USG use, it is believed that AES, when selected, will become the international standard for encryption into the next millennium. All AES candidates accept keys of 128, 196 or 256-bits and have a block size of 128-bits.

The OpenPGP standard [RFC2440] has allocated ID 7,8 & 9 for the 128, 192 & 256-bit keys respectively.

Anyone interested in reading more about AES is advised to see the NIST Round 1 report [NIST99b].

4.7. What is Twofish?

Twofish is an AES candidate produced by Schneier, Kelsey, Whiting, Wagner, Hall, Ferguson first presented in [SKWWHF98]. It is included as a separate section in this document because OpenPGP & NAI have decided that Twofish is such a promising cipher that it should be added to PGP prior to the outcome of the AES process [Koc98], [Pri99a].

Twofish is an evolution of the cipher Blowfish. Most changes seem to have been made to meet the AES criteria. Currently, there is no known way of breaking Twofish short of brute force, though this is to be expected considering the short time since publication.

Personally, I believe that it is a BAD idea to include Twofish as a cipher at this stage. My original comments on the choice [Sim99] were:

"It has previously been mentioned that Twofish would be added to PGP before completion of the AES process. I think everyone would agree that the move to a 128-bit block, 128/192/256-bit key cipher is a Good Thing, but the point of this message is to ask "why the choice of Twofish?"

Is strength (or "expected strength" at this stage) the criteria? If you're going to select a cipher from the x candidates (many of which, including Twofish, have only had 8 months peer-review) then surely you would go for the most ultra-conservative design? Even better, wouldn't you select a cipher which has been analysed for a longer period? Is speed a selection criteria for block ciphers in PGP (if so why 3DES)? Is heritage the criteria? If so, there are other candidates with a similar heritage: MARS (Coppersmith) , RC6 (Rivest), Serpent (Anderson, Biham & Knudsen), Rijndael (Daemen & Rijmen), DFC (Vaudenay), CAST-256 (Adams) etc. Are patent issues part of the criteria? We would expect so (in view of IETF views on this matter and the OpenPGP standard). This potentially discounts RC6 & MARS and one or two others. Are some of the more obscure (and of little practical importance in PGP?) criteria being considered? For example: key agility, resistance to timing / power analysis, smart card / hardware implementation, scalability to 64-bit architectures. I am a great fan of Bruce Schneier (and Twofish actually) - but isn't it too soon jump on the bandwagon? One notes that Twofish has received some criticism in AES Conference II papers: 1) "Report on the AES Candidates" by Vaudenay et al. Points out that S-Boxes should "no longer be called key-dependant". Also says "consists of a collection of patches" & "we do not think this design comes from deep investigation". Of course, this paper is written by the authors of another AES candidate. 2) "An observation on the Key Schedule of Twofish" by Mirza & Murphy (RHBNC), points out several deficiencies with the key schedule. Implications unknown, but it does directly contradict implicit claims in the original Twofish paper. None of the candidates escaped criticism from a "cryptographic security" point of view, but if one wanted to objectively select an AES candidate by any combination of the above criteria, would we logically select Twofish at the moment?

My main concern is that naive users will see "Twofish" & "Schneier" and create keys specifying this algorithm. Sure, the User Manual will no doubt state "Twofish is new blah blah blah" but, in my experience, users never RTFM anyway."

Basically I believe that Twofish is far to new to field in live cryptographic systems. Similar thoughts are expressed in [Pre99], [Knu99].

In my opinion, the saving grace is that recipients of messages in PGP have the choice of which symmetric ciphers they are willing to accept. For example, if the OpenPGP standard offered a simple XOR algorithm (totally insecure!), then recipients can simply disable this algorithm and they will never receive messages encrypted with this algorithm.

4.8. 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 2⁵⁶ keys until the correct one is found. Brute force takes, on average, 2^KeyLen-1 operations - so in the case of DES the machine has to try approximately 2⁵⁵ trial decryptions before being rewarded with the correct plaintext. One notes that brute force attacks are usually thought of as known-plaintext, but [WB94] outlines a chip capable of recognising correct decryption - this makes a brute force feasible even if a known-plaintext block is not known.

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 2⁵⁶ (approx. 10¹⁷) times harder to break than single DES [CYL98a] and as such can be considered very secure. An adversary would have to try on average 2¹¹¹ 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], [WB94], [Sch96a], [MOV96], [RSA96a], [RSA98], [Sch98g]. 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 10¹⁷ stronger than single-DES, we do a little arithmetic and find that this $300M computer can break a triple-DES key in about 4x10¹⁰ years, or about the age of the universe."

In the words of Bruce Schneier [Sch98g]: "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.9. 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.10. Which is stronger, IDEA, CAST, 3DES or Twofish?

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.".

Twofish is far to new to be considered stronger than either of the other 3 ciphers. In time it may be seen as secure, but for now it just hasn't been subjected to enough analysis. Some have claimed that because Blowfish is trusted, we should trust Twofish [Blu98] though this is simply not true. They are both BFN etc and the key schedule consists of iterations of a function used in encryption, but there are also many differences between the two ciphers. Small changes in block ciphers can move a cipher from "thought to be secure" to "trivially" broken.

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

The good write-up in Applied Cryptography [Sch96a].
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."

David Wagner has said [Wag99a]: "3DES is still my cipher of choice for security-critical applications."

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

The government's commitment to EES and DES is inconsistent with this objective.
Triple-DES is not exportable.
Further proliferation of triple-DES is counter to national security and economic concerns.

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], [Sch98g].

An NAI employee has expressed the opinion that [Pri99a]: "I'll choose CAST5 over either of those algorithms [Blowfish & 3DES] any day -- although I do believe all three are 'secure' in a general sense." A view I (and many other cryptographers) disagree with....

To summarise, CAST is the default algorithm for new keys produced with PGP v5+, but 3DES is the MUST algorithm in the OpenPGP standard (e.g. all implementations of the standard must provide the 3DES cipher). Personally, I'd use 3DES as my default cipher if I were creating a new key.

4.11. 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:

Every single computer (estimated at 3*10⁸) on the earth is used full time.
Every computer has the processing power of a PII 450Mhz.

Then a single (3DES) key can be brute forced in an average of 10¹¹ (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: 2¹¹¹ / 3*10⁸ / 18,921,600,000,000

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

It is assumed that computing power will remain constant.
It is assumed that the number of computers remains constant.

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

The number of computers in the world is equal to 100 Billion (that�s ten for every single person on earth in the year 2014 - there are expected to be 10 billion people (10¹⁰) alive in 2014).
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 infeasible within 10 years or so.
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 HW¹
Cipher	Effective Key Size	500 Supercomputers²	10 Billion computers (PII 450)³	100,000 Deep Crack machines⁴
3DES	112	61	44	45
CAST	128	85	65	69
IDEA	128	85	66	69

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

¹	Calculated using 'LOG((2^KeySize-1)/((KeysPerSecond606024365)NumberOfMachinesYearsSafetyMargin))*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.
²	It is assumed that each supercomputer can manage 10 Billion keys per second, regardless of the cipher employed.
³	Figures based on 10 processors per person [Odl95], CAST & 3DES implementation by A. Bosselaers ASM implementations, IDEA implementation by H. Lipmaa, timings from [Lip99].
⁴	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.12. Why doesn't PGP use a "provably secure" cipher?

Because there are no practical ciphers which offer a general proof of security!

Some ciphers offer provable security against certain specific classes of attacks (e.g. DFC [GGH+98]), and others offer a more general proof of security based upon some currently unproven underlying assumptions (e.g. Bear [AB96]). But none of these algorithms have undergone a significant amount of analysis.

The Twofish paper [SKWWHF98] states that "Any reasonable proof of general security for a block cipher would also prove P != NP". Similarly, [Bih99] states that "The search for provable security is still in progress, but it is not expected that a full proof of security of any cipher will be found in the next decades, as this proof is closely related to proving lower bounds of computational complexity, and to the problem of the relation of the classes P and NP."

[MOV96] says about unconditional security: "...it requires as many bits of secret key as plaintext and cannot be provided by a block cipher used to encrypt more than one block". Not very useful!

So, without using a One-time pad (also known as a Vernam cipher), w

Sam Simpson

Blog Tags

Recent Posts