The Protection of Your Secret Key

Version 1.0 - October 1998

Ralf Senderek

Die Sicherheit des geheimen Schlüssels

How secure is PGP ?
Can a digital signature be forged
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.

The Security of the Cryptographic Methods Used by PGP
The Cipher IDEA
The Public Key Cryptosystem RSA
The Hashfunction MD5
Attacks on the Use of PGP
Security-relevant Actions
How to Deal with Your Passphrase
Attacks on Your Passphrase
What Is a Good Passphrase ?
The Newer the Better ? - Versions of PGP
References to Other Sources of Information
A Final Request


When using PGP you generally persue the following objectives: The certification authority strongly recommends the use of PGP-2.6.3i based on RSA-keys with a minimum length of 1024 bit to reach those objectives reliably. We reject the certification of DSS/DH-keys which have been introduced by newer versions of PGP recently
(see the argument below).

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

A third strategy might be to launch an attack on the implementation of PGP. This could be done by changing the sourcecode 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 sourcecode results in a binary which makes it hard for the average user to tell it apart from the secure version of PGP. Because of the fact 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 religous 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 don't want to put the security of PGP to risk unintentionally. Most important is maintaining the secrecy of your passphrase which protects your secret key because maintainig this secrecy is a problem most people do underestimate dramatically.


As all the cryptographic methods used by PGP-2.6.x 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 appear as the only legitimate author or recipient of 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 is far more performant. 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 hashfunction 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 PGP (subsequently I mean PGP-2.6.x) 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 crypted 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 convertation, 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 2128 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".


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

Because as a matter of principle a computer will not have the necessary efficiency.

According to todays state of physical research which in future could change the spreading of information in every imaginable computersystem is limited by the speed of light.
Not even the results of current "experiments measuring velocities higher than the speed of light" do contradict that fact.

If you assume the size of a high-performance computer system performing keytests 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 during 317 years is truely not sufficient for testing 1022 different IDEA-keys because every keytest requires more than a single operation cycle. But even if it was possible to do a keytest that fast, the large number of 1038 IDEA-keys would be 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 it is definitely wrong to suppose "efficiency of any size" for future computer systems.

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:

If a message has been encrypted with a 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 reconstruct 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. The intellectual property of a person can only be protected by proving the copyright on a document if nobody else is able to create an information that matches with the public key of this person.

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 analyzed 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 being 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 determinating 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.

The Previous History of Factoring

  • 70-digit numbers will be factored today (1998) on a workstation within 10 hours.
  • 100-digit numbers will be factored on a 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 computerprogram written by K. Lenstra (Bell Labs, Morristown, New Jersey) on their workstations at night sharing the work of factoring over the internet.

  • 140-digit numbers are the smallest numbers not having been factored in 1996.
    They will be factored within about 5 years using large-scale networking.
  • 160-digit numbers:
    In 1996 experts expect factoring to be possible within about 5 years using a new method of factoring known as number field sieve.
  • 200-digit numbers:
    The time for factoring is estimated at 52 000 000 years in 1998

Using a minimal key length of 1024 bit corresponding to an 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. Even today lots of PGP-keys are certified with key lenghts of 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 from these attacks you should avoid to sign 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. Because 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.

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, totally 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 sucessfully faktored 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 parallelized, so that it could 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 totally new algorithm will be found which would make todays secure RSA-keys absolutely worthless. So it will be essential to observe new developements in the field of factoring and to consider them carefully when evaluating the length of RSA-keys.

The Hashfunction MD5

The integrity of a message or the security that the message has not been changed during transportation over networks depends on the hashfunction MD5 which is used to generate a 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 totally different result. In this way even a minimal change of the message could be detected reliably. Because of the fact the hashfunction 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 1038 different hashvalues (or fingerprints) and the one which is generated with the new message is inpredictable.

Of course it is possible that some other text will accidentally produce the same hashvalue because even if the number of different hashvalues is very large, it is also limited. But such a collision could not be constructed intentionally because you have to try about 1038 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 hashvalue from any two different texts is only:
0.000 000 000 000 000 000 000 000 000 000 000 000 029 percent (1/2128).

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 transferred to forging a digital signature, the forger can benefit from this situation considerably. If she does not intend to forge a certain document but rather confines herself to submit a document for signing by the potential victim and she has already found a forged document with 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 certainly 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).


