< draft-ietf-spki-cert-structure-04.txt   draft-ietf-spki-cert-structure-05.txt >
Simple Public Key Certificate Carl M. Ellison Simple Public Key Certificate Carl M. Ellison
INTERNET-DRAFT CyberCash, Inc. INTERNET-DRAFT CyberCash, Inc.
Expires: 26 May 1998 Expires: 18 September 1998
Bill Frantz Bill Frantz
Electric Communities Electric Communities
Butler Lampson Butler Lampson
Microsoft Microsoft
Ron Rivest Ron Rivest
MIT Laboratory for Computer Science MIT Laboratory for Computer Science
Brian M. Thomas Brian M. Thomas
Southwestern Bell Southwestern Bell
Tatu Ylonen Tatu Ylonen
SSH SSH
21 November 1997 13 March 1998
Simple Public Key Certificate Simple Public Key Certificate
------ ------ --- ----------- ------ ------ --- -----------
<draft-ietf-spki-cert-structure-04.txt> <draft-ietf-spki-cert-structure-05.txt>
Status of This Document Status of This Document
This document is one of three, superseding the draft filed under the This document supersedes the draft filed under the name draft-ietf-
name draft-ietf-spki-cert-structure-02.txt. The discussion and spki-cert-structure-04.txt.
background from that previous draft is now to be found in draft-
ietf-spki-cert-theory-01.txt. Examples of certificate uses are to be This version introduces "rsa-pkcs1" as one option for <pub-sig-alg-
found in draft-ieft-spki-cert-examples-01.txt. id>, while the working group considers the question of the proper
place to bind hash algorithm choice. It specifies the <sig-val>
structure needed by that option.
This version has removed the secret-key definitions, as requested at
the meeting in December 1997.
The theory behind this kind of certificate is to be found in draft-
ietf-spki-cert-theory-*.txt. Examples of certificate uses are to be
found in draft-ietf-spki-cert-examples-*.txt. The requirements
behind this work are listed in draft-ietf-cert-req-*.txt.
Distribution of this document is unlimited. Comments should be sent Distribution of this document is unlimited. Comments should be sent
to the SPKI (Simple Public Key Infrastructure) Working Group mailing to the SPKI (Simple Public Key Infrastructure) Working Group mailing
list <spki@c2.org> or to the authors. list <spki@c2.net> or to the authors.
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months. Internet-Drafts may be updated, replaced, or obsoleted by months. Internet-Drafts may be updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet- other documents at any time. It is not appropriate to use Internet-
Drafts as reference material or to cite them other than as a Drafts as reference material or to cite them other than as a
skipping to change at page 2, line 4 skipping to change at page 2, line 13
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months. Internet-Drafts may be updated, replaced, or obsoleted by months. Internet-Drafts may be updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet- other documents at any time. It is not appropriate to use Internet-
Drafts as reference material or to cite them other than as a Drafts as reference material or to cite them other than as a
``working draft'' or ``work in progress.'' ``working draft'' or ``work in progress.''
To learn the current status of any Internet-Draft, please check the To learn the current status of any Internet-Draft, please check the
1id-abstracts.txt listing contained in the Internet-Drafts Shadow 1id-abstracts.txt listing contained in the Internet-Drafts Shadow
Directories on ds.internic.net (East USA), ftp.isi.edu (West USA), Directories on ds.internic.net (East USA), ftp.isi.edu (West USA),
nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe), nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe),
munnari.oz.au (Pacific Rim), or ftp.is.co.za (Africa). munnari.oz.au (Pacific Rim), or ftp.is.co.za (Africa).
Abstract Abstract
This document specifies a standard form of digital certificate that This document specifies a standard form for digital certificates and
is both more general and simpler than what is traditionally access control lists. These structures bind either names or
considered to be a certificate. Since the word ''certificate'' was authorizations to keys or names that resolve to keys. The name and
first used by Loren Kohnfelder in 1978 to refer to a signed record authorization structures can be used separately or together. We use
holding a name and a public key, it has been assumed that the only S-expressions as the standard format for these certificates and
purpose of a certificate has been to bind a public key to a globally define a canonical form for those S-expressions.
unique name and therefore to a person. This binding was assumed both
necessary and sufficient for security.
The SPKI working group has found that the creation of a globally
unique name is neither necessary nor sufficient for Internet security
or electronic commerce. In fact, it can lead to a security flaw.
Therefore, we define certificate forms for binding local names to
keys (to retain security while offering the convenience of meaningful
names) and for assigning authorizations to keys (to provide adequate
information for real applications). These forms can be used alone or
together.
Acknowledgments
Several independent contributions, published elsewhere on the net or
in print, worked in synergy with our effort. Especially important to
our work were: [SDSI], [BFL] and [RFC2065]. The inspiration we
received from the notion of CAPABILITY in its various forms (SDS-940,
Kerberos, DEC DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated.
Significant contributions to this effort by the members of the SPKI These structures are also known under the name SDSI 2.0.
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.
Table of Contents Table of Contents
Status of This Document....................................1 Status of This Document....................................1
Abstract...................................................2
Abstract...................................................3 Table of Contents..........................................3
Acknowledgments............................................3
Table of Contents..........................................4
1. Overview of Contents....................................6 1. Overview of Contents....................................5
2. Definitions.............................................7 2. Glossary................................................6
2.1 Principal..............................................7
2.2 Keyholder..............................................7
2.3 Name...................................................8
2.4 Certificate............................................8
2.5 ACL Entry..............................................9
2.6 5-tuple...............................................10
2.7 S-Expression..........................................10
2.8 Prover................................................10
2.9 Verifier..............................................10
2.10 Validity conditions.................................11
3. Primitives.............................................12 3. Primitives..............................................8
3.1 Canonical S-expression................................12 3.1 Canonical S-expression.................................8
3.2 <byte-string>.........................................12 3.2 <byte-string>..........................................8
3.3 S-expression..........................................13 3.3 S-expression...........................................9
3.4 Encoding examples.....................................13 3.4 Encoding examples......................................9
3.5 Use of canonical S-expressions........................14 3.5 Use of canonical S-expressions........................10
3.6 Non-canonical (advanced) S-expressions................14 3.6 Advanced S-expressions................................10
3.7 Unique IDs............................................15 3.7 Unique IDs............................................11
3.8 SPKI/SDSI 2.0 Objects.................................15 3.8 Primitive Objects.....................................11
3.8.1 <pub-key>...........................................16 3.8.1 <pub-key>...........................................12
3.8.2 <sec-key>...........................................17 3.8.2 <hash>..............................................14
3.8.2.1 HMAC-MD5..........................................17 3.8.3 <signature>.........................................14
3.8.2.2 DES-CBC-MAC.......................................17 3.8.3.1 <sig-val>.........................................14
3.8.3 <hash>..............................................18
3.8.4 <signature>.........................................19
3.8.5 <acl>...............................................19
3.8.6 <sequence>..........................................20
4. Authorization Certificate..............................21 4. Authorization Certificate..............................16
4.1 <version>.............................................21 4.1 <version>.............................................16
4.2 <cert-display>........................................21 4.2 <cert-display>........................................16
4.3 <issuer>..............................................22 4.3 <issuer>..............................................17
4.4 <issuer-loc>..........................................22 4.4 <issuer-loc>..........................................17
4.5 <subject>.............................................22 4.5 <subject>.............................................17
4.5.1 <name>..............................................23 4.5.1 <obj-hash>..........................................18
4.5.2 <obj-hash>..........................................23 4.5.2 <keyholder>.........................................18
4.5.3 <sec-key>...........................................24 4.5.3 <subj-thresh>.......................................18
4.5.4 <keyholder>.........................................24 4.6 <subject-loc>.........................................19
4.5.5 <subj-thresh>.......................................25 4.7 <deleg>...............................................20
4.6 <subject-loc>.........................................26 4.8 <tag>.................................................20
4.7 <deleg>...............................................26 4.9 <valid>...............................................20
4.8 <tag>.................................................26 4.9.1 <date>..............................................21
4.9 <valid>...............................................27 4.9.2 <online-test>.......................................21
4.9.1 <date>..............................................28 4.10 <comment>............................................22
4.9.2 <online-test>.......................................28
4.10 <comment>............................................29
5. Name certificate.......................................30 5. Name certificate.......................................23
5.1 Name cert syntax......................................30 5.1 Name certificate syntax...............................23
5.2 Name reduction........................................31 5.2 <name>................................................24
5.3 Name reduction........................................24
6. On-line test reply formats.............................32 6. ACL and Sequence formats...............................26
6.1 CRL and delta-CRL.....................................32 6.1 <acl>.................................................26
6.2 Revalidation..........................................32 6.2 <sequence>............................................27
6.3 One-time revalidation.................................33
7. 5-Tuple Reduction......................................34 7. On-line test reply formats.............................28
7.1 <5-tuple> BNF.........................................34 7.1 CRL and delta-CRL.....................................28
7.2 Bare-bones case.......................................35 7.2 Revalidation..........................................28
7.3 Intersection of *-form tag sets.......................35 7.3 One-time revalidation.................................29
7.4 Reduction of SDSI names...............................36
7.4.1 Simple SDSI name reduction..........................37
7.4.2 SDSI name composition with subject name growth......37
7.5 Reduction of (subject (threshold ..)).................37
7.5.1 Left-to-right.......................................38
7.5.2 Right-to-left.......................................39
7.6 Authorization Loops...................................39
7.7 Certificate Result Certificates.......................40
8. Full BNF...............................................41 8. 5-Tuple Reduction......................................30
8.1 Top Level Objects.....................................41 8.1 <5-tuple> BNF.........................................30
8.2 Alphabetical List of BNF Rules........................41 8.2 Top level reduction rule..............................31
8.3 Intersection of tag sets..............................31
8.4 Reduction of (subject (threshold ..)).................32
8.7 Certificate Result Certificates.......................32
9. Other Certificate Formats..............................44 9. Full BNF...............................................34
9.1 Top Level Objects.....................................34
9.2 Alphabetical List of BNF Rules........................34
References................................................45 References................................................37
Authors' Addresses........................................47 Acknowledgments...........................................39
Expiration and File Name..................................48 Authors' Addresses........................................39
Expiration and File Name..................................40
1. Overview of Contents 1. Overview of Contents
This document contains the following sections: This document contains the following sections:
Section 1: this overview. Section 1: this overview.
Section 2: Definition of terms. Section 2: a glossary of terms.
Section 3: Primitives. Section 3: the definition of structure primitives used throughout the
rest of the document.
Section 4: Authorization certificate. Section 4: the definition of an authorization certificate and its
component parts.
Section 5: Name certificate. Section 5: the definition of a name certificate and the few parts
that differ from an authorization certificate.
Section 6: On-line test reply formats. Section 6: the definition of an ACL and a (sequence...) structure.
Section 7: Reduction rules. Section 7: the definition of on-line test reply formats. An on-line
test is a mechanism for asking for a CRL or a revalidation. The
replies are CRLs or revalidations.
Section 8: Full BNF. Section 8: the rules of 5-tuple reduction
Section 9: Other certificate forms. Section 9: the full BNF.
The References section lists all documents referred to in the text as 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 well as readings which might be of interest to anyone reading on this
topic. topic.
The Acknowledgements section.
The Authors' Addresses section gives the addresses, telephone numbers The Authors' Addresses section gives the addresses, telephone numbers
and e-mail addresses of the authors. and e-mail addresses of the authors.
2. Definitions 2. Glossary
If the reader is familiar with older forms of certificate and
encountering SPKI for the first time, it is important to bear in mind
that older certificates had as their purpose the binding of a public
key in cyberspace to a person in 3D space via his or her name in some
global namespace. Those older certificate descriptions kept the
reader firmly planted in 3D space. All operations referred back to
entity names.
By contrast, SPKI is a child of the 1990's. The reader needs to be
firmly planted in cyberspace. SPKI binds together public keys in
cyberspace and only rarely refers to 3D space or a namespace related
to 3D space. Finally, SPKI rejects the notion of a global namespace,
having determined that names in such a space can not be meaningful to
users. Instead, when SPKI uses names, they are defined in a local
namespace, meaningful by definition to the creator of that namespace
and not necessarily of significance to anyone else.
2.1 Principal
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.
Note that the secure hash of a public key is a global name for that
key and, by implication, for the associated private key and, by
another level of induction, for the holder of that private key.
2.2 Keyholder
By KEYHOLDER, we mean an entity in the 3D 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 or by the hash of that public key.
If K1 is a principal (key or key hash), the construct (keyholder K1)
refers to this 3D world entity. Therefore, while we speak of a
message signed by the principal K1, the message author was probably
(keyholder K1).
2.3 Name
By NAME (formally "SDSI Name") we mean a string of the form (K1 N1 N2
... Nk) where 1 <= k. Every name is a name in some namespace. We
give no special credance to a global namespace (such as the domain
name space, DNS), but rather treat it as just another local
namespace. Truly local namespaces have a special place in SPKI/SDSI
on the assumption that, like a private address book, the names in a
local namespace are meaningful to the creator of the namespace.
We identify each namespace by a principal (the principal that signs
certificates for that namespace). Names of the form (K1 N) are names
in K1's namespace. Each such name evaluates to one or more
principals -- e.g., {K2, K3}. When a name evaluates to one
principal, we tend to think of it as the name of an individual
keyholder, while when it evaluates to multiple principals, we call it
a group name. However, the two cases use the same syntax. An
individual name is a group name with one member in the group.
Letting "->" stand for a name definition, if we have (K1 N1) -> K2
and (K1 N1) -> K3, then (K1 N1 N2) -> (K2 N2) and (K1 N1 N2) -> (K3
N2).
Note that this definition of name includes an X.509 or DNSSEC
certificate chain naturally. Through this definition, one can refer
to existing X.509 or DNSSEC names from inside an SPKI certificate.
One can also refer to PGP names in this manner, although the richness
of PGP's web of trust is lost by following a single certification
thread as this form of name implies. That is, a PGP name assignment
is considered valid if there are numerous enough, short enough
certificate chains from the verifier's key to the target (name,key)
PGP certificate. Any single chain can be expressed simply as a SDSI
name sequence, but the fault tolerance and special trust model of PGP
is lost in the process.
2.4 Certificate
In [KOHNFELDER], Loren Kohnfelder defined CERTIFICATE as a digitally
signed record containing a name and a public key. The name was
assumed to identify unambiguously a given person: the keyholder of
that key.
We have realized that in any community beyond a small company common
names can not be used as identifiers because they are likely to be
ambiguous and persons identified by name are not likely to mean
anything to a trust computation. Therefore, we generalize the word
CERTIFICATE to be a signed record that binds some characteristic we
care about to a principal or set of principals.
Specifically, we define two basic forms of this general certificate
in this document: a name certificate (binding a name in the issuer's
namespace to a principal or group of principals) and an authorization
certificate (binding an authorization (permission) to a principal or
group of principals). A prior version of this spec did not separate
those two forms, but in the interest of clarity of explanation and
implementation, we have separated them here.
The parts of any certificate necessary for trust computations can be
expressed as up to five fields: Issuer, Subject, Delegation,
Authorization and Validity.
The ISSUER generates and signs the certificate.
The SUBJECT is the principal or set of principals to which the
certificate grants its name or authorization.
DELEGATION is a boolean, indicating if TRUE that the Subject is
allowed to delegate the specified Authorization further.
AUTHORIZATION is a structured field expressing the authorization that
this certificate grants to the Subject.
VALIDITY is some combination of dates or on-line tests specifying the
validity period/conditions of the certificate.
2.5 ACL Entry
An ACL entry, as we use the term, evolved from the entries one finds
in an Access Control List. More precisely, it is an unsigned
authorization certificate in which the Issuer is not specified
because it is assumed to be "self", referring to the machine on which
the ACL entry is used. A machine (its trust computation engine) is
assumed to have multiple ACL entries, referring to multiple Subjects
and/or multiple kinds of authorization. The ACL entry does not need
to be signed, because it is held in protected storage.
Every trust engine needs at least one ACL entry because there is no
one trusted source of all authorizations. Even if there were, the
trust engine would need a record if that principal and that record
would constitute an ACL entry.
2.6 5-tuple
There are up to 5 fields of any certificate or ACL entry necessary
for a trust computation. These are: Issuer, Subject, Delegation,
Authorization and Validity. These fields, taken together, are called
a "5-tuple". This document gives the rules for combining 5-tuples
("reducing" them) to yield a final 5-tuple giving trust results.
The final 5-tuple will be of the form:
<self,Subject,Delegation,Authorization,Validity>
in which Subject is a single principal, Delegation is of no use (at We use some terms in the body of this document in ways specific to
the end of the computation), Authorization is the quantity most of SPKI:
interest and Validity needs to include the present datime.
This final 5-tuple makes the statement "I (self) have determined that 5-TUPLE: The 5 security-relevant fields from a certificate or ACL
Subject is authorized to do (Authorization) at this time". entry, sometimes abbreviated <I,S,D,A,V>. [See "certificate",
below.]
2.7 S-Expression ACL: Access Control List -- a list of entries binding some attribute
to an identified entity. For our purposes, an ACL entry is like a
certificate, except that it is "issued" by "self" and need not be
signed. It yields a 5-tuple of the form <self,S,D,A,V>.
In this draft, the standard format adopted is that developed by SDSI, CERTIFICATE: a digitally signed record binding one or more attributes
modified slightly. Data objects are defined as S-expressions -- to a global identifier or to a name that can be resolved to a global
lists in which the first element is a token defining the data object. identifier. The certificate is assumed to have up to 5 kinds of
Rather than permit the full generality of S-expressions, we define a field with security value: Issuer, Subject, Delegation permission,
canonical format and accept only that form. Software is available to Authorization, Validity dates and/or tests.
translate between the canonical format and a presentation format.
This document presents the canonical format, but uses a presentation CANONICAL S-EXPRESSION: an encoding of an S-expression that removes
format for examples since the canonical format is binary and can not options and is designed for easy parsing.
easily be transmitted in a text document.
2.8 Prover KEYHOLDER: the person or other entity that owns and controls a given
private key is said to be the keyholder of the corresponding public
key.
By PROVER, we mean the entity which wishes access or digitally signs GLOBAL IDENTIFIER: a globally unique byte string, associated with the
a document. We assume that the prover assembles all certificates keyholder. In SPKI this is either the public key itself or a
necessary for use by the verifier, and puts those into order for the collision-free hash of the public key.
verifier. The prover is software but could be interacting with a
human user.
2.9 Verifier NAME: a SDSI name always relative to the definer of some name space.
This is sometimes also referred to as a local name. A global name
includes the global identifier of the definer of the name space. For
example, if
(name jim)
is a local name,
(name (hash md5 |+gbUgUltGysNgewRwu/3hQ==|) jim)
could be the corresponding global name.
By VERIFIER, we mean an entity which processes certificates, together ON-LINE TEST: one of three forms of validity test: (1) CRL; (2)
with its own ACL entries, to determine if the prover deserves access revalidation; or (3) one-time revalidation. Each refines the date
or if some signed document is valid. The verifier is most likely range during which a given certificate or ACL entry is considered
unattended software. valid.
2.10 Validity conditions PRINCIPAL: a signature key, capable of generating a digital
signature.
SPKI certificates may use one or both of two kinds of validity PROVER: the entity that wishes access or that digitally signs a
period: a date range (akin to expiration dates) or an on-line check. document.
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 a validity
period which is the intersection of the date ranges of the two data
items (usually equalling the date range of the on-line test result).
There are three forms of on-line test result defined: SPEAKING: a Principal is said to "speak" by means of a digital
signature. The statement made is the signed object (typically a
certificate, for SPKI purposes).
CRL S-EXPRESSION: the data format chosen for SPKI/SDSI. This is a LISP-
a list of certificates known to have been revoked. like parenthesized expression with the limitations that empty lists
are not allowed and the first element in any S-expression must be a
string, called the "type" of the expression.
Periodic revalidation VALIDITY CONDITIONS: a date range that must include the current time
a reassurance of validity for one specific certificate. and/or a set of on-line tests that must succeed before a certificate
or ACL entry is to be considered valid.
One-time revalidation VERIFIER: the entity that processes requests from a prover, including
a statement that for this one transaction, the indicated certificates. The verifier uses its own ACL entries and certificates
certificate is valid. [Instead of having a validity date range provided by the prover to perform "5-tuple reduction", to arrive at a
of its own, a one-time revalidation server receives a random 5-tuple it believes about the prover: <self,prover,D,A,V>.
nonce from the verifier and returns the validity result together
with that nonce, digitally signed. The resulting validity
period is formally that of the one trust computation and no
more. This is as close as we can come to a 0-length validity
period revalidation. It has the benefit of not requiring clock
synchronization.] A one-time revalidation can also have side
effects -- e.g., refer to a bank balance.
3. Primitives 3. Primitives
We have chosen a simplified form of S-expression (the canonical form) 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 as the format for SPKI objects. An S-expression is a list enclosed
in matching "(" and ")". We assume the S-expression technology of in matching "(" and ")". We assume the S-expression technology of
[SEXP] with the restrictions that no empty lists are allowed and that [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 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 element is the "type" or "name" of the object represented by the
list. list.
SPKI objects are defined below in a familiar extension of BNF -- with SPKI objects are defined below in a familiar extension of BNF -- with
"*" meaning closure (0 or more occurrences), "?" meaning optional (0 "|" meaning logical OR, "*" meaning closure (0 or more occurrences),
or 1 occurrence) and "+" meaning non-empty closure (1 or more "?" meaning optional (0 or 1 occurrence) and "+" meaning non-empty
occurrences). First we define the canonical S-expression form in closure (1 or more occurrences). A quoted string represents those
that BNF. characters. First we define the canonical S-expression form in that
BNF.
For the sake of readability, all examples and the BNF in this
document specify advanced rather than canonical S-expressions. That
is, single word strings that start with alphabetic characters are
used without quotes and strings can be in hex, base64 or double-
quoted ASCII. The mapping to canonical form is specified below.
3.1 Canonical S-expression 3.1 Canonical S-expression
We define a canonical S-expression as containing binary byte strings We define a canonical S-expression as containing binary byte strings,
each with a given length and punctuation "()[]" for forming lists. each with a given length, and punctuation "()[]" for forming lists.
The length of a byte string is a non-negative ASCII decimal number, The length of a byte string is a non-negative ASCII decimal number,
with no unnecessary leading "0" digits, terminated by ":". We with no unnecessary leading "0" digits, terminated by ":". We
further require that there be no empty lists and that the first list 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 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 representation of an S-expression and is used as the input to all
hash and signature functions. If canonical S-expressions need to be hash and signature functions. If canonical S-expressions need to be
transmitted over a 7-bit channel, there is a form defined for base64 transmitted over a 7-bit channel, there is a form defined for base64
encoding them. encoding them.
3.2 <byte-string> 3.2 <byte-string>
A byte string is a binary sequence of bytes (octets), optionally A byte string is a binary sequence of bytes (octets), optionally
modified by a display type. modified by a display type.
If the byte-string is used as a binary integer, these bytes are If the byte-string is used as a binary integer, these bytes are twos-
twos-complement, in network standard order (most significant byte complement, in network standard order (most significant byte first).
first). It is up to the application whether these are considered It is up to the application whether these are considered signed or
signed or unsigned. unsigned.
All byte strings carry explicit lengths and are therefore not 0- All byte strings carry explicit lengths and are therefore not
terminated as in the C language. They are treated as binary even 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. when they are ASCII, and can use any character set encoding desired.
Typically, such a choice of character set would be indicated by a Typically, such a choice of character set would be indicated by a
display type. display type.
A display type is assumed to be a MIME type giving optional A display type is assumed to be a MIME type giving optional
instructions to any program wishing to display or use the byte instructions to any program wishing to display or use the byte
string. For example, it might indicate that the string is in string. For example, it might indicate that the string is in
UNICODE, is a GIF or JPEG image, is an audio segment, etc. Although 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 the display type of a byte string is optional, it is considered part
of the string for any equality comparisons or hashing. of the string for any equality comparisons or hashing. That is, two
strings of the same bytes will not be considered equal if they have
unequal display types.
A byte-string is defined by: A byte-string is defined by:
<byte-string>:: <bytes> | <display-type> <bytes> ; <byte-string>:: <bytes> | <display-type> <bytes> ;
<bytes>:: <decimal> ":" {binary byte string of that length} ; <bytes>:: <decimal> ":" {binary byte string of that length} ;
<decimal>:: <nzddigit> <ddigit>* | "0" ; <decimal>:: <nzddigit> <ddigit>* | "0" ;
<nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; <nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
<ddigit>:: "0" | <nzddigit> ; <ddigit>:: "0" | <nzddigit> ;
<display-type>:: "[" <bytes> "]" ; <display-type>:: "[" <bytes> "]" ;
skipping to change at page 13, line 31 skipping to change at page 9, line 41
An S-expression is of the form: An S-expression is of the form:
<s-expr>:: "(" <byte-string> <s-part>* ")" ; <s-expr>:: "(" <byte-string> <s-part>* ")" ;
<s-part>:: <byte-string> | <s-expr> ; <s-part>:: <byte-string> | <s-expr> ;
where the first byte string in the S-expression is referred to here where the first byte string in the S-expression is referred to here
as its "type". as its "type".
3.4 Encoding examples 3.4 Encoding examples
(4:test26:abcdefghijklmnopqrstuvwxyz5:123455::: ::)
(4:test26:abcdefghijklmnopqrstuvwxyz5:123455::: ::)
is a canonical S-expression consisting of four byte strings: "test", is a canonical S-expression consisting of four byte strings: "test",
"abcdefghijklmnopqrstuvwxyz", "12345" and ":: ::". "abcdefghijklmnopqrstuvwxyz", "12345" and ":: ::".
The advanced text form is: The advanced text form is:
(test abcdefghijklmnopqrstuvwxyz "12345" ":: ::") (test abcdefghijklmnopqrstuvwxyz "12345" ":: ::")
showing that the advanced form follows familiar token recognition showing that the advanced form follows familiar token recognition
rules, not permitting tokens to start with digits, terminating them rules, not permitting tokens to start with digits, terminating them
with white space or punctuation marks. with white space or punctuation marks.
For transmission of true 8-bit forms, we permit base64 encodings For transmission of true 8-bit forms, we permit base64 encodings
according to [RFC2045], with the base64 characters enclosed in according to [RFC2045], with the base64 characters enclosed in
braces. The example above encodes to: braces. The example above encodes to:
{KDQ6dGVzdDI2OmFiY2RlZmdoaWprbG1ub3BxcnN0dXZ3eHl6NToxMjM0NTU {KDQ6dGVzdDI2OmFiY2RlZmdoaWprbG1ub3BxcnN0dXZ3eHl6NToxMjM0NTU
skipping to change at page 14, line 27 skipping to change at page 10, line 38
The canonical S-expression is the form which is hashed for both The canonical S-expression is the form which is hashed for both
generating and verifying signatures. These two processes can be generating and verifying signatures. These two processes can be
thought of as the start and end of an SPKI object's useful life and 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 both require canonical form. Therefore, it is recommended that the
canonical form be the form transmitted and stored in normal use, to canonical form be the form transmitted and stored in normal use, to
be converted temporarily to and from a more readable form by display be converted temporarily to and from a more readable form by display
or editing applications written for the purpose. or editing applications written for the purpose.
[Violating that suggestion, this document includes some advanced [Violating that suggestion, this document includes some advanced
(non-canonical) forms, for readability. Since this document is forms for readability. Since this document is required to be
required to be straight ASCII, no pure 8-bit canonical forms will be straight ASCII, no pure 8-bit canonical forms will be presented
presented except under base64 encoding.] except under base64 encoding.]
3.6 Non-canonical (advanced) S-expressions 3.6 Advanced S-expressions
[SEXP] includes a general purpose utility program for converting [SEXP] includes a general purpose utility program for converting
between canonical and advanced S-expression form. In the advanced between canonical and advanced S-expression form. In the advanced
form, individual byte strings may be expressed without length fields form, individual byte strings may be expressed without length fields
(if they are what most languages consider text tokens), may be (if they are what most languages consider text tokens), may be
written as quoted strings (under normal C string rules), or 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 individually hex or base64 encoded. Also in the advanced form, white
white space between list elements is allowed for readability and space between list elements is allowed for readability and ignored on
ignored on conversion to canonical form. conversion to canonical form.
For examples this document will normally use the advanced form, For examples, this document will normally use the advanced form
because of its readability, but for at least one concrete example the because of its readability, but for at least one concrete example the
canonical form and its hash are presented (base64 encoded where canonical form and its hash are presented (base64 encoded where
necessary). necessary, given that this document is 7-bit ASCII).
In these examples, we will use keywords without preceding length In these examples, we will use keywords without preceding length
fields, quoted strings, hex values (delimited by "#") and base64 fields, quoted strings, hex values (delimited by "#") and base64
values (delimited by "|"). Those are features of the advanced values (delimited by "|"). Those are features of the advanced
transport form of an S-expression, and are not part of the canonical transport form of an S-expression, and are not part of the canonical
form. We will always present the canonical form (base-64 encoded, form. We will always present the canonical form (base-64 encoded,
when it contains non-ASCII characters) which the reader can decode to when it contains non-ASCII characters) which the reader can decode to
get the actual canonical form. get the actual canonical form.
3.7 Unique IDs 3.7 Unique IDs
Top level object names are defined in this document along with Top level object names are defined in this document along with
certain algorithm names. <tag> objects are user-defined, using a certain algorithm names. <tag> objects are user-defined, using a
language for describing sets of permissions given here, and in the language for describing sets of permissions given here, and in the
process, the defining user can choose any object names he or she process, the defining user can choose any object names he or she
wishes. wishes.
For the definition of new algorithm names, it is our preference that 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 this be taken on by IANA [RFC1780] for single-word standard names.
interest of maximum flexibility we also permit users to define their In the interest of maximum flexibility we also permit users to define
own algorithm names via a normal URI's (which presumably point to their own algorithm names via a normal URIs (which presumably point
descriptions of the algorithms or even code). to descriptions of the algorithms or even to code).
3.8 SPKI/SDSI 2.0 Objects 3.8 Primitive Objects
The objects defined in SPKI/SDSI 2.0 are S-expressions. That is they 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 are lists of either byte strings or other lists. In our case, all S-
S-expressions start with a <byte-string>, called the object name. expressions start with a <byte-string>, called the object name. The
The remaining elements of the list are called "parts" of the object. remaining elements of the list are called "parts" of the object.
In a communication from prover to verifier, one might encounter only In a communication from prover to verifier, one might encounter only
a small number of different objects: usually a <sequence> of <cert>, a small number of different objects: usually a <sequence> of <cert>,
<pub-key>, <sec-key>, <signature> and <op>. The verifier will also <pub-key>, <signature> and <op>. The verifier will also need to
need to refer to its own <acl>. These are considered top level refer to its own <acl>. These are considered top level objects and
objects and are defined in the sections immediately following are defined in the sections immediately following
It is standard SPKI/SDSI practice to use names starting with a lower It is standard SPKI/SDSI practice to use names starting with a lower
case letter, followed by lower case letters, digits and hyphens for case letter, followed by lower case letters, digits and hyphens for
object types. SPKI/SDSI is case-sensitive, so the byte-string "RSA" object types. SPKI/SDSI is case-sensitive, so the byte-string "RSA"
is not the same as "rsa". Non-standard object types (i.e. <tag>s is not the same as "rsa". Non-standard object types (i.e. <tag>s
defined by an application developer) are unconstrained, may have defined by an application developer) are unconstrained, may have
display types and may even be URI's pointing to documentation of the display types and may even be URIs pointing to documentation of the
object type. object type.
The structure and interpretation of the parts is up to the designer The structure and interpretation of the parts is up to the designer
of the top-level object type. However, for the sake of of the top-level object type. However, for the sake of
simplification, we have decided that all objects are "positional". simplification, we have decided that all objects are "positional".
That is, their parts are listed in some fixed order with meaning of That is, their parts are listed in some fixed order with meaning of
the part depending on its position. Parts can be omitted only by the part depending on its position. Parts can be omitted only by
omitting a contiguous set of trailing parts. omitting a contiguous set of trailing parts. Exceptions to this are
found in the top level <cert> and <acl> constructs.
The following are the definitions of the top level objects which a The following are the definitions of the top level objects which a
verifying program may encounter. Note that the main object, cert, is verifying program may encounter. Note that the main object, <cert>,
sub-type based so the parameter fields may be in any order, but the is sub-type based so the parameter fields may be in any order, but
BNF suggests a fixed order. We use the BNF definition to indicate the BNF suggests a fixed order. We use the BNF definition to
that there may not be more than one of each of the listed fields, and indicate that there may not be more than one of each of the listed
also to suggest (for readability) that the cert parts be presented in fields, and also to suggest (for readability) that the certificate
the order given. This document will use that order. parts be presented in the order given. This document will use that
order.
3.8.1 <pub-key> 3.8.1 <pub-key>
<pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uri>* ")" ; <pub-key>:: "(" "public-key" "(" <pub-sig-alg-id> <s-expr>* ")"
<uris> ")" ;
A public key definition gives everything the user needs to employ the A public key definition gives everything the user needs to employ the
key for checking signatures. key for checking signatures. The <uri>s, if present, give locations
where one might find certificates empowering that public key.
The only pub-sig-alg-id's we have defined at this point are for 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 signature verification. That is because we need only signature keys
for certificate formation and access control. Other key types are for certificate formation and access control. Other key types are
open to being defined by users. open to being defined by users.
The following is an RSA signature key, shown in advanced transport The following is an RSA signature key, shown in advanced transport
format: format:
(public-key rsa-pkcs1-md5 (public-key
(e #03#) (rsa-pkcs1-md5
(n |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO (e #03#)
YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY (n
VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| )) |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO
YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY
VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| )))
For actual use, the key is held and presented in canonical form the For actual use, the key is held and presented in canonical form the
base64 encoding of which is: base64 encoding of which is:
{KDEwOnB1YmxpYy1rZXkxMzpyc2EtcGtjczEtbWQ1KDE6ZTE6AykoMTpuMTI {KDEwOnB1YmxpYy1rZXkoMTM6cnNhLXBrY3MxLW1kNSgxOmUxOgMpKDE6bjE
5OgDRwhvOY1xRponK9zBj4+dxWGEmNWlgLnujyp6RRKx4SjCWuB6yuFkikzm yOToA0cIbzmNcUaaJyvcwY+PncVhhJjVpYC57o8qekUSseEowlrgesrhZIpM
E05WqUc55xCw9g+5Vnd0PDw9JcotTSaTczJMUFR66wJyEKHM3jmbos/8mFQ8 5hNOVqlHOecQsPYPuVZ3dDw8PSXKLU0mk3MyTFBUeusCchChzN45m6LP/JhU
ydQ3YiJoscm/ycpntw9FIlF4XelRgM9MdHIKynnyp5o8uNdCq6N7ltSkp} PMnUN2IiaLHJv8nKZ7cPRSJReF3pUYDPTHRyCsp58qeaPLjXQquje5bUpKSk=}
Although not strictly needed by this draft, the private key for the Although not strictly needed by this draft, the private key for the
public key above is: public key above is:
(private-key rsa-pkcs1-md5 (e #03#) (n (private-key
|ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO (rsa-pkcs1-md5
YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY (e #03#)
VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| ) (d (n
|AIvWvTRCPYvEW9ykyu1CmkuQQMQjm5V0Um0xvwuDHaWGyw8lacx65hcM0 |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKT
QM3uRw2iaaCyCkCnuO+k19fX4ZMXOD7cLN/Qrql8Efx5mczcoGN+Eo6FF+ OYTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/
cvgXfupe1VM6PmJdFIauJerTHUOlPrI12N+NnAL7CvU6X1nhOnf/Z77iz| ) (p yYVDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3u
|APesjZ8gK4RGV5Qs1eCRAVp7mVblgf13R5fwApw6bTVWzunIwk/2sShyy W1|)
tpc90edr+0DPwldnvEXTUY1df0DwPc=|) (q (d
|ANjPQe6O0Jfv90GWE3q2c9724AX7FKx64g2F8lxgiWW0QKEeqiWiiEDx7 |AIvWvTRCPYvEW9ykyu1CmkuQQMQjm5V0Um0xvwuDHaWGyw8lacx65hcM
qh0lLrhmBT+VXEDFRG2LHmuNSTzj7M=|) (a 0QM3uRw2iaaCyCkCnuO+k19fX4ZMXOD7cLN/Qrql8Efx5mczcoGN+Eo6F
|AKUds79qx62EOmLIjpW2AOb9EOSZAVOk2mVKrGgm83jkifEwgYqkdhr3M F+cvgXfupe1VM6PmJdFIauJerTHUOlPrI12N+NnAL7CvU6X1nhOnf/Z77
ebopNppH/NXf1uTv0tk3i7OTqitK08=|) (b iz|)
|AJCKK/RfNbqf+iu5YlHO9+n56q6nYx2nQV5ZTD2VsO54KxYUcW5sWtX2n (p
xr4YydBEA3+46CsuLZ5cvvJeMNNCnc=|) (c |APesjZ8gK4RGV5Qs1eCRAVp7mVblgf13R5fwApw6bTVWzunIwk/2sShy
|CIPwAAO8Vmj0/BfCtsg+35+r94jwxGYHZ63RsqyNxbvkAO6xPqSht8/vz ytpc90edr+0DPwldnvEXTUY1df0DwPc=|)
dR93eX5B9ZKBQg1HHWCsHbqQtmNLQ==|)) (q
|ANjPQe6O0Jfv90GWE3q2c9724AX7FKx64g2F8lxgiWW0QKEeqiWiiEDx
where a, b and c are CRT parameters. 7qh0lLrhmBT+VXEDFRG2LHmuNSTzj7M=|)
(a
3.8.2 <sec-key> |AKUds79qx62EOmLIjpW2AOb9EOSZAVOk2mVKrGgm83jkifEwgYqkdhr3
MebopNppH/NXf1uTv0tk3i7OTqitK08=|)
<sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>* ")" ; (b
|AJCKK/RfNbqf+iu5YlHO9+n56q6nYx2nQV5ZTD2VsO54KxYUcW5sWtX2
3.8.2.1 HMAC-MD5 nxr4YydBEA3+46CsuLZ5cvvJeMNNCnc=|)
(c
Example: |CIPwAAO8Vmj0/BfCtsg+35+r94jwxGYHZ63RsqyNxbvkAO6xPqSht8/v
zdR93eX5B9ZKBQg1HHWCsHbqQtmNLQ==|)))
(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].
3.8.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}
3.8.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 or
(hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|) {KDExOnByaXZhdGUta2V5KDEzOnJzYS1wa2NzMS1tZDUoMTplMToDKSgxOm4
xMjk6ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSK
which, in base64 encoded canonical form, is TOYTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY
VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1KSg
xOmQxMjk6AIvWvTRCPYvEW9ykyu1CmkuQQMQjm5V0Um0xvwuDHaWGyw8lacx
65hcM0QM3uRw2iaaCyCkCnuO+k19fX4ZMXOD7cLN/Qrql8Efx5mczcoGN+Eo
6FF+cvgXfupe1VM6PmJdFIauJerTHUOlPrI12N+NnAL7CvU6X1nhOnf/Z77i
zKSgxOnA2NToA96yNnyArhEZXlCzV4JEBWnuZVuWB/XdHl/ACnDptNVbO6cj
CT/axKHLK2lz3R52v7QM/CV2e8RdNRjV1/QPA9ykoMTpxNjU6ANjPQe6O0Jf
v90GWE3q2c9724AX7FKx64g2F8lxgiWW0QKEeqiWiiEDx7qh0lLrhmBT+VXE
DFRG2LHmuNSTzj7MpKDE6YTY1OgClHbO/asethDpiyI6VtgDm/RDkmQFTpNp
lSqxoJvN45InxMIGKpHYa9zHm6KTaaR/zV39bk79LZN4uzk6orStPKSgxOmI
2NToAkIor9F81up/6K7liUc736fnqrqdjHadBXllMPZWw7ngrFhRxbmxa1fa
fGvhjJ0EQDf7joKy4tnly+8l4w00KdykoMTpjNjQ6CIPwAAO8Vmj0/BfCtsg
+35+r94jwxGYHZ63RsqyNxbvkAO6xPqSht8/vzdR93eX5B9ZKBQg1HHWCsHb
qQtmNLSkpKQ==}
{KDQ6aGFzaDM6bWQ1MTY6kuXyqx8jYWdZ/j7Vffr+yik=} where a, b and c are CRT parameters.
A hash of the hmac-md5 secret key defined above is: 3.8.2 <hash>
(hash md5 #33b7035665f7af8c6669bdabc58ab236#) or (hash md5 <hash>:: "(" "hash" <hash-alg-name> <hash-value> <uris> ")" ;
|M7cDVmX3r4xmab2rxYqyNg==|)
which, in base64 encoded canonical form, is A <hash> object gives the hash of some other object. For example,
the public key given above has the following hashes:
{KDQ6aGFzaDM6bWQ1MTY6M7cDVmX3r4xmab2rxYqyNik=} (hash md5 #9710f155723bc5f4e0422ea53ff7c495#)
{KDQ6aGFzaDM6bWQ1MTY6lxDxVXI7xfTgQi6lP/fElSk=}
This is perhaps of more interest than the hash of the public key (hash sha1 #1a6f6d62 1abd4476 f16d0800 fe4c32d0 6ff62e93#)
because a certificate generally released to the public can not {KDQ6aGFzaDQ6c2hhMTIwOhpvbWIavUR28W0IAP5MMtBv9i6TKQ==}
contain a secret key, for obvious reasons, but it might contain the
hash of the secret key without fear of loss of the secret.
3.8.4 <signature> 3.8.3 <signature>
<signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ; <signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ;
A signature object is typically used for a certificate body and A signature object is typically used for a certificate body and
typically follows that <cert> object in a <sequence>. We chose not typically follows that <cert> object in a <sequence>. One can also
to define an object <signed-cert> containing the cert body and sign objects other than certificate bodies, of course. For example,
signature, since there may be cases when the same cert body needs to one can form the signature of a file.
be signed by multiple keys.
One can also sign objects other than cert bodies, of course. For
example, one can form the signature of a file.
3.8.5 <acl>
<acl>:: "(" "acl" <version>? <acl-entry>* ")" ;
<acl-entry>:: "(" "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 subject is given the
permission specified in <tag>, without permission to delegate it,
with no expiration date or condition (until the ACL is edited to
remove the permission).
For example:
(acl
(entry
(name (hash md5 |p1isZirSN3CBscfNQSbiDA==|) sysadmin/operators)
(tag (ftp db.acme.com root))
)
(entry
(hash md5 |M7cDVmX3r4xmab2rxYqyNg==|)
(tag (ftp db.acme.com root))
)
(entry
(hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|)
(propagate)
(tag (http http://www.internal.acme.com/accounting/))
)
)
3.8.6 <sequence>
<sequence>:: "(" "sequence" <seq-ent>* ")" ;
<seq-ent>:: <cert> | <pub-key> | <signature> | <op> ;
<op>:: <hash-op> | <general-op> ; 3.8.3.1 <sig-val>;
<hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ; <sig-val> depends on the <pub-sig-alg-id> -- the algorithm listed in
the public key.
<general-op>:: "(" "do" <byte-string> <s-part>* ")" ; For rsa-pkcs1-md5 and rsa-pkcs1-sha1, <sig-val> is a <byte-string> --
the value of the RSA signature operation.
A <sequence> is a bundled sequence of objects which the verifier is For dsa-sha1, <sig-val> is a <byte-string>, consisting of the
to consider when deciding to grant access. We anticipate requiring concatenation of the values r and s (in that order) from the DSA.
the prover (who constructs and submits the <sequence>) to provide Each is of the length of the sub-prime, q. We could split these
elements in order, so that the verifier need only process the values out in an S-expression, but at least one popular cryptographic
<sequence> in order to prove to itself that the prover has the package (BSAFE) assumes the two values are concatenated so that
claimed access right. splitting and recombining would be extra work for the programmer.
The sequence can also contain instructions to the verifier, in the For rsa-pkcs1 (should that option be preferred by the working group
form of opcodes. At present the only opcode defined is "hash" -- over the specification of hash algorithm in the <pub-sig-alg-id>),
meaning, that the previous item in the sequence (the last one read <sig-val> would need to be:
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 <sig-val>:: "(" "rsa-pkcs1-sig" <hash-alg-name> <byte-string> ")" ;
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 Custom algorithms, specified by URI, might need custom <sig-val>
followed by multiple (do hash ..) opcodes. definitions. The <sig-val> structure for a custom <pub-sig-alg-id>
should be specified at the given URI even if it is one used by other
algorithms.
4. Authorization Certificate 4. Authorization Certificate
<cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>? <cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>?
<subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ; <subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ;
The basic certificate form is an authorization certificate. It The basic certificate form is an authorization certificate. It
transfers some specific authorization or permission from one transfers some specific authorization or permission from one
principal to another. principal to another. The fields defined here assume one wants SPKI
certificates without SDSI name definition. Some of those field
definitions are modified in Section 5, to provide name definition.
Because a certificate merely transfers authorizations, rather than Because a certificate merely transfers authorizations, rather than
creating them, the form we call ACL-entry is also defined below to creating them, the form we call ACL-entry is also defined below to
inject authorizations into a chain of certificates. An ACL entry inject authorizations into a chain of certificates. An ACL entry
lives on the machine of the verifier, leading to the observation that lives on the machine of the verifier, leading to the observation that
all authorization flow is in loops -- from the verifying machine, all authorization flow is in a circuit -- from the verifying
through certificates back to the verifying machine. Alternatively, machine's ACL, possibly through certificates and then back to the
one might say that the only root of an authorization certificate verifying machine. Alternatively, one might say that the only root
chain is the verifier. of an authorization certificate chain is the verifier.
4.1 <version> 4.1 <version>
<version>:: "(" "version" <byte-string> ")" ; <version>:: "(" "version" <byte-string> ")" ;
Version numbers are alphanumeric strings. If the <version> field is Version numbers are alphanumeric strings. If the <version> field is
missing from an object, it is assumed to be (version V0), which is missing from an object, it is assumed to be (version "0"), which is
the version of all objects in this draft. Elaboration of version the version of all objects in this draft. Elaboration of version
numbers, possibly with multiple fields, are left for later to define. numbers, possibly with multiple fields, are left for later to define.
It is assumed that a verifier, when encountering a structure it A certificate containing an unrecognized version number must be
doesn't know how to parse (because it has a version number it doesn't ignored.
recognize), will ignore that object.
4.2 <cert-display> 4.2 <cert-display>
<cert-display>:: "(" "display" <byte-string> ")" ; <cert-display>:: "(" "display" <byte-string> ")" ;
This optional field gives a display hint for the entire certificate. This optional field gives a display hint for the entire certificate.
This display parameter does not affect certificate chain reduction, This display parameter does not affect certificate chain reduction,
but is provided to aid user-interface software in certificate but is provided to aid user-interface software in certificate
display. display.
At this time, we have no such hints defined. This field is up to At this time, we have no such hints defined. This field is up to
developers to define as they see fit. developers to define as they see fit. For verifiers of certificates,
this field is treated as a comment.
4.3 <issuer> 4.3 <issuer>
<issuer>:: "(" "issuer" <principal> ")" ; <issuer>:: "(" "issuer" <principal> ")" ;
<principal>:: <pub-key> | <hash-of-key> ; <principal>:: <pub-key> | <hash-of-key> ;
This rules out <sec-key> issuers, since an explicit <sec-key> as an <hash-of-key> might be the preferred <principal>, not merely for size
issuer offers no security to the cert. However, one may have a but also in case one is using small RSA keys and protecting them from
<hash-of-key> field that is the hash of a <sec-key> as the issuer, cryptanalysis by keeping them secret.
for a cert where the only verifiers are in possession of the secret
key.
4.4 <issuer-loc> 4.4 <issuer-loc>
<issuer-loc>:: "(" "issuer-info" <uri>* ")" ; <issuer-loc>:: "(" "issuer-info" <uris> ")" ;
The (issuer-info ) object provides the location of the cert(s) by The (issuer-info ) object provides the location of the certificate(s)
which the issuer derives the authority to pass along the by which the issuer derives the authority to pass along the
authorization in the present <cert>. We expect the prover (the authorization in the present <cert>. We expect the prover (the
calling client) to track down such other certs and provide them to calling client) to track down such other certificates and provide
the verifier (the called server), but we allow this information in them to the verifier (the called server), but we allow this
the cert to simplify that process for the prover. information in the certificate to simplify that process for the
prover.
4.5 <subject> 4.5 <subject>
<subject>:: "(" "subject" <subj-obj> ")" ; <subject>:: "(" "subject" <subj-obj> ")" ;
<subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> | <subj-obj>:: <principal> | <name> | <obj-hash> | <keyholder> | <subj-
<keyholder> | <subj-thresh> ; thresh> ;
In the most basic form, a subject is a principal. However, it may
also be a name, representing a group of principals or a delayed
binding to some one principal.
In some certs, the subject is not reducible directly to principal(s).
It may be the hash of an object or a reference to some keyholder
(that is, some person or other entity in 3D space). It may also be a
K-of-N threshold of principals (in which case, the authorization
being granted to the subject is being spread out among multiple
parties that must cooperate to exercise that authorization).
4.5.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>+ ;
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 In the most basic form,
issuer's name space, the subject name can be in any name space.
(subject (name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred sam george <subj-obj>:: <principal> ;
mary))
refers through "fred" defined in the name space of and one may make an SPKI implementation with only that definition, in
|Txoz1GxK/uBvJbx3prIhEw==|, to reduce to: case names are considered unnecessary for the intended application.
(subject (name (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|) sam george However in full-blown implementations, the subject may also be a
mary)) name, representing a group of principals or a delayed binding to some
one principal, the hash of an object, or a K-of-N threshold of
principals (in which case, the authorization being granted to the
subject is being spread out among multiple parties that must
cooperate to exercise that authorization). The <keyholder> case is
special and of little interest to verifier code, since it is used in
a certificate that is a message to a human.
recursing until the subject reduces to a key. This construct allows See section 5 for the definition of <name>.
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
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.5.2 <obj-hash> 4.5.1 <obj-hash>
<obj-hash>:: "(" "object-hash" <hash> ")" ; <obj-hash>:: "(" "object-hash" <hash> ")" ;
This option for a (subject ) refers to an object other than a This option for a (subject ) refers to an object other than a
<principal> (or SDSI name reducing to a principal). One might use <principal>. One might use this form to assign attributes to an
this form to assign attributes to an object (a file, a web page, an object (a file, a web page, an executable program, ...).
executable program, ...).
4.5.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
certificate might also include a key serial number as part of its tag
field.
4.5.4 <keyholder> 4.5.2 <keyholder>
<keyholder>:: "(" "keyholder" <keyholder-obj> ")" ; <keyholder>:: "(" "keyholder" <keyholder-obj> ")" ;
<keyholder-obj>:: <principal> | <name> ; <keyholder-obj>:: <principal> | <name> ;
This form of subject refers to the flesh and blood (or iron and 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 silicon) holder of the referenced key. A <cert> with such a subject
is saying something about that person or machine -- such as its is saying something about that person or machine -- such as its
location, its address, its age, its weight, its height, its picture, location, its address, its age, its weight, its height, its picture,
.... .... Such a certificate is most probably a message to a human rather
than for use in a verification process, but we anticipate
applications that will appreciate the machine-readable format of such
information.
4.5.5 <subj-thresh> 4.5.3 <subj-thresh>
<subj-thresh>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ; <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 where K < N, and there are N <subj-obj> subjects listed.
<subj-obj> subjects listed.
A threshold subject, introduced by Tatu Ylonen for SPKI and by Rivest 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 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 ACL entry, of which K must agree before the permission is passed
along. along.
The actual intent is to insure that there are K distinct paths The actual intent is to insure that there are K distinct paths
passing permission between the verifier's ACL and the prover's passing permission between the verifier's ACL and the prover's
request. These multiple paths branch and re-join, so the k-of-n request. These multiple paths fork and join, so the k-of-n construct
construct could theoretically be part of either the Subject or the could theoretically be part of either the Subject or the Issuer.
Issuer. Since an ACL might want to specify these multiple paths (and Since an ACL might want to specify these multiple paths (and an ACL
an ACL has no Issuer) and since a cert is signed by a single Issuer, has no Issuer) and since a certificate is signed by a single Issuer,
we have chosen to specify the branching at the Subject. we have chosen to specify the branching at the Subject.
A certificate or ACL with a k-of-n Subject does not delegate A certificate or ACL with a k-of-n Subject does not delegate
permission to any of those subjects, alone. Rather, each of these permission to any of those subjects, alone. Rather, each of these
subjects receives a share of the delegated permission. Only if at subjects receives a share of the delegated permission. Only if at
least K of the N subjects show certificate paths which converge on a least K of the N subjects show certificate paths which converge on a
single target Subject during reduction, is that permission single target Subject during reduction, is that permission
transmitted to the target. If fewer than K such paths can be shown, transmitted to the target. If fewer than K such paths can be shown,
then the permission is not delegated. then the permission is not delegated.
skipping to change at page 26, line 21 skipping to change at page 19, line 46
both before the eventual subject gets the permission. This can both before the eventual subject gets the permission. This can
be achieved through the use of (online ) tests in a long-lived be achieved through the use of (online ) tests in a long-lived
certificate, but the K-of-N subject mechanism may be cleaner. certificate, but the K-of-N subject mechanism may be cleaner.
5. ultra-secure applications. There are many applications which 5. ultra-secure applications. There are many applications which
follow the nuclear weapons launch scenario. That is, multiple follow the nuclear weapons launch scenario. That is, multiple
agreement is required before the permission is granted. agreement is required before the permission is granted.
4.6 <subject-loc> 4.6 <subject-loc>
<subject-loc>:: "(" "subject-info" <uri>* ")" ; <subject-loc>:: "(" "subject-info" <uris> ")" ;
This optional field provides the location of information about the This optional field provides the location of information about the
subject. For example, if the subject is a hash of a key, this might subject. For example, if the subject is a hash of a key, this might
provide the location of the key being hashed. IF the subject is a provide the location of the key being hashed. If the subject is a
SDSI name, it might give the location of a SDSI name cert server. SDSI name, it might give the location of a SDSI name certificate
server.
4.7 <deleg> 4.7 <deleg>
<deleg>:: "(" "propagate" ")" ; <deleg>:: "(" "propagate" ")" ;
This optional field, if present, notes that the <subject> has not This optional field, if present, notes that the <subject> has not
only the permission given in the <cert>'s <tag> field but also the only the permission given in the <cert>'s <tag> field but also the
permission to delegate that (or some portion of it) to others. permission to delegate that (or some portion of it) to others.
4.8 <tag> 4.8 <tag>
<tag>:: "(" "tag" "(*)" ")" | "(" "tag" <tag-expr> ")" ; <tag>:: "(" "tag" "(*)" ")" | "(" "tag" <tag-expr> ")" ;
The form (tag (*)) means "all permissions". The form "(tag (*))" means "all permissions".
The simplest tag is an S-expression with no *-forms. This is a The simplest tag is an S-expression with no *-forms. This is a
specific permission which must be passed along and used intact. specific permission which must be passed along and used intact.
A tag with *-forms represents a set of specific permissions. Any A tag with *-forms represents a set of specific permissions. Any
subset of such a set of permissions may be delegated by a principal subset of such a set of permissions may be delegated by a principal
empowered to delegate. When one is reducing the 5-tuples from such empowered to delegate. When one is reducing the 5-tuples from such
certificates, one intersects the adjacent tag sets to find a certificates, one intersects the adjacent tag sets to find a
resulting tag set. Full tag intersection rules are given later. resulting tag set.
All tags are assumed to be positional. That is, parameters in a tag All tags are assumed to be positional. That is, parameters in a tag
have a meaning defined by their position. have a meaning defined by their position.
All tags are assumed to be extendable. That is, if one adds a field All tags are assumed to be extendable. That is, if one adds a field
to the end of a tag definition, one is restricting the permission to the end of a tag definition, one is restricting the permission
granted. [If the field added makes the tag invalid, then one has granted. [If the field added makes the tag invalid, then one has
restricted the original permission to zero.] restricted the original permission to zero.]
The full tag body BNF is: See the full BNF section for the full tag body BNF, including
specification of *-forms.
<tag-expr>:: <simple-tag> | <tag-set> | <tag-string> ;
<simple-tag>:: "(" <byte-string> <tag-expr>* ")" ;
<tag-set>:: "(" "*" "set" <tag-expr>* ")" ;
<tag-string>:: <byte-string> | <tag-range> | <tag-prefix> ;
<tag-range>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>?
")" ;
<range-ordering>:: "alpha" | "numeric" | "time" | "binary" | "date" ;
<low-lim>:: <gte> <byte-string> ;
<gte>:: "g" | "ge" ;
<up-lim>:: <lte> <byte-string> ;
<lte>:: "l" | "le" ;
<tag-prefix>:: "(" "*" "prefix" <byte-string> ")" ;
4.9 <valid> 4.9 <valid>
The <valid> field gives validity dates and/or on-line test The <valid> field gives validity dates and/or on-line test
information for the cert. information for the certificate.
<valid>:: <not-before>? <not-after>? <online-test>? ; <valid>:: <not-before>? <not-after>? <online-test>* ;
<not-after>:: "(" "not-after" <date> ")" ; <not-after>:: "(" "not-after" <date> ")" ;
<not-before>:: "(" "not-before" <date> ")" ; <not-before>:: "(" "not-before" <date> ")" ;
The not-after and not-before options are self-explanatory. If either 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 is missing, then the certificate is assumed valid for all time in
direction. For example, one might omit the <not-before> field, if that direction. For example, one might omit the <not-before> field,
that date would be before or at the time of creation of the cert, if that date would be before or at the time of creation of the
unless one wanted to note the creation time for documentary purposes. certificate, unless one wanted to note the creation time for
documentation purposes.
4.9.1 <date> 4.9.1 <date>
<date>:: <byte-string> ; <date>:: <byte-string> ;
A date field is an ASCII byte string of the form: A date field is an ASCII byte string of the form:
YYYY-MM-DD_HH:MM:SS YYYY-MM-DD_HH:MM:SS
always UTC. For internal use, it is treated as a normal byte string. 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- For example, "1997-07-26_23:15:10" is a valid date. So is
01_00:00:00". <date> fields are compared as normal ASCII byte "2001-01-01_00:00:00". <date> fields are compared as normal ASCII
strings since one never needs to compute the size of a time interval byte strings since one never needs to compute the size of a time
to test validity -- only determine greater-than, less-than or equal. interval to test validity -- only determine greater-than, less-than
or equal.
4.9.2 <online-test> 4.9.2 <online-test>
<online-test>:: "(" "online" <online-type> <uri> <principal> <s- <online-test>:: "(" "online" <online-type> <uris> <principal> <s-
part>* ")" ; part>* ")" ;
<online-type>:: "crl" | "reval" | "one-time" ; <online-type>:: "crl" | "reval" | "one-time" ;
The online test option allows a cert to be backed up by finer grain The online test option allows a certificate to be backed up by finer
validity testing. The reply from an online test is a digitally grain validity testing. The reply from an online test is a digitally
signed object, validated by the <principal> given in the test signed object, validated by the <principal> given in the test
specification. That object includes validity dates, so that once one specification. That object includes validity dates, so that once one
has the online test response, its validity dates can be intersected has the online test response, its validity dates can be intersected
with the parent cert's validity dates to yield the current working with the parent certificate's validity dates to yield the current
validity dates for the cert. working validity dates for the certificate.
The crl form tells the verifier (or prover, who fetches this The crl form tells the verifier (or prover, who fetches this
information for the verifier, in our standard model), the current information for the verifier, in our standard model), the current
list of invalid certs. If the present cert is not on that list, then list of invalid certificates. If the present certificate is not on
the cert is presumed valid. that list, then the certificate is presumed valid.
The revalidate form is the logical opposite of the crl. It tells the The re-validate form is the logical opposite of the crl. It tells
verifier a list of valid certs -- or, just that the current cert is the verifier a list of valid certificates or, more likely, just that
valid. the current certificate is valid.
The one-time form is a revalidate form without validity dates. It The one-time form is a re-validate form without validity dates. It
must be fetched by the verifier, rather than the prover, since it is 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 valid only for the current verification step. [In effect, it has a
validity period of just "now".] The process of getting this one-time validity period of just "now".] The process of getting this one-time
revalidation involves sending a unique (and partly random) challenge revalidation involves sending a unique (and partly random) challenge
which is returned as part of the signed response. which is returned as part of the signed response.
See section 6 for a full description of on-line test request and If there are multiple URIs specified, any one of them can be used.
reply formats.
If the URI specifies an HTTP connection to the on-line test, then
that URI can provide all parameters needed (e.g., a hash of the
certificate in question), but in other cases, one might need to list
such parameters in the optional <s-part>s.
See section 7 for a full description of on-line test reply formats.
4.10 <comment> 4.10 <comment>
<comment>:: "(" "comment" <byte-string> ")" ; <comment>:: "(" "comment" <byte-string> ")" ;
This optional field allows the issuer to attach comments meant to be 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. ignored by any processing code but presumably to be read by a human.
5. Name certificate 5. Name certificate
Names are defined for human convenience. For actual trust engine Names are defined for human convenience. For actual trust engine
computations, names must be reduced to keys. This section gives the computations, names must be reduced to keys. This section gives the
form of a name certificate and the rules for reducing name form of a name, a name certificate and the rules for reducing name
certificates to simple mappings from name to key. certificates to simple mappings from name to key.
Note that we do not include an <issuer-loc> option for a name Note that we do not include an <issuer-loc> option for a name
certificate. The issuer needs no authorization in order to create certificate. The issuer needs no authorization in order to create
names. Every issuer has that right. names. Every issuer has that right.
Similarly, there is no "certification practice statement" for these Similarly, there is no "certification practice statement" for these
name certificates. Nothing is implied by a name certificate about name certificates. Nothing is implied by a name certificate about
the principal(s) being named. There are no constraints on name the principal(s) being named. A name can be an arbitrary byte string
choice. A name can be an arbitrary byte string assigned by the assigned by the issuer and is intended to be meaningful only to that
issuer. It is not required or expected necessarily to conform to any issuer, although other parties may end up using it. A name is not
name string in the 3D world or in any other issuer's name space. required or expected necessarily to conform to any name string in the
physical world or in any other issuer's name space.
That said, it is possible to map name certificates generated by a That said, it is possible to map name certificates generated by a
commercial Certification Authority into SDSI names and thus refer to commercial Certification Authority into SDSI names and thus refer to
keys defined in that world from within SPKI/SDSI certificates. keys defined under that process from within SPKI/SDSI certificates.
5.1 Name cert syntax 5.1 Name certificate syntax
A name certificate has the form: A name certificate has the form:
(cert (cert
(issuer (name <prin> <name>)) (issuer (name <principal> <name>))
(subject ...) <subject>
<validity fields> <valid>
) )
<name-cert>:: "(" "cert" <version>? <cert-display>? <issuer-name> <name-cert>:: "(" "cert" <version>? <cert-display>? <issuer-name>
<subject> <valid> <comment> ")" ; <subject> <valid> <comment>? ")" ;
<issuer-name>:: "(" "issuer" "(" "name" <principal> <byte-string> ")" <issuer-name>:: "(" "issuer" "(" "name" <principal> <byte-string> ")"
")" ; ")" ;
That form maps directly into the intermediate form needed for name That form maps directly into the intermediate form needed for name
string reduction. The (tag) field is omitted and (tag (*)) is string reduction. The name must be under the <principal> of the
assumed. certificate issuer, and under this syntax the certificate issuer
<principal> is taken from the (name..) structure.
It is not syntactically possible to have delegation or authorization In a name certificate, the (tag) field is omitted and (tag (*)) is
fields in a name cert. Delegation is always true, through a name assumed. There is also no <deleg> field. A name definition is like
chain, and authorization is always (*). A name definition is like an an extension cord, passing everything the name is granted through to
extension cord, passing everything the name is granted through to the the subject.
subject.
The subject is unrestricted. It is what you are trying to name. The subject is unrestricted. It is what you are trying to name.
If there is more than one name certificate for a given name, with If there is more than one name certificate for a given name, with
different subjects, then that name is a group. More specifically, different subjects, then that name is a group. More specifically,
all name certificates define groups, many of which will have only one all name certificates define groups, many of which will have only one
member. A multi-member group is like a multi-plug extension cord, member. A multi-member group is like a multi-plug extension cord,
passing everything the name is granted through to all of its passing everything the name is granted through to any and all of its
subjects. subjects.
5.2 Name reduction 5.2 <name>
A name by itself is of little value. To be used, it must be reduced The <name> form is a option for <subject>, when one wants to generate
to a principal. The rules of reduction allow intermediate forms a certificate granting authorization to either a named group of
which grow in length, but the value of a name is a single principal principals or to a principal that has not been defined yet. This can
(or set of principals). Name reduction produces principals from be either a relative name or a fully-qualified name.
names. In the process, however, it can produce longer name strings.
<name>:: <relative-name> | <fq-name> ;
<relative-name>:: "(" "name" <names> ")" ;
<fq-name>:: "(" "name" <principal> <names> ")" ;
<names>:: <byte-string>+ ;
A relative name is defined only with respect to an issuer and should
show up only in a certificate, borrowing the <principal> from the
issuer of that certificate. For evaluation purposes, the relative
name is translated into a fully-qualified name before reduction.
Unlike the <issuer-name>, which is forced to be a name in the
issuer's name space, the subject name can be in any name space.
5.3 Name reduction
Given the name definition
(cert
(issuer
(name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred))
(subject (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|))
(not-after "2001-01-01_00:00:00"))
{KDQ6Y2VydCg2Omlzc3Vlcig0Om5hbWUoNDpoYXNoMzptZDUxNjpPGjPUbEr
+4G8lvHemsiETKTQ6ZnJlZCkpKDc6c3ViamVjdCg0Omhhc2gzOm1kNTE2Ome
acQg+uGMIEtSGOEYetaApKSg5Om5vdC1hZnRlcjE5OjIwMDEtMDEtMDFfMDA
6MDA6MDApKQ==}
the name
(subject (name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred sam george
mary))
reduces to
(subject (name (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|) sam george
mary))
recursing until the name reduces to a principal. In non-pathological
cases this is the only reduction rule needed.
It is possible for someone to generate a trouble-making name
certificate, such as:
(cert
(issuer
(name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred))
(subject (name fred sam))
(not-after "2001-01-01_00:00:00"))
in which case the reduction would grow without bound. Pairs of principals
could conspire to produce loops of name definition. Therefore, the name
reduction code needs to do loop detection.
6. ACL and Sequence formats
ACL and sequence structures are in the grey area. ACLs are private to
one developer or application. Sequences can be thought of as part of
the protocol using certificates.
6.1 <acl>
<acl>:: "(" "acl" <version>? <acl-entry>* ")" ;
<acl-entry>:: "(" "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. Since an ACL is
not communicated to others, developers are free to choose their
own formats.
If all the optional fields are left out, the subject is given the
permission specified in <tag>, without permission to delegate it, with
no expiration date or condition (until the ACL is edited to remove the
permission).
For example: For example:
<(K1 N1),(K2 N2 N3)> + <(K2 N2),K3> -> <(K1 N1),(K3 N3)> (acl
(entry
(name (hash md5 |p1isZirSN3CBscfNQSbiDA==|) sysadmin/operators)
(tag (ftp db.acme.com root)))
(entry
(hash md5 |M7cDVmX3r4xmab2rxYqyNg==|)
(tag (ftp db.acme.com root)))
(entry
(hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|)
(propagate)
(tag (http http://www.internal.acme.com/accounting/)))
)
<(K1 N1),(K2 N2)> + <(K2 N2),(K3 N3)> -> <(K1 N1),(K3 N3)> {KDM6YWNsKDU6ZW50cnkoNDpuYW1lKDQ6aGFzaDM6bWQ1MTY6p1isZirSN3C
BscfNQSbiDCkxODpzeXNhZG1pbi9vcGVyYXRvcnMpKDM6dGFnKDM6ZnRwMTE
6ZGIuYWNtZS5jb200OnJvb3QpKSkoNTplbnRyeSg0Omhhc2gzOm1kNTE2OjO
3A1Zl96+MZmm9q8WKsjYpKDM6dGFnKDM6ZnRwMTE6ZGIuYWNtZS5jb200OnJ
vb3QpKSkoNTplbnRyeSg0Omhhc2gzOm1kNTE2OpLl8qsfI2FnWf4+1X36/so
pKDk6cHJvcGFnYXRlKSgzOnRhZyg0Omh0dHA0MDpodHRwOi8vd3d3LmludGV
ybmFsLmFjbWUuY29tL2FjY291bnRpbmcvKSkpKQ==}
<(K1 N1),(K2 N2 N4)> + <(K2 N2),(K3 N3 N5)> -> <(K1 N1),(K3 N3 N5 6.2 <sequence>
N4)>
where K# are principals and N# are name strings. <sequence>:: "(" "sequence" <seq-ent>* ")" ;
<seq-ent>:: <cert> | <pub-key> | <signature> | <crl> | <delta-crl> |
<reval> | <op> ;
<op>:: <hash-op> | <general-op> ;
<hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ;
<general-op>:: "(" "do" <byte-string> <s-part>* ")" ;
6. On-line test reply formats A <sequence> is a bundled sequence of objects that the verifier is to
consider when deciding to grant access. We anticipate having the
prover (who constructs and submits the <sequence>) provide elements
in order, so that the verifier need only process the <sequence> in
order while proving to itself that the prover has the claimed access
right, but that is a developer decision.
Given here is the BNF for on-line test replies. This section does The sequence can also contain instructions to the verifier, in the
not give details of protocols for connecting to online servers or form of opcodes. At present the only opcode defined is "hash" --
transmitting messages between them. It is assumed that, for example, meaning, that the previous item in the sequence (the last one read
the requester can provide a URI and use HTTP, while the URI includes in) is to be hashed by the given algorithm and saved, indexed by that
any parameters the requester needs to pass along. The reply from the hash value. Presumably, that item (certificate body or public key,
on-line source will be in canonical form, according to the BNF given for example) is referred to by hash in some subsequent object.
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 At this time, we assume that <signature> does double duty, calling
for the hash of the preceding item. However, it would not hurt to
use an explicit <hash-op> prior to a <signature>.
The full or delta CRL is: If an object will be referenced by different hashes, it can be
followed by multiple <hash-op>s.
<crl>:: "(" "crl" <version> <hash-list> <valid-basic> ")" ; Additional <op>s might be defined for some algorithms doing
threshold-subject reduction (e.g., an <op> to push the current
5-tuple on a stack).
<hash-list>:: "(" "canceled" <hash>* ")" ; 7. On-line test reply formats
<delta-crl>:: "(" "delta-crl" <version> <hash-of-crl> <hash-list> An on-line test results in a digitally signed object carrying its own
<valid-basic> ")" ; date range, explicitly or implicitly. That object specifies either a
list of invalid certificates or that a given certificate (or list of
certificates) is still valid.
This section does not give details of protocols for connecting to
online servers or transmitting messages between them.
7.1 CRL and delta-CRL
If one wants to provide CRLs, and that CRL grows, then one may prefer
to send only a delta CRL.
<crl>:: "(" "crl" <version>? <hash-list> <valid-basic> ")" ;
<hash-list>:: "(" "canceled" <hash>* ")" ;
<delta-crl>:: "(" "delta-crl" <version>? <hash-of-crl> <hash-list>
<valid-basic> ")" ;
<hash-of-crl>:: <hash> ; <hash-of-crl>:: <hash> ;
and should be signed by the principal indicated in the (online...) The <hash-of-crl> should probably have a URI pointing to the location
field which directed the CRL to be fetched. of the full CRL.
The CRL request can be a straight HTTP transaction, using the URI The <crl> or <delta-crl> should be signed by the principal indicated
provided in the cert, but we do not specify online protocols in this in the (online...) field which directed the CRL to be fetched.
draft.
If the verifier has a complete CRL, then it can provide the hash of The CRL request can be a straight HTTP transaction, using the URI
that CRL in whatever protocol is chosen and get back just the provided in the certificate, but we do not specify online protocols
additions to the previous CRL, in the form of a <delta-crl> in this draft.
6.2 Revalidation The protocol for choosing between delta and full CRL is left open.
One can always provide the delta and let the caller fetch the full
specifically, for example.
<reval>:: "(" "reval" <version> <subj-hash> <valid-basic> ")" ; 7.2 Revalidation
<reval>:: "(" "reval" <version>? <subj-hash> <valid-basic> ")" ;
<subj-hash>:: "(" "cert" <hash> ")" ; <subj-hash>:: "(" "cert" <hash> ")" ;
This construct specifies the hash of the current cert as <subj-hash>
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 This construct specifies the hash of the current certificate as
provided in the (online...) field, but we do not specify online <subj-hash> and gives a new validity period for that certificate. It
protocols in this draft. should be signed by the <principal> indicated in the (online...)
field which directed it to be fetched.
6.3 One-time revalidation 7.3 One-time revalidation
For one-time revalidation, the verifier itself must fetch the (reval) For one-time revalidation, the verifier itself must fetch the (reval)
record, which will have the form: record, which will have the form:
<reval>:: "(" "reval" <version> <subj-hash> <one-valid> ")" ; <reval>:: "(" "reval" <version>? <subj-hash> <one-valid> ")" ;
<one-valid>:: "(" "one-time" <byte-string> ")" ; <one-valid>:: "(" "one-time" <byte-string> ")" ;
with the byte string inside <one-valid> being one provided by the where the byte string inside <one-valid> is one provided by the
caller, expected to be unique over time and unguessable -- e.g., a caller, expected to be unique over time and unguessable -- e.g., a
large random number or random number plus sequence number. This large random number or random number plus sequence number. This
reply should be signed by the <principal> indicated in the (online..) reply should be signed by the <principal> indicated in the (online..)
field which directed it to be fetched. field which directed it to be fetched.
This result, if successful, yields a Validity value for the 5-tuple This result corresponds to a 0-length validity interval of "now",
of "now". however the developer wishes to express that.
7. 5-Tuple Reduction 8. 5-Tuple Reduction
This section describes the operation of the trust evaluation This section describes the operation of the trust evaluation
machinery assumed to be part of every verifier which accepts SPKI machinery assumed to be part of every verifier which accepts SPKI
certificates. The inputs to that trust engine are 5-tuples and any certificates. The inputs to that trust engine are 5-tuples and any
kind of certificate, not just SPKI, as well as Access Control List 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 (ACL) entries can be translated to 5-tuples so that they can all
participate in the trust computation. participate in the trust computation.
A 5-tuple is an internal construct and therefore best described by a A 5-tuple is an internal construct and therefore best described by a
programming language data structure. A separate document will give programming language data structure. A separate document will give
the 5-tuple reduction code and those data structures. the 5-tuple reduction code and those data structures.
For this purpose, we describe the content in BNF, but want to make Name reduction is specified in section 5.3. Therefore, in what
sure that a 5-tuple will never be expressed in canonical BNF form, follows we assume all issuers and subjects are principals. We also
transmitted in that form, etc. The <5-tuple> differs from a <cert> assume that all principals are public keys. It is an implementation
by leaving out some fields of an authorization cert and by including decision whether to store these as explicit keys, hashes of keys
some absent fields for a name cert. (used as pointers) or addresses pointing to keys.
7.1 <5-tuple> BNF 8.1 <5-tuple> BNF
A 5-tuple is a positional construct of the form: How a 5-tuple is represented and stored is up to the developer. For
the sake of discussion, we assume a 5-tuple is a construct of the
form:
<5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ; <5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ;
<issuer5>:: <key5> | <i-name5> | "self" ; <issuer5>:: <key5> | "self" ;
<subject5>:: <key5> | <fq-name5> | <obj-hash> | <keyholder> | <subject5>:: <key5> | <obj-hash> | <keyholder> | <threshold-subj> ;
<threshold-subj> ;
<deleg5>:: "t" | "f" ; <deleg5>:: "t" | "f" ;
<key5>:: <pub-key> | <sec-key> ; <key5>:: <pub-key> ;
<i-name5>:: "(" "name" <key5> <name> ")" ;
<fq-name5>:: "(" "name" <key5> <names> ")" ;
<valid5>:: <valid-basic> | "null" ; <valid5>:: <valid-basic> | "null" | "now" ;
<tag-body5>:: <tag-body> | "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
key but referred to it by different hash algorithms.
The extra option for issuer, "self", is provided for ACL entries. The extra option for issuer, "self", is provided for ACL entries.
The self referred to is the verifier, holding that ACL and doing the The self referred to is the verifier, holding that ACL and doing the
verification of offered proofs. verification of offered proofs.
The only 5-tuples that can mean anything to the verifier, after The only 5-tuples that can mean anything to the verifier, after
reduction is done, are those with "self" as issuer. reduction is done, are those with "self" as issuer.
7.2 Bare-bones case 8.2 Top level reduction rule
In a bare-bones SPKI cert, 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: <i1,s1,d1,a1,v1> + <i2,s2,d2,a2,v2> yields <i1,s2,d2,a,v> if:
s1 = i2 s1 = i2
d1 = "t" d1 = "t"
a = the intersection of a1 and a2 a = the intersection of a1 and a2
v = the intersection of v1 and v2 v = the intersection of v1 and v2
Validity intersection involves normal intersection of date ranges, if Validity intersection involves normal intersection of date ranges, if
there are not-before or not-after fields in v1 or v2, and union of 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 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 includes a validity period, so there is a resulting validity interval
in terms of dates. This can include the string "now", as the product 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 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 range to yield either "now" or "null".
interval, then the certificates don't reduce.
The intersection of a1 and a2 in the basic case is given by the The intersection of a1 and a2 is given below. In the most basic
following rules: case,
If a1 is (tag (*)), a = a2. If a1 is (tag (*)), a = a2.
If a2 is (tag (*)), a = a1. If a2 is (tag (*)), a = a1.
If a1 == a2, a = a2. If a1 == a2, a = a2.
Otherwise, a = "null" and the 5-tuple doesn't reduce. Otherwise, a = "null" and the 5-tuple doesn't reduce.
7.3 Intersection of *-form tag sets 8.3 Intersection of tag sets
It is assumed that normal verification will proceed from right to
left -- that is, that a specific desired result tag will be
intersected with a general tag. Therefore, the only intersection
rules needed are those between *-forms and *-free tag elements. Such
an intersection will yield either "null" or a *-free tag.
The intersection rules are intuitive and recurse down into tag S-
expressions and along lists.
(* set ...):
a *-free <tag-expr> intersects with a (* set ...) to yield the *-free
<tag-expr> if that expression is an element of the set.
(* range ...):
a *-free <tag-expr> intersects with a (* range ...) to yield the *-
free <tag-expr> if the expression is a byte string contained within
the specified range. Otherwise, the intersection fails.
(* prefix ...):
a *-free <tag-expr> intersects with a (* prefix S1) to yield the *-
free <tag-expr> if the expression is a byte string starting with
string S1. Otherwise, the intersection fails.
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.
<i1,s1> + <i2,s2> yields <i1,s2> if:
s1 = i2
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>).
An Issuer 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),(name k2 n_1 .. n_m)> + <(name k2 n_1),(name k3 t_1 ..
t_u)>
where n_1 is assumed to be the same on both sides of the + operator.
The reduction is then:
<(name k1 r_1),(name k3 t_1 ... t_u n_2 ... n_m)>
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)>
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. Algorithms to find certificate paths and
avoid such loops have been developed by Ron Rivest and his SPKI
implementers, so we know that such are possible.
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
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 Two <tag> S-expressions intersect by the following rules. Note that
top of the normal stack and normal cert processing proceeds, up to in most cases, one of the two tag S-expressions will be free of
the point where the k-of-n cert would be required. At this point, *-forms. A developer is free to implement general purpose code that
another does set-to-set reductions, for example, but that is not likely to be
necessary.
(do copy) 1. basic: if a1 == a2, then the result is a1.
fetches another copy of the right end of this thread (the merge 2. basic: if a1 != a2 and neither has a *-form, then the result is
point) and another cert thread is processed. "null".
When all K threads are processed, the k-of-n cert is presented, the 3. (tag (*)): if a1 == (tag (*)), then the result is a2.
auxiliary stack is popped, and the k-of-n cert combines with the K If a2 == (tag (*)), then the result is a1.
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.
7.6 Authorization Loops 4. (* set ...): if some <tag> S-expression contains a (* set )
construct, then one expands the set and does the intersection of
the resulting simpler S-expressions.
By 5-tuple reduction, some chains of authorization statements will be 5. (* range ...): if some <tag> field compares a (* range ) to a
reduced to the form: <byte-string>, one does the specified range comparison and the
resulting field is the explicit one tested.
(self,X,D,A,V) 6. (* prefix ...): if some <tag> field compares a (* prefix ) to a
<byte-string>, then the result is the explicit string if the
test string is a prefix of it and otherwise "null".
where "self" represents the entity doing the verification, granting 8.4 Reduction of (subject (threshold ..))
access, etc. Such a 5-tuple says "Self says (I say) that X has
authority (D,A) for validity period (or conditions) V". In other
words, self has decided what it can trust about X.
Any authorization chain not reducing to a 5-tuple with self as issuer A separate document will give full algorithms for reduction of K-of-N
isn't relevant to decisions by self. threshold subjects. One general procedure is to make K copies of of
the 5-tuple containing the K-of-N subject and indicate which of those
subjects is being handled by that copy. One then reduces that copy
as if it had a single subject. One can stop the separate reductions
when all K of the reduced values have the same subject. At that
point, the K reduced 5-tuples become a single 5-tuple.
Therefore, any authorization chain which is to be used by self to do The actual algorithm choices for doing this reduction depend on
trust management must have self as a root. Since self is doing this whether one wants to reduce left-to-right or right-to-left and how
chain reduction and is therefore at the receiving end of the chain as much storage a verifier has.
well, that makes all useful authorization chains loops.
7.7 Certificate Result Certificates 8.7 Certificate Result Certificates
In cases where the verifier, Self, has access to a private key, once 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: it has reduced a chain of certificate bodies down to the form:
(Self,X,D,A,V) (Self,X,D,A,V)
it can sign that generated body, using its private key, producing an it can sign that generated body, using its private key, producing an
SPKI certificate. That certificate will have a validity period no SPKI certificate. That certificate will have a validity period no
larger that of any certificate in the loop which formed it, but 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 during that validity period it can be used by the prover instead of
the full chain, when speaking to that particular verifier. It is the full chain, when speaking to that particular verifier. It is
good only at that verifier (or at another which trusts that verifier, good only at that verifier (or at another which trusts that verifier,
Self, to delegate the authorization A). Therefore, one option by the 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 verifier is to sign and return the result 5-tuple to the caller for
this later use. this later use.
If it isn't important for any other verifier to accept this "result 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 certificate", it can even be signed by a symmetric key (an HMAC with
secret key private to the verifier). secret key private to the verifier), although such keys are not
defined in this standard.
The certificates which made up the loop forming this result 5-tuple 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 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 DNSSEC. They could also be PGP signed keys processed by an enriched
trust engine (one capable of dealing with the PGP web of trust trust engine (one capable of dealing with the PGP web of trust
rules). If the verifier, Self, were to be trusted to delegate the rules). If the verifier, Self, were to be trusted to delegate the
resulting authorization, its certificate result certificate then resulting authorization, its certificate result certificate then
becomes a mapping of these other forms. This may prove especially becomes a mapping of these other forms. This may prove especially
useful if a given certificate chain includes multiple forms or if the useful if a given certificate chain includes multiple forms or if the
result certificate is to be used by a computationally limited device 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 (such as a Smart-Card) which can not afford the code space to process
some of the more complex certificate formats. some of the more complex certificate formats.
8. Full BNF 9. Full BNF
8.1 Top Level Objects The following is the BNF of canonical forms and includes lengths for
each explicit byte string. So, for example, "cert" is expressed as
"4:cert".
9.1 Top Level Objects
The list of BNF rules that follows is sorted alphabetically, not The list of BNF rules that follows is sorted alphabetically, not
grouped by kind of definition. The top level objects defined are: grouped by kind of definition. The top level objects defined are:
<5-tuple>: an object defined for documentation purposes only. The <5-tuple>: an object defined for documentation purposes only. The
actual contents of a 5-tuple are implementation dependent. actual contents of a 5-tuple are implementation dependent.
<acl>: an object for local use which might be implementation <acl>: an object for local use which might be implementation
dependent. An ACL is not expected to be communicated from machine to dependent. An ACL is not expected to be communicated from machine to
machine. machine.
<crl>, <delta-crl> and <reval>: objects returned from on-line tests. <crl>, <delta-crl> and <reval>: objects returned from on-line tests.
<sequence>: the object carrying keys and certificates from machine to <sequence>: the object carrying keys, certificates and on-line test
machine. results from prover to verifier.
8.2 Alphabetical List of BNF Rules 9.2 Alphabetical List of BNF Rules
<5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ; <5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ;
<acl-entry>:: "(" "entry" <subj-obj> <deleg>? <tag> <valid>? <acl-entry>:: "(" "entry" <subj-obj> <deleg>? <tag> <valid>?
<comment>? ")" ; <comment>? ")" ;
<acl>:: "(" "acl" <version>? <acl-entry>* ")" ; <acl>:: "(" "acl" <version>? <acl-entry>* ")" ;
<byte-string>:: <bytes> | <display-type> <bytes> ; <byte-string>:: <bytes> | <display-type> <bytes> ;
<bytes>:: <decimal> ":" {binary byte string of that length} ; <bytes>:: <decimal> ":" {binary byte string of that length} ;
<cert-display>:: "(" "display" <byte-string> ")" ; <cert-display>:: "(" "display" <byte-string> ")" ;
<cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>? <cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>?
<subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ; <subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ;
<comment>:: "(" "comment" <byte-string> ")" ; <comment>:: "(" "comment" <byte-string> ")" ;
<crl>:: "(" "crl" <version> <hash-list> <valid-basic> ")" ; <crl>:: "(" "crl" <version>? <hash-list> <valid-basic> ")" ;
<date>:: <byte-string> ; <date>:: <byte-string> ;
<ddigit>:: "0" | <nzddigit> ; <ddigit>:: "0" | <nzddigit> ;
<decimal>:: <nzddigit> <ddigit>* | "0" ; <decimal>:: <nzddigit> <ddigit>* | "0" ;
<deleg5>:: "t" | "f" ; <deleg5>:: "t" | "f" ;
<deleg>:: "(" "propagate" ")" ; <deleg>:: "(" "propagate" ")" ;
<delta-crl>:: "(" "delta-crl" <version> <hash-of-crl> <hash-list> <delta-crl>:: "(" "delta-crl" <version>? <hash-of-crl> <hash-list>
<valid-basic> ")" ; <valid-basic> ")" ;
<display-type>:: "[" <bytes> "]" ; <display-type>:: "[" <bytes> "]" ;
<fq-name5>:: "(" "name" <key5> <names> ")" ;
<fq-name>:: "(" "name" <principal> <names> ")" ; <fq-name>:: "(" "name" <principal> <names> ")" ;
<general-op>:: "(" "do" <byte-string> <s-part>* ")" ; <general-op>:: "(" "do" <byte-string> <s-part>* ")" ;
<gte>:: "g" | "ge" ; <gte>:: "g" | "ge" ;
<hash-alg-name>:: "md5" | "sha1" | <uri> ; <hash-alg-name>:: "md5" | "sha1" | <uri> ;
<hash-list>:: "(" "canceled" <hash>* ")" ; <hash-list>:: "(" "canceled" <hash>* ")" ;
<hash-of-crl>:: <hash> ; <hash-of-crl>:: <hash> ;
<hash-of-key>:: <hash> ; <hash-of-key>:: <hash> ;
<hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ; <hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ;
<hash-value>:: <byte-string> ; <hash-value>:: <byte-string> ;
<hash>:: "(" "hash" <hash-alg-name> <hash-value> <uri>? ")" ; <hash>:: "(" "hash" <hash-alg-name> <hash-value> <uris> ")" ;
<i-name5>:: "(" "name" <key5> <name> ")" ; <issuer-loc>:: "(" "issuer-info" <uris> ")" ;
<issuer-loc>:: "(" "issuer-info" <uri>* ")" ;
<issuer-name>:: "(" "issuer" "(" "name" <principal> <byte-string> ")" <issuer-name>:: "(" "issuer" "(" "name" <principal> <byte-string> ")"
")" ; ")" ;
<issuer5>:: <key5> | <i-name5> | "self" ; <issuer5>:: <key5> | "self" ;
<issuer>:: "(" "issuer" <principal> ")" ; <issuer>:: "(" "issuer" <principal> ")" ;
<k-val>:: <byte-string> ; <k-val>:: <byte-string> ;
<key5>:: <pub-key> | <sec-key> ; <key5>:: <pub-key> ;
<keyholder-obj>:: <principal> | <name> ; <keyholder-obj>:: <principal> | <name> ;
<keyholder>:: "(" "keyholder" <keyholder-obj> ")" ; <keyholder>:: "(" "keyholder" <keyholder-obj> ")" ;
<low-lim>:: <gte> <byte-string> ; <low-lim>:: <gte> <byte-string> ;
<lte>:: "l" | "le" ; <lte>:: "l" | "le" ;
<n-val>:: <byte-string> ; <n-val>:: <byte-string> ;
<name-cert>:: "(" "cert" <version>? <cert-display>? <issuer-name> <name-cert>:: "(" "cert" <version>? <cert-display>? <issuer-name>
<subject> <valid> <comment> ")" ; <subject> <valid> <comment>? ")" ;
<name>:: <relative-name> | <fq-name> ; <name>:: <relative-name> | <fq-name> ;
<names>:: <byte-string>+ ; <names>:: <byte-string>+ ;
<not-after>:: "(" "not-after" <date> ")" ; <not-after>:: "(" "not-after" <date> ")" ;
<not-before>:: "(" "not-before" <date> ")" ; <not-before>:: "(" "not-before" <date> ")" ;
<nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; <nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
<obj-hash>:: "(" "object-hash" <hash> ")" ; <obj-hash>:: "(" "object-hash" <hash> ")" ;
<one-valid>:: "(" "one-time" <byte-string> ")" ; <one-valid>:: "(" "one-time" <byte-string> ")" ;
<online-test>:: "(" "online" <online-type> <uri> <principal> <s- <online-test>:: "(" "online" <online-type> <uris> <principal> <s-
part>* ")" ; part>* ")" ;
<online-type>:: "crl" | "reval" | "one-time" ; <online-type>:: "crl" | "reval" | "one-time" ;
<op>:: <hash-op> | <general-op> ; <op>:: <hash-op> | <general-op> ;
<principal>:: <pub-key> | <hash-of-key> ; <principal>:: <pub-key> | <hash-of-key> ;
<pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uri>* ")" ; <pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uris> ")" ;
<pub-sig-alg-id>:: "rsa-pkcs1-md5" | "rsa-pkcs1-sha1" | "dsa-sha1" | <pub-sig-alg-id>:: "rsa-pkcs1-md5" | "rsa-pkcs1-sha1" | "rsa-pkcs1" |
<uri> ; "dsa-sha1" | <uri> ;
<range-ordering>:: "alpha" | "numeric" | "time" | "binary" | "date" ; <range-ordering>:: "alpha" | "numeric" | "time" | "binary" | "date" ;
<relative-name>:: "(" "name" <names> ")" ; <relative-name>:: "(" "name" <names> ")" ;
<reval-body>:: <one-valid> | <valid-basic> ; <reval-body>:: <one-valid> | <valid-basic> ;
<reval>:: "(" "reval" <version> <subj-hash> <reval-body> ")" ; <reval>:: "(" "reval" <version>? <subj-hash> <reval-body> ")" ;
<s-expr>:: "(" <byte-string> <s-part>* ")" ; <s-expr>:: "(" <byte-string> <s-part>* ")" ;
<s-part>:: <byte-string> | <s-expr> ; <s-part>:: <byte-string> | <s-expr> ;
<sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>* ")" ; <seq-ent>:: <cert> | <name-cert> | <pub-key> | <signature> | <op> |
<sec-sig-alg-id>:: "hmac-md5" | "hmac-sha1" | "des-cbc-mac" | <uri> ; <reval> | <crl> | <delta-crl> ;
<seq-ent>:: <cert> | <name-cert> | <pub-key> | <signature> | <op> ;
<sequence>:: "(" "sequence" <seq-ent>* ")" ; <sequence>:: "(" "sequence" <seq-ent>* ")" ;
<sig-val>:: <s-part> ; <sig-val>:: <s-part> ;
<signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ; <signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ;
<simple-tag>:: "(" <byte-string> <tag-expr>* ")" ; <simple-tag>:: "(" <byte-string> <tag-expr>* ")" ;
<subj-hash>:: "(" "cert" <hash> ")" ; <subj-hash>:: "(" "cert" <hash> ")" ;
<subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> | <subj-obj>:: <principal> | <name> | <obj-hash> | <keyholder> | <subj-
<keyholder> | <subj-thresh> ; thresh> ;
<subj-thresh>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ; <subj-thresh>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ;
<subject-loc>:: "(" "subject-info" <uri>* ")" ; <subject-loc>:: "(" "subject-info" <uris> ")" ;
<subject5>:: <key5> | <fq-name5> | <obj-hash> | <keyholder> | <subj- <subject5>:: <key5> | <fq-name5> | <obj-hash> | <keyholder> | <subj-
thresh> ; thresh> ;
<subject>:: "(" "subject" <subj-obj> ")" ; <subject>:: "(" "subject" <subj-obj> ")" ;
<tag-body5>:: <tag-expr> | "null" ; <tag-body5>:: <tag-expr> | "null" ;
<tag-expr>:: <simple-tag> | <tag-set> | <tag-string> ; <tag-expr>:: <simple-tag> | <tag-set> | <tag-string> ;
<tag-prefix>:: "(" "*" "prefix" <byte-string> ")" ; <tag-prefix>:: "(" "*" "prefix" <byte-string> ")" ;
<tag-range>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>? <tag-range>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>?
")" ; ")" ;
<tag-set>:: "(" "*" "set" <tag-expr>* ")" ; <tag-set>:: "(" "*" "set" <tag-expr>* ")" ;
<tag-star>:: "(" "tag" "(*)" ")" ; <tag-star>:: "(" "tag" "(*)" ")" ;
<tag-string>:: <byte-string> | <tag-range> | <tag-prefix> ; <tag-string>:: <byte-string> | <tag-range> | <tag-prefix> ;
<tag>:: <tag-star> | "(" "tag" <tag-expr> ")" ; <tag>:: <tag-star> | "(" "tag" <tag-expr> ")" ;
<up-lim>:: <lte> <byte-string> ; <up-lim>:: <lte> <byte-string> ;
<uri>:: <byte-string> ; <uri>:: <byte-string> ;
<uris>:: "(" "uri" <uri>* ")" ;
<valid-basic>:: <not-before>? <not-after>? ; <valid-basic>:: <not-before>? <not-after>? ;
<valid5>:: <valid-basic> | "null" ; <valid5>:: <valid-basic> | "null" | "now" ;
<valid>:: <valid-basic> <online-test>? ; <valid>:: <valid-basic> <online-test>* ;
<version>:: "(" "version" <byte-string> ")" ; <version>:: "(" "version" <byte-string> ")" ;
9. Other Certificate Formats
We are aware of a number of actual and proposed kinds of signed
records which, by some definition, qualify as certificates:
1. PGP signed keys
2. X.509 identity certificates, from a number of sources
3. X.509 SET (Secure Electronic Transaction) certificates
4. DNS Security Extension signed keys
5. Signed PICS labels (from the W3C DSig effort)
It is not our intention to coerce these other certificate formats
into our mold, although they are welcome to switch over. The
certificate structure defined below is flexible enough to accommodate
all of the above.
However, we recognize that a real world system will involve some
mixture of SPKI and non-SPKI certificates as well as traditional
Access Control Lists (ACLs). Our design accommodates these by
allowing them to be mapped to 5-tuples and therefore to participate
in trust computations. Once one has reduced a possibly mixed set of
certificates into a partial or final result 5-tuple, that 5-tuple can
be signed to form a Certificate Result Certificate. This operation
can be done in all verifiers or can be done in an enterprise-wide
server reducing varied certificate forms to one simple, SPKI form.
References References
[Ab97] Abadi, Martin, "On SDSI's Linked Local Name Spaces", to appear [Ab97] Abadi, Martin, "On SDSI's Linked Local Name Spaces",
in the Proceedings of the 10th IEEE Computer Security Foundations Proceedings of the 10th IEEE Computer Security Foundations Workshop
Workshop (June 1997). (June 1997).
[BFL] Matt Blaze, Joan Feigenbaum and Jack Lacy, "Distributed Trust [BFL] Matt Blaze, Joan Feigenbaum and Jack Lacy, "Distributed Trust
Management", Proceedings 1996 IEEE Symposium on Security and Privacy. Management", Proceedings 1996 IEEE Symposium on Security and Privacy.
[CHAUM] D. Chaum, "Blind Signatures for Untraceable Payments", [CHAUM] D. Chaum, "Blind Signatures for Untraceable Payments",
Advances in Cryptology -- CRYPTO '82, 1983. Advances in Cryptology -- CRYPTO '82, 1983.
[DvH] J. B. Dennis and E. C. Van Horn, "Programming Semantics for [DvH] J. B. Dennis and E. C. Van Horn, "Programming Semantics for
Multiprogrammed Computations", Communications of the ACM 9(3), March Multiprogrammed Computations", Communications of the ACM 9(3), March
1966 1966
skipping to change at page 46, line 16 skipping to change at page 38, line 16
[PKCS1] PKCS #1: RSA Encryption Standard, RSA Data Security, Inc., 3 [PKCS1] PKCS #1: RSA Encryption Standard, RSA Data Security, Inc., 3
June 1991, Version 1.4. June 1991, Version 1.4.
[PKLOGIN] David Kemp, "The Public Key Login Protocol", working draft, [PKLOGIN] David Kemp, "The Public Key Login Protocol", working draft,
06/12/1996. 06/12/1996.
[RFC1321] R. Rivest, "The MD5 Message-Digest Algorithm", April 16 [RFC1321] R. Rivest, "The MD5 Message-Digest Algorithm", April 16
1992. 1992.
[RFC1780] J. Postel, "Internet Official Protocol Standards", March
1995.
[RFC2045] N. Freed and N. Borenstein, "Multipurpose Internet Mail [RFC2045] N. Freed and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part One: Format of Internet Message Bodies", Dec 2 Extensions (MIME) Part One: Format of Internet Message Bodies", Dec 2
1996. 1996.
[RFC2046] N. Freed and N. Borenstein, "Multipurpose Internet Mail [RFC2046] N. Freed and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part Two: Media Types", Dec 2 1996. Extensions (MIME) Part Two: Media Types", Dec 2 1996.
[RFC2047] K. Moore, "MIME (Multipurpose Internet Mail Extensions) [RFC2047] K. Moore, "MIME (Multipurpose Internet Mail Extensions)
Part Three: Message Header Extensions for Non-ASCII Text", Dec 2 Part Three: Message Header Extensions for Non-ASCII Text", Dec 2
1996. 1996.
skipping to change at page 47, line 5 skipping to change at page 39, line 5
Security Infrastructure [SDSI]", Security Infrastructure [SDSI]",
http://theory.lcs.mit.edu/~cis/sdsi.html http://theory.lcs.mit.edu/~cis/sdsi.html
[SEXP] Ron Rivest, code and description of S-expressions, [SEXP] Ron Rivest, code and description of S-expressions,
http://theory.lcs.mit.edu/~rivest/sexp.html . http://theory.lcs.mit.edu/~rivest/sexp.html .
[SRC-070] Abadi, Burrows, Lampson and Plotkin, "A Calculus for Access [SRC-070] Abadi, Burrows, Lampson and Plotkin, "A Calculus for Access
Control in Distributed Systems", DEC SRC-070, revised August 28, Control in Distributed Systems", DEC SRC-070, revised August 28,
1991. 1991.
Acknowledgments
Several independent contributions, published elsewhere on the net or
in print, worked in synergy with our effort. Especially important to
our work were: [SDSI], [BFL] and [RFC2065]. The inspiration we
received from the notion of CAPABILITY in its various forms (SDS-940,
Kerberos, DEC DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated.
Significant contributions to this effort by the members of the SPKI
mailing list and especially the following persons (listed in
alphabetic order) are gratefully acknowledged: Steve Bellovin, Mark
Feldman, John Gilmore, Phill Hallam-Baker, Bob Jueneman, David Kemp,
Angelos D. Keromytis, Paul Lambert, Jon Lasser, Jeff Parrett, Bill
Sommerfeld, Simon Spero.
Authors' Addresses Authors' Addresses
Carl M. Ellison Carl M. Ellison
CyberCash, Inc. CyberCash, Inc.
207 Grindall Street 207 Grindall Street
Baltimore MD 21230-4103 USA Baltimore MD 21230-4103 USA
Telephone: +1 410-727-4288 Telephone: +1 410-727-4288
+1 410-727-4293(FAX) +1 410-727-4293(FAX)
+1 703-620-4200(main office, Reston, Virginia, USA) +1 703-620-4200(main office, Reston, Virginia, USA)
skipping to change at page 48, line 17 skipping to change at page 40, line 33
Tatu Ylonen Tatu Ylonen
SSH Communications Security Ltd. SSH Communications Security Ltd.
Tekniikantie 12 Tekniikantie 12
FIN-02150 ESPOO FIN-02150 ESPOO
Finland Finland
E-mail: ylo@ssh.fi E-mail: ylo@ssh.fi
Expiration and File Name Expiration and File Name
This draft expires 26 May 1998. This draft expires 18 September 1998.
Its file name is draft-ietf-spki-cert-structure-03.txt Its file name is draft-ietf-spki-cert-structure-05.txt
 End of changes. 211 change blocks. 
1041 lines changed or deleted 682 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/