The Keysigning Party HOWTO

Copyright (c) 2000-2008 V. Alex Brennen (VAB).

This document is hereby placed in the public domain.

This document lives at http://cryptnet.net/fdp/crypto/keysigning_party/en/keysigning_party.html (DocBook XML)

This document is currently only available in the following languages:

If you know of a translation or would like to translate it to another language please let me know so that I can distribute or link to the translated versions.

A key signing party is a get-together of people who use the PGP encryption system with the purpose of allowing those people to sign each others keys. Key signing parties serve to extend the web of trust to a great degree. Key signing parties also serve as great opportunities to discuss the political and social issues surrounding strong cryptography, individual liberties, individual sovereignty, and even implementing encryption technologies or perhaps future work on free encryption software.

Key signing is act of digitally signing a public key packet and a user id packet that is attached to the key in that public key packet. Key signing is done to verify that a given user id and public key really do belong to the entity that appears to own the key. In more basic terms it is done to verify that the representation of identity in the user id packet is valid. Usually, this means that the name on the PGP key matches the name on the identification the person is presenting to you when asking that you sign their key.

The term "public key" has two meanings in PGP terminology. It can refer both to the actual public encryption key of a key pair or it can refer to the public encryption key of a key pair and the collection of associated signatures made upon that key as well as any encryption subkeys self-signed with that public key. To avoid confusion in this document, I will use the term "public key" when refering to the key, signatures, and subkeys. I will use the term "public key packet" when refering to the public encryption key of a key pair.

You can digitally sign your own public key packet and any associated id in that public key, or another entity's public key packet and associated user ids. Self signatures prevent adversaries from appending fake encryption or signature keys on your public key material while it is stored publicly or while it is being transmitted. If an adversary were able to add a fake encryption or signature key, they could add a public key packet to which only they posses the private key. This could result in an individual who wishes to communicate with you in secret inadvertently transmitting their communication to the person that serendipitously modified your public key in transit. By default, GnuPG and most other implementation of the openPGP standard automatically perform self signature on all User ID packets generated for a public key.

In a sense, key signatures validate public keys. They are an endorsement of validity of a public key packet and associated id by a third party. This is the way in which key signing builds the web of trust.

"Web of trust" is a term used to describe the trust relationships between a group of keys. A key signature is a link, or strand if you will, in the web of trust. These links are called "Trust Paths". Trust paths can be bi-directional or only one way. The ideal web of trust is one in which everyone is connected bi-directionally to everyone else. In effect, everyone trusts that every key does in fact belong to its owner. The web of trust can be thought of as the sum of all the trust paths, or links, between all key holding parties. As a visual example, here is a graph of a web of trust that I belong to.

Figure 2.1. An Example Web Of Trust Graph

There are three primary reasons to hold as many key signing parties as you possibly can.

First, and perhaps most importantly, you should hold as many key signing parties as possible in order to expand the web of trust. The deeper and more tightly inter-linked the web of trust is, the more difficult it is to defeat. This is of special significance to the Free Software Community, for both developers and users alike. Members of the community rely upon PGP technology to cryptographically protect the integrity of their software packages, security advisories, and announcements. The strength and robustness of the web of trust is directly proportional to the strength of the protection PGP provides the community from security threats such as trojan horses, malware, viruses, and forged messages.

Second, key signing parties help others get integrated into the security culture and encourage them to gain an understanding of PGP and related strong cryptography technologies. In order to get the benefits of strong cryptography, people must use strong cryptography, and use it properly. This requires a basic understanding of the underlying technology. It can be difficult for people new to computers and new to the free software culture to gain such an understanding. Introducing people who lack knowledge and skills in cryptography to individuals that have developed them can be very helpful to those trying to learn. It provides a great deal of value and benefits everyone.

Finally, key signing parties help build communities. They help techies get together to get to know each other, network, and discuss important issues like civil liberties, cryptorights, and internet regulation. Discussion is important because discussion is not only the first step, but also the step before action. When I first wrote this document there were not very many complex webs of trust in the world. Things have dramatically improved, with more plentiful webs that are much deeper than they were a few years ago. However, it still remains the case that if you work to build a web of trust in your local area, it is very likely that the first participants in that web will be the leaders and policy setters of the internet community in your area. They are the individuals who can choose to build secure strong cryptographic technology and protocols into the local infrastructure if they so choose. The integration of such technology and protocols could make issues like the FBI's carnivore system and the National Security Agency's illegal domestic surveillance technologically infeasible and therefore moot.

