SPKI Certificate Theory Carl M. Ellison INTERNET-DRAFT CyberCash, Inc. Expires: 15 September 1998 Bill Frantz Electric Communities Butler Lampson Microsoft Ron Rivest MIT Laboratory for Computer Science Brian M. Thomas Southwestern Bell Tatu Ylonen SSH 10 March 1998 SPKI Certificate Theory ---- ----------- ------ Status of This Document This document is one of three, superseding the draft filed under the name draft-ietf-spki-cert-theory-00.txt. SPKI structure definitions are to be found in draft-ietf-spki-cert-structure-*.txt and examples of certificate uses are to be found in draft-ietf-spki-cert- examples-*.txt. Distribution of this document is unlimited. Comments should be sent to the SPKI (Simple Public Key Infrastructure) Working Group mailing list or to the authors. This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months. Internet-Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet- Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Ellison, et al. [Page 1] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 To learn the current status of any Internet-Draft, please check the 1id-abstracts.txt listing contained in the Internet-Drafts Shadow Directories on ds.internic.net (East USA), ftp.isi.edu (West USA), nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe), munnari.oz.au (Pacific Rim), or ftp.is.co.za (Africa). Ellison, et al. [Page 2] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 Abstract The SPKI Working Group has developed a standard form for digital certificates and access control lists. These structures bind either names or authorizations to keys. The binding can be directly to a key, or indirectly through the hash of the key or a name for it. The name and authorization structures can be used separately or together. We use S-expressions as the standard format for these certificates and define a canonical form for those S-expressions. This document gives the theory behind SPKI certificates and ACLs without going into technical detail about those structures or their uses. Ellison, et al. [Page 3] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 Table of Contents Status of This Document....................................1 Abstract...................................................3 Table of Contents..........................................4 1. Overview of Contents....................................6 1.1 Glossary...............................................6 2. History of Certification................................8 2.1 Definition of CERTIFICATE..............................8 2.2 The X.500 dream and its failure........................9 2.3 X.509, PEM and PGP.....................................9 3. The Three Flaws........................................10 3.1 Name -> Person -> Characteristics -> Identity.........10 3.1.1 Name -> Person......................................10 3.1.2 Person -> Characteristics...........................10 3.1.3 Characteristics -> Identity.........................11 3.1.4 Failure of Name -> Identity.........................11 3.2 Trust.................................................12 3.3 Non-repudiation.......................................12 4. Authorization..........................................14 4.1 Global Identifiers....................................14 4.1.1 Inescapable identifiers.............................15 4.1.2 SPKI global identifiers.............................16 4.2 Local Identifiers.....................................16 4.2.1 Local SDSI names....................................17 4.2.2 Global SDSI names...................................17 4.2.3 Linking SDSI names..................................17 4.3 Specific Authorizations...............................18 4.4 Groups................................................19 4.5 Tags..................................................19 5. 5-tuples...............................................20 5.1 5-tuple Reduction.....................................20 5.2 intersection...................................21 5.3 intersection...............................22 6. Authorization flow.....................................23 6.1 Certificate Result Certificates.......................23 7. Other considerations...................................25 7.1 Key and certificate storage...........................25 7.2 Protection of Private Keys............................26 7.3 Relation to PolicyMaker...............................27 References................................................28 Ellison, et al. [Page 4] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 Acknowledgments...........................................31 Authors' Addresses........................................31 Expiration and File Name..................................32 Ellison, et al. [Page 5] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 1. Overview of Contents This document contains the following sections: Section 2: history of digital certification over the past 20+ years. Section 3: discussion of mistakes that have crept into certificate thinking in the areas of identity, trust and non-repudiation. Section 4: authorization as the desired purpose of a certificate. Section 5: definition of 5-tuples and the operations performed on them. Section 6: the flow of authorization, through 5-tuples. Section 7: some other considerations that have come up during working group discussions. The References section lists all documents referred to in the text as well as readings which might be of interest to anyone reading on this topic. The Acknowledgements section, listing contributors primarily at the start of the working group. This section has not been augmented in many months. The archive of working group mail is a more accurate source of such information. The Authors' Addresses section gives the addresses, telephone numbers and e-mail addresses of the authors. 1.1 Glossary We use some terms in the body of this document in ways specific to SPKI: KEYHOLDER: the person or other entity that owns and controls a given private key is said to be the keyholder of the corresponding public key. PRINCIPAL: a signature key, capable of generating a digital signature. SPEAKING: a Principal is said to "speak" by means of a digital signature. The statement made is the signed object (typically a certificate, for SPKI purposes). S-EXPRESSION: the data format chosen for SPKI/SDSI. This is a LISP- Ellison, et al. [Page 6] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 like parenthesized expression with the limitations that empty lists are not allowed and the first element in any S-expression must be a string, called the "type" of the expression. Ellison, et al. [Page 7] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 2. History of Certification It has entered the non-technical consciousness that digital certificates bind people to keys and that they have to be issued by trusted certification authorities. For example: "Without a KMI of trusted certificate authorities, users cannot know with whom they are dealing on the network...." [IWG] This is an old idea. It is also wrong. That is, it is based on characteristics of the world which were true at some time but are no longer true. Diffie and Hellman introduced public key cryptography in their seminal 1976 paper. Prior to this, key management was risky, involved and costly, usually employing special couriers with briefcases handcuffed to their wrists. Diffie and Hellman thought they had radically solved this problem. "Given a system of this kind, the problem of key distribution is vastly simplified. Each user generates a pair of inverse transformations, E and D, at his terminal. The deciphering transformation, D, must be kept secret but need never be communicated on any channel. The enciphering key, E, can be made public by placing it in a public directory along with the user's name and address. Anyone can then encrypt messages and send them to the user, but no one else can decipher messages intended for him." [DH] This modified telephone book, fully public, took the place of the trusted courier. This directory could be put on-line and therefore be available on demand, worldwide. In considering that prospect, Loren Kohnfelder, in his 1978 bachelor's thesis in electrical engineering from MIT [KOHNFELDER], noted: "Public-key communication works best when the encryption functions can reliably be shared among the communicants (by direct contact if possible). Yet when such a reliable exchange of functions is impossible the next best thing is to trust a third party. Diffie and Hellman introduce a central authority known as the Public File." 2.1 Definition of CERTIFICATE Kohnfelder then noted, "Each individual has a name in the system by which he is referenced in the Public File. Once two communicants have gotten each other's keys from the Public File then can securely communicate. The Public File digitally signs all of its transmission so that enemy impersonation of the Public File is precluded." In an effort to prevent performance problems, Kohnfelder invented a new construct: a digitally signed data record containing a name and a public key. He called this new construct a CERTIFICATE. Because it Ellison, et al. [Page 8] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 was digitally signed, such a certificate could be held by non-trusted parties and passed around from person to person, resolving the performance problem involved in a central directory. 2.2 The X.500 dream and its failure It was approximately ten years after Kohnfelder that the X.500 proposal took form in the ISO. X.500 was to be a global, distributed database of named entities: people, computers, printers, etc. In other words, it was to be a global, on-line telephone book. The organizations owning some portion of the name space would maintain that portion and possibly even provide the computers on which it was stored. To record the permission to modify nodes in this global name space X.509 certificates were defined. An X.509 certificate bound a so-called distinguished name to a public key. The distinguished name was a path in the X.500 database, identifying a node in that database. It is now obvious that the X.500 dream can not succeed. The designers had overlooked the fact that organizations consider their name spaces (e.g., their employee lists) to be confidential. For example, does anyone really believe that the CIA will put its employee list up on the web, in the form of a globally accessible X.500 database? Will IBM? 2.3 X.509, PEM and PGP Although the X.500 dream was doomed, X.509 lived on. It was adopted by the Privacy Enhanced Mail [PEM] effort of the Internet Engineering Task Force [RFC1114]. X.509 was also to be the death of PEM. There was no certificate infrastructure at that time and PEM would not function at all without one. Furthermore, the CA structure specified in RFC1114 and its successor RFC1422 was suitable for a hierarchy like the military but did not reflect the nature of commercial interactions. When it became obvious that PEM was not going to succeed, Mark Riordan of MSU introduced RIPEM, an implementation of PEM without certificates. RIPEM saw some deployment, but Phil Zimmerman's PGP soon won out over both RIPEM and PEM since PGP had certificates but did not require any infrastructure. Instead, it used the "web of trust" -- multiple, independent people voting on the validity of a binding between a global name and a public key. The global name was not an X.500/X.400 name, but rather a DNS name. This had the advantage of being globally deployed and useful. Ellison, et al. [Page 9] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 3. The Three Flaws In the discussion of digital certification, three concepts have been heavily but mistakenly used: identity, trust, and non-repudiation. The mistake in use of "identity" can be traced back to our history as individuals and as a culture. Our use of "trust" has suffered from imprecise language. Talk about "non-repudiation" is a sample of wishful thinking or, more precisely, an improper carry-over from technical papers to the popular mind. The subsections below describe those three flaws. 3.1 Name -> Person -> Characteristics -> Identity People speak of an X.509 (name,key) certificate as an "identity certificate". It is not. It can not bind an identity to a key. It binds a name to a key. This mistake lies in assuming that name implies identity. 3.1.1 Name -> Person The purpose of a common name is to identify someone. When there is name confusion, we take the liberty of adjusting the name so that it continues to function as an identifier: Little Joe, Tricky Dick, The Pink Lady, William G. Smith IV... We are limited in the number of names we can remember, but for most of our lives and most of human history, we have had a relatively small community around us. There is some evidence that names evolved to be just large enough to avoid collisions in communities the size of those normally around us. As a result, we were not normally troubled by name collisions. This reinforced our belief that name->person. 3.1.2 Person -> Characteristics One characteristic of a small community is that it is hard to keep secrets. A T-shirt for sale in one small US town has a caption that reads: "Small Town (def) a place where you don't have to use your turn signals because everyone knows where you are going." From these small town experiences, we tend to assume that if we know a person, we know their characteristics (marital status, credit history, general trustworthiness...). This leads us to extend the definition to name->person->characteristics. Ellison, et al. [Page 10] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 3.1.3 Characteristics -> Identity This is a matter of definition. "identity [...] (2a): the distinguishing character or personality of an individual; [...] (3): the condition of being the same with something described or asserted." [WEBSTER] Since distinguishing character or personality is one of those characteristics expected to be known about a person, definition (2a) gives us the final link, so that now we have name -> person -> characteristics -> identity. If names were globally unique and unchanging, then we might be able to establish that if name[1]==name[2] then person[1]==person[2] and therefore go directly from name -> identity by definition (3). However, for our purposes, definition (2a) is more interesting since what we really care about is characteristics of the individual: security clearance, ownership of a given bank account or credit card, military rank, citizenship, age, group membership, .... 3.1.4 Failure of Name -> Identity The name->identity chain of logic depends in two places on characteristics of small communities: the small name space in 3.1.1 and the small town of 3.1.2. University research groups, families, classes in school, etc., are small communities. The Internet is not. [Neither is New York City and signs of security flaws in the name->identity assumption in the 3D world can be found under the heading of "true name fraud".] The failure of the name->identity assumption might show up, for example, if the US Social Security Administration were to allow an outside CA to issue (name,key) certificates and then use those certificates for granting access to SSA records. One could go to such a CA, get a certificate announcing that he is "Carl Ellison" and then to go the SSA's server and request all records for persons named Carl Ellison. That would be a clear security policy violation. However, the legitimate request for "my records" would almost certainly involve a guess of which Carl Ellison the requester might be. If there is a guess involved in the secure process, then tamper- proof RSA signature engines, 2048 bit key lengths, etc. become a bank vault door in a cardboard wall. Ellison, et al. [Page 11] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 3.2 Trust The literature around certificates frequently uses the word "trust". "Certificates must be issued by trusted certificate authorities." "Internet commerce requires that trust be established between the parties." US currency carries the statement: IN GOD WE TRUST. One can assume unconditional trust in God but in real life we do not grant unconditional trust to fellow human beings. We might say, "I trust her", but that is shorthand for "I trust her to _________" or "I trust her to be _________". In the cryptographic literature, we find the word "trust" used without qualifier. In these cases, "trust" is used the way a mathematician would use the symbol X. Trust is the thing a certificate chain communicates, but what it is really is beyond the scope of a cryptographic research paper. It is assumed that the reader will fill in the blank appropriately. When this use of the naked word "trust" moves from research papers into the community of CA sales representatives, policy makers and lawyers, there opens up multiple opportunities for misinterpretation. When that is accidental, it is an unfortunate mistake. When it is intentional, it could be a form of deceit. Caveat lector. The first purpose of SPKI certificates is to address the issue of "trust" by avoiding the term and instead concentrating on asking what a given keyholder is permitted or authorized to do. 3.3 Non-repudiation If it were possible to achieve non-repudiation, that would be a desirable feature of public key cryptography. Several cryptographic research papers addressed this issue. One of their conclusions was that we need to secure the protocols, algorithms, keys and facilities of the issuers of certificates because if there are flaws in that process, non-repudiation is threatened. In the popular literature, this conclusion is sometimes inappropriately reversed to read that if a certificate comes from a properly secured issuer, then non-repudiation is achieved. That concept has even entered into some proposed and actual laws on digital signatures. Digital signatures differ from handwritten signatures. As Matt Blaze Ellison, et al. [Page 12] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 of AT&T Research has pointed out, a digital signature is tightly bound to the document it signs but not to the person signing while a handwritten signature is tightly bound to the person signing but not to the document. Non-repudiation is achieved by protecting the keyholder's private key from theft and protecting the computer that uses that private key from infiltration or subversion. Unfortunately, the hardware, virus- proof operating systems and locked, guarded rooms required to keep everyone but the keyholder from using that private key are beyond the resources of normal users. That situation may make it impossible to prosecute any keyholder on the basis of a digital signature, except to the extent that ordinary unsigned e-mail has been used in court as evidence of a commitment. On the positive side, however, there is a source of practical security for all users of signature keys, even when those keys are kept on normal disks and used in software. If there are millions of signing keys, each with a small value, then the value of one key may not exceed the cost of attacking that individual key -- and the key would remain safe. Therefore, even certificates from software-only issuers are likely to be usable for small-population, low-value access control while higher value keys would require higher levels of protection. Non-repudiation may be impossible, with current hardware and environments and is likely to remain so into the future. The loss of non-repudiation may rob certificates of their value as evidence against a keyholder but not of their value in granting access. That is, a private key and the certificate that empowers it may be viewed as a brass house key. That brass key might allow Joe Smith to enter a building, but knowing that the key was given to Joe Smith does not mean that only Joe Smith could have used it. That brass key has value to Joe but not to someone accusing Joe. Ellison, et al. [Page 13] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 4. Authorization Imagine that Joe's Garage has invested in the equipment, policies, procedures and personnel security necessary to make it a trusted issuer of certificates, under someone's criteria for "trust". Does this mean that Joe is trusted to grant access to your bank account, to your medical records, to the launch button for nuclear missiles, to your private confidentiality key, ...? In the physical world we might prize official-looking parchment certificates. The fancier the calligraphy the better. Such a certificate might be mounted in a frame and displayed. However, its beauty does not enhance its validity. Its validity comes from the authority of the issuer of the certificate to make such statements. Joe's Garage can not issue me a diploma from Harvard, no matter how much money Joe spends making it pretty. Similarly, a digital certificate becomes valid because of the authority of its issuer. The format of the certificate doesn't make it more valid. The cryptographic hardware used by the issuer might make the issuer's signature more trustworthy, but if the issuer has no authority to make the statement contained in the certificate, no amount of expensive cryptographic hardware makes up for that lack of authority. When we start listing kinds of authorization and their corresponding authorized issuers, we see that only very rarely would one issuer grant multiple kinds of authorization. Furthermore, when we envision a future with all personal computers on the network at all times and each one granting FTP and HTTP access via public key authorization, every computer owner in the world could become a certificate issuer. No one entity will be an authority on everything while every entity will be an authority on something. 4.1 Global Identifiers In order to grant access or authorization, we must be able to identify the recipient of that authorization. X9.57 describes an Attribute Certificate that binds an authorization to an X.509 Distinguished Name. This usage suffers from the same potential security flaw described in section 3.1.4. Imagine a bank, granting electronic access to your checking account. You go into the bank, establish your ownership of that account (e.g., by signing a piece of paper, swiping your ATM card, or whatever), and request the issuance of an attribute certificate to give you on-line checking account access. The request is sent to the back room where Ellison, et al. [Page 14] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 your account information (name, address, ...) is used to look up your distinguished name in some global directory of certificates. At that point, the information on file exceeds the account holder's common name and so does the distinguished name. However, the two bodies of information are not the same. Their intersection will be the common name and maybe one or two other pieces of information. From a scan of available X.509 certificates, the bank back office will come up with a set of possible matches to the account owner. If there are none, there is no security problem because no attribute certificate is issued. If there are multiple matches, bank policy dictates what happens next. If no certificate is issued, then there is no security flaw. If "the most likely" match is chosen and a certificate is issued to that match, then this involves a human guess and there is a security problem. If there is only one match, then presumably the (name,key) certificate is correct and the attribute certificate is issued. However, the bank does not know that the match is correct. This is an assumption and therefore also a violation of security in the sense of section 3.1.4. 4.1.1 Inescapable identifiers What is missing in the scenario above is a globally unique, universally used identifier of persons. There are some who speak of Distinguished Names as if they were such identifiers. That is, they speak of "inescapable identifiers" -- so that some evil-doer is not capable of doing evil under one name, changing his name and starting over again. It is unlikely that we will ever see such a global identifier. In the US, this falls under the category of a national ID card or national ID number and is resisted politically. The opposition is not above citing numbers tattooed on forearms to impart distaste. In some countries that do have national ID numbers, there are laws against being required to disclose those numbers except for official government purposes. In those countries, such a number would uniquely identify a person but not become universally used. As the (name,key) certificate business is evolving today, there are multiple competing CAs each creating disjoint Distinguished Name spaces and therefore a person is able to drop one Distinguished Name and get another, by changing CA. The notion of an inescapable identifier is therefore no closer to realization and, viewing the political opposition to it, not likely ever to be. Ellison, et al. [Page 15] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 4.1.2 SPKI global identifiers One of the fundamental realizations behind SPKI is that every user of a public key has a global name: the public key itself. The name may not be pronounceable and certainly not easily typed, but it is globally unique. It also has the advantage of not needing a certificate to tie it to the user's public key. If a given cryptographic hash function is collision-free, then the hash of the public key is also a globally unique identifier for the keyholder. The base64 representation of that hash is a text string that is a globally unique identifier for the keyholder. Neither of these needs a certificate to tie it to the corresponding public key. It is an often cited complaint that these identifiers derived from a public key can change and are not the name forms in common use. As we showed above, inescapable identifiers are unlikely ever to be accepted and used while common names fail to work as global names and common names extended to become unique lead to security flaws. Therefore, we embrace these key-centric global names as superior to the extended common names of X.400/X.500 thinking. 4.2 Local Identifiers No matter what we use as a global identifier, it is unlikely to be pleasant for a person to use. This is to be expected, since people have a limited capacity for remembering names and the capacity of even the most talented politician or memory expert would be taxed by a community that includes the entire world population. Two of us (Rivest and Lampson) proposed the solution to this problem, in the original SDSI 1.0 work. That work drops the fiction of a global name space and instead declares a local name space for every PRINCIPAL (every entity capable of digitally signing). It also defines a way to link local name spaces. Just as Einstein showed that one can do better physics by dropping the fiction of a global space-time and instead dealing with local space-times and the rules for linking them, SDSI dropped the fiction of a global name space and instead dealt with local name spaces while providing rules for linking them. This produces superior security in naming and as a result SPKI adopted SDSI naming from the start and eventually merged with SDSI. Ellison, et al. [Page 16] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 4.2.1 Local SDSI names A local SDSI name is of the form (name ), where is some name meaningful to the owner of the name space. These name strings are meant to identify the named entity for the name space owner, but are not intended to serve that purpose for anyone else in the world. They are most likely short and simple, like the nicknames or aliases most e-mail agents support. 4.2.2 Global SDSI names Any local SDSI name becomes a global identifier by becoming a "fully qualified SDSI name": (name ), where the is the global name of the owner of the name space. So, for example, the local name: (name jim) could become a global identifier in the form: (name (hash md5 |+gbUgUltGysNgewRwu/3hQ==|) jim) 4.2.3 Linking SDSI names The rule for linking SDSI names is perhaps best shown by example. (name (hash md5 |+gbUgUltGysNgewRwu/3hQ==|) jim marty) needs to reduce to a global identifier (ie., a public key or the hash of a key). SDSI defines a (name,key) certificate. Imagine a SDSI (name,key) certificate signed by (hash md5 |+gbUgUltGysNgewRwu/3hQ==|) declaring that (name (hash md5 |+gbUgUltGysNgewRwu/3hQ==|) jim) is (hash md5 |L5srYRkDOwenViTApnldHA==|) therefore Ellison, et al. [Page 17] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 (name (hash md5 |+gbUgUltGysNgewRwu/3hQ==|) jim marty) equals (name (hash md5 |L5srYRkDOwenViTApnldHA==|) marty). If one then has a certificate signed by (hash md5 |L5srYRkDOwenViTApnldHA==|) defining (name marty), one can finish resolving that linked SDSI name to a PRINCIPAL: a key or the hash of a key. 4.3 Specific Authorizations When we make security decisions, it is a person's characteristics we need to know. The definitions of global and local identifiers above allow one to identify a given keyholder. However, as noted in section 3.1.2, identification of a person leads to that person's characteristics only in a small community. If one has a small community of interest, then it is possible to grant authorizations via an access control list (ACL) referring to people by name. SPKI (inspired by the original SDSI) defines an ACL for this purpose. However, once that community grows (as discovered by another of us, Brian Thomas), the job of maintaining that ACL becomes extremely complex. For example, there was once a project to implement a firewall proxy allowing holders of Fortezza cards to access MILNET from the Internet. If Fortezza had taken off as was hoped at the time, then every member of the US armed forces would have had a card. This firewall proxy would then have to have had an ACL listing those who had this permission. No one branch of the service would have had the right to maintain that ACL. Therefore, the ACL would have to have been structured with different services (if not different organizations within each military service) having change control over its own portion of the ACL. The machinery to implement such change control would exceed the complexity of the original task. As an alternative to ACLs, the original SPKI certificate was designed to propagate a specific authorization from one keyholder to another or to a group. The issuing keyholder is identified globally (as a key or hash of key). The receiving keyholder (the Subject) is identified either globally (key, key hash, global SDSI name) or locally (as a SDSI name local to the issuer). The meat of this certificate is its authorization field, called its . Ellison, et al. [Page 18] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 4.4 Groups One is (tag (*)), meaning "all authorizations". A certificate that uses (tag (*)) propagates all the authorizations the Issuer possesses over to the Subject. Such a certificate is used to define a group. That is, one can define a group as a PRINCIPAL (a public key) and have it issue certificates granting all of its authorizations (except maybe the right to delegate) on to one or more other PRINCIPALs -- that is, on to the group members. A SDSI (name,key) certificate is implicitly (tag (*)), even though it does not carry an explicit field. One can define a group with SDSI (name,key) certificates also, by issuing multiple certificates with the same name but different keys. This can be true for individual names like (name jim) in case an individual has multiple, equivalent public keys, as well as for names of groups like (name faculty) 4.5 Tags The , described above as the meat of an SPKI certificate or ACL entry, is not explicitly defined in SPKI. Rather, we define rules for intersection of fields and allow individual developers to define the s of their choice. Each of these is assumed to be application-specific. However, to give guidance to such developers, we have produced a separate document listing examples of fields, for the basic applications. Some of these might find actual usage in applications, but that is not our intention for listing them. We expect individual application developers to invent or refine definitions and, after experience with them in real applications, consider standardizing them. See draft-ietf-spki-cert-examples-*.txt for those examples. Ellison, et al. [Page 19] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 5. 5-tuples We consider certificates as having the following five fields of interest during authorization computations: ISSUER: a principal making the certificate's statement. SUBJECT: the thing about which the statement is being made. In SPKI, this is usually a principal or a SDSI name reducible to a principal. However, it might also be some object (e.g., executable code or a web page). The subject is that which receives authority from the issuer by way of the certificate. DELEGATION: permission to delegate some authorization. This exists in some X.509v3 extensions as an integer. In SPKI, it is a boolean, represented by the optional modifier, "(propagate)". AUTHORIZATION: the specific authorization(s) being delegated in this certificate. SPKI defines these explicitly, but authorization fields can sometimes be deduced from other certificate forms, such as X.509v3's extensions. In many older certificates, the authorization field was effectively (tag(*)), and different authorizations were achieved by use of different issuing keys. VALIDITY: date ranges and/or online validity tests for determining certificate validity. A certificate is signed by its issuer. An ACL entry can also produce a 5-tuple, but has "self" as issuer and is not signed. The tamper- resistance of an ACL is to be achieved somehow by the computer where it is stored. These 5 fields can be expressed as the 5-tuple (,,,,) A basic SPKI certificate is such a 5-tuple, signed by its issuer. 5.1 5-tuple Reduction The process of "validating a certificate chain", often referred to in the literature, is called "5-tuple reduction" in SPKI. The rules for reduction are simple, when issuers and subjects are principals: Given (I1,S1,D1,A1,V1) Ellison, et al. [Page 20] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 and (I2,S2,D2,A2,V2) reduction is possible if S1==I2 and D1==true The reduced 5-tuple is then (I1,S2,D2,A,V) where A = intersection(A1,A2) and V = intersection(V1,V2) If one encounters a 5-tuple with a SDSI name as subject, then one can reduce the subject via (name,key) certificates to a principal, as shown in section 4.2, and the result is a 5-tuple with a principal as a subject, ready for the reduction process above. Both intersection() operators above are commutative. 5.2 intersection After much discussion about the definition and use of an algebra of sets, SPKI defines simple rules for intersections using a subset of the full algebra introduced in earlier drafts. An or is an S-expression. An S-expression is a list of strings or S-expressions, starting with a string that is taken to be the expression "type". The expression type of an or S- expression is "tag". If two s are equal, then the intersection is equal to them. s are required not to gain any authorization by appending new information. As a result, if Ai and Aj are s and Ai is a prefix of Aj, then the intersection of Ai and Aj is Aj. There are four special S-expression forms that stand for sets of S- expressions in s. These are called *-forms. (*) represents the set of every possible S-expression. That is, it is an identity operation for intersection. (* set * ) Ellison, et al. [Page 21] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 represents a set of simpler S-expressions. The intersection of a *-set with a simple S-expression is the set of intersections of each element of the set with that S-expression. If an intersection fails, it doesn't enter the result set. If the result set is empty, the intersection failed for the whole *-set. If one is intersecting two *-sets, the intersection is performed on each possible pair, one from each set. (* prefix ) stands for the set of all byte strings starting with the given string. (* range ? ?) stands for the set of all byte strings of the given ordering type (numeric, alphabetic, ...) subject to the given high and low limits. Low or high limits can be omitted, if one wants to specify a semi- infinite set. If two s have elements in the same position that are not *-forms and differ in value, then the intersection of the two s is NULL. 5.3 intersection A validity field might consist of dates (not-before and/or not-after) and of on-line tests. An on-line validity test queries some external database or service to determine whether a given 5-tuple is still valid. The result of an on-line test could be a failure -- in which case the 5-tuple is not valid and intersection is not possible -- or a success, in which case the on-line test result carries with it a date range for the validity of its own result. Therefore, all on-line tests can be applied to a 5-tuple to yield a date range during which it is valid. Two date ranges intersect in the natural way, to yield V. However, if one wants to have longer-lived reduced 5-tuples, one might choose to perform the intersection literally for literally provided date ranges, but to accumulate the union of on-line tests, to be applied at a later time to the reduced 5-tuple. This is under the assumption that the date range for an on-line test is a function of the time at which the test is made. Ellison, et al. [Page 22] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 6. Authorization flow There is no such thing as a "root key" -- some key, handed down from God to be trusted for all purposes and carry all authorizations. In the final analysis, there is an algorithm running on some computer with some private data storage and that algorithm makes a decision of whether to permit some access or perform some action. That algorithm makes authorization decisions. It might use certificates as the basis for those decisions, but the certificate merely passes authorization from the Issuer to the Subject. If one thinks of these certificates as being laid out left to right, there needs to be a left-most certificate -- and that certificate's Issuer needs to be granted its authorization from some source. The only structure capable of performing that function is an ACL entry. An ACL entry has no issuer and is therefore required to be left-most in such a structure. Its assumed Issuer is "self" -- namely the program doing the authorization computation (presumably acting for its owner). We therefore see that all authorizations useful for decision making flow from an ACL entry through 0 or more certificates until they arrive at the right end of this list of structures with a 5-tuple reduction of the form: (self, , , , ) The authorization program -- the Verifier -- then receives this result and acts on it. The authorization has then flowed from the Verifier, through the ACL, possibly through certificates back to the Verifier. In one sense, then, it has flowed in a loop -- like an electrical current. If one accepts this as a loop or circuit, then it is clear that all authorizations must exist in closed loops or circuits in order to be useful. Sticking with the electrical analogy, the Verifier is the battery in the circuit. 6.1 Certificate Result Certificates When a Verifier reduces a list of certificates to the final form: (self, , , , ) it has another choice. If that Verifier also has a private key, KV, then it can form the certificate body: (KV, , , , ) Ellison, et al. [Page 23] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 and sign it. If some other Verifier gives KV authority to make statements of the form , then that other Verifier can use this Certificate Result Certificate instead of having to go through the full verification process KV did. This process can be used to save time and possibly code space (especially if some verification process involves 5-tuples coming from different certificate formats (e.g., SPKI mixed with X.509)). It can also be used for protecting sensitive information. For example, a company might run such a Verifier in order to bind permissions to temporary keys, for generating temporary certificates to be released into the outside world, while protecting the internal certificate structure from disclosure. This need might arise because a certificate or a collection of them might contain data that is sensitive individually or by aggregation. Ellison, et al. [Page 24] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 7. Other considerations A number of considerations came up during the discussion in the SPKI WG. These included the following. 7.1 Key and certificate storage The term PKI is generally assumed to refer to an X.500 style global directory of certificates. We have rejected global directories of extended common names on security grounds, even though SPKI includes the substring PKI. Instead, we take the term PKI to refer to a general, distributed use of public keys empowered by certificates rather than assume some structure for certificate storage or official Certificate Authorities. It may still be necessary to have repositories of certificates. Some of these might even be intelligent. For example, they might perform the service of discovering a certificate path from a given issuer to a given subject, communicating a given permission, and return all the certificates in that path. However, we take such efforts to be future work and outside the immediate scope of the SPKI WG. There are several independent efforts at this time to provide a database of keys or certificates for the Internet. The DNS Security Working Group draft [RFC2065], specifies an efficient key storage and distribution mechanism. It may be possible to store an SPKI certificate in a KEY Resource Record (RR) or to create a new RR type for SPKI certificates, under the DNSSEC design. 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 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 Ellison, et al. [Page 25] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 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. 7.2 Protection of Private Keys For any public key cryptosystem to work, it is essential that a keyholder keep its private key to itself. In the case of a human being, this might involve keeping the private key encrypted under a high-entropy passphrase and storing it only on the person's own personal computer or floppy disks. Some humans might even keep the private key in a tamper-resistant PCMCIA card or Smart-Card which will never release it and will in fact destroy it after too many failed attempts to gain access. In the case of a network node, this might involve keeping the private key in a tamper-resistant cryptographic processor which generated it and which will destroy it if tampering is attempted. If the keyholder does not keep the private key protected (that is, if the private key gets out to others to use) then one can not know what entity is using that key and no certificate will be able to restore the resulting broken security. Therefore, we are forced to assume that all private keys are kept private and bound tightly to the one keyholder to which they belong. We will have to provide for methods of announcing the compromise of such private keys whenever this assumption proves false, but we must assume that unless such notification is delivered, each private key is secure and attached to its owner. Note: We have specifically included a process for one keyholder who has been granted some authority to delegate that authority to another, in order to reduce if not eliminate the motivation for one keyholder to loan a private key to another. So to reiterate, we do not expect every person, process and device in the Internet to employ true tamper resistance. Many people will keep and use private keys on an insecure personal computer or workstation. However, we are forced to assume protection of the private key or give up any notion of cryptographically strong authentication and Ellison, et al. [Page 26] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 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. 7.3 Relation to PolicyMaker Section 6.1 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. For example, it might yield fields that are not related to the input fields in any simple way. The policy machine would still have to have its own ACL entries to empower the keys it uses 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. [BFL] noted 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 empowered keys (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 to turn 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 5-tuple reduction. Ellison, et al. [Page 27] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 References [Ab97] Abadi, Martin, "On SDSI's Linked Local Name Spaces", 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. [DH] Whitfield Diffie and Martin Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, November 1976, pp. 644-654 [DvH] J. B. Dennis and E. C. Van Horn, "Programming Semantics for Multiprogrammed Computations", Communications of the ACM 9(3), March 1966 [ECR] Silvio Micali, "Efficient Certificate Revocation", manuscript, MIT LCS. [HARDY] Hardy, Norman, "THE KeyKOS Architecture", Operating Systems Review, v.19 n.4, October 1985. pp 8-25. [IDENT] Carl Ellison, "Establishing Identity Without Certification Authorities", USENIX Security Symposium, July 1996. [IWG] McConnell and Appel, ``Enabling Privacy, Commerce, Security and Public Safety in the Global Information Infrastructure'', report of the Interagency Working Group on Cryptography Policy, May 12, 1996; (quote from paragraph 5 of the Introduction) [KEYKOS] Bomberger, Alan, et al., "The KeyKOS(r) Nanokernel Architecture", Proceedings of the USENIX Workshop on Micro-Kernels and Other Kernel Architectures, USENIX Association, April 1992. pp 95-112 (In addition, there are KeyKOS papers on the net available through http://www.cis.upenn.edu/~KeyKOS/#bibliography) [KOHNFELDER] Kohnfelder, Loren M., "Towards a Practical Public-key Cryptosystem", MIT S.B. Thesis, May. 1978. [LAMPSON] B. Lampson, M. Abadi, M. Burrows, and E. Wobber, "Authentication in distributed systems: Theory and practice", ACM Trans. Computer Systems 10, 4 (Nov. 1992), pp 265-310. [LANDAU] Landau, Charles, "Security in a Secure Capability-Based System", Operating Systems Review, Oct 1989 pp 2-4 Ellison, et al. [Page 28] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 [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. [RFC1114] S. Kent, J. Linn, "Privacy Enhancement for Internet Electronic Mail: Part II -- Certificate-Based Key Management", August 1989. [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 [SET] Secure Electronic Transactions -- a protocol designed by VISA, MasterCard and others, including a certificate structure covering all participants. See http://www.visa.com/ [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, Ellison, et al. [Page 29] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 1991. [WEBSTER] "Webster's Ninth New Collegiate Dictionary", Merriam- Webster, Inc., 1991. Ellison, et al. [Page 30] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 Acknowledgments Several independent contributions, published elsewhere on the net or in print, worked in synergy with our effort. Especially important to our work were: [SDSI], [BFL] and [RFC2065]. The inspiration we received from the notion of CAPABILITY in its various forms (SDS-940, Kerberos, DEC DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated. Significant contributions to this effort by the members of the SPKI mailing list and especially the following persons (listed in alphabetic order) are gratefully acknowledged: Steve Bellovin, Mark Feldman, John Gilmore, Phill Hallam-Baker, Bob Jueneman, David Kemp, Angelos D. Keromytis, Paul Lambert, Jon Lasser, Jeff Parrett, Bill Sommerfeld, Simon Spero. 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 Ellison, et al. [Page 31] INTERNET-DRAFT SPKI Certificate Theory 10 March 1998 Ron Rivest Room 324, MIT Laboratory for Computer Science 545 Technology Square Cambridge MA 02139 Telephone: +1-617-253-5880 +1-617-258-9738(FAX) Email: rivest@theory.lcs.mit.edu Web: http://theory.lcs.mit.edu/~rivest Brian Thomas Southwestern Bell One Bell Center, Room 23Q1 St. Louis MO 63101 USA Telephone: +1 314-235-3141 +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 15 September 1998. Its file name is draft-ietf-spki-cert-theory-01.txt Ellison, et al. [Page 32]