Simple Public Key Certificate 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 Simple Public Key Certificate ------ ------ --- ----------- Status of This Document This document is one of three, superseding the draft filed under the name draft-ietf-spki-cert-structure-02.txt. The discussion and background from that previous draft is now to be found in draft- ietf-spki-cert-theory-01.txt. 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 Simple Public Key Certificate 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 Simple Public Key Certificate 21 November 1997 Abstract This document specifies 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 SPKI 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, it can lead to 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 Simple Public Key Certificate 21 November 1997 Table of Contents Status of This Document....................................1 Abstract...................................................3 Acknowledgments............................................3 Table of Contents..........................................4 1. Overview of Contents....................................6 2. Definitions.............................................7 2.1 Principal..............................................7 2.2 Keyholder..............................................7 2.3 Name...................................................8 2.4 Certificate............................................8 2.5 ACL Entry..............................................9 2.6 5-tuple...............................................10 2.7 S-Expression..........................................10 2.8 Prover................................................10 2.9 Verifier..............................................10 2.10 Validity conditions.................................11 3. Primitives.............................................12 3.1 Canonical S-expression................................12 3.2 .........................................12 3.3 S-expression..........................................13 3.4 Encoding examples.....................................13 3.5 Use of canonical S-expressions........................14 3.6 Non-canonical (advanced) S-expressions................14 3.7 Unique IDs............................................15 3.8 SPKI/SDSI 2.0 Objects.................................15 3.8.1 ...........................................16 3.8.2 ...........................................17 3.8.2.1 HMAC-MD5..........................................17 3.8.2.2 DES-CBC-MAC.......................................17 3.8.3 ..............................................18 3.8.4 .........................................19 3.8.5 ...............................................19 3.8.6 ..........................................20 4. Authorization Certificate..............................21 4.1 .............................................21 4.2 ........................................21 4.3 ..............................................22 4.4 ..........................................22 4.5 .............................................22 4.5.1 ..............................................23 4.5.2 ..........................................23 4.5.3 ...........................................24 4.5.4 .........................................24 4.5.5 .......................................25 Ellison, et al. [Page 4] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 4.6 .........................................26 4.7 ...............................................26 4.8 .................................................26 4.9 ...............................................27 4.9.1 ..............................................28 4.9.2 .......................................28 4.10 ............................................29 5. Name certificate.......................................30 5.1 Name cert syntax......................................30 5.2 Name reduction........................................31 6. On-line test reply formats.............................32 6.1 CRL and delta-CRL.....................................32 6.2 Revalidation..........................................32 6.3 One-time revalidation.................................33 7. 5-Tuple Reduction......................................34 7.1 <5-tuple> BNF.........................................34 7.2 Bare-bones case.......................................35 7.3 Intersection of *-form tag sets.......................35 7.4 Reduction of SDSI names...............................36 7.4.1 Simple SDSI name reduction..........................37 7.4.2 SDSI name composition with subject name growth......37 7.5 Reduction of (subject (threshold ..)).................37 7.5.1 Left-to-right.......................................38 7.5.2 Right-to-left.......................................39 7.6 Authorization Loops...................................39 7.7 Certificate Result Certificates.......................40 8. Full BNF...............................................41 8.1 Top Level Objects.....................................41 8.2 Alphabetical List of BNF Rules........................41 9. Other Certificate Formats..............................44 References................................................45 Authors' Addresses........................................47 Expiration and File Name..................................48 Ellison, et al. [Page 5] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 1. Overview of Contents This document contains the following sections: Section 1: this overview. Section 2: Definition of terms. Section 3: Primitives. Section 4: Authorization certificate. Section 5: Name certificate. Section 6: On-line test reply formats. Section 7: Reduction rules. Section 8: Full BNF. Section 9: Other certificate forms. 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 6] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 2. Definitions If the reader is familiar with older forms of certificate and encountering SPKI for the first time, it is important to bear in mind that older certificates had as their purpose the binding of a public key in cyberspace to a person in 3D space via his or her name in some global namespace. Those older certificate descriptions kept the reader firmly planted in 3D space. All operations referred back to entity names. By contrast, SPKI is a child of the 1990's. The reader needs to be firmly planted in cyberspace. SPKI binds together public keys in cyberspace and only rarely refers to 3D space or a namespace related to 3D space. Finally, SPKI rejects the notion of a global namespace, having determined that names in such a space can not be meaningful to users. Instead, when SPKI uses names, they are defined in a local namespace, meaningful by definition to the creator of that namespace and not necessarily of significance to anyone else. 2.1 Principal 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. Note that the secure hash of a public key is a global name for that key and, by implication, for the associated private key and, by another level of induction, for the holder of that private key. 2.2 Keyholder By KEYHOLDER, we mean an entity in the 3D 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 or by the hash of that public key. If K1 is a principal (key or key hash), the construct (keyholder K1) refers to this 3D world entity. Therefore, while we speak of a message signed by the principal K1, the message author was probably (keyholder K1). Ellison, et al. [Page 7] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 2.3 Name By NAME (formally "SDSI Name") we mean a string of the form (K1 N1 N2 ... Nk) where 1 <= k. Every name is a name in some namespace. We give no special credance to a global namespace (such as the domain name space, DNS), but rather treat it as just another local namespace. Truly local namespaces have a special place in SPKI/SDSI on the assumption that, like a private address book, the names in a local namespace are meaningful to the creator of the namespace. We identify each namespace by a principal (the principal that signs certificates for that namespace). Names of the form (K1 N) are names in K1's namespace. Each such name evaluates to one or more principals -- e.g., {K2, K3}. When a name evaluates to one principal, we tend to think of it as the name of an individual keyholder, while when it evaluates to multiple principals, we call it a group name. However, the two cases use the same syntax. An individual name is a group name with one member in the group. Letting "->" stand for a name definition, if we have (K1 N1) -> K2 and (K1 N1) -> K3, then (K1 N1 N2) -> (K2 N2) and (K1 N1 N2) -> (K3 N2). Note that this definition of name includes an X.509 or DNSSEC certificate chain naturally. Through this definition, one can refer to existing X.509 or DNSSEC names from inside an SPKI certificate. One can also refer to PGP names in this manner, although the richness of PGP's web of trust is lost by following a single certification thread as this form of name implies. That is, a PGP name assignment is considered valid if there are numerous enough, short enough certificate chains from the verifier's key to the target (name,key) PGP certificate. Any single chain can be expressed simply as a SDSI name sequence, but the fault tolerance and special trust model of PGP is lost in the process. 2.4 Certificate In [KOHNFELDER], Loren Kohnfelder defined CERTIFICATE as a digitally signed record containing a name and a public key. The name was assumed to identify unambiguously a given person: the keyholder of that key. We have realized that in any community beyond a small company common names can not be used as identifiers because they are likely to be ambiguous and persons identified by name are not likely to mean anything to a trust computation. Therefore, we generalize the word CERTIFICATE to be a signed record that binds some characteristic we Ellison, et al. [Page 8] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 care about to a principal or set of principals. Specifically, we define two basic forms of this general certificate in this document: a name certificate (binding a name in the issuer's namespace to a principal or group of principals) and an authorization certificate (binding an authorization (permission) to a principal or group of principals). A prior version of this spec did not separate those two forms, but in the interest of clarity of explanation and implementation, we have separated them here. The parts of any certificate necessary for trust computations can be expressed as up to five fields: Issuer, Subject, Delegation, Authorization and Validity. The ISSUER generates and signs the certificate. The SUBJECT is the principal or set of principals to which the certificate grants its name or authorization. DELEGATION is a boolean, indicating if TRUE that the Subject is allowed to delegate the specified Authorization further. AUTHORIZATION is a structured field expressing the authorization that this certificate grants to the Subject. VALIDITY is some combination of dates or on-line tests specifying the validity period/conditions of the certificate. 2.5 ACL Entry An ACL entry, as we use the term, evolved from the entries one finds in an Access Control List. More precisely, it is an unsigned authorization certificate in which the Issuer is not specified because it is assumed to be "self", referring to the machine on which the ACL entry is used. A machine (its trust computation engine) is assumed to have multiple ACL entries, referring to multiple Subjects and/or multiple kinds of authorization. The ACL entry does not need to be signed, because it is held in protected storage. Every trust engine needs at least one ACL entry because there is no one trusted source of all authorizations. Even if there were, the trust engine would need a record if that principal and that record would constitute an ACL entry. Ellison, et al. [Page 9] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 2.6 5-tuple There are up to 5 fields of any certificate or ACL entry necessary for a trust computation. These are: Issuer, Subject, Delegation, Authorization and Validity. These fields, taken together, are called a "5-tuple". This document gives the rules for combining 5-tuples ("reducing" them) to yield a final 5-tuple giving trust results. The final 5-tuple will be of the form: in which Subject is a single principal, Delegation is of no use (at the end of the computation), Authorization is the quantity most of interest and Validity needs to include the present datime. This final 5-tuple makes the statement "I (self) have determined that Subject is authorized to do (Authorization) at this time". 2.7 S-Expression 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. 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. 2.8 Prover 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. 2.9 Verifier By VERIFIER, we mean an entity which processes certificates, together with its own ACL entries, to determine if the prover deserves access Ellison, et al. [Page 10] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 or if some signed document is valid. The verifier is most likely unattended software. 2.10 Validity conditions 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 a validity period which is the intersection of the date ranges of the two data items (usually equalling 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 have been revoked. Periodic revalidation a reassurance of validity for one specific certificate. One-time revalidation a statement that for this one transaction, the indicated certificate is valid. [Instead of having a validity date range of its own, a one-time revalidation server receives a random nonce from the verifier and returns the validity result together with that nonce, digitally signed. The resulting validity period is formally that of the one trust computation and no more. This is as close as we can come to a 0-length validity period revalidation. It has the benefit of not requiring clock synchronization.] A one-time revalidation can also have side effects -- e.g., refer to a bank balance. Ellison, et al. [Page 11] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 3. Primitives We have chosen a simplified form of S-expression (the canonical form) as the format for SPKI objects. An S-expression is a list enclosed in matching "(" and ")". We assume the S-expression technology of [SEXP] with the restrictions that no empty lists are allowed and that each list must have a byte-string as its first element. That first element is the "type" or "name" of the object represented by the list. SPKI objects are defined below in a familiar extension of BNF -- with "*" meaning closure (0 or more occurrences), "?" meaning optional (0 or 1 occurrence) and "+" meaning non-empty closure (1 or more occurrences). First we define the canonical S-expression form in that BNF. 3.1 Canonical S-expression We define a canonical S-expression as containing binary byte strings each with a given length and punctuation "()[]" for forming lists. The length of a byte string is a non-negative ASCII decimal number, with no unnecessary leading "0" digits, terminated by ":". We further require that there be no empty lists and that the first list element be a byte string (as defined below). This form is a unique representation of an S-expression and is used as the input to all hash and signature functions. If canonical S-expressions need to be transmitted over a 7-bit channel, there is a form defined for base64 encoding them. 3.2 A byte string is a binary sequence of bytes (octets), optionally modified by a display type. If the byte-string is used as a binary integer, these bytes are twos-complement, in network standard order (most significant byte first). It is up to the application whether these are considered signed or unsigned. All byte strings carry explicit lengths and are therefore not 0- terminated as in the C language. They are treated as binary even when they are ASCII, and can use any character set encoding desired. Typically, such a choice of character set would be indicated by a display type. A display type is assumed to be a MIME type giving optional Ellison, et al. [Page 12] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 instructions to any program wishing to display or use the byte string. For example, it might indicate that the string is in UNICODE, is a GIF or JPEG image, is an audio segment, etc. Although the display type of a byte string is optional, it is considered part of the string for any equality comparisons or hashing. A byte-string is defined by: :: | ; :: ":" {binary byte string of that length} ; :: * | "0" ; :: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; :: "0" | ; :: "[" "]" ; 3.3 S-expression An S-expression is of the form: :: "(" * ")" ; :: | ; where the first byte string in the S-expression is referred to here as its "type". 3.4 Encoding examples (4:test26:abcdefghijklmnopqrstuvwxyz5:123455::: ::) is a canonical S-expression consisting of four byte strings: "test", "abcdefghijklmnopqrstuvwxyz", "12345" and ":: ::". The advanced text form is: (test abcdefghijklmnopqrstuvwxyz "12345" ":: ::") showing that the advanced form follows familiar token recognition rules, not permitting tokens to start with digits, terminating them with white space or punctuation marks. For transmission of true 8-bit forms, we permit base64 encodings according to [RFC2045], with the base64 characters enclosed in braces. The example above encodes to: {KDQ6dGVzdDI2OmFiY2RlZmdoaWprbG1ub3BxcnN0dXZ3eHl6NToxMjM0NTU 6OjogOjop} Ellison, et al. [Page 13] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 3.5 Use of canonical S-expressions Canonical S-expressions were designed to be as simple to pack and parse as possible. Some concessions were made to those developers who might want to examine a canonical S-expression in an ASCII editor like emacs (specifically the readable decimal length fields and readable "()[]" characters) but in general the form is as close to minimum size as possible. Parsing of a canonical form S-expression requires minimal look-ahead and no re-scanning of incoming bytes. As a result, the parsing code remains very small. Assuming each byte string is stored with a length field, generation of a canonical form from a data structure requires an extremely small amount of code. The canonical S-expression is the form which is hashed for both generating and verifying signatures. These two processes can be thought of as the start and end of an SPKI object's useful life and both require canonical form. Therefore, it is recommended that the canonical form be the form transmitted and stored in normal use, to be converted temporarily to and from a more readable form by display or editing applications written for the purpose. [Violating that suggestion, this document includes some advanced (non-canonical) forms, for readability. Since this document is required to be straight ASCII, no pure 8-bit canonical forms will be presented except under base64 encoding.] 3.6 Non-canonical (advanced) S-expressions [SEXP] includes a general purpose utility program for converting between canonical and advanced S-expression form. In the advanced form, individual byte strings may be expressed without length fields (if they are what most languages consider text tokens), may be written as quoted strings (under normal C string rules), or may be individually hex or base64 encoded. Also in the advanced form, extra white space between list elements is allowed for readability and ignored on conversion to canonical form. For examples this document will normally use the advanced form, because of its readability, but for at least one concrete example the canonical form and its hash are presented (base64 encoded where necessary). In these examples, we will use keywords without preceding length fields, quoted strings, hex values (delimited by "#") and base64 values (delimited by "|"). Those are features of the advanced transport form of an S-expression, and are not part of the canonical form. We will always present the canonical form (base-64 encoded, when it contains non-ASCII characters) which the reader can decode to Ellison, et al. [Page 14] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 get the actual canonical form. 3.7 Unique IDs Top level object names are defined in this document along with certain algorithm names. objects are user-defined, using a language for describing sets of permissions given here, and in the process, the defining user can choose any object names he or she wishes. For the definition of new algorithm names, it is our preference that this be taken on by IANA for single-word standard names. In the interest of maximum flexibility we also permit users to define their own algorithm names via a normal URI's (which presumably point to descriptions of the algorithms or even code). 3.8 SPKI/SDSI 2.0 Objects The objects defined in SPKI/SDSI 2.0 are S-expressions. That is they are lists of either byte strings or other lists. In our case, all S-expressions start with a , called the object name. The remaining elements of the list are called "parts" of the object. In a communication from prover to verifier, one might encounter only a small number of different objects: usually a of , , , and . The verifier will also need to refer to its own . These are considered top level objects and are defined in the sections immediately following It is standard SPKI/SDSI practice to use names starting with a lower case letter, followed by lower case letters, digits and hyphens for object types. SPKI/SDSI is case-sensitive, so the byte-string "RSA" is not the same as "rsa". Non-standard object types (i.e. s defined by an application developer) are unconstrained, may have display types and may even be URI's pointing to documentation of the object type. The structure and interpretation of the parts is up to the designer of the top-level object type. However, for the sake of simplification, we have decided that all objects are "positional". That is, their parts are listed in some fixed order with meaning of the part depending on its position. Parts can be omitted only by omitting a contiguous set of trailing parts. The following are the definitions of the top level objects which a Ellison, et al. [Page 15] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 verifying program may encounter. Note that the main object, cert, is sub-type based so the parameter fields may be in any order, but the BNF suggests a fixed order. We use the BNF definition to indicate that there may not be more than one of each of the listed fields, and also to suggest (for readability) that the cert parts be presented in the order given. This document will use that order. 3.8.1 :: "(" "public-key" * * ")" ; A public key definition gives everything the user needs to employ the key for checking signatures. The only pub-sig-alg-id's we have defined at this point are for signature verification. That is because we need only signature keys for certificate formation and access control. Other key types are open to being defined by users. The following is an RSA signature key, shown in advanced transport format: (public-key rsa-pkcs1-md5 (e #03#) (n |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| )) For actual use, the key is held and presented in canonical form the base64 encoding of which is: {KDEwOnB1YmxpYy1rZXkxMzpyc2EtcGtjczEtbWQ1KDE6ZTE6AykoMTpuMTI 5OgDRwhvOY1xRponK9zBj4+dxWGEmNWlgLnujyp6RRKx4SjCWuB6yuFkikzm E05WqUc55xCw9g+5Vnd0PDw9JcotTSaTczJMUFR66wJyEKHM3jmbos/8mFQ8 ydQ3YiJoscm/ycpntw9FIlF4XelRgM9MdHIKynnyp5o8uNdCq6N7ltSkp} Although not strictly needed by this draft, the private key for the public key above is: (private-key rsa-pkcs1-md5 (e #03#) (n |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| ) (d |AIvWvTRCPYvEW9ykyu1CmkuQQMQjm5V0Um0xvwuDHaWGyw8lacx65hcM0 QM3uRw2iaaCyCkCnuO+k19fX4ZMXOD7cLN/Qrql8Efx5mczcoGN+Eo6FF+ cvgXfupe1VM6PmJdFIauJerTHUOlPrI12N+NnAL7CvU6X1nhOnf/Z77iz| ) (p |APesjZ8gK4RGV5Qs1eCRAVp7mVblgf13R5fwApw6bTVWzunIwk/2sShyy tpc90edr+0DPwldnvEXTUY1df0DwPc=|) (q Ellison, et al. [Page 16] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 |ANjPQe6O0Jfv90GWE3q2c9724AX7FKx64g2F8lxgiWW0QKEeqiWiiEDx7 qh0lLrhmBT+VXEDFRG2LHmuNSTzj7M=|) (a |AKUds79qx62EOmLIjpW2AOb9EOSZAVOk2mVKrGgm83jkifEwgYqkdhr3M ebopNppH/NXf1uTv0tk3i7OTqitK08=|) (b |AJCKK/RfNbqf+iu5YlHO9+n56q6nYx2nQV5ZTD2VsO54KxYUcW5sWtX2n xr4YydBEA3+46CsuLZ5cvvJeMNNCnc=|) (c |CIPwAAO8Vmj0/BfCtsg+35+r94jwxGYHZ63RsqyNxbvkAO6xPqSht8/vz dR93eX5B9ZKBQg1HHWCsHbqQtmNLQ==|)) where a, b and c are CRT parameters. 3.8.2 :: "(" "secret-key" * * ")" ; 3.8.2.1 HMAC-MD5 Example: (secret-key hmac-md5 (k |ksTt2Lu9NSq3mGHJ7HmuksSYwFQ=|) ) which has a base64 encoded canonical form: {KDEwOnNlY3JldC1rZXk4OmhtYWMtbWQ1KDE6azIwOpLE7di7vTUqt5hhyex 5rpLEmMBUKSk=} The hmac-md5 and hmac-sha1 algorithms are defined in [RFC2104]. 3.8.2.2 DES-CBC-MAC Example: (secret-key des-cbc-mac (k |52Lyr9BPTSM=|) (nonce |v1jBW9SlFxAweNyYSzaMfHOzwds=|)) with base64 encoded canonical form {KDEwOnNlY3JldC1rZXkxMTpkZXMtY2JjLW1hYygxOms4Oudi8q/QT00jKSg 1Om5vbmNlMjA6v1jBW9SlFxAweNyYSzaMfHOzwdspKQ==} provides the DES key for a DES-CBC MAC. It also includes a nonce Ellison, et al. [Page 17] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 parameter which plays no part in the algorithm, but serves to insulate this key from brute force attacks using the published hash of the (secret-key...) canonical S-expression: (hash md5 |ilTuqvT5/AdeX/sfxA9lgQ==| examples/des.bin) with base64 encoded canonical form {KDQ6aGFzaDM6bWQ1MTY6ilTuqvT5/AdeX/sfxA9lgTE2OmV4YW1wbGVzL2R lcy5iaW4p} 3.8.3 :: "(" "hash" ? ")" ; A object gives the hash of some other object. For example, the public key given above has the following hash: (hash md5 #92e5f2ab1f23616759fe3ed57dfafeca#) or (hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|) which, in base64 encoded canonical form, is {KDQ6aGFzaDM6bWQ1MTY6kuXyqx8jYWdZ/j7Vffr+yik=} A hash of the hmac-md5 secret key defined above is: (hash md5 #33b7035665f7af8c6669bdabc58ab236#) or (hash md5 |M7cDVmX3r4xmab2rxYqyNg==|) which, in base64 encoded canonical form, is {KDQ6aGFzaDM6bWQ1MTY6M7cDVmX3r4xmab2rxYqyNik=} This is perhaps of more interest than the hash of the public key because a certificate generally released to the public can not contain a secret key, for obvious reasons, but it might contain the hash of the secret key without fear of loss of the secret. Ellison, et al. [Page 18] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 3.8.4 :: "(" "signature" ")" ; A signature object is typically used for a certificate body and typically follows that object in a . We chose not to define an object containing the cert body and signature, since there may be cases when the same cert body needs to be signed by multiple keys. One can also sign objects other than cert bodies, of course. For example, one can form the signature of a file. 3.8.5 :: "(" "acl" ? * ")" ; :: "(" "entry" ? ? ? ")" ; An ACL is a list of assertions: certificate bodies which don't need issuer fields or signatures because they are being held in secure memory. Since the fields of the ACL are fields of a , we will not repeat those common field definitions here. If all the optional fields are left out, the subject is given the permission specified in , without permission to delegate it, with no expiration date or condition (until the ACL is edited to remove the permission). For example: (acl (entry (name (hash md5 |p1isZirSN3CBscfNQSbiDA==|) sysadmin/operators) (tag (ftp db.acme.com root)) ) (entry (hash md5 |M7cDVmX3r4xmab2rxYqyNg==|) (tag (ftp db.acme.com root)) ) (entry (hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|) (propagate) (tag (http http://www.internal.acme.com/accounting/)) ) ) Ellison, et al. [Page 19] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 3.8.6 :: "(" "sequence" * ")" ; :: | | | ; :: | ; :: "(" "do" "hash" ")" ; :: "(" "do" * ")" ; A is a bundled sequence of objects which the verifier is to consider when deciding to grant access. We anticipate requiring the prover (who constructs and submits the ) to provide elements in order, so that the verifier need only process the in order to prove to itself that the prover has the claimed access right. The sequence can also contain instructions to the verifier, in the form of opcodes. At present the only opcode defined is "hash" -- meaning, that the previous item in the sequence (the last one read in) is to be hashed by the given algorithm and saved, indexed by that hash value. Presumably, that item (certificate body or public key, for example) is referred to by hash in some subsequent object. At this time, we assume that a (signature ) block following a cert body in a sequence will call for that cert body to be hashed by the algorithm indicated in the signature. If an object will be referenced by different hashes, it can be followed by multiple (do hash ..) opcodes. Ellison, et al. [Page 20] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 4. Authorization Certificate :: "(" "cert" ? ? ? ? ? ? ? ")" ; The basic certificate form is an authorization certificate. It transfers some specific authorization or permission from one principal to another. Because a certificate merely transfers authorizations, rather than creating them, the form we call ACL-entry is also defined below to inject authorizations into a chain of certificates. An ACL entry lives on the machine of the verifier, leading to the observation that all authorization flow is in loops -- from the verifying machine, through certificates back to the verifying machine. Alternatively, one might say that the only root of an authorization certificate chain is the verifier. 4.1 :: "(" "version" ")" ; Version numbers are alphanumeric strings. If the field is missing from an object, it is assumed to be (version V0), which is the version of all objects in this draft. Elaboration of version numbers, possibly with multiple fields, are left for later to define. It is assumed that a verifier, when encountering a structure it doesn't know how to parse (because it has a version number it doesn't recognize), will ignore that object. 4.2 :: "(" "display" ")" ; This optional field gives a display hint for the entire certificate. This display parameter does not affect certificate chain reduction, but is provided to aid user-interface software in certificate display. At this time, we have no such hints defined. This field is up to developers to define as they see fit. Ellison, et al. [Page 21] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 4.3 :: "(" "issuer" ")" ; :: | ; This rules out issuers, since an explicit as an issuer offers no security to the cert. However, one may have a field that is the hash of a as the issuer, for a cert where the only verifiers are in possession of the secret key. 4.4 :: "(" "issuer-info" * ")" ; The (issuer-info ) object provides the location of the cert(s) by which the issuer derives the authority to pass along the authorization in the present . We expect the prover (the calling client) to track down such other certs and provide them to the verifier (the called server), but we allow this information in the cert to simplify that process for the prover. 4.5 :: "(" "subject" ")" ; :: | | | | | ; In the most basic form, a subject is a principal. However, it may also be a name, representing a group of principals or a delayed binding to some one principal. In some certs, the subject is not reducible directly to principal(s). It may be the hash of an object or a reference to some keyholder (that is, some person or other entity in 3D space). It may also be a K-of-N threshold of principals (in which case, the authorization being granted to the subject is being spread out among multiple parties that must cooperate to exercise that authorization). Ellison, et al. [Page 22] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 4.5.1 The primary addition to the possibilities for is a SDSI name. This can be either a relative name or a fully-qualified name. :: | ; :: "(" "name" ")" ; :: "(" "name" ")" ; :: + ; For evaluation purposes, the relative name is translated into a fully-qualified name by using the key of the issuer. Unlike the SDSI name, which is forced to be a name in the issuer's name space, the subject name can be in any name space. (subject (name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred sam george mary)) refers through "fred" defined in the name space of |Txoz1GxK/uBvJbx3prIhEw==|, to reduce to: (subject (name (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|) sam george mary)) recursing until the subject reduces to a key. This construct allows deferred binding of keys to names, while the bare-bones SPKI format forces binding of keys to names at the time the certificate is issued. In particular, the owner of any name space involved in such a SDSI name chain can replace an existing name definition after the cert above is issued, without affecting the validity of that cert or forcing it to be reissued. For that matter, the cert above can be issued before there is any definition of the referenced name. 4.5.2 :: "(" "object-hash" ")" ; This option for a (subject ) refers to an object other than a (or SDSI name reducing to a principal). One might use this form to assign attributes to an object (a file, a web page, an executable program, ...). Ellison, et al. [Page 23] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 4.5.3 :: "(" "secret-key" * * ")" ; A secret key can also be a Principal, in the formal sense, but we do not permit it to appear explicitly in an for obvious reasons. Most likely, a using a secret key will use the hash of the key, so that the cert could be published. In that case, the builder of may be well advised to include a (nonce ...) field, unused by the secret-key algorithm but hiding any key value from brute force searches via the published hash value. It is also possible to have split secret keys, as is popular in some banking applications: e.g., (secret-key des3-split-4 (a #ba1c9bd4#) (b #e747105c#) (c #7f62536b#) (d #0fa235f9#) ) could define a 2-key triple-DES key, in four parts. This key could be split among 4 different parties, via the S-expressions: (secret-key des3-split-4 (a #ba1c9bd4#) (nonce #5b30e629#) ) (secret-key des3-split-4 (b #e747105c#) (nonce #a5e71fe3#) ) (secret-key des3-split-4 (c #7f62536b#) (nonce #3c317d99#) ) (secret-key des3-split-4 (d #0fa235f9#) (nonce #7597d39e#) ) and each of those 4 partial keys could be given to a different party to hold, together with a certificate referring to the part by its hash, verifying its authenticity and its intended mode of use. That certificate might also include a key serial number as part of its tag field. 4.5.4 :: "(" "keyholder" ")" ; :: | ; This form of subject refers to the flesh and blood (or iron and silicon) holder of the referenced key. A with such a subject is saying something about that person or machine -- such as its location, its address, its age, its weight, its height, its picture, .... Ellison, et al. [Page 24] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 4.5.5 :: "(" "k-of-n" * ")" ; where the first int is K and the second is N, K < N, and there are N subjects listed. A threshold subject, introduced by Tatu Ylonen for SPKI and by Rivest and Lampson in SDSI 1.0, specifies N subjects for a certificate or ACL entry, of which K must agree before the permission is passed along. The actual intent is to insure that there are K distinct paths passing permission between the verifier's ACL and the prover's request. These multiple paths branch and re-join, so the k-of-n construct could theoretically be part of either the Subject or the Issuer. Since an ACL might want to specify these multiple paths (and an ACL has no Issuer) and since a cert is signed by a single Issuer, we have chosen to specify the branching at the Subject. A certificate or ACL with a k-of-n Subject does not delegate permission to any of those subjects, alone. Rather, each of these subjects receives a share of the delegated permission. Only if at least K of the N subjects show certificate paths which converge on a single target Subject during reduction, is that permission transmitted to the target. If fewer than K such paths can be shown, then the permission is not delegated. This construct is far from simple. However, it is extremely useful. It has been demanded by a number of initial customers of SPKI certificates. It also solves a number of sticky political problems. This section lays out the specification of K-of-N subjects. The rules for reducing 5-tuples containing such entries are given later. Examples of the use of K-of-N permission propagation include: 1. co-signing of electronic corporate checks or purchase orders above a certain amount 2. establishing the root DNSSEC key, bypassing the political battles which would inevitably ensue if one country were to hold *the* root key for the entire world. The same goes for any root key. 3. establishing a root key for a trusted service, via multiple algorithms. That is, one could have three root keys, using RSA, DSA and Elliptic Curve signature algorithms (for example), and require that two of them yield a valid chain. This way, if someone were to break an entire algorithm (find a way to invert the algorithm), much less if someone were to break one key in the set of three, the root remains securely established. At the same Ellison, et al. [Page 25] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 time, there is fault tolerance. In case one of the keys is revoked, the following certificates remain empowered. 4. using online and off-line issuers. One could have a permission established by an off-line key issuing a long-lived certificate and echoed by an online automated server, issuing short-lived certificates. The delegation of this permission could require both before the eventual subject gets the permission. This can be achieved through the use of (online ) tests in a long-lived certificate, but the K-of-N subject mechanism may be cleaner. 5. ultra-secure applications. There are many applications which follow the nuclear weapons launch scenario. That is, multiple agreement is required before the permission is granted. 4.6 :: "(" "subject-info" * ")" ; This optional field provides the location of information about the subject. For example, if the subject is a hash of a key, this might provide the location of the key being hashed. IF the subject is a SDSI name, it might give the location of a SDSI name cert server. 4.7 :: "(" "propagate" ")" ; This optional field, if present, notes that the has not only the permission given in the 's field but also the permission to delegate that (or some portion of it) to others. 4.8 :: "(" "tag" "(*)" ")" | "(" "tag" ")" ; The form (tag (*)) means "all permissions". The simplest tag is an S-expression with no *-forms. This is a specific permission which must be passed along and used intact. A tag with *-forms represents a set of specific permissions. Any subset of such a set of permissions may be delegated by a principal empowered to delegate. When one is reducing the 5-tuples from such Ellison, et al. [Page 26] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 certificates, one intersects the adjacent tag sets to find a resulting tag set. Full tag intersection rules are given later. All tags are assumed to be positional. That is, parameters in a tag have a meaning defined by their position. All tags are assumed to be extendable. That is, if one adds a field to the end of a tag definition, one is restricting the permission granted. [If the field added makes the tag invalid, then one has restricted the original permission to zero.] The full tag body BNF is: :: | | ; :: "(" * ")" ; :: "(" "*" "set" * ")" ; :: | | ; :: "(" "*" "range" ? ? ")" ; :: "alpha" | "numeric" | "time" | "binary" | "date" ; :: ; :: "g" | "ge" ; :: ; :: "l" | "le" ; :: "(" "*" "prefix" ")" ; 4.9 The field gives validity dates and/or on-line test information for the cert. :: ? ? ? ; :: "(" "not-after" ")" ; :: "(" "not-before" ")" ; The not-after and not-before options are self-explanatory. If either Ellison, et al. [Page 27] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 is missing, then the cert is assumed valid for all time in that direction. For example, one might omit the field, if that date would be before or at the time of creation of the cert, unless one wanted to note the creation time for documentary purposes. 4.9.1 :: ; A date field is an ASCII byte string of the form: YYYY-MM-DD_HH:MM:SS always UTC. For internal use, it is treated as a normal byte string. For example, "1997-07-26_23:15:10" is a valid date. So is "2001-01- 01_00:00:00". fields are compared as normal ASCII byte strings since one never needs to compute the size of a time interval to test validity -- only determine greater-than, less-than or equal. 4.9.2 :: "(" "online" * ")" ; :: "crl" | "reval" | "one-time" ; The online test option allows a cert to be backed up by finer grain validity testing. The reply from an online test is a digitally signed object, validated by the given in the test specification. That object includes validity dates, so that once one has the online test response, its validity dates can be intersected with the parent cert's validity dates to yield the current working validity dates for the cert. The crl form tells the verifier (or prover, who fetches this information for the verifier, in our standard model), the current list of invalid certs. If the present cert is not on that list, then the cert is presumed valid. The revalidate form is the logical opposite of the crl. It tells the verifier a list of valid certs -- or, just that the current cert is valid. The one-time form is a revalidate form without validity dates. It must be fetched by the verifier, rather than the prover, since it is valid only for the current verification step. [In effect, it has a Ellison, et al. [Page 28] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 validity period of just "now".] The process of getting this one-time revalidation involves sending a unique (and partly random) challenge which is returned as part of the signed response. See section 6 for a full description of on-line test request and reply formats. 4.10 :: "(" "comment" ")" ; This optional field allows the issuer to attach comments meant to be ignored by any processing code but presumably to be read by a human. Ellison, et al. [Page 29] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 5. Name certificate Names are defined for human convenience. For actual trust engine computations, names must be reduced to keys. This section gives the form of a name certificate and the rules for reducing name certificates to simple mappings from name to key. Note that we do not include an option for a name certificate. The issuer needs no authorization in order to create names. Every issuer has that right. Similarly, there is no "certification practice statement" for these name certificates. Nothing is implied by a name certificate about the principal(s) being named. There are no constraints on name choice. A name can be an arbitrary byte string assigned by the issuer. It is not required or expected necessarily to conform to any name string in the 3D world or in any other issuer's name space. That said, it is possible to map name certificates generated by a commercial Certification Authority into SDSI names and thus refer to keys defined in that world from within SPKI/SDSI certificates. 5.1 Name cert syntax A name certificate has the form: (cert (issuer (name )) (subject ...) ) :: "(" "cert" ? ? ")" ; :: "(" "issuer" "(" "name" ")" ")" ; That form maps directly into the intermediate form needed for name string reduction. The (tag) field is omitted and (tag (*)) is assumed. It is not syntactically possible to have delegation or authorization fields in a name cert. Delegation is always true, through a name chain, and authorization is always (*). A name definition is like an extension cord, passing everything the name is granted through to the subject. Ellison, et al. [Page 30] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 The subject is unrestricted. It is what you are trying to name. If there is more than one name certificate for a given name, with different subjects, then that name is a group. More specifically, all name certificates define groups, many of which will have only one member. A multi-member group is like a multi-plug extension cord, passing everything the name is granted through to all of its subjects. 5.2 Name reduction A name by itself is of little value. To be used, it must be reduced to a principal. The rules of reduction allow intermediate forms which grow in length, but the value of a name is a single principal (or set of principals). Name reduction produces principals from names. In the process, however, it can produce longer name strings. For example: <(K1 N1),(K2 N2 N3)> + <(K2 N2),K3> -> <(K1 N1),(K3 N3)> <(K1 N1),(K2 N2)> + <(K2 N2),(K3 N3)> -> <(K1 N1),(K3 N3)> <(K1 N1),(K2 N2 N4)> + <(K2 N2),(K3 N3 N5)> -> <(K1 N1),(K3 N3 N5 N4)> where K# are principals and N# are name strings. Ellison, et al. [Page 31] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 6. On-line test reply formats Given here is the BNF for on-line test replies. This section does not give details of protocols for connecting to online servers or transmitting messages between them. It is assumed that, for example, the requester can provide a URI and use HTTP, while the URI includes any parameters the requester needs to pass along. The reply from the on-line source will be in canonical form, according to the BNF given below. If a protocol is used other than HTTP, the (online ...) object includes optional fields which can be used to hold parameters for those tests (e.g., indicating which certificate is of interest, how to authenticate to the server, etc.). 6.1 CRL and delta-CRL The full or delta CRL is: :: "(" "crl" ")" ; :: "(" "canceled" * ")" ; :: "(" "delta-crl" ")" ; :: ; and should be signed by the principal indicated in the (online...) field which directed the CRL to be fetched. The CRL request can be a straight HTTP transaction, using the URI provided in the cert, but we do not specify online protocols in this draft. If the verifier has a complete CRL, then it can provide the hash of that CRL in whatever protocol is chosen and get back just the additions to the previous CRL, in the form of a 6.2 Revalidation :: "(" "reval" ")" ; :: "(" "cert" ")" ; Ellison, et al. [Page 32] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 This construct specifies the hash of the current cert as and gives a new validity period for that cert. It should be signed by the indicated in the (online...) field which directed it to be fetched. The reval request can be a straight HTTP transaction, using the URI provided in the (online...) field, but we do not specify online protocols in this draft. 6.3 One-time revalidation For one-time revalidation, the verifier itself must fetch the (reval) record, which will have the form: :: "(" "reval" ")" ; :: "(" "one-time" ")" ; with the byte string inside being one provided by the caller, expected to be unique over time and unguessable -- e.g., a large random number or random number plus sequence number. This reply should be signed by the indicated in the (online..) field which directed it to be fetched. This result, if successful, yields a Validity value for the 5-tuple of "now". Ellison, et al. [Page 33] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 7. 5-Tuple Reduction This section describes the operation of the trust evaluation machinery assumed to be part of every verifier which accepts SPKI certificates. The inputs to that trust engine are 5-tuples and any kind of certificate, not just SPKI, as well as Access Control List (ACL) entries can be translated to 5-tuples so that they can all participate in the trust computation. A 5-tuple is an internal construct and therefore best described by a programming language data structure. A separate document will give the 5-tuple reduction code and those data structures. For this purpose, we describe the content in BNF, but want to make sure that a 5-tuple will never be expressed in canonical BNF form, transmitted in that form, etc. The <5-tuple> differs from a by leaving out some fields of an authorization cert and by including some absent fields for a name cert. 7.1 <5-tuple> BNF A 5-tuple is a positional construct of the form: <5-tuple>:: ; :: | | "self" ; :: | | | | ; :: "t" | "f" ; :: | ; :: "(" "name" ")" ; :: "(" "name" ")" ; :: | "null" ; :: | "null" ; Standard implementations are expected to store keys (and other bulky things) only once and refer to them by pointer. This permits us to use keys directly rather than hashes of keys while doing 5-tuple reduction. This also permits us to reduce certs which used the same key but referred to it by different hash algorithms. Ellison, et al. [Page 34] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 The extra option for issuer, "self", is provided for ACL entries. The self referred to is the verifier, holding that ACL and doing the verification of offered proofs. The only 5-tuples that can mean anything to the verifier, after reduction is done, are those with "self" as issuer. 7.2 Bare-bones case In a bare-bones SPKI cert, the only issuer and subject fields allowed are principals which are keys. The tag fields a_i are *-free S- expressions or the form (tag *). + yields if: s1 = i2 d1 = "t" a = the intersection of a1 and a2 v = the intersection of v1 and v2 Validity intersection involves normal intersection of date ranges, if there are not-before or not-after fields in v1 or v2, and union of on-line tests, if those are present in v1 or v2. Each on-line test includes a validity period, so there is a resulting validity interval in terms of dates. This can include the string "now", as the product of a one-time on-line test result. "now" intersects with any date range including the present to yield "now". If v is an empty time interval, then the certificates don't reduce. The intersection of a1 and a2 in the basic case is given by the following rules: If a1 is (tag (*)), a = a2. If a2 is (tag (*)), a = a1. If a1 == a2, a = a2. Otherwise, a = "null" and the 5-tuple doesn't reduce. 7.3 Intersection of *-form tag sets It is assumed that normal verification will proceed from right to left -- that is, that a specific desired result tag will be intersected with a general tag. Therefore, the only intersection rules needed are those between *-forms and *-free tag elements. Such an intersection will yield either "null" or a *-free tag. Ellison, et al. [Page 35] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 The intersection rules are intuitive and recurse down into tag S- expressions and along lists. (* set ...): a *-free intersects with a (* set ...) to yield the *-free if that expression is an element of the set. (* range ...): a *-free intersects with a (* range ...) to yield the *- free if the expression is a byte string contained within the specified range. Otherwise, the intersection fails. (* prefix ...): a *-free intersects with a (* prefix S1) to yield the *- free if the expression is a byte string starting with string S1. Otherwise, the intersection fails. 7.4 Reduction of SDSI names By the rules for bare-bones SPKI 5-tuple reduction, + yields if: s1 = i2 d1 = "t" For the purpose of this section, we consider only the first two elements of the 5-tuple: the issuer and subject. + yields if: s1 = i2 With the introduction of SDSI names, both Issuer and Subject names are mapped to fully qualified SDSI names: (name N_1 .. N_k) where k can be 0, in which case we have (name ). An Issuer always maps to a single name or single while a Subject may have a SDSI name chain longer than 1. The introduction of SDSI names causes this reduction rule to be modified to become: + yields Consider the general case: Ellison, et al. [Page 36] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 <(name k1 r_1),(name k2 n_1 .. n_m)> + <(name k2 n_1),(name k3 t_1 .. t_u)> where n_1 is assumed to be the same on both sides of the + operator. The reduction is then: <(name k1 r_1),(name k3 t_1 ... t_u n_2 ... n_m)> 7.4.1 Simple SDSI name reduction The most basic SDSI case is the definition of a single name as a key: <(name k1 fred),(name k2)> One can then do the reduction: + <(name k1 fred),(name k2)> = 7.4.2 SDSI name composition with subject name growth One is not limited to define local names as keys. They can be defined as other names. For example, <(name k1 fred), (name k2 joe brother)> which would lead to the "reduction": + <(name k1 fred), (name k2 joe brother)> = With this form of SDSI name definition allowed, any flood-style 5- tuple reduction software must be careful to detect and not allow infinite loops of names. Algorithms to find certificate paths and avoid such loops have been developed by Ron Rivest and his SPKI implementers, so we know that such are possible. 7.5 Reduction of (subject (threshold ..)) There are at least two ways to reduce a set of certificates including a (subject (threshold ...)): from left to right and from right to left. Ellison, et al. [Page 37] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 7.5.1 Left-to-right One plan for processing of k-of-n subjects introduces new opcodes for the (do ...) construct. Let us assume K=7 and N=12. We assume a primary "stack" for 5-tuples which never exceeds a depth of 2 for other reductions, but needs to be a real stack for this one. (cert ... (k-of-n ...)) arrives and is held on a separate stack. (do subject #01#) pulls a copy of the k-of-n cert from the separate stack and activates subject #1. So, the k-of-n 5-tuple acts like a normal, single- subject 5-tuple. It acquires a record noting which subject is active, so that at eventual reduction time, the code can verify that K different subjects were used. Normal 5-tuple reduction proceeds until the reduced subject field is the merge point of these K separate threads of certificates. Then the opcode (do subject #02#) brings one copy of the k-of-n 5-tuple from the top of the auxiliary stack and selects another subject. At this point, another thread can be reduced to the common (merge-point) subject. Whenever two threads have been reduced to 5-tuples on the primary stack, the opcode (do k-of-n) merges the top 2 items of the primary 5-tuple stack, verifying that their reduced subjects are equal and intersecting their tag and validity fields. At the end of the K thread reductions, the final (do k-of-n) yields the final result 5-tuple from the K different threads. At this point, (do pop-aux) pops the k-of-n 5-tuple from the auxiliary stack. Ellison, et al. [Page 38] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 7.5.2 Right-to-left If we choose to process k-of-n certs right-to-left, then all K cert threads to the right of the k-of-n cert are processed first. This requires the opcode: (do push) to move the current (R-to-L) 5-tuple result to the top of the auxiliary stack. (do copy) copies the current 5-tuple from the top of the auxiliary stack to the top of the normal stack and normal cert processing proceeds, up to the point where the k-of-n cert would be required. At this point, another (do copy) fetches another copy of the right end of this thread (the merge point) and another cert thread is processed. When all K threads are processed, the k-of-n cert is presented, the auxiliary stack is popped, and the k-of-n cert combines with the K 5-tuples on the stack below it, to yield a single 5-tuple or a "null" result. At this point, each of the K 5-tuples on the stack below the k-of-n cert will have to have the same subject field and an issuer field to match one of the k-of-n cert's subject fields. 7.6 Authorization 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 Ellison, et al. [Page 39] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 chain reduction and is therefore at the receiving end of the chain as well, that makes all useful authorization chains loops. 7.7 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 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. Ellison, et al. [Page 40] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 8. Full BNF 8.1 Top Level Objects The list of BNF rules that follows is sorted alphabetically, not grouped by kind of definition. The top level objects defined are: <5-tuple>: an object defined for documentation purposes only. The actual contents of a 5-tuple are implementation dependent. : an object for local use which might be implementation dependent. An ACL is not expected to be communicated from machine to machine. , and : objects returned from on-line tests. : the object carrying keys and certificates from machine to machine. 8.2 Alphabetical List of BNF Rules <5-tuple>:: ; :: "(" "entry" ? ? ? ")" ; :: "(" "acl" ? * ")" ; :: | ; :: ":" {binary byte string of that length} ; :: "(" "display" ")" ; :: "(" "cert" ? ? ? ? ? ? ? ")" ; :: "(" "comment" ")" ; :: "(" "crl" ")" ; :: ; :: "0" | ; :: * | "0" ; :: "t" | "f" ; :: "(" "propagate" ")" ; :: "(" "delta-crl" ")" ; :: "[" "]" ; :: "(" "name" ")" ; :: "(" "name" ")" ; :: "(" "do" * ")" ; :: "g" | "ge" ; :: "md5" | "sha1" | ; :: "(" "canceled" * ")" ; Ellison, et al. [Page 41] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 :: ; :: ; :: "(" "do" "hash" ")" ; :: ; :: "(" "hash" ? ")" ; :: "(" "name" ")" ; :: "(" "issuer-info" * ")" ; :: "(" "issuer" "(" "name" ")" ")" ; :: | | "self" ; :: "(" "issuer" ")" ; :: ; :: | ; :: | ; :: "(" "keyholder" ")" ; :: ; :: "l" | "le" ; :: ; :: "(" "cert" ? ? ")" ; :: | ; :: + ; :: "(" "not-after" ")" ; :: "(" "not-before" ")" ; :: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; :: "(" "object-hash" ")" ; :: "(" "one-time" ")" ; :: "(" "online" * ")" ; :: "crl" | "reval" | "one-time" ; :: | ; :: | ; :: "(" "public-key" * * ")" ; :: "rsa-pkcs1-md5" | "rsa-pkcs1-sha1" | "dsa-sha1" | ; :: "alpha" | "numeric" | "time" | "binary" | "date" ; :: "(" "name" ")" ; :: | ; :: "(" "reval" ")" ; :: "(" * ")" ; :: | ; :: "(" "secret-key" * * ")" ; :: "hmac-md5" | "hmac-sha1" | "des-cbc-mac" | ; :: | | | | ; :: "(" "sequence" * ")" ; :: ; :: "(" "signature" ")" ; :: "(" * ")" ; :: "(" "cert" ")" ; :: | | | | Ellison, et al. [Page 42] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 | ; :: "(" "k-of-n" * ")" ; :: "(" "subject-info" * ")" ; :: | | | | ; :: "(" "subject" ")" ; :: | "null" ; :: | | ; :: "(" "*" "prefix" ")" ; :: "(" "*" "range" ? ? ")" ; :: "(" "*" "set" * ")" ; :: "(" "tag" "(*)" ")" ; :: | | ; :: | "(" "tag" ")" ; :: ; :: ; :: ? ? ; :: | "null" ; :: ? ; :: "(" "version" ")" ; Ellison, et al. [Page 43] INTERNET-DRAFT Simple Public Key Certificate 21 November 1997 9. 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. Ellison, et al. [Page 44] INTERNET-DRAFT Simple Public Key Certificate 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 45] INTERNET-DRAFT Simple Public Key Certificate 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 46] INTERNET-DRAFT Simple Public Key Certificate 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 47] INTERNET-DRAFT Simple Public Key Certificate 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-structure-03.txt Ellison, et al. [Page 48]