Chapter 4. Keys

Q: Which key size should I use?
Q: Can a public key be forged?
Q: How do I detect a forged key?
Q: Why does PGP take so long to add new keys to my key ring?
Q: How can I extract multiple keys into a single armored file with the command line PGP?
Q: I tried encrypting the same message to the same address two times and got completely different outputs. Why is this?
Q: What does the message "Unknown signator, can't be checked" mean?
Q: How do I get PGP to display the trust parameters on a key?
Q: Should I include my key in every message (e.g. by putting it in my .signature)?
Q: How can I make my key available via finger?
Q: How do I specify which key to use when an individual has 2 public keys and the very same user ID on each, or when 2 different users have the same name?

Q: Which key size should I use?

A: PGP gives you choices for RSA and DSA key size ranging from 512 to 2048 or even 4096 bits. The larger the key, the more secure the RSA/DSA portion of the encryption is. The only place where the key size makes a large change in the running time of the program is during key generation. A 1024 bit key can take 8 times longer to generate than a 384 bit key. Fortunately, this is a one time process that doesn't need to be repeated unless you wish to generate another key pair.

During encryption, only the RSA portion of the encryption process is affected by key size. The RSA portion is only used for encrypting the session key used by the the symmetrical algorithm (IDEA, 3DES, CAST etcetera). The main body of the message is totally unaffected by the choice of RSA key size.

Dr Lenstra and Dr Verheul offer their recommendations for keylengths. In their calculation, a 2048 bit key should keep your secrets safe at least until 2020 against very highly funded and knowledgable adversaries (i.e. you have the NSA working against you). Against lesser adversaries such as mere multinationals your secret should be safe against bruteforce cryptoanalysis much longer, even with 1024 bit keys.

