Distribution of Public Keys

DISTRIBUTION OF PUBLIC KEYS

Several techniques have been proposed for the distribution of public keys. Virtually all these proposals can be grouped into the following general schemes:

•                           Public announcement

•                           Publicly available directory

•                           Public-key authority

•                           Public-key certificates

Public Announcement of Public Keys

On the face of it, the point of public-key encryption is that the public key is public. Thus, if there is some broadly accepted public-key algorithm, such as RSA, any par- ticipant can send his or her public key to any other participant or broadcast the key to the community at large (Figure 14.9). For example, because of the growing pop- ularity of PGP (pretty good privacy, discussed in Chapter 18), which makes use of RSA, many PGP users have adopted the practice of appending their public key to messages that they send to public forums, such as USENET newsgroups and Internet mailing lists.

Although this approach is convenient, it has a major weakness. Anyone can forge such a public announcement. That is, some user could pretend to be user A and send a public key to another participant or broadcast such a public key. Until such time as user A discovers the forgery and alerts other participants, the forger is able to read all encrypted messages intended for A and can use the forged keys for authentication (see Figure 9.3).

Publicly Available Directory

A greater degree of security can be achieved by maintaining a publicly available dynamic directory of public keys. Maintenance and distribution of the public direc- tory would have to be the responsibility of some trusted entity or organization (Figure 14.10). Such a scheme would include the following elements:

1.                        The authority maintains a directory with a {name, public key} entry for each participant.

2.                        Each participant registers a public key with the directory authority. Registration would have to be in person or by some form of secure authenti- cated communication.

3.                        A participant may replace the existing key with a new one at any time, either because of the desire to replace a public key that has already been used for a large amount of data, or because the corresponding private key has been com- promised in some way.

4.                                       Participants could also access the directory electronically. For this purpose, secure, authenticated communication from the authority to the participant is mandatory.

This scheme is clearly more secure than individual public announcements but still has vulnerabilities. If an adversary succeeds in obtaining or computing the private key of the directory authority, the adversary could authoritatively pass out counterfeit public keys and subsequently impersonate any participant and eaves- drop on messages sent to any participant. Another way to achieve the same end is for the adversary to tamper with the records kept by the authority.

Public-Key Authority

Stronger security for public-key distribution can be achieved by providing tighter control over the distribution of public keys from the directory. A typical scenario is illustrated in Figure 14.11, which is based on a figure in [POPE79]. As before, the scenario assumes that a central authority maintains a dynamic directory of public keys of all participants. In addition, each participant reliably knows a public key for the authority, with only the authority knowing the corresponding private key. The following steps (matched by number to Figure 14.11) occur.

1.                                       A sends a timestamped message to the public-key authority containing a request for the current public key of B.

2.                                       The authority responds with a message that is encrypted using the authority’s pri- vate key, PRauth.Thus,A is able to decrypt the message using the authority’s pub- lic key.Therefore,A is assured that the message originated with the authority.The message includes the following:

•                                 B’s public key, PUb, which A can use to encrypt messages destined for  B

•                                 The original request used to enable A to match this response with the cor- responding earlier request and to verify that the original request was not altered before reception by the authority

•                               The original timestamp given so A can determine that this is not an old mes- sage from the authority containing a key other than B’s current public key

3.                                     A stores B’s public key and also uses it to encrypt a message to B containing an identifier of A (IDA) and a nonce (N1), which is used to identify this transaction uniquely.

4, 5. B retrieves A’s public key from the authority in the same manner as A retrieved B’s public key.

At this point, public keys have been securely delivered to A and B, and they may begin their protected exchange. However, two additional steps are desirable:

6.       B sends a message to A encrypted with PUa and containing A’s nonce (N₁) as well as  a  new  nonce generated  by B (N₂). Because  only  B  could have decrypted message (3), the presence of N₁ in message (6) assures A that the correspondent is B.

6.                                     A returns N2, which is encrypted using B’s public key, to assure B that its cor- respondent is A.

Thus, a total of seven messages are required. However, the initial four mes- sages need be used only infrequently because both A and B can save the other’s public key for future use—a technique known as caching. Periodically, a user should request fresh copies of the public keys of its correspondents to ensure currency.

Public-Key Certificates

The scenario of Figure 14.11 is attractive, yet it has some drawbacks. The public-key authority could be somewhat of a bottleneck in the system, for a user must appeal to the authority for a public key for every other user that it wishes to contact. As before, the directory of names and public keys maintained by the authority is vul- nerable to tampering.

An alternative approach, first suggested by Kohnfelder [KOHN78], is to use certificates that can be used by participants to exchange keys without contacting a public-key authority, in a way that is as reliable as if the keys were obtained directly from a public-key authority. In essence, a certificate consists of a public key, an identifier of the key owner, and the whole block signed by a trusted third party. Typically, the third party is a certificate authority, such as a government agency or a financial institution, that is trusted by the user community. A user can present his or her public key to the authority in a secure manner and obtain a cer- tificate. The user can then publish the certificate. Anyone needing this user’s pub- lic key can obtain the certificate and verify that it is valid by way of the attached trusted signature. A participant can also convey its key information to another by transmitting its certificate. Other participants can verify that the certificate was created by the authority. We can place the following requirements on this scheme:

1.                                       Any participant can read a certificate to determine the name and public key of the certificate’s owner.

2.                                       Any participant can verify that the certificate originated from the certificate authority and is not counterfeit.

3.                                       Only the certificate authority can create and update certificates.

These requirements are satisfied by the original proposal in [KOHN78]. Denning [DENN83] added the following additional requirement:

4.                                       Any participant can verify the currency of the certificate.

A certificate scheme is illustrated in Figure 14.12. Each participant applies to the certificate authority, supplying a public key and requesting a certificate.

Application must be in person or by some form of secure authenticated communi- cation. For participant A, the authority provides a certificate of the form

CA = E(PRauth, [T || IDA || PUa])

where PRauth is the private key used by the authority and T is a timestamp. A may then pass this certificate on to any other participant, who reads and verifies the cer- tificate as follows:

D(PUauth, CA)  = D(PUauth, E(PRauth, [T || IDA || PUa]))  = (T || IDA || PUa)

The recipient uses the authority’s public key, PUauth, to decrypt the certifi- cate. Because the certificate is readable only using the authority’s public key, this verifies that the certificate came from the certificate authority. The elements IDA and PUa provide the recipient with the name and public key of the certificate’s holder. The timestamp T validates the currency of the certificate. The timestamp counters the following scenario. A’s private key is learned by an adversary. A gen- erates a new private/public key pair and applies to the certificate authority for a new certificate. Meanwhile, the adversary replays the old certificate to B. If B then encrypts messages using the compromised old public key, the adversary can read those messages.

In this context, the compromise of a private key is comparable to the loss of a credit card. The owner cancels the credit card number but is at risk until all possible communicants are aware that the old credit card is obsolete. Thus, the timestamp serves as something like an expiration date. If a certificate is sufficiently old, it is assumed to be expired.

One scheme has become universally accepted for formatting public-key cer- tificates: the X.509 standard. X.509 certificates are used in most network security applications, including IP security, transport layer security (TLS), and S/MIME, all of which are discussed in Part Five. X.509 is examined in detail in the next section.