The Protection of Your Secret Key

Editorial Note

Version 2.1 - October 2003

Ralf Senderek

PREFACE This document was first published in 1998 to encourage people to use PGP not in blind faith but with a certain degree of understanding of its basic principles and security mechanisms, and of course to increase their consciousness of possible risks which arise during the daily use of PGP. I hoped to contribute to the efforts of others to make the use of cryptography more transparent and more reliable. But since the old days of classic PGP the further development seems to me to lead into a different direction which has made the use of crypto more complex and more in-transparent leaving the user in a dangerous dependence on crypto code which almost nobody fully understands nor analyses for security, a situation, most users seem to have accepted wilfully. Something had to be done to tackle the inscrutability problem and I began to work out a concept of a pure crypto program (PCP) that uses only one single basic crypto function and will comprise of only the smallest amount of secure and highly readable code that will be understandable not only by security experts. As most of the content of the original document is also relevant for the Pure Crypto Project you can access a similar document that will explain the basic principles of the new project and that will make the security mechanisms clear with references to the open source code of PCP.

How secure is PGP ?
Can a digital signature be forged
or
can a confidential message be read by unauthorized individuals ?
Can you count on PGP's secure performance at any time ?

These are serious questions which cannot be answered in a simple way. First of all I would like to briefly summarize the essential results of my judgement of PGP's security before I try to give reasons for this judgement in detail.

Summary

Explanation

The Security of the Cryptographic Methods Used by PGP

The Cipher IDEA

The Public Key Cryptosystem RSA

The Hash Function MD5

Where Does the Session Key Come From ?
The Private Parts of PGP

Attacks on the Use of PGP

Security-relevant Actions

How to Deal with Your Passphrase

Attacks on Your Passphrase

What Is a Good Passphrase ?

Long Live the Signing Key !

The Newer the Better ? - Versions of PGP

Security Related Problems of the New Signature Format

Keep An Eye on the Threat

References to Other Sources of Information

A Final Request

Summary

When using PGP you generally pursue the following objectives:

• you intend to establish confidentiality of communication with other people, in a way that prevents other people reading the message in plain text except of the intended addressee,
• you intend to guarantee the reliability of the source of information (authenticity), in a way that prevents someone masquerading as the author of a message actually having been created by somebody else (protection of intellectual property),
• you intend to guarantee the integrity of a message, in a way that a composed message cannot be changed accidentally or deliberately.

It has been almost two years since I first published this analysis in August 1998 and more and more people are using the newest version of PGP now. But I am convinced that there is no better recommendation than to use the classic PGP version 2.6.x based on RSA-keys with a minimum length of 1024 bit to reach those objectives reliably.. Security problems have been discovered recently which relate to the complex signature format being used by new versions of PGP. One can suspect that more security related problems will emanate from the complexity of newer versions which makes the use of classic PGP even more valuable in future.

There are two possible strategies to attack the security of PGP:

• theoretical attacks

  which try to make use of the possible weakness of cryptographic methods used by PGP compromising the reliability and security of PGP fundamentally, and

• practical attacks

  which try to exploit weaknesses of the practical use of PGP. These attacks intend to compromise the passphrase to gain access to the user's secret key or try to deceive other people by distributing faked public keys.

A third strategy might be to launch an attack on the implementation of PGP. This could be done by changing the source code of PGP by altering the functionality of the cryptographic methods being used or by inserting new malicious code which makes security-related information accessible to somebody else. The compiled version of the manipulated source code results in a binary which makes it hard for the average user to tell it apart from the secure version of PGP. As this is an attempt to undermine the practical use of PGP, I will deal with this in section II below.

Theoretical attacks on PGP will be unsuccessful, as I will prove subsequently, because the use of RSA-keys of sufficient length makes it practically impossible to gain the user's secret key. The security of cryptographic methods is not merely based on near religious faith but can be justified by the history of failed attempts to break them. As theoretical security is based on the results of recent research in the field of computer science it has to be constantly reviewed in the light of new knowledge.

With the pointlessness of attacks on the cryptographic methods the attention of potential datafiends is shifting towards the weaknesses due to the daily use of the secret key. You have to consider a huge number of practical problems if you do not want to put the security of PGP at risk unintentionally. Most important is maintaining the secrecy of your passphrase which protects your secret key because maintaining this secrecy is a problem most people do underestimate dramatically.

Explanation

As all the cryptographic methods used by PGP-2.6.x (to which I will refer as "classic PGP" subsequently) do a different job I would like to give a short description of their purpose, before I will value their reliability. The asymmetric cipher RSA is used to enable a person to establish themselves as the only legitimate author or to ensure that only the intended person can read a message. Although RSA could do all of the encryption and decryption of relevant information, it is a bit slow, when long keys are used, so encryption and decryption of long texts actually is done by the symmetric cipher IDEA which has far better performance. Still RSA is used to link to a single person the ability to individually decrypt a message or to sign a document. So there is a combination of a method using a pair of keys assigned to a single person (RSA) and a method using an arbitrary session key for encryption and decryption (IDEA). A third method which is put to use by PGP is the hash function MD5. Its only purpose is to convert a very long text into a single number of 39 decimal digits which is used as a fingerprint to replace the long text in a digital signature.

The Security of the Cryptographic Methods Used by PGP

The Cipher IDEA

Can you really be sure that only the legitimate recipient of your message is able to read it in plain text?

For encryption of the text classic PGP uses IDEA, which is symmetric and works with a key of 128 bits of length, for instance

1010100101010010010010101010111101010101101100111101010000101110 1000011010110001001011110111001101111011010111111101011011000100

to encrypt a message. The same key has to be applied to the encrypted text to convert it into the original message, and any other key would leave meaningless gibberish. The message is split into blocks of 8 bytes which are converted into another 64-bit-string. The result of the conversion, in which several sequences of logical addition, multiplication and XOR-operations are applied using the bits of the key, depends on every single bit of the encryption key, so decryption will be impossible without using exactly this key. By the length of the IDEA-key it is guaranteed that there is a really huge amount of different keys (exactly 2¹²⁸ that is 340 282 366 920 938 463 463 374 607 431 768 211 456), making it practically impossible to "guess the key" by systematically testing every possible key,a method which is known as the "brute force attack".

EXCURSUS Why should it remain infeasible for a computer to test all possible IDEA-keys in the near future rather quickly ?

It remains infeasible because as a matter of principle a computer will not have the necessary efficiency. According to today's state of physical research which in future could change the spreading of information in every imaginable computer system is limited by the speed of light. Not even the results of current "experiments measuring velocities higher than the speed of light" do contradict this fact. If you assume the size of a high-performance computer system performing key tests is 0.3 mm for electronic or optical transfer of information, it can only perform 1 000 000 000 000 operations (1012) per second, otherwise it has to be smaller. Over a period of 317 years or 10 003 759 200 seconds that will sum up to 10 003 759 200 000 000 000 000 operations. This ability to perform no more than 1022 operations within 317 years is truly not sufficient for testing 1022 different IDEA-keys because every key test requires more than a single operation cycle. But even if it was possible to do a key test that fast, the large number of 1038 IDEA-keys would have been searched for no more than 0.000 000 000 000 000 029 percent. Thus a specific IDEA-key will not be found even if "lots" of those high-performance computers will work parallel to test the keys. This argument is based on empirical assumptions and therefore it can be refuted by experience. But without doubt any it is definitely wrong to suppose "efficiency of any size" for future computer systems. It is interesting to compare the ability of our proposed supercomputer to a real machine, "Deep Crack", which was invented in 1998 by EFF to show that a brute force attack on DES, the standard symmetric cipher used by banks and other commercial institutions for many years, was indeed possible. Deep Crack is a parallel computer using special hardware of 1500 Deep Crack chips and managed to test 90 billion DES-keys per second, so that any 56-bit DES-key can be found in about 5 days. This single machine today provides 9 percent of the ability we assigned to our proposed 0.3 mm supercomputer.

