Network Working Group C. Ellison Request for Comments: 2693 Intel Category: Experimental B. Frantz Electric Communities B. Lampson Microsoft R. Rivest MIT Laboratory for Computer Science B. Thomas Southwestern Bell T. Ylonen SSH September 1999 SPKI Certificate Theory Status of this Memo This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (1999). All Rights Reserved. Abstract The SPKI Working Group has developed a standard form for digital certificates whose main purpose is authorization rather than authentication. These structures bind either names or explicit authorizations to keys or other objects. The binding to a key can be directly to an explicit key, or indirectly through the hash of the key or a name for it. The name and authorization structures can be used separately or together. We use S-expressions as the standard format for these certificates and define a canonical form for those S-expressions. As part of this development, a mechanism for deriving authorization decisions from a mixture of certificate types was developed and is presented in this document. This document gives the theory behind SPKI certificates and ACLs without going into technical detail about those structures or their uses. Ellison, et al. Experimental [Page 1] RFC 2693 SPKI Certificate Theory September 1999 Table of Contents 1. Overview of Contents.......................................3 1.1 Glossary..................................................4 2. Name Certification.........................................5 2.1 First Definition of CERTIFICATE...........................6 2.2 The X.500 Plan and X.509..................................6 2.3 X.509, PEM and PGP........................................7 2.4 Rethinking Global Names...................................7 2.5 Inescapable Identifiers...................................9 2.6 Local Names..............................................10 2.6.1 Basic SDSI Names.......................................10 2.6.2 Compound SDSI Names....................................10 2.7 Sources of Global Identifiers............................11 2.8 Fully Qualified SDSI Names...............................11 2.9 Fully Qualified X.509 Names..............................12 2.10 Group Names.............................................12 3. Authorization.............................................12 3.1 Attribute Certificates...................................13 3.2 X.509v3 Extensions.......................................13 3.3 SPKI Certificates........................................14 3.4 ACL Entries..............................................15 4. Delegation................................................15 4.1 Depth of Delegation......................................15 4.1.1 No control.............................................15 4.1.2 Boolean control........................................16 4.1.3 Integer control........................................16 4.1.4 The choice: boolean....................................16 4.2 May a Delegator Also Exercise the Permission?............17 4.3 Delegation of Authorization vs. ACLs.....................17 5. Validity Conditions.......................................18 5.1 Anti-matter CRLs.........................................18 5.2 Timed CRLs...............................................19 5.3 Timed Revalidations......................................20 5.4 Setting the Validity Interval............................20 5.5 One-time Revalidations...................................20 5.6 Short-lived Certificates.................................21 5.7 Other possibilities......................................21 5.7.1 Micali's Inexpensive On-line Results...................21 5.7.2 Rivest's Reversal of the CRL Logic.....................21 6. Tuple Reduction...........................................22 6.1 5-tuple Defined..........................................23 6.2 4-tuple Defined..........................................24 6.3 5-tuple Reduction Rules..................................24 6.3.1 AIntersect.............................................25 6.3.2 VIntersect.............................................27 6.3.3 Threshold Subjects.....................................27 6.3.4 Certificate Path Discovery.............................28 Ellison, et al. Experimental [Page 2] RFC 2693 SPKI Certificate Theory September 1999 6.4 4-tuple Reduction........................................28 6.4.1 4-tuple Threshold Subject Reduction....................29 6.4.2 4-tuple Validity Intersection..........................29 6.5 Certificate Translation..................................29 6.5.1 X.509v1................................................29 6.5.2 PGP....................................................30 6.5.3 X.509v3................................................30 6.5.4 X9.57..................................................30 6.5.5 SDSI 1.0...............................................30 6.5.6 SPKI...................................................31 6.5.7 SSL....................................................31 6.6 Certificate Result Certificates..........................32 7. Key Management............................................33 7.1 Through Inescapable Names................................33 7.2 Through a Naming Authority...............................33 7.3 Through Certificates..........................34 7.4 Increasing Key Lifetimes.................................34 7.5 One Root Per Individual..................................35 7.6 Key Revocation Service...................................36 7.7 Threshold ACL Subjects...................................36 8. Security Considerations...................................37 References...................................................38 Acknowledgments..............................................40 Authors' Addresses...........................................41 Full Copyright Statement.....................................43 1. Overview of Contents This document contains the following sections: Section 2: history of name certification, from 1976 on. Section 3: discussion of authorization, rather than authentication, as the desired purpose of a certificate. Section 4: discussion of delegation. Section 5: discussion of validity conditions: date ranges, CRLs, re- validations and one-time on-line validity tests. Section 6: definition of 5-tuples and their reduction. Section 7: discussion of key management. Section 8: security considerations. Ellison, et al. Experimental [Page 3] RFC 2693 SPKI Certificate Theory September 1999 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 Acknowledgements section, including a list of contributors primarily from the start of the working group. [The archive of working group mail is a more accurate source of contributor information.] The Authors' Addresses section gives the addresses, telephone numbers and e-mail addresses of the authors. 1.1 Glossary We use some terms in the body of this document in ways that could be specific to SPKI: ACL: an Access Control List: a list of entries that anchors a certificate chain. Sometimes called a "list of root keys", the ACL is the source of empowerment for certificates. That is, a certificate communicates power from its issuer to its subject, but the ACL is the source of that power (since it theoretically has the owner of the resource it controls as its implicit issuer). An ACL entry has potentially the same content as a certificate body, but has no Issuer (and is not signed). There is most likely one ACL for each resource owner, if not for each controlled resource. CERTIFICATE: a signed instrument that empowers the Subject. It contains at least an Issuer and a Subject. It can contain validity conditions, authorization and delegation information. Certificates come in three categories: ID (mapping ), Attribute (mapping ), and Authorization (mapping ). An SPKI authorization or attribute certificate can pass along all the empowerment it has received from the Issuer or it can pass along only a portion of that empowerment. ISSUER: the signer of a certificate and the source of empowerment that the certificate is communicating to the Subject. KEYHOLDER: the person or other entity that owns and controls a given private key. This entity is said to be the keyholder of the keypair or just the public key, but control of the private key is assumed in all cases. PRINCIPAL: a cryptographic key, capable of generating a digital signature. We deal with public-key signatures in this document but any digital signature method should apply. Ellison, et al. Experimental [Page 4] RFC 2693 SPKI Certificate Theory September 1999 SPEAKING: A Principal is said to "speak" by means of a digital signature. The statement made is the signed object (often a certificate). The Principal is said to "speak for" the Keyholder. SUBJECT: the thing empowered by a certificate or ACL entry. This can be in the form of a key, a name (with the understanding that the name is mapped by certificate to some key or other object), a hash of some object, or a set of keys arranged in a threshold function. S-EXPRESSION: the data format chosen for SPKI/SDSI. This is a LISP- like parenthesized expression with the limitations that empty lists are not allowed and the first element in any S-expression must be a string, called the "type" of the expression. THRESHOLD SUBJECT: a Subject for an ACL entry or certificate that specifies K of N other Subjects. Conceptually, the power being transmitted to the Subject by the ACL entry or certificate is transmitted in (1/K) amount to each listed subordinate Subject. K of those subordinate Subjects must agree (by delegating their shares along to the same object or key) for that power to be passed along. This mechanism introduces fault tolerance and is especially useful in an ACL entry, providing fault tolerance for "root keys". 2. Name Certification Certificates were originally viewed as having one function: binding names to keys or keys to names. This thought can be traced back to the paper by Diffie and Hellman introducing public key cryptography in 1976. Prior to that time, key management was risky, involved and costly, sometimes employing special couriers with briefcases handcuffed to their wrists. Diffie and Hellman thought they had radically solved this problem. "Given a system of this kind, the problem of key distribution is vastly simplified. Each user generates a pair of inverse transformations, E and D, at his terminal. The deciphering transformation, D, must be kept secret but need never be communicated on any channel. The enciphering key, E, can be made public by placing it in a public directory along with the user's name and address. Anyone can then encrypt messages and send them to the user, but no one else can decipher messages intended for him." [DH] This modified telephone book, fully public, took the place of the trusted courier. This directory could be put on-line and therefore be available on demand, worldwide. In considering that prospect, Loren Kohnfelder, in his 1978 bachelor's thesis in electrical engineering from MIT [KOHNFELDER], noted: "Public-key communication works best when the encryption functions can reliably be shared among Ellison, et al. Experimental [Page 5] RFC 2693 SPKI Certificate Theory September 1999 the communicants (by direct contact if possible). Yet when such a reliable exchange of functions is impossible the next best thing is to trust a third party. Diffie and Hellman introduce a central authority known as the Public File." 2.1 First Definition of CERTIFICATE Kohnfelder then noted, "Each individual has a name in the system by which he is referenced in the Public File. Once two communicants have gotten each other's keys from the Public File they can securely communicate. The Public File digitally signs all of its transmissions so that enemy impersonation of the Public File is precluded." In an effort to prevent performance problems, Kohnfelder invented a new construct: a digitally signed data record containing a name and a public key. He called this new construct a CERTIFICATE. Because it was digitally signed, such a certificate could be held by non-trusted parties and passed around from person to person, resolving the performance problems involved in a central directory. 2.2 The X.500 Plan and X.509 Ten years after Kohnfelder's thesis, the ISO X.509 recommendation was published as part of X.500. X.500 was to be a global, distributed database of named entities: people, computers, printers, etc. In other words, it was to be a global, on-line telephone book. The organizations owning some portion of the name space would maintain that portion and possibly even provide the computers on which it was stored. X.509 certificates were defined to bind public keys to X.500 path names (Distinguished Names) with the intention of noting which keyholder had permission to modify which X.500 directory nodes. In fact, the X.509 data record was originally designed to hold a password instead of a public key as the record-access authentication mechanism. The original X.500 plan is unlikely ever to come to fruition. Collections of directory entries (such as employee lists, customer lists, contact lists, etc.) are considered valuable or even confidential by those owning the lists and are not likely to be released to the world in the form of an X.500 directory sub-tree. For an extreme example, imagine the CIA adding its directory of agents to a world-wide X.500 pool. The X.500 idea of a distinguished name (a single, globally unique name that everyone could use when referring to an entity) is also not likely to occur. That idea requires a single, global naming discipline and there are too many entities already in the business of defining names not under a single discipline. Legacy therefore militates against such an idea. Ellison, et al. Experimental [Page 6] RFC 2693 SPKI Certificate Theory September 1999 2.3 X.509, PEM and PGP The Privacy Enhanced Mail [PEM] effort of the Internet Engineering Task Force [RFC1114] adopted X.509 certificates, but with a different