PGP Key-signing and CA fire-and-forget

Someone at work used to have a kernel.org account but recently needed to re-establish the presense in the web of trust by getting his PGP key signed, so we met and exchanged our key IDs and fingerprints, to mutually sign our keys. I earlier attended a key-signing party and my key has been signed by many other people, and it was a good place to bootstrap his key.

A PGP key has two parts; the public part that you give to others, and the private part that you keep to yourself. The easiest and most common way to distribute public part of the key is to upload it to public keyservers, where other people can find and retrieve your key by specifying the key ID, your name or e-mail address.

When other people want to send a message to you and preserve the secrecy of the message, they only need to use the public part of your key to encrypt the message for you, and PGP guarantees that the encrypted message can be decrypted and read only by whoever holds the corresponding private part of the key unless a complex math problem that is believed to be practically unsolvable can somehow be solved (in other words, "public crypto-system gets broken"). When you want to prove that a message was written by you, you use the private part of your key to electronically sign the message and make the result public, others can check the authenticity of the electronic signature by using only the public part of your key, and again PGP guarantees that the message couldn't have been signed by a person who does not have the private part of the key.

The public part of your PGP key records your name and e-mail address, among other things. It can and often does record more than one pair of name and e-mail (e.g. work address vs personal address). Anybody can generate a PGP key on his or her own and record any name and e-mail address in its public part. If you see a message signed with a PGP key whose public part records my name and address, unless you somehow know that it indeed is the key I created for me and whose private part I have, such a signature has no value. It may have been created by a random person inpersonating me.
If you encrypt a message you want to show only to me, using a random PGP key that records my name and e-mail address to encrypt it would not guarantee that only I would be able to read it, unless you somehow know that the key belongs to me.

Hence, people need a way to validate the authenticity of public keys. People can add electronic signatures to the public part of a PGP key that belongs to another person, vouching that the signer knows the key belongs to the signee. This signature can be made per name and e-mail pair recorded in the public part of the key.

If you see a signature on an unknown public key, signed by public keys that you know belong to people you trust, you can be as sure as you trust these signers that the unknown publiic key belongs to the person it claims to belong to. This "web of trust" extends recursively and I heard that a recent study indicates that all people in the world are connected by 4.74 hops on average.

The only facts I learned when I met the other person for the purpose of key-signing are:

• The person looked like his photo in our employee directory, and possessed a photo ID that matches his name;
• The achievements by the person described in our employee directory matched what the person I was supposed to be meeting who worked in the Linux kernel project had done; and
• The person claimed that a public key belonged to him, and gave me a way to retrieve the public part of this key.

It is not directly the above that I am vouching for by signing the public part of his key, however. I am vouching for the fact that I somehow know that the public key belongs to the person who is in control of the name and e-mail address pair recorded therein. That is not something I checked by meeting the person and chatting with him. I only checked the "name" part, but not the "e-mail address" part.

CA fire-and-forget is a clever scheme to solve this last bit of the problem. Instead of signing the public part of the key for all the name and e-mail pairs and upload the result myself, I make N separate signatures on his public key, one for each pair of name and e-mail address recorded in it. And then I encrypt these N signatures with his public key and send them to the corresponding e-mail addresses. The recipient of these encrypted signatures then decrypt them and upload the result to the public keyservers to complete the cycle.

If the e-mail address belonged to somebody else who does not have the corresponding private part, the encrypted signature would not reach the intended recipient, and the signature would not be decrypted to be uploaded to the public keyservers. I'll see my signature only if the person sitting behind the e-mail address has the private key that corresponds to the public part I have signed.

It is a clever scheme, even though it is a bit cumbersome to use, even with the use of dedicated tools (caff found in signing-party package on some distributions).