Protocols for Public Key Systems

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 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 then exchange public keys. . .

. . . 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!