SPKI/SDSI and the Web of Trust

[4 April 2001]

PGP certificates differ from X.509 certificates, as seen by the general public, in two ways:

PGP certificates are issued (signed) by normal people while the popular impression is that X.509 certificates must be issued by a professional CA, and
PGP implements a security fault tolerance mechanism, called the Web of Trust, that was designed to compensate for the fact that issuers were not specially protected or professional.

Because SPKI/SDSI, like PGP, advocates widely distributed issuance of certificates rather than have them all come from a central CA hierarchy, people sometimes claim that SPKI/SDSI uses the Web of Trust but that is not a proper use of terms. SPKI certificates have deterministic certificate chains, just like those of X.509 and unlike the PGP Web of Trust.

As it turns out, SPKI/SDSI does have the ability to provide a security fault tolerance mechanism, different from the Web of Trust, but that just complicates this discussion. Further complicating this discussion is the fact that X.509 certificates can be issued by any party, not just professional CAs, while professional CAs are free to issue PGP or SPKI certificates.

In spite of these similarities and gray areas, there are substantial differences among certificate types. The table below summarizes those actual differences.

**Comparison of Certificate Types**
Kind of Certificate	Certification Authority Characteristics	Kind of Identifier
X.509	Naming authority hierarchies; cross-certification; CPS	Global by original definition, but local in practice [X.500 Distinguished Name, chosen by and hopefully unique to the issuing CA]
PGP	Web of Trust = multiple path of certification, to achieve fault tolerance in compensation for the fact that amateur certifiers are signing certificates	Global [e-mail name, globally unique (thanks to the Domain Name System) but maybe not persistent]
SPKI/SDSI	Single naming authority; no CPS necessary	Local [arbitrary]
SPKI without names	Authorization authority hierarchies; optional k-of-n subjects	Global [public key or hash of the public key, globally unique (thanks to mathematics) and persistent]

X.509

The assumption here is that a certificate binds a key to a person. That person is identified by a globally unique and globally meaningful name, according to the original X.500 work. However, X.500 achieved that global uniqueness by having a single directory root. That assumption is built into how the certificates are constructed and used. Unfortunately, the single directory root assumption is not valid and probably never will be. Therefore, the identifiers used (Distinguished Names {DNs}) are local names.

