How to certify public keys without a central authority
William Stallings
PGP (Pretty Good Privacy) is a widely used E-mail security package that relies heavily on public-key encryption (see ``Pretty Good Privacy,'' July 1994 BYTE). Use of PGP involves two keys--a private key known only to one user, and a corresponding public key made known to all users. With these two keys, it is possible to create digital signatures that guarantee the authenticity of a message and to encrypt a message so that only the intended recipient can read it.
Each user guards his or her private key and publishes the corresponding public key. Unfortunately, an impostor can generate a public/private key pair and disseminate the public key as if it were someone else's.
Suppose Alice wants to send a secure message to Bob. Meanwhile, Darth creates a public/private key pair, attaches to it Bob's name and an E-mail address that Darth can access, and disseminates the public key. Alice acquires this key, uses it to prepare her message for Bob, and sends it to the attached E-mail address. Result: Darth receives and can decrypt the message, and Bob never receives the message (which he wouldn't be able to read anyway, lacking the required private key).
One solution is to insist on the secure exchange of public keys. Users can, for example, store keys on disks and pass them from hand to hand or send them via snail mail. But for PGP to be more widely useful, it should be possible for people to exchange keys electronically with others whom they have never met and may not even know.
Public-Key Certificates
The tool that enables widespread use of PGP is the public-key certificate. The following items are essential ingredients of a public-key certific
ate:
-- The public key itself
-- A User ID, which includes the name and E-mail address of the owner of the key
-- One or more digital signatures for the public key and User ID
A signature testifies that the User ID associated with this public key is valid. It is formed using the private key of the signer. Anyone in possession of the corresponding public key can verify that the signature is valid. If any change is made to either the public key or the User ID, the signature will no longer compute as valid.
How do you manage public-key certificates? One approach, used in the PEM (Privacy Enhanced Mail) scheme, relies on a central certifying authority. Each user must register with the central authority and engage in a secure exchange, which involves independent techniques for verifying user identity. Once the central authority is convinced of the identity of a key holder, it signs that key. If everyone who uses this scheme trusts the central authority, then a key signed by the a
uthority is automatically accepted as valid.
PGP could take this approach, but that would violate its spirit as an E-mail security scheme for the masses. So PGP instead supports a ``web of trust,'' in which individuals sign each other's keys and create an interconnected community of public-key users. Here's how it might work. Suppose Bob physically passes his public key to Alice, who signs it. Alice keeps a copy of the signed key and also returns a copy to Bob. When Bob wants to communicate with Carol, he sends her his public key, with Alice's signature attached. Carol, who has Alice's public key and who trusts Alice to certify other people's keys, need only verify Alice's signature on Bob's key to accept his key as valid.
Computation of Trust
PGP does not specify a policy for establishing trust. It does provide mechanisms for associating trust with public keys and for using trust information. Each user collects signed keys and stores these in a PGP file known as a public-
key ring. Each entry in the ring has a key legitimacy field--computed by PGP--that measures the degree to which this PGP user trusts that the key is valid for its user. The higher the level of trust, the stronger is the binding of this user ID to this key. For each signature collected by the PGP user, there is a signature trust field that measures how far the PGP user trusts the signer to certify public keys. (The key legitimacy field for an entry derives from the signature trust fields.) Finally, there is the public key itself, associated with an owner, and an owner trust field that indicates the degree to which this PGP user trusts the key's owner to sign other public-key certificates. PGP doesn't compute this level of trust; the PGP user assigns it. You can think of a signature trust field as a cached copy of the owner trust field from another entry.
Periodically, PGP processes the public-key ring to achieve consistency. For each owner trust field, PGP scans the ring for all signatures authored by t
hat owner and updates the signature trust field to equal the owner trust field. This process starts with keys for which there is ultimate trust. Then, all key legitimacy fields are computed on the basis of the attached signatures. The figure ``PGP Trust Model'' shows how signature trust and key legitimacy are related. In this sample public-key ring, a PGP user has acquired a number of public keys, some directly from their owners and some from a third party, such as a key server. The root node, labeled ``You,'' denotes the entry in the public-key ring corresponding to this PGP user. This key is valid, and the owner trust value is ultimate trust. Moreover, this user will always trust users D, E, F, and L to sign other keys and will partially trust users A and B to sign other keys.
Note that all keys whose owners are fully or partially trusted by the user have been signed by this user, with the exception of node L. Such a user signature isn't always necessary, as the presence of node L indicates, but in p
ractice most users are likely to sign the keys for most owners that they trust. So, for example, even though E's key is already signed by trusted introducer F, the user chose to sign E's key directly.
Two partially trusted signatures may be sufficient to certify a key. Here the key for user H is deemed valid by PGP because it is signed by A and B, both of whom are partially trusted.
A user may deem a key valid (because one fully trusted or two partially trusted people have signed it) but still not trust its owner to sign other keys. For example, N's key is valid because E, whom this user trusts, signed it, but the user hasn't assigned N the trust value to sign other keys. Therefore, although N signed R's key, PGP doesn't consider R's key valid. This situation makes perfect sense. You can send a secret message to someone you don't trust; all you need is the correct public key for that individual.
The figure also shows a detached orphan node S, with two unknown signatures. Such a key may ha
ve been acquired from a key server. PGP cannot assume that this key is valid simply because it came from a reputable server. The user must declare the key valid by signing it or by telling PGP that it is willing to fully trust one of the key's signers.
It is the PGP web of trust that makes it practical as a universal E-mail security utility. Any group, no matter how informal and how dispersed, can build up the web of trust needed for secure communications.
PGP Trust Model
illustration_link (33 Kbytes)
William Stallings is an independent consultant and a frequent contributor to BYTE. He is the author of over a dozen books on data communication and computer topics, including Network and Internetwork Security (Prentice Hall, 1995). This article is based on material from his most recent book, Protect Your Privacy: A Guide for PGP Users (Prentice Hall, 1995). You ca
n contact him on the Internet at
stallings@acm.org
or on BIX c/o ``editors.''
The PGP Web of Trust