As an example, let's say that Alice and Bob generate PGP Keys with Gnu Privacy Guard (GPG) and hold a PGP key signing party. At the party Alice and Bob go verify each others' key information and later sign each others' keys. GPG by default automatically signs the public key of every pair it generates with the associated private key. So, Alice and Bob both now have at least two signatures validating that their keys belong to them. Alice's key was signed by Alice herself and by Bob. Bob's key was signed by Bob himself and Alice. In the future Alice and Bob meet Cathy. Cathy generates a key pair and tells Alice and Bob that she will send them both her key. Alice doesn't like Cathy and doesn't want Bob to exchange encrypted communications with her. Both Alice and Cathy generate PGP keys which they claim belong to Cathy. They both send them to Bob. Both keys have one signature, the self signature of the associated private key. Bob does not know which key is really Cathy's.

Cathy hears that Bob got two keys, and suspects Alice. Cathy, now angry, wishes to gain information that she can use against Alice. In order to acquire this information Cathy must compromise the encrypted communications between Alice and Bob. In order to do this, Cathy decides to forge an email to Bob from Alice telling him that Alice has generated a new key pair - a key pair for which only Cathy has the private key. In the forged email, Cathy includes Alice's "new" public key (which is in fact a fake key generated by Cathy). However, Bob knows for sure this is a trick because even though Bob now has two keys for Alice, one of the keys has been signed by multiple people (himself and Alice) verifying that it does indeed belong to Alice, while the other key - Cathy's fake key - only has its own signature.

The above example is very simplified and things can get a lot more complicated than that. You can read through the PGP FAQs or a good book on PKI for more information and a more detailed explanation. The above example does clearly explain the basics of key signing and its value. Cathy was not able to introduce a fake key pair for Alice because of the web of trust interconnections (key signatures) between Bob and Alice.

It is important to note however that signatures and webs of trust do not guarantee trustable keys. For example, when Bob and Alice first met Cathy, let's say that a friend of Cathy's, Donald, had been with Cathy. Donald could have generated fake key pairs for Alice and Bob, signed them with his key and signed both pairs of keys with the other pairs resulting in three signatures on each key and sent them to Cathy. Cathy would be facing a series of bad keys and signatures. How could key signing help Cathy resist such an attack? Well, let's say that all the people involved where exchanging keys through a key server. If Cathy searched the key server for Alice and Bob's keys, she'd find two sets for both Alice and Bob. If Alice and Bob had collected twenty key signatures at the keysigning party, it's obvious that Cathy could possibly better trust the public keys signed by twenty different individuals than the ones signed by only three individuals. Cathy should know something's up from the existence of the extra public keys - so she can look for closely at the generation dates and the trust web behind the public keys. The twenty keys from the party signatures should all be signed by twenty or more different individuals and have those signing keys would most likely have widely varying generation times. It's probable that the keys that signed the keysigning party's participant's keys were also signed by other keys of people who did not attend the party. Perhaps, people who don't even live in the same area. That would not be the case for the faked keys if Donald had generated twenty faked key pairs and generated a faked web of trust. The scope of Donald's fake web of trust would be limited in size and depth to the number of keys Donald generated or had gain control of. The multilayered web of trust supporting the real keys would provide a strong suggestion that Alice and Bob's genuine keys were more trustable than Donald's fake keys.

There are different possible structures for keysigning parties. These different formats were designed to accommodate the increasing levels of participation as PGP has become more popular. The sections below describe three of the most common methods and provide instructions for each one. By reading the Theory subsections below, you'll be able to determine and select the right party method for you.

The larger the party the better. You can announce your party to your local LUG email list, other computer related lists you're on in the area, even place an ad in the news paper or issue a press release.

If you're just starting to build the web of trust in your area, it's a good idea to try and get other active PGP users involved because they are the ones who are most likely to hold key signing parties of their own in the future. Good ways find such people are to talk with others who've sent email to lists you're on with PGP signatures, or by searching the keyserver networks for keys with email addresses specific to your local area. For example, email addresses that end in the domains of a university or large company which are located in your area often yield very high numbers of interested parties.

