Simple Public Key Certificate Carl M. Ellison
INTERNET-DRAFT CyberCash, Inc.
Expires: 29 January 98
Bill Frantz
Electric Communities
Butler Lampson
Microsoft
Ron Rivest
MIT Laboratory for Computer Science
Brian M. Thomas
Southwestern Bell
Tatu Ylonen
SSH
29 July 1997
Simple Public Key Certificate
------ ------ --- -----------
Status of This Document
This document supersedes the draft filed under the name draft-ietf-
spki-cert-structure-01.txt and reflects changes in the structure to
simplify it. The draft ends with a list of open questions for group
discussion.
Distribution of this document is unlimited. Comments should be sent
to the SPKI (Simple Public Key Infrastructure) Working Group mailing
list <spki@c2.org> or to the authors.
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Ellison, et al. [Page 1]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Internet-Drafts are draft documents valid for a maximum of six
months. Internet-Drafts may be updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet-
Drafts as reference material or to cite them other than as a
``working draft'' or ``work in progress.''
To learn the current status of any Internet-Draft, please check the
1id-abstracts.txt listing contained in the Internet-Drafts Shadow
Directories on ds.internic.net (East USA), ftp.isi.edu (West USA),
nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe),
munnari.oz.au (Pacific Rim), or ftp.is.co.za (Africa).
Ellison, et al. [Page 2]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Abstract
With the proliferation of public key cryptography on the Internet,
there arises a need for certification of keys. In the literature,
the word 'certificate' has generally been taken to mean 'identity
certificate': a signed statement which binds a key to the name of an
individual and has the intended meaning of delegating authority from
that named individual to the public key. (See, for example, RFC
1422.) This process is designed to copy a relationship between two
entities from the physical world into the digital world.
The Internet itself changed the world from the one in which identity
certificates made sense. We now deal with people we have never met
and never will, which makes their names meaningless to us, but we
still need to verify whether they are authorized to perform some
action, achieve some access, sign some document, etc.
SPKI certificates were designed to perform that function by directly
specifying the (permission,key) binding which is of interest in the
digital world. As merged with SDSI, the current certificate format
also allows someone to bind a key to a name in their own private name
space. The certificate structure presented here allows permissions
to be delegated to SDSI-named individuals or to raw keys.
Acknowledgments
Several independent contributions, published elsewhere on the net or
in print, worked in synergy with our effort. Especially important to
our work were: [BFL] and [RFC2065]. The inspiration we received from
the notion of CAPABILITY in its various forms (SDS-940, Kerberos, DEC
DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated.
Significant contributions to this effort by the members of the SPKI
mailing list and especially the following persons (listed in
alphabetic order) are gratefully acknowledged: Steve Bellovin, Mark
Feldman, John Gilmore, Phill Hallam-Baker, Bob Jueneman, David Kemp,
Angelos D. Keromytis, Paul Lambert, Jon Lasser, Jeff Parrett, Bill
Sommerfeld, Simon Spero.
Ellison, et al. [Page 3]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Table of Contents
Status of This Document....................................1
Abstract...................................................3
Acknowledgments............................................3
Table of Contents..........................................4
1. Overview of Contents....................................7
2. Scope Of This Effort....................................8
2.1 Charter of the SPKI group..............................8
2.2 Areas Covered And Not Covered..........................8
2.2.1 Key and certificate storage..........................8
2.2.2 Protocols to use public key authentication...........9
2.3 Other Certificate Formats.............................10
2.4 Goals of this effort..................................10
2.5 SPKI Certificates vs. Capabilities....................11
2.6 Chosen standard format................................11
3. Assumptions, Definitions and Design Issues.............12
3.1 Background............................................12
3.2 Definition of PRINCIPAL and KEYHOLDER.................13
3.2.1 Protection of Private Keys..........................14
3.3 Certificate Structure.................................15
3.3.1 5-tuple Reduction (introduction)....................16
3.3.2 Authority Loops.....................................17
3.3.3 Certificate Result Certificates.....................18
3.4 Relation to Policymaker...............................19
3.5 Name spaces and Identity Certificates.................20
3.5.1 X.500 and X.509.....................................20
3.5.2 Death of global identity certification..............21
3.5.3 SDSI 1.0 Name spaces................................21
3.5.4 Mappings within cyberspace..........................22
3.5.5 Mappings to (keyholder K1)..........................22
3.5.5.1 Donation Certificates.............................22
3.5.5.2 Process Server Certificates.......................23
3.6 Certificate validity periods..........................23
3.7 Unwanted Attributions.................................24
3.8 Blind Signatures......................................25
3.9 Determinism...........................................25
4. SPKI Object Definitions................................27
4.1 Canonical S-expression................................27
4.1.1 <byte-string>.......................................27
4.1.2 S-expression........................................28
4.1.3 Encoding examples...................................28
4.1.4 Use of canonical S-expressions......................29
4.1.5 Non-canonical (advanced) S-expressions..............29
Ellison, et al. [Page 4]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.1.6 Unique IDs..........................................30
4.2 SPKI/SDSI 2.0 Objects.................................30
4.2.1 <pub-key>...........................................31
4.2.2 <sec-key>...........................................33
4.2.2.1 HMAC-MD5..........................................33
4.2.2.2 DES-CBC-MAC.......................................33
4.2.3 <hash>..............................................34
4.2.4 <signature>.........................................34
4.2.5 <acl>...............................................36
4.2.6 <sequence>..........................................37
4.3 <cert> object.........................................37
4.3.1 Bare-bones SPKI.....................................38
4.3.1.1 <version>.........................................39
4.3.1.2 <cert-display>....................................39
4.3.1.3 <issuer>..........................................39
4.3.1.4 <issuer-loc>......................................40
4.3.1.5 <subject>.........................................40
4.3.1.6 <subject-loc>.....................................40
4.3.1.7 <deleg>...........................................40
4.3.1.8 <tag>.............................................41
4.3.1.9 <valid>...........................................41
4.3.1.9.1 <date>..........................................41
4.3.1.9.2 <online-test>...................................42
4.3.1.10 <comment>........................................43
4.3.2 SPKI/SDSI...........................................43
4.3.2.1 <issuer>..........................................43
4.3.2.2 <subject>.........................................44
4.3.2.2.1 <name>..........................................44
4.3.2.2.2 <obj-hash>......................................45
4.3.2.2.3 <sec-key>.......................................45
4.3.2.2.4 <keyholder>.....................................46
4.3.2.3 <subject-loc>.....................................46
4.3.3 Tag algebra.........................................46
4.3.3.1 *-forms...........................................47
4.3.3.1.1 Sets of S-expressions...........................47
4.3.3.1.2 S-expressions with *-form parts.................48
4.3.3.1.3 *-form reduction................................50
4.3.3.2 <tag> *-form BNF..................................51
4.3.4 Threshold subjects..................................52
4.3.4.1 Examples..........................................53
4.3.4.2 Definition........................................53
5. Examples...............................................54
5.1 ftp tag...............................................54
5.2 http tag..............................................54
5.3 telnet tag............................................54
5.4 Public Key Protected File System tags.................54
5.5 Authority to spend money..............................55
Ellison, et al. [Page 5]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
5.6 Process Server cert...................................55
5.7 PICS-like ratings cert................................55
5.8 Virus checking cert...................................56
5.9 Full sequence, with donation cert.....................56
6. On-line test reply formats.............................58
6.1 CRL and delta-CRL.....................................58
6.2 Revalidation..........................................58
6.3 One-time revalidation.................................59
7. 5-Tuple Reduction (full)...............................60
7.1 <5-tuple> BNF.........................................60
7.2 Bare-bones case.......................................61
7.3 Intersection of *-form tag sets.......................62
7.3.1 Reduction to (* null) by data type mismatch.........63
7.3.2 Specific intersections..............................63
7.3.3 Deferred intersections..............................64
7.4 Reduction of SDSI names...............................64
7.4.1 Simple SDSI name reduction..........................65
7.4.2 SDSI name composition with subject name growth......66
7.4.3 SDSI Name composition with issuer name growth.......66
7.5 Reduction of (subject (threshold ..)).................67
7.5.1 Left-to-right.......................................67
7.5.2 Right-to-left.......................................68
8. Full BNF...............................................69
Closed Issues.............................................73
Open Issues...............................................78
References................................................79
Authors' Addresses........................................81
Expiration and File Name..................................82
Ellison, et al. [Page 6]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
1. Overview of Contents
This document contains the following sections:
Section 2 describes the scope of both the SPKI working group and this
particular Internet Draft.
Section 3 gives necessary background for understanding the SPKI
certificate structure. It details assumptions, definitions and
design issues behind this structure design and is recommended reading
for anyone who did not follow the discussion on the working group
mailing list.
Section 4 describes SPKI data object formats -- listing the fields in
top level objects, especially the certificate, and giving encoding
details.
Section 5 describes predefined SPKI tag fields. These are the meat
of an SPKI certificate, since they carry the authority or other
information being bound to a subject public key.
Section 6 describes on-line tests and their reply formats.
Section 7 describes the full set of rules used by the basic trust
engine assumed to be part of every verifier which accepts SPKI
certificates.
Section 8 gives the full BNF for SPKI objects.
The Closed Issues section gives a list of questions which have been
resolved by the working group.
The Open Issues section gives a list of open questions to be resolved
by the SPKI working group.
The References section lists all documents referred to in the text as
well as readings which might be of interest to anyone reading on this
topic.
The Authors' Addresses section gives the addresses, telephone numbers
and e-mail addresses of the authors.
Ellison, et al. [Page 7]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
2. Scope Of This Effort
2.1 Charter of the SPKI group
Many Internet protocols and applications which use the Internet
employ public key technology for security purposes and require a
public key infrastructure to manage public keys.
The task of the working group will be to develop Internet standards
for an IETF sponsored public key certificate format, associated
signature and other formats, and key acquisition protocols. The key
certificate format and associated protocols are to be simple to
understand, implement, and use. For purposes of the working group,
the resulting formats and protocols are to be known as the Simple
Public Key Infrastructure, or SPKI.
The SPKI is intended to provide mechanisms to support security in a
wide range of Internet applications, including IPSEC protocols,
encrypted electronic mail and WWW documents, payment protocols, and
any other application which will require the use of public key
certificates and the ability to access them. It is intended that the
Simple Public Key Infrastructure will support a range of trust
models.
2.2 Areas Covered And Not Covered
This particular draft is concerned only with certificate, hash, key
and signature formats, using the certificates defined here both for
verification of identity and for proof of authorization. We do not
cover the other elements of a full public key infrastructure (PKI):
key/certificate storage and acquisition. We also do not cover all
the applications or protocols which must be modified to employ public
key authentication or privacy.
2.2.1 Key and certificate storage
There are several independent efforts at this time to provide a
database of keys or certificates for the Internet.
The DNS Security Working Group draft [RFC2065], specifies an
efficient key storage and distribution mechanism. It may be possible
to store an SPKI certificate in a KEY Resource Record (RR) or to
Ellison, et al. [Page 8]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
create a new RR type for SPKI certificates, under the DNSSEC design,
but that effort has not been undertaken yet.
The PGP key server at MIT operating both as a web page and as an e-
mail driven service provides another example of efficient certificate
storage and retrieval for the net at large. The custom key server
run by PGP, Inc., provides another possibility.
SDSI 1.0 demonstrated certificate servers for individuals to run on
their own net-connected workstations, in response to the fact that
more and more individuals remain connected to the network
permanently. We may see a similar effort establishing SDSI/SPKI
certificate servers.
On the other hand, there are those who view certificate servers as a
violation of privacy. A standard phenomenon in dealing with
classified documents is called "data aggregation". That is, two data
A and B may, by themselves, be unclassified, but if both were to be
known by one person, the combination would be considered classified.
The same might apply to the authorizations granted by certificates to
a given keyholder. Along similar lines, many corporations consider
their employee telephone lists confidential and are unlikely to host
a certificate server which gives the equivalent information to the
net.
The common practice which has evolved is that of the requester
supplying any and all certificates which the verifier needs in order
to permit the requested action. In this model, there may be no need
for certificate servers or if there are servers, it is likely that
they will be accessed by the requester (possibly under access
control) rather than the verifier.
2.2.2 Protocols to use public key authentication
Proposals for modification of applications to employ public key
authentication are proceeding independently, e.g., [PKLOGIN]. We
encourage other developers to actively enter this area of design,
aided by SPKI certificates as a tool. Others, such as TLS and SSH
already use public key authentication and are considering use of SPKI
certificates for communicating the permission required to achieve the
desired access.
Ellison, et al. [Page 9]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
2.3 Other Certificate Formats
We are aware of a number of actual and proposed kinds of signed
records which, by some definition, qualify as certificates:
1. PGP signed keys
2. X.509 identity certificates, from a number of sources
3. X.509 SET (Secure Electronic Transaction) certificates
4. DNS Security Extension signed keys
5. Signed PICS labels (from the W3C DSig effort)
It is not our intention to coerce these other certificate formats
into our mold, although they are welcome to switch over. The
certificate structure defined below is flexible enough to accommodate
all of the above.
However, we recognize that a real world system will involve some
mixture of SPKI and non-SPKI certificates as well as traditional
Access Control Lists (ACLs). Our design accommodates these through
the Certificate Result Certificate process, allowing all these to be
merged into a single, simple format as far as application software is
concerned.
2.4 Goals of this effort
In keeping with the design goals enumerated in section 3 of RFC1958,
it is our goal to keep the SPKI certificate pruned to the minimum
information necessary to accomplish the job at hand, which is secure
authentication and authorization of access control for the Internet.
We use well tested formats with a long history of success and have
chosen those which require the bare minimum of tool software so that
applications remain as small and efficient as possible. We desire to
offer the bare minimum of options, in order to reduce program size
and complexity.
We also recognize that some kinds of certification (such as notarized
identity certification) can carry risks of invasion of privacy for
the individual. We have therefore designed these certificates to
reveal the minimum information necessary to get the job done,
whatever that job happens to be. In many cases, the user can remain
anonymous in the traditional sense while exercising strongly verified
Ellison, et al. [Page 10]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
authorization. That is, the user can be identified by his public key
alone.
2.5 SPKI Certificates vs. Capabilities
An SPKI certificate is closer to a "capability" as defined by
[HARDY], [KEYKOS], [LANDAU], [SRC-070], etc., than to an identity
certificate. There is the difference that in a capability system,
the capability itself is a secret ticket, the possession of which
grants some authority. It is anonymous (more like cash than a
check). Therefore, if you grant authority to read a capability, you
have delegated the ability to use it. An SPKI certificate identifies
the specific key to which it grants authority and therefore the mere
ability to read (or copy) the certificate grants no authority and the
certificate itself does not need to be as tightly controlled.
Rather, control over the corresponding private signature key must be
tightly controlled.
With SPKI certificates, one can delegate authority (all or part of
the authority one has been delegated) to a different key, without
sharing the quantity which must be kept secret (the private key) --
as opposed to a capability which is kept secret except when it is
shared for the purpose of delegation.
2.6 Chosen standard format
In this draft, the standard format adopted is that developed by SDSI,
modified slightly. Data objects are defined as S-expressions --
lists in which the first element is a token defining the data object.
Rather than permit the full generality of S-expressions, we define a
canonical format and accept only that form. Software is available to
translate between the canonical format and a presentation format.
This document presents the canonical format, but uses a presentation
format for examples since the canonical format is binary and can not
easily be transmitted in a text document.
Ellison, et al. [Page 11]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
3. Assumptions, Definitions and Design Issues
There were a number of discussion topics involved in the design of
SPKI certificates and we summarize them here for the reader who was
not part of the SPKI discussion. This section should at least be
skimmed by even the reader with a solid grounding in classical
(identity) certification. Some of these might be new concepts. Some
provide definitions for terms which traditional discussions of
certification frequently leave undefined.
Throughout this document, we refer to two parties engaged in
certificate use: the prover and the verifier.
By PROVER, we mean the entity which wishes access or digitally
signs a document. We assume that the prover assembles all
certificates necessary for use by the verifier, and puts those
into order for the verifier. The prover is software but could
be interacting with a human user.
By VERIFIER, we mean an entity which processes certificates,
together with its own ACL entries, to determine if the prover
deserves access or if some signed document is valid. The
verifier is most likely unattended software.
3.1 Background
In the words of [LAMPSON], a public signature key "speaks for" its
owner: a person or entity we call the "keyholder". It is primarily
through such public key "speech" that one achieves security on the
inherently anonymous and spoof-able Internet.
There is a long standing effort to bind public keys to the "true
names" of their keyholders, in an attempt to identify the keyholder
and to permit the transfer of permissions or other attributes from
the physical world in which the keyholder lives into the digital
world. This effort has produced identity certificates, such as X.509
certificates or PGP signed keys, giving <name,key> bindings which
needed to be combined with certificates or ACL entries giving
<tag,name>, to yield the relationship <tag,key> which a computer then
uses to verify public-key driven access attempts. {<tag> here stands
for authorization, permission, etc.}
The Internet has changed the world from the one in which identity
certificates were originally seen to be necessary. In the new world
Ellison, et al. [Page 12]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
of the global Internet the entities which communicate are often not
known to each other in the physical world. This trend is likely to
increase as time goes on. Therefore a mechanism which transfers
attributes from the physical world to the digital world is
increasingly less appropriate while a mechanism which transfers
attributes within the digital world is vital and one which transfers
attributes from the digital world to the physical world is likely to
be needed very soon, if not immediately.
We have also observed that <key> is a perfectly adequate name for a
keyholder, at least as far as a computer is concerned. It and its
hash have the advantage of being unique while each portion of it (and
especially of its hash) is uniformly distributed and therefore of
particular value as an index into a database. It is also tied the
most strongly of any identifying string to the keyholder. We have
therefore defined a certificate which communicates <tag,key>
directly, leaving names out of the process except in the case where
the name is the item of interest (e.g., for secure e-mail).
3.2 Definition of PRINCIPAL and KEYHOLDER
The most important issue is the notion of a key as a principal and
the difference between that key and the person or machine which owns
and controls it.
By PRINCIPAL, we mean a signature key. That is, a principal is
capable of "speaking" in cyberspace by signing messages. We
also permit use of the secure hash of a signature key as a
principal, in an effort to save space in data structures which
use principals.
By KEYHOLDER, we mean an entity in the 3-D world which controls
a given (private) signature key. The keyholder is identified
primarily by the public verification key which corresponds to
the private signature key.
By definition, the keyholder has sole possession of the private key.
That private key could be used as the identifier of the keyholder --
as a name -- except the private key must be kept secret. There is
only one private key to match a given public key, so the keyholder
can be identified by the public key just as uniquely. Similarly,
there is only one public key which hashes to a given secure hash (by
definition of "secure hash", assuming we are limited in computation
power), so the secure hash of a public key can also be used to
Ellison, et al. [Page 13]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
identify the keyholder. If we are using symmetric (secret) signature
keys, the hash of that key can still serve as a name for the key and
for its keyholder(s).
We identify a PRINCIPAL by either a key or a secure hash of a key.
There is pressure, in the interest of simplicity, to restrict
PRINCIPAL to just a key. However, if one is using a shared secret
key (e.g., for HMAC or some symmetric algorithm like DES-MAC), it is
essential to keep the key secret and use of a hash permits that. It
is also possible to have shared secret public keys -- e.g., RSA
public keys of short moduli (for performance reasons) -- which must
not be published because the key can be broken, but for which the
hash of the key can be published without fear of compromise.
We identify a KEYHOLDER by the construct "(keyholder <principal>)" --
using the principal as the name of the private key and therefore the
keyholder, but explicitly noting that we refer to the keyholder in
physical space rather than the key in cyberspace.
Without certificates, we might not know anything else about the
keyholder (such as name, gender or even if the keyholder is a living
being) but we do know enough to link together separate messages from
the same keyholder. For some purposes, that is sufficient
identification (for example, when a person is first encountered on-
line via signed messages and there is no intention of linking that
person to any physical being, only to his or her own other messages).
However, there are other applications for which the ability to link
together separate messages from an anonymous source is not adequate
and therefore for which certificates are required.
3.2.1 Protection of Private Keys
For any public key cryptosystem to work, it is essential that a
keyholder keep its private key to itself. In the case of a human
being, this might involve keeping the private key encrypted under a
high-entropy passphrase and storing it only on the person's own
personal computer or floppy disks. Some humans might even keep the
private key in a tamper-resistant PCMCIA card or Smart-Card which
will never release it and will in fact destroy it after too many
failed attempts to gain access. In the case of a network node, this
might involve keeping the private key in a tamper-resistant
cryptographic processor which generated it and which will destroy it
if tampering is attempted.
If the keyholder does not keep the private key protected (that is, if
the private key gets out to others to use) then one can not know what
Ellison, et al. [Page 14]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
entity is using that key and no certificate will be able to restore
the resulting broken security.
Therefore, we are forced to assume that all private keys are kept
private and bound tightly to the one keyholder to which they belong.
We will have to provide for methods of announcing the compromise of
such private keys whenever this assumption proves false, but we must
assume that unless such notification is delivered, each private key
is secure and attached to its owner.
Note: We have specifically included a process for one keyholder
who has been granted some authority to delegate that authority
to another, in order to reduce if not eliminate the motivation
for one keyholder to loan a private key to another.
So to reiterate, we do not expect every person, process and device in
the Internet to employ true tamper resistance. Many people will keep
and use private keys on an insecure personal computer or workstation.
However, we are forced to assume protection of the private key or
give up any notion of cryptographically strong authentication and
authorization. Work is progressing on decreasing the cost of true
tamper-resistance but until it is ubiquitous, we must accept a
certain amount of risk from copied or stolen private keys. Even
then, there is risk from coerced use of one's private key.
3.3 Certificate Structure
An SPKI certificate body has several fields, five of which are
relevant for security purposes:
ISSUER: a principal or a single, top-level name in a principal's name
space. The principal is identified as a public key or the hash
of that key and the corresponding private key signs the
certificate.
SUBJECT: a principal, an object or a SDSI name reducible to either of
those. The subject is that which receives authority from the
issuer by way of the certificate.
DELEGATION: the optional modifier, "(propagate)", giving the subject
permission to delegate the authority presented in the
certificate (or part of it) to some other Subject. This is
Ellison, et al. [Page 15]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
represented as the delegation boolean, D, in the discussion
below. The two boolean states are (F: delegate only through
name declarations -- also known as "stop at key") and (T:
delegate to the subject).
AUTHORITY: the specific authorization(s) being delegated in this
certificate. These fields, of the form "(tag ...)", are to be
defined by those who have resources to control and describe
resource allocations. This document gives some examples for
such fields which are expected to be in common use, but more
importantly it gives the structure for <tag> fields and the
description of a standard process for manipulating them which is
expected to be implemented in all code conforming to this
standard.
VALIDITY: date ranges and/or online validity tests for determining
certificate validity.
A certificate is signed by its issuer. Section 6 gives details about
signature blocks.
The five security-relevant fields described above are termed a
"5-tuple" for lack of a better word, in the discussion below. The
assumption is that a certificate's signature will be checked to yield
the 5-tuple which, in turn, will be kept in trusted memory and will
participate in trust management decisions. Objects other than
certificates (such as ACL entries) can also yield 5-tuples which
participate in trust management decisions.
Informally, the meaning of the certificate is "The issuer says that
the subject has the stated authority during the validity period".
Another way of saying this is "The issuer says that the subject may
speak for the issuer with the stated authority during the validity
period." If the issuer issues several such certificates for
different subjects, then it is defining a group of subjects, each of
which can speak for it.
If the subject is an object that is not reducible to a principal, it
can't do any speaking; in this case the meaning is "The issuer says
that the subject has the properties stated by the 'authority'."
3.3.1 5-tuple Reduction (introduction)
A certificate which is received to be part of a verification process
has its signature checked. One whose signature checks is considered
Ellison, et al. [Page 16]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
valid. Other kinds of authorization statement (most specifically ACL
entries) can be considered valid without a signature check.
A valid authorization statement can be represented by five
quantities:
(I,S,D,A,V)
A pair of 5-tuples can be reduced as follows:
(I1,S1,D1,A1,V1) + (I2,S2,D2,A2,V2)
becoming
(I1,S2,D2,A,V)
if S1=I2 (meaning that they are the same public key)
and (D1 = TRUE) or (S1 is a SDSI name)
and A = intersection(A1,A2)
and V = intersection(V1,V2)
The actual process is slightly more complicated when I2 is of the
form
(issuer (name K3 nnn))
or when S1 is of the form
(subject (threshold K N (s1) (s2) ... (sN)))
Rules for those cases are given below in section 10, presenting the
full tuple reduction logic, but for the discussion to follow the
logic given above will suffice.
3.3.2 Authority Loops
By 5-tuple reduction, some chains of authorization statements will be
reduced to the form:
(Self,X,D,A,V)
where "Self" represents the entity doing the verification, granting
access, etc. Such a 5-tuple says "Self says (I say) that X has
authority (D,A) for validity period (or conditions) V". In other
words, it tells Self what it can trust about X.
Ellison, et al. [Page 17]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Any authorization chain not reducing to a 5-tuple with Self as issuer
isn't relevant to decisions by Self.
Therefore, any authorization chain which is to be used by Self to do
trust management must have Self as a root. Since Self is doing this
chain reduction and is therefore at the receiving end of the chain as
well, that makes all useful authorization chains loops.
3.3.3 Certificate Result Certificates
In cases where the verifier, Self, has access to a private key, once
it has reduced a chain of certificate bodies down to the form:
(Self,X,D,A,V)
it can sign that generated body, using its private key, producing an
SPKI certificate. That certificate will have a validity period no
larger that of any certificate in the loop which formed it, but
during that validity period it can be used by the prover instead of
the full chain, when speaking to that particular verifier. It is
good only at that verifier (or at another which trusts that verifier,
Self, to delegate the authorization A). Therefore, one option by the
verifier is to sign and return the result 5-tuple to the caller for
this later use.
If it isn't important for any other verifier to accept this "result
certificate", it can even be signed by a symmetric key (an HMAC with
secret key private to the verifier).
The certificates which made up the loop forming this result 5-tuple
could have been of any variety, including X.509v1, X.509v3, SET or
DNSSEC. They could also be PGP signed keys processed by an enriched
trust engine (one capable of dealing with the PGP web of trust
rules). If the verifier, Self, were to be trusted to delegate the
resulting authorization, its certificate result certificate then
becomes a mapping of these other forms. This may prove especially
useful if a given certificate chain includes multiple forms or if the
result certificate is to be used by a computationally limited device
(such as a Smart-Card) which can not afford the code space to process
some of the more complex certificate formats.
Ellison, et al. [Page 18]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
3.4 Relation to Policymaker
The section above introduced the possibility of a machine which
reduces a set of certificates, possibly a very complex one, and
yields a single certificate as a result. That single certificate
would be simpler and faster to verify. It might even stand alone in
granting access.
That machine reducing the set of certificates to a single result
might even execute a policy program which could be too complex to be
expressed in terms of SPKI 5-tuple reduction. The policy machine
would still have to have its own ACL entries, declaring the keys it
trusts as "roots" for various purposes and, in this hypothetical
case, a signature key, P. It would execute its policy program on the
credentials provided by the caller, come up with either a failure or
a certificate result, signed by P, and deliver that result to the
caller.
In the manner of [BFL] we note that one can take the same code
executed by that policy processing machine and digitally sign the
code -- then digitally sign the ACL entries for its "roots" (turning
them into certificates, issued by P) -- and ship the code plus
certificates to the caller, presumably a verifying computer. That
verifying computer could then run the policy code on P's behalf,
getting either a failure or a 5-tuple. It can't sign the 5-tuple
turning it into a certificate issued by P, because it would not have
P's private key -- but it doesn't need a certificate. It needs only
the trusted 5-tuple.
[BFL] introduces a language called Policymaker in which one can
express security policy statements. It is possible for Policymaker
to be used along with SPKI certificates in two ways:
1) It is believed possible to use Policymaker's language to implement
the standard SPKI 5-tuple reduction. The code has not been
written as of the time of this draft, but at this point it looks
possible.
2) For any trust policy which the full SPKI 5-tuple reduction can not
express, one must write a policy interpretation program and
Policymaker provides a language and body of examples for that
purpose. The result of the Policymaker execution can be a 5-tuple
to be used within an SPKI reduction.
Ellison, et al. [Page 19]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
3.5 Name spaces and Identity Certificates
Since the word "certificate" was first used by Kohnfelder in 1978 to
refer to a digitally signed binding between a name and a public key,
people have assumed that a certificate binds a name to a key.
For most of human history, people lived in relatively small, closed
communities. It was common in such a community for each member to
have his or her own unique name. Everyone in the community would
know everyone else in the community by that name. It was also
extremely unlikely for someone in such a small community to change
his or her name (except through marriage). The habit naturally
developed of thinking of a person's name as a unique and permanent
identifier, in a way synonymous with his or her identity.
Although such small communities have become unusual for the majority
of people today, the association between name and identity persists
in human thinking. Even today, a certificate which binds a name to a
key is often called an "identity certificate".
3.5.1 X.500 and X.509
At one time, it was assumed that there would be a worldwide directory
of names of people (and computers and other things), called X.500,
and there was a data structure defined, called X.509, to bind public
keys to portions of the X.500 hierarchy. The original purpose of
such certificates was to record who (which keyholder, ie., which key)
had permission to modify that portion of the distributed X.500
database.
At some point, it became apparent that X.500 was never going to occur
as a global directory. Among other things, corporations which were
to own and manage substantial sub-trees of the directory consider
their employee directories company confidential. The same applies to
some government agencies.
The fact that an X.500 node's address was a person's unique name (so-
called "distinguished name"), led people to view X.509 apart from its
purpose of controlling access to X.500 databases and instead treat it
as an identity certificate.
Ellison, et al. [Page 20]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
3.5.2 Death of global identity certification
Even if a global X.500 directory had occurred, global identity
certification would have died. The problem is one of the
unanticipated consequences of the Internet.
The purpose of an identity certificate is to map from the 3D space of
people to cyberspace, particularly to the space of public signature
keys.
This mapping takes two steps: from 3D space to a name space; from the
name space to key space. The latter step is accomplished by a
certificate (e.g., X.509). The former step is assumed, in the
X.500/X.509 case, to be common knowledge. The larger that name
space, the less likely that anyone would know the name of a specific
individual. Alice might suspect that her old friend Bob Smith has a
name in the global X.500 directory, but there are so many people
named Bob Smith in the world that it is unlikely Alice would know
which of the thousands of Bob Smiths was in fact her old friend.
The problem is that, like the telephone directory which inspired this
model of certification, the directory never claimed to record
information of interest to each user (e.g., Alice's old friend). In
fact, a directory which did so would almost certainly be viewed as a
violation of privacy on a massive scale and would be shut down.
3.5.3 SDSI 1.0 Name spaces
SDSI 1.0 [SDSI] solved this problem inherent in global name spaces by
ignoring the fantasy of a global name space and replacing it with
local name spaces, one for each principal (= signing key).
Principals may share name spaces as will be seen later, but in theory
each principal has its own name space.
The certificate mapping from name to key (SDSI, in this case) is just
as secure as the X.509 certificate mapping from the global name space
to a key, but the link from 3D space to name is considerably more
secure -- because it is a link defined by the user. Alice's old
friend Bob Smith might be named "Red" in her name space, for example.
Her name for him is not intended to be of any use to anyone else --
only to her. Such a local name space is already familiar to some
users of mail agents, under the label "nickname" or "alias".
Ellison, et al. [Page 21]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
3.5.4 Mappings within cyberspace
Identity certificates with their presumed ability to map from 3D
space to key space were assumed to be necessary "so that you know
with whom you are dealing in cyberspace". The assumption behind such
a thought is that a relationship is formed in 3D space between people
and that relationship needs to be mapped into cyberspace.
Unanticipated by the original designers of identity certificates was
the fact that the Internet brought with it the formation of
relationships in cyberspace. In such cases, there is no relationship
in 3D space to be mapped and therefore no need for identity
certificates.
There is, however, a need for certificates within cyberspace -- to
grant privileges, access rights, etc. -- from one cyberspace
principal to another (from one key to another). It was for this
situation that the original SPKI was designed.
3.5.5 Mappings to (keyholder K1)
Also not anticipated by the pre-Internet developers of identity
certificates was that relationships which formed online might need to
be mapped occasionally back to the 3D world. Those early designers
of certificates might have assumed that the binding between name
("identity") and key was bi-directional, but it was not. It mapped
name to key. The mapping from key to name is not satisfied by a
single approach. In particular, there can be no single issuer for
such a certificate, suitable for all purposes. Two such certificates
are described below but there are probably several varieties.
3.5.5.1 Donation Certificates
Situation: you meet someone (who uses key K1) online, are impressed
with his work and decide to hire him. You make an offer. He
accepts. He starts working for you and you like his work (all signed
by K1). You now need to send him a paycheck. So, you need a name to
put on the paycheck and you need a postal address to mail it to (and
maybe a phone number, if you are using Fed Ex).
This sounds like a traditional identity certificate, but it isn't.
There is no CA in this case. The one key you can trust the most to
sign this certificate is K1. It belongs to the individual with the
most to gain by providing correct information. In X.509-style
Ellison, et al. [Page 22]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
certification, one would never use a self-signed certificate.
3.5.5.2 Process Server Certificates
Situation: you meet someone (who uses key K1) online, are impressed
with his work and decide to hire him to do some protracted project.
You make an offer. He accepts. You need the work done and done
right. Failure to have the work done would be very harmful to you.
For that you write a contract which he signs with K1 and the contract
includes penalty clauses. In the event of his failure to perform,
you need to know that you can get redress through the legal system.
One way is to have his name and home address so that you could serve
legal papers on him should he default on the contract.
The certificate which lets you serve papers on Keyholder(K1) sounds
even more like a traditional identity certificate, but it isn't.
Neither is it a donation certificate, since this one should not be
signed by K1. Instead, it should be signed by Kp -- the key of a
company which does process serving. That company, Acme Process
Servers, however, would rather not have a name and address in the
certificate. Instead, Acme would prefer to have a simple sequence
number in the certificate, indexing Acme's own files on the person.
This forces you to use Acme to do the process serving, doubtless for
an additional fee, in the event that you do sue.
Meanwhile, you would prefer to have this certificate over an identity
certificate issued by the Post Office, listing the person's name and
address. The name and address certificate reflects facts at the time
of the start of the contract, not facts at the time legal papers need
to be served. It may take substantial investigative work to get from
the former to the latter. That is the work Acme would do for a
living and it would be for that work that Acme would charge both for
the initial certificate and for the act of serving papers on the
keyholder of K1. Acme might perform this work at time of default or
keep tabs on Keyholder(K1) during the life of the contract. That
would be Acme's choice.
3.6 Certificate validity periods
Our experience with credit cards has influenced the way we consider
validity periods of certificates.
A credit card is issued with an expiration date 1 to 3 years later
than the date of issue, yet one can revoke a credit card and have
Ellison, et al. [Page 23]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
that revocation be effective within a day of the request. That
credit card has a validity period of one day (or less) in spite of
its expiration date.
At one time, credit card validity was verified at a checkout counter
by looking the card number up in a book of revoked cards. The
validity period of a card not listed in such a book was the time
until that book was updated and the card had to be looked up again.
This practice has migrated into the digital world through the CRL
(Certificate Revocation List) construct.
Modern systems accepting credit cards perform an on-line validity
check, in which case the validity period can be very short and is
determined by the time it takes to make a database update from a
report of a lost or stolen card.
SPKI certificates may use one or both of two kinds of validity
period: a date range (akin to expiration dates) or an on-line check.
The on-line check will return information about the certificate's
validity and that information itself will have an expiration date and
time. The certificate together with its latest on-line test result
would then yield a valid assignment of authorization, with validity
period which is the intersection of the dates of the two data items
(usually just the date range of the on-line test result).
There are three forms of on-line test result defined:
CRL
a list of certificates known to be revoked since a certain time.
Periodic revalidation
a new assured validity date for the certificate being tested.
One-time revalidation
a statement that for this one transaction, the indicated
certificate is valid. [This is as close as we can come to a
0-length validity period revalidation.] The one-time
revalidation can also have side effects -- e.g., refer to a bank
balance.
3.7 Unwanted Attributions
There is a potential problem that a certificate might be issued which
the keyholder does not want.
Ellison, et al. [Page 24]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
For example, someone with the power to issue access certificates
wishes to make trouble for you. That person generates a cert for
you, giving you access to their company's file system. Someone
breaks into that file system and does damage, also wiping out the
audit logs of who broke in. So, the police ask the age-old Perry
Mason question: who had keys to that door? Your cert (even though
you never saw it) is a key to that door. It might even be the only
cert with the capability to do what was done, at least according to
the company records. That makes you a suspect. If for other reasons
you might be even the most logical suspect, then you might make it to
the top of the police list and get severely hassled.
For another example, a keyholder, Alice, has a signature key, K,
being used to sign digital lab notebooks for later use in patent
applications. That key is certified as hers by her company through
an SPKI identity certificate with an EMPLOYEE <tag> field.
Bob learns Alice's public key and builds a certificate using his own
name and her key, getting it signed by some reputable commercial CA.
Now when it comes time to dispute prior art on Alice's patent(s), Bob
produces his certificate and claims that Alice had not only copied
his work but stolen his private signature key.
Although we do not mandate such practice at this time, some
certificates could be signed by the <subject> as well as by the
<issuer> in order to make sure that the <subject> really does have
access to the indicated private key. Alternatively, it is possible
to establish a practice of getting a digitally signed receipt for a
certificate from each subject in certain cases before the certificate
is delivered. That separate receipt would serve the same function.
3.8 Blind Signatures
The issue of blind signatures [CHAUM] was raised in the working
group. As can be seen from the format of the Signature object,
normal blinding (e.g., of RSA by pre- and post- multiplication of a
signature value) can be applied.
3.9 Determinism
As defined above in section 3.6, CRLs are just one type of response
to an on-line request. Each CRL carries its own validity period and
signature.
Ellison, et al. [Page 25]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
This is different from an old concept of CRL which might be called
"wandering anti-matter". In that concept, CRLs would be signed,
might have validity dates (or at least sequence numbers) but would
not be required to be fetched. If someone happened to receive the
latest CRL and the given cert was on it, then the cert was invalid.
The CRLs wandered through cyberspace, like anti-matter, annihilating
any matching certs they happened to encounter.
This concept of CRL introduces non-deterministic behavior. It has
been one design goal of SPKI to make trust computations
deterministic. As a result, the only way defined here to get a CRL
is if a given cert demands that one be fetched as part of its
validity conditions.
For another example of enforced determinism, it is by definition not
possible to have two SPKI certificates which conflict, so that one
might override the other. If two different certs were issued
defining a given SDSI name as two different keys, for example, then
that name becomes a group with at least two members.
Ellison, et al. [Page 26]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4. SPKI Object Definitions
We have chosen a simplified form of S-expression (the canonical form)
as the format for SPKI objects. An S-expression is a list enclosed
in matching "(" and ")". We assume the S-expression technology of
[SEXP] with the restrictions that no empty lists are allowed and that
each list must have a byte-string as its first element. That first
element is the "type" or "name" of the object represented by the
list.
SPKI objects are defined below in a familiar extension of BNF -- with
"*" meaning closure (0 or more occurrences) and "?" meaning optional
(0 or 1 occurrence). First we define the canonical S-expression form
in that BNF.
4.1 Canonical S-expression
We define a canonical S-expression as containing binary byte strings
each with a given length and punctuation "()[]" for forming lists.
The length of a byte string is a positive ASCII decimal number, not
starting with "0", terminated by ":". We further require that there
be no empty lists and that the first list element be a byte string
(as defined below). This form is a unique representation of an S-
expression and is used as the input to all hash and signature
functions. If canonical S-expressions need to be transmitted over a
7-bit channel, there is a form defined for base64 encoding them.
4.1.1 <byte-string>
A byte string is a binary sequence of bytes (octets), optionally
modified by a display type.
If the byte-string is used as a binary number, these bytes are twos-
complement, in network standard order (most significant byte first).
This means that the sign of the first byte is the sign of the number,
so that if you have a positive number whose first byte exceeds 128,
then you need to prefix that number with a 0 byte to force it to be
positive. A canonical form positive number will not have unnecessary
leading 0x00 bytes while a canonical form negative number will not
have unnecessary leading 0xFF bytes. Such a byte is unnecessary if
by removing it, the remaining string has the same value as a twos-
complement integer.
All byte strings carry explicit lengths and are therefore not
Ellison, et al. [Page 27]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
0-terminated as in the C language. They are treated as binary even
when they are ASCII, and can use any character set encoding desired.
Typically, such a choice of character set would be indicated by a
display type.
A display type is assumed to be a MIME type giving optional
instructions to any program wishing to display or use the byte
string. For example, it might indicate that the string is in
UNICODE, is a GIF or JPEG image, is an audio segment, etc. Although
the display type of a byte string is optional, it is considered part
of the string for any equality comparisons or hashing.
A byte-string is defined by:
<byte-string>:: <bytes> | <display-type> <bytes> ;
<bytes>:: <decimal> ":" {binary byte string of that length} ;
<decimal>:: <nzddigit> <ddigit>* ;
<nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
<ddigit>:: "0" | <nzddigit> ;
<display-type>:: "[" <bytes> "]" ;
4.1.2 S-expression
An S-expression is of the form:
<s-expr>:: "(" <byte-string> <s-part>* ")" ;
<s-part>:: <byte-string> | <s-expr> ;
where the first byte string in the S-expression is referred to here
as its "type".
4.1.3 Encoding examples
(4:test26:abcdefghijklmnopqrstuvwxyz5:123455::: ::)
is a canonical S-expression consisting of four byte strings: "test",
"abcdefghijklmnopqrstuvwxyz", "12345" and ":: ::".
The advanced text form is:
(test abcdefghijklmnopqrstuvwxyz "12345" ":: ::")
showing that the advanced form follows familiar token recognition
Ellison, et al. [Page 28]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
rules, not permitting tokens to start with digits, terminating them
with white space or punctuation marks.
For transmission of true 8-bit forms, we permit base64 encodings
according to [RFC2045], with the base64 characters enclosed in
braces. The example above encodes to:
{KDQ6dGVzdDI2OmFiY2RlZmdoaWprbG1ub3BxcnN0dXZ3eHl6NToxMjM0NTU
6OjogOjop}
4.1.4 Use of canonical S-expressions
Canonical S-expressions were designed to be as simple to pack and
parse as possible. Some concessions were made to those developers
who might want to examine a canonical S-expression in an ASCII editor
like emacs (specifically the readable decimal length fields and
readable "()[]" characters) but in general the form is as close to
minimum size as possible. Parsing of a canonical form S-expression
requires minimal look-ahead and no re-scanning of incoming bytes. As
a result, the parsing code remains very small. Assuming each byte
string is stored with a length field, generation of a canonical form
from a data structure requires an extremely small amount of code.
The canonical S-expression is the form which is hashed for both
generating and verifying signatures. These two processes can be
thought of as the start and end of an SPKI object's useful life and
both require canonical form. Therefore, it is recommended that the
canonical form be the form transmitted and stored in normal use, to
be converted temporarily to and from a more readable form by display
or editing applications written for the purpose.
[Violating that suggestion, this document includes some advanced non-
canonical forms, for readability. Since this document is required to
be straight ASCII, no pure 8-bit canonical forms will be presented
except under base64 encoding.]
4.1.5 Non-canonical (advanced) S-expressions
[SEXP] includes a general purpose utility program for converting
between canonical and advanced S-expression form. In the advanced
form, individual byte strings may be expressed without length fields
(if they are what most languages consider text tokens), may be
written as quoted strings (under normal C string rules), or may be
individually hex or base64 encoded. Also in the advanced form, extra
Ellison, et al. [Page 29]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
white space between list elements is allowed for readability and
ignored on conversion to canonical form.
For examples this document will normally use the advanced form,
because of its readability, but for at least one concrete example the
canonical form and its hash are presented (base64 encoded where
necessary).
In these examples, we will use keywords without preceding length
fields, quoted strings, hex values (delimited by "#") and base64
values (delimited by "|"). Those are features of the advanced
transport form of an S-expression, and are not part of the canonical
form. We will always present the canonical form (base-64 encoded,
when it contains non-ASCII characters) which the reader can decode to
get the actual canonical form.
4.1.6 Unique IDs
Top level object names are defined in this document along with
certain algorithm names. <tag> objects are user-defined, using a
language for describing sets of permissions given here, and in the
process, the defining user can choose any object names he or she
wishes.
For the definition of new algorithm names, it is our preference that
this be taken on by IANA for single-word standard names. In the
interest of maximum flexibility we also permit users to define their
own algorithm names via a normal URI's (which presumably point to
descriptions of the algorithms or even code).
4.2 SPKI/SDSI 2.0 Objects
The objects defined in SPKI/SDSI 2.0 are S-expressions. That is they
are lists of either byte strings or other lists. In our case, all S-
expressions start with a <byte-string>, called the object name. The
remaining elements of the list are called "parts" of the object.
In a communication from prover to verifier, one might encounter only
a small number of different objects: usually a <sequence> of <cert>,
<pub-key>, <sec-key>, <signature> and <op>. The verifier will also
need to refer to its own <acl>. These are considered top level
objects and are defined in the sections immediately following
It is standard SPKI/SDSI practice to use names starting with a lower
Ellison, et al. [Page 30]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
case letter, followed by lower case letters, digits and hyphens for
object types. SPKI/SDSI is case-sensitive, so the byte-string "RSA"
is not the same as "rsa". Non-standard object types (i.e. those
defined by an application developer) are completely unconstrained,
may have display types and may even be URI's pointing to
documentation of the object type.
The structure and interpretation of the parts is up to the designer
of the top-level object type.
Normally, the object structure is one of two varieties:
"positional" -- the parts are listed in some fixed order with
possible omission of some of the later parts and meaning of the
part depending on its position
Example: (hash sha1 20:...)
"sub-type based" -- the parts are identified by object type of a
sublist or spelling of a byte-string and can be in any order.
These elements are expected all to have distinct types, and the
types of the parts determine their meaning with respect to the
top-level object. The set of allowable sub-object types is a
function of the object type, as is whether sub-objects of some
types are optional.
Example: (rsa (n 128:...) (e 1:.))
The following are the definitions of the top level objects which a
verifying program may encounter. Note that the main object, cert, is
sub-type based so the parameter fields may be in any order, but the
BNF suggests a fixed order. We use the BNF definition to indicate
that there may not be more than one of each of the listed fields, and
also to suggest (for readability) that the cert parts be presented in
the order given. This document will use that order.
4.2.1 <pub-key>
<pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uri>? ")" ;
A public key definition gives everything the user needs to employ the
key for checking signatures.
The only pub-sig-alg-id's we have defined at this point are for
signature verification. That is because we need only signature keys
for certificate formation and access control. Other key types are
Ellison, et al. [Page 31]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
open to being defined by users.
The following is an RSA signature key, shown in advanced transport
format:
(public-key rsa-pkcs1-md5
(e #03#)
(n |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO
YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY
VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| ))
For actual use, the key is held and presented in canonical form the
base64 encoding of which is:
{KDEwOnB1YmxpYy1rZXkxMzpyc2EtcGtjczEtbWQ1KDE6ZTE6AykoMTpuMTI
5OgDRwhvOY1xRponK9zBj4+dxWGEmNWlgLnujyp6RRKx4SjCWuB6yuFkikzm
E05WqUc55xCw9g+5Vnd0PDw9JcotTSaTczJMUFR66wJyEKHM3jmbos/8mFQ8
ydQ3YiJoscm/ycpntw9FIlF4XelRgM9MdHIKynnyp5o8uNdCq6N7ltSkp}
Although not strictly needed by this draft, the private key for the
public key above is:
(private-key rsa-pkcs1-md5
(e #03#)
(n |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO
YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY
VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| )
(d |AIvWvTRCPYvEW9ykyu1CmkuQQMQjm5V0Um0xvwuDHaWGyw8lacx65hcM0
QM3uRw2iaaCyCkCnuO+k19fX4ZMXOD7cLN/Qrql8Efx5mczcoGN+Eo6FF+
cvgXfupe1VM6PmJdFIauJerTHUOlPrI12N+NnAL7CvU6X1nhOnf/Z77iz| )
(p |APesjZ8gK4RGV5Qs1eCRAVp7mVblgf13R5fwApw6bTVWzunIwk/2sShyy
tpc90edr+0DPwldnvEXTUY1df0DwPc=|)
(q |ANjPQe6O0Jfv90GWE3q2c9724AX7FKx64g2F8lxgiWW0QKEeqiWiiEDx7
qh0lLrhmBT+VXEDFRG2LHmuNSTzj7M=|)
(a |AKUds79qx62EOmLIjpW2AOb9EOSZAVOk2mVKrGgm83jkifEwgYqkdhr3M
ebopNppH/NXf1uTv0tk3i7OTqitK08=|)
(b |AJCKK/RfNbqf+iu5YlHO9+n56q6nYx2nQV5ZTD2VsO54KxYUcW5sWtX2n
xr4YydBEA3+46CsuLZ5cvvJeMNNCnc=|)
(c |CIPwAAO8Vmj0/BfCtsg+35+r94jwxGYHZ63RsqyNxbvkAO6xPqSht8/vz
dR93eX5B9ZKBQg1HHWCsHbqQtmNLQ==|))
where a, b and c are CRT parameters.
Ellison, et al. [Page 32]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.2.2 <sec-key>
<sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>? ")" ;
4.2.2.1 HMAC-MD5
Example:
(secret-key hmac-md5 (k |ksTt2Lu9NSq3mGHJ7HmuksSYwFQ=|) )
which has a base64 encoded canonical form:
{KDEwOnNlY3JldC1rZXk4OmhtYWMtbWQ1KDE6azIwOpLE7di7vTUqt5hhyex
5rpLEmMBUKSk=}
The hmac-md5 and hmac-sha1 algorithms are defined in [RFC2104].
4.2.2.2 DES-CBC-MAC
Example:
(secret-key des-cbc-mac (k |52Lyr9BPTSM=|)
(nonce |v1jBW9SlFxAweNyYSzaMfHOzwds=|))
with base64 encoded canonical form
{KDEwOnNlY3JldC1rZXkxMTpkZXMtY2JjLW1hYygxOms4Oudi8q/QT00jKSg
1Om5vbmNlMjA6v1jBW9SlFxAweNyYSzaMfHOzwdspKQ==}
provides the DES key for a DES-CBC MAC. It also includes a nonce
parameter which plays no part in the algorithm, but serves to
insulate this key from brute force attacks using the published hash
of the (secret-key...) canonical S-expression:
(hash md5 |ilTuqvT5/AdeX/sfxA9lgQ==| examples/des.bin)
with base64 encoded canonical form
{KDQ6aGFzaDM6bWQ1MTY6ilTuqvT5/AdeX/sfxA9lgTE2OmV4YW1wbGVzL2R
lcy5iaW4p}
Ellison, et al. [Page 33]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.2.3 <hash>
<hash>:: "(" "hash" <hash-alg-name> <hash-value> <uri>? ")" ;
A <hash> object gives the hash of some other object. For example,
the public key given above has the following hash:
(hash md5 #92e5f2ab1f23616759fe3ed57dfafeca#)
or
(hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|)
which, in base64 encoded canonical form, is
{KDQ6aGFzaDM6bWQ1MTY6kuXyqx8jYWdZ/j7Vffr+yik=}
A hash of the hmac-md5 secret key defined above is:
(hash md5 #33b7035665f7af8c6669bdabc58ab236#)
or
(hash md5 |M7cDVmX3r4xmab2rxYqyNg==|)
which, in base64 encoded canonical form, is
{KDQ6aGFzaDM6bWQ1MTY6M7cDVmX3r4xmab2rxYqyNik=}
This is perhaps of more interest than the hash of the public key
because a certificate generally released to the public can not
contain a secret key, for obvious reasons, but it might contain the
hash of the secret key without fear of loss of the secret.
4.2.4 <signature>
<signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ;
A signature object is typically used for a certificate body and
typically follows that <cert> object in a <sequence>. We chose not
to define an object <signed-cert> containing the cert body and
signature, since there may be cases when the same cert body needs to
be signed by multiple keys.
One can also sign objects other than cert bodies, of course. For
example, the following is the signature of a file.
(signature
Ellison, et al. [Page 34]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
(hash md5 |8dIIGz8bZZpXpX2M/g/aVQ==|)
(public-key
rsa-pkcs1-md5
(e #03#)
(n
|ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTOYTT
lapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yYVDzJ1
DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1|))
|0Q5bkgsDoPlD9zkQo+YEnpmuXwC9REZHDcCoiT9FlzgTw1QPzM0yS0vg7+rG
4HmsHOgZWvgjFY2IWXt1Po2gD9Hjxw6sGl/vTpmjo2NldnONPbzNTJKqEEqh
8SFyuLibu04IdcuicqNGyaBJhuN1leXt29Wn+gHVPtufGCSK670=|)
which is equivalent to
(signature
(hash md5 |8dIIGz8bZZpXpX2M/g/aVQ==|)
(hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==| key2-pub)
|0Q5bkgsDoPlD9zkQo+YEnpmuXwC9REZHDcCoiT9FlzgTw1QPzM0yS0vg7+
rG4HmsHOgZWvgjFY2IWXt1Po2gD9Hjxw6sGl/vTpmjo2NldnONPbzNTJKqE
Eqh8SFyuLibu04IdcuicqNGyaBJhuN1leXt29Wn+gHVPtufGCSK670=|)
or, in base64 encoded canonical form,
{KDk6c2lnbmF0dXJlKDQ6aGFzaDM6bWQ1MTY68dIIGz8bZZpXpX2M/g/aVSk
oNDpoYXNoMzptZDUxNjqS5fKrHyNhZ1n+PtV9+v7KODprZXkyLXB1YikxMjg
60Q5bkgsDoPlD9zkQo+YEnpmuXwC9REZHDcCoiT9FlzgTw1QPzM0yS0vg7+r
G4HmsHOgZWvgjFY2IWXt1Po2gD9Hjxw6sGl/vTpmjo2NldnONPbzNTJKqEEq
h8SFyuLibu04IdcuicqNGyaBJhuN1leXt29Wn+gHVPtufGCSK670p}
As one more example, the signature on the hmac-md5 secret key defined
above, by the public key above, is:
(signature
(hash md5 |M7cDVmX3r4xmab2rxYqyNg==|)
(public-key
rsa-pkcs1-md5
(e #03#)
(n
|ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKT
OYTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/
yYVDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3u
W1|))
|fA9Jhf/YXYgtxHowCDPUBFWDeOgAKNAlfDGq73obef6E1xCYCrpeh/kPr4
V8yoE+eXY+CUQivbQsmKxfcEoxJbCAseDSzvuprZ2jeETDK0ESVhYfGPMyN
vx1pfkL1SQZwFqbf1g3G7obRU6SpPn/A12+IuHRBXKdLtUyFnBMxvE=|)
or, in base64 encoded canonical form:
Ellison, et al. [Page 35]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
{KDk6c2lnbmF0dXJlKDQ6aGFzaDM6bWQ1MTY6M7cDVmX3r4xmab2rxYqyNik
oMTA6cHVibGljLWtleTEzOnJzYS1wa2NzMS1tZDUoMTplMToDKSgxOm4xMjk
6ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTOYT
TlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yYVDzJ
1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1KSkxMjg
6fA9Jhf/YXYgtxHowCDPUBFWDeOgAKNAlfDGq73obef6E1xCYCrpeh/kPr4V
8yoE+eXY+CUQivbQsmKxfcEoxJbCAseDSzvuprZ2jeETDK0ESVhYfGPMyNvx
1pfkL1SQZwFqbf1g3G7obRU6SpPn/A12+IuHRBXKdLtUyFnBMxvEp}
4.2.5 <acl>
<acl>:: "(" "acl" <version>? <acl-entry>* ")" ;
<acl-entry>:: <subj-obj>* <deleg>? <tag> <valid>? <comment>? ;
An ACL is a list of assertions: certificate bodies which don't need
issuer fields or signatures because they are being held in secure
memory. Since the fields of the ACL are fields of a <cert>, we will
not repeat those common field definitions here.
If all the optional fields are left out, the (possible multiple)
subjects are given the permission specified in <tag>, without
permission to delegate it, but forever (until the ACL is edited to
remove the permission).
For example:
(acl
(name (hash md5 |p1isZirSN3CBscfNQSbiDA==|) sysadmin/operators)
(hash md5 |M7cDVmX3r4xmab2rxYqyNg==|)
(tag (ftp db.acme.com root))
(hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|)
(propagate)
(tag (http http://www.internal.acme.com/accounting/))
)
or
{KDM6YWNsKDQ6bmFtZSg0Omhhc2gzOm1kNTE2OqdYrGYq0jdwgbHHzUEm4gw
pMTg6c3lzYWRtaW4vb3BlcmF0b3JzKSg0Omhhc2gzOm1kNTE2OjO3A1Zl96+
MZmm9q8WKsjYpKDM6dGFnKDM6ZnRwMTE6ZGIuYWNtZS5jb200OnJvb3QpKSg
0Omhhc2gzOm1kNTE2OpLl8qsfI2FnWf4+1X36/sopKDk6cHJvcGFnYXRlKSg
zOnRhZyg0Omh0dHA0MDpodHRwOi8vd3d3LmludGVybmFsLmFjbWUuY29tL2F
jY291bnRpbmcvKSkp}
Ellison, et al. [Page 36]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.2.6 <sequence>
<sequence>:: "(" "sequence" <seq-ent>* ")" ;
<seq-ent>:: <cert> | <pub-key> | <signature> | <op> ;
<op>:: <hash-op> | <general-op> ;
<hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ;
<general-op>:: "(" "do" <byte-string> <s-part>* ")" ;
A <sequence> is a bundled sequence of objects which the verifier is
to consider when deciding to grant access. We anticipate requiring
the prover (who constructs and submits the <sequence>) to provide
elements in order, so that the verifier need only process the
<sequence> in order to prove to itself that the prover has the
claimed access right.
The sequence can also contain instructions to the verifier, in the
form of opcodes. At present the only opcode defined is "hash" --
meaning, that the previous item in the sequence (the last one read
in) is to be hashed by the given algorithm and saved, indexed by that
hash value. Presumably, that item (certificate body or public key,
for example) is referred to by hash in some subsequent object.
At this time, we assume that a (signature ) block following a cert
body in a sequence will call for that cert body to be hashed by the
algorithm indicated in the signature.
If an object will be referenced by different hashes, it can be
followed by multiple (do hash ..) opcodes.
4.3 <cert> object
<cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>?
<subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ;
The full SPKI/SDSI 2.0 specification as it has evolved over the past
year has departed somewhat from the original purpose of providing the
simplest possible, bare-bones certificate which is still useful to
Internet developers. It has acquired some features which we now
believe are of extreme value and therefore worth the complexity they
introduce. However, there are still expected to be some developers
who do not need all these additional features.
Ellison, et al. [Page 37]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
A SPKI/SDSI <cert> compliant with this proposed standard fits within
the full BNF given at the end of this draft. A fully "compliant"
verifier would accept all of that possible BNF. However, there may
be developers in closed environments which will never generate
SPKI/SDSI <certs> using all the features presented in the BNF and
using verifier code which can not accept the full set. As an aid in
selecting subsets of the SPKI/SDSI <cert> definition, we offer the
following four sections -- a basic <cert> and three extensions from
the basic which are independent of one another and therefore might be
included or left out as the developer wishes.
However, we urge everyone to consider use of the full definition and
to cut back only if it is obvious that some set of features will
never be needed or that the code required to process some feature can
not fit within the application's design constraints.
For that latter possibility, the developer can consider reducing full
SPKI/SDSI certs to Certificate Result Certs [CRCs] which can easily
be expressed in bare-bones format. It should be kept in mind that a
decision to accept less than the full SPKI cert limits the
certificate chains a verifier can accept without use of an
intermediary CRC engine.
1. Bare-bones SPKI
2. Simple SPKI/SDSI (addition of SDSI names)
3. Tag algebra (addition of the *-form construct)
4. Threshold subjects (addition of multiple-subject forms)
4.3.1 Bare-bones SPKI
A bare-bones SPKI cert is one which uses only principals (not names)
for both issuer and subject, and uses a non-intersectable S-
expression for the tag, to be interpreted by code at the verifier.
It does not permit threshold subjects.
This might show up in actual use as either a special, simple cert for
a specific purpose or as a Certificate Result Cert (CRC). We expect
verifiers which accept only bare-bones SPKI certs to be specialized
applications in closed environments, if any such verifiers are
fielded.
Ellison, et al. [Page 38]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.3.1.1 <version>
<version>:: "(" "version" <byte-string> ")" ;
Version numbers are non-negative and start with #00#. If the
<version> field is missing from an object, it is assumed to be
(version #00#), which is the version of all objects in this draft.
It is assumed that a verifier, when encountering a structure it
doesn't know how to parse (because it has a version number too high),
will ignore that object.
4.3.1.2 <cert-display>
<cert-display>:: "(" "display" <byte-string> ")" ;
This optional field gives a display hint for the entire certificate.
This display parameter does not affect certificate chain reduction,
but is provided to aid user-interface software in certificate
display.
At this time, we have no such hints defined, but we anticipate
allowing the differentiation between a SDSI individual name
definition, SDSI group membership definition, a straight permission
delegation, etc. Possible parameters for this field are left as an
open issue.
4.3.1.3 <issuer>
In the bare-bones SPKI cert, we have:
<issuer>:: "(" "issuer" <principal> ")" ;
<principal>:: <pub-key> | <hash-of-key> ;
and some implementations may prefer to simplify code and allow only
<pub-key> for <principal>. This rules out <sec-key> issuers,
although not a <hash-of-key> field which is the hash of a <sec-key>.
An explicit <sec-key> as an issuer offers no security to the cert.
Ellison, et al. [Page 39]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.3.1.4 <issuer-loc>
<issuer-loc>:: "(" "issuer-info" <uri>* ")" ;
The (issuer-info ) object provides the location of the cert(s) by
which the issuer derives the authority to pass along the
authorization in the present <cert>. We expect the prover (the
calling client) to track down such other certs and provide them to
the verifier (the called server), but we allow this information in
the cert to simplify that process for the prover.
4.3.1.5 <subject>
In the bare-bones SPKI cert, we have:
<subject>:: "(" "subject" <principal> ")" ;
<principal>:: <pub-key> | <hash-of-key> ;
and some implementations may prefer to simplify code and allow only
<pub-key> for <principal>.
4.3.1.6 <subject-loc>
<subject-loc>:: "(" "subject-info" <uri>* ")" ;
This optional field provides the location of information about the
subject. For example, if the subject is a hash of a key, this might
provide the location of the key being hashed.
4.3.1.7 <deleg>
<deleg>:: "(" "propagate" ")" ;
This optional field, if present, notes that the <subject> has not
only the permission given in the <cert>'s <tag> field but also the
permission to delegate that (or some portion of it) to others.
Ellison, et al. [Page 40]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.3.1.8 <tag>
In the bare-bones SPKI cert (and simple SPKI/SDSI cert), the tag
field has no special structure beyond the following:
<tag>:: "(" "tag" "(*)" ")" | "(" "tag" <tag-body> ")" ;
<tag-body>:: <simple-tag> ;
<simple-tag>:: "(" <byte-string> <tag-param>* ")" ;
<tag-param>:: <s-part> ;
The form (tag (*)) means "all permissions".
The <simple-tag> form gives an application-dependent S-expression.
The reduction rule for this simple form is that the S-expression must
match exactly [or must match with a (tag (*))].
4.3.1.9 <valid>
The <valid> field gives validity dates and/or on-line test
information for the cert.
<valid>:: <not-before>? <not-after>? <online-test>? ;
<not-after>:: "(" "not-after" <date> ")" ;
<not-before>:: "(" "not-before" <date> ")" ;
The not-after and not-before options are self-explanatory. If either
is missing, then the cert is assumed valid for all time in that
direction. For example, one might omit the <not-before> field, if
that date would be before or at the time of creation of the cert,
unless one wanted to note the creation time for documentary purposes.
4.3.1.9.1 <date>
<date>:: <byte-string> ;
A date field is an ASCII byte string of the form:
YYYY-MM-DD_HH:MM:SS
Ellison, et al. [Page 41]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
always UTC. For internal use, it is treated as a normal byte string.
For example, "1997-07-26_23:15:10" is a valid date. So is
"2001-01-01_00:00:00". <date> fields are compared as normal ASCII
byte strings since one never needs to compute the size of a time
interval to test validity -- only determine greater-than, less-than
or equal.
4.3.1.9.2 <online-test>
<online-test>:: "(" "online" <online-type> <uri> <principal> <s-
part>* ")" ;
<online-type>:: "crl" | "reval" | "one-time" ;
The online test option allows a cert to be backed up by finer grain
validity testing. The reply from an online test is a digitally
signed object, validated by the <principal> given in the test
specification. That object includes validity dates, so that once one
has the online test response, its validity dates can be intersected
with the parent cert's validity dates to yield the current working
validity dates for the cert.
The crl form tells the verifier (or prover, who fetches this
information for the verifier, in our standard model), the current
list of invalid certs. If the present cert is not on that list, then
the cert is presumed valid.
The revalidate form is the logical opposite of the crl. It tells the
verifier a list of valid certs -- or, just that the current cert is
valid.
The one-time form is a revalidate form without validity dates. It
must be fetched by the verifier, rather than the prover, since it is
valid only for the current verification step. [In effect, it has a
validity period of just "now".] The process of getting this one-time
revalidation involves sending a unique (and partly random) challenge
which is returned as part of the signed response.
See section 6 for a full description of on-line test request and
reply formats.
Ellison, et al. [Page 42]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.3.1.10 <comment>
<comment>:: "(" "comment" <byte-string> ")" ;
This optional field allows the issuer to attach comments meant to be
ignored by any processing code but presumably to be read by a human.
4.3.2 SPKI/SDSI
This level of <cert> fully implements the merged SPKI and SDSI
proposals, except for the <tag> algebra improvement which was
developed after the decision to merge (and which is described below).
The full SPKI/SDSI <cert> involves enhancement of the <issuer> and
<subject> fields, over what was included in the bare-bones SPKI cert.
4.3.2.1 <issuer>
The full form of issuer is:
<issuer>:: "(" "issuer" <issuer-name> ")" ;
<issuer-name>:: <principal> | <simple-name> ;
<simple-name>:: "(" "name" <principal> <byte-string> ")" ;
The additional construct allowed here gives the definition of a SDSI
name in the name space of the issuer. For example,
(cert
(issuer (name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred))
(subject (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|))
(tag (*)) )
or
{KDQ6Y2VydCg2Omlzc3Vlcig0Om5hbWUoNDpoYXNoMzptZDUxNjpPGjPUbEr
+4G8lvHemsiETKTQ6ZnJlZCkpKDc6c3ViamVjdCg0Omhhc2gzOm1kNTE2Ome
acQg+uGMIEtSGOEYetaApKSgzOnRhZygxOiopKSk=}
defines the name "fred" in the name space of the key which hashes to
|Txoz1GxK/uBvJbx3prIhEw==|. It is defined to be the key which hashes
to |Z5pxCD64YwgS1IY4Rh61oA==|. That key acquires all the permissions
which might be delegated to "fred" by name.
Ellison, et al. [Page 43]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
The cert must be signed by the key referenced in the (issuer ), in
this case, the key hashing to |Txoz1GxK/uBvJbx3prIhEw==|.
4.3.2.2 <subject>
The full form of subject (except for k-of-n, described below) is:
<subject>:: "(" "subject" <subj-obj> ")" ;
<subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> |
<keyholder> ;
4.3.2.2.1 <name>
The primary addition to the possibilities for <subject> is a SDSI
name. This can be either a relative name or a fully-qualified name.
<name>:: <relative-name> | <fq-name> ;
<relative-name>:: "(" "name" <names> ")" ;
<fq-name>:: "(" "name" <principal> <names> ")" ;
<names>:: <byte-string> | <names> <byte-string> ;
For evaluation purposes, the relative name is translated into a
fully-qualified name by using the key of the issuer.
Unlike the <issuer> SDSI name, which is forced to be a name in the
issuer's name space, the subject name can be in any name space.
(subject (name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred sam george
mary))
refers through "fred" defined in the name space of
|Txoz1GxK/uBvJbx3prIhEw==|, to reduce to:
(subject (name (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|) sam george
mary))
recursing until the subject reduces to a key. This construct allows
deferred binding of keys to names, while the bare-bones SPKI format
forces binding of keys to names at the time the certificate is
issued. In particular, the owner of any name space involved in such
Ellison, et al. [Page 44]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
a SDSI name chain can replace an existing name definition after the
cert above is issued, without affecting the validity of that cert or
forcing it to be reissued. For that matter, the cert above can be
issued before there is any definition of the referenced name.
4.3.2.2.2 <obj-hash>
<obj-hash>:: "(" "object-hash" <hash> ")" ;
This option for a (subject ) refers to an object other than a
<principal> (or SDSI name reducing to a principal). One might use
this form to assign attributes to an object (a file, a web page, an
executable program, ...).
4.3.2.2.3 <sec-key>
<sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>? ")" ;
A secret key can also be a Principal, in the formal sense, but we do
not permit it to appear explicitly in an <issuer> for obvious
reasons. Most likely, a <cert> using a secret key will use the hash
of the key, so that the cert could be published. In that case, the
builder of <sec-key> may be well advised to include a (nonce ...)
field, unused by the secret-key algorithm but hiding any key value
from brute force searches via the published hash value.
It is also possible to have split secret keys, as is popular in some
banking applications: e.g.,
(secret-key des3-split-4
(a #ba1c9bd4#) (b #e747105c#) (c #7f62536b#) (d #0fa235f9#)
)
could define a 2-key triple-DES key, in four parts. This key could
be split among 4 different parties, via the S-expressions:
(secret-key des3-split-4 (a #ba1c9bd4#) (nonce #5b30e629#) )
(secret-key des3-split-4 (b #e747105c#) (nonce #a5e71fe3#) )
(secret-key des3-split-4 (c #7f62536b#) (nonce #3c317d99#) )
(secret-key des3-split-4 (d #0fa235f9#) (nonce #7597d39e#) )
and each of those 4 partial keys could be given to a different party
to hold, together with a certificate referring to the part by its
hash, verifying its authenticity and its intended mode of use. That
Ellison, et al. [Page 45]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
certificate might also include a key serial number as part of its tag
field.
4.3.2.2.4 <keyholder>
<keyholder>:: "(" "keyholder" <principal> ")" ;
This form of subject refers to the flesh and blood (or iron and
silicon) holder of the referenced key. A <cert> with such a subject
is saying something about that person or machine -- such as its
location, its address, its age, its weight, its height, its picture,
....
4.3.2.3 <subject-loc>
<subject-loc>:: "(" "subject-info" <uri>* ")" ;
This optional field might give the location of SDSI name cert servers
to help the prover (the client code), which is building a list of
certs to present to the verifier, to find those certs.
4.3.3 Tag algebra
This extension to bare-bones SPKI/SDSI provides a means for
expressing sets of permissions (or ranges of parameters) so that a
standard, simple algorithm in the verifier can intersect tag fields
of two adjacent <certs> to yield the permission of the combination.
When a verifier is equipped to do tag algebra using "*-forms", as we
expect standard verifiers to be, cert chains can be expressed which
delegate only a sub-portion of one's permissions.
When composing certificate chains, the tag fields are automatically
intersected by a standard intersection algorithm. The user does not
have to specify an intersection algorithm for his tags, but he does
have to write his tags in such a way that the standard intersection
algorithm gives the desired behavior.
Ellison, et al. [Page 46]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.3.3.1 *-forms
An S-expression of the form ( * ... ) is called a "*-form".
An S-expression that does not contain any *-forms (at any level) is
called a "*-free" S-expression. (Byte strings are *-free.) *-free
S-expressions are significant because we assume that elementary
authorizations (permissions, or rights) are expressed as *-free S-
expressions. The simplest form of a certificate has a tag that is
*-free. [Bare-bones SPKI/SDSI certs have *-free tags.]
The intersection of two *-free S-expressions s1 and s2 is either s1
(if s1 and s2 are identical), or null otherwise.
Other S-expressions are called "variable" S-expressions.
Every S-expression (T) (*-free or not) is understood to represent a
set m(T) of *-free S-expressions. Each of those *-free tags has a
meaning and that meaning is defined by the verifier code.
A variable S-expression may represent a large set of *-free S-
expressions. The use of *-forms allows one to denote such a set
efficiently.
Issuing a certificate with tag T (i.e. with field (tag T)) has the
same effect as issuing a separate certificate with tag T' for every
element T' of m(T). That is, the elements of m(T) are assumed to
have meanings which are permissions or capabilities and the meaning
of m(T) is the union of the permissions of the elements of m(T).
A certificate chain with tags T1, ..., Tk reduces to a result
certificate with a meaning that is the intersection of
m(T1),...,m(Tk).
4.3.3.1.1 Sets of S-expressions
Here are some simple *-forms, operating on whole S-expressions:
(*) whose meaning is the set of all S-expressions
(* null) whose meaning is the empty set
(* set s1 ... sk) whose meaning is just the union of the meanings
m(s1), ..., m(sk)
(* intersect s1 ... sk) whose meaning is just the intersection of the
meanings m(s1),...,m(sk)
The (* null) expression is unlikely to occur in a certificate tag,
Ellison, et al. [Page 47]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
but is useful to have as part of the algebra of *-forms. The (*
intersect) form is also not expected to occur in a certificate. It
is defined for completeness. [In some cases, it can ease the
programming of the *-form intersection software by permitting it to
postpone an intersection. This is because it is always easy to
intersect a *-free form with a *-form and the final result of a
verification step is almost certainly a *-free form.]
One can also build sets of S-expressions by reordering, adding or
deleting parts:
( * append s ) -- represents all S-expressions that can be obtained
by appending additional elements to the end of list s.
Example:
T1 = ( tag ( * append ( ftp "abc.com" )))
allows there to be additional elements at the end of the ftp list
after "abc.com".
( * reorder s )
( * reorder-insert s )
( * reorder-delete s )
These represent the set of S-expressions you can get from s by re-
ordering the elements of s (other than the first) and possibly
inserting new elements, or deleting some elements (other than the
first).
For example, (* reorder (rsa (n #44#)(e #03#))) allows the n and e
fields to be given in either order.
Or, the meaning of (* reorder-insert (a (b "4")(c "5"))) includes (a
d (c "5") e f (g "23") (b "4"))
The (* reorder) family of constructs is good when the elements of the
list are indexed by keywords or list type, rather than by position,
while the (* append) construct is good for positional tag forms.
4.3.3.1.2 S-expressions with *-form parts
An s-expression can be written that is not a *-form, but which
contains *-forms:
Let s denote the list
(s1 s2 ... sk) (where s1 is not *)
Then m(s) is the set
Ellison, et al. [Page 48]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
{ ( t1 ... tk ) : each ti is an element of m(si) }
That is, the meaning of a list is the cross product of the meanings
of its elements.
For example:
if s = ( W (* set a b) (* set c d e) )
then m(s) = { (W a c) (W a d) (W a e) (W b c) (W b d) (W b e) }
If s is the list (s1 ... sk) and s' is the list (s1' ... sk') (where
s1 and s1' are not *), then
(* intersect s s')
has the same meaning as
((* intersect s1 s1') ... (* intersect sk sk'))
The meaning of an intersection of lists is the list of intersections
of their meaning.
[example] Consider the tag
T1 = (tag (spend-from "45123"))
Here 45123 is an account number at the bank. Since this is *-free,
the intersection of T1 with the tags from other certificates in a
certificate chain can only yield either T1 or (* null).
Consider now the variable S-expression of the form
T2 = (tag (spend-from (* set "45123" "11112")))
This is intended to denote an authorization to spend from either
account 45123 or account 11112.
Alice can delegate to Bob the authority to spend from either account
using tag T2, and Bob can delegate to Charles the ability to spend
from account 45123 only using tag T1. This works properly
automatically, since
(* intersect T1 T2) = T1
because
(* intersect tag tag) = tag
(* intersect spend-from spend-from) = spend-from
(* intersect "45123" (* set "45123" "11112")) = "45123"
Here are two simple *-forms representing sets of byte strings:
(* prefix "abc") -- represents the set of byte strings having
"abc" as a prefix.
Example of use:
T1 = (tag (http (* prefix "http://abc.com/")))
This can be automatically intersected with
T2 = (tag (http (* prefix "http://abc.com/accounting")))
to yield
Ellison, et al. [Page 49]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
T2 = (tag (http (* prefix "http://abc.com/accounting")))
(* range <order> <lower-limit>? <upper-limit>? )
where <order> is one of "alpha", "numeric", "time" or "binary" and
<lower-limit> ::= (<ge-or-geq> <byte-string>)
<ge-or-geq> ::= "g" | "ge" ;
<upper-limit> ::= (<le-or-leq> <byte-string>)
<le-or-leq> ::= "l" | "le"
"alpha" restricts the set to byte strings, with left-justified
comparisons
"numeric" restricts the set to ASCII strings representing positive or
negative numbers (possibly with a decimal point and following digits)
"time" restricts the set to ASCII strings representing times (apart
from their dates)
"binary" restricts the set to binary strings representing numbers,
that is byte strings with right-justified comparisons and sign taken
from the most significant bit.
Examples of use:
T1 = (tag (spend-amount (* range numeric (l "5000")) USD ))
authorizes someone to spend up to 5000 US dollars.
T2 = (tag (login cybercash.com cme (time (* range time (ge
"04:00:00") (le "12:00:00")))))
authorizes the keyholder to login on cybercash.com as user cme during
the hours 4 am to noon UTC.
4.3.3.1.3 *-form reduction
It is possible to recursively work out the intersections for tags
using *-forms in an automatic manner. For example, the intersection
of
(tag (spend (amount (* range numeric (l "5000"))) (account (* set
"12345" "67890")) (* reorder-insert (for socks shirt pants))))
and
(tag (spend (amount (* range numeric (l "1000"))) (account (* set
"87654" "12345")) (for tie pants socks belt shirt)))
is
(tag (spend (amount (* range numeric (l "1000"))) (account "12345")
(for tie pants socks belt shirt)))
Ellison, et al. [Page 50]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Note that *-forms can be used to get the effect of multiple tags per
certificate; a certificate with tag
( tag ( * set T1 T2 ... Tk ) )
is entirely equivalent to a set of separate certificates with tag
fields T1, T2, etc. However, we should point out that if too many
permissions are accumulated in a single certificate, then the
certificate itself forms a kind of dossier on the keyholder which
might be considered a privacy violation.
4.3.3.2 <tag> *-form BNF
The *-form algebra above is expressed in BNF as:
<tag>:: "(" "tag" <tag-body> ")" ;
<tag-body>:: <simple-tag> | <list-set> ;
<list-set>:: <impl-list-set> | <list-union> | <list-intersect> |
<misc-set> ;
<impl-list-set>:: "(" "*" <list-set-type> <tag-body> ")" ;
<list-set-type>:: "append" | "reorder" | "reorder-insert" | "reorder-
delete" ;
<list-union>:: "(" "*" "set" <tag-body>* ")" ;
<list-intersect>:: "(" "*" "intersect" <tag-body>* ")" ;
<misc-set>:: <all-set> | <null-set> ;
<all-set>:: "(" "*" ")" ;
<null-set>:: "(" "*" "null" ")" ;
<simple-tag>:: "(" <byte-string> <tag-param>* ")" ;
<tag-param>:: <s-part> | <string-set> ;
<string-set>:: <prefix-set> | <range-set> | <string-union> | <string-
intersect> | <misc-set> ;
<prefix-set>:: "(" "*" "prefix" <byte-string> ")" ;
Ellison, et al. [Page 51]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
<range-set>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>?
")" ;
<range-ordering>:: "alpha" | "numeric" | "time" | "binary" ;
<low-lim>:: <gte> <byte-string> ;
<gte>:: "g" | "ge" ;
<up-lim>:: <lte> <byte-string> ;
<lte>:: "l" | "le" ;
<string-union>:: "(" "*" "set" <byte-string>* ")" ;
<string-intersect>:: "(" "*" "intersect" <byte-string>* ")" ;
4.3.4 Threshold subjects
A threshold subject, introduced by Tatu Ylonen for SPKI and by Rivest
and Lampson in SDSI 1.0, specifies N subjects for a certificate or
ACL entry, of which K must agree before the permission is passed
along.
The actual intent is to insure that there are K distinct paths
passing permission between the verifier's ACL and the prover's
request. These multiple paths branch and re-join, so the k-of-n
construct could theoretically be part of either the Subject or the
Issuer. Since an ACL might want to specify these multiple paths (and
an ACL has no Issuer) and since a cert is signed by a single Issuer,
we have chosen to specify the branching at the Subject.
A certificate or ACL with a k-of-n Subject does not delegate
permission to any of those subjects, alone. Only if at least K of
the N subjects show certificate paths which converge on a single
target Subject during reduction, is that permission transmitted to
the target. If fewer than K such paths can be shown, then the
permission is blocked.
The first reaction is that this is far from simple. However, it is
extremely useful. It has been demanded by a number of initial
customers of SPKI certificates. It also solves a number of sticky
political problems. This section lays out the specification of K-of-
N subjects. The rules for reducing 5-tuples containing such entries
are given below in Section 7.
Ellison, et al. [Page 52]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
4.3.4.1 Examples
Examples of the use of K-of-N permission propagation include:
1. co-signing of electronic corporate checks or purchase orders
above a certain amount
2. establishing the root DNSSEC key, bypassing the political battles
which would inevitably ensue if one country were to hold *the*
root key for the entire world. The same goes for any root key.
3. establishing a root key for a trusted service, via multiple
algorithms. That is, one could have three root keys, using RSA,
DSA and Elliptic Curve signature algorithms (for example), and
require that two of them yield a valid chain. This way, if
someone were to break an entire algorithm (find a way to invert
the algorithm), much less if someone were to break one key in the
set of three, the root remains securely established. At the same
time, there is fault tolerance. In case one of the keys is
revoked, the following certificates remain empowered.
4. using online and off-line issuers. One could have a permission
established by an off-line key issuing a long-lived certificate
and echoed by an online automated server, issuing short-lived
certificates. The delegation of this permission could require
both before the eventual subject gets the permission. This can
be achieved through the use of (online ) tests in a long-lived
certificate, but the K-of-N subject mechanism may be cleaner.
5. ultra-secure applications. There are many applications which
follow the nuclear weapons launch scenario. That is, multiple
agreement is required before the permission is granted.
4.3.4.2 Definition
<subj-thresh>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ;
where the first int is K and the second is N, K < N, and there are N
<subj-obj> subjects listed.
The processing of certs and ACLs (therefore 5-tuples) using k-of-n
subjects is presented below in section 7.5.
Ellison, et al. [Page 53]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
5. Examples
The <tag> fields listed here are not meant to be an exhaustive list
of all possible <tag>s. Such is not possible. The final arbiter of
what needs to be an <tag> and what parameters a particular <tag>
needs is the designer of the code which verifies a certificate, e.g.,
to grant access. Listed here are <tag> fields we suspect might be
useful and we present these here as a guide to the developer's
imagination.
5.1 ftp tag
(tag (ftp cybercash.com cme ))
This <tag> indicates that the Subject has permission to do FTP into
host cybercash.com as user cme.
5.2 http tag
(tag (http http://acme.com/company-private/personnel/ ))
This <tag> gives the Subject permission to access web pages which
start with the given URI.
5.3 telnet tag
(tag (telnet clark.net cme ))
This <tag> gives the Subject permission to telnet into host clark.net
as user cme.
5.4 Public Key Protected File System tags
(tag (pkpfs //<host-name>/<path> <access> ))
(tag (pkpfs (* prefix //<host-name>/<path>/) <access> ))
refers to a hypothetical distributed file system whose access is
controlled by public key challenge/response. The first form gives
access to a single file or a small set of files (by use of "*" in the
file name) while the second form gives access to an entire sub-
Ellison, et al. [Page 54]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
directory.
<access> is a (* set ...) whose elements are chosen from:
(read) (write) (append) (delete) (execute)
5.5 Authority to spend money
(tag (spend <bank> <account> (* range le <amount> )))
indicates that the subject has authority to authorize spending up to
<amount> per electronic check from <account> at <bank>.
5.6 Process Server cert
A process server certificate, mentioned in Section 3.5.5.2, might
have the form:
(cert
(issuer (hash md5 |u2kl73MiObh5o1zkGmHdbA==|))
(subject (keyholder (hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==| key2-pub)))
(tag (tracking-fee "150" USD))
(not-after "2003-01-01_00:00:00")
)
{KDQ6Y2VydCg2Omlzc3Vlcig0Omhhc2gzOm1kNTE2OrtpJe9zIjm4eaNc5Bp
h3WwpKSg3OnN1YmplY3QoOTprZXlob2xkZXIoNDpoYXNoMzptZDUxNjqS5fK
rHyNhZ1n+PtV9+v7KODprZXkyLXB1YikpKSgzOnRhZygxMjp0cmFja2luZy1
mZWUzOjE1MDM6VVNEKSkoOTpub3QtYWZ0ZXIxOToyMDAzLTAxLTAxXzAwOjA
wOjAwKSk=}
noting in its tag field that it will serve papers on the indicated
Keyholder for a tracking fee of $150 until the beginning of 2003.
5.7 PICS-like ratings cert
(cert
(issuer (hash md5 |Ut9m14byPzdbCNZWdDjNQg==|))
(subject
(object-hash
(hash md5 |vN6ySKWE9K6T6cP9U5wntA==|
http://www.clark.net/pub/cme/home.html)))
(tag (ratings (sex "0") (violence "0") (crypto "6"))))
Ellison, et al. [Page 55]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
{KDQ6Y2VydCg2Omlzc3Vlcig0Omhhc2gzOm1kNTE2OlLfZteG8j83WwjWVnQ
4zUIpKSg3OnN1YmplY3QoMTE6b2JqZWN0LWhhc2goNDpoYXNoMzptZDUxNjq
83rJIpYT0rpPpw/1TnCe0Mzg6aHR0cDovL3d3dy5jbGFyay5uZXQvcHViL2N
tZS9ob21lLmh0bWwpKSkoMzp0YWcoNzpyYXRpbmdzKDM6c2V4MTowKSg4OnZ
pb2xlbmNlMTowKSg2OmNyeXB0bzE6NikpKSk=}
5.8 Virus checking cert
(cert
(issuer (hash md5 |Ut9m14byPzdbCNZWdDjNQg==|))
(subject
(object-hash
(hash md5 |szKSlSK+SNzIsHH3wjAsTQ==| runemacs.exe)))
(tag virus-free))
{KDQ6Y2VydCg2Omlzc3Vlcig0Omhhc2gzOm1kNTE2OlLfZteG8j83WwjWVnQ
4zUIpKSg3OnN1YmplY3QoMTE6b2JqZWN0LWhhc2goNDpoYXNoMzptZDUxNjq
zMpKVIr5I3MiwcffCMCxNMTI6cnVuZW1hY3MuZXhlKSkpKDM6dGFnMTA6dml
ydXMtZnJlZSkp}
5.9 Full sequence, with donation cert
For one full example of a real certificate, the following sequence
presents the public key used, calls for the verifier to hash it (and
store it away, to be referred to later by its hash), gives a
certificate body and then a signature (which by side-effect calls for
the previous object to be stored and hashed by the signature
algorithm's hash function). The example used is a temporary donation
cert.
(sequence
(public-key
rsa-pkcs1-md5
(e #03#)
(n
|AKMbo+VBqLu+90l2UuuGquzxLIXpqIypkSkrfEVprA0K2Vfm5ufmNZG3
0yWqdnXlxdGuyyBglj+FloXTrqHWSQQJfvTv5EMBz+icJ2GMbjtP1zCY8
krmchh5v/O3BntEwaq1hkMtmP+ZeFjI5yQ/YC2vVc5K1PTy+GOSP+xvYK
C1|))
(do hash md5)
(cert
(issuer (hash md5 |Z4a6hysK/0qN0L5SFkcJFQ==|))
(subject
(keyholder (hash md5 |Z4a6hysK/0qN0L5SFkcJFQ==|)))
Ellison, et al. [Page 56]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
(tag
(*
set
(name "Carl M. Ellison")
(street "207 Grindall St.")
(city "Baltimore MD 21230-4103")))
(not-after "1997-08-15_00:00:00"))
(signature
(hash md5 |PC4M1LNpkMHtgacc73ch5A==|)
(hash md5 |Z4a6hysK/0qN0L5SFkcJFQ==| cme.key)
|PQkhssqNW191aVwNR9DflDQemWf/E2maSdIk/5GulzRB7cjagEn9FqI9J
vGOTkqT5miJmsFx9pY5nXQxp+tJZdwLYeSEA3iAzjcwBY1qG+DQqpWu2AC
JqSnnKmo6kh8KbbySNtCbpguNJs2WM/eRBdkph/AUjTkqe0Xnv/mKEXA=|
))
with canonical form encoded in base 64:
{KDg6c2VxdWVuY2UoMTA6cHVibGljLWtleTEzOnJzYS1wa2NzMS1tZDUoMTp
lMToDKSgxOm4xMjk6AKMbo+VBqLu+90l2UuuGquzxLIXpqIypkSkrfEVprA0
K2Vfm5ufmNZG30yWqdnXlxdGuyyBglj+FloXTrqHWSQQJfvTv5EMBz+icJ2G
MbjtP1zCY8krmchh5v/O3BntEwaq1hkMtmP+ZeFjI5yQ/YC2vVc5K1PTy+GO
SP+xvYKC1KSkoMjpkbzQ6aGFzaDM6bWQ1KSg0OmNlcnQoNjppc3N1ZXIoNDp
oYXNoMzptZDUxNjpnhrqHKwr/So3QvlIWRwkVKSkoNzpzdWJqZWN0KDk6a2V
5aG9sZGVyKDQ6aGFzaDM6bWQ1MTY6Z4a6hysK/0qN0L5SFkcJFSkpKSgzOnR
hZygxOiozOnNldCg0Om5hbWUxNTpDYXJsIE0uIEVsbGlzb24pKDY6c3RyZWV
0MTY6MjA3IEdyaW5kYWxsIFN0LikoNDpjaXR5MjM6QmFsdGltb3JlIE1EIDI
xMjMwLTQxMDMpKSkoOTpub3QtYWZ0ZXIxOToxOTk3LTA4LTE1XzAwOjAwOjA
wKSkoOTpzaWduYXR1cmUoNDpoYXNoMzptZDUxNjo8LgzUs2mQwe2BpxzvdyH
kKSg0Omhhc2gzOm1kNTE2OmeGuocrCv9KjdC+UhZHCRU3OmNtZS5rZXkpMTI
4Oj0JIbLKjVtfdWlcDUfQ35Q0Hpln/xNpmknSJP+Rrpc0Qe3I2oBJ/RaiPSb
xjk5Kk+ZoiZrBcfaWOZ10MafrSWXcC2HkhAN4gM43MAWNahvg0KqVrtgAiak
p5ypqOpIfCm28kjbQm6YLjSbNljP3kQXZKYfwFI05KntF57/5ihFwKSk=}
Ellison, et al. [Page 57]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
6. On-line test reply formats
Given here is the BNF for on-line test replies. This section does
not give details of protocols for connecting to online servers or
transmitting messages between them. It is assumed that, for example,
the requester can provide a URI and use HTTP, while the URI includes
any parameters the requester needs to pass along. The reply from the
on-line source will be in canonical form, according to the BNF given
below. If a protocol is used other than HTTP, the (online ...)
object includes optional <s-part> fields which can be used to hold
parameters for those tests (e.g., indicating which certificate is of
interest, how to authenticate to the server, etc.).
6.1 CRL and delta-CRL
The full or delta CRL is:
<crl>:: "(" "crl" <version> <hash-list> <valid> ")" ;
<hash-list>:: "(" "canceled" <hash>* ")" ;
<delta-crl>:: "(" "delta-crl" <version> <hash-of-crl> <hash-list>
<valid> ")" ;
<hash-of-crl>:: <hash> ;
and should be signed by the principal indicated in the (online...)
field which directed the CRL to be fetched.
The CRL request can be a straight HTTP transaction, using the URI
provided in the cert, but we do not specify online protocols in this
draft.
If the verifier has a complete CRL, then it can provide the hash of
that CRL in whatever protocol is chosen and get back just the
additions to the previous CRL, in the form of a <delta-crl>
6.2 Revalidation
<reval>:: "(" "reval" <version> <subj-hash> <valid> ")" ;
<subj-hash>:: "(" "cert" <hash> ")" ;
This construct specifies the hash of the current cert as <subj-hash>
Ellison, et al. [Page 58]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
and gives a new validity period for that cert. It should be signed
by the <principal> indicated in the (online...) field which directed
it to be fetched.
The reval request can be a straight HTTP transaction, using the URI
provided in the (online...) field, but we do not specify online
protocols in this draft.
6.3 One-time revalidation
For one-time revalidation, the verifier itself must fetch the (reval
) record, which will have the form:
<reval>:: "(" "reval" <version> <subj-hash> <one-valid> ")" ;
<one-valid>:: "(" "one-time" <byte-string> ")" ;
with the byte string inside <one-valid> being one provided by the
caller, expected to be unique over time and unguessable -- e.g., a
large random number or random number plus sequence number. This
reply should be signed by the <principal> indicated in the (online..)
field which directed it to be fetched.
This result, if successful, yields a Validity value for the 5-tuple
of "now".
Ellison, et al. [Page 59]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
7. 5-Tuple Reduction (full)
This section describes the operation of the trust evaluation
machinery assumed to be part of every verifier which accepts SPKI
certificates. The inputs to that trust engine are 5-tuples and any
kind of certificate, not just SPKI, as well as Access Control List
(ACL) entries can be translated to 5-tuples so that they can all
participate in the trust engine decision process.
A 5-tuple is an internal construct and therefore best described by a
programming language data structure. A separate document will give
the 5-tuple reduction code and those data structures.
For this purpose, we describe the content in BNF, but want to make
sure that a 5-tuple will never be expressed in canonical BNF form,
transmitted in that form, etc. The <5-tuple> differs from a <cert>
by leaving out some fields and by augmenting the possibilities for
<issuer>. This latter is because there are intermediate states in
which the issuer holds a full SDSI name -- a state not allowed in
normal <cert>.
7.1 <5-tuple> BNF
A 5-tuple is a positional construct of the form:
<5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ;
<issuer5>:: <key5> | <fq-name5> | "self" ;
<subject5>:: <key5> | <fq-name5> | <obj-hash> | <keyholder> |
<threshold-subj> ;
<deleg5>:: "t" | "f" ;
<key5>:: <pub-key> | <sec-key> ;
<fq-name5>:: "(" "name" <key5> <names> ")" ;
<valid5>:: <valid> | "null" ;
<tag-body5>:: <tag-body> | "null" ;
Standard implementations are expected to store keys (and other bulky
things) only once and refer to them by pointer. This permits us to
use keys directly rather than hashes of keys while doing 5-tuple
reduction. This also permits us to reduce certs which used the same
Ellison, et al. [Page 60]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
key but referred to it by different hash algorithms.
The extra option for issuer, "self", is provided for ACL entries.
The self referred to is the verifier, holding that ACL and doing the
verification of offered proofs.
The only 5-tuples which mean anything to the verifier, after
reduction is done, are those with "self" as issuer.
7.2 Bare-bones case
A bare-bones SPKI cert is reduced as described above in section
3.3.1. The only issuer and subject fields allowed are principals
which are keys. The tag fields a_i are *-free S-expressions or the
form (tag *).
<i1,s1,d1,a1,v1> + <i2,s2,d2,a2,v2> yields <i1,s2,d2,a,v> if:
s1 = i2
d1 = "t"
a = (* intersect a1 a2)
v = the intersection of v1 and v2
Validity intersection involves normal intersection of date ranges, if
there are not-before or not-after fields in v1 or v2, and union of
on-line tests, if those are present in v1 or v2. Each on-line test
includes a validity period, so there is a resulting validity interval
in terms of dates. This can include the string "now", as the product
of a one-time on-line test result. "now" intersects with any date
range including the present to yield "now". If v is an empty time
interval, then the certificates don't reduce.
a = (* intersect a1 a2) in the bare-bones case is given by the
following rules:
If a1 is (tag (*)), a = a2.
If a2 is (tag (*)), a = a1.
If a1 == a2, a = a2.
Otherwise, a = (* null) and the 5-tuple doesn't reduce.
Ellison, et al. [Page 61]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
7.3 Intersection of *-form tag sets
The intersection of *-forms was presented above in section 4.3.3.1 by
way of examples. The full rules are presented below. Via these
rules any (tag)s can be intersected, but in actual practice it will
probably be the case that intersection will start with a *-free form
which will yield a *-free form for all intermediate results.
However, for theoretical completeness, the following rules are
provided:
S, T: *-free S-expressions, assumed unequal
A, B, C, D, E, F: byte-strings, assumed unequal in display type,
string value or both
U, V, X, Y, Z: any S-expression (*-free or *-form)
X . Y = Y . X
A . A = A
A . B = (* null)
A . U = (* null)
U . U = U
S . T = (* null)
Y . (* set X_1 ... X_n) = (* set Y.X_1 ... Y.X_n)
Y . (* intersect X_1 ... X_n) = (* intersect X_1 ... X_n Y)
= (* intersect Y.X_1 ... Y.X_n)
/* depending on which looks more productive */
/* do the second form if one of those becomes */
/* (* null) or if Y is *-free */
(* set (* null) X_1 ... X_n) = (* set X_1 ... X_n)
(* set (*) X_1 ... X_n ) = (*)
(* intersect (* null) X_1 ... X_n) = (* null)
(* intersect (*) X_1 ... X_n) = (* intersect X_1 ... X_n)
(* set X) = X
(* intersect X) = X
(* intersect X X Y_1 ... Y_n) = (* intersect X Y_1 ... Y_n)
(* set X X Y_1 ... Y_n) = (* set X Y_1 ... Y_n)
Both (* set) and (* intersect) are fully commutative, therefore any
(* null) in a (* intersect) turns the whole result (* null) and any
(* null) in a (* set) can be deleted, for example.
X . (*) = X
X . (* null) = (* null)
Ellison, et al. [Page 62]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
7.3.1 Reduction to (* null) by data type mismatch
If a byte-string is intersected with a list, the result is (* null).
Some *-forms are of one data type or the other, so this can lead to
reductions to (* null) at a high level. Specifically,
(* prefix ...)
(* range ...)
are always byte strings, while
(* append)
(* reorder)
(* reorder-insert)
(* reorder-delete)
are always lists.
7.3.2 Specific intersections
U . (* append X) = U if X is a prefix of U
U . (* reorder X) = U if X is a reordering of U
U . (* reorder-insert X) = U if X is a reordering of a subset of U
U . (* reorder-delete X) = U if X is a reordering of a superset of U
A . (* prefix B) = A if B is an initial substring of A and has the
same display hint as A
A . (* range ...) = A if A is contained within the specified range
and the range limits have the same display hints as A
(* append X) . (* append Y) = (* append Y) if X a prefix of Y
or (* append X) if Y is a prefix of X
or (* null)
(* reorder X) . (* reorder Y) = (* reorder X) if Y is a reordering
of X
(* reorder X) . (* reorder-insert Y) = (* reorder X) if Y is a
reordering of a subset of X
(* reorder X) . (* reorder-delete Y) = (* reorder X) if Y is a
reordering of a superset of X
Ellison, et al. [Page 63]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
(* reorder-insert X) . (* reorder-insert Y) = (* reorder-insert X)
if Y is a reordering of a subset of X
(* reorder-delete X) . (* reorder-delete Y) = (* reorder-delete X)
if Y is a reordering of a superset of X
(* prefix A) . (* prefix B) = (* prefix A) if B is a prefix of A
(* range A B) . (* range C D) = (* range E F) by intersection of
the two linear ranges
7.3.3 Deferred intersections
Note that in every case it is legal to express
X . Y as (* intersect X Y)
if another rule for intersection would involve a great deal of work
or if no rule is given. For example, intersection of sets could
produce a huge set, with no real benefit, assuming that an eventual
*-free form will yield a single element from each set.
7.4 Reduction of SDSI names
By the rules for bare-bones SPKI 5-tuple reduction,
<i1,s1,d1,a1,v1> + <i2,s2,d2,a2,v2> yields <i1,s2,d2,a,v> if:
s1 = i2
d1 = "t"
For the purpose of this section, we consider only the first two
elements of the 5-tuple: the issuer and subject. We also modify the
interpretation of d1 (to incorporate the so-called "stop at key"
condition).
<i1,s1> + <i2,s2> yields <i1,s2> if:
s1 = i2
(d1 = "t") OR (s1 is a name rather than a key)
With the introduction of SDSI names, both Issuer and Subject names
are mapped to fully qualified SDSI names:
(name <key> N_1 .. N_k)
where k can be 0, in which case we have (name <key>).
Ellison, et al. [Page 64]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
An Issuer inside a cert always maps to a single name or single <key>
while a Subject may have a SDSI name chain longer than 1.
The introduction of SDSI names causes this reduction rule to be
modified to become:
<i1,s1> + <i2,s2> yields <i3,s3>
Consider the general case:
<(name k1 r_1 .. r_s),(name k2 n_1 .. n_m)>
+ <(name k2 n_1 .. n_p),(name k3 t_1 .. t_u)>
where n_i is assumed to be the same on both sides of the + operator.
If m = p, then the reduction is:
<(name k1 r_1 .. r_s),(name k3 t_1 .. t_u)>
If m > p, the reduction is:
<(name k1 r_1 .. r_s),(name k3 t_1 .. t_u n_{p+1} .. n_m)>
If m < p, the reduction is:
<(name k1 r_1 .. r_s n_{m+1} .. n_p), (name k3 t_1 .. t_u)>
The following sections give some examples to illustrate this
procedure.
7.4.1 Simple SDSI name reduction
The most basic SDSI case is the definition of a single name as a key:
<(name k1 fred),(name k2)>
One can then do the reduction:
<i3, (name k1 fred sam)>
+ <(name k1 fred),(name k2)> = <i3,(name k2 sam)>
Ellison, et al. [Page 65]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
7.4.2 SDSI name composition with subject name growth
One is not limited to define local names as keys. They can be
defined as other names. For example,
<(name k1 fred), (name k2 joe brother)>
which would lead to the "reduction":
<i3, (name k1 fred sam)>
+ <(name k1 fred), (name k2 joe brother)>
= <i3, (name k2 joe brother sam)>
With this form of SDSI name definition allowed, any flood-style
5-tuple reduction software must be careful to detect and not allow
infinite loops of names. Current plans for 5-tuple reduction call
for the prover to drive the verifier with a fixed sequence, in which
case this is not an issue.
7.4.3 SDSI Name composition with issuer name growth
It is possible to imagine a pairing of 5-tuples in which the issuer
name grows beyond 1 name. Start with the three 2-tuples:
<(name k4),(name k1 alice joe)>
+ <(name k1 alice), (name k2)>
+ <(name k2 joe), (name k3)>
If we group the reduction from the left, we get
<(name k4), (name k2 joe)>
+ <(name k2 joe), (name k3)> = <(name k4),(name k3)>
However, if we group from the right, we get
<(name k1 alice), (name k2)>
+ <(name k2 joe), (name k3)> = <(name k1 alice joe), (name k3)>
and
<(name k4),(name k1 alice joe)>
+ <(name k1 alice joe), (name k3)> = <(name k4),(name k3)>
The result is the same, but there is an intermediate result in which
the issuer name grows. As in the previous example, we will need to
be careful to make sure to detect and prohibit infinite loops of name
Ellison, et al. [Page 66]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
growth in this case.
7.5 Reduction of (subject (threshold ..))
There are at least two ways to reduce a set of certificates including
a (subject (threshold ...)): from left to right and from right to
left.
7.5.1 Left-to-right
One plan for processing of k-of-n subjects introduces new opcodes for
the (do ...) construct. Let us assume K=7 and N=12. We assume a
primary "stack" for 5-tuples which never exceeds a depth of 2 for
other reductions, but needs to be a real stack for this one.
(cert ... (k-of-n ...))
arrives and is held on a separate stack.
(do subject #01#)
pulls a copy of the k-of-n cert from the separate stack and activates
subject #1. So, the k-of-n 5-tuple acts like a normal, single-
subject 5-tuple. It acquires a record noting which subject is
active, so that at eventual reduction time, the code can verify that
K different subjects were used.
Normal 5-tuple reduction proceeds until the reduced subject field is
the merge point of these K separate threads of certificates. Then
the opcode
(do subject #02#)
brings one copy of the k-of-n 5-tuple from the top of the auxiliary
stack and selects another subject. At this point, another thread can
be reduced to the common (merge-point) subject.
Whenever two threads have been reduced to 5-tuples on the primary
stack, the opcode
(do k-of-n)
merges the top 2 items of the primary 5-tuple stack, verifying that
their reduced subjects are equal and intersecting their tag and
Ellison, et al. [Page 67]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
validity fields. At the end of the K thread reductions, the final
(do k-of-n)
yields the final result 5-tuple from the K different threads. At
this point,
(do pop-aux)
pops the k-of-n 5-tuple from the auxiliary stack.
7.5.2 Right-to-left
If we choose to process k-of-n certs right-to-left, then all K cert
threads to the right of the k-of-n cert are processed first. This
requires the opcode:
(do push)
to move the current (R-to-L) 5-tuple result to the top of the
auxiliary stack.
(do copy)
copies the current 5-tuple from the top of the auxiliary stack to the
top of the normal stack and normal cert processing proceeds, up to
the point where the k-of-n cert would be required. At this point,
another
(do copy)
fetches another copy of the right end of this thread (the merge
point) and another cert thread is processed.
When all K threads are processed, the k-of-n cert is presented, the
auxiliary stack is popped, and the k-of-n cert combines with the K
5-tuples on the stack below it, to yield a single 5-tuple or a "null"
result. At this point, each of the K 5-tuples on the stack below the
k-of-n cert will have to have the same subject field and an issuer
field to match one of the k-of-n cert's subject fields.
Ellison, et al. [Page 68]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
8. Full BNF
In the BNF to follow, top level constructs are: <sequence>, <cert>,
<pub-key>, <signature>.
<acl-entry>:: <subj-obj>* <deleg>? <tag> <valid>? <comment>? ;
<acl>:: "(" "acl" <version>? <acl-entry>* ")" ;
<all-set>:: "(" "*" ")" ;
<byte-string>:: <bytes> | <display-type> <bytes> ;
<bytes>:: <decimal> ":" {binary byte string of that length} ;
<cert-display>:: "(" "display" <byte-string> ")" ;
<cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>?
<subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ;
<comment>:: "(" "comment" <byte-string> ")" ;
<date>:: <byte-string> ;
<ddigit>:: "0" | <nzddigit> ;
<decimal>:: <nzddigit> <ddigit>* ;
<deleg>:: "(" "propagate" ")" ;
<display-type>:: "[" <bytes> "]" ;
<fq-name>:: "(" "name" <principal> <names> ")" ;
<general-op>:: "(" "do" <byte-string> <s-part>* ")" ;
<gte>:: "g" | "ge" ;
<hash-alg-name>:: "md5" | "sha1" | <uri> ;
<hash-of-key>:: <hash> ;
<hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ;
<hash-value>:: <byte-string> ;
<hash>:: "(" "hash" <hash-alg-name> <hash-value> <uri>? ")" ;
Ellison, et al. [Page 69]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
<impl-list-set>:: "(" "*" <list-set-type> <tag-body> ")" ;
<issuer-loc>:: "(" "issuer-info" <uri>* ")" ;
<issuer-name>:: <principal> | <simple-name> ;
<issuer>:: "(" "issuer" <issuer-name> ")" ;
<k-val>:: <byte-string> ; a binary integer
<keyholder>:: "(" "keyholder" <principal> ")" ;
<list-intersect>:: "(" "*" "intersect" <tag-body>* ")" ;
<list-set-type>:: "append" | "reorder" | "reorder-insert" | "reorder-
delete" ;
<list-set>:: <impl-list-set> | <list-union> | <list-intersect> |
<misc-set> ;
<list-union>:: "(" "*" "set" <tag-body>* ")" ;
<low-lim>:: <gte> <byte-string> ;
<lte>:: "l" | "le" ;
<misc-set>:: <all-set> | <null-set> ;
<n-val>:: <byte-string> ; /* the number of <subj-obj> to follow */
<name>:: <relative-name> | <fq-name> ;
<names>:: <byte-string> | <names> <byte-string> ;
<not-after>:: "(" "not-after" <date> ")" ;
<not-before>:: "(" "not-before" <date> ")" ;
<null-set>:: "(" "*" "null" ")" ;
<nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
<obj-hash>:: "(" "object-hash" <hash> ")" ;
<online-test>:: "(" "online" <online-type> <uri> <principal> <s-
part>* ")" ;
<online-type>:: "crl" | "reval" | "one-time" ;
Ellison, et al. [Page 70]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
<op>:: <hash-op> | <general-op> ;
<prefix-set>:: "(" "*" "prefix" <byte-string> ")" ;
<principal>:: <pub-key> | <hash-of-key> ;
<priv-key>:: "(" "private-key" <pub-sig-alg-id> <s-expr>* <uri>? ")"
;
<pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uri>? ")" ;
<pub-sig-alg-id>:: "rsa-pkcs1-md5" | "rsa-pkcs1-sha1" | "dsa-sha1" |
<uri> ;
<range-ordering>:: "alpha" | "numeric" | "time" | "binary" ;
<range-set>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>?
")" ;
<relative-name>:: "(" "name" <names> ")" ;
<s-expr>:: "(" <byte-string> <s-part>* ")" ;
<s-part>:: <byte-string> | <s-expr> ;
<sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>? ")" ;
<sec-sig-alg-id>:: "hmac-md5" | "hmac-sha1" | "des-cbc-mac" | <uri> ;
<seq-ent>:: <cert> | <pub-key> | <signature> | <op> ;
<sequence>:: "(" "sequence" <seq-ent>* ")" ;
<sig-val>:: <s-part> ;
<signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ;
<simple-name>:: "(" "name" <principal> <byte-string> ")" ;
<simple-tag>:: "(" <byte-string> <tag-param>* ")" ;
<string-intersect>:: "(" "*" "intersect" <byte-string>* ")" ;
<string-set>:: <prefix-set> | <range-set> | <string-union> | <string-
intersect> | <misc-set> ;
<string-union>:: "(" "*" "set" <byte-string>* ")" ;
Ellison, et al. [Page 71]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
<subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> |
<keyholder> | <threshold-subj> ;
<subject-loc>:: "(" "subject-info" <uri>* ")" ;
<subject>:: "(" "subject" <subj-obj> ")" ;
<tag-body>:: <simple-tag> | <list-set> ;
<tag-param>:: <s-part> | <string-set> ;
<tag>:: "(" "tag" "*" ")" | "(" "tag" <tag-body> ")" ;
<threshold-subj>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ;
<up-lim>:: <lte> <byte-string> ;
<uri>:: <byte-string> ;
<valid>:: <not-before>? <not-after>? <online-test>? ;
<version>:: "(" "version" <byte-string> ")" ;
Ellison, et al. [Page 72]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Closed Issues
1) Should we require that all certificates be signed by both Issuer
and Subject, when the Subject reduces to a key? [When the
Subject is a non-key object, it can't sign.]
[Answer: no. Signing by the Subject can not be prevented
so it can be used if a need arises, but at present no
security enhancement is seen to come from Subject signing.
This seems to address the concerns of lawyers only.]
2) Can the Signature object support blind signatures with
algorithms other than RSA?
[Answer: yes -- any algorithm which supports blind
signatures can be used here.]
3) Should we eliminate the final ":" in field names? These are
always the first names in a list and the ":" seems to be a
carry-over from RFC822 without a real purpose.
[Answer: yes.]
4) Should we continue to lump public key algorithm, hash algorithm
and padding algorithm together in one pub-key-name? This could
lead to an explosion of names. Of course, on the other hand
this might reduce the number of competing algorithm/hash/pad
mixes and simplify code.
[Answer: no. There are a number of proposals for
expressing the components of a signature verification
algorithm and one should settle out by the week after the
April IETF meeting.]
[Revised answer: yes, for now. Each of those proposals had
a complication or flaw and we need to get this draft
solidified.]
5) Should the delegation parameter be integer or boolean?
[Answer: boolean is all people want, except for the third
value "stop-at-key" proposed by Ron Rivest. It turns out
that if delegate is false in a certificate with a SDSI name
subject, then "stop-at-key" must be intended.]
6) Are object names (e.g., "Issuer") case sensitive?
Ellison, et al. [Page 73]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
[Answer: yes. All other strings are, so these byte strings
should be also. However, we decided to use all lower-case
for object names that we define.]
7) Should we allow multiple <tag>s in one cert? It saves space and
time, maybe, but could constitute a privacy threat and may
complicate the cert reading code.
[Answer: yes. The (* set ..) mechanism makes it easy to
specify without constituting a serious complication to the
5-tuple reduction process.]
8) How much can we specify the <online-test>? Are there only a
handful possible/desirable tests, that we can fully spell out,
or do we need to leave that open for invention?
[Answer: this draft includes full specification of online
tests.]
9) How many pre-defined <tag>s should we bother defining?
[Answer: none should be cast in stone here -- only examples
provided to spur the imagination of developers.]
10) If the Subject is a hash of a Bundle of hashes of keys, does
this mean that the cert applies to all keys in the bundle?
[Answer: no -- although this is a discussion left to be
addressed by the folks who sign web pages.]
11) If the Subject is a hash of a file and the file contains hashes
of other things, does the cert apply to the other things?
[Answer: no, according to general opinion. This is a more
general issue which the community needs to consider.
Perhaps W3C DSig will be the first to encounter examples of
this in practice.]
12) Do we want to include validity fields for private key dates, as
was done with X.509v3?
[Answer: not at this time and not in these certificates.
An SPKI/SDSI certificate doesn't define a public key. The
public key is a primitive. There remains open the question
of whether we want keys to expire and, if so, what kind of
a data structure we want to support key validity dates.
The subject-info field can point to or yield such a
structure, should we define one.]
Ellison, et al. [Page 74]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
13) How do we want to name algorithms? One possibility is to define
a few common ones (ones we want to encourage everyone to use for
interoperability reasons) and allow others to be defined as URIs
pointing to the definition of the algorithm.
[Answer: we will choose short names and turn the process
over to IANA, but allow URIs for user-defined algorithm
names. Presumably the URI will give a description of the
algorithm and maybe even code to implement it.]
14) Should we restore the explanation of [ECR] and define a <valid>
field option for it? This was removed from this draft in the
interest of simplification.
[Answer: there has been no request for its restoration.]
15) Should we allow Object as an optional element of the Signature
expression, or force that block to give the Object's hash?
[Answer: this draft assumes that (signature ) contains only
the object hash, not the object, in order to avoid the
complexity of ASN.1's "SIGNED" macro and to permit multiple
signatures on the same body without habit getting in the
way.]
16) Should we define an RSA signature algorithm with no hash and no
padding, to hold verbatim objects being signed (assuming they
are small enough)?
[Answer: no.]
17) What is the difference between the Member and Name <tag>? Can
they be combined into one?
[Answer: these tags have disappeared with the use of names
in the issuer field.]
18) Should we restrict the <issuer> definition to preclude the
possibility of the same cert body being signed by multiple keys
as Issuer (which can happen when the <issuer> is a general SDSI
name resolving to a key)? If so, should we permit an <issuer>
to be a group name, thus allowing the (Moi) <tag> to define SDSI
group membership?
[Answer: this is an irrelevant question under the current
specification.]
Ellison, et al. [Page 75]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
19) [RLR] Should we replace the display info syntax [xxx] "yyy" with
( display-type xxx "yyy" ) ?
[Answer: no.]
20) [RLR] Should we have only one spelling of each object type? If
so, should it be the long or the short form? Can we make such
spellings short enough that they don't force line continuations
while keeping them descriptive?
[Answer: one spelling, preferably one English word (so that
a user can look it up in a dictionary).]
21) [CME] Are object types reserved words over the entire
certificate body or are they to be non-conflicting only within
their enclosing object? [In the latter case, the ( Tag XXX ...
) object is to be considered to be of type "Tag XXX".] That is,
when we go into an object, do we acquire a new dictionary of
object types relevant to the interior of that object or do we
use a single global such dictionary? [I believe we have to use
local dictionaries, in order to allow distributed <tag>
definition.]
[Answer: object names have scope only within an object
which defines them.]
22) [RLR] Should we allow the Subject to optionally be the hash of
some non-key object? This could be seen as encroaching on the
territory of signed PICS labels.
[Answer: yes. It's desirable enough and we don't want to
force all tags into the form of a PICS rating. On the +
side, this permits the single trust management program to
decide if a document or program is permitted to run. On
the - side, this doesn't help much with on-line access
control protocols.]
23) [RLR] Should we define another, non-cert object, ( assert .. ),
to cover signed statements about non-keys?
[Answer: no.]
24) [RLR] Should we make a clear statement that the keys used in
these certs are signature keys? [[CME] I think that's
understood from the fact that the only crypto we use is for
signatures.]
[Answer: yes -- this should be clear in the document.]
Ellison, et al. [Page 76]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
25) [RLR] Should we continue to use different object types for fq-
name, rel-name and grp-name, or use "Ref" as the type and let
the parameters determine which is intended?
[Answer: no -- use "ref", although that is not an English
word. Re-answered: use "name" instead of "ref", because
it's English.]
26) [RLR] Should we define (keyholder <principal>) to mean the human
or computer etc. who/which holds a private key, to be used in
Subject lines?
[Answer: yes.]
27) [RLR] There are different cert-like entities, in that they all
reduce to 5-tuples, but they may have different object names and
slightly different BNF definitions:
a) certificate -- subject is a <principal>
b) assertion -- subject is a cyberspace object
c) request -- (a kind of assertion)
d) ACL entry -- issuer is missing
e) auto-cert -- subject is (keyholder [of] <principal>)
[Answer: call them all certificates, except ACL. Request
is a wide open term, so that is probably different from
certificate also. This draft includes a field in <cert>
for a cert display type, so that the issuer can label the
kind of cert.]
28) [RLR, CME] As written now, it is inconsistent to have a name as
a Subject in a cert with (delegate false). RLR proposes that
(delegate to-key) mean that propagation occurs through
certificate sub-chains which have non-key subjects and stop when
the subject is a key.
[Answer: use to-key as an argument to delegate, but rename
delegate to propagate. Revised: (propagate) means
delegate; lack of that field means "stop at key".]
29) Should we extend <deleg> to permit a group name or key as a
parameter, that being the group of principals allowed to
delegate?
[Answer: no -- too complicated.]
Ellison, et al. [Page 77]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Open Issues
1) [RLR] Let's add a section to the I-D showing how each of the
original SDSI constructs is handled in SPKI. [[CME] We could
also add a section for PICS labels, X.509 certs, PGP signed
keys, ...]
2) Should we start another draft to cover operation of a
certificate server (as in SDSI 1.0) including protocols for
communicating with it or should that discussion be in this
draft?
3) Should we start another draft to cover fully worked out examples
of tags for real operations (e.g., FTP, HTTP) or let those be
part of this draft?
4) What kind of <cert-display> parameters might we want to allow?
Do we want <cert-display> in the first place?
5) [BL] Why not replace (* reorder-insert X) with
(* reorder (* append X)) ?
6) [CME] We need to specify (online..) protocols -- perhaps a
variety of them (HTTP, socket connection, e-mail, ...).
Ellison, et al. [Page 78]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
References
[Ab97] Abadi, Martin, "On SDSI's Linked Local Name Spaces", to appear
in the Proceedings of the 10th IEEE Computer Security Foundations
Workshop (June 1997).
[BFL] Matt Blaze, Joan Feigenbaum and Jack Lacy, "Distributed Trust
Management", Proceedings 1996 IEEE Symposium on Security and Privacy.
[CHAUM] D. Chaum, "Blind Signatures for Untraceable Payments",
Advances in Cryptology -- CRYPTO '82, 1983.
[DvH] J. B. Dennis and E. C. Van Horn, "Programming Semantics for
Multiprogrammed Computations", Communications of the ACM 9(3), March
1966
[ECR] Silvio Micali, "Efficient Certificate Revocation", manuscript,
MIT LCS.
[HARDY] Hardy, Norman, "THE KeyKOS Architecture", Operating Systems
Review, v.19 n.4, October 1985. pp 8-25.
[IDENT] Carl Ellison, "Establishing Identity Without Certification
Authorities", USENIX Security Symposium, July 1996.
[IWG] McConnell and Appel, ``Enabling Privacy, Commerce, Security and
Public Safety in the Global Information Infrastructure'', report of
the Interagency Working Group on Cryptography Policy, May 12, 1996;
(quote from paragraph 5 of the Introduction)
[KEYKOS] Bomberger, Alan, et al., "The KeyKOS(r) Nanokernel
Architecture", Proceedings of the USENIX Workshop on Micro-Kernels
and Other Kernel Architectures, USENIX Association, April 1992. pp
95-112 (In addition, there are KeyKOS papers on the net available
through http://www.cis.upenn.edu/~KeyKOS/#bibliography)
[LAMPSON] B. Lampson, M. Abadi, M. Burrows, and E. Wobber,
"Authentication in distributed systems: Theory and practice", ACM
Trans. Computer Systems 10, 4 (Nov. 1992), pp 265-310.
[LANDAU] Landau, Charles, "Security in a Secure Capability-Based
System", Operating Systems Review, Oct 1989 pp 2-4
[LEVY] Henry M. Levy, "Capability-Based Computer Systems", Digital
Press, 12 Crosby Dr., Bedford MA 01730, 1984
[LINDEN] T. A. Linden, "Operating System Structures to Support
Security and Reliable Software", Computing Surveys 8(4), December
Ellison, et al. [Page 79]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
1976.
[PKCS1] PKCS #1: RSA Encryption Standard, RSA Data Security, Inc., 3
June 1991, Version 1.4.
[PKLOGIN] David Kemp, "The Public Key Login Protocol", working draft,
06/12/1996.
[RFC1321] R. Rivest, "The MD5 Message-Digest Algorithm", April 16
1992.
[RFC2045] N. Freed and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part One: Format of Internet Message Bodies", Dec 2
1996.
[RFC2046] N. Freed and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part Two: Media Types", Dec 2 1996.
[RFC2047] K. Moore, "MIME (Multipurpose Internet Mail Extensions)
Part Three: Message Header Extensions for Non-ASCII Text", Dec 2
1996.
[RFC2065] D. Eastlake and C. Kaufman, "Proposed Standard for DNS
Security", Jan 1997.
[RFC2104] H. Krawczyk, M. Bellare and R. Canetti, "HMAC: Keyed-
Hashing for Message Authentication", Feb 1997.
[SDSI] Ron Rivest and Butler Lampson, "SDSI - A Simple Distributed
Security Infrastructure [SDSI]",
http://theory.lcs.mit.edu/~cis/sdsi.html
[SEXP] Ron Rivest, code and description of S-expressions,
http://theory.lcs.mit.edu/~rivest/sexp.html .
[SRC-070] Abadi, Burrows, Lampson and Plotkin, "A Calculus for Access
Control in Distributed Systems", DEC SRC-070, revised August 28,
1991.
Ellison, et al. [Page 80]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Authors' Addresses
Carl M. Ellison
CyberCash, Inc.
207 Grindall Street
Baltimore MD 21230-4103 USA
Telephone: +1 410-727-4288
+1 410-727-4293(FAX)
+1 703-620-4200(main office, Reston, Virginia, USA)
EMail: cme@cybercash.com
cme@acm.org
Web: http://www.clark.net/pub/cme
Bill Frantz
Electric Communities
10101 De Anza Blvd.
Cupertino CA 95014
Telephone: +1 408-342-9576
Email: frantz@netcom.com
Butler Lampson
Microsoft
180 Lake View Ave
Cambridge MA 02138
Telephone: +1 617-547-9580 (voice + FAX)
EMail: blampson@microsoft.com
Ron Rivest
Room 324, MIT Laboratory for Computer Science
545 Technology Square
Cambridge MA 02139
Telephone: +1-617-253-5880
+1-617-258-9738(FAX)
Email: rivest@theory.lcs.mit.edu
Web: http://theory.lcs.mit.edu/~rivest
Brian Thomas
Southwestern Bell
One Bell Center, Room 23Q1
St. Louis MO 63101 USA
Ellison, et al. [Page 81]
INTERNET-DRAFT Simple Public Key Certificate 29 July 1997
Telephone: +1 314-235-3141
+1 314-331-2755(FAX)
EMail: bt0008@entropy.sbc.com
Tatu Ylonen
SSH Communications Security Ltd.
Tekniikantie 12
FIN-02150 ESPOO
Finland
E-mail: ylo@ssh.fi
Expiration and File Name
This draft expires 29 January 1998.
Its file name is draft-ietf-spki-cert-structure-02.txt
Ellison, et al. [Page 82]
