Archive-name: PGP-DH-RSA
Version: 1.5
Last-modified: Thursday, 20th 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 - 20th 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 - 18th 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 - 16th 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 - 3rd 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 - 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
* 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:
a. Has PGP been broken?
b. Which version of PGP is stronger, RSA or DSS/DH?
c. Why doesn't PGP support RSA as standard anymore?
d. Is PGP cryptographically less secure than S/MIME?
e. 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 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 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 6th 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 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". The above assumes that all values are computed over
GF(p).
There are several downsides to using DH compared to using RSA:
a. 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.
b. 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).
c. 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.
d. 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:
a. 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").
b. 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.
c. 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].
d. RSA offers less "security-per-bit" of key material than both DH/DSS.
e. DH appears to be based upon more solid mathematical theory (see the
section "Any recent developments?" for details).
f. 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 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 [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 10151 512-bit primes. There are
approximately 1.5 x 10298 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:
i. Security. One of key factors of the strength of systems like PGP is the
size of the public / private key pairs.
ii. 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:
i. The public key algorithm is not actually used for bulk encryption,
instead it is just used to encrypt the session key to each recipient.
ii. 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:
a. Support for RSA keys up to 16,384 bits in length. Signatures using keys
of this size take around 2.5Kb :-)
b. 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 Version1
2.6.x 5.x.x 6.x.x 6.x.xic2 6.0.2ckt
RSA 2048 2048 2048 2048 16384
2048 8192 2048 4096 16384
DSA3 -- 1024 1024 1024 1024
-- 2048 1024 1024 2048
DH -- 4096 4096 4096 8192
-- 4096 4096 4096 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?4 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
1 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.
2 The international commercial version available from
www.pgpinternational.com
3 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.
4 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:
i. They don't offer any additional security against modern factoring
algorithms.
ii. 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(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-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(2n) 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 280 operations (or, worse 264 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 280 operations, and the signature key length allows some
attacks in around 280 operations. Compare this to deprecated v2.x keys,
where the signature scheme falls to some attacks in 264 operations while the
RSA key can offer security well in excess of 2128. 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:
i. 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.
ii. 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 ElGamal
(1024-bits) (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:
a. Produce non-cryptographically secure pseudo-random numbers. A strong
PRNG exists for the production on numbers that need cryptographic
security.
b. 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:
a. Creation of Digital Signatures. The message is passed through the hash
function and the resulting hash value is signed with the users private
key.
b. 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:
a. The function is One Way - that is to say it should be "hard" to find a
message that hashes to a pre-specified value.
b. 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:
a. Pseudo-collisions have been found in the compression function.
b. Collisions have been found in the compression function. This violates
the design goals of MD5.
c. 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:
a. 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.
b. Maintaining the pool of random data.
c. 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:
a. Truncated differential attack, effective up to 3.5 rounds of IDEA
[KR97].
b. Chosen-key differential attack on a very much weakened version of the
cipher with 3-rounds [KSW96].
c. 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].
d. 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].
e. 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 (251) 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 = DESk1(DES-1k2(DESk3(PlainText)))
And decipherment 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:
a. 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].
b. Optimised MITM attacks. Time / memory trade-offs 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.
c. Related key attack. Needs one chosen related-key query, one
chosen-ciphertext query and 256 to 272 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 12th 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 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. 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 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],
[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 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 [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:
a. The good write-up in Applied Cryptography [Sch96a].
b. 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:
i. Every single computer (estimated at 3*108) on the earth is used full
time.
ii. Every computer has the processing power of a PII 450Mhz.
Then a single (3DES) 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:
i. It is assumed that computing power will remain constant.
ii. 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:
i. 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 (1010) alive in 2014).
ii. 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.
iii. 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 Years until break feasible with different
Key Size HW1
500 10 Billion 100,000
Supercomputers2 computers Deep Crack
(PII 450)3 machines4
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.
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.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), which is
impractical, PGP has to do the "next best thing" - using a well trusted
block cipher offering heuristic security. Of all the block ciphers in the
public literature, 3DES appears to be the closest we have to an "ideal
cipher" in terms of strength.
The best we can hope to do is use our complete arsenal of analysis tools to
try and prove that a cipher is insecure. If it fails to succumb to these
tools then it is not proven to be secure, but it indicates that a degree of
faith can be placed in the cipher.
4.13. What are the performance differences between IDEA, CAST, 3DES &
Twofish?
Symmetric cipher timings (in Mbit/s on a 200Mhz Pentium) from [Lip99]:
3DES CAST5 IDEA
Assembly 13.8 58.2 35.8
Table 8: 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 or a key icon
with a head on it. 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 or a key icon with a head on
it 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:
a. Decrypt any messages sent to keys contained on your keyring. This
includes past messages, current messages and any future messages.
b. 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:
a. Don't store the file on a network or shared drive. I, for example,
store my keyring file on a ZIP disk.
b. 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], [Bac99b]. 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]:
a. provide complete application source code to RSADSI;
b. grant RSADSI the right to redistribute such application
c. distribute source of the application with each binary
d. 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 or BNLIB 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 CryptoAPI (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:
a. All messages past, present & future could be decrypted.
b. Digital signatures could be forged.
Obviously, these two points are disastrous so PGP now offers solutions to
both of these issues:
a. 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)
b. 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 the "Does anybody really bother
checking the PGP source code?" 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-1].
As a matter of personal interest, I abstracted the RNG functionality from
PGP v5.0i 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!):
a. 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 [Hit98].
b. Relating to DSS, Schnorr has implied that DSS infringes on Claim 6 of
his US patent 4,995,082 [Sch98j]. Schnorr has compared DSS & his patent
in [Sch98k].
[FIPS186-1] states decisively "The Department of Commerce is not aware of
any patents that would be infringed by this standard." & in [NIST98] "NIST
is not aware of any U.S. patent which might be infringed by the practice of
the invention claimed in its patent on DSA....NIST is not aware of any U.S.
patent which might be infringed by the use of SHA or SHA-1."
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.
RSA is still patented in the U.S. In Sept 2000 the patent will expire.
Amusingly, RSALabs have indicated [SD99] that they are to trademark the term
"RSA", despite previously assuring IEEE to the contrary [SD98]. It would
appear that in Sept 2000 users will be allowed to use the RSA scheme, but
vendors will be force to call it something else!
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, RIPEMD-160 against test vectors. I have also tested
the code used for DSS signature generation against the test vectors provided
in [FIPS186-1] 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
"How secure is the RNG in PGP?"
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 [BW94], [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:
i. DL & IFP based PK systems can be broken in polynomial time [RSA96a]
(e.g. QCs can factor and compute discrete logs of any size in
polynomial time.)
ii. 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.
Professor Peter Knight, a lead physicist researching into QCs has commented
that [Bro99] "It looks a long way of...if in four years we have worked out
how to build a machine that uses quantum mechanics to factories 15, everyone
will be hugely pleased."
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.
Currently, supercomputers can manage approximately 1012 operations per
second. It is thought plausible that a DNA based computer could exceed 1012
operations per second [MOV96]. The DNA based computer would also require
more modest energy & cooling requirements.
I highly recommend the papers [Bea95] & [Sho94] as an overview of DNA and QC
respectively, and in particular their practical application to factoring.
[Gro99] is also a good non-technical paper covering QC.
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:
i. Printing the PGP source code.
ii. 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.
iii. 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"
Without source code review, how do you know that the cryptographic system
isn't leaking key information with every signature or encryption performed?
Signatures employing subliminal channels are indistinguishable from normal
signatures - only the adversary (who has a secret key that allows them to
unlock the subliminal data) is even aware that the subliminal channel
exists.
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].
Very recently NIST have announced that the DES, DSA & SHA-1 algorithms from
the PGP Cryptographic SDK, version 1.5 have now been validated under
FIPS140-1 [NIST99c].
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 the 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-1], 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]:
* University professors use PGP to protect intellectual property.
* Accounting firms use PGP to protect backed up data.
* Lawyers use PGP to communicate confidentially with clients.
From [Zim98a]:
* Account of human rights activists in Romania - lives were probably
saved by the use of PGP.
From [WIR99]:
* In July 99, Republican legislators for the first time submitted a bill
to President Clinton via e-mail. What did Congress use to digitally
sign the bill? PGP.
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:
i. How does encrypting messages to multiple recipients affect the security
of the message?
ii. 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 the symmetric
cipher or any of the asymmetric 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 infeasible. But hang on -
breaking a single level of military grade encryption is totally infeasible
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. Note: this does not affect the "inner layer" -
this is as hard to break as any normal single PGP message.
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. What are the implications of Shamir's TWINKLE device on PGP security?
"TWINKLE" is a theoretical device thought up by Adi Shamir early in '99
[Sha99]. It stands for The Weizmann Institute Key Locating Engine.
TWINKLE is a sieving machine that can be used to break RSA keys and, to a
lesser extent, DH/DSS keys. To my knowledge, no TWINKLE machines have yet
been implemented, but they are thought to be practical. Rather than
inventing a new method of factoring, TWINKLE simply speeds up the
implementation of an existing algorithm (NFS).
NFS consists of two steps:
* Sieving. This step can be distributed among multiple machines.
* Solving the Matrix. Currently can only be performed on a single
machine. Very memory intensive.
Where feasible, the TWINKLE device dramatically speeds up the sieving
portion of NFS. A conventional computer is still then required to solve the
resulting matrix.
Recently, a team broke a 465-bit number using NFS. The sieving portion took
200 computers 4 weeks and solving the matrix took a CRAY supercomputer 4
days and 810Mb of RAM. In contrast [Sil99a], 6 of Adi Shamir's TWINKLE
machines would take about 6 days to undertake (plus 4 days on the
supercomputer to solve the matrix).
Unfortunately, it doesn't appear likely that TWINKLE can scale to 1,024-bit
(or even 768-bit) keys. It is projected that 45,000 TWINKLE devices would
take 500,000 years to sieve a 1,024-bit number and solving the matrix would
take at least 5 terabytes of RAM & in excess of 5 million years [Sil99b].
Realistically, it appears that TWINKLE is only a threat to keys in the
512-bit to 600-bit range.
TWINKLE can attack DH/DSS keys in the same way as RSA keys. BUT (and it's a
big but...), solving the matrix with DH keys is much harder as one has to
[Sil99b] "solve the matrix modulo the order of the group or field" rather
than mod 2.
It is also interesting to note that ECC security estimates are unaffected by
TWINKLE [Sil99b], [Cer99a].
Really, TWINKLE confirms previous thoughts:
* 512-bit keys are now insecure against a determined adversary.
1,024-bits keys are still thought to be secure.
* RSA keys are practically more susceptible than DH keys of the same
size.
The bottom line: PGP (since v5.5) only allows the creation of keys >=768-bit
- so no recently produced PGP keys are at risk by this development.
If you are interested in reading about TWINKLE then I'd recommend the
original paper by Adi Shamir [Sha99] and the analysis by Robert Silverman
[Sil99a].
7.20. What are the implications of the NSA key in CryptoAPI on PGP Security?
CryptoAPI is present in all modern version of Windows, including NTv4,
Windows 2000, Windows 95 & Windows 98 and offers cryptographic primitives
for use in high level applications (such as the SSL implementation in
Internet Explorer and the S/MIME implementation in Outlook).
Recently it has been disclosed that CryptoAPI (Microsoft's Cryptographic
API) has a "secret" key that enables the holder of the key to sign CryptoAPI
modules (these modules are known as CSPs, or Cryptographic Service
Providers) - these modules can then be silently installed onto a users
machine. The real big news is that this key is call _NSAKEY internally by
windows. This has led to speculation that this key is really a NSA owned key
that allows them to remotely install weakened crypto onto users machines
etc.
The _NSAKEY variable name was only discovered by accident - MS forgot to
strip the symbolic debugging information from NT v4 SP5 which allowed
A.Fernandes of Cryptonym to detect the name of the variable and work outs
it's use in signing CSP's.
Microsoft have denied these accusations claiming that "We do not share them
[the keys] with any third party, including the National Security Agency or
any other government agency." and that the second key is required as a
backup and to comply with export regulations. They also unconvincingly claim
that the variable name _NSAKEY is "...simply an unfortunate name." [Mic99].
There is no doubt that this issue has been over-hyped to some degree, but
personally I am not convinced by Microsoft's flimsy "rebuttal". I simply
don't believe that we know the true reason that the second keys are in every
copy of Windows.
The CryptoAPI matter is a concern to some PGP users who operate under Win32
(e.g. Windows 95, Windows 98, Windows NT v4, Windows 2000) as some versions
of PGP rely on the CryptoAPI for RSA support.
From [Sal99], the following table details how RSA support is implemented in
various versions of PGP:
PGP Version RSA Support Via:
v5.0 Freeware RSAREF1
v5.x Commercial (with RSA support) PGPInc Code
v5.x Commercial (without RSA support) None
v5.5.3 Freeware None
v6.x Commercial (with RSA support) BSAFE2
v6.0.2 Commercial (without RSA support) CryptoAPI3
v6.0.2 Freeware CryptoAPI3
v6.5.1 Commercial (with RSA support) BSAFE2
v6.5.1 Freeware RSAREF1
Table 9: How is RSA supported in modern PGP versions?
1 RSAREF = special non-commercial RSA library provided by RSADSI
2 BSAFE = standard commercial RSA library purchased from RSADSI
3 CryptoAPI = MS CryptoAPI including RSA code licensed by MS from RSADSI.
RSA support via CryptoAPI is only provided on machines with "domestic"
(e.g. 128-bit) browsers.
It is important to note that, apart from RSA support in the highlighted
versions, PGP does not rely on CryptoAPI (or any other 3rd party
libraries...) for any other cryptographic primitive. Hash functions,
symmetric ciphers, DSS etc are all provided by in house code.
I can confirm that International builds by:
* Stale Schumacher, as distributed from www.pgpi.com
* CKT builds by Imad R. Faiad
* "official" NAI international builds from PGPInternational
all use the PGPInc home grown code rather than RSAREF, CryptoAPI or BSAFE.
From a security perspective, I would certainly say that it makes senses at
the moment to avoid any versions of PGP (e.g. v6.0.2) that rely on CryptoAPI
if you need RSA support. Maybe if Microsoft come up with a reasonable
explanation then I'll recommend RSA support provided by CryptoAPI - but
somehow I doubt it.
Anyone interested in reading more about this saga should firstly consult the
original Cryptonym press release [Cry99] then secondly read the totally
unconvincing Microsoft press release [Mic99]. I'd also recommend reading the
considered comments by B.Schneier [Sch99b], M.Blaze [Bla99], D.Wagner
[Wag99b] & M.Kuhn [Kuh99] all of whom disagree that this is some major
conspiracy involving the NSA & Microsoft.
7.21. Why perform signing before message encryption?
When a user requests that PGP encrypt & 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:
i. 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?
ii. 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 receiver's 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.22. 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 10: 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 in
section "How big should my asymmetric key be?" 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, allow 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 key 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 but, interestingly, PGP v5.x + include a feature called
Additional Decryption Key (ADK) - sometimes also referred to as Corporate
Message Recovery. As previously mentioned, this feature does not form part
of the OpenPGP standard. Users interested in reading about this feature are
pointed towards [Bar99a].
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 "Does anybody really bother checking the PGP source code?". 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].
A more recent paper discussing the merits of open source security components
is available at [Sch99c]. My favourite quote of the paper is: "As a
cryptography and computer security expert, I have never understood the
current fuss about the open source software movement. In the cryptography
world, we consider open source necessary for good security; we have for
decades."
A version of S/MIME could be released (or could already be deployed?) that
implements "Kleptography" - e.g. implementing key-generation routines in DH
or RSA that produce keys which appear normal, but which allow a third party
(who has knowledge of an "unlocking key") to retrieve the private key. This
is an interesting development on the concept of subliminal channels, first
documented by Gus Simmons. For further information, the reader is directed
towards the paper [YY96]. No such covert channel exists in PGP v5.0i - a
quick review of the source code would reveal the offending code.
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 do
not inter-operate 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:
a. S/MIME is limited to 1024-bit public keys; PGP can accommodate keys of
up to 4096-bits.
b. The S/MIME certification standard contains facilities that can be used
easily for mandatory escrow. No such feature is present in the PGP
standard.
c. 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].
d. 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."
Once again, to quote Schneier [Sch98i]: "The S/MIME 2 e-mail standard took a
relatively strong design and implemented it with a weak cryptographic
algorithm"..."Functionality does not equal quality, and no amount of beta
testing will reveal every security flaw".
An article written by a well known cryptographer [GW96] has claimed about
Netscape Navigator (a well known program that purports to implement the
S/MIME standard) "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".
7.23. Program x offers 200-bit keys, is it better than PGP?
This is a question often asked by new users, and it raises a number of
interesting points:
a. The need for larger keys. Does the use of keys larger than offered in
PGP offer any practical additional security?
b. Source code released for peer review?
c. Does the software enjoy the widespread use of PGP? Will your intended
recipient have a copy of the program?
d. Has the software been peer reviewed as extensively as PGP?
e. Are all of the other cryptographic primitives (symmetric and asymmetric
ciphers, hash function etc) equally strong? Does it use a "custom"
cipher - these are invariably weaker than tried and tested algorithms.
f. Are there protocol failures?
Unfortunately, cryptography isn't like any other science; we (usually) rely
on empirical evidence to judge the strength of algorithms employed and the
system implementations. Bad crypto looks and smells just like good crypto.
Sometimes it's useful to think of encryption as a combination lock on a
safe. Is it better to have a lock with a greater number of possible
combinations? All other things being equal, the answer is yes. But those
"other things" are usually not equal. Some locks can be "picked" without
trying all the possible combinations. You wouldn't want your household
valuables to be protected by a lock that has trillions of possible
combinations, but can be opened quickly by a person with a stethoscope.
Short keys guarantee weakness, but long keys don't guarantee strength.
If you have read the above (and I'd suggest the Snake Oil FAQ), and still
think that the benefits outweigh the disadvantages, then help yourself!
7.24. So PGP is perfect?
No.
PGP is an evolving standard and as such is constantly improving. The
following list highlights common gripes about cryptographic elements of
OpenPGP:
a. Disparity in signature key size for DSS. DH keys can be up to
4096-bits, signature keys limited to 1024-bits. Situation should change
with the introduction of a new federal signature standard, but this
could take some time. As a work-around implementations could offer
ElGamal signatures greater than 1024-bits (as supported in the OpenPGP
standard).
b. Some implementations offer a feature known as "Additional Decryption
Key" (ADK). This is, in my humble opinion, truly awful and thankfully
has been dropped from the OpenPGP standard. See [Bac99b] for an
argument explaining why CMR is unacceptable.
c. The common use of "Encrypt to self" as a mechanism for providing
"secure" storage of sent mail. Ideally PGP would provide a separate
"archive" key used to encrypt data for long term storage [Bac99b].
d. The inclusion of Twofish in the OpenPGP standard. This cipher was added
as a "gut feel" by the OpenPGP group, but I don't think objectively
that Twofish is a good choice at the moment. Also, are we in any great
hurry to add new (and unproven1) ciphers? Are the ciphers we currently
use so deficient that we need to add ciphers? No, I don't think so.
Concerned users can of course disable the Twofish algorithm.
----------------------------------------------------------------------------
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:
a. 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.
b. 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 the section "RSAREF License
issues"
c. 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.
d. 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.
e. 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.
f. 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], [Sil96b] (also see Note
4), all of which have, by now, been extensively tested.
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, or if a new version of PGP is not available
for your operating platform.
8.1. Summary of PGP DH versus PGP RSA
In summary, DH PGP keys can be considered stronger than PGP RSA keys for the
following reasons (I have removed references from this section for clarity -
refer to previous sections of the document for justification of these
claims):
1. DH & DSS offer slightly more security per bit than RSA. This is likely
to remain the case. Conversely, RSA offers more security per clock
cycle than DH/DSS.
2. The hash used by RSA keys is badly flawed. Remember Schneier's comment
"I am wary of using MD5". DH keys use SHA-1 (or RIPEMD). Sure, it's
possible (with new versions of PGP) to select the hash function used
with RSA keys, but these signatures are incompatible with standard v2.x
versions of PGP and also continue to suffer from key ID attacks
(described next). RSA keys always use MD5 to create key fingerprints
[Bar99b].
3. RSA keys can be created with an arbitrary Key ID or fingerprint - which
can thus be used to spoof keyservers. This is just not possible with DH
keys.
4. DH keys offer a choice of multiple ciphers. If one cipher is broken
then not all DH keys will be useless. If IDEA is broken then all RSA
keys are useless.
5. DH keys consist of two components: signature keys and encryption keys.
Breaking (or being forced to divulge) one of the keys doesn't break the
other. Breaking an RSA key allows an adversary to perform both
decryption and signing.
6. DH keys can have multiple decryption subkeys. In this way a master
(signature) key can be kept for many years while multiple decryption
subkeys can be used to minimise the damage due to a "major break" in
one of the encryption keys. Again, this feature is not available with
RSA PGP keys.
7. Theoretically, DH keys appear stronger than RSA keys. One notes that
some instances of the DHP are provably equivalent to the underlying
hard mathematical problem (DLP). No such equivalence has been shown for
RSA, in fact some instances of the RSAP are provably not equivalent to
the underlying hard problem (IFP).
The only arguments I can make for not using DH/DSS keys is that RSA
signature keys can be significantly longer than DSS keys, however this point
is easily countered:
1. "Standard" (e.g. out of the box) RSA signatures are based upon MD5,
which is now considered all but broken.
2. If long term security is required from digital signatures, you can
simply use time stamping & document trail mechanisms.
Please let me know if you can think of other reasons why either key type is
more or less strong than the other.
8.2. 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.
The most significant threat to PGP comes from user sloppiness. 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.3. 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:
a. Inspecting the source code and satisfying yourself that it functions
correctly.
b. Using an older version of PGP.
c. Moving to another encryption system (S/MIME for example - and put up
with the inevitable severe security limitations).
d. 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).
e. Using PGP v6.02 (without RSA support) under the 128-bit version of IE
v4 which offers some limited RSA support via CryptoAPI.
f. Paying for the program that you so dearly need! (PGP for Business
Security still offers legacy RSA support).
8.4. 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, 1996 - A comprehensive and
definitive introduction to cryptography.
Handbook of Applied Cryptography by Menezes, van Oorschot & Vanstone, 1996 -
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 yy and z*m mod p to the recipient, 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 1997 posting to ietf-open-pgp mailing list
----------------------------------------------------------------------------
11. Acronyms
ADK Additional Decryption Key
AES Advanced Encryption Standard
API Application Programming Interface
BFN Balanced Fiestel Network
DES Data Encryption Standard
CA Certification Authority
CMR Corporate Message Recovery
CRHF Collision Resistant Hash Function
CSP Collision Cryptographic Service Provider
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
EC Elliptic Curve
ECM Elliptic Curve Method
ECDH Elliptic Curve Diffie-Hellman
ECDSA Elliptic Curve Digital Signature Algorithm
EDE Encrypt-Decrypt-Encrypt
EES Escrowed Encryption Standard
GAK Government Access to Keys
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
MIPS Millions of Instructions Per Second
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
RTFM Read the F*cking Manual
SHA Secure Hash Algorithm
SHS Secure Hash Standard
TTP Trusted Third Party
TWINKLE The Weizmann Institute Key Locating Engine.
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
[Adl97] L.M.Adleman, comments to NIST on proposed revision to
FIPS 186 as quoted by [Sch97d], 1997.
[AB96] R.Anderson, E.Biham "Two practical and provably secure
block ciphers BEAR and LION", Fast Software
Encryption, 1996.
[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.
[ANSI931] ANSI X9.31, "Digital Signatures using reversible
public key cryptography for the financial services
industry (rDSA)", 1998
[ANSI952] ANSI X9.52, "Triple data encryption modes of
operation", draft, 1996.
[AVPN96] R.Anderson, S.Vaudenay, B.Preneel, K.Nyberg, "The
Newton Channel", 1996.
[Bac99a] A.Back, personal communication, 13th Feb 1999.
[Bac99b] A.Back, "Commercial Data Recovery", 1999.
[Bal98] R.W.Baldwin, "Preliminary Analysis of the BSAFE 3.x
Pseudorandom Number Generators", RSA Labs Bulletin -
Number 8, Sept 1998.
[Bar99a] L.Baranyi, "Corporate use of PGP & Key
Management/recovery", Network Associates AB, Jan 1999.
[Bar99b] L.Baranyi, personal communication, 22nd Feb 1999.
[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.
[BB99] A.Back and I.Brown. "Reducing Vulnerability to Private
Key Compromise".
[Blu98] U.Blumenthal, "Re: Twofish", IETF OpenPGP mailing
list, 23rd Dec 1999.
[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.
[Bih99] E.Biham, "Comment on Selecting the Ciphers for the AES
Second Round", 1999.
[BK98] E.Biham, L.R.Knudsen, "DES, Triple-DES and AES", RSA
CryptoBytes - Volume4, Number1, Summer 1998.
[Bla99] M.Blaze, "Re: NSA key in MSFT Crypto API",
cryptography@c2.net mailing list, 3rd Sept 1999.
[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.
[Bro99] M.Brooks, "Quantum Leap in computing",Engineering and
Physical Sciences Research Council (EPSRC), 1999.
[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.
[BW94] D.Wagner, S.Bellovin, "A Programmable Plaintext
Recognizer", 1994.
[Cer99a] "Certicom responds to recent attack on RSA Security
System", Certicom, 6th May 1999.
[Cer99b] "RSA 512-bit Challenge Factored", Certicom, 22nd
August 1999.
[CJ98] F.Chabaud, A.Joux, "Differential Collisions in SHA-0",
Crypto '98 Proceedings, 1998.
[Cyb99a] Cyber-Knights Templar homepage
http://members.tripod.com/cyberkt/, 1999.
[Cyb99b] Cyber-Knights Templar, readckt.txt, as distributed
with PGP v6.0.2ckt Build 5, 1999.
[CNET97] "RSA under fire from IETF", CNet News.com Article, 3rd
Nov 1997.
[Cry99] "Microsoft, the NSA, and You", Press release,
Cryptonym, 31st Aug 1999.
[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.
[DBP99] H.Dobbertin, A.Bosselaers, B.Preneel. "The hash
function RIPEMD-160", Web page, 1999.
[Den98] D.Denning, message beginning "Eli Biham and Lars
Knudsen have exposed a...", 3rd Apr 1998.
[Dif98] W.Diffie, "Whitfield Diffie interview", Lem Bingley
interview with W.Diffie, Ziff-Davis, Nov 1998.
[DGV93] J.Daemen, R.Govaerts, J.Vandewalle, "Weak Keys for
IDEA", 1993.
[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.
[Dob95] H.Dobbertin, "RIPEMD with Two-Round Compress Function
is Not Collision-Free", Journal of Cryptology, Volume
10, Number 1, 1997.
[Dob96a] H.Dobbertin, "The Status of MD5 After a Recent
Attack", RSA CryptoBytes - Volume2, Number2, Summer
1996.
[Dob96b] H.Dobbertin, "MD5 Discussion" sci.crypt USENET
posting, 11th Jun 1996.
[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.
[Elg97] T.ElGamal, comments to NIST on proposed revision to
FIPS 186 as quoted by [Sch97d], 1997.
[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-1] "DIGITAL SIGNATURE STANDARD (DSS)", NIST Federal
Information Processing Standards Publication 186-1,
Dec 1998.
[Fro95] A.M.Froomkin, "THE METAPHOR IS THE KEY: CRYPTOGRAPHY,
THE CLIPPER CHIP, AND THE CONSTITUTION", 1995.
[GGH+98] H.Gilbert, M.Girault, P.Hoogvorst, F.Noilhan,
T.Pornin, G.Poupard, J.Stern, S.Vaudenay "Decorrelated
Fast Cipher: an AES Candidate", NIST AES Proposal,
1998
[Gla99] B.Gladman, "Implementation Experience with AES
Candidate Algorithms", as presented NIST AES
Conference II, 1999.
[Gro99] L.K.Grover, "Quantum Computing", The Sciences, July /
August 1999.
[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.
[Hit98] K.Ogawa, letter begining "We are pleased that IEEE
P1363" sent to B.Kaliski, Chair, IEEE P1363, 3rd
August 1998.
[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.
[Joh99a] D.Johnson, "RE: compare RSA and D-Hellman" sci.crypt
USENET posting, 24th Mar 1999.
[Joh99b] D.Johnson, "RE: RSA-512" sci.crypt USENET posting,
27th July 1999.
[Knu98] D.Knuth, "The Art of Computer Programming Volume 2:
Seminumerical Algorithms, 3rd Ed.", 1998.
[Knu99] L.R.Knudsen, "Some thoughts on the AES process", 15th
April 1999.
[KR97] L.R.Knudsen, V.Rijmen, "Truncated Differentials of
IDEA", 1997.
[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, "Side Channel
Cryptanalysis of Product Ciphers", 1998.
[Kob94] N.Koblitz, "Graduate Texts in Mathematics: A course in
number theory and cryptography", Springer, 1994.
[Koc98] W.Koch, "Twofish", IETF OpenPGP mailing list, 23rd Dec
1998.
[Kuh99] M.Kuhn, "RE: NSA key in MSFT Crypto API",
cryptography@c2.net mailing list, 4th Sept 1999.
[Lai91] X.Lai, "Detailed Description and a Software
Implementation of the IPES Cipher", Institute for
Signal and Information Processing, ETH-Zentrum,
Zurich, Switzerland, 1991.
[Len96] A.K.Lenstra, "Securing the net - the fruits of
incompetence", 1996.
[Ley99] P.Leyland, "RE: Asymmetric Key sizes", UK-Crypto
mailing list, 14th Feb 1999.
[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.
[Mic99] "There is no 'back door' in Windows", Press release,
Microsoft, 7th Sept 1999.
[Mir98] F.Mirza, "Block Ciphers And Cryptanalysis", Royal
Holloway University of London, 1998.
[MOV96] A.J.Menezes, P.C.van Oorschot, S.A.Vanstone "Handbook
of Applied Cryptography", CRC Press, 1996.
[Mun99] R.Munyer, personal communication, 7th Mar 1999.
[MW96] U.M.Maurer, S.Wolf, "On the Complexity of Breaking the
Diffie-Hellman Protocol", Institute of Theoretical
Computer Science, Switzerland, Apr 1996.
[NIST97] "ANNOUNCING REQUEST FOR CANDIDATE ALGORITHM
NOMINATIONS FOR THE ADVANCED ENCRYPTION STANDARD
(AES)", Federal Register Vol 62 Num 177, NIST, 12th
Sept 1997.
[NIST98] M.Smid, e-mail entitled "Re: P1363 patent update",
NIST, 25th June 1998.
[NIST99a] "Recommended Elliptic Curves For Federal Government
Use", Computer Security Resource Clearinghouse, NIST,
May 1999.
[NIST99b] "STATUS REPORT ON THE FIRST ROUND OF THE DEVELOPMENT
OF THE ADVANCED ENCRYPTION STANDARD", NIST, 14th Aug
1999.
[NIST99c] "FIPS 140-1 Cryptographic Modules Validation List",
NIST, 27th Aug 1999.
[Odl83] A.M.Odlyzko, "Discrete Logarithms in finite fields and
their cryptographic significance", 1983.
[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.
[Odl99] A.M.Odlyzko, "Discrete logarithms: The past and
future", 5th July 1999.
[Paa99] C.Paar, message beginning "The next RSA challenge,
RSA140...", as distributed on cryptography@c2.net
mailing list, 4th Feb 1999.
[PBD97] B.Preneel, A.Bosselaers, H.Dobbertin, "The
Cryptographic Hash Function RIPEMD-160", RSA
CryptoBytes - Volume2, Number2, Autumn 1997.
[Pet97] S.Peterson, "Re: Why is IDEA only 128 bits" sci.crypt
USENET posting, 18 July 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.
[Pre99] B.Preneel, "Some Observations on the 1st Round of the
AES Selection Process", 14th April 1999.
[Pri98] W.Price, "Re: [PGP-7634]: 6.0 & 4096 RSA" pgp-users
mailing list posting, 15th Oct 1998.
[Pri99a] W.Price, "Re: [PGP]: PGP and Blowfish" pgp-users
mailing list posting, 1st Feb 1999.
[Pri99b] W.Price, "Re: [PGP]: Shamir's factoring device"
pgp-users mailing list posting, 5th May 1999.
[RFC1321] R.Rivest, "The MD5 Message Digest Algorithm", RFC
1321, April 1992.
[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, 29th June 1995.
[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", RSA, 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/
[RSA99] "RSA Crypto Challenge Sets New Security Benchmark -
512-Bit Public Key Factored by International Team of
Researchers", RSA, 2th August 1999.
[Sal99] N.Salzman, "[PGP]: RSAREF", PGP-Users mailing list,
8th July 1999.
[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" sci.crypt USENET posting, 26th
Sept 1997.
[Sch97c] R.Schlafly, "Re: ElGamal - how many bits are required
for security?" sci.crypt USENET posting, 29th Apr
1997.
[Sch97d] S.Schnell, letter begining "We at RSA...", comments to
NIST on proposed revision to FIPS 186, 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" 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.
[Sch98i] B.Schneier, "Cryptographic Design Vulnerabilities"
IEEE, September 1998.
[Sch98j] C.P.Schnorr, letter entitled "RE Patents and
Trademarks for IEEE P1363 Working Group" sent to
B.Kaliski (Chair - IEEE P1363), 27th March 1998.
[Sch98k] C.P.Schnorr, "Coverage of the DSA by EP-Patent
0384475", 27th March 1998.
[Sch99a] R.Schlafly, "Re: ElGamal vs RSA" sci.crypt USENET
posting, 11th Mar 1999.
[Sch99b] B.Schneier, "Re: NSA and MS windows" sci.crypt USENET
posting, 4th Sept 1999.
[Sch99c] B.Schneier, Crypto-Gram, Counterpane, 15th Sept 1999.
[SD98] P.Livesay, letter entitled "RE Patents and Trademarks
for IEEE P1363 Working Group" sent to B.Kaliski (Chair
- IEEE P1363), Security Dynamics, 6th August 1998.
[SD99] M.K.Seif, letter entitled "RE Patents and Trademarks
for IEEE P1363 Working Group" sent to B.Kaliski (Chair
- IEEE P1363), Security Dynamics, 1st March 1999.
[SH97] B.Schneier, C.Hall "An Improved E-Mail Security
Protocol", 1997.
[Scr99] ScramDisk web site,
http://www.scramdisk.clara.net/,1999.
[Sha99] A.Shamir, "Factoring Large Numbers with the TWINKLE
Device", 1999.
[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.
[Sil96a] R.D.Silverman, "Re: "ConCryption" patent(s)" sci.crypt
USENET posting, 5th January 1996.
[Sil96b] R.D.Silverman, "Re: RSA attack : will this actually
work?" sci.crypt USENET posting, 15th January 1996.
[Sil97] R.D.Silverman, "Fast Generation of Random, Strong RSA
Primes", RSA Labs, 17th May 1997.
[Sil98] R.D.Silverman, "Re: Primes" sci.crypt USENET posting,
2nd October 1998.
[Sil99a] R.D.Silverman, "An Analysis of Shamir's Factoring
Device", 3rd May 1999.
[Sil99b] R.D.Silverman, "Re: Shamir's TWINKLE Factoring
Machine" sci.crypt USENET posting, 12th May 1999.
[SKWWHF98] B.Schneier, J.Kelsey, D.Whiting, D.Wagner, C.Hall,
N.Ferguson "Twofish:A 128-bit Block Cipher", 1998.
[Sim98] S.Simpson, "Re: To All Morons Using Greater That 3000
Bit RSA Keys!!!! READ!!!", alt.security.pgp USENET
posting, 29th November 1998.
[Sim99] S.Simpson, "[PGP]: PGP / AES / Twofish (Long)",
PGP-Users mailing list, 8th Mar 1999.
[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.
[Wag99a] D.Wagner, "Re: Labour reverses policy on Net
encryption" talk.politics.crypto USENET posting, 12th
March 1999.
[Wag99b] D.Wagner, "Re: NSA and MS windows" sci.crypt USENET
posting, 5th Sept 1999.
[WB94] D.Wagner, S.Bellovin, "A Programmable Plaintext
Recogniser", 1994.
[Web99] D.Weber, "Re: Factorization of 512-bits RSA key"
sci.crypt.research USENET posting, 8th Sept 1999.
[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.
[WIR99] "A Digital Milestone for Congress", Wired News
Article, 16th July 1999.
[YY96] A.Young, M.Yung, "The Dark Side of 'Black-Box'
Cryptography or: Should We Trust Capstone?", Crypto
'96, 1996.
[Zim96] "Interview with author of PGP (Pretty Good Privacy)",
R.D.Hoffman interview with P.R.Zimmermann, Feb 1996.
[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 20 September 1999. Copyright S.Simpson, 1999.
--------------------------------------------------------