Internet Info 1997 December

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_ietf_q_t / draft-ietf-spki-cert-structure-02.txt < prev next >

Wrap

Text File | 1997-07-31 | 158KB | 4,672 lines

Simple Public Key Certificate Carl M. Ellison INTERNET-DRAFT CyberCash, Inc. Expires: 29 January 98 Bill Frantz Electric Communities Butler Lampson Microsoft Ron Rivest MIT Laboratory for Computer Science Brian M. Thomas Southwestern Bell Tatu Ylonen SSH 29 July 1997 Simple Public Key Certificate ------ ------ --- ----------- Status of This Document This document supersedes the draft filed under the name draft-ietf- spki-cert-structure-01.txt and reflects changes in the structure to simplify it. The draft ends with a list of open questions for group discussion. Distribution of this document is unlimited. Comments should be sent to the SPKI (Simple Public Key Infrastructure) Working Group mailing list <spki@c2.org> 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. Ellison, et al. [Page 1] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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.'' 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 29 July 1997 Abstract With the proliferation of public key cryptography on the Internet, there arises a need for certification of keys. In the literature, the word 'certificate' has generally been taken to mean 'identity certificate': a signed statement which binds a key to the name of an individual and has the intended meaning of delegating authority from that named individual to the public key. (See, for example, RFC 1422.) This process is designed to copy a relationship between two entities from the physical world into the digital world. The Internet itself changed the world from the one in which identity certificates made sense. We now deal with people we have never met and never will, which makes their names meaningless to us, but we still need to verify whether they are authorized to perform some action, achieve some access, sign some document, etc. SPKI certificates were designed to perform that function by directly specifying the (permission,key) binding which is of interest in the digital world. As merged with SDSI, the current certificate format also allows someone to bind a key to a name in their own private name space. The certificate structure presented here allows permissions to be delegated to SDSI-named individuals or to raw keys. Acknowledgments Several independent contributions, published elsewhere on the net or in print, worked in synergy with our effort. Especially important to our work were: [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 29 July 1997 Table of Contents Status of This Document....................................1 Abstract...................................................3 Acknowledgments............................................3 Table of Contents..........................................4 1. Overview of Contents....................................7 2. Scope Of This Effort....................................8 2.1 Charter of the SPKI group..............................8 2.2 Areas Covered And Not Covered..........................8 2.2.1 Key and certificate storage..........................8 2.2.2 Protocols to use public key authentication...........9 2.3 Other Certificate Formats.............................10 2.4 Goals of this effort..................................10 2.5 SPKI Certificates vs. Capabilities....................11 2.6 Chosen standard format................................11 3. Assumptions, Definitions and Design Issues.............12 3.1 Background............................................12 3.2 Definition of PRINCIPAL and KEYHOLDER.................13 3.2.1 Protection of Private Keys..........................14 3.3 Certificate Structure.................................15 3.3.1 5-tuple Reduction (introduction)....................16 3.3.2 Authority Loops.....................................17 3.3.3 Certificate Result Certificates.....................18 3.4 Relation to Policymaker...............................19 3.5 Name spaces 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 Name spaces................................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 Process Server Certificates.......................23 3.6 Certificate validity periods..........................23 3.7 Unwanted Attributions.................................24 3.8 Blind Signatures......................................25 3.9 Determinism...........................................25 4. SPKI Object Definitions................................27 4.1 Canonical S-expression................................27 4.1.1 <byte-string>.......................................27 4.1.2 S-expression........................................28 4.1.3 Encoding examples...................................28 4.1.4 Use of canonical S-expressions......................29 4.1.5 Non-canonical (advanced) S-expressions..............29 Ellison, et al. [Page 4] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.1.6 Unique IDs..........................................30 4.2 SPKI/SDSI 2.0 Objects.................................30 4.2.1 <pub-key>...........................................31 4.2.2 <sec-key>...........................................33 4.2.2.1 HMAC-MD5..........................................33 4.2.2.2 DES-CBC-MAC.......................................33 4.2.3 <hash>..............................................34 4.2.4 <signature>.........................................34 4.2.5 <acl>...............................................36 4.2.6 <sequence>..........................................37 4.3 <cert> object.........................................37 4.3.1 Bare-bones SPKI.....................................38 4.3.1.1 <version>.........................................39 4.3.1.2 <cert-display>....................................39 4.3.1.3 <issuer>..........................................39 4.3.1.4 <issuer-loc>......................................40 4.3.1.5 <subject>.........................................40 4.3.1.6 <subject-loc>.....................................40 4.3.1.7 <deleg>...........................................40 4.3.1.8 <tag>.............................................41 4.3.1.9 <valid>...........................................41 4.3.1.9.1 <date>..........................................41 4.3.1.9.2 <online-test>...................................42 4.3.1.10 <comment>........................................43 4.3.2 SPKI/SDSI...........................................43 4.3.2.1 <issuer>..........................................43 4.3.2.2 <subject>.........................................44 4.3.2.2.1 <name>..........................................44 4.3.2.2.2 <obj-hash>......................................45 4.3.2.2.3 <sec-key>.......................................45 4.3.2.2.4 <keyholder>.....................................46 4.3.2.3 <subject-loc>.....................................46 4.3.3 Tag algebra.........................................46 4.3.3.1 *-forms...........................................47 4.3.3.1.1 Sets of S-expressions...........................47 4.3.3.1.2 S-expressions with *-form parts.................48 4.3.3.1.3 *-form reduction................................50 4.3.3.2 <tag> *-form BNF..................................51 4.3.4 Threshold subjects..................................52 4.3.4.1 Examples..........................................53 4.3.4.2 Definition........................................53 5. Examples...............................................54 5.1 ftp tag...............................................54 5.2 http tag..............................................54 5.3 telnet tag............................................54 5.4 Public Key Protected File System tags.................54 5.5 Authority to spend money..............................55 Ellison, et al. [Page 5] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 5.6 Process Server cert...................................55 5.7 PICS-like ratings cert................................55 5.8 Virus checking cert...................................56 5.9 Full sequence, with donation cert.....................56 6. On-line test reply formats.............................58 6.1 CRL and delta-CRL.....................................58 6.2 Revalidation..........................................58 6.3 One-time revalidation.................................59 7. 5-Tuple Reduction (full)...............................60 7.1 <5-tuple> BNF.........................................60 7.2 Bare-bones case.......................................61 7.3 Intersection of *-form tag sets.......................62 7.3.1 Reduction to (* null) by data type mismatch.........63 7.3.2 Specific intersections..............................63 7.3.3 Deferred intersections..............................64 7.4 Reduction of SDSI names...............................64 7.4.1 Simple SDSI name reduction..........................65 7.4.2 SDSI name composition with subject name growth......66 7.4.3 SDSI Name composition with issuer name growth.......66 7.5 Reduction of (subject (threshold ..)).................67 7.5.1 Left-to-right.......................................67 7.5.2 Right-to-left.......................................68 8. Full BNF...............................................69 Closed Issues.............................................73 Open Issues...............................................78 References................................................79 Authors' Addresses........................................81 Expiration and File Name..................................82 Ellison, et al. [Page 6] INTERNET-DRAFT Simple Public Key Certificate 29 July 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. Section 4 describes SPKI data object formats -- listing the fields in top level objects, especially the certificate, and giving encoding details. Section 5 describes predefined SPKI tag fields. These are the meat of an SPKI certificate, since they carry the authority or other information being bound to a subject public key. Section 6 describes on-line tests and their reply formats. Section 7 describes the full set of rules used by the basic trust engine assumed to be part of every verifier which accepts SPKI certificates. Section 8 gives the full BNF for SPKI objects. The Closed Issues section gives a list of questions which have been resolved by the working group. The Open Issues section gives a list of open questions to be resolved by the SPKI working group. 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 7] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 2. Scope Of This Effort 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 This particular draft is concerned only with certificate, hash, key and signature formats, using the certificates defined here both for verification of identity and for proof of authorization. We do not cover 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 Ellison, et al. [Page 8] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 requester 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 requester (possibly under access control) rather than the verifier. 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. Ellison, et al. [Page 9] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 through the Certificate Result Certificate process, allowing all these to be merged into a single, simple format as far as application software is concerned. 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 secure authentication and authorization of access control 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 Ellison, et al. [Page 10] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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. 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 11] INTERNET-DRAFT Simple Public Key Certificate 29 July 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. There is a long standing effort 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. This effort has produced identity certificates, such as X.509 certificates or PGP signed keys, giving <name,key> bindings which needed to be combined with certificates or ACL entries giving <tag,name>, to yield the relationship <tag,key> which a computer then uses to verify public-key driven access attempts. {<tag> here stands for authorization, permission, etc.} The Internet has changed the world from the one in which identity certificates were originally seen to be necessary. In the new world Ellison, et al. [Page 12] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 of the global Internet the entities which communicate are often not known to each other in the physical world. This trend is likely to increase as time goes on. Therefore a mechanism which transfers attributes from the physical world to the digital world is increasingly less appropriate while a mechanism which transfers attributes within the digital world is vital and one which 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 <key> 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 <tag,key> 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). 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 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 Ellison, et al. [Page 13] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 <principal>)" -- 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). 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 Ellison, et al. [Page 14] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 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 name space. 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 Ellison, et al. [Page 15] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 <tag> 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 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 Ellison, et al. [Page 16] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 pair of 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))) 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, it tells Self what it can trust about X. Ellison, et al. [Page 17] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 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 18] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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. 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. Ellison, et al. [Page 19] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 3.5 Name spaces 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 as an identity certificate. Ellison, et al. [Page 20] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 Name spaces 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 Simple Public Key Certificate 29 July 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 Ellison, et al. [Page 22] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 certification, one would never use a self-signed certificate. 3.5.5.2 Process Server 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 Ellison, et al. [Page 23] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 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. Ellison, et al. [Page 24] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 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 <tag> 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 <subject> as well as by the <issuer> in order to make sure that the <subject> 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. Ellison, et al. [Page 25] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 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 Simple Public Key Certificate 29 July 1997 4. SPKI Object Definitions 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) and "?" meaning optional (0 or 1 occurrence). First we define the canonical S-expression form in that BNF. 4.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 positive ASCII decimal number, not starting with "0", 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. 4.1.1 <byte-string> 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 number, these bytes are twos- complement, in network standard order (most significant byte first). This means that the sign of the first byte is the sign of the number, so that if you have a positive number whose first byte exceeds 128, then you need to prefix that number with a 0 byte to force it to be positive. A canonical form positive number will not have unnecessary leading 0x00 bytes while a canonical form negative number will not have unnecessary leading 0xFF bytes. Such a byte is unnecessary if by removing it, the remaining string has the same value as a twos- complement integer. All byte strings carry explicit lengths and are therefore not Ellison, et al. [Page 27] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 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: <byte-string>:: <bytes> | <display-type> <bytes> ; <bytes>:: <decimal> ":" {binary byte string of that length} ; <decimal>:: <nzddigit> <ddigit>* ; <nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; <ddigit>:: "0" | <nzddigit> ; <display-type>:: "[" <bytes> "]" ; 4.1.2 S-expression An S-expression is of the form: <s-expr>:: "(" <byte-string> <s-part>* ")" ; <s-part>:: <byte-string> | <s-expr> ; where the first byte string in the S-expression is referred to here as its "type". 4.1.3 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 Ellison, et al. [Page 28] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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} 4.1.4 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.] 4.1.5 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 Ellison, et al. [Page 29] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 get the actual canonical form. 4.1.6 Unique IDs Top level object names are defined in this document along with certain algorithm names. <tag> 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). 4.2 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 <byte-string>, 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 <sequence> of <cert>, <pub-key>, <sec-key>, <signature> and <op>. The verifier will also need to refer to its own <acl>. 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 Ellison, et al. [Page 30] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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. those defined by an application developer) are completely 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. Normally, the object structure is one of two varieties: "positional" -- the parts are listed in some fixed order with possible omission of some of the later parts and meaning of the part depending on its position Example: (hash sha1 20:...) "sub-type based" -- the parts are identified by object type of a sublist or spelling of a byte-string and can be in any order. These elements are expected all to have distinct types, and the types of the parts determine their meaning with respect to the top-level object. The set of allowable sub-object types is a function of the object type, as is whether sub-objects of some types are optional. Example: (rsa (n 128:...) (e 1:.)) The following are the definitions of the top level objects which a 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. 4.2.1 <pub-key> <pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uri>? ")" ; 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 Ellison, et al. [Page 31] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 |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. Ellison, et al. [Page 32] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.2.2 <sec-key> <sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>? ")" ; 4.2.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]. 4.2.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 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} Ellison, et al. [Page 33] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.2.3 <hash> <hash>:: "(" "hash" <hash-alg-name> <hash-value> <uri>? ")" ; A <hash> 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. 4.2.4 <signature> <signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ; A signature object is typically used for a certificate body and typically follows that <cert> object in a <sequence>. We chose not to define an object <signed-cert> 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, the following is the signature of a file. (signature Ellison, et al. [Page 34] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 (hash md5 |8dIIGz8bZZpXpX2M/g/aVQ==|) (public-key rsa-pkcs1-md5 (e #03#) (n |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTOYTT lapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yYVDzJ1 DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1|)) |0Q5bkgsDoPlD9zkQo+YEnpmuXwC9REZHDcCoiT9FlzgTw1QPzM0yS0vg7+rG 4HmsHOgZWvgjFY2IWXt1Po2gD9Hjxw6sGl/vTpmjo2NldnONPbzNTJKqEEqh 8SFyuLibu04IdcuicqNGyaBJhuN1leXt29Wn+gHVPtufGCSK670=|) which is equivalent to (signature (hash md5 |8dIIGz8bZZpXpX2M/g/aVQ==|) (hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==| key2-pub) |0Q5bkgsDoPlD9zkQo+YEnpmuXwC9REZHDcCoiT9FlzgTw1QPzM0yS0vg7+ rG4HmsHOgZWvgjFY2IWXt1Po2gD9Hjxw6sGl/vTpmjo2NldnONPbzNTJKqE Eqh8SFyuLibu04IdcuicqNGyaBJhuN1leXt29Wn+gHVPtufGCSK670=|) or, in base64 encoded canonical form, {KDk6c2lnbmF0dXJlKDQ6aGFzaDM6bWQ1MTY68dIIGz8bZZpXpX2M/g/aVSk oNDpoYXNoMzptZDUxNjqS5fKrHyNhZ1n+PtV9+v7KODprZXkyLXB1YikxMjg 60Q5bkgsDoPlD9zkQo+YEnpmuXwC9REZHDcCoiT9FlzgTw1QPzM0yS0vg7+r G4HmsHOgZWvgjFY2IWXt1Po2gD9Hjxw6sGl/vTpmjo2NldnONPbzNTJKqEEq h8SFyuLibu04IdcuicqNGyaBJhuN1leXt29Wn+gHVPtufGCSK670p} As one more example, the signature on the hmac-md5 secret key defined above, by the public key above, is: (signature (hash md5 |M7cDVmX3r4xmab2rxYqyNg==|) (public-key rsa-pkcs1-md5 (e #03#) (n |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKT OYTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/ yYVDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3u W1|)) |fA9Jhf/YXYgtxHowCDPUBFWDeOgAKNAlfDGq73obef6E1xCYCrpeh/kPr4 V8yoE+eXY+CUQivbQsmKxfcEoxJbCAseDSzvuprZ2jeETDK0ESVhYfGPMyN vx1pfkL1SQZwFqbf1g3G7obRU6SpPn/A12+IuHRBXKdLtUyFnBMxvE=|) or, in base64 encoded canonical form: Ellison, et al. [Page 35] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 {KDk6c2lnbmF0dXJlKDQ6aGFzaDM6bWQ1MTY6M7cDVmX3r4xmab2rxYqyNik oMTA6cHVibGljLWtleTEzOnJzYS1wa2NzMS1tZDUoMTplMToDKSgxOm4xMjk 6ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTOYT TlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yYVDzJ 1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1KSkxMjg 6fA9Jhf/YXYgtxHowCDPUBFWDeOgAKNAlfDGq73obef6E1xCYCrpeh/kPr4V 8yoE+eXY+CUQivbQsmKxfcEoxJbCAseDSzvuprZ2jeETDK0ESVhYfGPMyNvx 1pfkL1SQZwFqbf1g3G7obRU6SpPn/A12+IuHRBXKdLtUyFnBMxvEp} 4.2.5 <acl> <acl>:: "(" "acl" <version>? <acl-entry>* ")" ; <acl-entry>:: <subj-obj>* <deleg>? <tag> <valid>? <comment>? ; 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 <cert>, we will not repeat those common field definitions here. If all the optional fields are left out, the (possible multiple) subjects are given the permission specified in <tag>, without permission to delegate it, but forever (until the ACL is edited to remove the permission). For example: (acl (name (hash md5 |p1isZirSN3CBscfNQSbiDA==|) sysadmin/operators) (hash md5 |M7cDVmX3r4xmab2rxYqyNg==|) (tag (ftp db.acme.com root)) (hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|) (propagate) (tag (http http://www.internal.acme.com/accounting/)) ) or {KDM6YWNsKDQ6bmFtZSg0Omhhc2gzOm1kNTE2OqdYrGYq0jdwgbHHzUEm4gw pMTg6c3lzYWRtaW4vb3BlcmF0b3JzKSg0Omhhc2gzOm1kNTE2OjO3A1Zl96+ MZmm9q8WKsjYpKDM6dGFnKDM6ZnRwMTE6ZGIuYWNtZS5jb200OnJvb3QpKSg 0Omhhc2gzOm1kNTE2OpLl8qsfI2FnWf4+1X36/sopKDk6cHJvcGFnYXRlKSg zOnRhZyg0Omh0dHA0MDpodHRwOi8vd3d3LmludGVybmFsLmFjbWUuY29tL2F jY291bnRpbmcvKSkp} Ellison, et al. [Page 36] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.2.6 <sequence> <sequence>:: "(" "sequence" <seq-ent>* ")" ; <seq-ent>:: <cert> | <pub-key> | <signature> | <op> ; <op>:: <hash-op> | <general-op> ; <hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ; <general-op>:: "(" "do" <byte-string> <s-part>* ")" ; A <sequence> 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 <sequence>) to provide elements in order, so that the verifier need only process the <sequence> 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. 4.3 <cert> object <cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>? <subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ; The full SPKI/SDSI 2.0 specification as it has evolved over the past year has departed somewhat from the original purpose of providing the simplest possible, bare-bones certificate which is still useful to Internet developers. It has acquired some features which we now believe are of extreme value and therefore worth the complexity they introduce. However, there are still expected to be some developers who do not need all these additional features. Ellison, et al. [Page 37] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 A SPKI/SDSI <cert> compliant with this proposed standard fits within the full BNF given at the end of this draft. A fully "compliant" verifier would accept all of that possible BNF. However, there may be developers in closed environments which will never generate SPKI/SDSI <certs> using all the features presented in the BNF and using verifier code which can not accept the full set. As an aid in selecting subsets of the SPKI/SDSI <cert> definition, we offer the following four sections -- a basic <cert> and three extensions from the basic which are independent of one another and therefore might be included or left out as the developer wishes. However, we urge everyone to consider use of the full definition and to cut back only if it is obvious that some set of features will never be needed or that the code required to process some feature can not fit within the application's design constraints. For that latter possibility, the developer can consider reducing full SPKI/SDSI certs to Certificate Result Certs [CRCs] which can easily be expressed in bare-bones format. It should be kept in mind that a decision to accept less than the full SPKI cert limits the certificate chains a verifier can accept without use of an intermediary CRC engine. 1. Bare-bones SPKI 2. Simple SPKI/SDSI (addition of SDSI names) 3. Tag algebra (addition of the *-form construct) 4. Threshold subjects (addition of multiple-subject forms) 4.3.1 Bare-bones SPKI A bare-bones SPKI cert is one which uses only principals (not names) for both issuer and subject, and uses a non-intersectable S- expression for the tag, to be interpreted by code at the verifier. It does not permit threshold subjects. This might show up in actual use as either a special, simple cert for a specific purpose or as a Certificate Result Cert (CRC). We expect verifiers which accept only bare-bones SPKI certs to be specialized applications in closed environments, if any such verifiers are fielded. Ellison, et al. [Page 38] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.3.1.1 <version> <version>:: "(" "version" <byte-string> ")" ; Version numbers are non-negative and start with #00#. If the <version> field is missing from an object, it is assumed to be (version #00#), which is the version of all objects in this draft. It is assumed that a verifier, when encountering a structure it doesn't know how to parse (because it has a version number too high), will ignore that object. 4.3.1.2 <cert-display> <cert-display>:: "(" "display" <byte-string> ")" ; 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, but we anticipate allowing the differentiation between a SDSI individual name definition, SDSI group membership definition, a straight permission delegation, etc. Possible parameters for this field are left as an open issue. 4.3.1.3 <issuer> In the bare-bones SPKI cert, we have: <issuer>:: "(" "issuer" <principal> ")" ; <principal>:: <pub-key> | <hash-of-key> ; and some implementations may prefer to simplify code and allow only <pub-key> for <principal>. This rules out <sec-key> issuers, although not a <hash-of-key> field which is the hash of a <sec-key>. An explicit <sec-key> as an issuer offers no security to the cert. Ellison, et al. [Page 39] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.3.1.4 <issuer-loc> <issuer-loc>:: "(" "issuer-info" <uri>* ")" ; 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 <cert>. 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.3.1.5 <subject> In the bare-bones SPKI cert, we have: <subject>:: "(" "subject" <principal> ")" ; <principal>:: <pub-key> | <hash-of-key> ; and some implementations may prefer to simplify code and allow only <pub-key> for <principal>. 4.3.1.6 <subject-loc> <subject-loc>:: "(" "subject-info" <uri>* ")" ; 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. 4.3.1.7 <deleg> <deleg>:: "(" "propagate" ")" ; This optional field, if present, notes that the <subject> has not only the permission given in the <cert>'s <tag> field but also the permission to delegate that (or some portion of it) to others. Ellison, et al. [Page 40] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.3.1.8 <tag> In the bare-bones SPKI cert (and simple SPKI/SDSI cert), the tag field has no special structure beyond the following: <tag>:: "(" "tag" "(*)" ")" | "(" "tag" <tag-body> ")" ; <tag-body>:: <simple-tag> ; <simple-tag>:: "(" <byte-string> <tag-param>* ")" ; <tag-param>:: <s-part> ; The form (tag (*)) means "all permissions". The <simple-tag> form gives an application-dependent S-expression. The reduction rule for this simple form is that the S-expression must match exactly [or must match with a (tag (*))]. 4.3.1.9 <valid> The <valid> field gives validity dates and/or on-line test information for the cert. <valid>:: <not-before>? <not-after>? <online-test>? ; <not-after>:: "(" "not-after" <date> ")" ; <not-before>:: "(" "not-before" <date> ")" ; The not-after and not-before options are self-explanatory. If either is missing, then the cert is assumed valid for all time in that direction. For example, one might omit the <not-before> 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.3.1.9.1 <date> <date>:: <byte-string> ; A date field is an ASCII byte string of the form: YYYY-MM-DD_HH:MM:SS Ellison, et al. [Page 41] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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". <date> 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.3.1.9.2 <online-test> <online-test>:: "(" "online" <online-type> <uri> <principal> <s- part>* ")" ; <online-type>:: "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 <principal> 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 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. Ellison, et al. [Page 42] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.3.1.10 <comment> <comment>:: "(" "comment" <byte-string> ")" ; 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. 4.3.2 SPKI/SDSI This level of <cert> fully implements the merged SPKI and SDSI proposals, except for the <tag> algebra improvement which was developed after the decision to merge (and which is described below). The full SPKI/SDSI <cert> involves enhancement of the <issuer> and <subject> fields, over what was included in the bare-bones SPKI cert. 4.3.2.1 <issuer> The full form of issuer is: <issuer>:: "(" "issuer" <issuer-name> ")" ; <issuer-name>:: <principal> | <simple-name> ; <simple-name>:: "(" "name" <principal> <byte-string> ")" ; The additional construct allowed here gives the definition of a SDSI name in the name space of the issuer. For example, (cert (issuer (name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred)) (subject (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|)) (tag (*)) ) or {KDQ6Y2VydCg2Omlzc3Vlcig0Om5hbWUoNDpoYXNoMzptZDUxNjpPGjPUbEr +4G8lvHemsiETKTQ6ZnJlZCkpKDc6c3ViamVjdCg0Omhhc2gzOm1kNTE2Ome acQg+uGMIEtSGOEYetaApKSgzOnRhZygxOiopKSk=} defines the name "fred" in the name space of the key which hashes to |Txoz1GxK/uBvJbx3prIhEw==|. It is defined to be the key which hashes to |Z5pxCD64YwgS1IY4Rh61oA==|. That key acquires all the permissions which might be delegated to "fred" by name. Ellison, et al. [Page 43] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 The cert must be signed by the key referenced in the (issuer ), in this case, the key hashing to |Txoz1GxK/uBvJbx3prIhEw==|. 4.3.2.2 <subject> The full form of subject (except for k-of-n, described below) is: <subject>:: "(" "subject" <subj-obj> ")" ; <subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> | <keyholder> ; 4.3.2.2.1 <name> The primary addition to the possibilities for <subject> is a SDSI name. This can be either a relative name or a fully-qualified name. <name>:: <relative-name> | <fq-name> ; <relative-name>:: "(" "name" <names> ")" ; <fq-name>:: "(" "name" <principal> <names> ")" ; <names>:: <byte-string> | <names> <byte-string> ; For evaluation purposes, the relative name is translated into a fully-qualified name by using the key of the issuer. Unlike the <issuer> 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 Ellison, et al. [Page 44] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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.3.2.2.2 <obj-hash> <obj-hash>:: "(" "object-hash" <hash> ")" ; This option for a (subject ) refers to an object other than a <principal> (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, ...). 4.3.2.2.3 <sec-key> <sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>? ")" ; A secret key can also be a Principal, in the formal sense, but we do not permit it to appear explicitly in an <issuer> for obvious reasons. Most likely, a <cert> using a secret key will use the hash of the key, so that the cert could be published. In that case, the builder of <sec-key> 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 Ellison, et al. [Page 45] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 certificate might also include a key serial number as part of its tag field. 4.3.2.2.4 <keyholder> <keyholder>:: "(" "keyholder" <principal> ")" ; This form of subject refers to the flesh and blood (or iron and silicon) holder of the referenced key. A <cert> 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, .... 4.3.2.3 <subject-loc> <subject-loc>:: "(" "subject-info" <uri>* ")" ; This optional field might give the location of SDSI name cert servers to help the prover (the client code), which is building a list of certs to present to the verifier, to find those certs. 4.3.3 Tag algebra This extension to bare-bones SPKI/SDSI provides a means for expressing sets of permissions (or ranges of parameters) so that a standard, simple algorithm in the verifier can intersect tag fields of two adjacent <certs> to yield the permission of the combination. When a verifier is equipped to do tag algebra using "*-forms", as we expect standard verifiers to be, cert chains can be expressed which delegate only a sub-portion of one's permissions. When composing certificate chains, the tag fields are automatically intersected by a standard intersection algorithm. The user does not have to specify an intersection algorithm for his tags, but he does have to write his tags in such a way that the standard intersection algorithm gives the desired behavior. Ellison, et al. [Page 46] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.3.3.1 *-forms An S-expression of the form ( * ... ) is called a "*-form". An S-expression that does not contain any *-forms (at any level) is called a "*-free" S-expression. (Byte strings are *-free.) *-free S-expressions are significant because we assume that elementary authorizations (permissions, or rights) are expressed as *-free S- expressions. The simplest form of a certificate has a tag that is *-free. [Bare-bones SPKI/SDSI certs have *-free tags.] The intersection of two *-free S-expressions s1 and s2 is either s1 (if s1 and s2 are identical), or null otherwise. Other S-expressions are called "variable" S-expressions. Every S-expression (T) (*-free or not) is understood to represent a set m(T) of *-free S-expressions. Each of those *-free tags has a meaning and that meaning is defined by the verifier code. A variable S-expression may represent a large set of *-free S- expressions. The use of *-forms allows one to denote such a set efficiently. Issuing a certificate with tag T (i.e. with field (tag T)) has the same effect as issuing a separate certificate with tag T' for every element T' of m(T). That is, the elements of m(T) are assumed to have meanings which are permissions or capabilities and the meaning of m(T) is the union of the permissions of the elements of m(T). A certificate chain with tags T1, ..., Tk reduces to a result certificate with a meaning that is the intersection of m(T1),...,m(Tk). 4.3.3.1.1 Sets of S-expressions Here are some simple *-forms, operating on whole S-expressions: (*) whose meaning is the set of all S-expressions (* null) whose meaning is the empty set (* set s1 ... sk) whose meaning is just the union of the meanings m(s1), ..., m(sk) (* intersect s1 ... sk) whose meaning is just the intersection of the meanings m(s1),...,m(sk) The (* null) expression is unlikely to occur in a certificate tag, Ellison, et al. [Page 47] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 but is useful to have as part of the algebra of *-forms. The (* intersect) form is also not expected to occur in a certificate. It is defined for completeness. [In some cases, it can ease the programming of the *-form intersection software by permitting it to postpone an intersection. This is because it is always easy to intersect a *-free form with a *-form and the final result of a verification step is almost certainly a *-free form.] One can also build sets of S-expressions by reordering, adding or deleting parts: ( * append s ) -- represents all S-expressions that can be obtained by appending additional elements to the end of list s. Example: T1 = ( tag ( * append ( ftp "abc.com" ))) allows there to be additional elements at the end of the ftp list after "abc.com". ( * reorder s ) ( * reorder-insert s ) ( * reorder-delete s ) These represent the set of S-expressions you can get from s by re- ordering the elements of s (other than the first) and possibly inserting new elements, or deleting some elements (other than the first). For example, (* reorder (rsa (n #44#)(e #03#))) allows the n and e fields to be given in either order. Or, the meaning of (* reorder-insert (a (b "4")(c "5"))) includes (a d (c "5") e f (g "23") (b "4")) The (* reorder) family of constructs is good when the elements of the list are indexed by keywords or list type, rather than by position, while the (* append) construct is good for positional tag forms. 4.3.3.1.2 S-expressions with *-form parts An s-expression can be written that is not a *-form, but which contains *-forms: Let s denote the list (s1 s2 ... sk) (where s1 is not *) Then m(s) is the set Ellison, et al. [Page 48] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 { ( t1 ... tk ) : each ti is an element of m(si) } That is, the meaning of a list is the cross product of the meanings of its elements. For example: if s = ( W (* set a b) (* set c d e) ) then m(s) = { (W a c) (W a d) (W a e) (W b c) (W b d) (W b e) } If s is the list (s1 ... sk) and s' is the list (s1' ... sk') (where s1 and s1' are not *), then (* intersect s s') has the same meaning as ((* intersect s1 s1') ... (* intersect sk sk')) The meaning of an intersection of lists is the list of intersections of their meaning. [example] Consider the tag T1 = (tag (spend-from "45123")) Here 45123 is an account number at the bank. Since this is *-free, the intersection of T1 with the tags from other certificates in a certificate chain can only yield either T1 or (* null). Consider now the variable S-expression of the form T2 = (tag (spend-from (* set "45123" "11112"))) This is intended to denote an authorization to spend from either account 45123 or account 11112. Alice can delegate to Bob the authority to spend from either account using tag T2, and Bob can delegate to Charles the ability to spend from account 45123 only using tag T1. This works properly automatically, since (* intersect T1 T2) = T1 because (* intersect tag tag) = tag (* intersect spend-from spend-from) = spend-from (* intersect "45123" (* set "45123" "11112")) = "45123" Here are two simple *-forms representing sets of byte strings: (* prefix "abc") -- represents the set of byte strings having "abc" as a prefix. Example of use: T1 = (tag (http (* prefix "http://abc.com/"))) This can be automatically intersected with T2 = (tag (http (* prefix "http://abc.com/accounting"))) to yield Ellison, et al. [Page 49] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 T2 = (tag (http (* prefix "http://abc.com/accounting"))) (* range <order> <lower-limit>? <upper-limit>? ) where <order> is one of "alpha", "numeric", "time" or "binary" and <lower-limit> ::= (<ge-or-geq> <byte-string>) <ge-or-geq> ::= "g" | "ge" ; <upper-limit> ::= (<le-or-leq> <byte-string>) <le-or-leq> ::= "l" | "le" "alpha" restricts the set to byte strings, with left-justified comparisons "numeric" restricts the set to ASCII strings representing positive or negative numbers (possibly with a decimal point and following digits) "time" restricts the set to ASCII strings representing times (apart from their dates) "binary" restricts the set to binary strings representing numbers, that is byte strings with right-justified comparisons and sign taken from the most significant bit. Examples of use: T1 = (tag (spend-amount (* range numeric (l "5000")) USD )) authorizes someone to spend up to 5000 US dollars. T2 = (tag (login cybercash.com cme (time (* range time (ge "04:00:00") (le "12:00:00"))))) authorizes the keyholder to login on cybercash.com as user cme during the hours 4 am to noon UTC. 4.3.3.1.3 *-form reduction It is possible to recursively work out the intersections for tags using *-forms in an automatic manner. For example, the intersection of (tag (spend (amount (* range numeric (l "5000"))) (account (* set "12345" "67890")) (* reorder-insert (for socks shirt pants)))) and (tag (spend (amount (* range numeric (l "1000"))) (account (* set "87654" "12345")) (for tie pants socks belt shirt))) is (tag (spend (amount (* range numeric (l "1000"))) (account "12345") (for tie pants socks belt shirt))) Ellison, et al. [Page 50] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 Note that *-forms can be used to get the effect of multiple tags per certificate; a certificate with tag ( tag ( * set T1 T2 ... Tk ) ) is entirely equivalent to a set of separate certificates with tag fields T1, T2, etc. However, we should point out that if too many permissions are accumulated in a single certificate, then the certificate itself forms a kind of dossier on the keyholder which might be considered a privacy violation. 4.3.3.2 <tag> *-form BNF The *-form algebra above is expressed in BNF as: <tag>:: "(" "tag" <tag-body> ")" ; <tag-body>:: <simple-tag> | <list-set> ; <list-set>:: <impl-list-set> | <list-union> | <list-intersect> | <misc-set> ; <impl-list-set>:: "(" "*" <list-set-type> <tag-body> ")" ; <list-set-type>:: "append" | "reorder" | "reorder-insert" | "reorder- delete" ; <list-union>:: "(" "*" "set" <tag-body>* ")" ; <list-intersect>:: "(" "*" "intersect" <tag-body>* ")" ; <misc-set>:: <all-set> | <null-set> ; <all-set>:: "(" "*" ")" ; <null-set>:: "(" "*" "null" ")" ; <simple-tag>:: "(" <byte-string> <tag-param>* ")" ; <tag-param>:: <s-part> | <string-set> ; <string-set>:: <prefix-set> | <range-set> | <string-union> | <string- intersect> | <misc-set> ; <prefix-set>:: "(" "*" "prefix" <byte-string> ")" ; Ellison, et al. [Page 51] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 <range-set>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>? ")" ; <range-ordering>:: "alpha" | "numeric" | "time" | "binary" ; <low-lim>:: <gte> <byte-string> ; <gte>:: "g" | "ge" ; <up-lim>:: <lte> <byte-string> ; <lte>:: "l" | "le" ; <string-union>:: "(" "*" "set" <byte-string>* ")" ; <string-intersect>:: "(" "*" "intersect" <byte-string>* ")" ; 4.3.4 Threshold subjects 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. 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 blocked. The first reaction is that this 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 below in Section 7. Ellison, et al. [Page 52] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 4.3.4.1 Examples 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 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.3.4.2 Definition <subj-thresh>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ; where the first int is K and the second is N, K < N, and there are N <subj-obj> subjects listed. The processing of certs and ACLs (therefore 5-tuples) using k-of-n subjects is presented below in section 7.5. Ellison, et al. [Page 53] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 5. Examples The <tag> fields listed here are not meant to be an exhaustive list of all possible <tag>s. Such is not possible. The final arbiter of what needs to be an <tag> and what parameters a particular <tag> needs is the designer of the code which verifies a certificate, e.g., to grant access. Listed here are <tag> fields we suspect might be useful and we present these here as a guide to the developer's imagination. 5.1 ftp tag (tag (ftp cybercash.com cme )) This <tag> indicates that the Subject has permission to do FTP into host cybercash.com as user cme. 5.2 http tag (tag (http http://acme.com/company-private/personnel/ )) This <tag> gives the Subject permission to access web pages which start with the given URI. 5.3 telnet tag (tag (telnet clark.net cme )) This <tag> gives the Subject permission to telnet into host clark.net as user cme. 5.4 Public Key Protected File System tags (tag (pkpfs //<host-name>/<path> <access> )) (tag (pkpfs (* prefix //<host-name>/<path>/) <access> )) refers to a hypothetical distributed file system whose access is controlled by public key challenge/response. The first form gives access to a single file or a small set of files (by use of "*" in the file name) while the second form gives access to an entire sub- Ellison, et al. [Page 54] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 directory. <access> is a (* set ...) whose elements are chosen from: (read) (write) (append) (delete) (execute) 5.5 Authority to spend money (tag (spend <bank> <account> (* range le <amount> ))) indicates that the subject has authority to authorize spending up to <amount> per electronic check from <account> at <bank>. 5.6 Process Server cert A process server certificate, mentioned in Section 3.5.5.2, might have the form: (cert (issuer (hash md5 |u2kl73MiObh5o1zkGmHdbA==|)) (subject (keyholder (hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==| key2-pub))) (tag (tracking-fee "150" USD)) (not-after "2003-01-01_00:00:00") ) {KDQ6Y2VydCg2Omlzc3Vlcig0Omhhc2gzOm1kNTE2OrtpJe9zIjm4eaNc5Bp h3WwpKSg3OnN1YmplY3QoOTprZXlob2xkZXIoNDpoYXNoMzptZDUxNjqS5fK rHyNhZ1n+PtV9+v7KODprZXkyLXB1YikpKSgzOnRhZygxMjp0cmFja2luZy1 mZWUzOjE1MDM6VVNEKSkoOTpub3QtYWZ0ZXIxOToyMDAzLTAxLTAxXzAwOjA wOjAwKSk=} noting in its tag field that it will serve papers on the indicated Keyholder for a tracking fee of $150 until the beginning of 2003. 5.7 PICS-like ratings cert (cert (issuer (hash md5 |Ut9m14byPzdbCNZWdDjNQg==|)) (subject (object-hash (hash md5 |vN6ySKWE9K6T6cP9U5wntA==| http://www.clark.net/pub/cme/home.html))) (tag (ratings (sex "0") (violence "0") (crypto "6")))) Ellison, et al. [Page 55] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 {KDQ6Y2VydCg2Omlzc3Vlcig0Omhhc2gzOm1kNTE2OlLfZteG8j83WwjWVnQ 4zUIpKSg3OnN1YmplY3QoMTE6b2JqZWN0LWhhc2goNDpoYXNoMzptZDUxNjq 83rJIpYT0rpPpw/1TnCe0Mzg6aHR0cDovL3d3dy5jbGFyay5uZXQvcHViL2N tZS9ob21lLmh0bWwpKSkoMzp0YWcoNzpyYXRpbmdzKDM6c2V4MTowKSg4OnZ pb2xlbmNlMTowKSg2OmNyeXB0bzE6NikpKSk=} 5.8 Virus checking cert (cert (issuer (hash md5 |Ut9m14byPzdbCNZWdDjNQg==|)) (subject (object-hash (hash md5 |szKSlSK+SNzIsHH3wjAsTQ==| runemacs.exe))) (tag virus-free)) {KDQ6Y2VydCg2Omlzc3Vlcig0Omhhc2gzOm1kNTE2OlLfZteG8j83WwjWVnQ 4zUIpKSg3OnN1YmplY3QoMTE6b2JqZWN0LWhhc2goNDpoYXNoMzptZDUxNjq zMpKVIr5I3MiwcffCMCxNMTI6cnVuZW1hY3MuZXhlKSkpKDM6dGFnMTA6dml ydXMtZnJlZSkp} 5.9 Full sequence, with donation cert For one full example of a real certificate, the following sequence presents the public key used, calls for the verifier to hash it (and store it away, to be referred to later by its hash), gives a certificate body and then a signature (which by side-effect calls for the previous object to be stored and hashed by the signature algorithm's hash function). The example used is a temporary donation cert. (sequence (public-key rsa-pkcs1-md5 (e #03#) (n |AKMbo+VBqLu+90l2UuuGquzxLIXpqIypkSkrfEVprA0K2Vfm5ufmNZG3 0yWqdnXlxdGuyyBglj+FloXTrqHWSQQJfvTv5EMBz+icJ2GMbjtP1zCY8 krmchh5v/O3BntEwaq1hkMtmP+ZeFjI5yQ/YC2vVc5K1PTy+GOSP+xvYK C1|)) (do hash md5) (cert (issuer (hash md5 |Z4a6hysK/0qN0L5SFkcJFQ==|)) (subject (keyholder (hash md5 |Z4a6hysK/0qN0L5SFkcJFQ==|))) Ellison, et al. [Page 56] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 (tag (* set (name "Carl M. Ellison") (street "207 Grindall St.") (city "Baltimore MD 21230-4103"))) (not-after "1997-08-15_00:00:00")) (signature (hash md5 |PC4M1LNpkMHtgacc73ch5A==|) (hash md5 |Z4a6hysK/0qN0L5SFkcJFQ==| cme.key) |PQkhssqNW191aVwNR9DflDQemWf/E2maSdIk/5GulzRB7cjagEn9FqI9J vGOTkqT5miJmsFx9pY5nXQxp+tJZdwLYeSEA3iAzjcwBY1qG+DQqpWu2AC JqSnnKmo6kh8KbbySNtCbpguNJs2WM/eRBdkph/AUjTkqe0Xnv/mKEXA=| )) with canonical form encoded in base 64: {KDg6c2VxdWVuY2UoMTA6cHVibGljLWtleTEzOnJzYS1wa2NzMS1tZDUoMTp lMToDKSgxOm4xMjk6AKMbo+VBqLu+90l2UuuGquzxLIXpqIypkSkrfEVprA0 K2Vfm5ufmNZG30yWqdnXlxdGuyyBglj+FloXTrqHWSQQJfvTv5EMBz+icJ2G MbjtP1zCY8krmchh5v/O3BntEwaq1hkMtmP+ZeFjI5yQ/YC2vVc5K1PTy+GO SP+xvYKC1KSkoMjpkbzQ6aGFzaDM6bWQ1KSg0OmNlcnQoNjppc3N1ZXIoNDp oYXNoMzptZDUxNjpnhrqHKwr/So3QvlIWRwkVKSkoNzpzdWJqZWN0KDk6a2V 5aG9sZGVyKDQ6aGFzaDM6bWQ1MTY6Z4a6hysK/0qN0L5SFkcJFSkpKSgzOnR hZygxOiozOnNldCg0Om5hbWUxNTpDYXJsIE0uIEVsbGlzb24pKDY6c3RyZWV 0MTY6MjA3IEdyaW5kYWxsIFN0LikoNDpjaXR5MjM6QmFsdGltb3JlIE1EIDI xMjMwLTQxMDMpKSkoOTpub3QtYWZ0ZXIxOToxOTk3LTA4LTE1XzAwOjAwOjA wKSkoOTpzaWduYXR1cmUoNDpoYXNoMzptZDUxNjo8LgzUs2mQwe2BpxzvdyH kKSg0Omhhc2gzOm1kNTE2OmeGuocrCv9KjdC+UhZHCRU3OmNtZS5rZXkpMTI 4Oj0JIbLKjVtfdWlcDUfQ35Q0Hpln/xNpmknSJP+Rrpc0Qe3I2oBJ/RaiPSb xjk5Kk+ZoiZrBcfaWOZ10MafrSWXcC2HkhAN4gM43MAWNahvg0KqVrtgAiak p5ypqOpIfCm28kjbQm6YLjSbNljP3kQXZKYfwFI05KntF57/5ihFwKSk=} Ellison, et al. [Page 57] INTERNET-DRAFT Simple Public Key Certificate 29 July 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 <s-part> 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>:: "(" "crl" <version> <hash-list> <valid> ")" ; <hash-list>:: "(" "canceled" <hash>* ")" ; <delta-crl>:: "(" "delta-crl" <version> <hash-of-crl> <hash-list> <valid> ")" ; <hash-of-crl>:: <hash> ; 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 <delta-crl> 6.2 Revalidation <reval>:: "(" "reval" <version> <subj-hash> <valid> ")" ; <subj-hash>:: "(" "cert" <hash> ")" ; This construct specifies the hash of the current cert as <subj-hash> Ellison, et al. [Page 58] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 and gives a new validity period for that cert. It should be signed by the <principal> 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>:: "(" "reval" <version> <subj-hash> <one-valid> ")" ; <one-valid>:: "(" "one-time" <byte-string> ")" ; with the byte string inside <one-valid> 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 <principal> 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 59] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 7. 5-Tuple Reduction (full) 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 engine decision process. 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 <cert> by leaving out some fields and by augmenting the possibilities for <issuer>. This latter is because there are intermediate states in which the issuer holds a full SDSI name -- a state not allowed in normal <cert>. 7.1 <5-tuple> BNF A 5-tuple is a positional construct of the form: <5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ; <issuer5>:: <key5> | <fq-name5> | "self" ; <subject5>:: <key5> | <fq-name5> | <obj-hash> | <keyholder> | <threshold-subj> ; <deleg5>:: "t" | "f" ; <key5>:: <pub-key> | <sec-key> ; <fq-name5>:: "(" "name" <key5> <names> ")" ; <valid5>:: <valid> | "null" ; <tag-body5>:: <tag-body> | "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 Ellison, et al. [Page 60] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 key but referred to it by different hash algorithms. 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 which mean anything to the verifier, after reduction is done, are those with "self" as issuer. 7.2 Bare-bones case A bare-bones SPKI cert is reduced as described above in section 3.3.1. 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 *). <i1,s1,d1,a1,v1> + <i2,s2,d2,a2,v2> yields <i1,s2,d2,a,v> if: s1 = i2 d1 = "t" a = (* intersect a1 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. a = (* intersect a1 a2) in the bare-bones 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. Ellison, et al. [Page 61] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 7.3 Intersection of *-form tag sets The intersection of *-forms was presented above in section 4.3.3.1 by way of examples. The full rules are presented below. Via these rules any (tag)s can be intersected, but in actual practice it will probably be the case that intersection will start with a *-free form which will yield a *-free form for all intermediate results. However, for theoretical completeness, the following rules are provided: S, T: *-free S-expressions, assumed unequal A, B, C, D, E, F: byte-strings, assumed unequal in display type, string value or both U, V, X, Y, Z: any S-expression (*-free or *-form) X . Y = Y . X A . A = A A . B = (* null) A . U = (* null) U . U = U S . T = (* null) Y . (* set X_1 ... X_n) = (* set Y.X_1 ... Y.X_n) Y . (* intersect X_1 ... X_n) = (* intersect X_1 ... X_n Y) = (* intersect Y.X_1 ... Y.X_n) /* depending on which looks more productive */ /* do the second form if one of those becomes */ /* (* null) or if Y is *-free */ (* set (* null) X_1 ... X_n) = (* set X_1 ... X_n) (* set (*) X_1 ... X_n ) = (*) (* intersect (* null) X_1 ... X_n) = (* null) (* intersect (*) X_1 ... X_n) = (* intersect X_1 ... X_n) (* set X) = X (* intersect X) = X (* intersect X X Y_1 ... Y_n) = (* intersect X Y_1 ... Y_n) (* set X X Y_1 ... Y_n) = (* set X Y_1 ... Y_n) Both (* set) and (* intersect) are fully commutative, therefore any (* null) in a (* intersect) turns the whole result (* null) and any (* null) in a (* set) can be deleted, for example. X . (*) = X X . (* null) = (* null) Ellison, et al. [Page 62] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 7.3.1 Reduction to (* null) by data type mismatch If a byte-string is intersected with a list, the result is (* null). Some *-forms are of one data type or the other, so this can lead to reductions to (* null) at a high level. Specifically, (* prefix ...) (* range ...) are always byte strings, while (* append) (* reorder) (* reorder-insert) (* reorder-delete) are always lists. 7.3.2 Specific intersections U . (* append X) = U if X is a prefix of U U . (* reorder X) = U if X is a reordering of U U . (* reorder-insert X) = U if X is a reordering of a subset of U U . (* reorder-delete X) = U if X is a reordering of a superset of U A . (* prefix B) = A if B is an initial substring of A and has the same display hint as A A . (* range ...) = A if A is contained within the specified range and the range limits have the same display hints as A (* append X) . (* append Y) = (* append Y) if X a prefix of Y or (* append X) if Y is a prefix of X or (* null) (* reorder X) . (* reorder Y) = (* reorder X) if Y is a reordering of X (* reorder X) . (* reorder-insert Y) = (* reorder X) if Y is a reordering of a subset of X (* reorder X) . (* reorder-delete Y) = (* reorder X) if Y is a reordering of a superset of X Ellison, et al. [Page 63] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 (* reorder-insert X) . (* reorder-insert Y) = (* reorder-insert X) if Y is a reordering of a subset of X (* reorder-delete X) . (* reorder-delete Y) = (* reorder-delete X) if Y is a reordering of a superset of X (* prefix A) . (* prefix B) = (* prefix A) if B is a prefix of A (* range A B) . (* range C D) = (* range E F) by intersection of the two linear ranges 7.3.3 Deferred intersections Note that in every case it is legal to express X . Y as (* intersect X Y) if another rule for intersection would involve a great deal of work or if no rule is given. For example, intersection of sets could produce a huge set, with no real benefit, assuming that an eventual *-free form will yield a single element from each set. 7.4 Reduction of SDSI names By the rules for bare-bones SPKI 5-tuple reduction, <i1,s1,d1,a1,v1> + <i2,s2,d2,a2,v2> yields <i1,s2,d2,a,v> 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. We also modify the interpretation of d1 (to incorporate the so-called "stop at key" condition). <i1,s1> + <i2,s2> yields <i1,s2> if: s1 = i2 (d1 = "t") OR (s1 is a name rather than a key) With the introduction of SDSI names, both Issuer and Subject names are mapped to fully qualified SDSI names: (name <key> N_1 .. N_k) where k can be 0, in which case we have (name <key>). Ellison, et al. [Page 64] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 An Issuer inside a cert always maps to a single name or single <key> 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: <i1,s1> + <i2,s2> yields <i3,s3> Consider the general case: <(name k1 r_1 .. r_s),(name k2 n_1 .. n_m)> + <(name k2 n_1 .. n_p),(name k3 t_1 .. t_u)> where n_i is assumed to be the same on both sides of the + operator. If m = p, then the reduction is: <(name k1 r_1 .. r_s),(name k3 t_1 .. t_u)> If m > p, the reduction is: <(name k1 r_1 .. r_s),(name k3 t_1 .. t_u n_{p+1} .. n_m)> If m < p, the reduction is: <(name k1 r_1 .. r_s n_{m+1} .. n_p), (name k3 t_1 .. t_u)> The following sections give some examples to illustrate this procedure. 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: <i3, (name k1 fred sam)> + <(name k1 fred),(name k2)> = <i3,(name k2 sam)> Ellison, et al. [Page 65] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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": <i3, (name k1 fred sam)> + <(name k1 fred), (name k2 joe brother)> = <i3, (name k2 joe brother sam)> 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. Current plans for 5-tuple reduction call for the prover to drive the verifier with a fixed sequence, in which case this is not an issue. 7.4.3 SDSI Name composition with issuer name growth It is possible to imagine a pairing of 5-tuples in which the issuer name grows beyond 1 name. Start with the three 2-tuples: <(name k4),(name k1 alice joe)> + <(name k1 alice), (name k2)> + <(name k2 joe), (name k3)> If we group the reduction from the left, we get <(name k4), (name k2 joe)> + <(name k2 joe), (name k3)> = <(name k4),(name k3)> However, if we group from the right, we get <(name k1 alice), (name k2)> + <(name k2 joe), (name k3)> = <(name k1 alice joe), (name k3)> and <(name k4),(name k1 alice joe)> + <(name k1 alice joe), (name k3)> = <(name k4),(name k3)> The result is the same, but there is an intermediate result in which the issuer name grows. As in the previous example, we will need to be careful to make sure to detect and prohibit infinite loops of name Ellison, et al. [Page 66] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 growth in this case. 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. 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 Ellison, et al. [Page 67] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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. 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. Ellison, et al. [Page 68] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 8. Full BNF In the BNF to follow, top level constructs are: <sequence>, <cert>, <pub-key>, <signature>. <acl-entry>:: <subj-obj>* <deleg>? <tag> <valid>? <comment>? ; <acl>:: "(" "acl" <version>? <acl-entry>* ")" ; <all-set>:: "(" "*" ")" ; <byte-string>:: <bytes> | <display-type> <bytes> ; <bytes>:: <decimal> ":" {binary byte string of that length} ; <cert-display>:: "(" "display" <byte-string> ")" ; <cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>? <subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ; <comment>:: "(" "comment" <byte-string> ")" ; <date>:: <byte-string> ; <ddigit>:: "0" | <nzddigit> ; <decimal>:: <nzddigit> <ddigit>* ; <deleg>:: "(" "propagate" ")" ; <display-type>:: "[" <bytes> "]" ; <fq-name>:: "(" "name" <principal> <names> ")" ; <general-op>:: "(" "do" <byte-string> <s-part>* ")" ; <gte>:: "g" | "ge" ; <hash-alg-name>:: "md5" | "sha1" | <uri> ; <hash-of-key>:: <hash> ; <hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ; <hash-value>:: <byte-string> ; <hash>:: "(" "hash" <hash-alg-name> <hash-value> <uri>? ")" ; Ellison, et al. [Page 69] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 <impl-list-set>:: "(" "*" <list-set-type> <tag-body> ")" ; <issuer-loc>:: "(" "issuer-info" <uri>* ")" ; <issuer-name>:: <principal> | <simple-name> ; <issuer>:: "(" "issuer" <issuer-name> ")" ; <k-val>:: <byte-string> ; a binary integer <keyholder>:: "(" "keyholder" <principal> ")" ; <list-intersect>:: "(" "*" "intersect" <tag-body>* ")" ; <list-set-type>:: "append" | "reorder" | "reorder-insert" | "reorder- delete" ; <list-set>:: <impl-list-set> | <list-union> | <list-intersect> | <misc-set> ; <list-union>:: "(" "*" "set" <tag-body>* ")" ; <low-lim>:: <gte> <byte-string> ; <lte>:: "l" | "le" ; <misc-set>:: <all-set> | <null-set> ; <n-val>:: <byte-string> ; /* the number of <subj-obj> to follow */ <name>:: <relative-name> | <fq-name> ; <names>:: <byte-string> | <names> <byte-string> ; <not-after>:: "(" "not-after" <date> ")" ; <not-before>:: "(" "not-before" <date> ")" ; <null-set>:: "(" "*" "null" ")" ; <nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; <obj-hash>:: "(" "object-hash" <hash> ")" ; <online-test>:: "(" "online" <online-type> <uri> <principal> <s- part>* ")" ; <online-type>:: "crl" | "reval" | "one-time" ; Ellison, et al. [Page 70] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 <op>:: <hash-op> | <general-op> ; <prefix-set>:: "(" "*" "prefix" <byte-string> ")" ; <principal>:: <pub-key> | <hash-of-key> ; <priv-key>:: "(" "private-key" <pub-sig-alg-id> <s-expr>* <uri>? ")" ; <pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uri>? ")" ; <pub-sig-alg-id>:: "rsa-pkcs1-md5" | "rsa-pkcs1-sha1" | "dsa-sha1" | <uri> ; <range-ordering>:: "alpha" | "numeric" | "time" | "binary" ; <range-set>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>? ")" ; <relative-name>:: "(" "name" <names> ")" ; <s-expr>:: "(" <byte-string> <s-part>* ")" ; <s-part>:: <byte-string> | <s-expr> ; <sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>? ")" ; <sec-sig-alg-id>:: "hmac-md5" | "hmac-sha1" | "des-cbc-mac" | <uri> ; <seq-ent>:: <cert> | <pub-key> | <signature> | <op> ; <sequence>:: "(" "sequence" <seq-ent>* ")" ; <sig-val>:: <s-part> ; <signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ; <simple-name>:: "(" "name" <principal> <byte-string> ")" ; <simple-tag>:: "(" <byte-string> <tag-param>* ")" ; <string-intersect>:: "(" "*" "intersect" <byte-string>* ")" ; <string-set>:: <prefix-set> | <range-set> | <string-union> | <string- intersect> | <misc-set> ; <string-union>:: "(" "*" "set" <byte-string>* ")" ; Ellison, et al. [Page 71] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 <subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> | <keyholder> | <threshold-subj> ; <subject-loc>:: "(" "subject-info" <uri>* ")" ; <subject>:: "(" "subject" <subj-obj> ")" ; <tag-body>:: <simple-tag> | <list-set> ; <tag-param>:: <s-part> | <string-set> ; <tag>:: "(" "tag" "*" ")" | "(" "tag" <tag-body> ")" ; <threshold-subj>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ; <up-lim>:: <lte> <byte-string> ; <uri>:: <byte-string> ; <valid>:: <not-before>? <not-after>? <online-test>? ; <version>:: "(" "version" <byte-string> ")" ; Ellison, et al. [Page 72] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 Closed Issues 1) Should we require that all certificates be signed by both Issuer and Subject, when the Subject reduces to a key? [When the Subject is a non-key object, it can't sign.] [Answer: no. Signing by the Subject can not be prevented so it can be used if a need arises, but at present no security enhancement is seen to come from Subject signing. This seems to address the concerns of lawyers only.] 2) Can the Signature object support blind signatures with algorithms other than RSA? [Answer: yes -- any algorithm which supports blind signatures can be used here.] 3) Should we eliminate the final ":" in field names? These are always the first names in a list and the ":" seems to be a carry-over from RFC822 without a real purpose. [Answer: yes.] 4) Should we continue to lump public key algorithm, hash algorithm and padding algorithm together in one pub-key-name? This could lead to an explosion of names. Of course, on the other hand this might reduce the number of competing algorithm/hash/pad mixes and simplify code. [Answer: no. There are a number of proposals for expressing the components of a signature verification algorithm and one should settle out by the week after the April IETF meeting.] [Revised answer: yes, for now. Each of those proposals had a complication or flaw and we need to get this draft solidified.] 5) Should the delegation parameter be integer or boolean? [Answer: boolean is all people want, except for the third value "stop-at-key" proposed by Ron Rivest. It turns out that if delegate is false in a certificate with a SDSI name subject, then "stop-at-key" must be intended.] 6) Are object names (e.g., "Issuer") case sensitive? Ellison, et al. [Page 73] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 [Answer: yes. All other strings are, so these byte strings should be also. However, we decided to use all lower-case for object names that we define.] 7) Should we allow multiple <tag>s in one cert? It saves space and time, maybe, but could constitute a privacy threat and may complicate the cert reading code. [Answer: yes. The (* set ..) mechanism makes it easy to specify without constituting a serious complication to the 5-tuple reduction process.] 8) How much can we specify the <online-test>? Are there only a handful possible/desirable tests, that we can fully spell out, or do we need to leave that open for invention? [Answer: this draft includes full specification of online tests.] 9) How many pre-defined <tag>s should we bother defining? [Answer: none should be cast in stone here -- only examples provided to spur the imagination of developers.] 10) If the Subject is a hash of a Bundle of hashes of keys, does this mean that the cert applies to all keys in the bundle? [Answer: no -- although this is a discussion left to be addressed by the folks who sign web pages.] 11) If the Subject is a hash of a file and the file contains hashes of other things, does the cert apply to the other things? [Answer: no, according to general opinion. This is a more general issue which the community needs to consider. Perhaps W3C DSig will be the first to encounter examples of this in practice.] 12) Do we want to include validity fields for private key dates, as was done with X.509v3? [Answer: not at this time and not in these certificates. An SPKI/SDSI certificate doesn't define a public key. The public key is a primitive. There remains open the question of whether we want keys to expire and, if so, what kind of a data structure we want to support key validity dates. The subject-info field can point to or yield such a structure, should we define one.] Ellison, et al. [Page 74] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 13) How do we want to name algorithms? One possibility is to define a few common ones (ones we want to encourage everyone to use for interoperability reasons) and allow others to be defined as URIs pointing to the definition of the algorithm. [Answer: we will choose short names and turn the process over to IANA, but allow URIs for user-defined algorithm names. Presumably the URI will give a description of the algorithm and maybe even code to implement it.] 14) Should we restore the explanation of [ECR] and define a <valid> field option for it? This was removed from this draft in the interest of simplification. [Answer: there has been no request for its restoration.] 15) Should we allow Object as an optional element of the Signature expression, or force that block to give the Object's hash? [Answer: this draft assumes that (signature ) contains only the object hash, not the object, in order to avoid the complexity of ASN.1's "SIGNED" macro and to permit multiple signatures on the same body without habit getting in the way.] 16) Should we define an RSA signature algorithm with no hash and no padding, to hold verbatim objects being signed (assuming they are small enough)? [Answer: no.] 17) What is the difference between the Member and Name <tag>? Can they be combined into one? [Answer: these tags have disappeared with the use of names in the issuer field.] 18) Should we restrict the <issuer> definition to preclude the possibility of the same cert body being signed by multiple keys as Issuer (which can happen when the <issuer> is a general SDSI name resolving to a key)? If so, should we permit an <issuer> to be a group name, thus allowing the (Moi) <tag> to define SDSI group membership? [Answer: this is an irrelevant question under the current specification.] Ellison, et al. [Page 75] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 19) [RLR] Should we replace the display info syntax [xxx] "yyy" with ( display-type xxx "yyy" ) ? [Answer: no.] 20) [RLR] Should we have only one spelling of each object type? If so, should it be the long or the short form? Can we make such spellings short enough that they don't force line continuations while keeping them descriptive? [Answer: one spelling, preferably one English word (so that a user can look it up in a dictionary).] 21) [CME] Are object types reserved words over the entire certificate body or are they to be non-conflicting only within their enclosing object? [In the latter case, the ( Tag XXX ... ) object is to be considered to be of type "Tag XXX".] That is, when we go into an object, do we acquire a new dictionary of object types relevant to the interior of that object or do we use a single global such dictionary? [I believe we have to use local dictionaries, in order to allow distributed <tag> definition.] [Answer: object names have scope only within an object which defines them.] 22) [RLR] Should we allow the Subject to optionally be the hash of some non-key object? This could be seen as encroaching on the territory of signed PICS labels. [Answer: yes. It's desirable enough and we don't want to force all tags into the form of a PICS rating. On the + side, this permits the single trust management program to decide if a document or program is permitted to run. On the - side, this doesn't help much with on-line access control protocols.] 23) [RLR] Should we define another, non-cert object, ( assert .. ), to cover signed statements about non-keys? [Answer: no.] 24) [RLR] Should we make a clear statement that the keys used in these certs are signature keys? [[CME] I think that's understood from the fact that the only crypto we use is for signatures.] [Answer: yes -- this should be clear in the document.] Ellison, et al. [Page 76] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 25) [RLR] Should we continue to use different object types for fq- name, rel-name and grp-name, or use "Ref" as the type and let the parameters determine which is intended? [Answer: no -- use "ref", although that is not an English word. Re-answered: use "name" instead of "ref", because it's English.] 26) [RLR] Should we define (keyholder <principal>) to mean the human or computer etc. who/which holds a private key, to be used in Subject lines? [Answer: yes.] 27) [RLR] There are different cert-like entities, in that they all reduce to 5-tuples, but they may have different object names and slightly different BNF definitions: a) certificate -- subject is a <principal> b) assertion -- subject is a cyberspace object c) request -- (a kind of assertion) d) ACL entry -- issuer is missing e) auto-cert -- subject is (keyholder [of] <principal>) [Answer: call them all certificates, except ACL. Request is a wide open term, so that is probably different from certificate also. This draft includes a field in <cert> for a cert display type, so that the issuer can label the kind of cert.] 28) [RLR, CME] As written now, it is inconsistent to have a name as a Subject in a cert with (delegate false). RLR proposes that (delegate to-key) mean that propagation occurs through certificate sub-chains which have non-key subjects and stop when the subject is a key. [Answer: use to-key as an argument to delegate, but rename delegate to propagate. Revised: (propagate) means delegate; lack of that field means "stop at key".] 29) Should we extend <deleg> to permit a group name or key as a parameter, that being the group of principals allowed to delegate? [Answer: no -- too complicated.] Ellison, et al. [Page 77] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 Open Issues 1) [RLR] Let's add a section to the I-D showing how each of the original SDSI constructs is handled in SPKI. [[CME] We could also add a section for PICS labels, X.509 certs, PGP signed keys, ...] 2) Should we start another draft to cover operation of a certificate server (as in SDSI 1.0) including protocols for communicating with it or should that discussion be in this draft? 3) Should we start another draft to cover fully worked out examples of tags for real operations (e.g., FTP, HTTP) or let those be part of this draft? 4) What kind of <cert-display> parameters might we want to allow? Do we want <cert-display> in the first place? 5) [BL] Why not replace (* reorder-insert X) with (* reorder (* append X)) ? 6) [CME] We need to specify (online..) protocols -- perhaps a variety of them (HTTP, socket connection, e-mail, ...). Ellison, et al. [Page 78] INTERNET-DRAFT Simple Public Key Certificate 29 July 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) [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 Security and Reliable Software", Computing Surveys 8(4), December Ellison, et al. [Page 79] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 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 80] INTERNET-DRAFT Simple Public Key Certificate 29 July 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 Ellison, et al. [Page 81] INTERNET-DRAFT Simple Public Key Certificate 29 July 1997 Telephone: +1 314-235-3141 +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 29 January 1998. Its file name is draft-ietf-spki-cert-structure-02.txt Ellison, et al. [Page 82]