Greg Mullane developed a very nice site, know as Big Lumber, for finding individuals near a given geographical location interested in participating in keysigning parties. Listing your keysigning party and yourself no the site is a good way to promote your party. It is also a great way to fine out about other parties that happening near you or near destinations you're planning on traveling to.

Here are some sample announcements:

The process of generating a key pair is rather simple. Basically, you just need to run:

gpg --gen-key

However, I recommend that you also generate a revocation certificate for your key in case you ever loose access to your secret key (i.e. loose your passphrase or loose your secret key). The instructions for generating a revocation certificate can be found in the section called “Generating a Revocation Certificate” of this document.

The step-by-step instructions below where written with best practice security (severe paranoia) in mind. For example:

Some people may be comfortable with out taking all of these security precautions. For example, if you have a portable computer or a home computer which you read all of your email from, you may feel comfortable enough to store your key on the hard drive of that computer. You may also feel comfortable generating a key pair that never expires which you can use for identification and most communications only. You can then generating additional key pairs for extremely sensitive communications (should you have any). Again, the step by step instructions below were written with best practice security in mind. You don't necessarily need to follow them, you just need to generate a keypair. On the other hand, if you are an extremely paranoid security freak like me following the directions below will temporarily provide you with that swiftly fleeting sense of calm that you ohh so need to feel right now.

1) Go to GnuPG's Website and download the latest version of gnupg, gnupg-x.x.x.tar.gz. Then download the detached PGP signature of that archive, gnupg-x.x.x.tar.gz.sig.

Warning: Make sure you're running at least version 1.4.3 of GnuPG. Versions prior to 1.4.3 had at least one significant security weakness in them.

2) Check the PGP signature and the SHA-1 Checksum on the GnuPG archive:

bash$ gpg --verify gnupg-x.x.x.tar.gz.sig gnupg-x.x.x.tar.gz
bash$ sha1sum gnupg-x.x.x.tar.gz

3) Extract the archive, configure, compile and install it:

bash$ tar xzf gnupg-x.x.x.tar.gz
bash$ cd gnupg-x.x.x
bash$ ./configure
bash$ make
bash$ su
bash# make install
bash# exit
bash$ cd

If you share the system you're install GnuPG on with others, you may also want to make gpg setuid root so that it can use secured memory. If you do choose to do this, you should make sure to take precautions previously recommended, checking your archive with the sha1sum signature and the pgp signature to make sure you're not installing a trojan horse.

4) Get a USB device to store your keys on and partition and format it.

bash# /sbin/fdisk /dev/sda
bash# /sbin/mkfs.ext3 /dev/sda1

4a) Mount the USB device and make a directory on it owned by you for your keys:

bash$ mount /mnt/usbfs
bash$ mkdir /mnt/usbfs/.gnupg

and if necessary (depending on device access on your system):

bash$ chown <your_uid>:<your_gid> /mnt/usbfs/.gnupg

4b) Make a symlink from your home dir to the USB device

bash$ ln -s /mnt/usbfs/.gnupg .gnupg

5) Generate your gnupg keys

bash$ gpg --gen-key

5a) Select the key types you want - The default is good.

Please select what kind of key you want:

   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
Your selection? <return>

5b) Select your key size: 4096

RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048) 4096<return>
Requested keysize is 4096 bits

5c) Set the lifetime of this key: 5 years is good

Requested keysize is 4096 bits
Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 1y<return>
Key expires at Fri Nov  5 00:19:43 EST 2014
Is this correct (y/n)? y<return>

5d) Enter your name and email address(es)...

Real name: Demo User<return>
Email address: demo@nonexistent.nowhere<return>
Comment:
You selected this USER-ID:
    "Demo User <demo@nonexistent.nowhere>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit?  O<return>

5e) Choose a pass phrase. You need to pick a good one. It should be long and very difficult to guess. Any pass phrase less than twelve characters can be guessed by current cluster computing technology. A best practice is to use a program like passgen (FreshMeat) to generate your phrase from operating system sources of pseudorandomness. If you don't use a program like passgen, a pass phrase rather than a password is highly recommended. It should be something you won't forget. If you forget your pass phrase, you cannot recover your key.

