SPKI Certificate Theory Carl M. Ellison
INTERNET-DRAFT CyberCash, Inc.
Expires: 26 May 1998
Bill Frantz
Electric Communities
Butler Lampson
Microsoft
Ron Rivest
MIT Laboratory for Computer Science
Brian M. Thomas
Southwestern Bell
Tatu Ylonen
SSH
21 November 1997
SPKI Certificate Theory
---- ----------- ------
Status of This Document
This document is one of three, superseding the draft filed under the
name draft-ietf-spki-cert-structure-02.txt. This draft contains the
discussion and background from that previous draft. The structure
definition is to be found in draft-ietf-spki-cert-structure-03.txt
and examples of certificate uses are to be found in draft-ieft-spki-
cert-examples-01.txt.
Distribution of this document is unlimited. Comments should be sent
to the SPKI (Simple Public Key Infrastructure) Working Group mailing
list <spki@c2.org> or to the authors.
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
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 21 November 1997
To learn the current status of any Internet-Draft, please check the
1id-abstracts.txt listing contained in the Internet-Drafts Shadow
Directories on ds.internic.net (East USA), ftp.isi.edu (West USA),
nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe),
munnari.oz.au (Pacific Rim), or ftp.is.co.za (Africa).
Ellison, et al. [Page 2]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
Abstract
The SPKI Working Group has developed a standard form of digital
certificate that is both more general and simpler than what is
traditionally considered to be a certificate. Since the word
''certificate'' was first used by Loren Kohnfelder in 1978 to refer to
a signed record holding a name and a public key, it has been assumed
that the only purpose of a certificate has been to bind a public key
to a globally unique name and therefore to a person. This binding
was assumed both necessary and sufficient for security.
The working group has found that the creation of a globally unique
name is neither necessary nor sufficient for Internet security or
electronic commerce. In fact, use of global names can introduce a
security flaw. Therefore, we define certificate forms for binding
local names to keys (to retain security while offering the
convenience of meaningful names) and for assigning authorizations to
keys (to provide adequate information for real applications). These
forms can be used alone or together.
Acknowledgments
Several independent contributions, published elsewhere on the net or
in print, worked in synergy with our effort. Especially important to
our work were: [SDSI], [BFL] and [RFC2065]. The inspiration we
received from the notion of CAPABILITY in its various forms (SDS-940,
Kerberos, DEC DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated.
Significant contributions to this effort by the members of the SPKI
mailing list and especially the following persons (listed in
alphabetic order) are gratefully acknowledged: Steve Bellovin, Mark
Feldman, John Gilmore, Phill Hallam-Baker, Bob Jueneman, David Kemp,
Angelos D. Keromytis, Paul Lambert, Jon Lasser, Jeff Parrett, Bill
Sommerfeld, Simon Spero.
Ellison, et al. [Page 3]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
Table of Contents
Status of This Document....................................1
Abstract...................................................3
Acknowledgments............................................3
Table of Contents..........................................4
1. Overview of Contents....................................5
2. Scope Of This Effort....................................6
2.1 Charter of the SPKI group..............................6
2.2 Areas Covered And Not Covered..........................6
2.2.1 Key and certificate storage..........................7
2.2.2 Protocols to use public key authentication...........8
2.3 Other Certificate Formats..............................8
2.4 Goals of this effort...................................8
2.5 SPKI Certificates vs. Capabilities.....................9
2.6 Chosen standard format.................................9
3. Assumptions, Definitions and Design Issues.............11
3.1 Background............................................11
3.2 Definition of PRINCIPAL and KEYHOLDER.................13
3.2.1 Protection of Private Keys..........................15
3.3 Certificate Structure.................................16
3.3.1 5-tuple Reduction (introduction)....................17
3.3.2 Authority Loops.....................................18
3.3.3 Certificate Result Certificates.....................18
3.4 Relation to PolicyMaker...............................19
3.5 Namespaces and Identity Certificates..................20
3.5.1 X.500 and X.509.....................................20
3.5.2 Death of global identity certification..............21
3.5.3 SDSI 1.0 Namespaces.................................21
3.5.4 Mappings within cyberspace..........................22
3.5.5 Mappings to (keyholder K1)..........................22
3.5.5.1 Donation Certificates.............................22
3.5.5.2 Locator Certificates..............................23
3.6 Certificate validity periods..........................23
3.7 Unwanted Attributions.................................24
3.8 Blind Signatures......................................25
3.9 Determinism...........................................25
References................................................27
Authors' Addresses........................................29
Expiration and File Name..................................30
Ellison, et al. [Page 4]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
1. Overview of Contents
This document contains the following sections:
Section 2 describes the scope of both the SPKI working group and this
particular Internet Draft.
Section 3 gives necessary background for understanding the SPKI
certificate structure. It details assumptions, definitions and
design issues behind this structure design and is recommended reading
for anyone who did not follow the discussion on the working group
mailing list.
The References section lists all documents referred to in the text as
well as readings which might be of interest to anyone reading on this
topic.
The Authors' Addresses section gives the addresses, telephone numbers
and e-mail addresses of the authors.
Ellison, et al. [Page 5]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
2. Scope Of This Effort
The SPKI certificate form reflects a change in point of view thanks
to the Internet. Older certificate efforts assumed that all
relationships and all granting of permission occurred in 3D space
among people who knew each other. A global name was assumed to be
needed to refer to these persons, and all certificate operations
referred back to 3D space via those names. The SPKI effort
recognizes that a growing number of relationships form in cyberspace,
among people who have never met and maybe never will. Even for
relationships among people who have met, SPKI recognizes that the
certificate verifying mechanism cares as little about an entity's
name as does an ATM or POS terminal. SPKI certificate forms
therefore refer to the 3D world entity only if something is being
said about that entity (cf., (keyholder K)). If that entity's key is
being empowered by a certificate, the key is referred to directly (or
indirectly via some local name for the key, defined and used as a
convenience to the issuer).
2.1 Charter of the SPKI group
Many Internet protocols and applications which use the Internet
employ public key technology for security purposes and require a
public key infrastructure to manage public keys.
The task of the working group will be to develop Internet standards
for an IETF sponsored public key certificate format, associated
signature and other formats, and key acquisition protocols. The key
certificate format and associated protocols are to be simple to
understand, implement, and use. For purposes of the working group,
the resulting formats and protocols are to be known as the Simple
Public Key Infrastructure, or SPKI.
The SPKI is intended to provide mechanisms to support security in a
wide range of Internet applications, including IPSEC protocols,
encrypted electronic mail and WWW documents, payment protocols, and
any other application which will require the use of public key
certificates and the ability to access them. It is intended that the
Simple Public Key Infrastructure will support a range of trust
models.
2.2 Areas Covered And Not Covered
To this point, the working group has been concerned only with
certificate, hash, key and signature formats, using the certificates
defined here both for verification of identity and for proof of
Ellison, et al. [Page 6]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
authorization. We have not covered the other elements of a full
public key infrastructure (PKI): key/certificate storage and
acquisition. We also do not cover all the applications or protocols
which must be modified to employ public key authentication or
privacy.
2.2.1 Key and certificate storage
There are several independent efforts at this time to provide a
database of keys or certificates for the Internet.
The DNS Security Working Group draft [RFC2065], specifies an
efficient key storage and distribution mechanism. It may be possible
to store an SPKI certificate in a KEY Resource Record (RR) or to
create a new RR type for SPKI certificates, under the DNSSEC design,
but that effort has not been undertaken yet.
The PGP key server at MIT operating both as a web page and as an e-
mail driven service provides another example of efficient certificate
storage and retrieval for the net at large. The custom key server
run by PGP, Inc., provides another possibility.
SDSI 1.0 demonstrated certificate servers for individuals to run on
their own net-connected workstations, in response to the fact that
more and more individuals remain connected to the network
permanently. We may see a similar effort establishing SDSI/SPKI
certificate servers.
On the other hand, there are those who view certificate servers as a
violation of privacy. A standard phenomenon in dealing with
classified documents is called "data aggregation". That is, two data
A and B may, by themselves, be unclassified, but if both were to be
known by one person, the combination would be considered classified.
The same might apply to the authorizations granted by certificates to
a given keyholder. Along similar lines, many corporations consider
their employee telephone lists confidential and are unlikely to host
a certificate server which gives the equivalent information to the
net.
The common practice which has evolved is that of the requestor
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 requestor (possibly under access
control) rather than the verifier.
Ellison, et al. [Page 7]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
2.2.2 Protocols to use public key authentication
Proposals for modification of applications to employ public key
authentication are proceeding independently, e.g., [PKLOGIN]. We
encourage other developers to actively enter this area of design,
aided by SPKI certificates as a tool. Others, such as TLS and SSH
already use public key authentication and are considering use of SPKI
certificates for communicating the permission required to achieve the
desired access.
2.3 Other Certificate Formats
We are aware of a number of actual and proposed kinds of signed
records which, by some definition, qualify as certificates:
1. PGP signed keys
2. X.509 identity certificates, from a number of sources
3. X.509 SET (Secure Electronic Transaction) certificates
4. DNS Security Extension signed keys
5. Signed PICS labels (from the W3C DSig effort)
It is not our intention to coerce these other certificate formats
into our mold, although they are welcome to switch over. The
certificate structure defined below is flexible enough to accommodate
all of the above.
However, we recognize that a real world system will involve some
mixture of SPKI and non-SPKI certificates as well as traditional
Access Control Lists (ACLs). Our design accommodates these by
allowing them to be mapped to 5-tuples and therefore to participate
in trust computations. Once one has reduced a possibly mixed set of
certificates into a partial or final result 5-tuple, that 5-tuple can
be signed to form a Certificate Result Certificate. This operation
can be done in all verifiers or can be done in an enterprise-wide
server reducing varied certificate forms to one simple, SPKI form.
2.4 Goals of this effort
In keeping with the design goals enumerated in section 3 of RFC1958,
it is our goal to keep the SPKI certificate pruned to the minimum
information necessary to accomplish the job at hand -- which is
Ellison, et al. [Page 8]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
secure authentication and authorization of access control and
confidentiality for the Internet. We use well tested formats with a
long history of success and have chosen those which require the bare
minimum of tool software so that applications remain as small and
efficient as possible. We desire to offer the bare minimum of
options, in order to reduce program size and complexity.
We also recognize that some kinds of certification (such as notarized
identity certification) can carry risks of invasion of privacy for
the individual. We have therefore designed these certificates to
reveal the minimum information necessary to get the job done,
whatever that job happens to be. In many cases, the user can remain
anonymous in the traditional sense while exercising strongly verified
authorization. That is, the user can be identified by his public key
alone.
2.5 SPKI Certificates vs. Capabilities
An SPKI certificate is closer to a "capability" as defined by
[HARDY], [KEYKOS], [LANDAU], [SRC-070], etc., than to an identity
certificate. There is the difference that in a capability system,
the capability itself is a secret ticket, the possession of which
grants some authority. It is anonymous (more like cash than a
check). Therefore, if you grant authority to read a capability, you
have delegated the ability to use it. An SPKI certificate identifies
the specific key to which it grants authority and therefore the mere
ability to read (or copy) the certificate grants no authority and the
certificate itself does not need to be as tightly controlled.
Rather, control over the corresponding private signature key must be
tightly controlled.
With SPKI certificates, one can delegate authority (all or part of
the authority one has been delegated) to a different key, without
sharing the quantity which must be kept secret (the private key) --
as opposed to a capability which is kept secret except when it is
shared for the purpose of delegation.
2.6 Chosen standard format
In this draft, the standard format adopted is that developed by SDSI,
modified slightly. Data objects are defined as S-expressions --
lists in which the first element is a token defining the data object.
Rather than permit the full generality of S-expressions, we define a
canonical format and accept only that form. Software is available to
translate between the canonical format and a presentation format.
Ellison, et al. [Page 9]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
This document presents the canonical format, but uses a presentation
format for examples since the canonical format is binary and can not
easily be transmitted in a text document.
Ellison, et al. [Page 10]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
3. Assumptions, Definitions and Design Issues
There were a number of discussion topics involved in the design of
SPKI certificates and we summarize them here for the reader who was
not part of the SPKI discussion. This section should at least be
skimmed by even the reader with a solid grounding in classical
(identity) certification. Some of these might be new concepts. Some
provide definitions for terms which traditional discussions of
certification frequently leave undefined.
Throughout this document, we refer to two parties engaged in
certificate use: the prover and the verifier.
By PROVER, we mean the entity which wishes access or digitally
signs a document. We assume that the prover assembles all
certificates necessary for use by the verifier, and puts those
into order for the verifier. The prover is software but could
be interacting with a human user.
By VERIFIER, we mean an entity which processes certificates,
together with its own ACL entries, to determine if the prover
deserves access or if some signed document is valid. The
verifier is most likely unattended software.
3.1 Background
In the words of [LAMPSON], a public signature key "speaks for" its
owner: a person or entity we call the "keyholder". It is primarily
through such public key "speech" that one achieves security on the
inherently anonymous and spoof-able Internet. In a sense, the public
key is a proxy for or projection of a person in cyberspace.
Older certificate forms endeavoured to bind public keys to the "true
names" of their keyholders, in an attempt to identify the keyholder
and to permit the transfer of permissions or other attributes from
the physical world in which the keyholder lives into the digital
world. It was assumed that all relationships were formed in the 3D
world and needed to be mapped into cyberspace.
This effort has produced so-called "identity certificates", such as
X.509 certificates or PGP signed keys, giving <name,key> bindings
which needed to be combined with certificates or ACL entries of the
form <tag,name>, to yield the relationship <tag,key> which a computer
then uses to verify public-key driven access attempts. {<tag> here
stands for authorization, permission, etc.}
That effort is motivated by a long standing human habit that grew out
of life in small communities and is replayed for each individual by
Ellison, et al. [Page 11]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
his development inside a family. [This is a slightly abstract
example of the classic observation that ontogeny recapitulates
phylogeny.]
Human beings are driven to use names for persons. We remember
characteristics of a person (his or her identity, as far as we know
it) but we label those memories with a name for the person. In a
small community, names are unique. If they are not unique, we force
them to be, so that they are useable as identifiers. E.g., the
Ellison family had Little Carl and Big Carl.
So, we learn early (as a species and as individuals) that we can
assume
name = person
Small communities have another characteristic: no privacy. A T-shirt
for sale in a small town in Michigan sums this up with the caption:
"Small Town (def) A place where you don't have to use your turn
signals because everyone knows where you are going".
This leads us to extend our assumption to:
name = person = characteristics
By one dictionary definition of the word, "identity" is the defining
characteristics of an individual. This extends the assumption to:
name = person = characteristics = identity
When the small community is closed as well, as it is at first, we
learn that Alice can talk to Bob about Carol and know that Bob is
thinking of the same Carol Alice is. That is, we can use names to
refer to persons in speaking to other persons.
From this chain of reasoning, in this set of circumstances, it is
perfectly reasonable to build a certificate that binds a name to a
key and call it an "Identity Certificate" and assume that one can
transmit it to a third person and have it be meaningful to that
person.
The trouble with this line of reasoning is that we do not live in
small communities. As a species, we stopped that with the rise of
cities and especially with the industrial revolution. As
individuals, we leave our early families and enter the larger world.
In the 1990's, we enter that larger world via the Internet even
before we leave our families.
In this larger world, it is no longer true that a person's name is a
valid identifier. One response to this fact has been the effort to
create globally unique names, with a common name as a portion. That
can be done, of course, but for a name to be meaningful to a user it
must be held in the mind of the user and humans have a limited
Ellison, et al. [Page 12]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
capacity for remembering names. A person who can remember thousands
of names is considered unusual, if not a freak.
The global community is closed and therefore it should be
theoretically possible to use global names for introduction and
reference purposes. That is, Alice can tell Bob about Carol. For
this to be meaningful, however, Alice has some memory of Carol and
wants to make sure that when she tells Bob about Carol, he accesses
his memories of the same person. This process breaks down in two
ways, when one uses global names. First, there are so many global
names that Bob is unlikely to have Carol's global name in his memory.
[If global names are long enough, Bob is unlikely to have his own
global name in his memory.] Second, if Bob has never met Carol, he
has no body of memories to tie that name to. The process then
becomes an empty ritual, reflecting something that had meaning under
different circumstances but that has lost its meaning.
Meanwhile, one basic premise of the older certificate formats was
that relationships were formed in the 3D world and needed to be
mapped into cyberspace. Instead, we see relationships increasingly
form in cyberspace. Therefore, a mechanism that maps attributes from
the physical world to the digital world is increasingly less
appropriate while a mechanism that transfers attributes within the
digital world is vital and one that transfers attributes from the
digital world to the physical world is likely to be needed very soon,
if not immediately.
We have also observed that <key> is a perfectly adequate name for a
keyholder, at least as far as a computer is concerned. It and its
hash have the advantage of being unique while each portion of it (and
especially of its hash) is uniformly distributed and therefore of
particular value as an index into a database. It is also tied the
most strongly of any identifying string to the keyholder. We have
therefore defined a certificate which communicates <tag,key>
directly, leaving names out of the process except in the case where
the name is the item of interest (e.g., for secure e-mail).
We have also observed that a global name (e.g., Distinguished Name)
that includes a person's common name as a substring is a security
flaw. That is because it induces humans (scanning a database or
cache of certificates, for example) to guess the connection between a
global name and the person they have in mind. This introduction of a
human guess in a security protocol dwarfs other security risks.
3.2 Definition of PRINCIPAL and KEYHOLDER
The most important issue is the notion of a key as a principal and
the difference between that key and the person or machine which owns
Ellison, et al. [Page 13]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
and controls it.
By PRINCIPAL, we mean a signature key. That is, a principal is
capable of "speaking" in cyberspace by signing messages. We
also permit use of the secure hash of a signature key as a
principal, in an effort to save space in data structures which
use principals.
By KEYHOLDER, we mean an entity in the 3-D world which controls
a given (private) signature key. The keyholder is identified
primarily by the public verification key which corresponds to
the private signature key.
By definition, the keyholder has sole possession of the private key.
That private key could be used as the identifier of the keyholder --
as a name -- except the private key must be kept secret. There is
only one private key to match a given public key, so the keyholder
can be identified by the public key just as uniquely. Similarly,
there is only one public key which hashes to a given secure hash (by
definition of "secure hash", assuming we are limited in computation
power), so the secure hash of a public key can also be used to
identify the keyholder. If we are using symmetric (secret) signature
keys, the hash of that key can still serve as a name for the key and
for its keyholder(s).
We identify a PRINCIPAL by either a key or a secure hash of a key.
There is pressure, in the interest of simplicity, to restrict
PRINCIPAL to just a key. However, if one is using a shared secret
key (e.g., for HMAC or some symmetric algorithm like DES-MAC), it is
essential to keep the key secret and use of a hash permits that. It
is also possible to have shared secret public keys -- e.g., RSA
public keys of short moduli (for performance reasons) -- which must
not be published because the key can be broken, but for which the
hash of the key can be published without fear of compromise.
We identify a KEYHOLDER by the construct "(keyholder <principal>)" --
using the principal as the name of the private key and therefore the
keyholder, but explicitly noting that we refer to the keyholder in
physical space rather than the key in cyberspace.
Without certificates, we might not know anything else about the
keyholder (such as name, gender or even if the keyholder is a living
being) but we do know enough to link together separate messages from
the same keyholder. For some purposes, that is sufficient
identification (for example, when a person is first encountered on-
line via signed messages and there is no intention of linking that
person to any physical being, only to his or her own other messages).
Ellison, et al. [Page 14]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
However, there are other applications for which the ability to link
together separate messages from an anonymous source is not adequate
and therefore for which certificates are required.
3.2.1 Protection of Private Keys
For any public key cryptosystem to work, it is essential that a
keyholder keep its private key to itself. In the case of a human
being, this might involve keeping the private key encrypted under a
high-entropy passphrase and storing it only on the person's own
personal computer or floppy disks. Some humans might even keep the
private key in a tamper-resistant PCMCIA card or Smart-Card which
will never release it and will in fact destroy it after too many
failed attempts to gain access. In the case of a network node, this
might involve keeping the private key in a tamper-resistant
cryptographic processor which generated it and which will destroy it
if tampering is attempted.
If the keyholder does not keep the private key protected (that is, if
the private key gets out to others to use) then one can not know what
entity is using that key and no certificate will be able to restore
the resulting broken security.
Therefore, we are forced to assume that all private keys are kept
private and bound tightly to the one keyholder to which they belong.
We will have to provide for methods of announcing the compromise of
such private keys whenever this assumption proves false, but we must
assume that unless such notification is delivered, each private key
is secure and attached to its owner.
Note: We have specifically included a process for one keyholder
who has been granted some authority to delegate that authority
to another, in order to reduce if not eliminate the motivation
for one keyholder to loan a private key to another.
So to reiterate, we do not expect every person, process and device in
the Internet to employ true tamper resistance. Many people will keep
and use private keys on an insecure personal computer or workstation.
However, we are forced to assume protection of the private key or
give up any notion of cryptographically strong authentication and
authorization. Work is progressing on decreasing the cost of true
tamper-resistance but until it is ubiquitous, we must accept a
Ellison, et al. [Page 15]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
certain amount of risk from copied or stolen private keys. Even
then, there is risk from coerced use of one's private key.
3.3 Certificate Structure
An SPKI certificate body has several fields, five of which are
relevant for security purposes:
ISSUER: a principal or a single, top-level name in a principal's
namespace. The principal is identified as a public key or the
hash of that key and the corresponding private key signs the
certificate.
SUBJECT: a principal, an object or a SDSI name reducible to either of
those. The subject is that which receives authority from the
issuer by way of the certificate.
DELEGATION: the optional modifier, "(propagate)", giving the subject
permission to delegate the authority presented in the
certificate (or part of it) to some other Subject. This is
represented as the delegation boolean, D, in the discussion
below. The two boolean states are (F: delegate only through
name declarations -- also known as "stop at key") and (T:
delegate to the subject).
AUTHORITY: the specific authorization(s) being delegated in this
certificate. These fields, of the form "(tag ...)", are to be
defined by those who have resources to control and describe
resource allocations. This document gives some examples for
such fields which are expected to be in common use, but more
importantly it gives the structure for <tag> fields and the
description of a standard process for manipulating them which is
expected to be implemented in all code conforming to this
standard.
VALIDITY: date ranges and/or online validity tests for determining
certificate validity.
A certificate is signed by its issuer. Section 6 gives details about
signature blocks.
The five security-relevant fields described above are termed a "5-
tuple" for lack of a better word, in the discussion below. The
assumption is that a certificate's signature will be checked to yield
the 5-tuple which, in turn, will be kept in trusted memory and will
participate in trust management decisions. Objects other than
Ellison, et al. [Page 16]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
certificates (such as ACL entries) can also yield 5-tuples which
participate in trust management decisions.
Informally, the meaning of the certificate is "The issuer says that
the subject has the stated authority during the validity period".
Another way of saying this is "The issuer says that the subject may
speak for the issuer with the stated authority during the validity
period." If the issuer issues several such certificates for
different subjects, then it is defining a group of subjects, each of
which can speak for it.
If the subject is an object that is not reducible to a principal, it
can't do any speaking; in this case the meaning is "The issuer says
that the subject has the properties stated by the 'authority'."
3.3.1 5-tuple Reduction (introduction)
A certificate which is received to be part of a verification process
has its signature checked. One whose signature checks is considered
valid. Other kinds of authorization statement (most specifically ACL
entries) can be considered valid without a signature check.
A valid authorization statement can be represented by five
quantities:
(I,S,D,A,V)
A set of simple 5-tuples can be reduced as follows:
(I1,S1,D1,A1,V1) + (I2,S2,D2,A2,V2)
becoming
(I1,S2,D2,A,V)
if S1=I2 (meaning that they are the same public key)
and (D1 = TRUE) or (S1 is a SDSI name)
and A = intersection(A1,A2)
and V = intersection(V1,V2)
The actual process is slightly more complicated when I2 is of the
form
(issuer (name K3 nnn))
or when S1 is of the form
(subject (threshold K N (s1) (s2) ... (sN)))
Ellison, et al. [Page 17]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
Rules for those cases are given below in section 10, presenting the
full tuple reduction logic, but for the discussion to follow the
logic given above will suffice.
3.3.2 Authority Loops
By 5-tuple reduction, some chains of authorization statements will be
reduced to the form:
(Self,X,D,A,V)
where "Self" represents the entity doing the verification, granting
access, etc. Such a 5-tuple says "Self says (I say) that X has
authority (D,A) for validity period (or conditions) V". In other
words, Self has decided what it can trust about X
Any authorization chain not reducing to a 5-tuple with Self as issuer
isn't relevant to decisions by Self.
Therefore, any authorization chain which is to be used by Self to do
trust management must have Self as a root. Since Self is doing this
chain reduction and is therefore at the receiving end of the chain as
well, that makes all useful authorization chains loops.
3.3.3 Certificate Result Certificates
In cases where the verifier, Self, has access to a private key, once
it has reduced a chain of certificate bodies down to the form:
(Self,X,D,A,V)
it can sign that generated body, using its private key, producing an
SPKI certificate. That certificate will have a validity period no
larger that of any certificate in the loop which formed it, but
during that validity period it can be used by the prover instead of
the full chain, when speaking to that particular verifier. It is
good only at that verifier (or at another which trusts that verifier,
Self, to delegate the authorization A). Therefore, one option by the
verifier is to sign and return the result 5-tuple to the caller for
this later use.
If it isn't important for any other verifier to accept this "result
certificate", it can even be signed by a symmetric key (an HMAC with
secret key private to the verifier).
The certificates which made up the loop forming this result 5-tuple
Ellison, et al. [Page 18]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
could have been of any variety, including X.509v1, X.509v3, SET or
DNSSEC. They could also be PGP signed keys processed by an enriched
trust engine (one capable of dealing with the PGP web of trust
rules). If the verifier, Self, were to be trusted to delegate the
resulting authorization, its certificate result certificate then
becomes a mapping of these other forms. This may prove especially
useful if a given certificate chain includes multiple forms or if the
result certificate is to be used by a computationally limited device
(such as a Smart-Card) which can not afford the code space to process
some of the more complex certificate formats.
3.4 Relation to PolicyMaker
The section above introduced the possibility of a machine which
reduces a set of certificates, possibly a very complex one, and
yields a single certificate as a result. That single certificate
would be simpler and faster to verify. It might even stand alone in
granting access.
That machine reducing the set of certificates to a single result
might even execute a policy program which could be too complex to be
expressed in terms of SPKI 5-tuple reduction. The policy machine
would still have to have its own ACL entries, declaring the keys it
trusts as "roots" for various purposes and, in this hypothetical
case, a signature key, P. It would execute its policy program on the
credentials provided by the caller, come up with either a failure or
a certificate result, signed by P, and deliver that result to the
caller.
In the manner of [BFL] we note that one can take the same code
executed by that policy processing machine and digitally sign the
code -- then digitally sign the ACL entries for its "roots" (turning
them into certificates, issued by P) -- and ship the code plus
certificates to the caller, presumably a verifying computer. That
verifying computer could then run the policy code on P's behalf,
getting either a failure or a 5-tuple. It can't sign the 5-tuple
turning it into a certificate issued by P, because it would not have
P's private key -- but it doesn't need a certificate. It needs only
the trusted 5-tuple.
[BFL] introduces a language called Policymaker in which one can
express security policy statements. It is possible for Policymaker
to be used along with SPKI certificates in two ways:
1) It is believed possible to use Policymaker's language to implement
the standard SPKI 5-tuple reduction. The code has not been
written as of the time of this draft, but at this point it looks
possible.
Ellison, et al. [Page 19]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
2) For any trust policy which the full SPKI 5-tuple reduction can not
express, one must write a policy interpretation program and
Policymaker provides a language and body of examples for that
purpose. The result of the Policymaker execution can be a 5-tuple
to be used within an SPKI reduction.
3.5 Namespaces and Identity Certificates
Since the word "certificate" was first used by Kohnfelder in 1978 to
refer to a digitally signed binding between a name and a public key,
people have assumed that a certificate binds a name to a key.
For most of human history, people lived in relatively small, closed
communities. It was common in such a community for each member to
have his or her own unique name. Everyone in the community would
know everyone else in the community by that name. It was also
extremely unlikely for someone in such a small community to change
his or her name (except through marriage). The habit naturally
developed of thinking of a person's name as a unique and permanent
identifier, in a way synonymous with his or her identity.
Although such small communities have become unusual for the majority
of people today, the association between name and identity persists
in human thinking. Even today, a certificate which binds a name to a
key is often called an "identity certificate".
3.5.1 X.500 and X.509
At one time, it was assumed that there would be a worldwide directory
of names of people (and computers and other things), called X.500,
and there was a data structure defined, called X.509, to bind public
keys to portions of the X.500 hierarchy. The original purpose of
such certificates was to record who (which keyholder, ie., which key)
had permission to modify that portion of the distributed X.500
database.
At some point, it became apparent that X.500 was never going to occur
as a global directory. Among other things, corporations which were
to own and manage substantial sub-trees of the directory consider
their employee directories company confidential. The same applies to
some government agencies.
The fact that an X.500 node's address was a person's unique name (so-
called "distinguished name"), led people to view X.509 apart from its
purpose of controlling access to X.500 databases and instead treat it
Ellison, et al. [Page 20]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
as an identity certificate.
3.5.2 Death of global identity certification
Even if a global X.500 directory had occurred, global identity
certification would have died. The problem is one of the
unanticipated consequences of the Internet.
The purpose of an identity certificate is to map from the 3D space of
people to cyberspace, particularly to the space of public signature
keys.
This mapping takes two steps: from 3D space to a name space; from the
name space to key space. The latter step is accomplished by a
certificate (e.g., X.509). The former step is assumed, in the
X.500/X.509 case, to be common knowledge. The larger that name
space, the less likely that anyone would know the name of a specific
individual. Alice might suspect that her old friend Bob Smith has a
name in the global X.500 directory, but there are so many people
named Bob Smith in the world that it is unlikely Alice would know
which of the thousands of Bob Smiths was in fact her old friend.
The problem is that, like the telephone directory which inspired this
model of certification, the directory never claimed to record
information of interest to each user (e.g., Alice's old friend). In
fact, a directory which did so would almost certainly be viewed as a
violation of privacy on a massive scale and would be shut down.
3.5.3 SDSI 1.0 Namespaces
SDSI 1.0 [SDSI] solved this problem inherent in global name spaces by
ignoring the fantasy of a global name space and replacing it with
local name spaces, one for each principal (= signing key).
Principals may share name spaces as will be seen later, but in theory
each principal has its own name space.
The certificate mapping from name to key (SDSI, in this case) is just
as secure as the X.509 certificate mapping from the global name space
to a key, but the link from 3D space to name is considerably more
secure -- because it is a link defined by the user. Alice's old
friend Bob Smith might be named "Red" in her name space, for example.
Her name for him is not intended to be of any use to anyone else --
only to her. Such a local name space is already familiar to some
users of mail agents, under the label "nickname" or "alias".
Ellison, et al. [Page 21]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
3.5.4 Mappings within cyberspace
Identity certificates with their presumed ability to map from 3D
space to key space were assumed to be necessary "so that you know
with whom you are dealing in cyberspace". The assumption behind such
a thought is that a relationship is formed in 3D space between people
and that relationship needs to be mapped into cyberspace.
Unanticipated by the original designers of identity certificates was
the fact that the Internet brought with it the formation of
relationships in cyberspace. In such cases, there is no relationship
in 3D space to be mapped and therefore no need for identity
certificates.
There is, however, a need for certificates within cyberspace -- to
grant privileges, access rights, etc. -- from one cyberspace
principal to another (from one key to another). It was for this
situation that the original SPKI was designed.
3.5.5 Mappings to (keyholder K1)
Also not anticipated by the pre-Internet developers of identity
certificates was that relationships which formed online might need to
be mapped occasionally back to the 3D world. Those early designers
of certificates might have assumed that the binding between name
("identity") and key was bi-directional, but it was not. It mapped
name to key. The mapping from key to name is not satisfied by a
single approach. In particular, there can be no single issuer for
such a certificate, suitable for all purposes. Two such certificates
are described below but there are probably several varieties.
3.5.5.1 Donation Certificates
Situation: you meet someone (who uses key K1) online, are impressed
with his work and decide to hire him. You make an offer. He
accepts. He starts working for you and you like his work (all signed
by K1). You now need to send him a paycheck. So, you need a name to
put on the paycheck and you need a postal address to mail it to (and
maybe a phone number, if you are using Fed Ex).
This sounds like a traditional identity certificate, but it isn't.
There is no CA in this case. The one key you can trust the most to
sign this certificate is K1. It belongs to the individual with the
most to gain by providing correct information. In X.509-style
certification, one would never use a self-signed certificate.
Ellison, et al. [Page 22]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
3.5.5.2 Locator Certificates
Situation: you meet someone (who uses key K1) online, are impressed
with his work and decide to hire him to do some protracted project.
You make an offer. He accepts. You need the work done and done
right. Failure to have the work done would be very harmful to you.
For that you write a contract which he signs with K1 and the contract
includes penalty clauses. In the event of his failure to perform,
you need to know that you can get redress through the legal system.
One way is to have his name and home address so that you could serve
legal papers on him should he default on the contract.
The certificate which lets you serve papers on Keyholder(K1) sounds
even more like a traditional identity certificate, but it isn't.
Neither is it a donation certificate, since this one should not be
signed by K1. Instead, it should be signed by Kp -- the key of a
company which does process serving. That company, Acme Process
Servers, however, would rather not have a name and address in the
certificate. Instead, Acme would prefer to have a simple sequence
number in the certificate, indexing Acme's own files on the person.
This forces you to use Acme to do the process serving, doubtless for
an additional fee, in the event that you do sue.
Meanwhile, you would prefer to have this certificate over an identity
certificate issued by the Post Office, listing the person's name and
address. The name and address certificate reflects facts at the time
of the start of the contract, not facts at the time legal papers need
to be served. It may take substantial investigative work to get from
the former to the latter. That is the work Acme would do for a
living and it would be for that work that Acme would charge both for
the initial certificate and for the act of serving papers on the
keyholder of K1. Acme might perform this work at time of default or
keep tabs on Keyholder(K1) during the life of the contract. That
would be Acme's choice.
3.6 Certificate validity periods
Our experience with credit cards has influenced the way we consider
validity periods of certificates.
A credit card is issued with an expiration date 1 to 3 years later
than the date of issue, yet one can revoke a credit card and have
that revocation be effective within a day of the request. That
credit card has a validity period of one day (or less) in spite of
its expiration date.
At one time, credit card validity was verified at a checkout counter
by looking the card number up in a book of revoked cards. The
Ellison, et al. [Page 23]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
validity period of a card not listed in such a book was the time
until that book was updated and the card had to be looked up again.
This practice has migrated into the digital world through the CRL
(Certificate Revocation List) construct.
Modern systems accepting credit cards perform an on-line validity
check, in which case the validity period can be very short and is
determined by the time it takes to make a database update from a
report of a lost or stolen card.
SPKI certificates may use one or both of two kinds of validity
period: a date range (akin to expiration dates) or an on-line check.
The on-line check will return information about the certificate's
validity and that information itself will have an expiration date and
time. The certificate together with its latest on-line test result
would then yield a valid assignment of authorization, with validity
period which is the intersection of the dates of the two data items
(usually just the date range of the on-line test result).
There are three forms of on-line test result defined:
CRL
a list of certificates known to be revoked since a certain time.
Periodic revalidation
a new assured validity date for the certificate being tested.
One-time revalidation
a statement that for this one transaction, the indicated
certificate is valid. [This is as close as we can come to a 0-
length validity period revalidation.] The one-time revalidation
can also have side effects -- e.g., refer to a bank balance.
3.7 Unwanted Attributions
There is a potential problem that a certificate might be issued which
the keyholder does not want.
For example, someone with the power to issue access certificates
wishes to make trouble for you. That person generates a cert for
you, giving you access to their company's file system. Someone
breaks into that file system and does damage, also wiping out the
audit logs of who broke in. So, the police ask the age-old Perry
Mason question: who had keys to that door? Your cert (even though
you never saw it) is a key to that door. It might even be the only
cert with the capability to do what was done, at least according to
the company records. That makes you a suspect. If for other reasons
Ellison, et al. [Page 24]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
you might be even the most logical suspect, then you might make it to
the top of the police list and get severely hassled.
For another example, a keyholder, Alice, has a signature key, K,
being used to sign digital lab notebooks for later use in patent
applications. That key is certified as hers by her company through
an SPKI identity certificate with an EMPLOYEE <tag> field.
Bob learns Alice's public key and builds a certificate using his own
name and her key, getting it signed by some reputable commercial CA.
Now when it comes time to dispute prior art on Alice's patent(s), Bob
produces his certificate and claims that Alice had not only copied
his work but stolen his private signature key.
Although we do not mandate such practice at this time, some
certificates could be signed by the <subject> as well as by the
<issuer> in order to make sure that the <subject> really does have
access to the indicated private key. Alternatively, it is possible
to establish a practice of getting a digitally signed receipt for a
certificate from each subject in certain cases before the certificate
is delivered. That separate receipt would serve the same function.
3.8 Blind Signatures
The issue of blind signatures [CHAUM] was raised in the working
group. As can be seen from the format of the Signature object,
normal blinding (e.g., of RSA by pre- and post- multiplication of a
signature value) can be applied.
3.9 Determinism
As defined above in section 3.6, CRLs are just one type of response
to an on-line request. Each CRL carries its own validity period and
signature.
This is different from an old concept of CRL which might be called
"wandering anti-matter". In that concept, CRLs would be signed,
might have validity dates (or at least sequence numbers) but would
not be required to be fetched. If someone happened to receive the
latest CRL and the given cert was on it, then the cert was invalid.
The CRLs wandered through cyberspace, like anti-matter, annihilating
any matching certs they happened to encounter.
This concept of CRL introduces non-deterministic behavior. It has
been one design goal of SPKI to make trust computations
Ellison, et al. [Page 25]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
deterministic. As a result, the only way defined here to get a CRL
is if a given cert demands that one be fetched as part of its
validity conditions.
For another example of enforced determinism, it is by definition not
possible to have two SPKI certificates which conflict, so that one
might override the other. If two different certs were issued
defining a given SDSI name as two different keys, for example, then
that name becomes a group with at least two members.
Ellison, et al. [Page 26]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
References
[Ab97] Abadi, Martin, "On SDSI's Linked Local Name Spaces", to appear
in the Proceedings of the 10th IEEE Computer Security Foundations
Workshop (June 1997).
[BFL] Matt Blaze, Joan Feigenbaum and Jack Lacy, "Distributed Trust
Management", Proceedings 1996 IEEE Symposium on Security and Privacy.
[CHAUM] D. Chaum, "Blind Signatures for Untraceable Payments",
Advances in Cryptology -- CRYPTO '82, 1983.
[DvH] J. B. Dennis and E. C. Van Horn, "Programming Semantics for
Multiprogrammed Computations", Communications of the ACM 9(3), March
1966
[ECR] Silvio Micali, "Efficient Certificate Revocation", manuscript,
MIT LCS.
[HARDY] Hardy, Norman, "THE KeyKOS Architecture", Operating Systems
Review, v.19 n.4, October 1985. pp 8-25.
[IDENT] Carl Ellison, "Establishing Identity Without Certification
Authorities", USENIX Security Symposium, July 1996.
[IWG] McConnell and Appel, ``Enabling Privacy, Commerce, Security and
Public Safety in the Global Information Infrastructure'', report of
the Interagency Working Group on Cryptography Policy, May 12, 1996;
(quote from paragraph 5 of the Introduction)
[KEYKOS] Bomberger, Alan, et al., "The KeyKOS(r) Nanokernel
Architecture", Proceedings of the USENIX Workshop on Micro-Kernels
and Other Kernel Architectures, USENIX Association, April 1992. pp
95-112 (In addition, there are KeyKOS papers on the net available
through http://www.cis.upenn.edu/~KeyKOS/#bibliography)
[KOHNFELDER] Kohnfelder, Loren M., "Towards a Practical Public-key
Cryptosystem", MIT S.B. Thesis, May. 1978.
[LAMPSON] B. Lampson, M. Abadi, M. Burrows, and E. Wobber,
"Authentication in distributed systems: Theory and practice", ACM
Trans. Computer Systems 10, 4 (Nov. 1992), pp 265-310.
[LANDAU] Landau, Charles, "Security in a Secure Capability-Based
System", Operating Systems Review, Oct 1989 pp 2-4
[LEVY] Henry M. Levy, "Capability-Based Computer Systems", Digital
Press, 12 Crosby Dr., Bedford MA 01730, 1984
[LINDEN] T. A. Linden, "Operating System Structures to Support
Ellison, et al. [Page 27]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
Security and Reliable Software", Computing Surveys 8(4), December
1976.
[PKCS1] PKCS #1: RSA Encryption Standard, RSA Data Security, Inc., 3
June 1991, Version 1.4.
[PKLOGIN] David Kemp, "The Public Key Login Protocol", working draft,
06/12/1996.
[RFC1321] R. Rivest, "The MD5 Message-Digest Algorithm", April 16
1992.
[RFC2045] N. Freed and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part One: Format of Internet Message Bodies", Dec 2
1996.
[RFC2046] N. Freed and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part Two: Media Types", Dec 2 1996.
[RFC2047] K. Moore, "MIME (Multipurpose Internet Mail Extensions)
Part Three: Message Header Extensions for Non-ASCII Text", Dec 2
1996.
[RFC2065] D. Eastlake and C. Kaufman, "Proposed Standard for DNS
Security", Jan 1997.
[RFC2104] H. Krawczyk, M. Bellare and R. Canetti, "HMAC: Keyed-
Hashing for Message Authentication", Feb 1997.
[SDSI] Ron Rivest and Butler Lampson, "SDSI - A Simple Distributed
Security Infrastructure [SDSI]",
http://theory.lcs.mit.edu/~cis/sdsi.html
[SEXP] Ron Rivest, code and description of S-expressions,
http://theory.lcs.mit.edu/~rivest/sexp.html .
[SRC-070] Abadi, Burrows, Lampson and Plotkin, "A Calculus for Access
Control in Distributed Systems", DEC SRC-070, revised August 28,
1991.
Ellison, et al. [Page 28]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
Authors' Addresses
Carl M. Ellison
CyberCash, Inc.
207 Grindall Street
Baltimore MD 21230-4103 USA
Telephone: +1 410-727-4288
+1 410-727-4293(FAX)
+1 703-620-4200(main office, Reston, Virginia, USA)
EMail: cme@cybercash.com
cme@acm.org
Web: http://www.clark.net/pub/cme
Bill Frantz
Electric Communities
10101 De Anza Blvd.
Cupertino CA 95014
Telephone: +1 408-342-9576
Email: frantz@netcom.com
Butler Lampson
Microsoft
180 Lake View Ave
Cambridge MA 02138
Telephone: +1 617-547-9580 (voice + FAX)
EMail: blampson@microsoft.com
Ron Rivest
Room 324, MIT Laboratory for Computer Science
545 Technology Square
Cambridge MA 02139
Telephone: +1-617-253-5880
+1-617-258-9738(FAX)
Email: rivest@theory.lcs.mit.edu
Web: http://theory.lcs.mit.edu/~rivest
Brian Thomas
Southwestern Bell
One Bell Center, Room 23Q1
St. Louis MO 63101 USA
Telephone: +1 314-235-3141
Ellison, et al. [Page 29]
INTERNET-DRAFT SPKI Certificate Theory 21 November 1997
+1 314-331-2755(FAX)
EMail: bt0008@entropy.sbc.com
Tatu Ylonen
SSH Communications Security Ltd.
Tekniikantie 12
FIN-02150 ESPOO
Finland
E-mail: ylo@ssh.fi
Expiration and File Name
This draft expires 26 May 1998.
Its file name is draft-ietf-spki-cert-theory-01.txt
Ellison, et al. [Page 30]