The CA hierarchy is designed to bind these assumed global names to keys. The CPS (Certification Practices Statement) is designed, in part, to show to the relying party what quality of job that CA does. [The CPS has evolved to a document that spends a sizable fraction of its content spelling out why it is not the fault of the CA when the relying party's expectations are not met and to many people, that is the only apparent function of the CPS.]

The original design, from X.500, was for a single global naming root. Under the early PEM work, a single certification root was also assumed. In reality, either single root is politically impossible. To accommodate the inevitable multiple certification roots, cross-certification in a variety of forms is being developed. It is not clear how those in favor of cross-certification will resolve the lack of a common naming root when two ID hierarchies are linked by cross-certification. Those two hierarchies could have issued identical names to different keys, belonging to different keyholders.

The assumption behind X.509 (inherited from X.500) is that the global identifier [DN] is somehow inherently bound to a person and that everyone who might use the certificate will correctly map from that name to the named person or from the named person to the name. The probability of error in performing this mapping affects the system wide probability of error, alongside any cryptographic errors. It needs to be extremely small in order not to overwhelm the cryptography used and become the dominant source of error.

[We observe that it is very hard to do this mapping from name to person when one has a large domain of named people. It is even harder to do the mapping from person to name. Failures in either name mapping are likely to dominate the probability of security error in any system using such names as part of a security decision. Specifically, Carol the CA assigns some constructed name to Bob. Alice is then expected to look at that name and understand which Bob is being named, without any prior communication with either Carol or Bob on this topic. (That usage of names was inherited from the original paper on public key cryptography, Diffie and Hellman, "New Directions in Cryptography", 1976.) We already know that with e-mail names, people often make incorrect guesses about the linkage between name and person and, as a result, e-mail goes to the wrong person. There is no reason to believe that this association between name and person will be any more accurate with X.500 Distinguished Names. In fact, since Microsoft Outlook (Exchange) uses X.500 Distinguished Names for e-mail and we have seen a high percentage of mistakes in mail addressing under Outlook/Exchange (in domains of as few as 50,000 people), there is reason to believe that the DN yields at least as high an error rate as any other e-mail name, and possibly a significantly higher rate. Full scientific studies of those rates have yet to be done, however.]

PKIX vs. X.509

Phillip Hallam-Baker <hallam@ai.mit.edu> wrote to the SPKI list on Fri, 1 Sep 2000 10:37:09 -0400 in comment on the above:

``PKIX usage is not identical to the X.509 concept.

``In particular the actual usage of PKIX certs is that the X.500 distinguished name is in practice only really useful as an internal name. There being no actual X.500 name space and no applications routing messages on the name[,] the end entities tend to use the DN as a private name.

``The name that does get used is the SubjectAltName which does refer to a global namespace - the DNS system. Incidentally the fact that DNS exists shows that it is not politically impossible for a single entity to control a uniform namespace. What the DNS/X.500 situation does show is that it is not possible for there to be two uniform global namespaces.''

[DNS does show that it is possible to make a global name system, where X.500 failed to do that, but the intense political debates experienced by IETF TLD efforts and then ICANN suggests that DNS may have succeeded only because it was designed and implemented before larger political forces became aware of it or of its importance.]

PGP

The assumption here is that a certificate binds a key to a person. That person is identified by a name chosen by the keyholder himself, called the UserID. These names are assumed to be globally unique and meaningful, by including both a common name and an e-mail name in the key's UserID. The e-mail name provides global uniqueness and some measure of meaningfulness. Nothing insures honesty on the part of the keyholder in choosing his UserID. One must look instead at who besides the keyholder himself signed (attested to) that claimed binding and how many such people have made that attestation, in order to decide how reliable that choice of UserID might be.

Certificates are not issued by CAs that have strict business rules, documented in some CPS. Rather, certificates are issued by normal people who are probably more fallible than one would expect a professional CA to be. To make these certified bindings more reliable, PGP incorporates a security fault tolerance feature called the Web of Trust. Under the Web of Trust, multiple different keyholders sign each certificate (each binding between UserID and key), attesting to the validity of that binding. The assumption is that these different keyholders are independent so that even if one of them makes a bad judgment, they won't all do so. It is also assumed that no false binding will have more than the specified web of trust number of signatures.

In reality, people rarely understand or use the Web of Trust. However, it has the interesting design feature that the verifier (what X.509 calls the Relying Party) sets the level of trust in keys -- and can in principle demand some number of independent signatures on a PGP certificate before that binding is considered valid.

Working against this theory of operation is the fact that we can not prove independence of keys, since we have no means of determining whether two different private keys are controlled by the same one person. The relying party has the opportunity to enforce that independence by assigning trust only to one key per person and only to people who treat certificate signing responsibly, but there is nothing to force a PGP user to go to that trouble.

SPKI/SDSI ID Certificate

The assumption here is that a certificate's ID binds a key to a keyholder or group of keyholders. A keyholder is identified by an arbitrary local name, meaningful only to the issuer of the certificate. It is explicitly stated in the SPKI/SDSI literature that others must not assume any binding between the local identifier and a particular person, based on the spelling of that name. If I have a friend named Sheri and want to give her the ID Phred, that's my choice.

This definition of name means that the issuer of the certificate is the sole authority on name binding. No other entity is in a position to question that assignment or binding. Therefore, no CPS is needed. An issuer can not fail to do a perfect job at all times, because that issuer is the only entity qualified to render an opinion on the quality of the name assignment.

Parties other than the certificate issuer identify keyholders by their keys. The ID certificate is defined strictly for the convenience of the issuer, either as a nickname for some keyholder or to define named groups of keyholders. The local name is made useful to others by being converted to a global name of the form: (name <key> <ID>).

SPKI without names

The original SPKI certificate, before the merger with SDSI, identified keyholders only by public key (or hash of the public key). Even after the merger, authorization certificates still bind authorizations directly to public keys (as opposed to attribute certificates that bind authorizations to names).

A public key (or its hash, if hashes are collision free) is a globally unique identifier of the private key. If proper key security is in place, as we must assume in all certification systems, then the private key is associated with exactly one keyholder. The public key or its hash is therefore a globally unique identifier of that keyholder.

[Should some system design have keys held in common by groups of keyholders, then the public key is an identifier of that group without the possibility of more explicit identification. One might use such keys in order to achieve anonymity, for example.]

SPKI/SDSI k-of-n Subjects

As the design of SPKI/SDSI matured, the concept of k-of-n (threshold) subject was added. A k-of-n subject is a list of n subjects (keys, names or other k-of-n constructs) together with the values of k and n, such that the verifier needs k complete paths between this certificate (or ACL entry) and some eventual subject. This provides a fault tolerance like PGP's Web of Trust, but with one significant difference. In SPKI/SDSI, the issuer of a certificate or the editor of an ACL decides what level of fault tolerance is required. That party also selects keys known in advance and therefore may be in a position to insure that these keys are controlled by different keyholders.

Carl Ellison; cme@acm.org