5f) Move the mouse and hit some keys maybe update locate in the background or run a big find. GPG is reading from /dev/random to get some randomness for your key generation. /dev/random is populated in part by the interrupts happening on your computer.

6) Modify your key if you want. For example if you have multiple email addresses and you want to list them as valid on your key:

bash$ gpg --list-secret-keys

/home/demo/.gnupg/secring.gpg
----------------------------
sec  4096R/C01BAFC3 2013-11-05 Demo User <demo@dublin.ie>
ssb  4096R/7A4087F3 2013-11-05
bash$ gpg --edit-key C01BAFC3
Command> help
Command> adduid
[...]
Command> save

7) Optionally, send your key to the keyserver:

bash$ gpg --keyserver <keyserver> --send-key <Your_Key_ID>

You should see a success message like this:

gpg: success sending to `<keyserver>' (status=200)

8) Email your info to the Coordinator telling him that you're coming to the key signing party. The command below will print out the information that you want to need to send to the coordinator if you're using a keyserver. You can then send that information in an encrypted email message to the coordinator.

bash$ gpg --fingerprint  <Your_Key_ID>

9) Unmount the usbdevice and remove it:

bash$ umount /mnt/usbfs

Note: You can carry the USB Flash device around with you for additional security, or you can just leave it in a safe, locked desk drawer etc. Generally, it's a very bad idea to have your .gnupg directory containing your keys in a location accessible over the internet. If an attacker makes a copy of your secret key ring file, he can run a dictionary (password guessing) attack against it to gain control of your keypair.

10) Show up at the party.

This following additional step is optional, but recommended.

A revocation certificate is a special from of digital signature on a public key that can be used to revoke that key in the event that you loose access to your private key due to compromise, seizure, forgotten passphrase, or media failure. To use a revocation certificate, you simply need to circulate it in the same matter that you circulated your public key. For example, if you upload the revocation certificate to a public keyserver, the keyserver will merge it with your key there by revoking it. If you want to have the ability to revoke your public key when you do not have access to your private key, you should generate a revocation certificate and store it a secure and safe place. You should also print out a copy of your ascii encoded revocation certificate so that it can be entered and used in the event of the failure or loss of the media that it is stored on.

If you revocation certificate is compromised, the individual who compromises your revocation certificate will be able to circulate the certificate thereby disabling your key. However, the individual will not be able to compromise your secret key through his access to your revocation certificate. Therefor, they will not be able to generate fake signatures, decrypt messages encrypted with your keypair, or otherwise misrepresent themselves as the owner of your keypair. Since the only negative outcome possible from the compromise of a revocation certificate is the disabling of your keypair, it is a generally safe and good thing to do.

The GnuPG command to generate an ascii encoded revocation certification is:

bash$ gpg --output revcert.asc --gen-revoke <key_id>

It's important to note here that some people believe that keeping their public key secret adds an extra degree of security to their encrypted communications. This is true, because a keyserver could be broken or compromised and return the incorrect public key when queried. Further, the key on a given public keyserver may not be the most up to date version of the key. For example, additional signatures may have been added to the key which have not been propagated or uploaded to the keyserver. Those signatures could include key or user id revocation signatures which could result in the continued use of a key or user id which had been revoked due to compromise. It is also true because the public key of a key pair is needed to carry out certain types of attacks against the public key cryptosystems which pgp uses. While many people expect, with reasonably large keysizes, that these attacks are so extremely unlikely to be successful that it does not matter if the public key is broadcast, keeping the public key secret does in fact strengthen the key pair by reducing the possibility of an opportunity where these attacks can be attempted. Finally, some details of your social network and who you have met in the past, and possibly may speak with now, may be leaked by what signatures have been made on that public key.

I don't recommend that you keep your public key secret as it will discourage others from using PGP in their communications with you. To address the issue of the possibility of a compromised or broken keyserver returning an invalid key you can take steps to protect yourself from having messages sent to you encrypted with invalid keys, such as publishing your key's fingerprint in your .signature file or on your web page. To address the concern about the attacking of your key pair though your publicly available public key, I would say that if you are very concerned about the strength of your keypair or truly paranoid about the secrecy of your communications, you could generate additional keypairs (which expire in a matter of hours or days) for each communication and exchange the public keys of those keypairs though encrypted communications with the individual you'll be communicating with.

If you don't wish to have your key on a public keyserver, you should skip this step and instead email your public key to the keysigning party coordinator with a message stating that you don't want your key on a public keyserver. The coordinator can then extract your public key information and forward your key on to the other participants via encrypted e-mail, or some other method, along with a note stating that the key should be returned to its owner after signature rather than uploaded to a keyserver.

You may wish to post a key signing policy on the web. A key signing policy is a statement of what conditions you require to be met in order for you to be willing to sign a PGP key. It may or may not detail the requirements for different types of PGP signatures.

The purpose of posting a signing policy is two fold. First, a signing policy lets individuals who would like to have you sign their key gain an understanding of what they'll need to do in order to get that signature. the policy may detail what documents you require, what type of keys you'll sign, or even if you'll sign the PGP keys of people you do not have a long standing personal relationship with at all. Second, a signing policy can help others evaluate the quality of the signatures you have made on other's PGP keys.

Here is an example key signing policy for your reference.

Step 1: Get a copy of the key

Normally, you'll be working from a keyserver. However if you are signing the key that is not available on a keyserver, you can use simply import the key with gpg --import. If you are working with a keyserver, the following command will download the key from the keyserver into your public keyring.

bash$ gpg --keyserver <keyserver> --recv-keys <Key_ID>

If you get a read error, it means the keyserver is overloaded. Please, try again in a few seconds.

Step 2: Fingerprint and Verify the key

bash$ gpg --fingerprint <Key_ID>

GPG will print out the fingerprint of the Key with <Key_ID> (the key you just downloaded). Check the fingerprint against the checklist that you where given at the party. Note: Don't check the fingerprint on your checklist against the fingerprint on the web page as the server may not send you the same key it displays on the web page.

Step 3: Sign the key

bash$ gpg --sign-key <Key_ID>

If you have multiple private keys, you can specify which of your private keys to sign the other persons public key with like this:

bash$ gpg --default-key <Key_to_use> --sign-key <Key_ID>

If you have trouble dealing with RSA keys, you're probably using an old version of gnupg. Versions of GnuPG older that 1.0.3 do not include RSA support. Note: You may have to uninstall an older version if your distribution installed it with package management software. You can check the version you're executing like this:

bash$ gpg --version

Step 4: Return or Upload the signed key

If you are working with an entity which does not want their key on a public keyserver, you should at this point you should return their signed key back to them by their method of choice - normally encrypted email. You should not send a public key to a keyserver with out the permission of the key's owner. Publicizing a public key slightly reduces the security of a key pair, therefor it is considered rude to make a key more public than its owner desires.

Most likely you are working with a keyserver. If that is the case, you can send the signed key back to the keyserver like this:

bash$ gpg --keyserver <keyserver> --send-key <Key_ID>

You should see a success message like this:

gpg: success sending to `<keyserver>' (status=200)