So unless you have a very good reason for doing otherwise, select the 1024 or 2048 bit key size. Using currently available algorithms for factoring and available computing power, the 384 and 512 bit keys are known to be within reach of adversaries and 768 is questionable (see also Can't you break PGP by trying all of the possible keys?).

Q: Can a public key be forged?

A: In short: not completely, but parts may be.

There are four components in a public key, each of which has its own weaknesses. The four components are user IDs, key IDs, signatures and the key fingerprint.

It is quite easy to create a fake user ID. If a user ID on a key is changed, and the key is then added to another keyring, the changed user ID will be seen as a new user ID and so it gets added to the ones already present. This implies that an unsigned user ID should never be trusted. Question Should I sign my own key? discusses this in more detail.

It is possible to create a key with a chosen key ID, as Paul Leyland explains:

A PGP key ID is just the bottom 64 bits of the public modulus (but only the bottom 32 bits are displayed with pgp -kv). It is easy to select two primes which when multiplied together have a specific set of low-order bits.

This makes it possible to create a fake key with the same key ID as an existing one. The fingerprint will still be different, though.

By the way, this attack is sometimes referred to as a DEADBEEF attack. This term originates from an example key with key ID 0xDEADBEEF which was created to demonstrate that this was possible.

There are currently no methods to create a fake signature for a user ID on someone's key. To create a signature for a user ID, you need the signatory's secret key. A signature actually signs a hash of the user ID it applies to, so you can't copy a signature from one user ID to another or modify a signed user ID without invalidating the signature.

Yes, it is possible to create a public key with the same fingerprint as an existing one, thanks to a design misfeature in PGP 2.x when signing RSA keys. The fake key will not be of the same length, so it should be easy to detect. Usually such keys have odd key lengths.

Paul Leyland provided the following technical explanation:

Inside a PGP key, the public modulus and encryption exponent are each represented as the size of the quantity in bits, followed by the bits of the quantity itself. The key fingerprint, displayed by pgp -kvc, is the MD5 hash of the bits, but NOT of the lengths. By transferring low-order bits from the modulus to the high-order portion of the exponent and altering the two lengths accordingly, it is possible to create a new key with exactly the same fingerprint.

Q: How do I detect a forged key?

A: As explained in question Can a public key be forged?, each component of the public key can be faked. It is, however, not possible to create a fake key for which all the components match.

For this reason, you should always verify that key ID, fingerprint, and key size correspond when you are about to use someone's key. And when you sign a user ID, make sure it is signed by the key's owner!

Similarly, if you want to provide information about your key, include key ID, fingerprint and key size.

Q: Why does PGP take so long to add new keys to my key ring?

A: The time required to check signatures and add keys to your public key ring tends to grow as the square of the size of your existing public key ring. This can reach extreme proportions, especially if you are trying to add the entire public keyring you retrieved from a keyserver (see What are the Public Key Servers?) to your own keyring.

In this case, it might be faster to rename your public keyring to something else, then name the keyserver's keyring pubring.pgp and add your own keyring to the big one. There is a danger to this, though; the trust parameters to your old keys will be lost, and you will be using the trust parameters from this big keyring. See also How do I create a secondary key file?.

A: If your keyring has been damaged, PGP can also take a while to process it.

Q: How can I extract multiple keys into a single armored file with the command line PGP?

A: A number of people have more than one public key that they would like to make available. One way of doing this is executing the -kxa command for each key you wish to extract from the key ring into separate armored files, then appending all the individual files into a single long file with multiple armored blocks. This is not as convenient as having all of your keys in a single armored block.

Unfortunately, the present version of PGP does not allow you to do this directly. Fortunately, there is an indirect way to do it.

   pgp -kx uid1 extract
    pgp -kx uid2 extract
    pgp -kx uid3 extract
   


This puts all three keys into extract.pgp. To get an ascii amored file, call: pgp -a extract.pgp

You get an extract.asc. Someone who does a pgp extract and has either file processes all three keys simultaneously.

A Unix script to perform the extraction with a single command would be as follows:

     #!/bin/sh
      for name in name1 name2 name3 ... ; do
      pgp -kx "$name" /tmp/keys.pgp <keyring>
      end
   
An equivalent DOS command would be: for %a in (name1 name2 name3 ...) do pgp -kx %a keys.pgp <keyring>

Q: I tried encrypting the same message to the same address two times and got completely different outputs. Why is this?

A: Every time you run PGP, a different session key is generated. This session key is used as the key for the symmetrical encryption algorithm (IDEA, 3DES etcetera). As a result, the entire header and body of the message changes. You will never see the same output twice, no matter how many times you encrypt the same message to the same address. This adds to the overall security of PGP.

To generate this random session key, PGP will try to use information from a file called randseed.bin. If this file does not exist, or for some reason isn't random enough, you are asked to type in some random keystrokes which will then be used as a "seed" for the random number generator.

Q: What does the message "Unknown signator, can't be checked" mean?

A: It means that the key used to create that signature does not exist in your public keyring, therefor PGP complains that it cannot check the signature. If at sometime in the future, you happen to add that key to your public keyring, then the signature line will read normally. It is completely harmless to leave these non-checkable signatures in your public keyring. They neither add to nor take away from the validity of the key in question.

Q: How do I get PGP to display the trust parameters on a key?

A: You can only do this when you run the -kc option by itself on the entire database. The parameters will not be shown if you give a specific ID on the command line. The correct command is: pgp -kc. The command pgp -kc smith will not show the trust parameters for "smith".

Q: Should I include my key in every message (e.g. by putting it in my .signature)?

A: No. Although it is important to spread your key as far as possible, it is a lot better to send it to a keyserver (see What are the Public Key Servers?) or to make it available via finger (see How can I make my key available via finger?), or perhaps as a link off your WWW homepage. This way, people who need your key will be able to get it, and you don't send it out to a lot of uninterested people every time you email or post something.

Additionally, keep in mind a snooper reading your outgoing mail can easily switch the public key in there with his own fake key. If this substituted key is used, the snooper can still read the messages sent to you. If the other party gets your key from a different location with a different method, it is a lot harder for that snooper to change the keys. Note that signing the message containing the key will not help; the snooper can easily re-sign the message with his key, see Can a public key be forged?. So always check the fingerprint as described in How do I detect a forged key?.

Q: How can I make my key available via finger?

A: The first step is always to extract the key to an ASCII-armored text file with pgp -kxa. After that, it depends on what type of computer you want your key to be available on. Check the documentation for that computer and/or its networking software.

Many computers running a Unix flavor will read information to be displayed via finger from a file in your home directory called .plan. If your computer supports this, you can put your public key in this file. Make sure the file is world-readable, use chmod 644 $HOME/.plan if other people can't get at your plan. The home directory also has to be accessible. Use chmod +x $HOME in your home directory to do this. Contact your system administrator if you have further problems with this.

Q: How do I specify which key to use when an individual has 2 public keys and the very same user ID on each, or when 2 different users have the same name?

A: Instead of specifying the user's name in the ID field of the PGP command, you can use the key ID number. The format is 0xNNNNNNNN where NNNNNNNN is the user's 8 character key ID number. It should be noted that you don't need to enter the entire ID number, a few consecutive digits from anywhere in the ID should do the trick. The key ID shows up directly after the key size when you do pgp -kv userid.

Be careful: If you enter 0x123, you will be matching key IDs 0x12393764, 0x64931237, or 0x96412373. Any key ID that contains 123 anywhere in it will produce a match. They don't need to be the starting characters of the key ID. You will recognize that this is the format for entering hex numbers in the C programming language. For example, any of the following commands could be used to encrypt a file to my public key:

       pgp -e <filename> "Wouter Slegers"
        pgp -e <filename> wouter@yourcreativesolutions.nl
        pgp -e <filename> 0x5217C2AF
   
This same method of key identification can be used in the config.txt file in the MyName variable to specify exactly which of the keys in the secret key ring should be used for encrypting a message.