SPKI Certificate Theory Carl M. Ellison INTERNET-DRAFT CyberCash, Inc. Expires: 26 May 1998 Bill Frantz Electric Communities Butler Lampson Microsoft Ron Rivest MIT Laboratory for Computer Science Brian M. Thomas Southwestern Bell Tatu Ylonen SSH 21 November 1997 SPKI Certificate Theory ---- ----------- ------ Status of This Document This document is one of three, superseding the draft filed under the name draft-ietf-spki-cert-structure-02.txt. This draft contains the discussion and background from that previous draft. The structure definition is to be found in draft-ietf-spki-cert-structure-03.txt and examples of certificate uses are to be found in draft-ieft-spki- cert-examples-01.txt. Distribution of this document is unlimited. Comments should be sent to the SPKI (Simple Public Key Infrastructure) Working Group mailing list or to the authors. This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months. Internet-Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet- Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Ellison, et al. [Page 1] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 To learn the current status of any Internet-Draft, please check the 1id-abstracts.txt listing contained in the Internet-Drafts Shadow Directories on ds.internic.net (East USA), ftp.isi.edu (West USA), nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe), munnari.oz.au (Pacific Rim), or ftp.is.co.za (Africa). Ellison, et al. [Page 2] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 Abstract The SPKI Working Group has developed a standard form of digital certificate that is both more general and simpler than what is traditionally considered to be a certificate. Since the word ''certificate'' was first used by Loren Kohnfelder in 1978 to refer to a signed record holding a name and a public key, it has been assumed that the only purpose of a certificate has been to bind a public key to a globally unique name and therefore to a person. This binding was assumed both necessary and sufficient for security. The working group has found that the creation of a globally unique name is neither necessary nor sufficient for Internet security or electronic commerce. In fact, use of global names can introduce a security flaw. Therefore, we define certificate forms for binding local names to keys (to retain security while offering the convenience of meaningful names) and for assigning authorizations to keys (to provide adequate information for real applications). These forms can be used alone or together. Acknowledgments Several independent contributions, published elsewhere on the net or in print, worked in synergy with our effort. Especially important to our work were: [SDSI], [BFL] and [RFC2065]. The inspiration we received from the notion of CAPABILITY in its various forms (SDS-940, Kerberos, DEC DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated. Significant contributions to this effort by the members of the SPKI mailing list and especially the following persons (listed in alphabetic order) are gratefully acknowledged: Steve Bellovin, Mark Feldman, John Gilmore, Phill Hallam-Baker, Bob Jueneman, David Kemp, Angelos D. Keromytis, Paul Lambert, Jon Lasser, Jeff Parrett, Bill Sommerfeld, Simon Spero. Ellison, et al. [Page 3] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 Table of Contents Status of This Document....................................1 Abstract...................................................3 Acknowledgments............................................3 Table of Contents..........................................4 1. Overview of Contents....................................5 2. Scope Of This Effort....................................6 2.1 Charter of the SPKI group..............................6 2.2 Areas Covered And Not Covered..........................6 2.2.1 Key and certificate storage..........................7 2.2.2 Protocols to use public key authentication...........8 2.3 Other Certificate Formats..............................8 2.4 Goals of this effort...................................8 2.5 SPKI Certificates vs. Capabilities.....................9 2.6 Chosen standard format.................................9 3. Assumptions, Definitions and Design Issues.............11 3.1 Background............................................11 3.2 Definition of PRINCIPAL and KEYHOLDER.................13 3.2.1 Protection of Private Keys..........................15 3.3 Certificate Structure.................................16 3.3.1 5-tuple Reduction (introduction)....................17 3.3.2 Authority Loops.....................................18 3.3.3 Certificate Result Certificates.....................18 3.4 Relation to PolicyMaker...............................19 3.5 Namespaces and Identity Certificates..................20 3.5.1 X.500 and X.509.....................................20 3.5.2 Death of global identity certification..............21 3.5.3 SDSI 1.0 Namespaces.................................21 3.5.4 Mappings within cyberspace..........................22 3.5.5 Mappings to (keyholder K1)..........................22 3.5.5.1 Donation Certificates.............................22 3.5.5.2 Locator Certificates..............................23 3.6 Certificate validity periods..........................23 3.7 Unwanted Attributions.................................24 3.8 Blind Signatures......................................25 3.9 Determinism...........................................25 References................................................27 Authors' Addresses........................................29 Expiration and File Name..................................30 Ellison, et al. [Page 4] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 1. Overview of Contents This document contains the following sections: Section 2 describes the scope of both the SPKI working group and this particular Internet Draft. Section 3 gives necessary background for understanding the SPKI certificate structure. It details assumptions, definitions and design issues behind this structure design and is recommended reading for anyone who did not follow the discussion on the working group mailing list. The References section lists all documents referred to in the text as well as readings which might be of interest to anyone reading on this topic. The Authors' Addresses section gives the addresses, telephone numbers and e-mail addresses of the authors. Ellison, et al. [Page 5] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 2. Scope Of This Effort The SPKI certificate form reflects a change in point of view thanks to the Internet. Older certificate efforts assumed that all relationships and all granting of permission occurred in 3D space among people who knew each other. A global name was assumed to be needed to refer to these persons, and all certificate operations referred back to 3D space via those names. The SPKI effort recognizes that a growing number of relationships form in cyberspace, among people who have never met and maybe never will. Even for relationships among people who have met, SPKI recognizes that the certificate verifying mechanism cares as little about an entity's name as does an ATM or POS terminal. SPKI certificate forms therefore refer to the 3D world entity only if something is being said about that entity (cf., (keyholder K)). If that entity's key is being empowered by a certificate, the key is referred to directly (or indirectly via some local name for the key, defined and used as a convenience to the issuer). 2.1 Charter of the SPKI group Many Internet protocols and applications which use the Internet employ public key technology for security purposes and require a public key infrastructure to manage public keys. The task of the working group will be to develop Internet standards for an IETF sponsored public key certificate format, associated signature and other formats, and key acquisition protocols. The key certificate format and associated protocols are to be simple to understand, implement, and use. For purposes of the working group, the resulting formats and protocols are to be known as the Simple Public Key Infrastructure, or SPKI. The SPKI is intended to provide mechanisms to support security in a wide range of Internet applications, including IPSEC protocols, encrypted electronic mail and WWW documents, payment protocols, and any other application which will require the use of public key certificates and the ability to access them. It is intended that the Simple Public Key Infrastructure will support a range of trust models. 2.2 Areas Covered And Not Covered To this point, the working group has been concerned only with certificate, hash, key and signature formats, using the certificates defined here both for verification of identity and for proof of Ellison, et al. [Page 6] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 authorization. We have not covered the other elements of a full public key infrastructure (PKI): key/certificate storage and acquisition. We also do not cover all the applications or protocols which must be modified to employ public key authentication or privacy. 2.2.1 Key and certificate storage There are several independent efforts at this time to provide a database of keys or certificates for the Internet. The DNS Security Working Group draft [RFC2065], specifies an efficient key storage and distribution mechanism. It may be possible to store an SPKI certificate in a KEY Resource Record (RR) or to create a new RR type for SPKI certificates, under the DNSSEC design, but that effort has not been undertaken yet. The PGP key server at MIT operating both as a web page and as an e- mail driven service provides another example of efficient certificate storage and retrieval for the net at large. The custom key server run by PGP, Inc., provides another possibility. SDSI 1.0 demonstrated certificate servers for individuals to run on their own net-connected workstations, in response to the fact that more and more individuals remain connected to the network permanently. We may see a similar effort establishing SDSI/SPKI certificate servers. On the other hand, there are those who view certificate servers as a violation of privacy. A standard phenomenon in dealing with classified documents is called "data aggregation". That is, two data A and B may, by themselves, be unclassified, but if both were to be known by one person, the combination would be considered classified. The same might apply to the authorizations granted by certificates to a given keyholder. Along similar lines, many corporations consider their employee telephone lists confidential and are unlikely to host a certificate server which gives the equivalent information to the net. The common practice which has evolved is that of the requestor supplying any and all certificates which the verifier needs in order to permit the requested action. In this model, there may be no need for certificate servers or if there are servers, it is likely that they will be accessed by the requestor (possibly under access control) rather than the verifier. Ellison, et al. [Page 7] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 2.2.2 Protocols to use public key authentication Proposals for modification of applications to employ public key authentication are proceeding independently, e.g., [PKLOGIN]. We encourage other developers to actively enter this area of design, aided by SPKI certificates as a tool. Others, such as TLS and SSH already use public key authentication and are considering use of SPKI certificates for communicating the permission required to achieve the desired access. 2.3 Other Certificate Formats We are aware of a number of actual and proposed kinds of signed records which, by some definition, qualify as certificates: 1. PGP signed keys 2. X.509 identity certificates, from a number of sources 3. X.509 SET (Secure Electronic Transaction) certificates 4. DNS Security Extension signed keys 5. Signed PICS labels (from the W3C DSig effort) It is not our intention to coerce these other certificate formats into our mold, although they are welcome to switch over. The certificate structure defined below is flexible enough to accommodate all of the above. However, we recognize that a real world system will involve some mixture of SPKI and non-SPKI certificates as well as traditional Access Control Lists (ACLs). Our design accommodates these by allowing them to be mapped to 5-tuples and therefore to participate in trust computations. Once one has reduced a possibly mixed set of certificates into a partial or final result 5-tuple, that 5-tuple can be signed to form a Certificate Result Certificate. This operation can be done in all verifiers or can be done in an enterprise-wide server reducing varied certificate forms to one simple, SPKI form. 2.4 Goals of this effort In keeping with the design goals enumerated in section 3 of RFC1958, it is our goal to keep the SPKI certificate pruned to the minimum information necessary to accomplish the job at hand -- which is Ellison, et al. [Page 8] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 secure authentication and authorization of access control and confidentiality for the Internet. We use well tested formats with a long history of success and have chosen those which require the bare minimum of tool software so that applications remain as small and efficient as possible. We desire to offer the bare minimum of options, in order to reduce program size and complexity. We also recognize that some kinds of certification (such as notarized identity certification) can carry risks of invasion of privacy for the individual. We have therefore designed these certificates to reveal the minimum information necessary to get the job done, whatever that job happens to be. In many cases, the user can remain anonymous in the traditional sense while exercising strongly verified authorization. That is, the user can be identified by his public key alone. 2.5 SPKI Certificates vs. Capabilities An SPKI certificate is closer to a "capability" as defined by [HARDY], [KEYKOS], [LANDAU], [SRC-070], etc., than to an identity certificate. There is the difference that in a capability system, the capability itself is a secret ticket, the possession of which grants some authority. It is anonymous (more like cash than a check). Therefore, if you grant authority to read a capability, you have delegated the ability to use it. An SPKI certificate identifies the specific key to which it grants authority and therefore the mere ability to read (or copy) the certificate grants no authority and the certificate itself does not need to be as tightly controlled. Rather, control over the corresponding private signature key must be tightly controlled. With SPKI certificates, one can delegate authority (all or part of the authority one has been delegated) to a different key, without sharing the quantity which must be kept secret (the private key) -- as opposed to a capability which is kept secret except when it is shared for the purpose of delegation. 2.6 Chosen standard format In this draft, the standard format adopted is that developed by SDSI, modified slightly. Data objects are defined as S-expressions -- lists in which the first element is a token defining the data object. Rather than permit the full generality of S-expressions, we define a canonical format and accept only that form. Software is available to translate between the canonical format and a presentation format. Ellison, et al. [Page 9] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 This document presents the canonical format, but uses a presentation format for examples since the canonical format is binary and can not easily be transmitted in a text document. Ellison, et al. [Page 10] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 3. Assumptions, Definitions and Design Issues There were a number of discussion topics involved in the design of SPKI certificates and we summarize them here for the reader who was not part of the SPKI discussion. This section should at least be skimmed by even the reader with a solid grounding in classical (identity) certification. Some of these might be new concepts. Some provide definitions for terms which traditional discussions of certification frequently leave undefined. Throughout this document, we refer to two parties engaged in certificate use: the prover and the verifier. By PROVER, we mean the entity which wishes access or digitally signs a document. We assume that the prover assembles all certificates necessary for use by the verifier, and puts those into order for the verifier. The prover is software but could be interacting with a human user. By VERIFIER, we mean an entity which processes certificates, together with its own ACL entries, to determine if the prover deserves access or if some signed document is valid. The verifier is most likely unattended software. 3.1 Background In the words of [LAMPSON], a public signature key "speaks for" its owner: a person or entity we call the "keyholder". It is primarily through such public key "speech" that one achieves security on the inherently anonymous and spoof-able Internet. In a sense, the public key is a proxy for or projection of a person in cyberspace. Older certificate forms endeavoured to bind public keys to the "true names" of their keyholders, in an attempt to identify the keyholder and to permit the transfer of permissions or other attributes from the physical world in which the keyholder lives into the digital world. It was assumed that all relationships were formed in the 3D world and needed to be mapped into cyberspace. This effort has produced so-called "identity certificates", such as X.509 certificates or PGP signed keys, giving bindings which needed to be combined with certificates or ACL entries of the form , to yield the relationship which a computer then uses to verify public-key driven access attempts. { here stands for authorization, permission, etc.} That effort is motivated by a long standing human habit that grew out of life in small communities and is replayed for each individual by Ellison, et al. [Page 11] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 his development inside a family. [This is a slightly abstract example of the classic observation that ontogeny recapitulates phylogeny.] Human beings are driven to use names for persons. We remember characteristics of a person (his or her identity, as far as we know it) but we label those memories with a name for the person. In a small community, names are unique. If they are not unique, we force them to be, so that they are useable as identifiers. E.g., the Ellison family had Little Carl and Big Carl. So, we learn early (as a species and as individuals) that we can assume name = person Small communities have another characteristic: no privacy. A T-shirt for sale in a small town in Michigan sums this up with the caption: "Small Town (def) A place where you don't have to use your turn signals because everyone knows where you are going". This leads us to extend our assumption to: name = person = characteristics By one dictionary definition of the word, "identity" is the defining characteristics of an individual. This extends the assumption to: name = person = characteristics = identity When the small community is closed as well, as it is at first, we learn that Alice can talk to Bob about Carol and know that Bob is thinking of the same Carol Alice is. That is, we can use names to refer to persons in speaking to other persons. From this chain of reasoning, in this set of circumstances, it is perfectly reasonable to build a certificate that binds a name to a key and call it an "Identity Certificate" and assume that one can transmit it to a third person and have it be meaningful to that person. The trouble with this line of reasoning is that we do not live in small communities. As a species, we stopped that with the rise of cities and especially with the industrial revolution. As individuals, we leave our early families and enter the larger world. In the 1990's, we enter that larger world via the Internet even before we leave our families. In this larger world, it is no longer true that a person's name is a valid identifier. One response to this fact has been the effort to create globally unique names, with a common name as a portion. That can be done, of course, but for a name to be meaningful to a user it must be held in the mind of the user and humans have a limited Ellison, et al. [Page 12] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 capacity for remembering names. A person who can remember thousands of names is considered unusual, if not a freak. The global community is closed and therefore it should be theoretically possible to use global names for introduction and reference purposes. That is, Alice can tell Bob about Carol. For this to be meaningful, however, Alice has some memory of Carol and wants to make sure that when she tells Bob about Carol, he accesses his memories of the same person. This process breaks down in two ways, when one uses global names. First, there are so many global names that Bob is unlikely to have Carol's global name in his memory. [If global names are long enough, Bob is unlikely to have his own global name in his memory.] Second, if Bob has never met Carol, he has no body of memories to tie that name to. The process then becomes an empty ritual, reflecting something that had meaning under different circumstances but that has lost its meaning. Meanwhile, one basic premise of the older certificate formats was that relationships were formed in the 3D world and needed to be mapped into cyberspace. Instead, we see relationships increasingly form in cyberspace. Therefore, a mechanism that maps attributes from the physical world to the digital world is increasingly less appropriate while a mechanism that transfers attributes within the digital world is vital and one that transfers attributes from the digital world to the physical world is likely to be needed very soon, if not immediately. We have also observed that is a perfectly adequate name for a keyholder, at least as far as a computer is concerned. It and its hash have the advantage of being unique while each portion of it (and especially of its hash) is uniformly distributed and therefore of particular value as an index into a database. It is also tied the most strongly of any identifying string to the keyholder. We have therefore defined a certificate which communicates directly, leaving names out of the process except in the case where the name is the item of interest (e.g., for secure e-mail). We have also observed that a global name (e.g., Distinguished Name) that includes a person's common name as a substring is a security flaw. That is because it induces humans (scanning a database or cache of certificates, for example) to guess the connection between a global name and the person they have in mind. This introduction of a human guess in a security protocol dwarfs other security risks. 3.2 Definition of PRINCIPAL and KEYHOLDER The most important issue is the notion of a key as a principal and the difference between that key and the person or machine which owns Ellison, et al. [Page 13] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 and controls it. By PRINCIPAL, we mean a signature key. That is, a principal is capable of "speaking" in cyberspace by signing messages. We also permit use of the secure hash of a signature key as a principal, in an effort to save space in data structures which use principals. By KEYHOLDER, we mean an entity in the 3-D world which controls a given (private) signature key. The keyholder is identified primarily by the public verification key which corresponds to the private signature key. By definition, the keyholder has sole possession of the private key. That private key could be used as the identifier of the keyholder -- as a name -- except the private key must be kept secret. There is only one private key to match a given public key, so the keyholder can be identified by the public key just as uniquely. Similarly, there is only one public key which hashes to a given secure hash (by definition of "secure hash", assuming we are limited in computation power), so the secure hash of a public key can also be used to identify the keyholder. If we are using symmetric (secret) signature keys, the hash of that key can still serve as a name for the key and for its keyholder(s). We identify a PRINCIPAL by either a key or a secure hash of a key. There is pressure, in the interest of simplicity, to restrict PRINCIPAL to just a key. However, if one is using a shared secret key (e.g., for HMAC or some symmetric algorithm like DES-MAC), it is essential to keep the key secret and use of a hash permits that. It is also possible to have shared secret public keys -- e.g., RSA public keys of short moduli (for performance reasons) -- which must not be published because the key can be broken, but for which the hash of the key can be published without fear of compromise. We identify a KEYHOLDER by the construct "(keyholder )" -- using the principal as the name of the private key and therefore the keyholder, but explicitly noting that we refer to the keyholder in physical space rather than the key in cyberspace. Without certificates, we might not know anything else about the keyholder (such as name, gender or even if the keyholder is a living being) but we do know enough to link together separate messages from the same keyholder. For some purposes, that is sufficient identification (for example, when a person is first encountered on- line via signed messages and there is no intention of linking that person to any physical being, only to his or her own other messages). Ellison, et al. [Page 14] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 However, there are other applications for which the ability to link together separate messages from an anonymous source is not adequate and therefore for which certificates are required. 3.2.1 Protection of Private Keys For any public key cryptosystem to work, it is essential that a keyholder keep its private key to itself. In the case of a human being, this might involve keeping the private key encrypted under a high-entropy passphrase and storing it only on the person's own personal computer or floppy disks. Some humans might even keep the private key in a tamper-resistant PCMCIA card or Smart-Card which will never release it and will in fact destroy it after too many failed attempts to gain access. In the case of a network node, this might involve keeping the private key in a tamper-resistant cryptographic processor which generated it and which will destroy it if tampering is attempted. If the keyholder does not keep the private key protected (that is, if the private key gets out to others to use) then one can not know what entity is using that key and no certificate will be able to restore the resulting broken security. Therefore, we are forced to assume that all private keys are kept private and bound tightly to the one keyholder to which they belong. We will have to provide for methods of announcing the compromise of such private keys whenever this assumption proves false, but we must assume that unless such notification is delivered, each private key is secure and attached to its owner. Note: We have specifically included a process for one keyholder who has been granted some authority to delegate that authority to another, in order to reduce if not eliminate the motivation for one keyholder to loan a private key to another. So to reiterate, we do not expect every person, process and device in the Internet to employ true tamper resistance. Many people will keep and use private keys on an insecure personal computer or workstation. However, we are forced to assume protection of the private key or give up any notion of cryptographically strong authentication and authorization. Work is progressing on decreasing the cost of true tamper-resistance but until it is ubiquitous, we must accept a Ellison, et al. [Page 15] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 certain amount of risk from copied or stolen private keys. Even then, there is risk from coerced use of one's private key. 3.3 Certificate Structure An SPKI certificate body has several fields, five of which are relevant for security purposes: ISSUER: a principal or a single, top-level name in a principal's namespace. The principal is identified as a public key or the hash of that key and the corresponding private key signs the certificate. SUBJECT: a principal, an object or a SDSI name reducible to either of those. The subject is that which receives authority from the issuer by way of the certificate. DELEGATION: the optional modifier, "(propagate)", giving the subject permission to delegate the authority presented in the certificate (or part of it) to some other Subject. This is represented as the delegation boolean, D, in the discussion below. The two boolean states are (F: delegate only through name declarations -- also known as "stop at key") and (T: delegate to the subject). AUTHORITY: the specific authorization(s) being delegated in this certificate. These fields, of the form "(tag ...)", are to be defined by those who have resources to control and describe resource allocations. This document gives some examples for such fields which are expected to be in common use, but more importantly it gives the structure for fields and the description of a standard process for manipulating them which is expected to be implemented in all code conforming to this standard. VALIDITY: date ranges and/or online validity tests for determining certificate validity. A certificate is signed by its issuer. Section 6 gives details about signature blocks. The five security-relevant fields described above are termed a "5- tuple" for lack of a better word, in the discussion below. The assumption is that a certificate's signature will be checked to yield the 5-tuple which, in turn, will be kept in trusted memory and will participate in trust management decisions. Objects other than Ellison, et al. [Page 16] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 certificates (such as ACL entries) can also yield 5-tuples which participate in trust management decisions. Informally, the meaning of the certificate is "The issuer says that the subject has the stated authority during the validity period". Another way of saying this is "The issuer says that the subject may speak for the issuer with the stated authority during the validity period." If the issuer issues several such certificates for different subjects, then it is defining a group of subjects, each of which can speak for it. If the subject is an object that is not reducible to a principal, it can't do any speaking; in this case the meaning is "The issuer says that the subject has the properties stated by the 'authority'." 3.3.1 5-tuple Reduction (introduction) A certificate which is received to be part of a verification process has its signature checked. One whose signature checks is considered valid. Other kinds of authorization statement (most specifically ACL entries) can be considered valid without a signature check. A valid authorization statement can be represented by five quantities: (I,S,D,A,V) A set of simple 5-tuples can be reduced as follows: (I1,S1,D1,A1,V1) + (I2,S2,D2,A2,V2) becoming (I1,S2,D2,A,V) if S1=I2 (meaning that they are the same public key) and (D1 = TRUE) or (S1 is a SDSI name) and A = intersection(A1,A2) and V = intersection(V1,V2) The actual process is slightly more complicated when I2 is of the form (issuer (name K3 nnn)) or when S1 is of the form (subject (threshold K N (s1) (s2) ... (sN))) Ellison, et al. [Page 17] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 Rules for those cases are given below in section 10, presenting the full tuple reduction logic, but for the discussion to follow the logic given above will suffice. 3.3.2 Authority Loops By 5-tuple reduction, some chains of authorization statements will be reduced to the form: (Self,X,D,A,V) where "Self" represents the entity doing the verification, granting access, etc. Such a 5-tuple says "Self says (I say) that X has authority (D,A) for validity period (or conditions) V". In other words, Self has decided what it can trust about X Any authorization chain not reducing to a 5-tuple with Self as issuer isn't relevant to decisions by Self. Therefore, any authorization chain which is to be used by Self to do trust management must have Self as a root. Since Self is doing this chain reduction and is therefore at the receiving end of the chain as well, that makes all useful authorization chains loops. 3.3.3 Certificate Result Certificates In cases where the verifier, Self, has access to a private key, once it has reduced a chain of certificate bodies down to the form: (Self,X,D,A,V) it can sign that generated body, using its private key, producing an SPKI certificate. That certificate will have a validity period no larger that of any certificate in the loop which formed it, but during that validity period it can be used by the prover instead of the full chain, when speaking to that particular verifier. It is good only at that verifier (or at another which trusts that verifier, Self, to delegate the authorization A). Therefore, one option by the verifier is to sign and return the result 5-tuple to the caller for this later use. If it isn't important for any other verifier to accept this "result certificate", it can even be signed by a symmetric key (an HMAC with secret key private to the verifier). The certificates which made up the loop forming this result 5-tuple Ellison, et al. [Page 18] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 could have been of any variety, including X.509v1, X.509v3, SET or DNSSEC. They could also be PGP signed keys processed by an enriched trust engine (one capable of dealing with the PGP web of trust rules). If the verifier, Self, were to be trusted to delegate the resulting authorization, its certificate result certificate then becomes a mapping of these other forms. This may prove especially useful if a given certificate chain includes multiple forms or if the result certificate is to be used by a computationally limited device (such as a Smart-Card) which can not afford the code space to process some of the more complex certificate formats. 3.4 Relation to PolicyMaker The section above introduced the possibility of a machine which reduces a set of certificates, possibly a very complex one, and yields a single certificate as a result. That single certificate would be simpler and faster to verify. It might even stand alone in granting access. That machine reducing the set of certificates to a single result might even execute a policy program which could be too complex to be expressed in terms of SPKI 5-tuple reduction. The policy machine would still have to have its own ACL entries, declaring the keys it trusts as "roots" for various purposes and, in this hypothetical case, a signature key, P. It would execute its policy program on the credentials provided by the caller, come up with either a failure or a certificate result, signed by P, and deliver that result to the caller. In the manner of [BFL] we note that one can take the same code executed by that policy processing machine and digitally sign the code -- then digitally sign the ACL entries for its "roots" (turning them into certificates, issued by P) -- and ship the code plus certificates to the caller, presumably a verifying computer. That verifying computer could then run the policy code on P's behalf, getting either a failure or a 5-tuple. It can't sign the 5-tuple turning it into a certificate issued by P, because it would not have P's private key -- but it doesn't need a certificate. It needs only the trusted 5-tuple. [BFL] introduces a language called Policymaker in which one can express security policy statements. It is possible for Policymaker to be used along with SPKI certificates in two ways: 1) It is believed possible to use Policymaker's language to implement the standard SPKI 5-tuple reduction. The code has not been written as of the time of this draft, but at this point it looks possible. Ellison, et al. [Page 19] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 2) For any trust policy which the full SPKI 5-tuple reduction can not express, one must write a policy interpretation program and Policymaker provides a language and body of examples for that purpose. The result of the Policymaker execution can be a 5-tuple to be used within an SPKI reduction. 3.5 Namespaces and Identity Certificates Since the word "certificate" was first used by Kohnfelder in 1978 to refer to a digitally signed binding between a name and a public key, people have assumed that a certificate binds a name to a key. For most of human history, people lived in relatively small, closed communities. It was common in such a community for each member to have his or her own unique name. Everyone in the community would know everyone else in the community by that name. It was also extremely unlikely for someone in such a small community to change his or her name (except through marriage). The habit naturally developed of thinking of a person's name as a unique and permanent identifier, in a way synonymous with his or her identity. Although such small communities have become unusual for the majority of people today, the association between name and identity persists in human thinking. Even today, a certificate which binds a name to a key is often called an "identity certificate". 3.5.1 X.500 and X.509 At one time, it was assumed that there would be a worldwide directory of names of people (and computers and other things), called X.500, and there was a data structure defined, called X.509, to bind public keys to portions of the X.500 hierarchy. The original purpose of such certificates was to record who (which keyholder, ie., which key) had permission to modify that portion of the distributed X.500 database. At some point, it became apparent that X.500 was never going to occur as a global directory. Among other things, corporations which were to own and manage substantial sub-trees of the directory consider their employee directories company confidential. The same applies to some government agencies. The fact that an X.500 node's address was a person's unique name (so- called "distinguished name"), led people to view X.509 apart from its purpose of controlling access to X.500 databases and instead treat it Ellison, et al. [Page 20] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 as an identity certificate. 3.5.2 Death of global identity certification Even if a global X.500 directory had occurred, global identity certification would have died. The problem is one of the unanticipated consequences of the Internet. The purpose of an identity certificate is to map from the 3D space of people to cyberspace, particularly to the space of public signature keys. This mapping takes two steps: from 3D space to a name space; from the name space to key space. The latter step is accomplished by a certificate (e.g., X.509). The former step is assumed, in the X.500/X.509 case, to be common knowledge. The larger that name space, the less likely that anyone would know the name of a specific individual. Alice might suspect that her old friend Bob Smith has a name in the global X.500 directory, but there are so many people named Bob Smith in the world that it is unlikely Alice would know which of the thousands of Bob Smiths was in fact her old friend. The problem is that, like the telephone directory which inspired this model of certification, the directory never claimed to record information of interest to each user (e.g., Alice's old friend). In fact, a directory which did so would almost certainly be viewed as a violation of privacy on a massive scale and would be shut down. 3.5.3 SDSI 1.0 Namespaces SDSI 1.0 [SDSI] solved this problem inherent in global name spaces by ignoring the fantasy of a global name space and replacing it with local name spaces, one for each principal (= signing key). Principals may share name spaces as will be seen later, but in theory each principal has its own name space. The certificate mapping from name to key (SDSI, in this case) is just as secure as the X.509 certificate mapping from the global name space to a key, but the link from 3D space to name is considerably more secure -- because it is a link defined by the user. Alice's old friend Bob Smith might be named "Red" in her name space, for example. Her name for him is not intended to be of any use to anyone else -- only to her. Such a local name space is already familiar to some users of mail agents, under the label "nickname" or "alias". Ellison, et al. [Page 21] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 3.5.4 Mappings within cyberspace Identity certificates with their presumed ability to map from 3D space to key space were assumed to be necessary "so that you know with whom you are dealing in cyberspace". The assumption behind such a thought is that a relationship is formed in 3D space between people and that relationship needs to be mapped into cyberspace. Unanticipated by the original designers of identity certificates was the fact that the Internet brought with it the formation of relationships in cyberspace. In such cases, there is no relationship in 3D space to be mapped and therefore no need for identity certificates. There is, however, a need for certificates within cyberspace -- to grant privileges, access rights, etc. -- from one cyberspace principal to another (from one key to another). It was for this situation that the original SPKI was designed. 3.5.5 Mappings to (keyholder K1) Also not anticipated by the pre-Internet developers of identity certificates was that relationships which formed online might need to be mapped occasionally back to the 3D world. Those early designers of certificates might have assumed that the binding between name ("identity") and key was bi-directional, but it was not. It mapped name to key. The mapping from key to name is not satisfied by a single approach. In particular, there can be no single issuer for such a certificate, suitable for all purposes. Two such certificates are described below but there are probably several varieties. 3.5.5.1 Donation Certificates Situation: you meet someone (who uses key K1) online, are impressed with his work and decide to hire him. You make an offer. He accepts. He starts working for you and you like his work (all signed by K1). You now need to send him a paycheck. So, you need a name to put on the paycheck and you need a postal address to mail it to (and maybe a phone number, if you are using Fed Ex). This sounds like a traditional identity certificate, but it isn't. There is no CA in this case. The one key you can trust the most to sign this certificate is K1. It belongs to the individual with the most to gain by providing correct information. In X.509-style certification, one would never use a self-signed certificate. Ellison, et al. [Page 22] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 3.5.5.2 Locator Certificates Situation: you meet someone (who uses key K1) online, are impressed with his work and decide to hire him to do some protracted project. You make an offer. He accepts. You need the work done and done right. Failure to have the work done would be very harmful to you. For that you write a contract which he signs with K1 and the contract includes penalty clauses. In the event of his failure to perform, you need to know that you can get redress through the legal system. One way is to have his name and home address so that you could serve legal papers on him should he default on the contract. The certificate which lets you serve papers on Keyholder(K1) sounds even more like a traditional identity certificate, but it isn't. Neither is it a donation certificate, since this one should not be signed by K1. Instead, it should be signed by Kp -- the key of a company which does process serving. That company, Acme Process Servers, however, would rather not have a name and address in the certificate. Instead, Acme would prefer to have a simple sequence number in the certificate, indexing Acme's own files on the person. This forces you to use Acme to do the process serving, doubtless for an additional fee, in the event that you do sue. Meanwhile, you would prefer to have this certificate over an identity certificate issued by the Post Office, listing the person's name and address. The name and address certificate reflects facts at the time of the start of the contract, not facts at the time legal papers need to be served. It may take substantial investigative work to get from the former to the latter. That is the work Acme would do for a living and it would be for that work that Acme would charge both for the initial certificate and for the act of serving papers on the keyholder of K1. Acme might perform this work at time of default or keep tabs on Keyholder(K1) during the life of the contract. That would be Acme's choice. 3.6 Certificate validity periods Our experience with credit cards has influenced the way we consider validity periods of certificates. A credit card is issued with an expiration date 1 to 3 years later than the date of issue, yet one can revoke a credit card and have that revocation be effective within a day of the request. That credit card has a validity period of one day (or less) in spite of its expiration date. At one time, credit card validity was verified at a checkout counter by looking the card number up in a book of revoked cards. The Ellison, et al. [Page 23] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 validity period of a card not listed in such a book was the time until that book was updated and the card had to be looked up again. This practice has migrated into the digital world through the CRL (Certificate Revocation List) construct. Modern systems accepting credit cards perform an on-line validity check, in which case the validity period can be very short and is determined by the time it takes to make a database update from a report of a lost or stolen card. SPKI certificates may use one or both of two kinds of validity period: a date range (akin to expiration dates) or an on-line check. The on-line check will return information about the certificate's validity and that information itself will have an expiration date and time. The certificate together with its latest on-line test result would then yield a valid assignment of authorization, with validity period which is the intersection of the dates of the two data items (usually just the date range of the on-line test result). There are three forms of on-line test result defined: CRL a list of certificates known to be revoked since a certain time. Periodic revalidation a new assured validity date for the certificate being tested. One-time revalidation a statement that for this one transaction, the indicated certificate is valid. [This is as close as we can come to a 0- length validity period revalidation.] The one-time revalidation can also have side effects -- e.g., refer to a bank balance. 3.7 Unwanted Attributions There is a potential problem that a certificate might be issued which the keyholder does not want. For example, someone with the power to issue access certificates wishes to make trouble for you. That person generates a cert for you, giving you access to their company's file system. Someone breaks into that file system and does damage, also wiping out the audit logs of who broke in. So, the police ask the age-old Perry Mason question: who had keys to that door? Your cert (even though you never saw it) is a key to that door. It might even be the only cert with the capability to do what was done, at least according to the company records. That makes you a suspect. If for other reasons Ellison, et al. [Page 24] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 you might be even the most logical suspect, then you might make it to the top of the police list and get severely hassled. For another example, a keyholder, Alice, has a signature key, K, being used to sign digital lab notebooks for later use in patent applications. That key is certified as hers by her company through an SPKI identity certificate with an EMPLOYEE field. Bob learns Alice's public key and builds a certificate using his own name and her key, getting it signed by some reputable commercial CA. Now when it comes time to dispute prior art on Alice's patent(s), Bob produces his certificate and claims that Alice had not only copied his work but stolen his private signature key. Although we do not mandate such practice at this time, some certificates could be signed by the as well as by the in order to make sure that the really does have access to the indicated private key. Alternatively, it is possible to establish a practice of getting a digitally signed receipt for a certificate from each subject in certain cases before the certificate is delivered. That separate receipt would serve the same function. 3.8 Blind Signatures The issue of blind signatures [CHAUM] was raised in the working group. As can be seen from the format of the Signature object, normal blinding (e.g., of RSA by pre- and post- multiplication of a signature value) can be applied. 3.9 Determinism As defined above in section 3.6, CRLs are just one type of response to an on-line request. Each CRL carries its own validity period and signature. This is different from an old concept of CRL which might be called "wandering anti-matter". In that concept, CRLs would be signed, might have validity dates (or at least sequence numbers) but would not be required to be fetched. If someone happened to receive the latest CRL and the given cert was on it, then the cert was invalid. The CRLs wandered through cyberspace, like anti-matter, annihilating any matching certs they happened to encounter. This concept of CRL introduces non-deterministic behavior. It has been one design goal of SPKI to make trust computations Ellison, et al. [Page 25] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 deterministic. As a result, the only way defined here to get a CRL is if a given cert demands that one be fetched as part of its validity conditions. For another example of enforced determinism, it is by definition not possible to have two SPKI certificates which conflict, so that one might override the other. If two different certs were issued defining a given SDSI name as two different keys, for example, then that name becomes a group with at least two members. Ellison, et al. [Page 26] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 References [Ab97] Abadi, Martin, "On SDSI's Linked Local Name Spaces", to appear in the Proceedings of the 10th IEEE Computer Security Foundations Workshop (June 1997). [BFL] Matt Blaze, Joan Feigenbaum and Jack Lacy, "Distributed Trust Management", Proceedings 1996 IEEE Symposium on Security and Privacy. [CHAUM] D. Chaum, "Blind Signatures for Untraceable Payments", Advances in Cryptology -- CRYPTO '82, 1983. [DvH] J. B. Dennis and E. C. Van Horn, "Programming Semantics for Multiprogrammed Computations", Communications of the ACM 9(3), March 1966 [ECR] Silvio Micali, "Efficient Certificate Revocation", manuscript, MIT LCS. [HARDY] Hardy, Norman, "THE KeyKOS Architecture", Operating Systems Review, v.19 n.4, October 1985. pp 8-25. [IDENT] Carl Ellison, "Establishing Identity Without Certification Authorities", USENIX Security Symposium, July 1996. [IWG] McConnell and Appel, ``Enabling Privacy, Commerce, Security and Public Safety in the Global Information Infrastructure'', report of the Interagency Working Group on Cryptography Policy, May 12, 1996; (quote from paragraph 5 of the Introduction) [KEYKOS] Bomberger, Alan, et al., "The KeyKOS(r) Nanokernel Architecture", Proceedings of the USENIX Workshop on Micro-Kernels and Other Kernel Architectures, USENIX Association, April 1992. pp 95-112 (In addition, there are KeyKOS papers on the net available through http://www.cis.upenn.edu/~KeyKOS/#bibliography) [KOHNFELDER] Kohnfelder, Loren M., "Towards a Practical Public-key Cryptosystem", MIT S.B. Thesis, May. 1978. [LAMPSON] B. Lampson, M. Abadi, M. Burrows, and E. Wobber, "Authentication in distributed systems: Theory and practice", ACM Trans. Computer Systems 10, 4 (Nov. 1992), pp 265-310. [LANDAU] Landau, Charles, "Security in a Secure Capability-Based System", Operating Systems Review, Oct 1989 pp 2-4 [LEVY] Henry M. Levy, "Capability-Based Computer Systems", Digital Press, 12 Crosby Dr., Bedford MA 01730, 1984 [LINDEN] T. A. Linden, "Operating System Structures to Support Ellison, et al. [Page 27] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 Security and Reliable Software", Computing Surveys 8(4), December 1976. [PKCS1] PKCS #1: RSA Encryption Standard, RSA Data Security, Inc., 3 June 1991, Version 1.4. [PKLOGIN] David Kemp, "The Public Key Login Protocol", working draft, 06/12/1996. [RFC1321] R. Rivest, "The MD5 Message-Digest Algorithm", April 16 1992. [RFC2045] N. Freed and N. Borenstein, "Multipurpose Internet Mail Extensions (MIME) Part One: Format of Internet Message Bodies", Dec 2 1996. [RFC2046] N. Freed and N. Borenstein, "Multipurpose Internet Mail Extensions (MIME) Part Two: Media Types", Dec 2 1996. [RFC2047] K. Moore, "MIME (Multipurpose Internet Mail Extensions) Part Three: Message Header Extensions for Non-ASCII Text", Dec 2 1996. [RFC2065] D. Eastlake and C. Kaufman, "Proposed Standard for DNS Security", Jan 1997. [RFC2104] H. Krawczyk, M. Bellare and R. Canetti, "HMAC: Keyed- Hashing for Message Authentication", Feb 1997. [SDSI] Ron Rivest and Butler Lampson, "SDSI - A Simple Distributed Security Infrastructure [SDSI]", http://theory.lcs.mit.edu/~cis/sdsi.html [SEXP] Ron Rivest, code and description of S-expressions, http://theory.lcs.mit.edu/~rivest/sexp.html . [SRC-070] Abadi, Burrows, Lampson and Plotkin, "A Calculus for Access Control in Distributed Systems", DEC SRC-070, revised August 28, 1991. Ellison, et al. [Page 28] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 Authors' Addresses Carl M. Ellison CyberCash, Inc. 207 Grindall Street Baltimore MD 21230-4103 USA Telephone: +1 410-727-4288 +1 410-727-4293(FAX) +1 703-620-4200(main office, Reston, Virginia, USA) EMail: cme@cybercash.com cme@acm.org Web: http://www.clark.net/pub/cme Bill Frantz Electric Communities 10101 De Anza Blvd. Cupertino CA 95014 Telephone: +1 408-342-9576 Email: frantz@netcom.com Butler Lampson Microsoft 180 Lake View Ave Cambridge MA 02138 Telephone: +1 617-547-9580 (voice + FAX) EMail: blampson@microsoft.com Ron Rivest Room 324, MIT Laboratory for Computer Science 545 Technology Square Cambridge MA 02139 Telephone: +1-617-253-5880 +1-617-258-9738(FAX) Email: rivest@theory.lcs.mit.edu Web: http://theory.lcs.mit.edu/~rivest Brian Thomas Southwestern Bell One Bell Center, Room 23Q1 St. Louis MO 63101 USA Telephone: +1 314-235-3141 Ellison, et al. [Page 29] INTERNET-DRAFT SPKI Certificate Theory 21 November 1997 +1 314-331-2755(FAX) EMail: bt0008@entropy.sbc.com Tatu Ylonen SSH Communications Security Ltd. Tekniikantie 12 FIN-02150 ESPOO Finland E-mail: ylo@ssh.fi Expiration and File Name This draft expires 26 May 1998. Its file name is draft-ietf-spki-cert-theory-01.txt Ellison, et al. [Page 30]