Web of Trust and Key signing protocol

Introduction

There are many HOWTOs about how to set up key signing, and even more about the benefits of signing keys. Since the mighty Google knows all, what is the point of yet another document on this? Well, I have been following this protocol for several years now, and while this is a little more involved than the norm, it does tend to ad value to my signature: if you see a key signed by me, you can be assured that I have followed the process outlined below, and have some assurance that some basic sanity checks were followed before my signature was attached.

This is not to say that my process is infallible; it is certainly possible to hoodwink me. While I like to think I raise the bar for identity assurance, this is by no means a substitute for a background check :-). So what does following this process buy one? It allows a potential key-signer be reasonably assured that owners of the key being signed are who they claim to be, and that they control the corresponding private key, and that they are able to receives email from the email addresses in the ids that shall be signed. .

Weaknesses

The key could be compromised, and no one aware of it. I try and not sign keys whose owners practice poor key management policies (that I become aware of). I have been forced to drop the rule about not signing keys that live on networked boxes; apparently, if I did not, I would effectively be excluding myself from the web of trust.
The identifications could be faked. While I do try to follow the dictates of common sense when it comes to examining official identification documents, I am not an expert (by a very, very long shot) at identifying forgeries, and would not know what official passports from most countries even look like, or drivers license, etc, so I can certainly be fooled. However, it does raise the bar a trifle ...

Protocol

Suppose Alice and Bob are at a key signing meeting, and they want to get their keys signed to extend the Web of trust. They are conscientious folks who would like to not introduce a flaw in the web of trust (and they care about their key-signing reputation as well).

Preliminary Steps

Everyone comes to the meeting with 2 picture ID's, at least one of which is issued by the government.
Everyone comes with lots and lots of slips of paper containing their name, email address, and key fingerprint of a key available on a public server. The name on the slip must match the name on the picture ID's.
Everyone has a sheet of paper, and a pen.

Identity checks

Alice and Bob look at each others picture ID (assuming they want to sign the other person's key: if Alice does not intend to sign Bob's key, she can skip this step). They make sure that the names on the ID's match the names on the key.

Process

Alice thinks up of an arbitrary word (call it Secret A), and writes it on one of the slips of paper (which already has her name on it), and makes a note of it in her sheet.
If Bob wants his key signed by Alice, he does the same, creating Secret B.
If Alice is signing Bob's key, She asks Bob for a random word (secret B, which he has created before, or makes up on the spot), and writes it down on the slip of paper, and makes a note of it on her sheet, along with a reminder that the secrets A and B are to be associated with Bob. So, if both Alice and Bob are signing each others keys, they have two parts of a shared secret; if only one of them is signing a key, then a single shared secret suffices.
Alice then hands bob the slip of paper. At this point, both Alice and Bob have shared secret(s), and they each know which person these secrets are associated with.
If Bob wants his key signed as well, he hands over his slip of paper to Alice, also with the same secrets A and B.
(In some organized key signing parties, the organizers provide pre-printed sheets of paper with every participants name and key details. In that case, every participant must publicly speak out their key fingerprints aloud, so that all participants ensure that the pre-printed sheet is accurate).
Alice and Bob check that the slip(s) of paper (and Alice's sheet) have the proper names, and these names match the ID's they just examined.
Alice (and Bob) repeats this process with all other participants. This is generally where the meeting ends.
Bob, at home, then downloads Alice's public key from the key servers (this reduces the chances of being handed a fake local key, since many eyes, presumably, shall be on the keys on public key servers) -- or a physical copy on a floppy, or whatever.
(If Alice is signing Bob's key, she does the same).
Bob then checks to make sure that the fingerprint of the key downloaded matches Alice's information on the slip. Bob also makes sure that the other details (email addresses, etc) also match.(Alice does the same, if she is signing Bob's key).
Bob then looks at each ID Alice has on her key, and for each such ID (assuming she has n ID's on her key), he generates a new secret (call it secrets B₁, B₂, ... B_n). He sends an encrypted email to each of the email addresses associated with Alice's key.
If Bob is getting his key signed by Alice as well, and they have negotiated a second secret (secret B), he adds that shared secret to all the mail messages. This allows Alice to check that Bob knows part of the shared secret as well.
In each message, Bob also includes one of the newly created numbers (Secret B₁, B₂, ... B_n). So, Bob sends Alice n emails.
On getting Bob's emails, Alice decrypts¹ it, looks up the other part of the shared secret she shared with Bob (Secret A)², and sends an encrypted message back to Bob containing secrets B, and as many of the secrets B₁, B₂, ... B_n that made it through³.
If Alice is also signing Bob's key, she should also generate a set of new secrets, one for each ID on Bob's key. Say Bob has m ID's on his key. Call these newly generated secrets A₁, A₂, ... A_m. She sends these m emails to Bob. (Actually, Alice could send these messages without waiting for Bob's email).
On getting Alice's first email, Bob decrypts it, checks to ensure that it contains the other half of the shared secret (Secret A), and that it is signed by Alice's key. So now Bob knows that:
1. Alice controls her secret key,
2. Alice knows the secret they exchanged in person after checking ID's, and
3. Alice controls that email address.
Bob can now sign Alice's key. After doing so, Bob emails the signed key to Alice, and uploads it to the public key servers.
One getting the m emails from Alice, Bob just needs to send an email back with as many of the secrets A₁, A₂, ... A_m as got through, along with the shared secrets A and B for good measure.
When Alice gets this final response from Bob, she knows that Bob:
- controls his secret key,
- is present at that address, and
- knows the secret Alice gave in person after checking ID's.
Alice can now sign Bob's key, and upload it to the key servers as well.

Conclusion

There are potentially four sets of secrets involved, two exchanged in the face to face meeting, a third set created in the first email (the number here depends on how may ID's are present on the key being signed), and potentially a fourth set created in the acknowledgment (again, number depends on the number of ID's on the other key). This is anal retentive (not a bad thing in security, really), but it ensures (to a reasonable degree) that the person whose ID you checked does indeed control the email address, and can indeed use the private key corresponding to the public key you are signing.

This may be more work than is generally done, but is more secure than most ad hoc key signing sessions I have attended ;-). I generally ask for two forms of ID, but even that is not perfect (nothing is). And I have been known to sign keys even when the owner did not have a second picture ID. I should also mention that I have never actually participated in a key signing where all these secrets were actually required; I have generally just used Secrets A and B₁, B₂, ... B_n.

Manoj Srivastava <srivasta@debian.org>