The comp.security.pgp FAQ

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.

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.

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 2^128 possible combinations would be legal as a key, and only that one key would successfully decrypt all message blocks. 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 still a fairly new algorithm, and work still needs to be done on it as it relates to complexity theory, but 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 is unworkable. The nonlinear transformation that takes place in IDEA puts it in a class of extremely difficult to solve mathmatical problems.

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 in- person 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 now.

This question has been asked many times. If the NSA were able to crack RSA, you would probably never hear about it from them. Now that RSA is getting more and more popular, it would be a very closely guarded secret. The best defense against this is the fact the algorithm for RSA is 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 RSA, I'm sure that we would hear about it from them. I think that it would be hard to hide such a discovery.

For this reason, when you read messages on USENET 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 message at http://www.quadralay.com/www/Crypt/NSA/break-pgp.html is a joke.

Two RSA-encrypted messages have been cracked publicly.

First, there is 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 512 bits as a recommended minimum security level.

Note that this effort cracked only a single RSA key. Nothing was discovered during the course of the experiment to cause any other keys to become less secure than they had been.

For more information on the RSA-129 project, see: ftp://ftp.ox.ac.uk/pub/math/rsa129/rsa129.ps.gz

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.

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

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, then change the passphrase to something else, and then store the secret keyring with the changed passphrase in a safe location.

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.

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, so if you pick a strong passphrase your files will still be safe. See http://www.voicenet.com/~markm/pgpcrack.html for more information and the program itself.

There are also other methods to get at the contents of an encrypted message, such as bribery, snooping of electronic emanation from the computers processing the message (often called a TEMPEST attack), blackmail, or "rubber-hose cryptography" - beating you on the head with a rubber hose until you give the passphrase.

No, not unless they have also stolen your secret pass phrase, 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. 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.

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.

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. For a simple way to pick provably strong passphrases that are easy to remember, please see Arnold Reinhold's Diceware website.

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 binary versions of MIT 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.

A quick note: If you upgrade to MIT PGP from an older copy (2.3a or before), you may have problems verifying the signature. See question 3.14 for a more detailed treatment of this problem.

To check the signature, you must use your old version of PGP to check the archive file containing the new version. If your old version of PGP is in a directory called C:\PGP and your new archive file and signature is in C:\NEW (and you have retrieved MIT PGP 2.6.2), you may execute the following command:
c:\pgp\pgp c:\new\pgp262i.asc c:\new\pgp262i.zip

If you retrieve the source distribution of MIT PGP, you will find two more files in your distribution: an archive file for the RSAREF library and a signature file for RSAREF. You can verify the RSAREF library in the same way as you verify the main PGP source archive.

Non-MIT versions typically include a signature file for the PGP.EXE program file only. This file will usually be called PGPSIG.ASC. You can check the integrity of the program itself this way by running your older version of PGP on the new version's signature file and program file.

Phil Zimmermann himself signed all versions of PGP up to 2.3a. Since then, the primary developers for each of the different versions of PGP have signed their distributions. As of this writing, the developers whose signatures appear on the distributions are:

MIT PGP 2.6.2                Jeff Schiller <jis@mit.edu>
ViaCrypt PGP 2.7.1           ViaCrypt
PGP 2.6.2i                   Stale Schumacher <staalesc@ifi.uio.no>
PGP 2.6ui                    mathew <mathew@mantis.co.uk>

The reason for this, of course, is that the signatures generated by MIT PGP (which is what Jeff Schiller uses to sign his copy) are no longer readable with PGP 2.3a.

You may, first of all, not verify the signature and follow other methods for making sure you aren't getting a bad copy. This isn't as secure, though; if you're not careful, you could get passed a bad copy of PGP.

If you're intent on checking the signature, you may do an intermediate upgrade to MIT PGP 2.6. This older version was signed before the "time bomb" took effect, so its signature is readable by the older versions of PGP. Once you have validated the signature on the intermediate version, you can then use that version to check the current version.

As another alternative, you may upgrade to PGP 2.6.2i or 2.6ui, checking their signatures with 2.3a, and use them to check the signature on the newer version. People living in the USA who do this may be violating the RSA patent in doing so; then again, you may have been violating it anyway by using 2.3a, so you're not in much worse shape.

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 re-compile the entire program.

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 were). 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!

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 violate a patent which is only valid in the USA.

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

Yes. PGP will compile for 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.

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

Yes. PGP for DOS 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.

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.

Two reasons: First, the IDEA encryption algorithm used in PGP is actually much stronger than RSA given the same key length. Even with a 1024 bit RSA key, it is believed that IDEA encryption is still stronger, and, since a chain is no stronger than its weakest link, it is believed that RSA is actually the weakest part of the RSA - IDEA approach. Second, RSA encryption is much slower than IDEA. The only purpose of RSA in most public key schemes is for the transfer of session keys to be used in the conventional secret key algorithm, and to encode signatures.

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. Even when it doesn't involve money, some people are obsessed with breaking into systems.

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

Gary Edstrom reported the following in earlier versions of this FAQ:

The following information applies only to citizens of the United States in U.S. Courts. The laws in other countries may vary.

There have been several threads on Internet concerning the question of whether or not the fifth amendment right about not being forced to give testimony against yourself can be applied to the subject of being forced to reveal your pass phrase. Not wanting to settle for the many conflicting opinions of armchair lawyers on usenet, I asked for input from individuals who were more qualified in the area. The results were somewhat mixed. There apparently has NOT been much case history to set precedents in this area. So if you find yourself in this situation, you should be prepared for a long and costly legal fight on the matter. Do you have the time and money for such a fight? Also remember that judges have great freedom in the use of "Contempt of Court". They might choose to lock you up until you decide to reveal the pass phrase and it could take your lawyer some time to get you out. (If only you just had a poor memory!)