Congratulations, the signature of the other entity's key is now complete and your signature has been incorporated into their public key. A trust path has been established.

The openPGP standard includes a spectrum of signature packet designations so that you can sign a public key and user ID pack with a variety of different levels of trust.

Typically, it is acceptable to use GnuPG's default signature type. However, the other types are available for use if you'd like to attempt to build a more granular and accurate web of trust with your key. For specific information on the usage of these different types of signatures, please see RFC4880.

Nothing gets people's interest peaked like colorful graphics. Therefor, graphing the web of trust in your local area as you build it can help motivate people to participate as well as giving everyone a clear sense of what's being accomplished as things progress.

You can very easily create a graph of all of the keys and signatures in your web of trust by converting that information into a dot file which can be fed into a graphing program like dot or neato. A perl script which converts the keys and signatures in a keyring to a file in the dot format was written by Darxus and is also available under the terms of the GPL. In order to graph the web of trust you'll need to download Darxus' sig2dot.pl script and the graphviz software from AT&T Research or Darxus' springgraph perl code, which can graph in 3D. You may not be able to graph a web of trust with more than a few hundred nodes due to the amount of memory needed to perform such an operation.

Instructions for graphing the web of trust in a gpg keyring are included in the sig2dot.pl script, or can be found on the Debian keyring graphing page. Again, here is a link to view a graph of a web of trust which was produced with the sig2dot.pl script and the neato graphing program. More information is available from the Debian keyring graphing page.

