Protocols for Public Key Systems

PGP Lock

An issue arises with standard cryptography regarding key exchange. Imagine: Two people who cannot meet wish to encrypt a communication. With 'symmetrical' cryptography this cannot be done as they must first agree a key with which they can encrypt their data.

They must agree a key securely, i.e. without eavesdroppers, if their message is to be secure. If they can do this then surely they don't need to use cryptography in the first place!

There are two solutions to this which I am aware of, one is quantum cryptography and the other is public key cryptography. Here we'll discuss the latter.

A public key system addresses this issue by using two keys.

These keys are the public and the private key. The public key is published widely.

The public key can be used by anyone to "lock up" the message, but it will not decode the message - only the private key will do that, and of course, the private key is kept just that - private. (Unless one is using Key escrow!)

There are many ways to produce such a key pair, sufficed to say that the detailed method is not important when discussing how the keys are used. Functions which could be used in this way are called 'trapdoor' functions, as they are easy to use in one direction (e.g. from the private key to calculate the public key) but hard to use in the other.

Let's talk about Alice, Bob and Carol, the cryptographer's stooges. Alice and Bob wish to establish secure communications without having met each other, but Carol is trying to listen in. Can they talk securely?

In a single key system Alice and Bob first have to agree on a key. Carol will simply record the key it is exchanged, and thereafter be able to decode all messages with ease. Clearly this will not be sufficient if the correspondants cannot meet.

Can a public key system solve this dilemma? In the present form the answer is NO. This is not immediately transparent and so I will work through it with you.

Alice and Bob make their keys

Alice and Bob both generate a key pair, public and private key. The private key is not revealed, but the public key (shown) is made available for distribution.

Remember, at no point do either disclose their private key.

Alice and Bob exchange keys

Alice and Bob then exchange public keys. . .

Carol takes a Copy

. . . and of course, Carol takes a copy of each key.


Surely this is secure? These are public keys remember - they can only be used to encipher information - they cannot be used to decipher the information - only the private key can do that.

Carol cannot read the traffic . . . but have we missed something?

Predictably, Yes we have.

What if Carol is in a position where she can intercept and replace the communication, i.e. what if Carol is, for example, an internet service provider - where all email goes en route through her machine? Then we have a problem.

Carol can replace the keys.

If Carol is in a position where the email goes through her machine then when Alice sends her public key to Bob, Carol could substitute her own key which claims to belong to Alice. Similarly, when Bob sends his key to Alice then Carol simply substitutes a fake "Bob key".

The situation now is that Alice has her real key pair, and a key which she believes belongs to Bob. Bob has his key pair, and a fake Alice key. Carol has the real public keys for Alice and Bob, the fake public keys for Alice and Bob, and also the private keys which correspond to the fake keys.

What happens now when Alice sends a message to Bob?

Well, Alice composes and codes her message as usual. Except now she code it with the faked key which Carol slipped to her. Alice then sends the message. Carol can set up software to automatically intercept the email from Alice, and decrypt it - remember she possesses a private key which corresponds to the fake public key of Bob's.

Having read the message, Carol can the re-encipher the message using Bob's real public key and forward the message to Bob as usual. Thus Alice and Bob think they're having a secure conversation, yet in reality Carol is listening in - and she doesn't have the real private keys for either Bob or Alice!

Plugging the Loophole

As we have seen, the main weakness in a public key system is this:
How do I know that this key really belongs to my correspondant?

Protocols have been derived to answer this question. Let's examine several examples.

The most trivial case is the one where the correspondants have had an opportunity to meet, and they've handed over a copy of their keys on floppy disk. They can each be sure that the keys belong to the other person. Obviously, if it is possible to do this then it is surely a good method of knowing that a key may be trusted, however, it is not always practical - otherwise why use Public Key?

This may strike you as being rather cumbersome. It is. This is why key fingerprints were devised. The fingerprint is analagous to a human fingerprint - it's extremely unlikely that two keys will share the same fingerprint.

If Alice and Bob meet then they can exchange key fingerprints, these may be handily printed onto a slip of paper or business card and carried on the person. When Alice and Bob get back home they can simply compare the fingerprint on the piece of paper with the fingerprint of the key under suspicion. Carol's fake keys will bear a different fingerprint, and hence will not be used by Alice or Bob. The fake keys are revealed for what they are.

Of course, if Alice and Bob know each other well enough to talk to over the telephone, then the fingerprint may be read out over the phone.

What if Alice and Bob have never met, and are never likely to meet? This is where key signatures come in.

If you have personally verified that a given key belongs to a given person, then it is common practice to sign that key. The signature is made with your private key - so only you can make the signature - your signature may be verified by anybody, comparing the signature with your public key.

Now suppose Alice and Bob have a mutual friend, David. David has signed both Alice's key and Bob's key, and both Alice and Bob have a verified copy of David's key.

When Bob examines Alice's key he observes that her key was signed by David, Bob trusts that David is reliable when it comes to signing other people's keys. Therefore Bob can be fairly certain that the key belongs to Alice.

The thing with PGP in particular is that YOU decide who is trustworthy when it comes to keysigning.

For instance, it could be that David signs any old key without really verifying the key (as described above) - or it could be that David's private key doesn't belong to David at all. In these cases you'd mark David's key as being "untrustworthy" and his signature would carry no weight.

In this way, by verifying and signing keys wherever possible a "web of trust" may be built up. With trusted keys vouching for new keys. Of course, the weak point is now that person who signs a key without justification - this is why PGP is configurable to allow the user to say how much they trust a key's owner to sign other keys, how many valid signatures are required for a valid key, etc.

Remember, when someone signs a key they are not saying "I believe that this person is a good and trustworthy soul", they are simply saying "I have good evidence that this key belongs to the person whose name is attached to the key".

So if you cannot get any signatures, don't take it as a personal snub, simply supply better evidence as to your identity!