The Public Key Cryptosystem RSA

To ensure a reliable link between a single person and the ability to decrypt or sign a message the public key cryptosystem (RSA) is of utmost importance for PGP.

The secure performance of the public key cryptosystem guarantees:

• the confidentiality of the message, because the IDEA-key, a large arbitrary random number used for encryption should be applied by the intended recipient of the message only, and
• the authenticity of the message, it enables a person to sign a document reliably. So a message can be scrutinized whether it has been created by a particular person or not.

If a message has been encrypted with an IDEA-key (random session-key), this key has to be sent to the recipient together with the encrypted message in a way that only this person is able to recover the IDEA-key to decrypt the message. To ensure this, the IDEA-key itself will be encrypted with the addressee's public RSA-key. To gain the original message, firstly the recipient has to apply his secret key, the counterpart to his public key, which must be in the possession of the recipient only to decrypt the session-key which is needed to finally decrypt the original message. The authenticity of the message therefore is only guaranteed if the pair of keys (public key, secret key) is assigned to a certain person, even if you do not know the author personally. But the validity of a digital signature depends on the fact, that only the person itself was able to create the document by applying his or her secret key which also made him or her responsible for the contents of the document. A person's intellectual property can only be protected by proving the copyright in a document if nobody else is able to create an information that matches with this person's public key.

The RSA cryptosystem basically uses three different and very long numbers (e,d,n), even if one of those numbers actually is chosen very small due to the technical implementation of the cipher, the security of the cipher will not be reduced. Two of them, the public key e and the modulus n are used to encrypt a message. The message to be encrypted in principle is understood as a very long number itself which will be raised to the power of e, the recipient's public key, and the modulus n will then be subtracted from the result until it gets smaller than n. This remainder (mod n) is the cryptogram or the encrypted message ready to be sent to the recipient. The recipient himself applies the same procedure to the cryptogram to decrypt it. Again the encrypted message is understood as a very long number being raised to the power of d, the secret key, which miraculously yields the original message after the remainder has been computed using the modulus n. Just one single number d strictly has to be kept secret whereas the method of computation and both publicly known numbers e and n as well as the cryptogram need not to be made secret and can safely be analysed by everybody.

But the RSA cryptosystem only works well, if the three numbers fit together "in an appropriate way". Matching this condition is ensured by the process of generating a pair of keys which also gives a fine recipe for cracking the whole cryptosystem.
To generate a pair of keys you have to find two very large primes, p and q, which make up the modulus as a product (n = p*q). You can derive both interesting numbers, e and d, which form the actual pair of keys, very quickly from these two primes which are thrown away finally.
An attacker who knows the modulus n, say p*q, only needs to find out which primes the modulus is composed of, in other words he or she just has to factor the modulus, after that computing the secret key is a matter of seconds. Fortunately the problem of factoring is a job causing an awful lot of work if numbers are concerned which consist of several hundred decimal digits, so this is a practically insoluble problem .

The security of the RSA cryptosystem therefore depends on the fact, that it is practically impossible to factor the large known modulus n. So nobody can infer the two primes p and q from his or her knowledge of the publicly known modulus to gain the secret key.

It may be worth noting, that the security of RSA also depends on the absence of any "short-cut", so that there is no way to decrypt or sign a message without using the secret key. Because of the fact that the cryptogram was created by taking the message to the e-th power (modulo n) one might think that computing the e-th root of the cryptogram (modulo n) will produce the message. On one hand nobody has found a way to perform this calculation yet, given that really large numbers are involved but on the other hand it has not been proved that calculations of e-th roots modulo n is of the same complexity and requires as much effort as factoring the modulus. So there might be a short-cut not yet known to the cryptographic community that can render the use of RSA useless in future and it would be wise not only to have a close eye on the advances in factoring but also on the possibility of shortcuts like calculations of roots or even some completely different approach.

The Previous History of Factoring 70-digit numbers have been factored in 1998 on a workstation within 10 hours. 100-digit numbers will be factored on a single workstation within 1 year. 129-digit numbers : In August 1977 Martin Gardner asked the readers of Scientific American to factor 114 381 625 757 888 867 669 235 779 967 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 . Some 16 years later, in April 1994, the factors were presented by Paul Leyland (University of Oxford), Michael Graff (University of Iowa) and Derek Atkins (MIT). They had been supported by over 600 volunteers running a computer program written by K. Lenstra (Bell Labs, Morristown, New Jersey) on their workstations at night sharing the work of factoring over the internet. Later the amount of work was estimated to approximately 5000 Mips years. One Mips year is equivalent to 3.15 * 1013 operations. This experience gave rise to the "RSA Factoring Challenge" a contest which aimed at encouraging the research into number theory and the exploration of the difficulty of factoring in practice. A 155-digit number had been factored on August 22, 1999 by a group of researchers using the general number field sieve method. The work started on March 17, 1999 and kept a total of 292 computers busy for little more than 5 months. The process of sieving required some preparations in which CRAY supercomputers were involved and it took nearly 4 months time and was worth approximately 8000 Mips years of effort. This complies excellently with the prediction made in 1996. 160-digit numbers: In 1996 experts expected factoring to be possible within about 5 years using a new method of factoring known as number field sieve. Factoring of RSA-155 in 1999 was important, since it made RSA-keys insecure which had a length of 512 bit, a key length which was considered as "Low commercial grade, fast but less secure" since PGP has first been introduced in 1991. 200-digit numbers: The time for factoring was estimated at 52 000 000 years in 1998.

Conclusion	Using a minimal key length of 1024 bit corresponding to a RSA-modulus of at least 309 decimal digits, it is guaranteed that RSA can be considered safe for the near future as long as there will be no fundamental advance in the factoring of large numbers. Today lots of PGP-keys are certified with key lengths of even 2048 bit corresponding to 617 decimal digits.

Attacks on the RSA Cryptosystem

As factoring of the modulus is doomed to failure, if a sufficient large key is used, attacks which currently have become known were directed towards the implementation of the algorithm (timing attack) or they presuppose the attacker being able to submit a chosen message to the victim for signing (chosen-ciphertext-attack). Both types of attacks have been discussed in detail by W. Unruh, so I will not dig into that matter any further.