It is possible that you will be approached at the party or at some time through email or even an anonymous remailer system asking you to sign a PGP Key which is linked with a pseudononymous identity. Normally, most people consider the web of trust as the mathematical mechanism that validly links a meatspace identity with a cyberspace identity. However, this is only one possible use for the web of trust. What the web of trust was meant to do at it's most basic level is provide a reasonable assurance that the person you're in communication with is actually the person that you think you're in communication with. The web of trust is an identity authentication mechanism.

Identity can come in many different forms. People can have, as the great Framers did, pen names. People can represent corporations, or informal groups. People can even have a combined identity with others, such as is the case with married couples. People can even give computer programs an identity and establish identities, or brands, for completely virtual constructs like internet sites or ethereal events like conferences, coding parties, competitions, or meetings.

So, how can the web of trust be used to validate a key pair ownership with an identity that does not have a human meatspace equivalent? It can do so because linking a key pair with any identity con be done by simply communicating a shared secret through a channel secured by the key pair that is claimed to be linked with the identity claimed on the PGP Public key's user ID packet. Demonstration of knowledge of the secret is proof of possesion of the secret key, are therefor control of the keypair.

For a real world example, lets say that we have an individual who is planning on releasing a new linux distribution. He has secured the domain name grayhat.org to use for the new distribition which is to be called, Gray Hat Linux. But, he has no company or formal organization at this point. The developer would like to have a PGP key that he has generated to sign packages and security advisories integrated into the web of trust. However, this individual has managed to get many other people to work with him on the distribition and each take responsibility for some of the many different software packages. For this reason, he has created a role key with a user id packet that says: GrayHat Security <security@grayhat.org>. Let's also say that you do not know this individual. Therefor you have no way of knowing if he is actually authorized to represent the owner of the grayhat domain in this way.

The way to do some level of verification that this individual does have access to both the email address and the secret key of the key pair he is attempting to get validated would be to email a secret encrypted with the public key he has asked you to sign to the email address listed on that public key. If he is able to receive and decrypt that message and demonstrate that to you by demonstrating knowledge of your secret, you can assume that he is the rightful owner of the PGP Keypair and the identity and email address asserted by it.

While it is certainly possible that he could be a hacker that gained control of the grayhat.org server or its DNS record, that is not necessarily your concern. Your PGP signature says noting about how secure the grayhat.org domain is, only that you made some level of effort to verify that the individual that presented you with a public key to sign appeared to you to be in control, and there for the rightful owner, of both. Individuals considering the amount of trust that they can place in the GrayHat Security key pair that you signed, should consider in their calculations the fact that their existed no government nor corporate identification documents to back the assertion linking that individual and the cyberspace identity he asserted. They should also consider that the keypair may be shared among a group of developers and that the individual making asserting with the keypair may be someone who you, the signer, has never met.

It does not diminish the value of your key or the signatures you made if this key or the associated account turns out to have been compromised. Your signature does not give your condition and boundless endorsement of identity and validity. It just states that you did a verification with what you considered to be a due diligence process and felt sufficiently satisfied by that to sign the key. Trust is between the two individuals interacting at a given moment, it is ethereal. That said, should your due diligence have been long lacking and others encountering many inappropriate signatures made by your key, the value of your signatures will certainly suffer. For example, if you sign keys with out checking fingerprints, or sign keys with out making any attempt at verification.

Some effort has been made to better analyze the connections created in the web of trust. Because the signatures on keys can be thought of as links between the keys, some interesting analysis methods can be borrowed from graph theory. The keys become nodes in a graph, and the signatures become edges. When viewing a web of trust as a graph, it is possible to compute a number of different types of statistics on keys, such as their proximity to another key or their level of interconnectedness. One example of a program which calculates these types of figures is wotsap.

