Simple Public Key Certificate Carl M. Ellison INTERNET-DRAFT CyberCash, Inc. Expires: 30 September 97 Bill Frantz Periwinkle Brian M. Thomas Southwestern Bell 25 March 1997 Simple Public Key Certificate ------ ------ --- ----------- Status of This Document This document supersedes the draft filed under the name draft-ietf- spki-cert-structure-00.txt and reflects changes in the structure to prepare the way for merging the SPKI certificate structure of the previous draft with the SDSI proposal of Rivest and Lampson. The primary change is the use of S-expression format for data objects such as certificate bodies. A section giving the BNF of all data objects is given so this draft is more complete than the previous one. It has also been simplified in a number of places. 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 or to the authors. This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six Ellison, Frantz, Thomas [Page 1] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 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, Frantz, Thomas [Page 2] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 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 been generally 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 transfer 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 were considered necessary. As Internet use increases, we increasingly interact with people or companies with whom we have no relationship in the physical world. A transfer of relationship from the physical world to the digital world is meaningless in such cases. Instead, we need to establish relationships directly in the digital world through an instrument which assigns attributes (authority, permission, ...) to the digital principal. We call that an "authorization certificate". SPKI certificates were designed to perform that function by directly specifying the binding which is of interest in the digital world. Acknowledgments Several independent contributions, published elsewhere on the net or in print, worked in synergy with our effort. Especially important to our work were: [SDSI], [BFL] and [DNSSEC]. 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 and we must thank Butler Lampson for most of this inspiration. 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, Paul Lambert, Jon Lasser, Jeff Parrett, Ron Rivest, Bill Sommerfeld, Simon Spero. Ellison, Frantz, Thomas [Page 3] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 Table of Contents Status of This Document....................................1 Abstract...................................................3 Acknowledgments............................................3 Table of Contents..........................................4 1. Overview of Contents....................................6 2. Scope Of This Effort....................................7 2.1 Charter of the SPKI group..............................7 2.2 Areas Covered And Not Covered..........................7 2.2.1 Key and certificate storage..........................7 2.2.2 Protocols to use public key authentication...........8 2.3 Other Certificate Formats..............................8 2.4 Goals of this effort...................................9 2.5 SPKI Certificates vs. Capabilities.....................9 2.6 Chosen standard format.................................9 3. Assumptions, Definitions and Design Issues.............10 3.1 Background............................................10 3.2 Binding of key to principal...........................11 3.2.1 Protection of Private Keys..........................11 3.2.2 Definition of KEYHOLDER.............................12 3.3 Certificate Structure.................................13 3.3.1 5-tuple Reduction...................................13 3.3.2 Authority Loops.....................................14 3.3.3 Certificate Result Certificates.....................14 3.4 Policy Structures.....................................15 3.4.1 Equality of ..................................16 3.4.2 Partial ordering of s.........................16 3.4.3 General fields...............................16 3.5 Certifying Identity with SPKI Certificates............16 3.6 Certificate validity periods..........................17 3.7 Unwanted Attributions.................................19 3.8 Secret Certificates...................................19 3.9 Blind Signatures......................................20 4. Data Object Formats....................................21 4.1 BNF of SPKI Objects...................................21 4.1.1 Version.............................................24 4.1.2 Issuer..............................................24 4.1.3 Issuer-cert-loc.....................................24 4.1.4 Subject.............................................24 4.1.5 Subject-info-loc....................................25 4.1.6 May-delegate........................................25 4.1.7 Auth................................................25 4.1.7.1 Auth field reduction rules........................25 Ellison, Frantz, Thomas [Page 4] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 4.1.7.2 Auth global uniqueness............................26 4.1.8 Comment.............................................26 4.1.9 Not-after, Not-before...............................26 4.1.10 Online.............................................26 4.1.11 Signature..........................................27 4.1.12 Bundle.............................................27 4.1.13 ..........................................27 4.1.14 Hash...............................................27 4.1.15 ...................................28 4.1.16 Fully-qualified-name...............................28 4.1.17 Ref................................................28 4.1.18 Date...............................................29 4.2 Primitives............................................29 4.2.1 byte-string.........................................29 4.2.1.1 token.............................................29 4.2.1.2 quoted string.....................................29 4.2.1.3 hex string........................................29 4.2.1.4 base64 string.....................................30 4.2.1.5 literal binary string.............................30 4.2.1.6 concatenation of strings..........................30 4.2.2 Display information.................................30 4.2.3 List counts.........................................31 4.3 Binary (canonical) form...............................31 4.3.1 Byte strings........................................31 4.3.2 List counts.........................................31 4.3.3 blanks..............................................31 5. Field Examples..................................32 5.1 Member-of-issuer......................................32 5.2 Name..................................................32 5.3 Member................................................32 5.4 FTP...................................................33 5.5 HTTP..................................................33 5.6 TELNET................................................33 5.7 Public Key Protected File System......................33 5.8 Dating Service Bindings...............................34 5.9 Authority to spend money..............................34 Issues....................................................35 References................................................37 Authors' Addresses........................................39 Expiration and File Name..................................39 Ellison, Frantz, Thomas [Page 5] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 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 a certificate and giving encoding details. Section 5 describes predefined SPKI fields. These are the meat of an SPKI certificate, since they carry the authority or other information being bound to a subject public key. The 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, Frantz, Thomas [Page 6] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 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 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 [DNSSEC], specifies an efficient key storage and distribution mechanism. It may be possible to store an SPKI certificate in a KEY Resource Record (RR) or to create a new Ellison, Frantz, Thomas [Page 7] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 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. SDSI 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. 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. 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 Ellison, Frantz, Thomas [Page 8] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 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 and confidentiality for the Internet. We use well tested formats with a long history of success and have chosen those which require the bare minimum of tool software so that applications remain as small and efficient as possible. We offer the bare minimum of options, in order to reduce program size and complexity. We also recognize that some kinds of certification (such as notarized identity certification) can carry risks of invasion of privacy for the individual. We have therefore designed these certificates to reveal the minimum information necessary to get the job done, whatever that job happens to be. In many cases, the user can remain anonymous in the traditional sense while exercising strongly verified authorization. 2.5 SPKI Certificates vs. Capabilities An SPKI certificate is closer to a "capability" as defined by Butler Lampson et al. 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 (cash rather 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 individual or group to whom it grants authority and therefore the ability to read the certificate grants no authority and the certificate itself does not need to be as tightly controlled. 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. Ellison, Frantz, Thomas [Page 9] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 3. Assumptions, Definitions and Design Issues There were a number of discussion topics involved in the design of the 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. 3.1 Background In the words of Butler 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 spoofable 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, giving bindings which needed to be combined with certificates or ACL entries giving , to yield the relationship which a computer needs to verify public-key driven access attempts. { 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 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 inappropriate. We also observed that is a perfectly adequate name for a keyholder, at least as far as a computer is concerned. We therefore set about declaring a certificate which would communicate 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). Ellison, Frantz, Thomas [Page 10] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 3.2 Binding of key to principal The most important issue is the notion of the binding of a key to a principal. By PRINCIPAL, we mean an entity (e.g., person, processor, process, device (such as a printer), ...) which supplies a service or requests action in a distributed computer system. Discussions of certification frequently speak of binding of keys to an "identity" (specifically, under X.509, to a Distinguished Name) as if the "identity" were the same as the principal and as if the identity certificate accomplished the binding of key to principal. We observe that the binding between a public key and a principal has nothing to do with certificates. Here we distinguish between a principal and its name or "identity", however one defines that latter term. 3.2.1 Protection of Private Keys For any public key cryptosystem to work, it is essential that a principal 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 SmartCard 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 principal does not keep the private key protected (that is, if the private key gets out to others to use) then one can not know what entity is using that key and no certificates 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 principal 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. Ellison, Frantz, Thomas [Page 11] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 Note: We have specifically included the possibility for a holder of authority to delegate that authority without appeal to some certification authority, in order to reduce if not eliminate the motivation for one principal to loan a private key to another. 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. 3.2.2 Definition of KEYHOLDER The keyholder has sole possession of the private key by definition and could be identified by that key, but that key is secret. There is only one private key to match a given public key, so the keyholder can be identified by the public key just as uniquely. Similarly, there is only one public key which hashes to a given secure hash (by definition of "secure hash", assuming we are limited in computation power), so the secure hash of a public key can also be used to identify the keyholder. DEFINITION: Keyholder -- a principal who holds a given private key. The private key is indicated by either its corresponding public key or a secure hash of that public key. Every key has a keyholder, by definition. There is no implication in the word "keyholder" that anything else is known about this principal except the fact that it holds the indicated private key. Without certificates, we might not know anything else about the principal (such as name, gender or even if the principal is a living being) but we do know enough to link together separate messages from the same principal. 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. Ellison, Frantz, Thomas [Page 12] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 3.3 Certificate Structure An SPKI certificate body has five groups of fields: ISSUER: the public key of the issuing party or something reducible to that public key, both as a means for verifying the certificate signature and as a name for the issuing principal. SUBJECT: the object receiving authority via this certificate or something reducible to that object (usually a key or the hash of a key or a document). MODIFIERS: modifiers on the certificate. At present the only one defined is "May-delegate:" -- the permission to delegate the authority presented in the certificate (or part of it) to some other Subject. AUTHORITY: the specific authorization(s) being delegated in this certificate. Section 5 gives details about fields. VALIDITY: at least an expiration date but possibly a more complex procedure for determining certificate validity. Section 6 gives details about validity fields. A certificate is signed by the issuer and, optionally, by the subject. The dual signature is required for authorizations which also imply responsibilities. The issuer is granting an authorization, but the subject is accepting responsibility. Each of those actions requires a signature. Section 7 gives details about signature blocks. 3.3.1 5-tuple Reduction The authorization statement in a valid certificate can be represented by five quantities: (I,S,D,A,V) A set of certificates can be reduced as follows: (I1,S1,D1,A1,V1) + (I2,S2,D2,A2,V2) becomes Ellison, Frantz, Thomas [Page 13] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 (I1,S2,D2,A,V) if S1=I2 (meaning that they are or resolve to the same public key) and D1 > D2 (if delegation is integer) or D1 >= D2 (if delegation is boolean) and A = intersection(A1,A2) and V = intersection(V1,V2) 3.3.2 Authority Loops By 5-tuple reduction, some chains of certificates will be reduced to the form: (Self,X,D,A,V) where "Self" represents the computer doing the verification, granting access, etc. Such a 5-tuple says "Self says that X has authority (D,A) for validity period (or conditions) V". In other words, it tells Self what it can trust about X. Any certificate chain not reducing to a 5-tuple with Self as issuer isn't relevant to decisions by Self. Therefore, any certificate 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, that makes all useful authorization certificate chains loops. 3.3.3 Certificate Result Certificates If one has reduced a chain of certificate bodies down to the form: (Self,X,D,A,V) one can sign that generated body, using a private key of Self, producing an SPKI certificate. Such a certificate is the result of 5-tuple reduction (and possibly PolicyMaker execution) over one or more certificates (which could be of various formats, including SPKI, X.509, DNSSEC, ...). This certificate result certificate, CRC, could then be given back to the caller (protocol permitting) for that caller to use throughout interval V. Such a certificate should reduce transmission and verification time. The signature used by Self could even employ a secret-key algorithm, on the assumption that the issuer and verifier are the same entity. Alternatively, one Ellison, Frantz, Thomas [Page 14] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 could use a public-key-signed CRC to enable a trusted server to translate certificate formats from something difficult to deal with (such as X.509) into SPKI. 3.4 Policy Structures [BFL] introduces a language called PolicyMaker in which one can express security policy statements -- the specific certificate requirements by which a given action will be authorized. The actual requirements are written in a safe language which program is then bound to a key or set of keys by an issuer's signature. PolicyMaker is likely to be used along with SPKI certificates in three ways. 1) It is believed possible to use the PolicyMaker language to implement the 5-tuple reduction described in the previous section. The code has not been written as of the time of this draft, but at this point it looks possible. 2) The default reduction rule is an operation on two certificate bodies yielding a third. For some policies, there are more than two input bodies and therefore the reduction code needs to be more general than the simple rules given in the section above. 3) For some kinds of trust management, it will be necessary to translate fields. That is, the simple rule A=intersection(A1,A2) makes it impossible for A to be greater than either A1 or A2. For example, if company policy is that a purchase order is good only if signed by two vice presidents, A1a might be "signed by VP #1" and A1b might be "signed by VP #2", while A=A2 might be "purchase order is good". Neither of the VPs has the authority to make a purchase order good by himself or herself. Therefore, A > A1a and A > A1b. The first case is a matter of coding convenience. The others are cases of logic of trust management. There must be machinery in the verifying engine which reduces certificate bodies. For everything but fields, this is straight-forward. Since every verifier of certificates is permitted to define custom fields, with custom semantics, the simple reduction rules given above might not suffice and full PolicyMaker programs might be needed. Ellison, Frantz, Thomas [Page 15] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 Three forms of processing during 5-tuple reduction are envisioned for the engine running in the verifier: 3.4.1 Equality of This simplest of reduction operations applies when fields are equal. No logic is required to supplement the reduction operation. 3.4.2 Partial ordering of s If the definer of the field specifies rules for partial ordering of those fields, the engine which reduces them can choose the lesser of A1 and A2 and choose that as A -- to perform the normal reduction indicated above. 3.4.3 General fields In the most general case, the definer of the field must provide a program which reduces these fields. That program is not limited to taking two certificate bodies in and producing one on output, as is true for the default rule. It can take one or more certificate bodies and produce one or more outputs (although a single output is probably sufficient for our purposes). 3.5 Certifying Identity with SPKI Certificates It is possible to certify identity with an SPKI certificate. We support the SDSI naming mechanism, since we recognize that all names are local to some name-space -- even when that name-space desires to be treated as global. [SDSI] recognized that all names are local, even those generated by an allegedly global CA. More importantly, for a name to be meaningful, it must be known by the person or program using it (the verifier) and unambiguously associated by that verifier with the person or object (the subject) to which it refers. In the case of a person as verifier, this name space is inherently limited in size and complexity by the capacity of a human memory. SDSI achieves a global name space by linking together local name Ellison, Frantz, Thomas [Page 16] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 spaces. That is, two people, Alice and Bob, may each have a friend they call Carol. To each of them, the name (ref: carol) is used. If Ted knows both Alice and Bob, then Ted might have occasion to speak with each of them about Carol. Not necessarily having met Alice's or Bob's Carol, Ted uses the names (FQN: K-ted alice carol) and (FQN: K- ted bob carol). David might be able to tell that Alice and Bob know the same Carol by inspecting the certificates issued by Alice and Bob for Carol: (K-alice,K1,D1,"(Name: carol)",V1) (K-bob,K2,D2,"(Name: carol)",V2) If K1 = K2, then Alice and Bob both use the name Carol to refer to the same person. However, Alice and Bob are free to reorganize their local name spaces at will, without notifying anyone who might have learned name mappings, so this equality of keyholders can be considered valid only for the shorter of the two certificate validity periods. After that period, Ted may have to get new certificates from Alice and Bob to determine if they still refer to the same person by the name Carol. Of course, this is an academic exercise since the names by which Alice and Bob know the keyholder of K1 is probably of limited importance. Under SDSI, a name might be an individual or it might be a group. One could think of an individual as a group of one member, in which case all SDSI names can be thought of as groups. The entity defining that name is responsible for issuing certificates binding a key to the name or declaring that the principal (the key) is a member or not a member of the named group. SDSI names are defined with the fields: Name: and Member: described later in this document. 3.6 Certificate validity periods Our experience with credit cards has influenced the way we consider validity periods of certificates. A credit card is issued with an expiration date 1 to 3 years later than the date of issue, yet one can revoke a credit card and have that revocation be effective within a day of the request. That credit card has a validity period of one day (or less) in spite of its expiration date. At one time, credit card validity was verified at a checkout counter Ellison, Frantz, Thomas [Page 17] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 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. An authorization certificate can be stored in read-write storage, since it is protected from tampering by its digital signature(s). Therefore, it has a third option for short-term validity checks. It can hold a guaranteed validity time which is re-written as needed during an on-line check, but can be trusted without the on-line check until that time. All of these methods of validity checking are functionally equivalent but they have different performance impacts. CRL: If one can afford to keep a copy of the CRL, there is the communications load of accepting periodic additions to the CRL (hopefully very small and relatively infrequent). Each verification then requires a local memory reference. If the CRL must be delivered by the supplicant or fetched from an on-line source with each verification, then the communications load of CRL usage is proportional to CRL size and can become very high. On-line: The communications load for on-line checking is constant. Periodic-revalidation: If a certificate is used more than once during its validity period, periodic-revalidation provides a caching effect, saving the communications load for on-line checking. It also permits the supplicant to perform the on-line check and distributes that load away from the verifier. Because of the time it takes to communicate and the need to allow for clock skew, a validity period can never go to zero. The shorter the period, the less risk an issuer runs of having a withdrawn authorization active in the world. The longer the period, the less communication and revalidation overhead is incurred. Choice of Ellison, Frantz, Thomas [Page 18] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 validity period is left up to the issuer of the certificate. The closest one can get to zero-length validity fields is an on-line check with random challenge response, so that it can not be replayed. Such a check can be considered valid only for that one transaction. 3.7 Unwanted Attributions There is a potential problem that a certificate might be issued which the keyholder does not want. For example, a keyholder, Alice, has a signature key, K, being used to sign digital lab notebooks for later use in patent applications. That key is certified as hers by her company through an SPKI identity certificate with an EMPLOYEE field. Bob learns Alice's public key and builds a certificate using his own name and her key, getting it signed by some reputable commercial CA. Now when it comes time to dispute prior art on Alice's patent(s), Bob produces his certificate and claims that Alice had copied not only his work but his private signature key. For another example, Bob could give Alice read-write access to a directory structure Bob intends to corrupt, blaming that corruption on Alice. To resolve this, some certificates should be signed by the as well as by the . An identity certificate is one such. It is an open issue whether we should require all certificates with keys for s to be signed by both and . 3.8 Secret Certificates Some certificates need to be kept secret (e.g., a certificate binding a name to a symmetric-algorithm signature key). Such certificates can be encrypted in a key known only to the intended verifier. In some cases, it is that verifier who issued the certificate and in that case it can be kept in protected storage at the verifier and never given out. Ellison, Frantz, Thomas [Page 19] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 3.9 Blind Signatures The issue of blind signatures was raised on the list. 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. It is an open issue whether blinding of other algorithms can be accommodated as easily. Ellison, Frantz, Thomas [Page 20] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 4. Data Object Formats Borrowing heavily from the SDSI work, we define a certificate format using S-expressions. An S-expression is a list whose first item is a token giving the name of the object (or identifying some program to run) while the remaining items are parameters. These parameters can be positional and merely tokens or they can be lists whose first token is the name of the parameter. In most cases we assume parameters are named and leave positional definitions as an option for those who create their own expressions. There is a set of rules for converting from S-expression to a minimal size binary format. That is the form which is fed to a hash function when signing an object. It is also available as a binary format for transmission into a device with small memory or slow interface (such as a SmartCard). Those rules are given below, in section 4.3. It is our intention to provide C programs for converting between binary and S-expression formats. We take as a rule that the thing signed is the binary of the thing transmitted, even if it is transmitted in S-expression format. That is, the transmitted object specifies order and content of parameters. The binary conversion provides space-saving and canonicalization. 4.1 BNF of SPKI Objects The following defines an SPKI certificate and related objects, expressed here in pseudo-BNF -- with "*" meaning closure (0 or more occurrences) and "?" meaning optional (0 or 1 occurrence). At the top level (not used internally in any other object) are the following three objects. Other objects (such as ) might also occur at a top level, to be hashed and referred to by hash. :: "(" ? ? ? * ")" ; :: "(" ")" ; :: "(" * ")" ; Note that the fields in a don't need to be in the order given by the BNF, because they are all self-identified, but we recommend that they be given in that order, for human readability. Defined below are the other elements of this BNF description. Ellison, Frantz, Thomas [Page 21] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 :: "Auth:" | "A:" ; :: "Bundle:" ; :: "Certificate:" | "C:" ; :: "D:" | "May-delegate:" ; :: "FQN:" | "Fully-qualified-name:" ; :: "H:" | "Hash:" ; :: "IL:" | "Issuer-cert-loc:" ; :: "Issuer:" | "I:" ; :: "Member-of-issuer:" | "Moi:" ; :: "Not-after:" | "NA:" ; :: "Not-before:" | NB:" ; :: "K:" | "Public-key:" ; :: "Signature:" | "Sig:" ; :: "SL:" | "Subject-info-loc:" ; :: "Subject:" | "S:" ; :: byte-string ; :: "(" token * ")" | ; :: "(" "Comment:" byte-string * ")" ; :: "(" ")" ; :: "(" ")" ; :: "SHA1" | "MD5" | etc..... ; :: ; :: byte-string ; :: "(" ? ")" ; Ellison, Frantz, Thomas [Page 22] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 :: byte-string ; :: byte-string ; :: "(" * ")" :: "(" ")" ; :: byte-string ; :: token | token ; :: "(" ")" ; :: "(" ")" ; :: "(" "Object:" byte-string ")" ; :: "(" "Online:" * ")" ; :: byte-string | ; :: "(" "FTP:" ")" | "(" "HTTP:" ")" | "(" "Name:" token ")" | "(" "Member:" token ")" | "(" ")" | etc.... ; :: | | ; :: "(" ")" ; :: "(" "RSA-SHA1-PKCS1:" "(" "E:" ")" "(" "N:" ")" ")" | "(" "RSA-SHA1-PKCS1:" ")" | etc.... ; :: "(" "Ref:" ")" ; :: "(" token * ")" ; :: "(" "HMAC-SHA1:" ")" | etc.... ; :: ; :: | ; :: | | | ; :: "(" * ")" ; Ellison, Frantz, Thomas [Page 23] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 :: "(" ")" ; :: ? ? ? ; :: "(" "Version:" ")" ; 4.1.1 Version If the version number is not specified, the version is 1. 4.1.2 Issuer The issuer is a principal -- that is, a public key or something which can be reduced to a public key -- because it is used to sign certificates. 4.1.3 Issuer-cert-loc The optional issuer certificate location field is for information only. It gives a network address of a web page or server which can return the issuer's certificate authorizing the current certificate. 4.1.4 Subject The subject is a principal or something reducible to one, in the normal case, but has been extended to also be a secret signature key or the hash of an object. 1: principals include: a: a public key b: a fully qualified name c: a hash of a public key d: a relative name (anchored in the name-space of the issuer) 2: secret signature key -- like a principal, but there is no public key which can be given out. The certificate which defines a mapping to this secret key must itself be kept secret. This certificate could define a name in the issuer's name-space as a name for that key and the name could be used elsewhere. Ellison, Frantz, Thomas [Page 24] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 3: hash of an object -- in case one wants to assign attributes to an object. E.g., a purchase order could be "signed by VP # 103", where that latter string is an field and the P.O. is the Subject of the certificate. 4.1.5 Subject-info-loc The subject information location is an optional field which provides the location of a network resource where one can learn about the Subject -- e.g., find the subject public key, find the subject's home page, etc. 4.1.6 May-delegate The May-delegate field is the only modifier defined on a certificate so far. It is defined to take an integer parameter, currently, but that may be changed to a boolean. This is an open issue. 4.1.7 Auth The Auth field can be a pre-defined field, described in section 5, or a custom field defined by a developer who is programming a use of certificates. The custom definitions are of the form: "(" token * ")" where the token is the developer's name for this and the optional list of parameters are as defined by that developer. These parameters can be position sensitive or can be S-expressions of the form "(" ")" at the developer's discretion. 4.1.7.1 Auth field reduction rules When a developer defines a new field, he or she must also define how the new field is to be reduced. By default, two Ellison, Frantz, Thomas [Page 25] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 certificates which have identical fields will reduce provided the rest of the 5-tuple fields permit it. If strict equality is not adequate, the developer can define partial ordering between fields (e.g., sorting rules over different parameters). If partial ordering relationships aren't adequate to reduce the intended fields, then the developer can write a program to do that reduction (as described elsewhere, under the heading of PolicyMaker). 4.1.7.2 Auth global uniqueness If a developer desires to have a unique name for his or her token in some global name-space, that name can have a true random string appended, with length of string chosen according to the risk of accidental duplication of name the developer is willing to tolerate. 4.1.8 Comment A comment field may contain any text or other strings the author desires. These strings may have display instructions. The comment is included in the signature of a certificate, but is not expected to be read by any computer program. 4.1.9 Not-after, Not-before The not-before and not-after dates are normal validity dates for a certificate. In many cases, there is no other validity constraint needed. However, for those other cases, the Online: directive is provided. 4.1.10 Online The Online: validity option gives the location of a remote service which will pass judgment on the current validity of a certificate. Details of such a service have not been specified at the time of this draft. There is an open issue about whether we should include specification of one or more such services beyond merely making room for such specifications in the certificate definition. Ellison, Frantz, Thomas [Page 26] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 4.1.11 Signature A signature expression can refer to anything, but typically a certificate body. If the object hash is used (as expected), that hash must use the same hash algorithm specified in the signing key. In that case, the hash value given in the Signature expression is the one which is to be used to verify the signature. 4.1.12 Bundle A bundle expression is provided only for convenience, in case someone wants to bundle a set of public keys and certificate bodies and signatures into one expression for communication. 4.1.13 A public signature key expression, for example: (K: (RSA-SHA1-PKCS1: &03 =gJVtABwLSwwTVM0tg1QPgsOVUoA5EjPz- =UtNKU3PLElkMk0IAE0yhyy0zYuwVSnQzFEvM0hSns1OKzC08AO0SB84yUsDTgDnL- =fAyVYtRCHAyPlW0NTDPKcksSh9Tt9EwuQ1SsEgAtMy0XQAAKSxVtA4KODLkzjQzz- =VFIL00pUc9J= ) ) defines a public key algorithm, a hash algorithm and a padding method (PKCS1 in this example). A public key can be transmitted at the top level of a communication. In that case, it is assumed that the key is referred to by hash in the body of one or more certificates in the same communication. 4.1.14 Hash A hash expression, for example: (H: SHA1 =SxVtA4KODLkzjQzzVFIL00pUc9J= ) or (H: SHA1 =SxVtA4KODLkzjQzzVFIL00pUc9J= http://ietf.org/ ) gives a hash algorithm name and a hash value of some object. Optionally, the hash expression also gives a URI of that object. Ellison, Frantz, Thomas [Page 27] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 4.1.15 A secret signature key expression, for example: (HMAC-SHA1: &17fa34017c320401 &75e3391ac90d0a38 ) gives the secret key values for computing a MAC, keyed hash or encrypted cookie, to permit a symmetric algorithm to be used for signatures. This is expected to be faster than a public key algorithm, but is limited to cases where the signer and the verifier have mutual trust. 4.1.16 Fully-qualified-name A fully qualified SDSI name, for example: (FQN: (H: SHA1 =SxVtA4KODLkzjQzzVFIL00pUc9J= ) fred sam ) specifies a key (and therefore its name space) for the first name in the list ("fred" in this example). That first name can then be resolved to a key and the process recurses until the FQN is reduced to a key. The example above might reduce to: (FQN: (H: SHA1 =yy0zYuwVSnQzFEvM0hSns1OKzC0= ) sam ) etc. 4.1.17 Ref A Ref expression is a relative name. It is converted to a fully qualified SDSI name by using the Issuer of the certificate of which it is a part as the key defining the name-space. (Ref: joe fred sam) might become (FQN: (H: SHA1 =SxVtA4KODLkzjQzzVFIL00pUc9J= ) joe fred sam ) for example. Ellison, Frantz, Thomas [Page 28] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 4.1.18 Date A date field is an ASCII byte string of the form: YYYY-MM-DD_HH:MM:SS assumed to be UTC, with lower significance time fields optional and taken to be 0 if missing. For internal use, it is treated as a normal byte string. Dates are compared as byte string comparisons. 4.2 Primitives Not defined in the BNF above are the primitives: byte-string and token. 4.2.1 byte-string A byte string is the general atomic element of a list. It can be expressed in a number of different ways, in ASCII S-expressions: 4.2.1.1 token A token is a sequence of printable characters other than parentheses, braces, single or double quotes, square brackets, hash mark, equal sign or ampersand. It may not start with a digit or end in a minus sign. Such a token does not need to be quoted. 4.2.1.2 quoted string A string not containing a double quote can be quoted in double quotes. A string not containing a single quote can be quoted in single quotes. 4.2.1.3 hex string A byte string can be represented in hex by preceding the hex characters with an ampersand, "&", and terminating it with a blank. Ellison, Frantz, Thomas [Page 29] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 4.2.1.4 base64 string A byte string can be represented in base64 by preceding it with an equal sign, "=", and terminating it with a blank. The base64 string must be a multiple of 4 characters in length, although it may end with "=" character(s) to show that it is short 1 or 2 bytes of being a multiple of 3 bytes in binary. 4.2.1.5 literal binary string A byte string can be represented as a literal string of binary bytes by prefixing it with a length and a colon, ":". The length is expressed in base 256, prefixing each byte of the length with a hash mark, "#". If "\001" stands for the byte 0x01, also known as ^A, #\001:" represents a byte string of 1 byte holding the double quote character. A length #A#B: would start a literal byte string of length 16706. 4.2.1.6 concatenation of strings A byte string, in any of the forms above, can be continued by following it with the hyphen, "-", and then another byte string. The two byte strings do not need to be encoded in the same style. They are represented internally as a single string. 4.2.2 Display information A byte string may be prefixed with an optional piece of display information. This is in the form: :: "[" "]" The display information is assumed to give information about how to display the byte string. For example, we envision strings like: [utc-8], [unicode], [jpeg], [gif], [wav], etc. The content of the display info is allowed to be an S-expression, in case we encounter display commands which need parameters, but for now we expect it to be a simple name. Ellison, Frantz, Thomas [Page 30] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 4.2.3 List counts A list can be preceded by a count (of the form ## but with no ":"). This is for informational use -- primarily out of consideration for devices which want to allocate arrays to hold lists rather than store them as linked elements. 4.3 Binary (canonical) form Any of these S-expressions which is hashed is to be converted to binary form prior to the hash. This gives a canonical form and also reduces the size of the expression to save time in case the hash function is expensive. The binary form can also be used to transmit certificates whenever the communication rate into a device is limited or there is no reason to keep certificates human readable. 4.3.1 Byte strings All byte strings are expressed as binary strings (preceded by length byte(s) and ":") and therefore there is no need for blanks to terminate strings. Continuation of byte strings is never used in binary form. 4.3.2 List counts In packed binary form, for hash purposes, there are no list lengths. 4.3.3 blanks In binary form, there are no blanks. Ellison, Frantz, Thomas [Page 31] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 5. Field Examples The fields listed here are not meant to be an exhaustive list of all possible s. Such is not possible. The final arbiter of what needs to be an and what parameters a particular needs is the designer of the code which verifies a certificate, e.g., to grant access. Listed here are fields we know to be useful. For cases we have not anticipated, there is a field "Auth:" to handle arbitrary new fields, described above in section 4.1.7. 5.1 Member-of-issuer (Moi:) This grants the Subject all the authority of the Issuer. It is anticipated that this will be used to delegate permissions to a temporary signing key or to indicate members of a group (where the Issuer is the group). 5.2 Name (Name: fred) This defines a SDSI name in the Issuer's name-space, in this example "fred". The Subject of the certificate is assumed to reduce to the key for that name and most likely to be that key. 5.3 Member (Member: faculty) This declares that the Subject is a member of where is a name in the Issuer's name space. This is a SDSI group definition, since SDSI groups had only names in some name-space. Native SPKI uses a public key as a group name and the (Moi:) for delegating privileges to group members. Ellison, Frantz, Thomas [Page 32] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 5.4 FTP (FTP: cybercash.com cme ) This indicates that the Subject has permission to do FTP into host cybercash.com as user cme. 5.5 HTTP (HTTP: http://acme.com/company-private/personnel/ ) This gives the Subject permission to access web pages which start with the given URL. 5.6 TELNET (TELNET: erols.com spinne ) This gives the Subject permission to telnet into host erols.com as user spinne. 5.7 Public Key Protected File System (PKPFS: /// ) (PKPFS: //// ) refers to a hypothetical distributed file system whose access is controlled by public key challenge/response. If ends in "/" (as in the second example), access is to an entire subtree. Otherwise, it is to an indicated file (or set of files via "*"). is a set of letters: R: for read W: for (over-)write A: for add to directory (or append to file) D: for delete Ellison, Frantz, Thomas [Page 33] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 5.8 Dating Service Bindings There is some information which might be certified for a fee by a commercial on-line dating service: MARITAL-STATUS: BIRTH-YEAR: HEIGHT: WEIGHT: PICTURE: , This is specialized enough not to be pre-defined. E.g., one might use: (Auth: Dating ) 5.9 Authority to spend money (Auth: Spend ) indicates that the subject has authority to authorize spending up to per electronic check from at . For reduction of two certificates with this , if any field is present in one and not the other, that field is copied to the of the result. If present in both, and must be equal. The byte string is taken to be ASCII of a floating- point decimal number and if present in both s, the of the result is the minimum of the two input s. Ellison, Frantz, Thomas [Page 34] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 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.] 2) Can the Signature: object support blind signatures with algorithms other than RSA? 3) Should we keep 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. 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. 5) Should the delegation parameter be integer or boolean? 6) Are object names (e.g., "Issuer:") case sensitive? 7) Should we allow multiple s in one cert? It saves space and time, maybe, but could constitute a privacy threat and may complicate the cert reading code. 8) How much can we specify the ? Are there only a handful possible/desirable tests, that we can fully spell out, or do we need to leave that open for invention? 9) How many pre-defined s should we bother defining? 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? 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? 12) Do we want to include validity fields for private key dates, as was done with X.509v3? 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. Ellison, Frantz, Thomas [Page 35] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 14) Should we restore the explanation of [ECR] and define a field option for it? This was removed from this draft in the interest of simplification. 15) Should we allow Object as an optional element of the Signature expression, or force that block to give the Object's hash? 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)? 17) What is the difference between the Member: and Name: ? Can they be combined into one? Ellison, Frantz, Thomas [Page 36] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 References [BFL] Matt Blaze, Joan Feigenbaum and Jack Lacy, "Distributed Trust Management", Proceedings 1996 IEEE Symposium on Security and Privacy. [DNSSEC] Donald Eastlake and Charles Kaufman, "Domain Name System Security Extensions", (working draft of the DNSSEC Working Group). [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) [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 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. Ellison, Frantz, Thomas [Page 37] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 1997 [RFC1321] The MD5 Message-Digest Algorithm, R. Rivest, April 16 1992. [SDSI] Ron Rivest and Butler Lampson, "SDSI - A Simple Distributed Security Infrastructure [SDSI]", http://theory.lcs.mit.edu/~rivest/... [SRC-070] Abadi, Burrows, Lampson and Plotkin, "A Calculus for Access Control in Distributed Systems", DEC SRC-070, revised August 28, 1991. Ellison, Frantz, Thomas [Page 38] INTERNET-DRAFT Simple Public Key Certificate 25 Mar 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 Brian Thomas Southwestern Bell One Bell Center, Room 23Q1 St. Louis MO 63101 USA Telephone: +1 314-235-3141 +1 314-331-2755(fax) EMail: bt0008@entropy.sbc.com Bill Frantz Periwinkle 16345 Englewood Ave. Los Gatos, CA 95032 Telephone: +1 408-356-8506 Email: frantz@netcom.com Expiration and File Name This draft expires 30 September 1997. Its file name is draft-ietf-spki-cert-structure-01.txt Ellison, Frantz, Thomas [Page 39]