With N different documents (benign and malicious all in all) there are N(N-1)/2 pairs. Given that there are K = 2128 different hashvalues the probability of two different documents sharing the same hashvalue 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.
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 himself. That 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 pubic key as reliable you have to certify it by 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 by 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. Although 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!

Because if you aren't requested to enter your passphrase then your passphrase is stored somewhere or not been set anyway, which makes its compromitation 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 (may be 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 needs 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 to copy 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 multiuser 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.

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.

Attacks on Your Passphrase

Vulnerabilities of the Operating System

If you have 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 filesystem but it is still possible to recover the physically stored data, because deleting a file only cancels the link between the destroyed filename 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 few times. PGP has an option -w (wipe) for this purpose which overwrites the contents of an existing plaintext file at least once. Special
"file wiping utilities" do that job by overwriting the file several times.

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

Also 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 filesystem, 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 harddisk 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 professionality of another person who is responsible for the UNIX system.

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

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 keyloggers 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 runnig DOS or WINDOWS everybody will be able to install keyloggers without any difficulties, if he or she has access to your harddisk. But such an alteration could be done by a boot virus as well.
To get an efficient protection against these alterations of the operating system it is necessary to check the intactness 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.

Using 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 Sytem (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 Rune Braathen's Crash Course in X Windows Security. You should always avoid to enter 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 could restrict access to your X server to your localhost using the UNIX command "xhost -", so you could only be threatened by users who have already logged into your local computer.

Convenience and "Brandnew 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 realistic 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 authentification with a remote host using RSA and subsequently all data will be transferred over the network conventionally encrypted (i.e. with 3DES) 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 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 sent it over the internet via email. Convenience normally would urge you to use the precompiled 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 it in a safe place, so you can verify the integrity of the binary you are currently using with this fingerprint regularly.

Some PGP-shells have been developed for WINDOWS which comfortably save users the trouble of using PGP with its commandline options. Instead the processes of decryption, signing and key management have been hidden behind some "fancy buttons and checkboxes". 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.

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 secutity of your secret key at risk.

How Long Should a Passphrase Be ?

The passphrase protects your secret key from being used (or misused) by other individuals. If you like to have as much security as IDEA is offering, 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, solutions have to be found that will work safe. At this point two different strategies can be offered to guarantee the memory ot the passphrase, both leading to a loss of security.

Both strategies do raise the question what length will be required to make a passphrase still secure. My argument concerning the efficiency of a future computersystem has shown, that it will be sufficient to ensure, that the work for "systematic guessing" the passphrase will reach about 1022 operations. If you choose your passphrase in a way that in principle there are 1022 possible passphrases, you certainly are on the safe side. To cause this amount of work 72 bits or 9 Bytes will be sufficient, because this will leave 272 or 4,7 * 1021 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 sysmbols, 12 of those randomly chosen characters will be sufficient to cause the required work (7012 = 1,4 * 1022).
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 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 drastical deterioration.

A dictionary contains may be 60000 different items, so an arbitrary choice of five different items would again produce plenty of combinations (600005 = 7,7 * 1023). But your secure passphrase salmagundi_latrine_warning_gowk_marathon now has a lenght 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 lowtech computer technology (PC-486 and PGP-2.6.2). Performing at least two keytests 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 passphrese, 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 totally 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 1022 keytest. It is known that 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 1012 different possibilities.

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.

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 hashfunction 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 = GX 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's 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 2160 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. Whether or not the range of secret keys is also restricted to some extend with the ElGamal algorithm would be a worthwhile study beeing quite releant for the valuation of the security of the new method.

The New Key Format

With the introduction of the new DSS/DH-keys the format in which those keys were stored have also been changed. This change becomes visible in the new key filenames of the keyrings 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 CAF (Corporate Access Field), which brings along drastic changes . The CAF is designated for storing a second key in the user's key certificate, the message recovery key of the company. In this way the 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 recover key will be sent in addition to the addressee's public key. I do not know which mechanism will prevent a user's public key to be 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. Because while 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 compulsatorily 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 endevours 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 CAF (PGP-2.6.x) but also to warn of the threatening dangers of those new features to prevent their creeping adoption without open discussion. One could hope, that the efforts of developing an open standard for PGP (OpenPGP) will result in a clear exclusion of the possibility to link a user's public key with any other key.

References to Other Sources of Information

A Final Request

I have tried to turn all information I have come to know into a well-founded valuation of the security of PGP. May be I have made some mistakes or I have drawn wrong conclusions. Please do not hesitate
to send me your opinions, 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.

Copyright © 1998-2000 Ralf Senderek