In the future, some more advanced analysis tools may become available. As we saw in the advanced signing section, features exist in the openPGP standard that allow signatories to sign keys with varying levels of trust. While wide spread analysis has not yet been done publicly on a web of trust that extensively used these type of signature packets, it is possible. In a graph visualization, this type of information on individual edges, or links, could be viewed as weights. By selecting keys as anchor nodes degrees of trust could be calculated for every node linked to the anchor nodes allowing a reputation system which ranked keys. Since the different types of openPGP certification signatures are not yet in wide spread use, I do not believe any program such as what I describe exists.

When your key expires, you have two options. You can either generate a new key, or you can extend the lifetime of your current key. The generation of a new key is the preferred and technically correct way to deal with this event.

It is best practice to generate a new key pair before the old key pair expired. Then, to use the old key pair to sign the new key pair there by linking it into the web of trust.

After doing that, the next step is to mail all of the people who signed your old key in the past requesting that they sign the new key. Upon receiving a note with a signature from a key that they explicitly trust, or with a signature from a key signed by a key that they explicitly trust, they should be willing to trust the new key enough to sign it.

There is nothing inherently wrong with extending the key's expiration date. But, I think that before some one does that they should themselves - "What has changed about the threat model that I now trust his key to be valid for a longer period of time than I did when I first generated it?" Historically, cryptographic algorithms, protocols, and systems have always gotten easier to break over time.

Additionally, it's beneficial to change keys every few years because if a key is ever compromised only the signatures for a limited amount of time are compromised. The compromise is limited to the amount of time that you had used that specific compromised key, rather than every signature that you've ever made.

Finally, if an attacker managed to get someone to sign an invalid key and every one expired their keys regularly, that key would eventually fall out of the currently unexpired web of trust.

If the key has expired before you have made the signature to extend the expiration date. There are no issues created by extending the date after the key has expired. The only possibility of concern is that an expired copy of your public key is still circulating out there. Perhaps, on another Key Server network. But, that shouldn't cause you any significant problems.

In regards to the key material itself:

In Version 3, the expiration date of the key is coded into the public key material. The self signature by the secret key on the public key material validates the expiration date. The OpenPGP standard does not allow for a public key to include multiple key expiration date packets. So, once someone receives the copy of your public key with the updated expiration date, no history of the old expiration date will have been maintained. But, You should no longer use a Version 3 key due to technical weaknesses in the design of PGP Version 3.

In Version 4, the expiration date of the key is coded into the a signature subpacket of the self signature made on the key. A signature contaning multiple signature expiration time subpackets is not valid. A correctly working OpenPGP compliant PGP implementation would respect the self signature with the latest creation time as authoritative. If you wanted to, you could delete the older self signature with GnuPG using the --edit-key command line option.

You may revoke a signature on another's key at any time.

A signature of the following type may be used to revoke a signature of any of the four types, 0x10 through 0x13, on another's user ID packet:

The certification revocation signature should be made by the same key that was used to create the signature that you wish to revoke. If that is not possible, an authorized revocation key may be used instead.

In the event that you suspect that your secret key has been compromised, you should revoke your public key immediately. Key revocation takes place by the addition of a Revocation Signature to a public key. The revocation of a key suggests that a key is no longer valid (secure) and should not be used. One a revocation certificate is issued, it cannot be withdrawn.

Since your PGP key is distributed (read circulated) to people rather than distributed from a central point every time it is accessed, you must circulate or distribute your revocation certificate in the same manner that you distributed your public key. The circulation of the revocation certificate in the same manner as the distribution of your public key would usually mean uploading the revocation certificate to the keyserver networks. If you had not uploaded your public key due to security considerations, you may still want to upload your revocation certificate to the keyserver. In this case you would be making a trade off between the slight reduction in security which results from having your public key publicly available, and the reduction in security which could occur from having someone potentially not realize that your key has been revoked.

In review, the gpg command to generate a revocation certificate is:

bash$ gpg --output revcert.asc --gen-revoke <key_id>

If you have an idea about how or when you key was compromised and you generated a revocation certificate during key generation, you will still likely want to generate a new revocation certificate to revoke your keypair. This is the case because the openPGP standard will allow you to specify the reason why you are revoking your keypair and even provide some free text comments about the reason for revocation. The circulation of a revocation certificate with this type of information is likely advantageous and preferable to the circulation of a generic certificate created during key generation.