To protect yourself against these attacks you should avoid signing( a document which could contain arbitrary hidden data, for instance an unknown word-processor document containing information (on formatting) which is not to be seen in the plain text. As the chosen-ciphertext-attack is based on the fact, that an attacker is able to smuggle some skilful chosen data into the message, so that an encryption with the secret key turns out to be actually a decryption of the message or at least part of it. But even if the attacker was successful he would not get the secret key itself. The existence of the chosen-ciphertext-attack is one reason why you do not sign the whole document, but a fingerprint of it created by the one-way hash function MD5 to avoid such attacks. The signature made on this representation of the document is smaller now but also the security of digital signatures now does not depend on RSA only but on the hash function as well.

Without any doubt mathematics has made considerable progress within recent years in factoring very large numbers which has been discussed in detail by J. Buchmann in the June-issue of Scientific American 1996. Using advanced computer technology massively, completely different methods of factoring have been developed which essentially differ from conventional methods.

In 1985 W. Lenstra developed a method based on elliptic curves, which made it possible to find factors of 30 decimal digits size within three weeks using current workstation technology. This method is successful even if the number which has to be factored consists of several thousand decimal digits. If the RSA-modulus is composed of a small and a large factor, the small one could be found within an acceptable period of time. So it is essential that two sufficiently large primes of almost the same size are used for RSA-key generation to prevent fast factoring of the modulus.

A different method known as quadratic sieve requires the solution of a system of linear equations consisting of a huge number of linear equations and unknown quantities. Using this method a 120-digit RSA-number was successfully factored in 1993, although 252222 equations with a total of 245810 unknown quantities had to be solved. This work which would have taken almost 50 years using a single workstation could be run in parallel, so that it will be done within a much shorter period of time. The method of number field sieves which is based on a similar principle but works much faster than the quadratic sieve was successfully used in 1996 for the factoring of a 130-digit RSA-number.

Considering the progress of factoring over the last ten years one could expect 150-digit numbers to be factored in the near future even if today no known algorithm is able to perform this job within a reasonable amount of time. But it is still possible that a completely new algorithm will be found which would make today's secure RSA-keys absolutely worthless. So it will be essential to observe new developments in the field of factoring and to consider them carefully when evaluating the length of RSA-keys.

RSA has long been subject to a patent (No. 4,405,829) under the law of the United States of America which turned out to be an impediment to the future development of PGP and it seems to be the reason why newer versions proceeded to introduce new Diffie-Hellman/ElGamal keys. But this patent has expired in September 2000 and RSA now is in the public domain even in the US.

The Hash Function MD5

The integrity of a message or the security that the message has not been changed during transportation over networks depends on the hash function MD5 which is used to generate a digital fingerprint of the document.

What Is a Fingerprint ?

A fingerprint is a large number (MD5 uses 39 decimal digits) which fits to a message unambiguously. The fingerprint is computed by a one-way-function from the characters of the message, ensuring that changing a single bit within the message would produce a completely different result. In this way even a minimal change of the message could be detected reliably. Because of the fact that the hash function is irreversible there is no way of reconstructing the message from the fingerprint. It is practically impossible as well to design a new message (as a forgery) in a way, that it computes the same fingerprint as the original message, because there are 10³⁸ different hash values (or fingerprints) and the one which is generated with the new message is unpredictable.

Of course it is possible that some other text will accidentally produce the same hash value because even if the number of different hash values is very large, it is also limited. But such a collision could not be constructed intentionally because you have to try about 10³⁸ variations to find one. The one-way-function does not give any clue for an appropriate choice of the forgery and the possibility to get the same hash value from any two different texts is only:
0.000 000 000 000 000 000 000 000 000 000 000 000 029 percent (1/2¹²⁸).

The Birthday-Attack on MD5

How many people are required to make the possibility for two of them having their birthday on the same day reach 50 percent ? The wrong answer is: 365/2 = 182 people. Actually you only need 23 people which is far less than expected, and related to forging a digital signature, the forger can benefit from this situation considerably. If she does not intend to forge a certain existing document but rather confines herself to submit a document to the potential victim for signing and she has already found a forged document which hashes to the same MD5-fingerprint, forging someone's digital signature is possible, using such a "suitable pair of documents" (benign and malicious document). The number of pairs of documents she has to check until she will probably find one working pair is no longer 2127 (170 141 183 460 469 231 731 687 303 715 884 105 728), "but merely" 264 (18 446 744 073 709 551 616) that is 1019 pairs of documents. Finding a working pair of documents still is "bloody lotta work", but can not be considered as impossible (see my argumentation concerning the brute-force-attack on IDEA-keys). Proof With N different documents (benign and malicious all in all) there are N(N-1)/2 pairs. Given that there are K = 2128 different hash values the probability of two different documents sharing the same hash value is 1/K. To be on the safe side one must try at least half of N2 pairs of documents, for if the probability for a collision should be 50 percent, 264 pairs of documents will be sufficient. (N2 * 1/K) / 2 = 0,5 N = sqrt(K) = 264. Among those 18 446 744 073 709 551 616 different pairs one will probably be suitable for forging a digital signature. It might be necessary to check slightly more than 264 documents, because of the fact that there are half malicious and half benign documents a matching pair can be within one of the groups which does not help to make a forgery. But since there are twice as many "cross-community" pairs than "single-community" pairs, 265 documents will provide a fair chance for a forgery.

Attacks on the Hash Function MD5

Some have never used PGP because of the US-patent restrictions, others have thrown classic PGP into the dustbin because of "minor weaknesses in the MD5 hash algorithm" as quoted by RFC-2440 summarizing the advantages of a new key format. And indeed MD5 is the weakest component used in PGP. But that does not mean that classic PGP is obsolete.

First of all the birthday attack is a threat to every hash function. Although plenty of work is needed to successfully launch such an attack it would become more unlikely with more bits in the hash value (as SHA-1 is providing). On the other hand never signing any document presented by a third party without making little changes will prevent birthday attacks, regardless of the additonal 32 bits.

But there is a different problem related to MD5. An ideal hash function would spread its hash values over all possible values so that any specific value is as likely to appear as any other. If a hash function clustered at certain hash values, it would be a lot easier to make a forgery of signatures, because not all hash values have to be considered and the amount of work to find a malicious document that hashes to one of the cluster hash values would shrink accordingly There is still no indication that MD5 does not spread its hash values evenly.

Another weaker property of a hash function which is of utmost importance is its "collision-resistance", it must be practically impossible to create a different document deliberately that hashes to the same value, otherwise the hash function is compromised and can no longer be used for digital signatures. Please keep in mind that always there will be collisions for every hash function because the number of possible documents which can be an input of a hash function are digested into a fixed number of hash values, but those collisions which are inevitable cannot be created at will and therefore it is extremely unlikely but nevertheless possible that collisions can be found accidentally. Producing collisions is not a problem as long as it is an extremely unlikely event and it is unpredictable. But any chance to create a collision using a certain method would certainly be the death of the hash function.

In light of this it is important to consider the findings of Hans Dobbertin on the collision-resistance of MD5 which have been published in 1996 and which gave rise to concerns about the usefulness of MD5 for digital signatures. Before we can think about the conclusions of Dobbertin's work for PGP we have to spend a piece of brain grease to understand the basic functionality of hash functions like MD5.

The hash value is not computed from all the message bits in one step but there are several sequences of compression in which blocks of plain text are used to create the final outcome. First of all to make the hash function one-way there has to be a reduction of information during the compression. If no information was thrown away, the input message would be recoverable using the output hash value, which has to be impossible. Therefore the message bits are expanded to a certain length so that they could be split up into blocks of 512 bits. Those message blocks are used to feed a compression-function which uses those 512 bits to change an initial value (IV) of 128 bits into a different one of the same length. The result of the compression is another 128-bit number which can be used as input for the next compression using the next message block. The number which is transformed during compression is passed on to the next compression until it drops out of the process as a hash value. It is called a "chaining variable" because it represents the link between successive compressions. After having performed as many compressions as message blocks are available, the very first initial value has been transformed into the final hash value and every bit of the message has contributed to this transformation. Every computation of hash values starts with the same initial value , which has to be 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 according to the specification in RFC-1321 and the message bits which feed the compression-function will change this initial value to the final hash value that represents the message in a digital signature.

We are now heading for the tricky part of the whole process directly. To achieve the desired effect of information reduction the compression function itself applies a number of 64 complex operations (4 rounds of 16 operations each) in which all bits of the current chaining variable are mixed with a successive selection of 16 bits of the message using NOT, AND, OR and XOR binary operations. In the end all 512 message bits had their effect on all the bits of the chaining variable but only 128 bits are transferred to the next compression to be chewed further using the next message block.

The reason, why concerns about the security of MD5 came up, was that Dobbertin discovered that collisions of the compression functions can be found on a pentium PC within 10 hours. Dobbertin reported in 1996 that if the initial value can be set to 12 ac 23 75 3b 34 10 42 6f 62 b9 7c 4b a7 63 ed two slightly different messages of 512 bit will produce the same output in the compression function. The second message was almost identical except bit 14 in every two bytes of the message. To assess the implications of Dobbertin's demonstrations properly is not an easy thing to do. Finding a method to produce collisions on the compression function is a severe problem for every hash function but although RSA Laboratories noted in their Bulletin of November 1996 "On Recent Results for MD2, MD4 and MD5"

that given "the surprising speed with which techniques on MD4 were extended to MD5 we feel that it is only prudent to draw a cautious conclusion and to expect that collisions for the entire hash function might soon be found",

no collisions have been demonstrated to be feasible until today.

This might be due to the fact that to create collisions for the full MD5 would certainly require the substitution of the chaining variable with some suitable value that can be used in a way similar to Dobbertin's demonstration. Since an attacker cannot rely on the fact that any message will produce his special value ready to substitute the chaining variable, the attack would affect PGP only if it were possible to alter the initial value in PGP's source code. This can be prevented when PGP is obtained from reliable sources.

There is a second fact to be considered to estimate how much the usefulness of MD5 may be limited by Dobbertin's findings. Signatures which have already been created will remain safe from compromise even if there was a method of finding collisions because if the collision-resistance of a hashi function gets lost, cracking existent signatures will require finding a "second pre-image", that is a second message which hashes to a fixed hash value and therefore is protected by one-wayness even if collision-resistance is gone. As RSA Laboratories state "it seems that current techniques used to cryptanalyse MD5 do not offer any advantage in finding a second pre-image".

In the end trust is important. The assessment that MD5 has almost been broken is nonsense, but putting too much faith into the fact that as nobody can demonstrate collisions today, MD5 will survive those attempts to crack for a long time may be imprudent. There is no need to turn away from MD5 but there is also no need to stick to MD5 unless serious doubts about the reliability of the alternatives are justified. So in this situation it depends upon how much trust you put into the alternatives to replace classic PGP because of the problems concerned with MD5. Being cautious and claiming high demands on cryptographic methods can be wise, but regarding classic PGP as deprecated and using SHA-fueled PGP on insecure Windows boxes instead is certainly plain folly.

Where Does the Session Key Come From?
The Private Parts of PGP

There is another piece of software in PGP that has an effect on the security and reliability of the whole system and which usually does not cause a sensation because of all parts of PGP it is the most unsexy one, but it is the source of all the secrecy in PGP and therefore its most private part, the Pseudo Random Number Generator , or PRNG for short. As we saw a message is encrypted with a session key of 128 bit length using IDEA. To enable the recipient to unscramble the cryptogram the session key is sent together with the cryptogram but encrypted with the recipient's public key. The privacy of the message relies on the fact that an eavesdropper is unable to calculate the recipient's secret key from his public key and that guessing the session key is equivalent to a brute force attack, that is testing a very large portion of the 10³⁹ possible session keys. Imagine, that the PRNG is not sufficiently random and may produce only a tiny fraction of all those 128-bit strings, say some few hundred billion, then brute force is not necessary to get the session key and read the message in plain text. Worse, if such a would-be PRNG is used to create RSA-keys factoring can be much easier than you expect.

Why is it so difficult to pick a truly random number? A computer is a very deterministic thing, even if sometimes we do not have reason to belief this because sometimes it tends to behave like a queer fellow. Anyway, Pseudo Random Number Generators are called pseudo because they do not pick numbers randomly, but following some procedure that relies on random data as input and then creates a sequence of outputs that look pretty random to a human although the sequence would repeat itself after a long time and therefore is not truly random. The output of a PRNG can be analysed statistically and gives pretty good results in this respect but the sequence of successive numbers is completely dependent on the initial state of the generator. So it is important to hide the information about the state of the generator and to set up the generator with real random data when security-critical processes are initiated that use random numbers. Note that there must be a source of randomness which is fed into the generator from outside that cannot be created by the software itself.

The most important source of randomness is the user's input when he first creates a file called "randseed.bin" usually in his home directory. A latency timer is used to measure the time between two successive key strokes on the user's keyboard, which establishes the first content of this file. The more random the keystrokes the better the original pool data, it is as simple as that. Every time a session key is needed for encryption some 24 bytes of data from the pool feed another generator, the ANSI X9.17, which spits out a random number after having been "pre-washed" with a hash of the plain text to be encrypted. To ensure that the random data pool gets more and more random, the pool is "washed" twice, before and after use. Washing essentially can be considered as a process of encryption with IDEA in which the hash of the plain text is used as a key, so more user-input is fed into the pool. Details of this procedure can be found in W. Unruhs analysis of PGP's security.

Do we really need all this laundry, you may ask. In 1998 four security experts, J. Kelsey, B. Schneier, D. Wagner and C. Hall examined the strength of four PRNGs which are used in real systems and published their results in a paper " Cryptanalytic Attacks on Pseudorandom Number Generators". One of those real-world PRNGs was the X9.17 generator and the authors show that the main weakness of this generator may be caused by a state compromise from which the generator would never recover fully. The authors do not see any weakness concerning a direct attack on the generator without being able to control the input of the generator which in fact is taken from PGP's random pool. As long as this random data cannot be frozen there is no way for input-based attacks. But once the internal IDEA-key is compromised and the attacker learns the internal state of the generator it will never recover from this compromise even if there are lots of real random numbers fed into the X9.17 subsequently. The obvious recommendation given by the authors to minimize the effect of a possible state compromise is:

"For systems that use X9.17, the most obvious way to resist this class of attack is to occasionally use the current X9.17 state to generate a whole new X9.17 state, including a new K [the IDEA-key, R.S.] and a new starting seed[i]." [PGP's random pool data]

PGP actually translates "occasionally" to "always". Since the generator is washed with the hash of the plain text, its state will depend on the message the user intends to encrypt. While creating the IDEA-encryption key (or session key), more bytes are read into the generator from the pool which will be encrypted (washed) before they are used in the generator to produce pseudo-random numbers. A fraction of these create the session key and the rest is fed back into the pool after having been washed again, so the pool itself will be different next time a session key needs to be created.

You may have noticed that PGP asks for a lot of random keystrokes when a RSA key pair is to be created because public/secret key generation requires selecting two very large primes p and q. Since large prime numbers cannot be generated they are made up with random bits and are tested whether they are composed or prime subsequently applying the fermat test. PGP considers such a guessed number prime if it passes the fermat test with four different bases. To create secure large primes it is important to have enough truly random data in the pool.

It is worth noting that in May 2000 Germano Caronni found out that a certain version of PGP-5.0i for LINUX and OpenBSD used a source of randomness (the special file /dev/random) which produced too few randomness while keys are generated without user interaction. This key generation problem was reported and stressed the fact that intense random user interaction is needed during key generation to prevent weak keys. We can see that no security is obtained without effort and a consciousness of the underlying processes.

RESULT	Using sufficient long keys an attack on cryptographic methods used by PGP is practically pointless. This "theoretical security" has to be evaluated with respect to current results of cryptographic research.

Practical Attacks on PGP

Because of the fact that attacks on the cryptographic methods used by PGP are practically impossible the attention of potential attackers is shifted towards the practical use of PGP.

Security-relevant Actions

Practical use of PGP sometimes requires the use of the secret key to sign a document or to decrypt a confidential message. There are dangers lying in wait when using the secret key (security-relevant action) that could make the cryptographic methods worthless all at once, so you have to be extremely cautious in using your secret key. It is essential to develop a consciousness of the possible vulnerabilities of the security of PGP, which is usually extremely high.

Fortunately most of the everyday tasks can be carried out without any difficulties, because only public keys are used. If you want to check the signatures of your emails you have received you only have to apply the public key of the sender. Even if you send confidential information to other people, you have to encrypt them using the public key of the recipient.

But adding such a public key of an unknown person to your keyring, i.e to the file which collects all the public keys is definitely a security-relevant action, because by adding the new public key you definitely recognize that the available public key you often have received from non-reliable sources (i.e. key-servers) is actually identical with the public key as it was initially generated by that person itself. This could be a problem if you don't know that person or if you can only communicate with him or her using an unreliable channel like the internet which frequently happens.

Of course you could add a new public key to your keyring as "untrusted" without applying your secret key but as soon as you want to accept a public key as reliable you have to certify it yourself using the secret key for signing the key.

So how can you judge the reliability of an unknown public key? PGP offers two different ways to solve that problem. You can obtain the FINGERPRINT of the public key through a direct and reliable contact with that person comparing this first hand information with the fingerprint of the public key you have received from unreliable sources. If that confirms the authenticity of the public key you can certify this new key yourself signing the new key with your secret key while adding it to your keyring.

But if the new public key has already been certified by a certification authority you trust adding this key to your keyring does not require your signature of the key. However, the premise would be that you have signed the public key of the certification authority and you have consented to certify new public keys by the certification authority, which is a security-relevant action itself.

But even if you add a non-certified key to your keyring you only have to confirm the authenticity of the new key once by signing it. During your everyday use of the different people's public key your own secret key will never be used. So security-relevant actions do reduce to signing own documents (as the "crowning finish" of your creative work) and to decrypting messages meant only for your eyes.

Please pay attention to the fact, that whenever such a security-relevant action is carried out, you always have to enter your passphrase!

For if you aren't requested to enter your passphrase then your passphrase is stored somewhere or has not been set anyway, which makes its compromise drastically easier or there is something foul with your PGP working environment, especially with your binary you are using. As soon as that happens to you once, you should change your passphrase which makes your secret key be encrypted freshly and you should scan the security of your working environment thoroughly (maybe with the help of others). With multi-user systems there is the danger of someone getting access to the superuser's password or tampering with the working environment by making use of weaknesses of certain system programs in gaining root permission. So it is usually advisable to inform your system administrator if you observe such a "queer behaviour" of your environment.

If somebody got to know your passphrase he or she just would need to get your secret key (ring) to be able to sign in your name or read your private data. Practically you could try to prevent someone copying your secret key ring by using file-permissions provided by the operating system. Although with a suitable networking environment, one could restrict the access to sensible data, it can not be guaranteed that the encrypted secret key ring will not fall into the hands of other people, i.e as a result of burglary. Of course during normal operation there is a fundamental difference between a responsibly administered multi-user system and an utterly unprotected desktop PC. But because of the fact, that in the worst case the theft of your secret key ring is to be expected, the quality of your passphrase is essential which protects your secret key from being (mis)used by others.

How to Deal with Your Passphrase

Even if you have found a sophisticated passphrase (better two of them, so you can change it when necessary) you should avoid making the following mistakes in order to get your secret key secure for eternity.

• Don't ever write your passphrase down (in plain text)! Don't even think about doing so.

• Don't use your passphrase for something else (i.e as login-password). Even similarities would make drawing conclusions much easier, if you just weren't cautious some time.

• Don't communicate your passphrase to other people, come hell or high water! You would destroy the link between your pair of keys and a single individual, that is you. Nobody, except you, has the right to use your secret key, so you have to resist any attempt to "squeeze the passphrase out of you". You should consider attempts of somebody to obtain the passphrase of other people not as a peccadillo but as a perfidious attack on privacy in computer networks. Such attempts of "social engineering" destroy trust in the reliability of cryptographic methods and have to be seen as social-harmful behaviour, especially as the right of an individual to use a private key is threatened by the exploitation of relationships of dependency (i.e in a company). Privacy is a right, not a generous concession.

• Take care that you are not observed when entering your passphrase. Everyone who is aware of the value of cryptography will avoid "peeping at your fingers". You can easily recognize people without any consciousness of the problem or with suspicious intention by their behaviour in those situations. You do not have to defend your right "to enter your passphrase unobserved", claim it as a matter of course.

• Don't ever forget your passphrase. If you don't remember your passphrase you will be in exactly the same situation as someone who has his eyes on your passphrase but in contrast to him you cannot catch yourself entering your passphrase. This situation is desperate and without any help. But it is rather unlikely that you will forget your passphrase if you use PGP regularly.

• Please generate a "key-revocation-certificate" which is a document that declares your public key null and void and has been signed by yourself. The revocation certificate could be distributed like your public key (via key-server) if the worst case has happened and you have to or want to withdraw your public key. But be sure to keep your revocation certificate safe.

• Please make a backup of your secret keyring and lock it away in a safe place.

Attacks on Your Passphrase

Vulnerabilities of the Operating System

If you received a confidential message it will usually be stored on a disk in plain text after decryption with your secret key. After deleting this file containing sensitive data it has surely disappeared from the file system but it is still possible to recover the physically stored data, because deleting a file only cancels the link between the destroyed file name and the original blocks of data on the medium, which are still existent. To actually destroy the confidential data the file has to be overwritten with some other data in its full length before it is deleted, preferably a dozen times. PGP has an option -w (wipe) for this purpose which overwrites the contents of an existing plain text file with random data at least once. Special "file wiping utilities" do that job by overwriting the file several times.

Some text editors create temporary files on their own, which hold a copy of the text during the process of editing. After finishing those "tempfiles" will usually only be deleted not "wiped", leaving sensitive data undestroyed on the medium.

Moreover your passphrase is at risk to appear on a storage medium, if your operating system is extending its memory by "swapping" . While UNIX does separate this swap-space from the rest of the file system, so that someone has to gain root access to analyse it, MS-WINDOWS directly stores parts of the memory to disk. Therefore with some luck everyone who has access to your hard disk could find your passphrase or parts of confidential information in the swapfile in plain text. Especially in a networking environment a swapfile is a serious danger to your passphrase. It definitely would be the least to avoid swapping while using WINDOWS or at least to wipe the swapfile before turning off your computer, because deleting does not destroy the contents of your swapfile.

UNIX restricts the ability to examine any blocks of data to the person of the system administrator. In principle he or she also has access to the memory (/dev/kmem) and can search for your passphrase in the memory during the execution of your PGP-process. Do not hesitate to speak to your system administrator about this problem. A responsible system administrator will put himself to a lot of trouble to prevent others from using the superuser's password and he or she will be able to assure you that your passphrase will not be at risk by root access. At this point the security of your secret key depends on the ethos and proficiency of another person who is responsible for the UNIX system. At least since Bruce Schneier's epiphany we begin to understand that security is a process and not a product. Therefore do not bother to ask your system administrator about monitoring, intrusion detection and risk management to make sure that the integrity of your working environment is carefully observed.

Peter Gutmann has examined the reliability of safe destruction of data stored on magnetic disks and solid-state memory and found surprisingly that data seem to be more resistant to destruction on these media than expected. In case your computer falls into the hands of an attacker procedures including "Magnetic Force Microscopy" can be applied to retain stored data which had even been overwritten several times. There are different reasons for the persistence of formerly stored data on magnetic media ranging from the inability of writing data to exactly the same track so that old data remains at the edges to a lack of overwrite performance which leaves progressively diminishing images of older written data in present patterns on the disk. Based on an analysis of the way raw data is written to disks Gutmann proposes a method of truly erasing data which uses a sequence of 35 consecutive write circles to get rid of old data reliably.

He also found out that data present in RAM is recoverable after power is switched off depending on the time the data is held in memory unchanged. Interestingly not only static RAM could "remember" last stored states over days but also dynamic RAM can hold such information because the charge of cells is retained while the electric field stresses the thin oxide that makes up storage capacitor dielectric and thus changes its electric properties remaining in the cells. This effect is not exploitable unless the data remains constant for several minutes but after that the information remains for days depending on temperature once it has reached a critical threshold. Unfortunately overwriting RAM does not have the same effect as with magnetic media, rather the data used for erasure should be applied unchanged for as long as possible and should not be changed as often as possible to be effective. As a precaution Gutmann proposes that security relevant data like passphrases and secret keys should be held in specially designed RAM which has to flip constantly to prevent "burning in" of secret information at all.

Snooping Attacks

Spending large technical effort, different possibilities could be realized which all can lead to a revelation of your passphrase but which also have to be considered as "rather unlikely" with respect to the normal situation of use. It is possible to capture all your keyboard input using hidden video surveillance or a specially prepared keyboard, which emits a different radio signal with every key press, to compromise the whole cryptosystem all at once. Recently methods have been disclosed to reconstruct information from the electromagnetic radiation of computing equipment (van Eck Radiation). Whether or not this is a realistic scenario is hard to say but the necessary technical effort is not too big to rule out such a danger basically. In December 2000 it was reported that FBI agents installed a bugging device on a suspect's business computer to find out the password the suspect was using.

But without any big effort "key-logging utilities" or "key-press snooping tools" can be installed in operating systems without access control (DOS/WINDOWS) which will detect every key pressed, storing them somewhere or sending them over the network. Those key-loggers replace some parts of the operating system, which control the keyboard input by tampered code thus leading to an alteration of the operating system. With computers running DOS or WINDOWS everybody will be able to install key-loggers without any difficulties, if he or she has access to your hard disk. But such an alteration could be done by a boot virus as well or based on a network attack with Back Orifice giving an adversary control over your machine using the network connection.

To get an efficient protection against these alterations of the operating system it is necessary to check the integrity of the corresponding routines of the operating system regularly before you use PGP. This could be done by generating MD5-fingerprints of relevant parts of the operating system comparing them with the actual software-fingerprints (may be automatically) to ensure a change of the operating system not to remain undetected. Tripwire can be of help in those situations.

With UNIX "key-logging" requires access to the corresponding device files (terminals) which normally is not permitted to other people. An alteration of the input routines of the operating system is possible only with root access. But the X Window System (X11R6) which is the graphical user interface for UNIX features a conceptual design error, which could be exploited for "key-press-snooping" without root access. You will find comprehensive information about this in Roger Bråthen's Crash Course in X Windows Security. You should always avoid entering your passphrase during a X Window session and you should switch to the character based console if possible. But if you cannot do so, you can restrict access to your X server to your localhost using the UNIX command "xhost -", so you can only be threatened by users who have already logged into your local computer.

Convenience and "Brand-new Features"

On the one hand working in a network environment is quite profitable but on the other hand it also bears some severe risks concerning the use of PGP. In TCP/IP-networks "packet sniffers" are a real threat. Dumping any packet of data transmitted over the network can be made ineffective with the use of cryptographic methods. By using the Secure Shell (SSH) as a replacement for rlogin one can perform authentication with a remote host using RSA and subsequently all data will be transferred over the network conventionally encrypted (i.e. with 3DES or IDEA) making packet sniffers completely useless. This encrypted connection to a remote host only requires very small additional effort; for every host participating and for every user a pair of RSA-keys has to be generated and exchanged between the systems reliably. So an arbitrary connection to any remote host (as with telnet or rlogin) would not be possible without exchanging trusted RSA-keys. This emphasizes the fact, that a gain of security can only be reached at the expense of practical convenience. But using the secure shell allows really long and secure passwords to protect the secret key.

How Secure is Your Source for PGP ?

As the source code of PGP is publicly known, it is possible that a faked version of PGP will be distributed as the legitimate original, which might store the passphrase or send it over the internet via email. Convenience normally would urge you to use the pre-compiled version of PGP which is included in your software distribution being configured "rough and ready". But you should bother to obtain a version of PGP which has been compiled using scrutinized source code. Stale Schumacher (Key-ID: CCEF447D) has signed the legitimate source code of PGP-2.6.3i, so you can check the integrity of the software, if you have got his public key (or fingerprint) from a reliable source. Please ask your system administrator or your certification authority for a scrutinized version of PGP or build one yourself. In any case you should generate MD5-fingerprints of your reliable PGP-binary and store them in a safe place, so you can verify the integrity of the binary you are currently using with this fingerprint from time to time.

Some PGP-shells have been developed for WINDOWS which comfortably save users the trouble of using PGP with its command line options. Instead the processes of decryption, signing and key management have been hidden behind some "fancy buttons and check boxes". Clearly there is a danger that entering your passphrase within a shell will cause undesirable side effects, especially if the PGP-shell is distributed as pure binary without a publication of the source code.

Following the support of JAVA, JAVA-Script and ACTIVE-X by the new generation of web browsers a severe lack of security has become known, because unauthorized access to private local data over the network has been permitted due to the implementation of these new features. The concerted action of the software industry to deliver "brand-new features" in a premature and imperfect condition will certainly damage the security of the browsers in their further development - particularly, if you take into account the rivalry between Microsoft and Netscape.
The demand for comfort and user-friendliness lots of users call for, causes suspicion of an increase of security-relevant attacks using applets and "hostile webpages" in future. Even today some websites intend to cause destructive effects based on JAVA-applets. So in future those pages could also be dedicated to the purpose of hidden information gathering. You can face these dangers best, if you do not use your system for PGP and as a platform for testing web browsers simultaneously.

Usually a firewall is useful to protect against intruders, if configured correctly, which has become much of an art today. Some products that offer personal firewalls have been found to leak information out into the internet, a problem called "internal extrusion". To check the ability of personal firewalls against such leakages Steve Gibson developed a free utility called LeakTest which tries to pass out through the firewall. Unfortunately most of the current products today fail the leak test.
But even if firewalls work reliably they do not block faked DNS-requests which can be used to send confidential information to the nameserver of a hostile domain, as was reported by Richard Cox in a prominent security mailinglist.

What Is a Good Passphrase ?

In the following section I will discuss some criteria, you might consider while choosing your passphrase if you do not want to put the security of your secret key at risk.

How Long Should a Passphrase Be ?

The passphrase protects your secret key from being (mis)used by other individuals. If you like having as much security as IDEA offers, a 128-bit-string of 0's and 1's as mentioned earlier would be an appropriate solution. If you replace any 4 bits by a hexadecimal digit, this solution will force you to remember i.e. the passphrase "A9 52 4A AF 55 B3 D4 2E 86 B1 2F 73 7B 5F D6 C4" , which probably is expecting to much of the digital Joe Blow.

Because of the fact that you should never forget your passphrase, otherwise your secret key is useless and the protected data is lost, solutions have to be found that will work safely. At this point two different strategies can be offered to guarantee the memorability ot the passphrase, both leading to a loss of security.

• You can reduce the number of characters until you can remember the passphrase
• or instead of using random characters you can try to introduce "meaning" into your passphrase.

Both strategies do raise the question what length will be required to make sure that a passphrase is still secure. My argument concerning the efficiency of a future computer system has shown, that it will be sufficient to ensure, that the work for "systematic guessing" the passphrase will reach about 10²² operations. If you choose your passphrase in a way that in principle there are 10²² possible passphrases, you certainly are on the safe side. To cause this amount of work 72 bits or 9 Bytes of truly random data will be sufficient, because this will leave 2⁷² or 4,7 * 10²¹ variations.

Strategy 1 : Random Character Strings

A shorter, but still secure passphrase would be "4C 72 1A FD 94 5B BA 39 E6". If you think, you can remember such a thing this solution is strongly recommended.

The number of characters could be reduced further by using more than those 16 hexadecimal characters (0-9A-F). Using not only all lower and upper case letters but also every special character you can enter through the keyboard resulting in some 70 different symbols, 12 of those randomly chosen characters will be sufficient to cause the required work (70¹² = 1,4 * 10²²).
Then may be your passphrase would be e8ZWr!ySFt?m.

By using the <SHIFT>, <CTRL> and <ALT>-keys and the combination <CTRL><ALT> as well you can easily increase the number of different characters to 160, which results in an unbeatable secure 10-character passphrase like
G<ALT>)a<CTRL>#Hs<CTRL><ALT>e.3<ALT>wY .

So the gain you have achieved using the meta keys is rather modest and you simply cannot construct a secure passphrase with less than 10 characters!

Strategy 2 : "Meaningful" Character Strings

If you try to fill your passphrase with meaning, you will rule out a lot of "meaningless" combinations from the amount of passphrases to test and therefore you either accept a considerable extension of your passphrase or a drastic deterioration.

A dictionary contains maybe 60000 different items, so an arbitrary choice of five different items would again produce plenty of combinations (60000⁵ = 7,7 * 10²³). But your secure passphrase salmagundi_latrine_warning_gowk_marathon now has a length of 36 characters, a price you have to pay for the fact, that you only need to remember the order of the five different words, which all have meaning now.

One single word chosen from a dictionary is clearly useless as a passphrase. R. T. Williams describes the attempt of testing PGP-passphrases using low-tech computer technology (PC-486 and PGP-2.6.2). Performing at least two key tests per second one easily covers 172800 words a day, so every dictionary will be searched exhaustively within a short period of time.

If you still want to use a single word as a passphrase, it is advisable to choose a random-looking word, which has no meaning for anyone except you. Twcae,pwcab. would be no poor candidate for my passphrase, if nobody could get the idea that it reflects the quotation of I. Kant "Thoughts without content are empty, perceptions without concepts are blind". But those who know that I am busy with philosophy professionally might get this idea, so this passphrase is completely useless for me. But if you can invent such an "abbreviation", nobody who knows you would possibly assume, this would be a good passphrase given an appropriate length and spending plenty of <CTRL><ALT>.

Useless Passphrases

Certainly useless passphrases are those, whose systematic testing would require far less than 10²² key tests. It is known that not only the NSA (National Security Agency) is able to crack keys of 40-bit (5 byte) length without any problems, corresponding to a random character string of 7 characters (out of 70), because this only results in 10¹² different possibilities. In 1997 Bruce Schneier developed a screen saver that cracked 40 bit S/MIME-keys by brute force to show the insecurity of short keys.

RESULT

The PROTECTION of your PASSPHRASE is the crucial factor which determines the security of PGP. The trouble you are taking to choose a good passphrase and to make your working environment secure but also your consciousness of the various possibilities of practical attacks on the use of PGP builds the basis of your security and the basis of the trust of others in the value of cryptographic applications like PGP as well.

Long Live the Signing Key !

Classic PGP-keys can be used to sign documents and to encrypt confidential messages. Even though it has become common practice to use one single key for both signing and encryption there is a pile of good reasons not to use one key for both purposes. For an attacker - or with a bit of bad luck your government - it makes a remarkable difference whether someone intends to forge your signature or tries to access the plain text of your encrypted communication.

A key used to create signatures usually has a very long lifetime, because trusted key distribution is an awful expensive procedure and in case of a compromise of your secret key the secure revocation of your signing key takes equal pain. Moreover you would probably use your signing key more frequently so that spending an extra effort to protect your secret key would be only prudent. On the other hand keys which protect confidential communication should have a short lifetime to minimize the damage caused by a key compromise. The change of even revocation of a short-life encryption key would be a pretty normal thing whereas you would probably go through much trouble to avoid the revocation of your long-life signing key. Governments have often toyed with the idea of demanding the disclosure of private encryption keys used to protect confidential communication but have confined themselves to include private signing keys in this demand up to now. Using two different keys for signing and encryption is terribly advisable in the light of those intentions of governments to establish the seizure of private keys as a natural means of law enforcement which are currently developing in different countries all around the globe and especially in the European Union.

You can easily specify the purpose of your long-life key by adding something like "high security signing key, not for encryption" to your PGP-user-ID and use this key to sign any short lifetime "encryption key [expires: date]" which can be published on a website and can be replaced even monthly without revocation so that everyone who has got your signing key reliably can obtain your current encryption key and check its validity before starting a confidential conversation. There is no need for a wide distribution of your encryption keys using key servers because only your signing key has to be certified properly to ensure the authenticity of all your other keys which are to be replaced from time to time. This will imply that you use a different key-ring for the short lifetime keys in order to separate them from the long-term ones. To complete this picture there is also a need for a safe data haven which is immune against demands for cryptographic keys.

The Newer the Better ? - Versions of PGP

When PGP-5.0 was introduced in 1997 it promised to get rid of all the weak points of PGP-2.6.x and to clear the way for a massive use of strong cryptography, particularly on modern desktop computers with a graphical user interface. Although I think, that using PGP on the command line does not expect too much of the responsible, average user, I would surely welcome improvements of the handling of PGP and its integration in standard applications, as long as the user is always understanding what he is doing and what consequences will be caused. However important such questions of user-friendliness will be for the further spreading of PGP, I would like to concentrate on the valuation of the security of the new features of PGP-5.x, because some of those "improvements" which have been carried out in a view of the adaptation of PGP to the requirements of modern information technology turn out as extremely questionable, if not incompatible with the original objective of the protection of privacy in computer networks.

Fortunately PGP-5.x is backward-compatible, so RSA-keys which have been generated with PGP-2.6.x are still valid and all signed documents can be checked and all encrypted messages can be decrypted without limitation. All three methods RSA, IDEA and MD5 can still be used in PGP-5.x. Additionally PGP-5.x puts a new type of key at the user's disposal (actually two keys, one for signing (DSS) and one for encryption (DH/ElGamal)), which is supposed to make the latest advances in cryptography available to the user. In the new version PGP-5.x the Secure Hash Algorithm (SHA-1) with 160 bits replaces the old 128-bit hash function MD5. Digital signatures will be generated using the Digital Signature Algorithm (DSA) with a maximum "key-length" of 1024 bit instead of the RSA cryptosystem. And asymmetric encryption, which was previously done by RSA, will be performed by a variation of the ElGamal public key algorithm (Diffie/Hellman variation) which uses keys of maximal 4096 bits for encryption. For symmetric encryption in addition to IDEA PGP-5.x offers a variety of algorithms including CAST (128 bit) and triple-DES (168 bit).

This raises the question how high the security of the new methods especially DSA and ElGamal/Diffie-Hellman has to be valued compared to MD5 and RSA. Which problem is to be solved by a potential datafiend - analogous to the problem of factoring with RSA - to gain the secret key ?

Both the Digital Signature Algorithm and the ElGamal algorithm use the following relation between the secret key X and the public key Y :

Y = G^X mod P
Using the base G (generator) and the large prime P to calculate the remainder will guarantee, that it is impossible to draw conclusions from the public key Y to gain the secret key X. So a potential datafiend has to calculate a table (of logs) which shows the appropriate public key Y (mod P) for a large number of secret keys X, so that one can look up the secret key for a given public key.

The DSS (Digital Signature Standard) restricts the size of the prime P to 1024 bits, which appears as a minor restriction compared to the RSA algorithm which commonly uses 1024-2048 bits. But it is more important for the datafiend, that this standard restricts the secret key to 160 bits as well. Therefore it is enough to check a relevant part of the numbers between 0 and 2¹⁶⁰ to find the secret key, while the size of the prime does only increase the time for calculation of one single test but does not increase the amount of possible secret keys.

The range of numbers for secret keys is still very large, but it would be a misunderstanding to confuse the size of the secret key (which is always 160 bit) with the size of the DSS-key (that is the length of the used prime). Additionally the range of possible secret keys might be restricted more, if an analysis of the random number generator, which produces the secret keys, will give further hints. For an overview of necessary key lengths based on the research of Lenstra and Verheul their comparison of symmetric and asymmetric ciphers can be very informative.

The New Key Format

With the introduction of the new DSS/DH-keys the format in which those keys were stored has also been changed. This change becomes visible in the new key file names of the key-rings which are no longer named pubring.pgp and secring.pgp but pubring.pkr and secring.skr lately. In the commercial version PGP-5.5 this new file format contains a piece of data, the ARR (Additional Recipient Record), which brings along drastic changes . The ARR is designated for storing a second key (the ADK) in the user's key certificate, the message recovery key of the company or Additional Decryption Key . In this way a company will have access to the content of the message, because while using the user's public key certificate the message will be encrypted a second time with the message recovery key. During the process of key generation this message recovery key will be linked firmly to the user's public key, so always both keys, the user's public key and the message recovery key will be used if someone is sending a confidential message. For this reason any time a public key is retrieved from a key server, the corresponding message recovery key will be sent in addition to the addressee's public key. As far as I know there is still no reliable mechanism which will prevent a user's public key being linked with another faked message recovery key without the user's consent or knowledge.

It would be wrong to misunderstand this mechanism as a "comfortable replacement" for encryption to groups, which already exists. Whereas using the facility to send a confidential message to different individuals simultaneously is based on a voluntary decision of the sender, the inscription of a second key into the user's key certificate will surely be equivalent to abolishing his privacy in computer networks. As much as this mechanism would be in accordance with the organisational needs of trade and industry, this compulsory deposition of a copy of every confidential message at a central supervisory authority does clearly contradict an efficient protection of the user's privacy and personality - and most important, it contradicts the original intention of the project Pretty Good Privacy.

The obvious dangers which raise from the abolition of the user's self-responsibility by this forced mechanism of supervision will come in effect if the new key format is introduced under the cloak of "cryptographic innovation" and will then be sanctioned as a legal format within the scope of legal endeavours towards regulation of cryptography. The legitimate interest in message recovery could be satisfied by "encryption to groups" on the basis of self-responsibility of the user as well, without forcing every possible sender of a confidential message to deposit a readable copy of the message at a central authority by using the supervision-key. If the responsibility for the sensitive use of cryptographic methods shall be exercised by self-responsible individuals in future, it is essential not only to use the old key format without ADKs (PGP-2.6.x) but also to warn against the threatening dangers of those new features to prevent their creeping adoption without open discussion.

Security Related Problems of the New Signature Format

Given that the new cryptographic algorithms including AES which will speedily find its way into the very next versions of PGP and GnuPG will be subject to further research and examination, the security of these algorithms will not be a major concern. But what gives rise to serious suspicion is the new open signature format that bears a number of possible and actual security risks which have not been examined in full yet.

In my study KEY-EXPERIMENTS - How PGP Deals With Manipulated Keys - I presented the results of experimental research on the ADK-feature of PGP and warned in a note to the public that the ADK-problem creates a long living risk which would not at all be eliminated with the bug-fixes that followed my publication. The experiments show that Network Associated Inc. not only had implanted the ADK in the new signatures without any checking whether it is inside or outside the hashed part of the self-signature, so that manipulated public keys encrypted messages to a faked ADK and made every new Diffie-Hellman key a target for manipulation. It turned out that a key manipulation would not even be detected and that after converting old RSA-keys to the new format even those were affected and could be stuffed with ADKs long after the owner had self-signed them.

As expected there were lots of attempts to play down the importance of the problem, some descriptions of the conditions under which the ADK-problem arises are still incorrect (CA-2000-18: PGP May Encrypt Data With Unauthorized ADKs, section Impact), but the security relevant risk of the ADK essentially was, that no user was able to avoid the problem by using "fixed" versions of PGP. Unfortunately the problem would not go away until every possible user of PGP either used a version immune to ADKs or was very careful with every public key and would examine public keys for subsequent manipulations for which official PGP was simply no help. As Ross Anderson wrote:

The problem won't go away until all vulnerable versions of PGP are retired, since it's the sender who is responsible for encrypting to the ADKs, not the recipient.

During the process of bug-fixing Philip Zimmermann reported that there was a similar problem related to the designated revoker feature which would allow to add unauthorized revocation key packets to a key and which has been fixed. One needs not be a prophet to suspect that there are more undiscovered security relevant problems lurking in the new signature format. Not only the number of 21 different sub-packets which are allowed in newer signatures show that we should not be surprised when other packets show security relevant cracks but there are very few specifications which require that those sub-packets have to be in the hashed part of the signature at all. Circumstances might be conceivable in which sub-packets may have consequences when they reappear in the unhashed part of the signature. This raises the question if an unhashed part inside the signature is tolerable at all because it violates the usual picture of a signature and bears a potentially risky reservoir of data which can be used to blow up a signature without the owner's consent. It seems to me that having unhashed packets in signatures is bloody nonsense. And on the other hand the vast majority of users simply does not even know which of the 21 sub-packets are included in their self-signature they are responsible for.

There are no security relevant risks in the new signature format? The final word on that should be spoken not before someone has examined this experimentally. Because in theory there is no difference between theory and practice, but in practice there is.

Keep An Eye on the Threat

In the struggle of improving PGP with new features Network Associates Inc. have got on the wrong track. In their response to the ADK-Problem they have made it clear that there will not be an ADK-free version because it won't sell. Many French users of OpenPGP have openly regretted the way PGP has adopted to the demands of business and have required a rebirth as "a thinned version of PGP, without superfluous gadget like the SDA or special keys (ADK, share keys, reconstructed keys, special RSA keys, etc), by respecting security minimal requirements". Although seeing PGP drifting away from its original objectives is a sad thing, the real threat to our digital life comes from a very different direction and it approaches directly without any disguise.

The British Government has pushed the Regulations of Investigative Powers Act (RIPA) through legislation which provides for orders to disclose private encryption keys and threatens everyone served with those orders with two or even five years of jail who fails to comply with the demands. While some are still figuring out how far the powers provided by this act will reach - the conditions under which orders may be served or surveillance devices can be installed seem pretty much stretchable - others begin to protest while other EU governments seem to show the political will to adopt this famous legislation. The unequivocal obligation to reveal your private communication by law is an effective method to tempt the uninformed public into not using cryptography to protect their privacy and to criminalize those who do. Therefore it is important that some far-sighted people have begun to develop crypto-products that can help to face this threats and which may possibly lead away from PGP as well. It seems that 2001 promises to become a busy year.

References to Other Sources of Information

• m-o-o-t : Defense against RIPA
• International Cryptography
• The Federal Information Standards Publication: DIGITAL SIGNATURE STANDARD (DSS)
• The passphrase FAQ
• The Memorability and Security of Passwords - Some Empirical Results
  by Jianxin Yan, Alan Blackwell, Ross Anderson and Alasdair Grant
• The Electronic Privacy Information Center
• PGP Attacks by W. Unruh
• Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems by Paul C. Kocher
• Practical Attacks on PGP by Joel McNamara
• Commercial Data Recovery by Adam Back

Final Request

I have tried to turn all information I have come across into a well-founded valuation of the security of PGP. Maybe I have made some mistakes or I have drawn wrong conclusions. Please do not hesitate to send me your opinion, I am looking forward to your comments.

Thanks a Lot !

I would like to thank Stefan Kelm for his helping support during the composition of this document and especially I would like to thank my friend Thomas Schoch for his constant moral support of the whole project. Numerous others including Thomas Gebhard and Scott A Crosby have contributed hints and suggestions to improve the quality of this document during the revision. Thank you all very much.

Copyright © 1998-2001 Ralf Senderek