RFC 2693
SPKI Certificate Theory
RFC 2693: SPKI Certificate Theory 🎀
bestie, this one is a September 1999 doc from the Experimental category 🧪 It was written by C. Ellison (Intel), B. Frantz (Electric Communities), B. Lampson (Microsoft), R. Rivest (MIT Laboratory for Computer Science), B. Thomas (Southwestern Bell), and T. Ylonen (SSH) 👑 Their header has no Obsoletes or Updates line, so it doesn't list anything it replaces or changes 💅
Status of this Memo ✨
okay so this memo defines an Experimental Protocol for the Internet community 🧪 It is not an Internet standard of any kind, so don't go treating it like one 🙈 The authors are literally asking for discussion and suggestions for improvement, and the memo can be distributed with no limits 🦋
Copyright Notice 🌸
Copyright (C) The Internet Society (1999). All Rights Reserved. 💜
Abstract 🔮
the SPKI Working Group cooked up a standard form for digital certificates whose main job is authorization (what you're allowed to do) rather than authentication (proving who you are) 💖 These structures bind either names or explicit authorizations to keys or other objects 🗝️ The binding to a key can go straight to an explicit key, or indirectly through the hash of the key or a name for it 🧩 The name and authorization structures can be used separately or together, your call 🫶
They use S-expressions as the standard format for these certificates and define a canonical form for those S-expressions 📜 As part of all this, the team came up with a mechanism for deriving authorization decisions from a mixture of certificate types, and it's presented in this document 🔥
This document gives the theory behind SPKI certificates and ACLs without going into the technical details of those structures or their uses. It's the vibes-and-reasoning version, bestie ✨
Table of Contents 📚
1. Overview of Contents.......................................3
1.1 Glossary..................................................4
2. Name Certification.........................................5
2.1 First Definition of CERTIFICATE...........................6
2.2 The X.500 Plan and X.509..................................6
2.3 X.509, PEM and PGP........................................7
2.4 Rethinking Global Names...................................7
2.5 Inescapable Identifiers...................................9
2.6 Local Names..............................................10
2.6.1 Basic SDSI Names.......................................10
2.6.2 Compound SDSI Names....................................10
2.7 Sources of Global Identifiers............................11
2.8 Fully Qualified SDSI Names...............................11
2.9 Fully Qualified X.509 Names..............................12
2.10 Group Names.............................................12
3. Authorization.............................................12
3.1 Attribute Certificates...................................13
3.2 X.509v3 Extensions.......................................13
3.3 SPKI Certificates........................................14
3.4 ACL Entries..............................................15
4. Delegation................................................15
4.1 Depth of Delegation......................................15
4.1.1 No control.............................................15
4.1.2 Boolean control........................................16
4.1.3 Integer control........................................16
4.1.4 The choice: boolean....................................16
4.2 May a Delegator Also Exercise the Permission?............17
4.3 Delegation of Authorization vs. ACLs.....................17
5. Validity Conditions.......................................18
5.1 Anti-matter CRLs.........................................18
5.2 Timed CRLs...............................................19
5.3 Timed Revalidations......................................20
5.4 Setting the Validity Interval............................20
5.5 One-time Revalidations...................................20
5.6 Short-lived Certificates.................................21
5.7 Other possibilities......................................21
5.7.1 Micali's Inexpensive On-line Results...................21
5.7.2 Rivest's Reversal of the CRL Logic.....................21
6. Tuple Reduction...........................................22
6.1 5-tuple Defined..........................................23
6.2 4-tuple Defined..........................................24
6.3 5-tuple Reduction Rules..................................24
6.3.1 AIntersect.............................................25
6.3.2 VIntersect.............................................27
6.3.3 Threshold Subjects.....................................27
6.3.4 Certificate Path Discovery.............................28
6.4 4-tuple Reduction........................................28
6.4.1 4-tuple Threshold Subject Reduction....................29
6.4.2 4-tuple Validity Intersection..........................29
6.5 Certificate Translation..................................29
6.5.1 X.509v1................................................29
6.5.2 PGP....................................................30
6.5.3 X.509v3................................................30
6.5.4 X9.57..................................................30
6.5.5 SDSI 1.0...............................................30
6.5.6 SPKI...................................................31
6.5.7 SSL....................................................31
6.6 Certificate Result Certificates..........................32
7. Key Management............................................33
7.1 Through Inescapable Names................................33
7.2 Through a Naming Authority...............................33
7.3 Through <name,key> Certificates..........................34
7.4 Increasing Key Lifetimes.................................34
7.5 One Root Per Individual..................................35
7.6 Key Revocation Service...................................36
7.7 Threshold ACL Subjects...................................36
8. Security Considerations...................................37
References...................................................38
Acknowledgments..............................................40
Authors' Addresses...........................................41
Full Copyright Statement.....................................431. Overview of Contents 🗺️
this doc is laid out in these sections, so you can jump around like a main character 💅
- Section 2: the history of name certification, from 1976 on 🕰️
- Section 3: discussion of authorization, rather than authentication, as the desired purpose of a certificate 🔑
- Section 4: discussion of delegation 🤝
- Section 5: discussion of validity conditions: date ranges, CRLs, re-validations and one-time on-line validity tests ⏳
- Section 6: definition of 5-tuples and their reduction 🧮
- Section 7: discussion of key management 🗝️
- Section 8: security considerations 🚨
The References section lists all documents referred to in the text, plus readings that might be of interest to anyone reading on this topic 📖 The Acknowledgements section includes a list of contributors, mostly from the start of the working group. [The archive of working group mail is a more accurate source of contributor information.] 🫶 The Authors' Addresses section gives the addresses, telephone numbers and e-mail addresses of the authors 📮
1.1 Glossary 💜
the body of this document uses some terms in ways that could be specific to SPKI, so here's the tea 🍵
ACL: an Access Control List: a list of entries that anchors a certificate chain 🔗 Sometimes called a "list of root keys", the ACL is the source of empowerment for certificates. Here's the thing: a certificate passes power from its issuer to its subject, but the ACL is where that power actually comes from (since it theoretically has the owner of the resource it controls as its implicit issuer) 👑 An ACL entry has potentially the same content as a certificate body, but it has no Issuer (and is not signed) ✍️ There is most likely one ACL for each resource owner, if not for each controlled resource 🏰
CERTIFICATE: a signed instrument that empowers the Subject 🎀 It contains at least an Issuer and a Subject, and it can also hold validity conditions, authorization and delegation information. Certificates come in three categories: ID (mapping <name,key>), Attribute (mapping <authorization,name>), and Authorization (mapping <authorization,key>) 🗂️ An SPKI authorization or attribute certificate can pass along all the empowerment it got from the Issuer, or just a portion of it 🎁
ISSUER: the signer of a certificate and the source of the empowerment that the certificate communicates to the Subject 📣
KEYHOLDER: the person or other entity that owns and controls a given private key 🔐 This entity is said to be the keyholder of the keypair or just the public key, but control of the private key is assumed in all cases 🦋
PRINCIPAL: a cryptographic key that's capable of generating a digital signature 🧬 This document deals with public-key signatures, but any digital signature method should apply 🌈
SPEAKING: a Principal is said to "speak" by means of a digital signature 🗣️ The statement made is the signed object (often a certificate). The Principal is said to "speak for" the Keyholder 💅
SUBJECT: the thing empowered by a certificate or ACL entry 🌟 This can be a key, a name (with the understanding that the name is mapped by certificate to some key or other object), a hash of some object, or a set of keys arranged in a threshold function 🧩
S-EXPRESSION: the data format chosen for SPKI/SDSI 📜 It's a LISP-like parenthesized expression, with the limitations that empty lists are not allowed and the first element in any S-expression must be a string, called the "type" of the expression 🍓
THRESHOLD SUBJECT: a Subject for an ACL entry or certificate that specifies K of N other Subjects 🛡️ Conceptually, the power being transmitted to the Subject by the ACL entry or certificate is transmitted in (1/K) amount to each listed subordinate Subject. K of those subordinate Subjects must agree (by delegating their shares along to the same object or key) for that power to be passed along. This mechanism introduces fault tolerance and is especially useful in an ACL entry, providing fault tolerance for "root keys" 🫧
2. Name Certification ✨
okay so certificates were originally only supposed to do ONE job 🎀 binding names to keys, or keys to names. this idea goes all the way back to the Diffie and Hellman paper that introduced public key cryptography in 1976 💅 before that, key management was risky, expensive, and kinda chaotic, sometimes involving special couriers with briefcases handcuffed to their wrists 😭
Diffie and Hellman thought they had totally solved this problem 🔥 they wrote: "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]
the big idea was a modified phone book that's fully public 📖🦋 it replaced the trusted courier entirely! and this directory could go online, so it'd be available on demand, worldwide 🌍 Loren Kohnfelder thought about that possibility in his 1978 bachelor's thesis in electrical engineering from MIT [KOHNFELDER] and wrote: "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 First Definition of CERTIFICATE
Kohnfelder then said, "Each individual has a name in the system by which he is referenced in the Public File. Once two communicants have gotten each other's keys from the Public File they can securely communicate. The Public File digitally signs all of its transmissions so that enemy impersonation of the Public File is precluded." 🫶 to try to prevent performance problems, he invented a brand new construct: a digitally signed data record holding a name and a public key 💖 and he called it a CERTIFICATE ✨ because it was digitally signed, a certificate could be held by non-trusted parties and passed around from person to person. that solved the performance problems that come with one central directory 👑
2.2 The X.500 Plan and X.509
ten years after Kohnfelder's thesis, the ISO X.509 recommendation was published as part of X.500 🌸 X.500 was supposed to be a global, distributed database of named entities: people, computers, printers, etc. basically a global, online phone book 📞 the organizations owning a piece of the name space would maintain that piece and maybe even provide the computers where it's stored 🏢 X.509 certificates were defined to bind public keys to X.500 path names (Distinguished Names), with the goal of noting which keyholder had permission to modify which X.500 directory nodes 🔐 fun fact: the X.509 data record was originally designed to hold a password instead of a public key as the record-access authentication mechanism 🙈
the original X.500 plan is unlikely ever to happen 💀 lists of directory entries (like employee lists, customer lists, contact lists, etc.) are considered valuable or even confidential by the people who own them, so they're not likely to be released to the world as an X.500 directory sub-tree. for an extreme example, imagine the CIA adding its directory of agents to a world-wide X.500 pool 😭
the X.500 idea of a distinguished name (a single, globally unique name everyone could use when referring to an entity) is also not likely to happen 🥲 that idea needs one single, global naming discipline, and there are way too many entities already in the business of defining names outside of any single discipline. legacy therefore pushes against such an idea 🍓
2.3 X.509, PEM and PGP
the Privacy Enhanced Mail [PEM] effort of the Internet Engineering Task Force [RFC1114] adopted X.509 certificates, but with a different interpretation ✨ where X.509 was originally meant to say "the keyholder may modify this portion of the X.500 database," PEM took the certificate to mean "the key speaks for the named person." so what used to be an access control tool became an identity tool, kinda like Diffie, Hellman and Kohnfelder had imagined 🦋
the insistence on X.509 certificates with a single global root slowed PEM down so much that it missed its window of viability 😭 RIPEM, by Mark Riordan of MSU, was a version of PEM without X.509 certificates 🌈 it got distributed and used by a small community, but it fell out of use. MOSS (a MIME-enhanced version of PEM, produced by TIS (www.tis.com)) made certificate use optional, but it didn't get much distribution either 🥀
at about the same time, in 1991, Phil Zimmermann's PGP showed up with a totally different certificate model 💜 instead of waiting around for a single global root and the hierarchy of Certificate Authorities descending from it, PGP let multiple, (hopefully) independent but not specially trusted individuals sign a <name,key> association to attest to its validity 🎀 the theory was that with enough of these signatures, the association could be trusted, because not all of those signers would be corrupt 🫧 this became known as the "web of trust" model 🕸️ it differed from X.509 in how it assured trust in the <name,key> binding, but it still intended to bind a globally unique name to a key. so with PEM and PGP, the goal was for a keyholder to be known to anyone in the world by this certified global name 🌍✨
2.4 Rethinking Global Names
the assumption that a certificate's job was to bind a name to a key made total sense when it was first published 🕰️ in the 1970's, people operated in relatively small communities 🏘️ relationships formed face to face. once you knew who someone was, you often knew enough to decide how to behave with them. as a result, people boiled this requirement down to the simple phrase: "know who you're dealing with" 💅
names are, in turn, what we humans use as identifiers of persons 🧸 we learn this as infants, and it works in the family environment even today 👨👩👧 what we learn as infants is especially hard to unlearn later in life 🙈 so it's natural for people to translate the need to know who the keyholder is into a need to know the keyholder's name 💭
computer applications need to make decisions about keyholders 🤖 these decisions are almost never made strictly on the basis of a keyholder's name. there's some other fact about the keyholder that matters to the application (or to the human running the application) 👀 if a name functions at all for security purposes, it's as an index into some database (or human memory) of that other information 🗂️ and to play this role, the name has to be unique, so it can work as an index, and there has to be some information to index 🫶
the names we use to identify people are usually unique within our local domain, but that is not true on a global scale 🌏 it's extremely unlikely that the name we know someone by, a given name, would work as a unique identifier on the Internet 😭 given names still do the social job of making the named person feel recognized when they're addressed by name, but they're inadequate as the identifiers Diffie, Hellman and Kohnfelder had in mind 💖
in the 1970's, and even through the early 1990's, relationships formed in person, and you could assume you'd met the keyholder and therefore had acquired knowledge about them 🤝 if you could find a name that was an adequate identifier of that keyholder, you could use it to index into your memories about them and then make the relevant decision 🧠✨
in the late 1990's, this is no longer true 🌐 with the explosion of the Internet, you'll probably run into keyholders who are complete strangers in the physical world and will stay that way 👻 contact gets made digitally and stays digital for the whole relationship 📱 so on first encounter, there's no body of knowledge to be indexed by any identifier 🥺
one could consider building a global database of facts about all persons in the world and making it available (maybe for a fee) 💸 the name that indexes that database might also serve as a globally unique ID for the person it references 🪪 the database entry under that name could hold all the information needed to make a security decision 🔑 since there are multiple decision-makers, each interested in specific information, the database would need to contain the union of multiple sets of information 🧩 but that solution would be a massive privacy violation, and it would probably be rejected as politically impossible 🚫
a globally unique ID might even fail when dealing with people we DO know 🙃 few of us know the full given names of the people we deal with. a globally unique name for a person would be longer than the full given name (and probably contain it, out of respect for a person's fondness for their own name) 💅 so it wouldn't be a name we actually know the person by, unless humans radically change their behavior 🫠
a globally unique ID that contains a person's given name poses a special danger 🚨 if a human is part of the process (like scanning a database of global IDs to find the ID of a specific person in order to issue an attribute certificate), the human operator would probably pay attention to the familiar part of the ID (the common name) and less attention to the rest 👁️ since the common name isn't an adequate ID, this can lead to mistakes 😬 and where there can be mistakes, there's an avenue for attack ⚠️
when globally unique identifiers do need to be used, the best ID is probably one that looks uniform (like a long number or random-looking text string) so it has no recognizable sub-field 🌟 it should also be large enough (from a sparse enough name space) that typos wouldn't turn it into another valid identifier 🎯 iykyk, and now you do 💖✨
2.5 Inescapable Identifiers 🫣
okay so some people talk about global IDs like they're inescapable, as in they could stop someone from doing evil under one name, because that person would just change their name and start over. 💀 To make that actually happen, you'd need identifiers to get assigned (probably by governments, at birth) and some mechanism so you can always get from any real, flesh-and-blood person back to their ID. With that mechanism in place, any Certificate Authority wanting to issue a cert to a certain person would presumably pick that same inescapable name for the cert. A full set of biometrics might be enough, for example, to look someone up with no danger of a false positive in a database of globally assigned ID numbers, and with that procedure you could implement inescapable IDs. 😳
It's possible in some countries, but in others (like the US) it would meet strong political opposition. 🚫 Some countries give citizens government-assigned ID numbers but also have privacy regulations that ban using those numbers for routine business. In either of these latter cases, the inescapable ID wouldn't be available for use in routine certificates. 🙅♀️
There was a concern that commercial Certificate Authorities might be used to bring inescapable names into existence, bypassing the political process and the opposition to those names in countries where that opposition is strong. 👀 The way the (name,key) certificate business is evolving today, there are multiple competing CAs, each creating disjoint Distinguished Name spaces. There's also no real block to creating new CAs. So a person can drop one Distinguished Name and get another just by changing CA, which means these names are not inescapable. 🦋
2.6 Local Names 🏡
Globally unique names might be politically undesirable and kinda useless in the world of the Internet, but we use names all the time, bestie. 💖
The names we use are local names. These are the names we write in our personal address books or use as nicknames or aliases with email agents. ✉️ They can also be IDs assigned by corporations (like bank account numbers or employee numbers). These names or IDs don't need to be globally unique. Instead, they need to be unique for the one entity that maintains that address book, email alias file, or list of accounts. More importantly, they need to be meaningful to the person who uses them as indexes. 🧠
Ron Rivest and Butler Lampson showed with SDSI 1.0 [SDSI] that you can not only use local names locally, you can use local names globally. 🤯 The clear security advantage and operational simplicity of SDSI names caused us in the SPKI group to adopt SDSI names as part of the SPKI standard. 🌟
2.6.1 Basic SDSI Names 🎀
A basic SDSI 2.0 name is an S-expression with two elements: the word "name" and the chosen name. For example,
george: (name fred)represents a basic SDSI name "fred" in the name space defined by george. 🧚
2.6.2 Compound SDSI Names 🧩
If fred in turn defines a name, for example,
fred: (name sam)then george can refer to this same entity as
george: (name fred sam)2.7 Sources of Global Identifiers 🔑
Even though humans use local names, computer systems often need globally unique identifiers. 🤖 Even in the examples of section 2.6.2 above, we needed to make the local names more global, and we did that by specifying the name-space owner. 👑
If we're using public key cryptography, we have a ready source of globally unique identifiers. 💜
When someone creates a key pair for use in public key cryptography, the private key is bound to its owner by good key safeguarding practice. 🔐 If that private key gets loose from its owner, then a basic premise of public key cryptography has been violated, and that key is no longer of interest. 😱
The private key is also globally unique. If it weren't, the key generation process would be seriously flawed, and we'd have to abandon this public key system implementation. 💀
The private key must be kept secret, so it isn't a possible identifier. But each public key corresponds to one private key and therefore to one keyholder. So the public key, viewed as a byte string, is an identifier for the keyholder. 🫶
If there exists a collision-free hash function, then a collision-free hash of the public key is also a globally unique identifier for the keyholder, and probably a shorter one than the public key itself. ✨
2.8 Fully Qualified SDSI Names 🌈
SDSI local names are of great value to their definer. Each local name maps to one or more public keys and therefore to the corresponding keyholder(s). 🗝️ Through SDSI's name chaining, these local names become potentially useful to the whole world. [See section 2.6.2 for an example of SDSI name chaining.] 🔗
To a computer system making use of these names, the name string is not enough. You have to identify the name space in which that byte string is defined. That name space can be identified globally by a public key. 🌍
It's SDSI 1.0 convention, preserved in SPKI, that if a (local) SDSI name occurs within a certificate, then the public key of the issuer is the identifier of the name space in which that name is defined. 📜
However, if a SDSI name is ever going to occur outside of a certificate, the name space within which it's defined must be identified. This gives rise to the Fully Qualified SDSI Name. That name is a public key followed by one or more names relative to that key. If there are two or more names, then the string of names is a SDSI name chain. For example,
(name (hash sha1 |TLCgPLFlGTzgUbcaYLW8kGTEnUk=|) jim therese)is a fully qualified SDSI name, using the SHA-1 hash of a public key as the global identifier defining the name space and anchoring this name string. 🦋
2.9 Fully Qualified X.509 Names 📛
An X.509 Distinguished Name can, and sometimes must, be expressed as a Fully Qualified Name. 😤 If the PEM or original X.500 vision of a single root for a global name space had come true, this wouldn't be necessary, because all names would be relative to that same one root key. But there is not now, and is not likely ever to be, a single root key. 💔 Therefore, every X.509 name should be expressed as the pair
(name <root key> <leaf name>)if all leaf names descending from that root are unique. If uniqueness is enforced only within each individual CA, then one would build a Fully Qualified Name chain from an X.509 certificate chain, yielding the form
(name <root key> <CA(1)> <CA(2)> ... <CA(k)> <leaf name>)2.10 Group Names 👯
SPKI/SDSI does not claim to enforce one key per name. So a named group can be defined by issuing multiple (name,key) certificates with the same name, one for each group member. 🎉
3. Authorization 🛡️
Fully qualified SDSI names represent globally unique names, but at every step of their construction, the local name used is presumably meaningful to the issuer. So with SDSI name certificates, you can identify the keyholder by a name that's relevant to someone. 🥰
However, what an application needs to do, when given a public key certificate or a set of them, is answer the question of whether the remote keyholder is permitted some access. 🚪 That application must make a decision. The data needed for that decision is almost never the spelling of a keyholder's name. 💅
Instead, the application needs to know whether the keyholder is authorized for some access. According to the members of the SPKI WG, this is the primary job of a certificate, and the SPKI certificate was designed to meet this need as simply and directly as possible. ⭐
We realize the world isn't going to switch to SPKI certificates overnight. So we developed an authorization computation process that can use certificates in any format. That process is described below in section 6. 🧮
The various methods of establishing authorization are documented below, briefly. (See also [UPKI]) 📚
3.1 Attribute Certificates 🏷️
An Attribute Certificate, as defined in X9.57, binds an attribute that could be an authorization to a Distinguished Name. For an application to use this information, it must combine an attribute certificate with an ID certificate, in order to get the full mapping:
authorization -> name -> keyPresumably, the two certificates involved came from different issuers: one an authority on the authorization, and the other an authority on names. 🤝 However, if either of these issuers were subverted, an attacker could obtain an authorization improperly. 😬 Therefore, both the issuers need to be trusted with the authorization decision. 🙏
3.2 X.509v3 Extensions 🧾
X.509v3 permits general extensions. These extensions can be used to carry authorization information. This makes the certificate an instrument mapping both:
authorization -> keyand
name -> keyIn this case, there's only one issuer, who must be an authority on both the authorization and the name. 👑
Some propose issuing a master X.509v3 certificate to an individual and letting extensions hold all the attributes or authorizations the individual would need. 🫠 This would require the issuer to be an authority on all of those authorizations. Also, aggregating attributes would shorten the lifetime of the certificate, since each attribute would have its own lifetime. ⏳ Finally, aggregation of attributes amounts to building a dossier and represents a potential privacy violation. 🙈
For all of these reasons, it is desirable that authorizations be limited to one per certificate. 💯
3.3 SPKI Certificates 🌸
A basic SPKI certificate defines a straight authorization mapping:
authorization -> keyIf someone wants access to a keyholder's name, for logging purposes or even for punishment after wrongdoing, then one can map from key to location information (name, address, phone, ...) to get:
authorization -> key -> nameThis mapping has an apparent security advantage over the attribute certificate mapping. In the mapping above, only the
authorization -> keymapping needs to be secure at the level required for the access control mechanism. 🔒 The
key -> namemapping (and the issuer of any certificates involved) needs to be secure enough to satisfy lawyers or private investigators, but a subversion of this mapping does not let the attacker defeat the access control. 🕵️♀️ Presumably, therefore, the care with which these certificates (or database entries) are created is less critical than the care with which the authorization certificate is issued. It's also possible that the mapping to name doesn't need to be on-line or protected as certificates, since human investigators would only use it in unusual circumstances. 🧐
3.4 ACL Entries 🔐
SDSI 1.0 had an ACL that granted authorization to names. Honestly, it was basically like an attribute certificate, except it didn't need to be signed or issued by any key. It lived in local memory and was assumed to be issued by the owner of the computer, and therefore by the owner of the resource being controlled. so cozy 🧚
In SPKI, an ACL entry can be implemented however the developer likes 💅. It never gets communicated, so it doesn't need to be standardized. There is a sample implementation documented, though: it's a certificate body minus the issuer field. The ACL entry can have a name as its subject, like in SDSI 1.0, or it can have a key as its subject. Examples of the key version are the list of SSL root keys in an SSL capable browser, or the file .ssh/authorized_keys in a user's home UNIX directory 🗝️. Those ACLs are single-purpose, so their individual entries don't carry explicit authorizations. SPKI does use explicit authorizations, though, so you can run common authorization computation code across multiple applications. that's the glow-up ✨
4. Delegation 🎀
Okay, one of the best powers of an authorization certificate is delegation. You can pass authorizations from one person to another without bothering the owner of the resource(s) involved 🦋. You can issue a simple permission (like "read some file"), or you can issue the permission to delegate that permission further. Iconic.
Two issues came up while we were thinking about delegation. One was the desire to limit the depth of delegation. The other was the question of separating delegators from the people who can actually exercise the delegated permission. it's giving complicated, but we handled it 💖
4.1 Depth of Delegation 🌸
There were three camps when it came to depth of delegation: no control, boolean control, and integer control. Each camp still has supporters, but the group ended up deciding in favor of boolean control.
4.1.1 No control 🙈
The argument for no control goes like this: if a keyholder is given permission to do something but not permission to delegate it, that keyholder can still loan out the empowered private key, or set up a proxy service that signs challenges or requests for the intended delegate. So trying to restrict the permission to delegate is ineffective, and it might backfire by leading to improper security practices 💀.
4.1.2 Boolean control 🍓
The argument for boolean control is that you might need to specify an inability to delegate. Picture the US Commerce Department having a key that's authorized to declare a cryptographic software module exportable, and also to delegate that authorization to others (like manufacturers). It's reasonable to assume the Commerce Department would not issue permission to delegate this further. Instead, it would want a direct legal agreement with each manufacturer, and it would issue a certificate to that manufacturer only to reflect that the legal agreement is in place 📜.
4.1.3 Integer control 🔢
The argument for integer control is that you might want to restrict the depth of delegation so you can control how far a delegated permission spreads 🌿.
4.1.4 The choice: boolean ✨
Of the three, the group picked boolean control 👑. The subject of a certificate or ACL entry can exercise any permission granted to it and, if delegation is TRUE, it can also delegate that permission (or some subset of it) to others.
Now, the no control argument is logically appealing, but it still assumes a user will value their private key enough not to loan it out, or that the key will be locked in hardware where it can't be copied to another user. That doesn't stop the user from setting up a signing oracle, though lack of network connectivity might get in the way of that mechanism 🛜.
The integer control option was the original design, and it had appeal. It was defeated by the inability to predict the proper depth of delegation, though. You can always end up needing to go one more level down, for example by creating a temporary signing key for a laptop 💻. So the initially predicted depth could be way off.
As for controlling how permissions proliferate: there's no control on the width of the delegation tree, so controlling its depth isn't a tight control on proliferation either. sorry integer control, you got cooked 🫠
4.2 May a Delegator Also Exercise the Permission? 💅
We decided that a delegator is free to create a new key pair, also controlled by the delegator, and delegate the rights to that key so it can exercise the delegated permission. So there was no benefit in trying to restrict someone from exercising a permission just because they're allowed to delegate it. no point fighting it, bestie 🤷♀️
4.3 Delegation of Authorization vs. ACLs 🏰
One concern with defining an authorization certificate is that the same function can be performed by traditional <authorization,name> ACLs and <name,key> ID certificates that define groups. That mechanism was described in SDSI 1.0. A new mechanism needs to add value, or it just complicates life for the developer 😤.
So, why is delegated authorization better than ACLs? Check out this example 👀.
Imagine a firewall proxy that permits telnet and ftp access from the Internet into a network of US DoD machines. Because that destination network is so sensitive, strong access control would be desired 🛡️. You could use public key authentication and public key certificates to establish who the individual keyholder is. Both the private key and the keyholder's certificates could be kept on a Fortezza card. That card holds X.509v1 certificates, though, so all that can be established is the name of the keyholder. Then it's the firewall's job to keep an ACL that lists named keyholders and the forms of access each one is permitted.
Now think about the ACL itself. Not only would it be potentially huge, demanding way more storage than the firewall would otherwise need, but it would also need its own ACL. You couldn't, for example, have someone in the Army decide whether someone in the Navy gets access 🙅♀️. In fact, the ACL would probably need not one level of its own ACL, but a nested set of ACLs, eventually reflecting the organizational structure of the entire Defense Department 🌀.
Without the ACLs, the firewall could be implemented in a device with no mass storage, sitting in a sealed unit you could easily hold in one hand 🤏. With the ACLs, it would need a large mass storage device, which would be accessed not only while making access control decisions but also while updating the ACLs 📦.
Now, let the access be controlled by authorization certificates instead. The firewall would have an ACL with just one entry, granting a key belonging to the Secretary of Defense the right to delegate all access through the firewall 🫡. The Secretary would, in turn, issue certificates delegating this permission to delegate to each of their subordinates. The process would keep iterating until some enlisted man received permission to penetrate that firewall for one specific protocol, but without permission to delegate that permission further. the chain of trust is literally a family tree 🌈
The certificate structure generated would reflect the organizational structure of the entire Defense Department, just like the nested ACLs would have. The difference is that control of these certificates (through their issuance and revocation) is distributed. It doesn't need to show up in that one firewall, or be replicated in all firewalls 🦋. Each individual delegator performs a simple, well-understood task, so the application software that allows the delegation is correspondingly simple. Main character energy for the whole design ✨.
5. Validity Conditions ⏳
A certificate, or an ACL entry, has optional validity conditions. The traditional ones are validity dates: not-before and not-after 📅.
The SPKI group resolved, in discussion, that on-line tests of various kinds are validity conditions too. That means they further refine the valid date range of a certificate. Three kinds of on-line tests are envisioned: CRL, re-validation, and one-time 🔍.
When validity confirmation is provided by some online test, the issuer of those refinements doesn't need to be the issuer of the original certificate. In lots of cases, the business or security model for the two issuers is different 🏢. However, in SPKI, the certificate issuer must specify the issuer of validity confirmations. no skipping this part, it's important 📌
5.1 Anti-matter CRLs 👻
An early form of CRL [Certificate Revocation List] was modeled after the newsprint book that used to be kept at supermarket checkout stands 🛒. Those books held lists of bad checking account numbers and, later, bad credit card numbers. If your payment instrument wasn't listed in the book, it was considered good.
These books were issued periodically and delivered by some means that didn't necessarily take a constant time 📚. When a new book arrived, though, the clerk would replace the older edition with the new one and start using it. This design fit the constraints of the implementation: physical books, delivered by physical means. The book held bad account numbers rather than good ones because the list of bad accounts was smaller 🧾.
An early CRL design followed this model. It had a list of revoked certificate identifiers. It also had a sequence number, so you could tell which of two CRLs was more recent. A newer CRL would replace an older one 🔄.
This mode of operation is like wandering anti-matter 🌌. When the issuer wants to revoke a certificate, it gets listed in the next CRL to go out. If the revocation is urgent, that CRL can be released immediately. The CRL then follows some dissemination process that's unrelated to what the consumers of the CRL need 📡. If the CRL runs into a certificate it has listed, it effectively annihilates that certificate. If it runs into an older CRL, it annihilates that CRL too, leaving copies of itself at the verifiers it encounters. chaotic but make it protocol 💀
However, this process is non-deterministic. The result of the authorization computation is at least timing dependent. Given an active adversary, it can also be a security hole 🚨. That is, an adversary can prevent revocation of a given certificate just by preventing the delivery of new CRLs. This doesn't take cryptographic-level effort, just network tampering. yikes, the security implications are NOT it 😭
SPKI has ruled out the use of wandering anti-matter CRLs for its certificates. Under SPKI rules, every authorization computation is deterministic 💜.
5.2 Timed CRLs
okay so SPKI totally allows timed CRLs 🎀. if a certificate can be referenced in a CRL, the CRL process has to follow three conditions, and they're lowkey iconic:
- The certificate must list the key (or its hash) that will sign the CRL and may give one or more locations where that CRL might be fetched.
- The CRL must carry validity dates.
- CRL validity date ranges must not intersect. That is, one may not issue a new CRL to take effect before the expiration of the CRL currently deployed.
so with these rules, no certificate that could use a CRL gets processed without a valid CRL 💅, and no surprise CRL can pop up at the verifier 👀. the result is a deterministic validity computation that doesn't care about clock skew ✨. the catch is that if the verifier's clock is off, it might land on a result the issuer didn't want 🙈. the CRL here is more like completing the certificate, not a dramatic "I changed my mind" announcement to the whole world 💀.
CRLs can get super big, and they tend to only grow 📈, so you might want to send changes instead of full ones. that means a full CRL followed by a sequence of delta-CRLs 🍓. that whole sequence gets treated as one current CRL, and the combined CRL must follow the conditions listed above 🫶.
5.3 Timed Revalidations
CRLs are negative statements (the "nope, this one's dead" list 💀). the positive version is called a revalidation ✨. typically a revalidation lists only one certificate, the one you care about, although it might list a set of certificates (to save digital signature effort) 🖋️.
as with the CRL, SPKI demands that this process be deterministic, so the revalidation has to follow the same rules listed above (in section 5.2) 💜.
5.4 Setting the Validity Interval
both timed CRLs and timed revalidations have non-0 validity intervals 🌸. to set this validity interval, you have to answer the big question: "How long are you willing to let the world believe and act on a statement you know to be false?" 😳
so picture this: the previous CRL or revalidation was just signed and sent to at least one consumer, which means it's locking up a time slot 🔒. the next available time slot starts after this validity interval ends. that's the earliest you can revoke a certificate you've learned is false 💀.
the answer comes from risk management 📊. it'll probably be based on expected monetary losses, at least in commercial cases 💰.
5.5 One-time Revalidations
validity intervals of length zero are not possible 🙅♀️. transmission takes time, so by the time a CRL reaches the verifier, it'd already be out of date and unusable. that's assuming perfect clock synchronization, and if clock skew is taken into account, the validity intervals need to be that much larger to be meaningful ⏰.
but for anyone who wants a zero validity interval anyway, SPKI defines a one-time revalidation 🦋.
this one has no lifetime beyond the current authorization computation ✨. you apply for it online by submitting a request containing a nonce. that nonce gets returned in the signed revalidation instrument, which prevents replay attacks 🔐. this protocol takes the place of a validity date range and represents a validity interval of zero, starting and ending at the time the authorization computation completes 🫧.
5.6 Short-lived Certificates
if you're doing a performance analysis of the different ways to get fine-grained control over a certificate's validity interval, you should consider just making the original certificate short-lived 🧚. this is especially worth a look if the online test result is issued by the same key that issued the certificate 🔑. there are cases where a short-lived certificate needs fewer signatures and less network traffic than the online test options. a short-lived certificate always needs fewer signature verifications than a certificate plus an online test result 🏃♀️.
if you want to issue short-lived certificates, SPKI defines a kind of online test statement that tells the certificate's user where a replacement short-lived certificate might be fetched 🎁.
5.7 Other possibilities
there are other possibilities to think about when you're choosing a validity condition model 🤔.
5.7.1 Micali's Inexpensive On-line Results
Silvio Micali has patented a mechanism that uses hash chains to revalidate or revoke a certificate inexpensively 🔗. this changes the performance requirements of those models, so it might change the conclusion from a performance analysis [ECR] 📉.
5.7.2 Rivest's Reversal of the CRL Logic
Ron Rivest wrote a paper [R98] arguing that the whole validity condition model is flawed 🤯. the reason is that it assumes the issuer (or some entity it delegates to) decides the conditions under which a certificate is valid. that traditional model fits a military key management model, where a central authority handles key release and decides key validity 🎖️.
but in the commercial space, it's the verifier, not the issuer, who takes the risk by accepting a certificate 😤. so it should be the verifier who decides what level of assurance he needs before accepting a credential. the verifier needs information from the issuer, and the more recent that information is the better, but the decision is the verifier's in the end 👑.
this line of thought deserves more consideration, but it isn't reflected in the SPKI structure definition 🙃. it might even be that both the issuer and the verifier have a stake in this decision, so any replacement validity logic would have to include inputs from both 🫶.
6. Tuple Reduction ✨
the processing of certificates and related objects to yield an authorization result is the province of the developer of the application or system 💻. the processing plan here is an example you may follow, but its main purpose is to clarify the semantics of an SPKI certificate and how it, and various other kinds of certificate, might be used to yield an authorization result 💖.
there are three kinds of entity that might be input to the computation that yields an authorization result:
<name,key>(as a certificate)<authorization,name>(as an attribute certificate or ACL entry)<authorization,key>(as an authorization certificate or ACL entry)
these entities get processed in three stages 🎢.
- Individual certificates are verified by checking their signatures and possibly performing other work. then they're mapped to intermediate forms, called "tuples" here 🧩.
the other work for SPKI or SDSI certificates might include processing of online test results (CRL, revalidation or one-time validation) 🔍.
the other work for PGP certificates may include a web-of-trust computation 🕸️.
the other work for X.509 certificates depends on the written documentation for that particular use of X.509 (typically tied to the root key the certificate descended from). it could involve checking information in the parent certificate as well as additional information in the certificate's extensions 📜. that's because some people use X.509 certificates just to define names, while others use X.509 to communicate an authorization implicitly (e.g., SSL server certificates). some might define extensions of X.509 to carry explicit authorizations 🪪. all of these interpretations are specified in written documentation associated with the certificate chain, and therefore with the root the chain descends from 🌳.
if online tests are involved in the certificate processing, then the validity dates of those online test results are intersected by VIntersect() [defined in 6.3.2, below] with the validity dates of the certificate. that gives you the dates in the certificate's tuple(s) 📅.
- Uses of names are replaced with simple definitions (keys or hashes), based on the name definitions available from reducing name 4-tuples 🔁.
- Authorization 5-tuples are then reduced to a final authorization result 🏁.
6.1 5-tuple Defined
the 5-tuple is an intermediate form that's assumed to be held in trusted memory, so it doesn't need a digital signature for integrity 🔐. it's produced from certificates or other credentials via trusted software. its contents are the same as the contents of an SPKI certificate body, but it might be derived from another form of certificate or from an ACL entry 💫.
the elements of a 5-tuple are:
- Issuer: a public key (or its hash), or the reserved word
Self. this identifies the entity speaking this intermediate result 🗣️. - Subject: a public key (or its hash), a name used to identify a public key, the hash of an object, or a threshold function of subordinate subjects. this identifies the entity being spoken about in this intermediate result 🎯.
- Delegation: a boolean. if
TRUE, then the Subject is permitted by the Issuer to further propagate the authorization in this intermediate result 📣. - Authorization: an S-expression. [Rules for combination of Authorizations are given below.] 🧾
- Validity dates: a not-before date and a not-after date, where "date" means date and time. if the not-before date is missing from the source credential, then minus infinity is assumed. if the not-after date is missing, then plus infinity is assumed ♾️.
6.2 4-tuple Defined
a <name,key> certificate (such as X.509v1 or SDSI 1.0) carries no authorization field but does carry a name 🏷️. since it's qualitatively different from an authorization certificate, it gets its own intermediate form 🩷.
the elements of a Name 4-tuple are:
- Issuer: a public key (or its hash). this identifies the entity defining this name in its private name space 🏠.
- Name: a byte string 🔤.
- Subject: a public key (or its hash), a name, or a threshold function of subordinate subjects. this defines the name 🪄.
- Validity dates: a not-before date and a not-after date, where "date" means date and time. if the not-before date is missing from the source credential, then minus infinity is assumed. if the not-after date is missing, then plus infinity is assumed 📆.
6.3 5-tuple Reduction Rules
the two 5-tuples:
<I1,S1,D1,A1,V1> + <I2,S2,D2,A2,V2>yield:
<I1,S2,D2,AIntersect(A1,A2),VIntersect(V1,V2)>provided:
- the two intersections succeed,
S1 = I2,- and
D1 = TRUE.
it's a whole vibe, honestly 🌈. if S1 is a threshold subject, there's a slight modification to this rule, as described below in section 6.3.3 🫧.
6.3.1 AIntersect ✨
okay so an authorization is basically a list of strings or sub-lists, and what they mean is defined by the app that's going to use it for access control 🔐. two authorizations intersect by matching, element for element 💅. if one list is longer but they match at every spot where both lists have elements, the longer one is the result. so extra elements have to make the permission tighter 🫶
the actual authorization strings are app-dependent, but AIntersect gives you automatic rules for intersecting them so devs can actually know what their strings mean 🧠. special semantics would need special reduction software, so keep that in mind 😭
here's an example. imagine an ftpd that does public key access control with authorization certificates. under that service,
(ftp (host ftp.clark.net))might mean the keyholder can do ftp access to all directories on ftp.clark.net, with every kind of access (read, write, delete, ...). that's way more general (it allows more access) than
(ftp (host ftp.clark.net) (dir /pub/cme))which allows every kind of access but only in the directory specified. the intersection of the two is the second one 🎀
since the AIntersect rules imply position dependency, you could also write the previous authorization string as:
(ftp ftp.clark.net /pub/cme)to keep the form compact 🦋
for wild cards, there's a small number of special S-expressions, using * as the expression name 🌸
(*)stands for the set of all S-expressions and byte-strings. in other words, it matches anything. when you intersect it with anything, the result is that other thing. [The AIntersect rule about lists of different length treats a list as if it had enough (*) entries implicitly appended to it to match the length of another list with which it was being intersected.] 🙈
(* set <tag-expr>*)stands for the set of elements listed in the *-form 💜
(* prefix <byte-string>)stands for the set of all byte strings that start with the one given in the *-form ✨
(* range <ordering> <lower-limit>? <upper-limit>?)stands for the set of all byte strings lexically (or numerically) between the two limits. the ordering parameter (alpha, numeric, time, binary, date) specifies the kind of strings allowed 🍓
AIntersect() is normal set intersection, when *-forms are defined like above and a normal list means all lists that start with those elements 🧚 the examples below should explain it for anyone who'd rather skip the set-operation talk 🫶
AIntersect( (tag (ftp ftp.clark.net cme (* set read write))),
(tag (*)) )evaluates to
(tag (ftp ftp.clark.net cme (* set read write)))AIntersect( (tag (* set read write (foo bla) delete)),
(tag (* set write read) ) )evaluates to
(tag (* set read write))AIntersect( (tag (* set read write (foo bla) delete)),
(tag read ) )evaluates to
(tag read)AIntersect( (tag (* prefix http://www.clark.net/pub/)),
(tag (* prefix http://www.clark.net/pub/cme/html/)) )evaluates to
(tag (* prefix http://www.clark.net/pub/cme/html/))AIntersect( (tag (* range numeric ge #30# le #39# )), (tag #26#) )fails to intersect. 💀
6.3.2 VIntersect 📅
date range intersection is super straightforward 😌
V = VIntersect( X, Y )is defined as
Vmin = max( Xmin, Ymin )Vmax = min( Xmax, Ymax )and if Vmin > Vmax, then the intersection failed 💔
these rules assume daytimes are expressed in a monotonic form, the way they are in SPKI ⏰
the full SPKI VIntersect() also deals with online tests. in the most straightforward implementation, each online test a certificate is subject to gets evaluated. each one carries a validity interval, in terms of dates. that validity interval gets intersected with any present in the certificate, to yield a new, current validity interval 🔄
an implementation of VIntersect() can also gather up the online tests present in each certificate and include the union of all those tests in the accumulating tuples. in that case, evaluating those online tests is deferred until the end of the process. this might make sense if the tuple reduction is for generating a summary certificate (Certificate Result Certificate) that you hope will be useful for a long time, rather than answering an immediate authorization question 🧃
6.3.3 Threshold Subjects 🧩
a threshold subject is specified by two numbers, K and N [0<K<=N], and N subordinate subjects. a threshold subject gets reduced to a single subject by selecting K of the N subjects and reducing each of those K to the same subject, through a sequence of certificates. the (N-K) unselected subordinate subjects are set to (null) 🫠
the intermediate form for a threshold subject is a copy of the tuple it appears in, but with only one of the subordinate subjects. those subordinate tuples get reduced individually until the list of subordinate tuples has (N-K) (null) entries and K entries with the same subject. at that point, those K tuples are validity-, authorization- and delegation- intersected to yield the single tuple that replaces the list of tuples 👑
6.3.4 Certificate Path Discovery 🗺️
all reduction operations happen in the order the prover provides. that makes the verifier's life easier, but it leaves finding the correct list of reductions to the prover 🙏
the general algorithm for finding the right certificate paths from a big unordered set of certificates has been solved[ELIEN], but it might only be needed rarely 🤓 each keyholder who gets some authority should receive a sequence of certificates delegating that authority. that keyholder may then want to delegate part of it on to another keyholder. to do that, a single additional certificate is generated and appended to the sequence already available, giving a sequence the delegatee can use to prove access permission 💖
6.4 4-tuple Reduction 🌈
there are name 4-tuples in two classes: ones that define the name as a key, and ones that define the name as another name 🎀
1. [(name K1 N) -> K2]
2. [(name K1 N) -> (name K2 N1 N2 ... Nk)]just like the 5-tuples in the previous section, name definition 4-tuples should be delivered in the order the prover needs. then the rule for name reduction is to replace the name just defined with its definition. for example,
(name K1 N N1 N2 N3) + [(name K1 N) -> K2]
-> (name K2 N1 N2 N3)or, in case 2 above,
(name K1 N Na Nb Nc) + [(name K1 N) -> (name K2 N1 N2 ... Nk)]
-> (name K2 N1 N2 ... Nk Na Nb Nc)with the second form of name definition, names can temporarily grow 📈 if the prover is providing certificates in order, the verifier only needs to do as it's told 🫡
if the verifier is working from an unordered pool of tuples, then a safe rule for name reduction is to apply only those 4-tuples that define a name as a key. those applications should bring 4-tuples that started out in class (2) into class (1), and eventually reduce all names to keys. any naming loops get avoided by this process 🔁✅
6.4.1 4-tuple Threshold Subject Reduction 🧠
some of a threshold subject's subordinate subjects might be names. those names have to be reduced by applying 4-tuples. the name reduction process runs independently on each name in the subordinate subject, as indicated in 6.3.3 above 🫶
you can reduce individual named subjects in a threshold subject and leave the subject in threshold form, if you want. there's no delegation- or authorization-intersection involved, only a validity- intersection during name reduction. this might be used by a service that produces Certificate Result Certificates [see 6.7] 🧾
6.4.2 4-tuple Validity Intersection ⏳
whenever a 4-tuple is used to reduce the subject (or part of the subject) of another tuple, its validity interval gets intersected with that of the tuple holding the subject being reduced, and the intersection is used in the resulting tuple. since a 4-tuple has no delegation or authorization fields, the delegation permission and authorization of the tuple being acted upon don't change 🌸
6.5 Certificate Translation 🔮
any certificate currently defined, plus ACL entries and possibly other instruments, can be translated to 5-tuples (or name tuples) and therefore take part in an authorization computation. the specific rules for those are below 🦋
6.5.1 X.509v1 📜
the original X.509 certificate is a <name,key> certificate. it translates directly to a name tuple. the form
[Kroot, (name <leaf-name>), K1, validity]is used if the rules for that particular X.509 hierarchy say all leaf names are unique under that root. if uniqueness of names applies only to individual CAs in the X.509 hierarchy, then you have to generate
[Kroot, (name CA1 CA2 ... CAk <leaf-name>), K1, validity]after verifying the certificate chain by the rules that fit that particular chain 🔍
6.5.2 PGP 🐧
a PGP certificate is a <name,key> certificate. it gets verified by web-of-trust rules (as specified in the PGP documentation). once verified, it yields name tuples of the form
[Ki, name, K1, validity]where Ki is a key that signed that PGP (UserID,key) pair. there'd be one tuple produced for each signature on the key, K1 ✍️
6.5.3 X.509v3 🪪
an X.509v3 certificate may be used to declare a name. it might also declare explicit authorizations, through extensions. it might also declare an implicit authorization of the form (tag (*)). the actual set of tuples it yields depends on the documentation associated with that line of certificates. conceptually, that documentation could be considered associated with the root key of the certificate chain 🌳 some X.509v3 certificates (like the ones used for SET) have defined extra validity tests for certificate chains that depend on custom extensions. so X.509v3 chains will likely have to be validated independently, by chain validation code specific to each root key 😤 after that validation, that root-specific code can generate the appropriate multiple tuples from the one certificate 💅
6.5.4 X9.57 🏷️
an X9.57 attribute certificate should yield one or more 5-tuples, with names as Subject. the code translating the attribute certificate will have to build a fully-qualified name to represent the Distinguished Name in the Subject. for any attribute certificates that refer to an ID certificate explicitly, the Subject of the 5-tuple can be the key in that ID certificate, skipping the construction of name 4-tuples 🙌
6.5.5 SDSI 1.0 🌷
a SDSI 1.0 certificate maps directly to one 4-tuple 🎯
6.5.6 SPKI 🫧
an SPKI certificate maps directly to one 4- or 5- tuple, depending on whether it's a name certificate or carries an authorization 💜
6.5.7 SSL ✨
okay bestie, an SSL certificate is carrying a bunch of permissions, and some of them are just implied 💅 The authorization:
(tag (ssl))is implicit, so nobody has to write it down 🫶 The server cert also has a DNS name parameter that gets matched against the DNS name of the web page you're connecting to. That could be encoded as:
(tag (dns <domain-name>))Then there's the "global cert" permission 🌍 It's the one that lets a US-supplied browser connect with full strength symmetric cryptography even when the server is outside the USA. It might look like:
(tag (us-crypto))Other key usage attributes get encoded as tag fields too, but the full tea on those is saved for the examples document 📚
An ACL entry for an SSL root key would have the tag:
(tag (* set (ssl) (dns (*))))which, by the rules of intersection, is the same as:
(tag (* set (ssl) (dns)))unless that root key also got permission from the US Commerce Department to grant us-crypto, in which case it would be:
(tag (* set (ssl) (dns) (us-crypto)))A CA certificate used for SSL then only has to pass down its chain whatever permissions were allocated in the ACL 🔗 So its tag might translate to:
(tag (*))A leaf server certificate for the Datafellows server could have a tag field like:
(tag (* set (ssl) (dns www.datafellows.com)))This shows it's allowed to do SSL and to operate from that domain name, but it is not allowed to use US crypto with a US browser 🙅♀️
The (* set) form for those two attributes could have been shortened to:
(tag (ssl www.datafellows.com))and CA certificates might carry (tag (ssl (*))) or just (tag (*)) ✨ Keeping them separate with (* set) leaves room for a future SSL upgrade 🔮 In that setup, the (ssl) permission would come from one set of root keys (the current CAs), the (dns) permission from another set (the ones empowered to speak in DNSSEC), and the (us-crypto) permission only from a root key belonging to the US Department of Commerce. The verifying code, like a browser, would then run three separate tests, each doing its own 5-tuple reduction from a different root key ACL entry 🧩
The fact that these three kinds of permission are treated as if ANDed comes from the logic of the code that interprets them, not from the certificate itself 🤔 That decision lives in the authorization code the verifying application runs.
6.6 Certificate Result Certificates
Typically you'll reduce a chain of certificates to answer one of two authorization questions 🧐
- Is this Subject, S, allowed to do A, under this ACL and with this set of certificates?
- What is Subject S allowed to do, under this ACL and with this set of certificates?
The answer to the second question can be packed into a new certificate issued by whoever did the computation 📦 That one certificate matches the semantics of the underlying certificates and online test results. We call it a Certificate Result Certificate 💖
7. Key Management
Cryptographic keys have limited lifetimes 💀 Keys can get stolen, and they might also be discovered through cryptanalysis. If a theft is noticed, the key can be replaced like a credit card. The scarier case is when the theft isn't noticed, so to cover that, keys get replaced routinely 🔄
Replacing a key has to be announced to everyone who would use the new one 📣 It also has to happen smoothly, with as little hassle as possible 🧚
Rather than define a mechanism for declaring a key bad or replaced, SPKI gives certificates limited lifetimes so they can be swapped out 🦋 So under SPKI, you don't declare a key bad. You just stop empowering it and empower some other key instead. The limit on a certificate's lifetime can come from a limit set at issuance, or from a lifetime picked up through an online test (CRL, revalidation, or one-time). That means all key lifetime control turns into certificate lifetime control ✨
7.1 Through Inescapable Names
If keyholders had inescapable names [see section 2.5, above], you could refer to them by those names and define a certificate that maps from an inescapable name to the person's current key 🗝️ Any CA could issue that certificate, since all CAs would use the same inescapable name for the keyholder. The attribute certificates and ACLs that refer to the keyholder would all point to that one inescapable name.
However, there are no inescapable names for keyholders 😭 [See section 2.5, above.]
7.2 Through a Naming Authority
You could conceivably have a government body or some other entity that voluntarily issues names to a keyholder, strictly for key management 🏛️ You'd receive all authorizations through that name. There would have to be only one such authority, though. Otherwise, names would have to be built from parts: an authority name plus the individual's name. And the authority name would, in turn, have to be granted by some single global authority 🌐
That authority would then be able to make its own keys and certificates to empower them as any individual. Through those fake certificates, it could pick up the access rights of anyone in the world 👀 Such power is not likely to be tolerated, so a central authority like this is not likely to come to pass 🙅♀️
7.3 Through <name,key> Certificates
Instead of inescapable names or single-root naming authorities, we have names assigned by some entity that issues a <name,key> certificate 📜 As noted in sections 2.8 and 2.9, above, these names don't mean anything on their own. They have to be fully qualified to have meaning 💅
So in the construct:
(name (hash sha1 |TLCgPLFlGTzgUbcaYLW8kGTEnUk=|) jim)the name is not
"jim"but rather
"(name (hash sha1 |TLCgPLFlGTzgUbcaYLW8kGTEnUk=|) jim)"This name includes a public key (through its hash, in the example above) 🔑 That key has a lifetime like any other key, so this name doesn't have the kind of permanence that an inescapable name has, free from key lifetimes 😤 Still, it looks like our only alternative, so it's the one we've got 🫠
The keyholder could easily issue this name themselves, purely for key management. In that case, there's no worry about a third-party naming authority messing with access control 🙌
7.4 Increasing Key Lifetimes
By the logic above, any name hangs off some public key. So the job is to increase the lifetime of that public key ⏳ Once a key's lifetime is longer than the expected lifetime of any authorization granted through it, a series of new, long-lifetime keys can cover a keyholder forever 👑
For a key to have a long lifetime, it needs to be strong against cryptanalytic attack and against theft 🛡️ It should be used only on a trusted machine running trusted software. It should not be used on an on-line machine. It should be used very rarely, so the attacker has few chances to find the key in the clear where it could be stolen 🥷
Different entities will approach these requirements in different ways 🌸 A private individual making their own naming root key for this purpose has an edge: they're too small to attract a well funded attack, compared to what a commercial CA might face 🐣
7.5 One Root Per Individual
In the limit, you could have one highly protected naming root key per individual 💎 You could even have more than one key per individual, to frustrate attempts to build dossiers, but for the rest of this discussion, let's assume just one key.
If only one name descends from that key, you can drop the name entirely 🙈 Authorizations can go straight onto the key itself, in raw SPKI style, instead of onto some name defined under that key. Nothing is lost in terms of lifetime. Only the subject of the certificate the authorizing key uses to delegate authority changes 🔁
There is one big difference under the SPKI structure, though 👀 Say you delegate one authorization to
(name (hash sha1 |TLCgPLFlGTzgUbcaYLW8kGTEnUk=|) carl)and a different authorization directly to
(hash sha1 |TLCgPLFlGTzgUbcaYLW8kGTEnUk=|)and neither one grants the permission to delegate. That key can keep delegating at will through <name,key> certificates in the first case, but it can't delegate at all in the second case 🚫
For key management, we want to be able to delegate from a long lived, rarely used key to a shorter lived, often used key. So in this case, the first mechanism (through an SDSI name) gives way more freedom 🥰
7.6 Key Revocation Service
In either of the models above, key |TLCgPLFlGTzgUbcaYLW8kGTEnUk=| issues a certificate 📝 In the first model it's a <name,key> certificate. In the second it's an authorization certificate that delegates all rights through to the more temporary key.
Either of those certificates might want an online validity test. Whether that test is a CRL, a revalidation, or a one-time test, some entity that's online has to supply it 🌐
As the world moves toward having every machine online all the time, that entity might be the user's own machine 💻 But until then, and maybe even after, the user might want to hire a service to do this job 📞 That service could run a 24x7 manned desk to take phone calls reporting a lost key. That authority would not have the power to generate a new key for the user, only to revoke a current one 🙅♀️
If, in the worst case, a user loses their master key, the same process that happens today with lost wallets would apply 👛 All issuers of authorizations through that master key would need to issue new authorizations through the new master key. And if the old master key had been stolen, they'd also need to cancel all old authorizations made through it 🚨
7.7 Threshold ACL Subjects 🌟
Okay bestie, so the big question is how you keep root keys alive for ages 🔐. The fault-tolerance people have been saying it forever: truly long lifetimes only happen with redundancy and replacement. Both can be done with threshold subjects [section 6.3.3], especially inside ACL entries 🔥
If you swap a single key subject for a threshold subject in an ACL (or a certificate), you get redundancy right away ✨. And it's not only keys, it's algorithms too! The keys in a threshold subject don't need to use the same algorithm. Iconic 🦋
Truly long lifetimes come from replacement, not just redundancy. The second a component breaks (or a key is assumed compromised), it must be replaced 💀.
An ACL needs its own access control, ngl. That's the main character plot twist 🎀. Say the ACL has an entry with this authorization:
(tag (acl-edit))Now say what might have been one root authorization key, K1, is actually a threshold subject:
(k-of-n #03# #07# K1 K2 K3 K4 K5 K6 K7)used in any ACL entry that grants a normal authorization.
That same ACL could have the subject of its (acl-edit) entry be:
(k-of-n #05# #07# K1 K2 K3 K4 K5 K6 K7)This lets the set of root keys vote in new members and retire the old ones 🗳️👑. So replacement and redundancy happen together, and if you pick K and N the right way, threshold subject key lifetimes should approach infinity ♾️💖.
8. Security Considerations 🔮
Okay, this part is serious, so listen up 🚨. There are three classes of information that public key certificates can bind together: key, name and authorization. That means there are three general kinds of certificate, depending on which pair of items the certificate ties together. If you look at the direction of the mapping between items, there are six classes:
name->key
key->name
authorization->name
name->authorization
authorization->key
key->authorizationThe SPKI working group concluded that the most important use for certificates is access control 🔑. With all those possible mappings, there are at least two ways to implement access control. You can use a straight authorization certificate:
(authorization->key)or you can use an attribute certificate and an ID certificate:
(authorization->name) + (name->key)The first way is more secure than the second, and there are at least two reasons why 😤.
- Every certificate has an issuer. If that issuer gets subverted, the attacker can gain access. In the first case there is only one issuer to trust. In the second case there are two.
- In the second case, the certificates are linked by name. If the name space of the ID certificate's issuer is different from the name space of the attribute certificate's issuer, then one of the two issuers has to use a foreign name space. Picking the right name from a foreign name space is more complicated than string matching and might even involve a human guessing 🙈. That's a recipe for mistakes, and such a mistake can happen by accident or be guided by an attacker 💀.
This doesn't mean you must never use the second construct. If both certificates come from the same issuer, and therefore share the same name space, then both of the security differentiators above are canceled out ✨.
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.
[ELIEN] Jean-Emile Elien, "Certificate Discovery Using SPKI/SDSI
2.0 Certificates", Masters Thesis, MIT LCS, May 1998,
<http://theory.lcs.mit.edu/~cis/theses/elien-masters.ps>
[also .pdf and
[HARDY] Hardy, Norman, "THE KeyKOS Architecture", Operating
Systems Review, v.19 n.4, October 1985. pp 8-25.
[IDENT] Carl Ellison, "Establishing Identity Without
Certification Authorities", USENIX Security Symposium,
July 1996.
[IWG] McConnell and Appel, "Enabling Privacy, Commerce,
Security and Public Safety in the Global Information
Infrastructure", report of the Interagency Working Group
on Cryptography Policy, May 12, 1996; (quote from
paragraph 5 of the Introduction).
[KEYKOS] Bomberger, Alan, et al., "The KeyKOS(r) Nanokernel
Architecture", Proceedings of the USENIX Workshop on
Micro-Kernels and Other Kernel Architectures, USENIX
Association, April 1992. pp 95-112 (In addition, there
are KeyKOS papers on the net available through
<http://www.cis.upenn.edu/~KeyKOS/#bibliography>).
[KOHNFELDER] Kohnfelder, Loren M., "Towards a Practical Public-key
Cryptosystem", MIT S.B. Thesis, May. 1978.
[LAMPSON] B. Lampson, M. Abadi, M. Burrows, and E. Wobber,
"Authentication in distributed systems: Theory and
practice", ACM Trans. Computer Systems 10, 4 (Nov.
1992), pp 265-310.
[LANDAU] Landau, Charles, "Security in a Secure Capability-Based
System", Operating Systems Review, Oct 1989 pp 2-4.
[LEVY] Henry M. Levy, "Capability-Based Computer Systems",
Digital Press, 12 Crosby Dr., Bedford MA 01730, 1984.
[LINDEN] T. A. Linden, "Operating System Structures to Support
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", Work in
Progress.
[R98] R. Rivest, "Can We Eliminate Revocation Lists?", to
appear in the Proceedings of Financial Cryptography
1998, <http://theory.lcs.mit.edu/~rivest/revocation.ps>.
[RFC1114] Kent, S. and J. Linn, "Privacy Enhancement for Internet
Electronic Mail: Part II -- Certificate-Based Key
Management", RFC 1114, August 1989.
[RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC
1321, April 1992.
[RFC2045] Freed, N. and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part One: Format of Internet Message
Bodies", RFC 2045, December 1996.
[RFC2046] Freed, N. and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part Two: Media Types", RFC 2046,
December 1996.
[RFC2047] K. Moore, "MIME (Multipurpose Internet Mail Extensions)
Part Three: Message Header Extensions for Non-ASCII
Text", RFC 2047, December 1996.
[RFC2065] Eastlake, D. and C. Kaufman, "Proposed Standard for DNS
Security", RFC 2065, January 1997.
[RFC2104] Krawczyk, H., Bellare, M. and R. Canetti, "HMAC:
Keyed-Hashing for Message Authentication", RFC 2104,
February 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, 1991.
[UPKI] C. Ellison, "The nature of a useable PKI", Computer
Networks 31 (1999) pp. 823-830.
[WEBSTER] "Webster's Ninth New Collegiate Dictionary", Merriam-
Webster, Inc., 1991.Acknowledgments 🫶
Several independent contributions, published elsewhere on the net or in print, worked in synergy with our effort 🌈. The especially important ones were [SDSI], [BFL] and [RFC2065]. The inspiration we got from the notion of CAPABILITY in its various forms (SDS-940, Kerberos, DEC DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated 👑.
Huge thanks to the members of the SPKI mailing list, who made significant contributions to this effort. We're especially grateful to the following people, listed in alphabetic order 💜: 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
Intel Corporation
2111 NE 25th Ave M/S JF3-212
Hillsboro OR 97124-5961 USA
Phone: +1-503-264-2900
Fax: +1-503-264-6225
EMail: carl.m.ellison@intel.com
cme@alum.mit.edu
Web: http://www.pobox.com/~cme
Bill Frantz
Electric Communities
10101 De Anza Blvd.
Cupertino CA 95014
Phone: +1 408-342-9576
EMail: frantz@netcom.com
Butler Lampson
Microsoft
180 Lake View Ave
Cambridge MA 02138
Phone: +1 617-547-9580 (voice + FAX)
EMail: blampson@microsoft.com
Ron Rivest
Room 324, MIT Laboratory for Computer Science
545 Technology Square
Cambridge MA 02139
Phone: +1-617-253-5880
Fax: +1-617-258-9738
EMail: rivest@theory.lcs.mit.edu
Web: http://theory.lcs.mit.edu/~rivest
Brian Thomas
Southwestern Bell
One Bell Center, Room 34G3
St. Louis MO 63101 USA
Phone: +1 314-235-3141
Fax: +1 314-235-0162
EMail: bt0008@sbc.com
Tatu Ylonen
SSH Communications Security Ltd.
Tekniikantie 12
FIN-02150 ESPOO
Finland
EMail: ylo@ssh.fiFull Copyright Statement 💖
Okay bestie, this is the legal bit at the very end, so I'm keeping every word exactly as written. ✨
Copyright (C) The Internet Society (1999). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement 🫶
Last bit! 🌸 The RFC Editor function is funded right now by the Internet Society, so a big thank-you to them.
Funding for the RFC Editor function is currently provided by the Internet Society.
📦 where this page comes from
- ietf: rfc2693 1999-09
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms