Chapter 3. Security Questions

Q: How secure is PGP?
Q: Can't you break PGP by trying all of the possible keys?
Q: How secure is the conventional cryptography option?
Q: Can the NSA crack PGP (or RSA, DSS, IDEA, 3DES,...)?
Q: Has RSA ever been cracked publicly?
Q: What is the best way to crack PGP?
Q: What if I forget my pass phrase?
Q: Why do you use the term "pass phrase" instead of "password"?
Q: If my secret key ring is stolen, can my messages be read?
Q: How do I choose a pass phrase?
Q: How do I remember my pass phrase?
Q: How do I verify that my copy of PGP has not been tampered with?
Q: How do I know that there is no trap door in the program?
Q: I heard that the NSA put a back door in MIT PGP, and that they only allowed it to be legal with the back door.
Q: Is there a back door in the international version?
Q: Can I put PGP on a multi-user system like a UNIX machine or a mainframe?
Q: Can I use PGP under a "swapping" operating system like Windows, OS/2 or UNIX?
Q: Aren't all of these security procedures a little paranoid?
Q: Can I be forced to reveal my pass phrase in any legal proceedings?
Q: How secure is the "for your eyes only" option?

Q: How secure is PGP?

A: Very secure against eavesdroppers.

The cryptographic algorithms used for encryption and signing in PGP are very well researched and have shown no practical weaknesses (see Can't you break PGP by trying all of the possible keys?).

The big unknown in any encryption scheme based on RSA is whether or not there is an efficient way to factor huge numbers, or if there is some backdoor algorithm that can break the code without solving the factoring problem. Even if no such algorithm exists, it is still believed that RSA is the weakest link in the PGP chain.

A: PGP does not protect you if you use your secret key on a compromised system, i.e. you type your passphrase and sign or decrypt something, or if you stored the passphrase in plaintext on the compromised system (as described in How can I give my passphrase to the commandline PGP automatically?).

If you use PGP on a compromised system, the attacker can capture your passphrase as you type it. In combination with you secret keyring, this is sufficient to decode all messages that where encrypted with your public key and signing documents in your name thus impersonating you.

Make sure you keep your system secure from such compromises!

A: These are the most important attacks you should be aware of. It would be beyond the goal of this FAQ to discuss all possible attacks against or possible flaws in PGP. If you want to know more than what is available in here, see infiNity's PGP Attack FAQ.

Q: Can't you break PGP by trying all of the possible keys?

A: This is one of the first questions that people ask when they are first introduced to cryptography. They do not understand the size of the problem. For the IDEA encryption scheme, a 128 bit key is required. Any one of the 2128 possible combinations would be legal as a key, and only that one key would successfully decrypt the message. Let's say that you had developed a special purpose chip that could try a billion keys per second. This is far beyond anything that could really be developed today. Let's also say that you could afford to throw a billion such chips at the problem at the same time. It would still require over 10,000,000,000,000 years to try all of the possible 128 bit keys. That is something like a thousand times the age of the known universe! While the speed of computers continues to increase and their cost decrease at a very rapid pace, it will probably never get to the point that IDEA could be broken by the brute force attack.

The only type of attack that might succeed is one that tries to solve the problem from a mathematical standpoint by analyzing the transformations that take place between plain text blocks and their cipher text equivalents. IDEA is a well researched algorithm, and although work still needs to be done on it as it relates to complexity theory, so far it appears that there is no algorithm much better suited to solving an IDEA cipher than the brute force attack, which we have already shown to be unworkable.

Similarly all of the symmetrical algorithms additionally available in the 5.x and GNU Privacy Guard are not known to have significant flaws:

  • 3DES is probably the most studied cryptographic algorithm ever. It offers the strength equivalent to a 112-bit block cipher. The best attacks published require massive amounts of storage and still take more than 2108 operations.

  • CAST is a well studied 128-bit algorithm. There is no known way of breaking it faster then brute force.

  • AES or Rijndael is a relatice newcomer in crypto-algorithms, chosen to replace DES/3DES with larger keys (128, 192 or 256 bit) and higher performance. Although there is a lot of attention to all the AES-contestants and finalists in general and Rijndael in particular, it hasn't had nearly as much scrutiny as the previously mentioned algorithms.

  • Blowfish and its newer cousin (and AES-finalist) Twofish have gotten much (media) attention but are both still relatively new. Because of they do not seem encumbered by patents and there are no serious, publicly known attacks, these algorithms are popular with many open source projects.



Q: How secure is the conventional cryptography option?

A: Assuming that you are using a good strong random pass phrase, it is actually much stronger than the normal mode of encryption because you have removed RSA which is believed to be the weakest link in the chain. Of course, in this mode, you will need to exchange secret keys ahead of time with each of the recipients using some other secure method of communication, such as an inperson meeting or trusted courier.

This option is especially useful if you want to back up sensitive files, or want to take an encrypted file to another system where you will decrypt it. Now you don't have to take your secret key with you. It will also be useful when you lose your secret key. And you can even pick a different passphrase for each file you encrypt, so that an attacker who manages to get one file decrypted can't decrypt all the other files as well.

Q: Can the NSA crack PGP (or RSA, DSS, IDEA, 3DES,...)?

A: This question has been asked many times. If the NSA were able to crack RSA or any of the other well known cryptographic algorithms, you would probably never hear about it from them. Now that RSA and the other algorithms are very widely used, it would be a very closely guarded secret.

The best defense against this is the fact the algorithms are known worldwide. There are many competent mathematicians and cryptographers outside the NSA and there is much research being done in the field right now. If any of them were to discover a hole in one of the algorithms, I'm sure that we would hear about it from them via a paper in one of the cryptography conferences.

For this reason, when you read messages saying that "someone told them" that the NSA is able to break PGP, take it with a grain of salt and ask for some documentation on exactly where the information is coming from. In particular, the story called NSA Can Break PGP Encryption is a joke.

Q: Has RSA ever been cracked publicly?

A: Several messages RSA-encrypted with small (< 513 bits) keys have been cracked publicly. Further effort is still ongoing, RSA Security offers prizes for their RSA factoring challenges.

First was the RSA-129 key. The inventors of RSA published a message encrypted with a 129-digits (430 bits) RSA public key, and offered $100 to the first person who could decrypt the message. In 1994, an international team coordinated by Paul Leyland, Derek Atkins, Arjen Lenstra, and Michael Graff successfully factored this public key and recovered the plaintext. The message read: " THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE "

They headed a huge volunteer effort in which work was distributed via E-mail, fax, and regular mail to workers on the Internet, who processed their portion and sent the results back. About 1600 machines took part, with computing power ranging from a fax machine to Cray supercomputers. They used the best known factoring algorithm of the time; better methods have been discovered since then, but the results are still instructive in the amount of work required to crack a RSA-encrypted message.

The coordinators have estimated that the project took about eight months of real time and used approximately 5000 MIPS-years of computing time.

What does all this have to do with PGP? The RSA-129 key is approximately equal in security to a 426-bit PGP key. This has been shown to be easily crackable by this project. PGP used to recommend 384-bit keys as "casual grade" security; recent versions offer 768 bits as a recommended minimum security level.

Note that this effort cracked only a single RSA key. If this had been a PGP key, it would have allowed them to decrypt all messages encrypted to that key. Nothing was discovered during the course of the experiment to cause any other keys to become less secure than they had been, i.e. it would not make it any easier to read messages encrypted to other keys.

A year later, the first real PGP key was cracked. It was the infamous Blacknet key, a 384-bits key for the anonymous entity known as "Blacknet". A team consisting of Alec Muffett, Paul Leyland, Arjen Lenstra and Jim Gillogly managed to use enough computation power (approximately 1300 MIPS) to factor the key in three months. It was then used to decrypt a publicly-available message encrypted with that key.

The most important thing in this attack is that it was done in almost complete secrecy. Unlike with the RSA-129 attack, there was no publicity on the crack until it was complete. Most of the computers only worked on it in spare time, and the total power is well within reach of a large, perhaps even a medium sized organization.

Q: What is the best way to crack PGP?

A: Currently, the best attack possible on PGP itself is a dictionary attack on the pass phrase. This is an attack where a program picks words out of a dictionary and strings them together in different ways in an attempt to guess your pass phrase.

This is why picking a strong pass phrase is so important. Many of these cracker programs are very sophisticated and can take advantage of language idioms, popular phrases, and rules of grammar in building their guesses. Single-word "phrases" proper names (especially famous ones), or famous quotes are almost always crackable by a program with any "smarts" in it at all.

There is a program available which can "crack" conventionally encrypted files by guessing the passphrase. It does not do any cryptanalysis and works on the 2.x-format only, so if you pick a strong passphrase your files will still be safe. Unfortunately the original website has vanished. The program is still widely available, e.g. at zedz.net.

There are also other methods to get at the contents of an encrypted message, such as bribery, tapping your keyboard, installing trojan horses, snooping of electronic emanation from the computers processing the message (often called a TEMPEST attack), blackmail, or rubber-hose cryptoanalysis (beating you with a rubber hose until you give the passphrase or similar, see Can I be forced to reveal my pass phrase in any legal proceedings?).

Q: What if I forget my pass phrase?

A: In a word: don't. If you forget your pass phrase, there is absolutely no way to recover any encrypted files. If you're concerned about forgetting your passphrase, you could make a copy of your secret keyring, change its passphrase to something else you are sure not to forget, and then store the secret keyring with the changed passphrase in a safe location.

Q: Why do you use the term "pass phrase" instead of "password"?

A: This is because most people, when asked to choose a password, select some simple common word. This can be cracked by a program that uses a dictionary to try out passwords on a system. Since most people really don't want to select a truly random password, where the letters and digits are mixed in a nonsense pattern, the term pass phrase is used to urge people to at least use several unrelated words in sequence as the pass phrase.

Q: If my secret key ring is stolen, can my messages be read?

A: No, not unless they have also stolen your secret pass phrase or you foolishly put it in plaintext on the same disk (see How can I give my passphrase to the commandline PGP automatically?), or if your pass phrase is susceptible to a brute-force attack. Neither part is useful without the other. You should, however, revoke that key and generate a fresh key pair using a different pass phrase just to be sure. Before revoking your old key, you might want to add another user ID that states what your new key id is so that others can know of your new address.

Q: How do I choose a pass phrase?

A: All of the security that is available in PGP can be made absolutely useless if you don't choose a good pass phrase to encrypt your secret key ring. Too many people use their birthday, their telephone number, the name of a loved one, or some easy to guess common word. While there are a number of suggestions for generating good pass phrases, the ultimate in security is obtained when the characters of the pass phrase are chosen completely at random. It may be a little harder to remember, but the added security is worth it. As an absolute minimum pass phrase, I would suggest a random combination of at least 8 letters and digits, with 12 being a better choice. With a 12 character pass phrase made up of the lower case letters a-z plus the digits 0-9, you have about 62 bits of key, which is 6 bits better than the 56 bit DES keys. If you wish, you can mix upper and lower case letters in your pass phrase to cut down the number of characters that are required to achieve the same level of security.

A pass phrase which is composed of ordinary words without punctuation or special characters is susceptible to a dictionary attack. Transposing characters or mis-spelling words makes your pass phrase less vulnerable, but a professional dictionary attack will cater for this sort of thing.

See Randall T. Williams' Passphrase FAQ for a more detailed analysis.

Q: How do I remember my pass phrase?

A: This can be quite a problem especially if you are like me and have about a dozen different pass phrases that are required in your everyday life. Writing them down someplace so that you can remember them would defeat the whole purpose of pass phrases in the first place. There is really no good way around this. Either remember it, or write it down someplace and risk having it compromised.

It may be a good idea to periodically try out all the passphrases, or to iterate them in your mind. Repeating them often enough will help keep them from being completely blanked out when the time comes that you need them.

If you use long passphrases, it may be possible to write down the initial portion without risking compromising it, so that you can read the "hint" and remember the rest of the passphrase. If you chose to write down these (partial) passphrases, consider putting them in an tamper evident, non-transparent enveloppe and storing them in a secure place.

For a simple way to pick provably strong passphrases that are easy to remember, please see Arnold Reinhold's Diceware website.

Q: How do I verify that my copy of PGP has not been tampered with?

A: If you do not presently own any copy of PGP, use great care on where you obtain your first copy. What I would suggest is that you get two or more copies from different sources that you feel that you can trust. Compare the copies to see if they are absolutely identical. This won't eliminate the possibility of having a bad copy, but it will greatly reduce the chances.

If you already own a trusted version of PGP, it is easy to check the validity of any future version. Newer versions of PGP are distributed in popular archive formats; the archive file you receive will contain only another archive file, a file with the same name as the archive file with the extension .asc, and a setup.doc file. The .asc file is a stand-alone signature file for the inner archive file that was created by the developer in charge of that particular PGP distribution. Since nobody except the developer has access to his/her secret key, nobody can tamper with the archive file without it being detected. Of course, the inner archive file contains the newer PGP distribution.

Q: How do I know that there is no trap door in the program?

A: The fact that the entire source code for the free versions of PGP is available makes it just about impossible for there to be some hidden trap door. The source code has been examined by countless individuals and no such trap door has been found. To make sure that your executable file actually represents the given source code, all you need to do is to compile the program yourself and use the resulting executable.

For the PGP 5.x and higher versions based on the PGPsdk so its sourcecode can be verified, but the use of "home-compiled" binaries seems to be forbidden by the license, even when you bought a commercial license for the same product. Only comparison between a "home-compiled" binary and the binaries as provided in the commercial package seems to be allowed, but this very hard and has not been succesfully done as far as I know (even if exactly the same compiler with exactly the same options would be used, the resulting binary would differ in non-trivial ways). Bottom line: if you do not trust NAI to have sold you the untampered version, you should be using one of the open source versions whose license does allow compilation from source and use of the subsequent binary.

Q: I heard that the NSA put a back door in MIT PGP, and that they only allowed it to be legal with the back door.

A: First of all, the NSA had nothing to do with PGP becoming "legal". The legality problems solved by MIT PGP had to do with the alleged patent on the RSA algorithm used in PGP.

Second, all the freeware versions of PGP are released with full source code to both PGP and to the RSAREF library they use (just as every other freeware version before them was). Thus, it is subject to the same peer review mentioned in the question above. If there were an intentional hole, it would probably be spotted. If you're really paranoid, you can read the code yourself and look for holes!

Q: Is there a back door in the international version?

A: No. The international version of PGP is based on an illegally exported version of PGP, and uses an RSA encryption/decryption library (MPILIB) which may have violated the RSA patent which is only valid in the USA (see What's with the patent on RSA?).

There are no intentional backdoors of any kind in the international version, nor is the encryption strength reduced in any way.

Q: Can I put PGP on a multi-user system like a UNIX machine or a mainframe?

A: Yes. PGP will compile and run on several high-end operating systems such as Unix and VMS. Other versions may easily be used on machines connected to a network.

You should be very careful, however. Your pass phrase may be passed over the network in the clear where it could be intercepted by network monitoring equipment, or the operator on a multi-user machine may install "keyboard sniffers" to record your pass phrase as you type it in. Also, while it is being used by PGP on the host system, it could be caught by some trojan horse program. Also, even though your secret key ring is encrypted, it would not be good practice to leave it lying around for anyone else to look at. Also do not leave the passphrase around (see How can I give my passphrase to the commandline PGP automatically?).

So why distribute PGP with directions for making it on Unix and VMS machines at all? The simple answer is that not all Unix and VMS machines are network servers or "mainframes." If you use your machine only from the console (or if you use some network encryption package such as Kerberos, IPSec or SSH), you are the only user, you take reasonable system security measures to prevent unauthorized access, and you are aware of the risks above, you can securely use PGP on one of these systems.

You can still use PGP on multi-user systems or networks without a secret key for checking signatures and encrypting. As long as you don't process a private key or type a pass phrase on the multiuser system, you can use PGP securely there.

Of course, it all comes down to how important you consider your secret key. If it's only used to sign posts to Usenet, and not for important private correspondence, you don't have to be as paranoid about guarding it. If you trust your system administrators, then you can protect yourself against malicious users by making the directory in which the keyrings are only accessible by you.

Q: Can I use PGP under a "swapping" operating system like Windows, OS/2 or UNIX?

A: Yes. PGP 2.x runs OK in most "DOS windows" for these systems, and PGP can be built natively for many of them as well.

The problem with using PGP on a system that swaps is that the system will often swap PGP out to disk while it is processing your pass phrase. If this happens at the right time, your pass phrase could end up in cleartext in your swap file. How easy it is to swap "at the right time" depends on the operating system; Windows reportedly swaps the pass phrase to disk quite regularly, though it is also one of the most inefficient systems. PGP does make every attempt to not keep the pass phrase in memory by "wiping" memory used to hold the pass phrase before freeing it, but this solution isn't perfect.

Because swapfiles shrink, and many applications (e.g. Microsoft Word and Microsoft compilers) grab disk space (and unused memory) and don't always fill it all out, you will regularly get fragments of other work embedded in files unrelated to it.

Disabling swapping (after getting more memory) will help, but you should also be cautious about sending binary attachments (like Word DOCs). If you wish to keep your hard-drive more secure, you should consider a sector-level encryptor (such as Scramdisk, SFS or PGPdisk).

If you have reason to be concerned about this, you might consider getting a swapfile wiping utility to securely erase any trace of the pass phrase once you are done with the system. Several such utilities exist for Windows and Linux at least. Many of them perform not nearly as well as claimed in the documentation though. Under OpenBSD you can configure the OS to encrypt the swap, preventing this altogether.

Q: Aren't all of these security procedures a little paranoid?

A: That all depends on how much your privacy means to you! Even apart from the government, there are many people out there who would just love to read your private mail. And many of these individuals would be willing to go to great lengths to compromise your mail. Look at the amount of work that has been put into some of the virus programs that have found their way into various computer systems, including the old "Caligula"-virus that sends the PGP secret keyring to the codebreakers.org site. Even when it doesn't involve money, some people are obsessed with breaking into systems. Once a system is compromised, use of PGP on that system will expose both your pass phrase and secret keyring, giving the attacker everything to he needs to read your secret mail.

In addition, don't forget that private keys are useful for more than decrypting. Someone with your private key can also sign items that could later prove to be difficult to deny. Keeping your private key secure can prevent, at the least, a bit of embarassment, and at most could prevent charges of fraud or breach of contract.

Besides, many of the above procedures are also effective against some common indirect attacks. As an example, the digital signature also serves as an effective integrity check of the file signed; thus, checking the signature on new copies of PGP ensures that your computer will not get a virus through PGP (unless, of course, the PGP version developer contracts a virus and infects PGP before signing).

Q: Can I be forced to reveal my pass phrase in any legal proceedings?

A: Bert-Jaap Koops has a Crypto and Self-Incrimination FAQ adressing this issue. The ultra-short version is that no country is known to have a law requiring suspects to decrypt under legal warrant, with the exception of the UK and the Regulation of Investigatory Powers Act 2000.

Note that the GNU Privacy Guard has a --show-session-key option specifically for those under the obligation to provide the decryption key. It allows one to disclose the individual session keys of encrypted messages instead of the longlived secret keys. Without disclosure of your secret keys, newly encrypted messages are still safe from all prying eyes.

Note that law enforcement agencies have been known to install means to capture your passphrase and/or plaintext, such as keyboard sniffers and trojans, making the self-incrimination question irrelevant.

Q: How secure is the "for your eyes only" option?

A: It is not secure at all. There are many ways to defeat it. Probably the easiest way is to simply redirect your screen output to a file as follows: pgp [filename] > [diskfile]

The "for your eyes" option was not intended as a fail-safe option to prevent plain text files from being generated, but to serve simply as a warning to the person decrypting the file that he probably shouldn't keep a copy of the plain text on his system.