Simple Public Key Certificate                            Carl M. Ellison
INTERNET-DRAFT                                           CyberCash, Inc.
Expires: 26 May 18 September 1998
                                                             Bill Frantz
                                                    Electric Communities

                                                          Butler Lampson
                                                               Microsoft

                                                              Ron Rivest
                                     MIT Laboratory for Computer Science

                                                         Brian M. Thomas
                                                       Southwestern Bell

                                                             Tatu Ylonen
                                                                     SSH

                                                        21 November 1997

                                                           13 March 1998

                     Simple Public Key Certificate
                     ------ ------ --- -----------

                 <draft-ietf-spki-cert-structure-04.txt>

                <draft-ietf-spki-cert-structure-05.txt>

Status of This Document

   This document is one of three, superseding supersedes the draft filed under the name draft-ietf-spki-cert-structure-02.txt.  The discussion and
   background from draft-ietf-
   spki-cert-structure-04.txt.

   This version introduces "rsa-pkcs1" as one option for <pub-sig-alg-
   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 previous draft 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 now to be found in draft-
   ietf-spki-cert-theory-01.txt.
   ietf-spki-cert-theory-*.txt.  Examples of certificate uses are to be
   found in draft-ieft-spki-cert-examples-01.txt. 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
   to the SPKI (Simple Public Key Infrastructure) Working Group mailing
   list <spki@c2.org> <spki@c2.net> or to the authors.

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months.  Internet-Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet-
   Drafts as reference material or to cite them other than as a
   ``working draft'' or ``work in progress.''

   To learn the current status of any Internet-Draft, please check the
   1id-abstracts.txt listing contained in the Internet-Drafts Shadow
   Directories on ds.internic.net (East USA), ftp.isi.edu (West USA),
   nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe),
   munnari.oz.au (Pacific Rim), or ftp.is.co.za (Africa).

Abstract

   This document specifies a standard form of for digital certificate that
   is both more general and simpler than what is traditionally
   considered to be a certificate.  Since the word ''certificate'' was
   first used by Loren Kohnfelder in 1978 to refer to a signed record
   holding a name certificates and a public key, it has been assumed that the only
   purpose of a certificate has been to
   access control lists.  These structures bind a public key to a globally
   unique name and therefore to a person.  This binding was assumed both
   necessary and sufficient for security.

   The SPKI working group has found that the creation of a globally
   unique name is neither necessary nor sufficient for Internet security either names or electronic commerce.  In fact, it can lead
   authorizations to a security flaw.
   Therefore, we define certificate forms for binding local keys or names that resolve to
   keys (to retain security while offering the convenience of meaningful
   names) keys.  The name and for assigning authorizations to keys (to provide adequate
   information for real applications).  These forms
   authorization structures can be used alone separately 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  We use
   S-expressions as the SPKI
   mailing list standard format for these certificates and especially the following persons (listed in
   alphabetic order)
   define a canonical form for those S-expressions.

   These structures 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. also known under the name SDSI 2.0.

Table of Contents

      Status of This Document....................................1

      Abstract...................................................3
      Acknowledgments............................................3
      Abstract...................................................2

      Table of Contents..........................................4 Contents..........................................3

      1. Overview of Contents....................................6 Contents....................................5

      2. Definitions.............................................7
      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 Glossary................................................6

      3. Primitives.............................................12 Primitives..............................................8
      3.1 Canonical S-expression................................12 S-expression.................................8
      3.2 <byte-string>.........................................12 <byte-string>..........................................8
      3.3 S-expression..........................................13 S-expression...........................................9
      3.4 Encoding examples.....................................13 examples......................................9
      3.5 Use of canonical S-expressions........................14 S-expressions........................10
      3.6 Non-canonical (advanced) S-expressions................14 Advanced S-expressions................................10
      3.7 Unique IDs............................................15 IDs............................................11
      3.8 SPKI/SDSI 2.0 Objects.................................15 Primitive Objects.....................................11
      3.8.1 <pub-key>...........................................16 <pub-key>...........................................12
      3.8.2 <sec-key>...........................................17
      3.8.2.1 HMAC-MD5..........................................17
      3.8.2.2 DES-CBC-MAC.......................................17 <hash>..............................................14
      3.8.3 <hash>..............................................18
      3.8.4 <signature>.........................................19
      3.8.5 <acl>...............................................19
      3.8.6 <sequence>..........................................20 <signature>.........................................14
      3.8.3.1 <sig-val>.........................................14

      4. Authorization Certificate..............................21 Certificate..............................16
      4.1 <version>.............................................21 <version>.............................................16
      4.2 <cert-display>........................................21 <cert-display>........................................16
      4.3 <issuer>..............................................22 <issuer>..............................................17
      4.4 <issuer-loc>..........................................22 <issuer-loc>..........................................17
      4.5 <subject>.............................................22 <subject>.............................................17
      4.5.1 <name>..............................................23 <obj-hash>..........................................18
      4.5.2 <obj-hash>..........................................23 <keyholder>.........................................18
      4.5.3 <sec-key>...........................................24
      4.5.4 <keyholder>.........................................24
      4.5.5 <subj-thresh>.......................................25 <subj-thresh>.......................................18
      4.6 <subject-loc>.........................................26 <subject-loc>.........................................19
      4.7 <deleg>...............................................26 <deleg>...............................................20
      4.8 <tag>.................................................26 <tag>.................................................20
      4.9 <valid>...............................................27 <valid>...............................................20
      4.9.1 <date>..............................................28 <date>..............................................21
      4.9.2 <online-test>.......................................28 <online-test>.......................................21
      4.10 <comment>............................................29 <comment>............................................22

      5. Name certificate.......................................30 certificate.......................................23
      5.1 Name cert syntax......................................30 certificate syntax...............................23
      5.2 <name>................................................24
      5.3 Name reduction........................................31 reduction........................................24

      6. ACL and Sequence formats...............................26
      6.1 <acl>.................................................26
      6.2 <sequence>............................................27

      7. On-line test reply formats.............................32
      6.1 formats.............................28
      7.1 CRL and delta-CRL.....................................32
      6.2 Revalidation..........................................32
      6.3 delta-CRL.....................................28
      7.2 Revalidation..........................................28
      7.3 One-time revalidation.................................33

      7. revalidation.................................29

      8. 5-Tuple Reduction......................................34
      7.1 Reduction......................................30
      8.1 <5-tuple> BNF.........................................34
      7.2 Bare-bones case.......................................35
      7.3 BNF.........................................30
      8.2 Top level reduction rule..............................31
      8.3 Intersection of *-form tag sets.......................35
      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 sets..............................31
      8.4 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 ..)).................32
      8.7 Certificate Result Certificates.......................40

      8. Certificates.......................32

      9. Full BNF...............................................41
      8.1 BNF...............................................34
      9.1 Top Level Objects.....................................41
      8.2 Objects.....................................34
      9.2 Alphabetical List of BNF Rules........................41

      9. Other Certificate Formats..............................44

      References................................................45 Rules........................34

      References................................................37

      Acknowledgments...........................................39
      Authors' Addresses........................................47 Addresses........................................39
      Expiration and File Name..................................48 Name..................................40

1. Overview of Contents

   This document contains the following sections:

   Section 1: this overview.

   Section 2: Definition a glossary of terms.

   Section 3: Primitives. the definition of structure primitives used throughout the
   rest of the document.

   Section 4: Authorization certificate. the definition of an authorization certificate and its
   component parts.

   Section 5: Name the definition of a name certificate and the few parts
   that differ from an authorization certificate.

   Section 6: On-line the definition of an ACL and a (sequence...) structure.

   Section 7: the definition of on-line test reply formats.

   Section 7: Reduction rules.  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. the rules of 5-tuple reduction

   Section 9: Other certificate forms. the full BNF.

   The References section lists all documents referred to in the text as
   well as readings which might be of interest to anyone reading on this
   topic.

   The Acknowledgements section.

   The Authors' Addresses section gives the addresses, telephone numbers
   and e-mail addresses of the authors.

2. Definitions

   If the reader is familiar with older forms of certificate and
   encountering SPKI for the first time, it is important to bear Glossary

   We use some terms in mind
   that older certificates had as their purpose the binding body of a public
   key this document in cyberspace ways specific to
   SPKI:

   5-TUPLE: The 5 security-relevant fields from a person in 3D space via his certificate or her name in ACL
   entry, sometimes abbreviated <I,S,D,A,V>.  [See "certificate",
   below.]

   ACL: Access Control List -- a list of entries binding some
   global namespace.  Those older certificate descriptions kept the
   reader firmly planted in 3D space.  All operations referred back attribute
   to
   entity names.

   By contrast, SPKI an identified entity.  For our purposes, an ACL entry is like a child
   certificate, except that it is "issued" by "self" and need not be
   signed.  It yields a 5-tuple 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 form <self,S,D,A,V>.

   CERTIFICATE: a namespace related digitally signed record binding one or more attributes
   to 3D space.  Finally, SPKI rejects the notion of a global namespace,
   having determined that names in such identifier or to a space name that can not be meaningful resolved to
   users.  Instead, when SPKI uses names, they are defined in a local
   namespace, meaningful by definition global
   identifier.  The certificate is assumed to the creator of that namespace
   and not necessarily of significance have up 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 5 kinds of the secure hash
   field with security value:  Issuer, Subject, Delegation permission,
   Authorization, Validity dates and/or tests.

   CANONICAL S-EXPRESSION: an encoding of a signature key as a principal, in an effort to save space in data structures which use principals.

   Note S-expression that the secure hash of a public key removes
   options and is a global name for that
   key and, by implication, for the associated private key and, by
   another level of induction, designed for easy parsing.

   KEYHOLDER: the holder of that private key.

2.2 Keyholder

   By KEYHOLDER, we mean an person or other entity in the 3D world which that owns and 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 said 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 be the name keyholder 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 corresponding public
   key.

   GLOBAL IDENTIFIER: a group name globally unique byte string, associated 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
   keyholder.  In 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 either the verifier's public key to the target (name,key)
   PGP certificate.  Any single chain can be expressed simply as itself or a SDSI
   name sequence, but the fault tolerance and special trust model
   collision-free hash 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

   NAME: a small company common
   names can not be used as identifiers because they are likely to be
   ambiguous and persons identified by SDSI name are not likely to mean
   anything always relative 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 definer of this general certificate
   in this document: a name certificate (binding a some name in the issuer's
   namespace to a principal or group of principals) and an authorization
   certificate (binding an authorization (permission) space.
   This is sometimes also referred to as a principal or
   group of principals). local name.  A prior version of this spec did not separate
   those two forms, but in global name
   includes the interest of clarity of explanation and
   implementation, we have separated them here.

   The parts global identifier 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 definer of principals to which the
   certificate grants its name or authorization.

   DELEGATION is a boolean, indicating space.  For
   example, if TRUE that the Subject is
   allowed to delegate the specified Authorization further.

   AUTHORIZATION
     (name jim)
   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 local name,
     (name (hash md5 |+gbUgUltGysNgewRwu/3hQ==|) jim)
   could 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 corresponding global name.

   ON-LINE TEST: one trusted source of all authorizations.  Even if there were, three forms of validity test: (1) CRL; (2)
   revalidation; or (3) one-time revalidation.  Each refines the
   trust engine would need date
   range during which 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 given 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 considered
   valid.

   PRINCIPAL: a single principal, Delegation is of no use (at
   the end of the computation), Authorization is the quantity most signature key, capable of
   interest and Validity needs to include the present datime.

   This final 5-tuple makes generating a digital
   signature.

   PROVER: the statement "I (self) have determined entity that
   Subject is authorized to do (Authorization) at this time".

2.7 S-Expression

   In this draft, the standard format adopted is wishes access or that developed by SDSI,
   modified slightly.  Data objects are defined as S-expressions --
   lists in which the first element is digitally signs a token defining the data object.
   Rather than permit the full generality of S-expressions, we define
   document.

   SPEAKING: a
   canonical format and accept only that form.  Software Principal is available said to
   translate between the canonical format and "speak" by means of a presentation format.

   This document presents digital
   signature.  The statement made is the canonical format, but uses signed object (typically a presentation
   format
   certificate, for examples since SPKI purposes).

   S-EXPRESSION: the canonical data format chosen for SPKI/SDSI.  This is binary and can not
   easily be transmitted in a text document.

2.8 Prover

   By PROVER, we mean LISP-
   like parenthesized expression with the entity which wishes access or digitally signs
   a document.  We assume limitations that the prover assembles all certificates
   necessary for use by the verifier, empty lists
   are not allowed and puts those into order for the
   verifier.  The prover is software but could first element in any S-expression must be interacting with a
   human user.

2.9 Verifier

   By VERIFIER, we mean an entity which processes certificates, together
   with its own ACL entries, to determine if
   string, called the prover deserves access
   or if some signed document is valid.  The verifier is most likely
   unattended software.

2.10  Validity conditions

   SPKI certificates may use one or both of two kinds "type" of validity
   period: a date range (akin to expiration dates) or an on-line check.
   The on-line check will return information about the certificate's
   validity and that information itself will have an expiration date and
   time.  The certificate together with its latest on-line test result
   would then yield a valid assignment of authorization, with expression.

   VALIDITY CONDITIONS: a validity
   period which is the intersection of the date ranges of the two data
   items (usually equalling the date range of that must include the on-line test result).

   There are three forms of on-line test result defined:

   CRL
        a list of certificates known to have been revoked.

   Periodic revalidation current time
   and/or a reassurance set of validity for one specific certificate.

   One-time revalidation
        a statement on-line tests that for this one transaction, the indicated must succeed before a certificate
   or ACL entry is to be considered valid.  [Instead of having a validity date range
        of its own, a one-time revalidation server receives a random
        nonce from

   VERIFIER: the verifier and returns the validity result together
        with entity that nonce, digitally signed. processes requests from a prover, including
   certificates.  The resulting validity
        period is formally that of the one trust computation verifier uses its own ACL entries and no
        more.  This is as close as we can come to a 0-length validity
        period revalidation.  It has certificates
   provided by the benefit of not requiring clock
        synchronization.]  A one-time revalidation can also have side
        effects -- e.g., refer prover to perform "5-tuple reduction", to arrive at a bank balance.
   5-tuple it believes about the prover: <self,prover,D,A,V>.

3. Primitives

   We have chosen a simplified form of S-expression (the canonical form)
   as the format for SPKI objects.  An S-expression is a list enclosed
   in matching "(" and ")".  We assume the S-expression technology of
   [SEXP] with the restrictions that no empty lists are allowed and that
   each list must have a byte-string byte string as its first element.  That first
   element is the "type" or "name" of the object represented by the
   list.

   SPKI objects are defined below in a familiar extension of BNF -- with
   "|" meaning logical OR, "*" meaning closure (0 or more occurrences),
   "?" meaning optional (0 or 1 occurrence) and "+" meaning non-empty
   closure (1 or more occurrences).  A quoted string represents those
   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

   We define a canonical S-expression as containing binary byte strings strings,
   each with a given length length, and punctuation "()[]" for forming lists.
   The length of a byte string is a non-negative ASCII decimal number,
   with no unnecessary leading "0" digits, terminated by ":".  We
   further require that there be no empty lists and that the first list
   element be a byte string (as defined below).  This form is a unique
   representation of an S-expression and is used as the input to all
   hash and signature functions.  If canonical S-expressions need to be
   transmitted over a 7-bit channel, there is a form defined for base64
   encoding them.

3.2 <byte-string>

   A byte string is a binary sequence of bytes (octets), optionally
   modified by a display type.

   If the byte-string is used as a binary integer, these bytes are
   twos-complement, twos-
   complement, in network standard order (most significant byte first).
   It is up to the application whether these are considered signed or
   unsigned.

   All byte strings carry explicit lengths and are therefore not 0-
   terminated
   0-terminated as in the C language.  They are treated as binary even
   when they are ASCII, and can use any character set encoding desired.
   Typically, such a choice of character set would be indicated by a
   display type.

   A display type is assumed to be a MIME type giving optional
   instructions to any program wishing to display or use the byte
   string.  For example, it might indicate that the string is in
   UNICODE, is a GIF or JPEG image, is an audio segment, etc.  Although
   the display type of a byte string is optional, it is considered part
   of the string for any equality comparisons or hashing.  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:

   <byte-string>:: <bytes> | <display-type> <bytes> ;
   <bytes>:: <decimal> ":" {binary byte string of that length} ;
   <decimal>:: <nzddigit> <ddigit>* | "0" ;
   <nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
   <ddigit>:: "0" | <nzddigit> ;
   <display-type>:: "[" <bytes> "]" ;

3.3 S-expression

   An S-expression is of the form:

   <s-expr>:: "(" <byte-string> <s-part>* ")" ;

   <s-part>:: <byte-string> | <s-expr> ;

   where the first byte string in the S-expression is referred to here
   as its "type".

3.4 Encoding examples

     (4:test26:abcdefghijklmnopqrstuvwxyz5:123455::: ::)

   is a canonical S-expression consisting of four byte strings: "test",
   "abcdefghijklmnopqrstuvwxyz", "12345" and ":: ::".

   The advanced text form is:

     (test abcdefghijklmnopqrstuvwxyz "12345" ":: ::")

   showing that the advanced form follows familiar token recognition
   rules, not permitting tokens to start with digits, terminating them
   with white space or punctuation marks.

   For transmission of true 8-bit forms, we permit base64 encodings
   according to [RFC2045], with the base64 characters enclosed in
   braces.  The example above encodes to:

   {KDQ6dGVzdDI2OmFiY2RlZmdoaWprbG1ub3BxcnN0dXZ3eHl6NToxMjM0NTU
   6OjogOjop}

3.5 Use of canonical S-expressions

   Canonical S-expressions were designed to be as simple to pack and
   parse as possible.  Some concessions were made to those developers
   who might want to examine a canonical S-expression in an ASCII editor
   like emacs (specifically the readable decimal length fields and
   readable "()[]" characters) but in general the form is as close to
   minimum size as possible.  Parsing of a canonical form S-expression
   requires minimal look-ahead and no re-scanning of incoming bytes.  As
   a result, the parsing code remains very small.  Assuming each byte
   string is stored with a length field, generation of a canonical form
   from a data structure requires an extremely small amount of code.

   The canonical S-expression is the form which is hashed for both
   generating and verifying signatures.  These two processes can be
   thought of as the start and end of an SPKI object's useful life and
   both require canonical form.  Therefore, it is recommended that the
   canonical form be the form transmitted and stored in normal use, to
   be converted temporarily to and from a more readable form by display
   or editing applications written for the purpose.

   [Violating that suggestion, this document includes some advanced
   (non-canonical) forms,
   forms for readability.  Since this document is required to be
   straight ASCII, no pure 8-bit canonical forms will be presented
   except under base64 encoding.]

3.6 Non-canonical (advanced) Advanced S-expressions

   [SEXP] includes a general purpose utility program for converting
   between canonical and advanced S-expression form.  In the advanced
   form, individual byte strings may be expressed without length fields
   (if they are what most languages consider text tokens), may be
   written as quoted strings (under normal C string rules), or may be
   individually hex or base64 encoded.  Also in the advanced form, extra white
   space between list elements is allowed for readability and ignored on
   conversion to canonical form.

   For examples examples, this document will normally use the advanced form, form
   because of its readability, but for at least one concrete example the
   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
   fields, quoted strings, hex values (delimited by "#") and base64
   values (delimited by "|").  Those are features of the advanced
   transport form of an S-expression, and are not part of the canonical
   form.  We will always present the canonical form (base-64 encoded,
   when it contains non-ASCII characters) which the reader can decode to
   get the actual canonical form.

3.7 Unique IDs

   Top level object names are defined in this document along with
   certain algorithm names.  <tag> objects are user-defined, using a
   language for describing sets of permissions given here, and in the
   process, the defining user can choose any object names he or she
   wishes.

   For the definition of new algorithm names, it is our preference that
   this be taken on by IANA [RFC1780] for single-word standard names.
   In the interest of maximum flexibility we also permit users to define
   their own algorithm names via a normal URI's URIs (which presumably point
   to descriptions of the algorithms or even to code).

3.8 SPKI/SDSI 2.0 Primitive Objects

   The objects defined in SPKI/SDSI 2.0 are S-expressions.  That is they
   are lists of either byte strings or other lists.  In our case, all
   S-expressions S-
   expressions start with a <byte-string>, called the object name.  The
   remaining elements of the list are called "parts" of the object.

   In a communication from prover to verifier, one might encounter only
   a small number of different objects: usually a <sequence> of <cert>,
   <pub-key>, <sec-key>, <signature> and <op>.  The verifier will also need to
   refer to its own <acl>.  These are considered top level objects and
   are defined in the sections immediately following

   It is standard SPKI/SDSI practice to use names starting with a lower
   case letter, followed by lower case letters, digits and hyphens for
   object types.  SPKI/SDSI is case-sensitive, so the byte-string "RSA"
   is not the same as "rsa".  Non-standard object types (i.e. <tag>s
   defined by an application developer) are unconstrained, may have
   display types and may even be URI's URIs pointing to documentation of the
   object type.

   The structure and interpretation of the parts is up to the designer
   of the top-level object type.  However, for the sake of
   simplification, we have decided that all objects are "positional".
   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
   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
   verifying program may encounter.  Note that the main object, cert, <cert>,
   is sub-type based so the parameter fields may be in any order, but
   the BNF suggests a fixed order.  We use the BNF definition to
   indicate that there may not be more than one of each of the listed
   fields, and also to suggest (for readability) that the cert certificate
   parts be presented in the order given.  This document will use that
   order.

3.8.1 <pub-key>

   <pub-key>:: "(" "public-key" "(" <pub-sig-alg-id> <s-expr>* <uri>* ")"
   <uris> ")" ;

   A public key definition gives everything the user needs to employ the
   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
   signature verification.  That is because we need only signature keys
   for certificate formation and access control.  Other key types are
   open to being defined by users.

   The following is an RSA signature key, shown in advanced transport
   format:

   (public-key rsa-pkcs1-md5
    (rsa-pkcs1-md5
     (e #03#)
     (n
      |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO
      YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY
      VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| )) )))

   For actual use, the key is held and presented in canonical form the
   base64 encoding of which is:

   {KDEwOnB1YmxpYy1rZXkxMzpyc2EtcGtjczEtbWQ1KDE6ZTE6AykoMTpuMTI
   5OgDRwhvOY1xRponK9zBj4+dxWGEmNWlgLnujyp6RRKx4SjCWuB6yuFkikzm
   E05WqUc55xCw9g+5Vnd0PDw9JcotTSaTczJMUFR66wJyEKHM3jmbos/8mFQ8
   ydQ3YiJoscm/ycpntw9FIlF4XelRgM9MdHIKynnyp5o8uNdCq6N7ltSkp}

   {KDEwOnB1YmxpYy1rZXkoMTM6cnNhLXBrY3MxLW1kNSgxOmUxOgMpKDE6bjE
   yOToA0cIbzmNcUaaJyvcwY+PncVhhJjVpYC57o8qekUSseEowlrgesrhZIpM
   5hNOVqlHOecQsPYPuVZ3dDw8PSXKLU0mk3MyTFBUeusCchChzN45m6LP/JhU
   PMnUN2IiaLHJv8nKZ7cPRSJReF3pUYDPTHRyCsp58qeaPLjXQquje5bUpKSk=}

   Although not strictly needed by this draft, the private key for the
   public key above is:

   (private-key rsa-pkcs1-md5
    (rsa-pkcs1-md5
     (e #03#)
     (n
   |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKTO
   YTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/yY
   VDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3uW1| )
      |ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSKT
      OYTTlapRznnELD2D7lWd3Q8PD0lyi1NJpNzMkxQVHrrAnIQoczeOZuiz/
      yYVDzJ1DdiImixyb/Jyme3D0UiUXhd6VGAz0x0cgrKefKnmjy410Kro3u
      W1|)
     (d
   |AIvWvTRCPYvEW9ykyu1CmkuQQMQjm5V0Um0xvwuDHaWGyw8lacx65hcM0
   QM3uRw2iaaCyCkCnuO+k19fX4ZMXOD7cLN/Qrql8Efx5mczcoGN+Eo6FF+
   cvgXfupe1VM6PmJdFIauJerTHUOlPrI12N+NnAL7CvU6X1nhOnf/Z77iz| )
      |AIvWvTRCPYvEW9ykyu1CmkuQQMQjm5V0Um0xvwuDHaWGyw8lacx65hcM
      0QM3uRw2iaaCyCkCnuO+k19fX4ZMXOD7cLN/Qrql8Efx5mczcoGN+Eo6F
      F+cvgXfupe1VM6PmJdFIauJerTHUOlPrI12N+NnAL7CvU6X1nhOnf/Z77
      iz|)
     (p
   |APesjZ8gK4RGV5Qs1eCRAVp7mVblgf13R5fwApw6bTVWzunIwk/2sShyy
   tpc90edr+0DPwldnvEXTUY1df0DwPc=|)
      |APesjZ8gK4RGV5Qs1eCRAVp7mVblgf13R5fwApw6bTVWzunIwk/2sShy
      ytpc90edr+0DPwldnvEXTUY1df0DwPc=|)
     (q
   |ANjPQe6O0Jfv90GWE3q2c9724AX7FKx64g2F8lxgiWW0QKEeqiWiiEDx7
   qh0lLrhmBT+VXEDFRG2LHmuNSTzj7M=|)
      |ANjPQe6O0Jfv90GWE3q2c9724AX7FKx64g2F8lxgiWW0QKEeqiWiiEDx
      7qh0lLrhmBT+VXEDFRG2LHmuNSTzj7M=|)
     (a
   |AKUds79qx62EOmLIjpW2AOb9EOSZAVOk2mVKrGgm83jkifEwgYqkdhr3M
   ebopNppH/NXf1uTv0tk3i7OTqitK08=|)
      |AKUds79qx62EOmLIjpW2AOb9EOSZAVOk2mVKrGgm83jkifEwgYqkdhr3
      MebopNppH/NXf1uTv0tk3i7OTqitK08=|)
     (b
   |AJCKK/RfNbqf+iu5YlHO9+n56q6nYx2nQV5ZTD2VsO54KxYUcW5sWtX2n
   xr4YydBEA3+46CsuLZ5cvvJeMNNCnc=|)
      |AJCKK/RfNbqf+iu5YlHO9+n56q6nYx2nQV5ZTD2VsO54KxYUcW5sWtX2
      nxr4YydBEA3+46CsuLZ5cvvJeMNNCnc=|)
     (c
   |CIPwAAO8Vmj0/BfCtsg+35+r94jwxGYHZ63RsqyNxbvkAO6xPqSht8/vz
   dR93eX5B9ZKBQg1HHWCsHbqQtmNLQ==|))
      |CIPwAAO8Vmj0/BfCtsg+35+r94jwxGYHZ63RsqyNxbvkAO6xPqSht8/v
      zdR93eX5B9ZKBQg1HHWCsHbqQtmNLQ==|)))

   or

   {KDExOnByaXZhdGUta2V5KDEzOnJzYS1wa2NzMS1tZDUoMTplMToDKSgxOm4
   xMjk6ANHCG85jXFGmicr3MGPj53FYYSY1aWAue6PKnpFErHhKMJa4HrK4WSK
   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==}

   where a, b and c are CRT parameters.

3.8.2 <sec-key>

   <sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>* ")" ;

3.8.2.1 HMAC-MD5

   Example:

   (secret-key hmac-md5 (k |ksTt2Lu9NSq3mGHJ7HmuksSYwFQ=|) )

   which has a base64 encoded canonical form:

   {KDEwOnNlY3JldC1rZXk4OmhtYWMtbWQ1KDE6azIwOpLE7di7vTUqt5hhyex
   5rpLEmMBUKSk=}

   The hmac-md5 and hmac-sha1 algorithms are defined in [RFC2104].

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>? <uris> ")" ;

   A <hash> object gives the hash of some other object.  For example,
   the public key given above has the following hash: hashes:

   (hash md5 #92e5f2ab1f23616759fe3ed57dfafeca#)

   or #9710f155723bc5f4e0422ea53ff7c495#)
   {KDQ6aGFzaDM6bWQ1MTY6lxDxVXI7xfTgQi6lP/fElSk=}

   (hash md5 |kuXyqx8jYWdZ/j7Vffr+yg==|)

   which, in base64 encoded canonical form, is

   {KDQ6aGFzaDM6bWQ1MTY6kuXyqx8jYWdZ/j7Vffr+yik=}

   A hash of the hmac-md5 secret key defined above is:

   (hash md5 #33b7035665f7af8c6669bdabc58ab236#) or (hash md5
   |M7cDVmX3r4xmab2rxYqyNg==|)

   which, in base64 encoded canonical form, is

   {KDQ6aGFzaDM6bWQ1MTY6M7cDVmX3r4xmab2rxYqyNik=}

   This is perhaps of more interest than the hash of the public key
   because a certificate generally released to the public can not
   contain a secret key, for obvious reasons, but it might contain the
   hash of the secret key without fear of loss of the secret.

3.8.4 sha1 #1a6f6d62 1abd4476 f16d0800 fe4c32d0 6ff62e93#)
   {KDQ6aGFzaDQ6c2hhMTIwOhpvbWIavUR28W0IAP5MMtBv9i6TKQ==}

3.8.3 <signature>

   <signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ;

   A signature object is typically used for a certificate body and
   typically follows that <cert> object in a <sequence>.  We chose not
   to define an object <signed-cert> containing the cert body and
   signature, since there may be cases when the same cert body needs to
   be signed by multiple keys.  One can also
   sign objects other than cert certificate 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,

3.8.3.1 <sig-val>

   <sig-val> depends on the subject is given <pub-sig-alg-id> -- the
   permission specified algorithm listed in <tag>, without permission to delegate it,
   with no expiration date or condition (until
   the ACL public key.

   For rsa-pkcs1-md5 and rsa-pkcs1-sha1, <sig-val> is edited to
   remove a <byte-string> --
   the permission). value of the RSA signature operation.

   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> ;

   <hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ;

   <general-op>:: "(" "do" <byte-string> <s-part>* ")" ;

   A <sequence> dsa-sha1, <sig-val> is a bundled sequence <byte-string>, consisting of objects which the verifier is
   to consider when deciding to grant access.  We anticipate requiring
   concatenation of the prover (who constructs values r and submits the <sequence>) to provide
   elements in order, so that the verifier need only process the
   <sequence> in order to prove to itself s (in that order) from the prover has the
   claimed access right.

   The sequence can also contain instructions to the verifier, in the
   form DSA.
   Each is of opcodes.  At present the only opcode defined is "hash" --
   meaning, that length of the previous item sub-prime, q.  We could split these
   values out in the sequence (the last an S-expression, but at least one read
   in) is to be hashed by popular cryptographic
   package (BSAFE) assumes 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 two values are concatenated so that a (signature ) block following a cert
   body in a sequence will call
   splitting and recombining would be extra work for the programmer.

   For rsa-pkcs1 (should that cert body to option be hashed preferred by the working group
   over the specification of hash algorithm indicated in the signature.

   If an object will be referenced <pub-sig-alg-id>),
   <sig-val> would need to be:

   <sig-val>:: "(" "rsa-pkcs1-sig" <hash-alg-name> <byte-string> ")" ;

   Custom algorithms, specified by different hashes, it can URI, might need custom <sig-val>
   definitions.  The <sig-val> structure for a custom <pub-sig-alg-id>
   should be
   followed specified at the given URI even if it is one used by multiple (do hash ..) opcodes. other
   algorithms.

4. Authorization Certificate

   <cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>?
   <subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ;

   The basic certificate form is an authorization certificate.  It
   transfers some specific authorization or permission from one
   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
   creating them, the form we call ACL-entry is also defined below to
   inject authorizations into a chain of certificates.  An ACL entry
   lives on the machine of the verifier, leading to the observation that
   all authorization flow is in loops a circuit -- from the verifying machine,
   machine's ACL, possibly through certificates and then back to the
   verifying machine.  Alternatively, one might say that the only root
   of an authorization certificate chain is the verifier.

4.1 <version>

   <version>:: "(" "version" <byte-string> ")" ;

   Version numbers are alphanumeric strings.  If the <version> field is
   missing from an object, it is assumed to be (version V0), "0"), which is
   the version of all objects in this draft.  Elaboration of version
   numbers, possibly with multiple fields, are left for later to define.

   It is assumed that a verifier, when encountering a structure it
   doesn't know how to parse (because it has a

   A certificate containing an unrecognized version number it doesn't
   recognize), will ignore that object. must be
   ignored.

4.2 <cert-display>

   <cert-display>:: "(" "display" <byte-string> ")" ;

   This optional field gives a display hint for the entire certificate.
   This display parameter does not affect certificate chain reduction,
   but is provided to aid user-interface software in certificate
   display.

   At this time, we have no such hints defined.  This field is up to
   developers to define as they see fit.  For verifiers of certificates,
   this field is treated as a comment.

4.3 <issuer>

   <issuer>:: "(" "issuer" <principal> ")" ;

   <principal>:: <pub-key> | <hash-of-key> ;

   This rules out <sec-key> issuers, since an explicit <sec-key> as an
   issuer offers no security to the cert.  However, one may have a

   <hash-of-key> field that is the hash of a <sec-key> as might be the issuer, preferred <principal>, not merely for a cert where the only verifiers are size
   but also in possession of the secret
   key. case one is using small RSA keys and protecting them from
   cryptanalysis by keeping them secret.

4.4 <issuer-loc>

   <issuer-loc>:: "(" "issuer-info" <uri>* <uris> ")" ;

   The (issuer-info ) object provides the location of the cert(s) certificate(s)
   by which the issuer derives the authority to pass along the
   authorization in the present <cert>.  We expect the prover (the
   calling client) to track down such other certs certificates and provide
   them to the verifier (the called server), but we allow this
   information in the cert certificate to simplify that process for the
   prover.

4.5 <subject>

   <subject>:: "(" "subject" <subj-obj> ")" ;

   <subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> | <keyholder> | <subj-thresh> <subj-
   thresh> ;

   In the most basic form, a

   <subj-obj>:: <principal> ;

   and one may make an SPKI implementation with only that definition, in
   case names are considered unnecessary for the intended application.

   However in full-blown implementations, the 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 principal, the hash of an object or a reference to some keyholder
   (that is, some person object, 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 <keyholder> case is translated into a
   fully-qualified name by using the key
   special and of the issuer.

   Unlike the <issuer> SDSI name, which is forced little interest to be a name in the
   issuer's name space, the subject name can be in any name space.

   (subject (name (hash md5 |Txoz1GxK/uBvJbx3prIhEw==|) fred sam george
   mary))

   refers through "fred" defined verifier code, since it is used in the name space of
   |Txoz1GxK/uBvJbx3prIhEw==|, to reduce to:

   (subject (name (hash md5 |Z5pxCD64YwgS1IY4Rh61oA==|) sam george
   mary))

   recursing until the subject reduces to
   a key.  This construct allows
   deferred binding of keys to names, while the bare-bones SPKI format
   forces binding of keys to names at the time the certificate that 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 message to be reissued.  For that matter, a human.

   See section 5 for the cert above can be
   issued before there is any definition of the referenced name.

4.5.2 <name>.

4.5.1 <obj-hash>

   <obj-hash>:: "(" "object-hash" <hash> ")" ;

   This option for a (subject ) refers to an object other than a
   <principal> (or SDSI name reducing to a principal).
   <principal>.  One might use this form to assign attributes to an
   object (a file, a web page, an 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

4.5.2 <keyholder>

   <keyholder>:: "(" "keyholder" <keyholder-obj> ")" ;
   <keyholder-obj>:: <principal> | <name> ;

   This form of subject refers to the flesh and blood (or iron and
   silicon) holder of the referenced key.  A <cert> with such a subject
   is saying something about that person or machine -- such as its
   location, its address, its age, its weight, its height, its picture,
   ....

4.5.5  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.3 <subj-thresh>

   <subj-thresh>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ;

   where the first int is K and the second is N, K < N, and there are N <subj-obj> subjects listed.

   A threshold subject, introduced by Tatu Ylonen for SPKI and by Rivest
   and Lampson in SDSI 1.0, specifies N subjects for a certificate or
   ACL entry, of which K must agree before the permission is passed
   along.

   The actual intent is to insure that there are K distinct paths
   passing permission between the verifier's ACL and the prover's
   request.  These multiple paths branch fork and re-join, join, so the k-of-n construct
   could theoretically be part of either the Subject or the Issuer.
   Since an ACL might want to specify these multiple paths (and an ACL
   has no Issuer) and since a cert certificate is signed by a single Issuer,
   we have chosen to specify the branching at the Subject.

   A certificate or ACL with a k-of-n Subject does not delegate
   permission to any of those subjects, alone.  Rather, each of these
   subjects receives a share of the delegated permission.  Only if at
   least K of the N subjects show certificate paths which converge on a
   single target Subject during reduction, is that permission
   transmitted to the target.  If fewer than K such paths can be shown,
   then the permission is not delegated.

   This construct is far from simple.  However, it is extremely useful.
   It has been demanded by a number of initial customers of SPKI
   certificates.  It also solves a number of sticky political problems.
   This section lays out the specification of K-of-N subjects.  The
   rules for reducing 5-tuples containing such entries are given later.

   Examples of the use of K-of-N permission propagation include:

   1.  co-signing of electronic corporate checks or purchase orders
       above a certain amount

   2.  establishing the root DNSSEC key, bypassing the political battles
       which would inevitably ensue if one country were to hold *the*
       root key for the entire world.  The same goes for any root key.

   3.  establishing a root key for a trusted service, via multiple
       algorithms.  That is, one could have three root keys, using RSA,
       DSA and Elliptic Curve signature algorithms (for example), and
       require that two of them yield a valid chain.  This way, if
       someone were to break an entire algorithm (find a way to invert
       the algorithm), much less if someone were to break one key in the
       set of three, the root remains securely established.  At the same
       time, there is fault tolerance.  In case one of the keys is
       revoked, the following certificates remain empowered.

   4.  using online and off-line issuers.  One could have a permission
       established by an off-line key issuing a long-lived certificate
       and echoed by an online automated server, issuing short-lived
       certificates.  The delegation of this permission could require
       both before the eventual subject gets the permission.  This can
       be achieved through the use of (online ) tests in a long-lived
       certificate, but the K-of-N subject mechanism may be cleaner.

   5.  ultra-secure applications.  There are many applications which
       follow the nuclear weapons launch scenario.  That is, multiple
       agreement is required before the permission is granted.

4.6 <subject-loc>

   <subject-loc>:: "(" "subject-info" <uri>* <uris> ")" ;

   This optional field provides the location of information about the
   subject.  For example, if the subject is a hash of a key, this might
   provide the location of the key being hashed.  IF  If the subject is a
   SDSI name, it might give the location of a SDSI name cert certificate
   server.

4.7 <deleg>

   <deleg>:: "(" "propagate" ")" ;

   This optional field, if present, notes that the <subject> has not
   only the permission given in the <cert>'s <tag> field but also the
   permission to delegate that (or some portion of it) to others.

4.8 <tag>

   <tag>:: "(" "tag" "(*)" ")" | "(" "tag" <tag-expr>  ")" ;

   The form (tag (*)) "(tag (*))" means "all permissions".

   The simplest tag is an S-expression with no *-forms.  This is a
   specific permission which must be passed along and used intact.

   A tag with *-forms represents a set of specific permissions.  Any
   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
   certificates, one intersects the adjacent tag sets to find a
   resulting tag set.  Full tag intersection rules are given later.

   All tags are assumed to be positional.  That is, parameters in a tag
   have a meaning defined by their position.

   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
   granted.  [If the field added makes the tag invalid, then one has
   restricted the original permission to zero.]

   The

   See the full BNF section for the full tag body BNF is:

   <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> ")" ; BNF, including
   specification of *-forms.

4.9 <valid>

   The <valid> field gives validity dates and/or on-line test
   information for the cert. certificate.

   <valid>:: <not-before>? <not-after>? <online-test>? <online-test>* ;

   <not-after>:: "(" "not-after" <date> ")" ;
   <not-before>:: "(" "not-before" <date> ")" ;

   The not-after and not-before options are self-explanatory.  If either
   is missing, then the cert certificate is assumed valid for all time in
   that direction.  For example, one might omit the <not-before> field,
   if that date would be before or at the time of creation of the cert,
   certificate, unless one wanted to note the creation time for documentary
   documentation purposes.

4.9.1 <date>

   <date>:: <byte-string> ;

   A date field is an ASCII byte string of the form:

   YYYY-MM-DD_HH:MM:SS

   always UTC.  For internal use, it is treated as a normal byte string.
   For example, "1997-07-26_23:15:10" is a valid date.  So is "2001-01-
   01_00:00:00".
   "2001-01-01_00:00:00".  <date> fields are compared as normal ASCII
   byte strings since one never needs to compute the size of a time
   interval to test validity -- only determine greater-than, less-than
   or equal.

4.9.2 <online-test>

   <online-test>:: "(" "online" <online-type> <uri> <uris> <principal> <s-
   part>* ")" ;

   <online-type>:: "crl" | "reval" | "one-time" ;

   The online test option allows a cert certificate to be backed up by finer
   grain validity testing.  The reply from an online test is a digitally
   signed object, validated by the <principal> given in the test
   specification.  That object includes validity dates, so that once one
   has the online test response, its validity dates can be intersected
   with the parent cert's certificate's validity dates to yield the current
   working validity dates for the cert. certificate.

   The crl form tells the verifier (or prover, who fetches this
   information for the verifier, in our standard model), the current
   list of invalid certs. certificates.  If the present cert certificate is not on
   that list, then the cert certificate is presumed valid.

   The revalidate re-validate form is the logical opposite of the crl.  It tells
   the verifier a list of valid certs -- certificates or, more likely, just that
   the current cert certificate is valid.

   The one-time form is a revalidate re-validate form without validity dates.  It
   must be fetched by the verifier, rather than the prover, since it is
   valid only for the current verification step.  [In effect, it has a
   validity period of just "now".]  The process of getting this one-time
   revalidation involves sending a unique (and partly random) challenge
   which is returned as part of the signed response.

   If there are multiple URIs specified, any one of them can be used.

   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 6 7 for a full description of on-line test request and reply formats.

4.10 <comment>

   <comment>::  "(" "comment" <byte-string> ")" ;

   This optional field allows the issuer to attach comments meant to be
   ignored by any processing code but presumably to be read by a human.

5. Name certificate

   Names are defined for human convenience.  For actual trust engine
   computations, names must be reduced to keys.  This section gives the
   form of a name, a name certificate and the rules for reducing name
   certificates to simple mappings from name to key.

   Note that we do not include an <issuer-loc> option for a name
   certificate.  The issuer needs no authorization in order to create
   names.  Every issuer has that right.

   Similarly, there is no "certification practice statement" for these
   name certificates.  Nothing is implied by a name certificate about
   the principal(s) being named.  There are no constraints on name
   choice.  A name can be an arbitrary byte string
   assigned by the
   issuer.  It issuer and is intended to be meaningful only to that
   issuer, although other parties may end up using it.  A name is not
   required or expected necessarily to conform to any name string in the 3D
   physical world or in any other issuer's name space.

   That said, it is possible to map name certificates generated by a
   commercial Certification Authority into SDSI names and thus refer to
   keys defined in under that world process from within SPKI/SDSI certificates.

5.1 Name cert certificate syntax

   A name certificate has the form:

   (cert
    (issuer (name <prin> <principal> <name>))
    (subject ...)
    <validity fields>
    <subject>
    <valid>
   )

   <name-cert>:: "(" "cert" <version>? <cert-display>? <issuer-name>
   <subject> <valid> <comment> <comment>? ")" ;

   <issuer-name>:: "(" "issuer" "(" "name" <principal> <byte-string> ")"
   ")" ;

   That form maps directly into the intermediate form needed for name
   string reduction.  The name must be under the <principal> of the
   certificate issuer, and under this syntax the certificate issuer
   <principal> is taken from the (name..) structure.

   In a name certificate, the (tag) field is omitted and (tag (*)) is
   assumed.

   It is not syntactically possible to have delegation or authorization
   fields in a name cert.  Delegation is always true, through a name
   chain, and authorization  There is always (*). also no <deleg> field.  A name definition is like
   an extension cord, passing everything the name is granted through to
   the subject.

   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
   different subjects, then that name is a group.  More specifically,
   all name certificates define groups, many of which will have only one
   member.  A multi-member group is like a multi-plug extension cord,
   passing everything the name is granted through to any and all of its
   subjects.

5.2 Name reduction

   A name by itself <name>

   The <name> form is of little value.  To be used, it must be reduced a option for <subject>, when one wants to generate
   a principal.  The rules certificate granting authorization to either a named group of reduction allow intermediate forms
   which grow
   principals or to a principal that has not been defined yet.  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>+ ;

   A relative name is defined only with respect to an issuer and should
   show up only in length, but a certificate, borrowing the value <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 single principal
   (or set of principals). name in the
   issuer's name space, the subject name can be in any name space.

5.3 Name reduction produces principals from
   names.

   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 process, however, it can produce longer only reduction rule needed.

   It is possible for someone to generate a trouble-making name strings.

   For example:

   <(K1 N1),(K2 N2 N3)> + <(K2 N2),K3> -> <(K1 N1),(K3 N3)>

   <(K1 N1),(K2 N2)> + <(K2 N2),(K3 N3)> -> <(K1 N1),(K3 N3)>

   <(K1 N1),(K2 N2 N4)> + <(K2 N2),(K3 N3 N5)> -> <(K1 N1),(K3 N3 N5
   N4)>

   where K# are
   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 and N# are
   could conspire to produce loops of name strings. definition.  Therefore, the name
   reduction code needs to do loop detection.

6. On-line test reply ACL and Sequence formats

   Given here

   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 BNF for on-line test replies.  This section does
   not give details fields of protocols for connecting the ACL are fields of a <cert>, we will
   not repeat those common field definitions here.  Since an ACL is
   not communicated to online servers 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
   transmitting messages between them.  It condition (until the ACL is assumed that, for example, edited to remove the requester can provide
   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/)))
   )

   {KDM6YWNsKDU6ZW50cnkoNDpuYW1lKDQ6aGFzaDM6bWQ1MTY6p1isZirSN3C
   BscfNQSbiDCkxODpzeXNhZG1pbi9vcGVyYXRvcnMpKDM6dGFnKDM6ZnRwMTE
   6ZGIuYWNtZS5jb200OnJvb3QpKSkoNTplbnRyeSg0Omhhc2gzOm1kNTE2OjO
   3A1Zl96+MZmm9q8WKsjYpKDM6dGFnKDM6ZnRwMTE6ZGIuYWNtZS5jb200OnJ
   vb3QpKSkoNTplbnRyeSg0Omhhc2gzOm1kNTE2OpLl8qsfI2FnWf4+1X36/so
   pKDk6cHJvcGFnYXRlKSgzOnRhZyg0Omh0dHA0MDpodHRwOi8vd3d3LmludGV
   ybmFsLmFjbWUuY29tL2FjY291bnRpbmcvKSkpKQ==}

6.2 <sequence>

   <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>* ")" ;

   A <sequence> is a URI bundled sequence of objects that the verifier is to
   consider when deciding to grant access.  We anticipate having the
   prover (who constructs and use HTTP, while submits the URI includes
   any parameters <sequence>) provide elements
   in order, so that the requester needs verifier need only process the <sequence> in
   order while proving to pass along. itself that the prover has the claimed access
   right, but that is a developer decision.

   The reply from sequence can also contain instructions to the
   on-line source will be verifier, in canonical form, according the
   form of opcodes.  At present the only opcode defined is "hash" --
   meaning, that the previous item in the sequence (the last one read
   in) is to be hashed by the BNF given
   below.  If a protocol algorithm and saved, indexed by that
   hash value.  Presumably, that item (certificate body or public key,
   for example) is used other than HTTP, referred to by hash in some subsequent object.

   At this time, we assume that <signature> does double duty, calling
   for the (online ...) hash of the preceding item.  However, it would not hurt to
   use an explicit <hash-op> prior to a <signature>.

   If an object includes optional <s-part> fields which will be referenced by different hashes, it can be used to hold
   parameters
   followed by multiple <hash-op>s.

   Additional <op>s might be defined for those tests some algorithms doing
   threshold-subject reduction (e.g., indicating which an <op> to push the current
   5-tuple on a stack).

7. On-line test reply formats

   An on-line test results in a digitally signed object carrying its own
   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
   interest, how to authenticate protocols for connecting to the server, etc.).

6.1
   online servers or transmitting messages between them.

7.1 CRL and delta-CRL

   The full or delta

   If one wants to provide CRLs, and that CRL is: grows, then one may prefer
   to send only a delta CRL.

   <crl>:: "(" "crl" <version> <version>? <hash-list> <valid-basic> ")" ;
   <hash-list>:: "(" "canceled" <hash>* ")" ;
   <delta-crl>:: "(" "delta-crl" <version> <version>? <hash-of-crl> <hash-list>
   <valid-basic> ")" ;
   <hash-of-crl>:: <hash> ;

   and

   The <hash-of-crl> should probably have a URI pointing to the location
   of the full CRL.

   The <crl> or <delta-crl> should be signed by the principal indicated
   in the (online...)  field which directed the CRL to be fetched.

   The CRL request can be a straight HTTP transaction, using the URI
   provided in the cert, certificate, but we do not specify online protocols
   in this draft.

   If the verifier has a complete CRL, then it

   The protocol for choosing between delta and full CRL is left open.
   One can always provide the hash of
   that CRL in whatever protocol is chosen delta and get back just the
   additions to let the previous CRL, in caller fetch the form of a <delta-crl>

6.2 full
   specifically, for example.

7.2 Revalidation

   <reval>:: "(" "reval" <version> <version>? <subj-hash> <valid-basic> ")" ;
   <subj-hash>:: "(" "cert" <hash> ")" ;

   This construct specifies the hash of the current cert certificate as
   <subj-hash> and gives a new validity period for that cert. certificate.  It
   should be signed by the <principal> indicated in the (online...)
   field which directed it to be fetched.

   The reval request can be a straight HTTP transaction, using the URI
   provided in the (online...) field, but we do not specify online
   protocols in this draft.

6.3

7.3 One-time revalidation

   For one-time revalidation, the verifier itself must fetch the (reval)
   record, which will have the form:

   <reval>:: "(" "reval" <version> <version>? <subj-hash> <one-valid> ")" ;

   <one-valid>:: "(" "one-time" <byte-string> ")" ;

   with

   where the byte string inside <one-valid> being is one provided by the
   caller, expected to be unique over time and unguessable -- e.g., a
   large random number or random number plus sequence number.  This
   reply should be signed by the <principal> indicated in the (online..)
   field which directed it to be fetched.

   This result, if successful, yields result corresponds to a Validity value for the 5-tuple 0-length validity interval of "now".

7. "now",
   however the developer wishes to express that.

8. 5-Tuple Reduction

   This section describes the operation of the trust evaluation
   machinery assumed to be part of every verifier which accepts SPKI
   certificates.  The inputs to that trust engine are 5-tuples and any
   kind of certificate, not just SPKI, as well as Access Control List
   (ACL) entries can be translated to 5-tuples so that they can all
   participate in the trust computation.

   A 5-tuple is an internal construct and therefore best described by a
   programming language data structure.  A separate document will give
   the 5-tuple reduction code and those data structures.

   For this purpose, we describe the content in BNF, but want to make
   sure that a 5-tuple will never be expressed

   Name reduction is specified in canonical BNF form,
   transmitted section 5.3.  Therefore, in what
   follows we assume all issuers and subjects are principals.  We also
   assume that form, etc.  The all principals are public keys.  It is an implementation
   decision whether to store these as explicit keys, hashes of keys
   (used as pointers) or addresses pointing to keys.

8.1 <5-tuple> differs from BNF

   How a <cert>
   by leaving out some fields of an authorization cert 5-tuple is represented and by including
   some absent fields for stored is up to the developer.  For
   the sake of discussion, we assume a name cert.

7.1 <5-tuple> BNF

   A 5-tuple is a positional construct of the
   form:

   <5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ;

   <issuer5>:: <key5> | <i-name5> | "self" ;

   <subject5>:: <key5> | <fq-name5> | <obj-hash> | <keyholder> | <threshold-subj> ;

   <deleg5>:: "t" | "f" ;

   <key5>:: <pub-key> | <sec-key> ;

   <i-name5>:: "(" "name" <key5> <name> ")" ;

   <fq-name5>:: "(" "name" <key5> <names> ")" ;

   <valid5>:: <valid-basic> | "null" | "now" ;

   <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 self referred to is the verifier, holding that ACL and doing the
   verification of offered proofs.

   The only 5-tuples that can mean anything to the verifier, after
   reduction is done, are those with "self" as issuer.

7.2 Bare-bones case

   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 *).

8.2 Top level reduction rule

   <i1,s1,d1,a1,v1> + <i2,s2,d2,a2,v2> yields <i1,s2,d2,a,v> if:
   s1 = i2
   d1 = "t"
   a = the intersection of a1 and a2
   v = the intersection of v1 and v2

   Validity intersection involves normal intersection of date ranges, if
   there are not-before or not-after fields in v1 or v2, and union of
   on-line tests, if those are present in v1 or v2.  Each on-line test
   includes a validity period, so there is a resulting validity interval
   in terms of dates.  This can include the string "now", as the product
   of a one-time on-line test result.  "now" intersects with any date
   range including the present to yield "now".  If v is an empty time
   interval, then the certificates don't reduce. either "now" or "null".

   The intersection of a1 and a2 in the basic case is given by below.  In the
   following rules: most basic
   case,

   If a1 is (tag (*)), a = a2.

   If a2 is (tag (*)), a = a1.

   If a1 == a2, a = a2.

   Otherwise, a = "null" and the 5-tuple doesn't reduce.

7.3

8.3 Intersection of *-form tag sets

   It is assumed

   Two <tag> S-expressions intersect by the following rules.  Note that normal verification
   in most cases, one of the two tag S-expressions will proceed from right be free of
   *-forms.  A developer is free to
   left -- implement general purpose code that is,
   does set-to-set reductions, for example, but that a specific desired result tag will is not likely to be
   intersected with a general tag.  Therefore,
   necessary.

    1. basic: if a1 == a2, then the only intersection
   rules needed are those between *-forms result is a1.

    2. basic: if a1 != a2 and *-free tag elements.  Such
   an intersection will yield either "null" or neither has a *-free tag.

   The intersection rules are intuitive and recurse down into tag S-
   expressions and along lists. *-form, then the result is
        "null".

    3. (tag (*)): if a1 == (tag (*)), then the result is a2.
        If a2 == (tag (*)), then the result is a1.

    4. (* set ...):
   a *-free <tag-expr> intersects with if some <tag> S-expression contains a (* set ...) to yield )
        construct, then one expands the *-free
   <tag-expr> if that expression is an element set and does the intersection of
        the set. resulting simpler S-expressions.

    5. (* range ...):
   a *-free <tag-expr> intersects with if some <tag> field compares a (* range ...) ) to yield the *-
   free <tag-expr> if the expression is a byte string contained within
        <byte-string>, one does the specified range.  Otherwise, range comparison and the intersection fails.
        resulting field is the explicit one tested.

    6. (* prefix ...):
   a *-free <tag-expr> intersects with if some <tag> field compares 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
        <byte-string>, then 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 result is assumed to be the same on both sides of explicit string if 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
        test string 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 prefix of names.  Algorithms to find certificate paths and
   avoid such loops have been developed by Ron Rivest it and his SPKI
   implementers, so we know that such are possible.

7.5 otherwise "null".

8.4 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"

   A separate document will give full algorithms for 5-tuples which never exceeds a depth reduction of 2 for
   other reductions, but needs to be a real stack for this one.

   (cert ... (k-of-n ...))

   arrives and K-of-N
   threshold subjects.  One general procedure is held on a separate stack.

   (do subject #01#)

   pulls a copy to make K copies of 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- containing the K-of-N subject 5-tuple.  It acquires a record noting and indicate which subject of those
   subjects is
   active, so being handled by that at eventual reduction time, the code can verify copy.  One then reduces 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
   as if it had a single subject.  At this point, another thread  One can
   be reduced to stop 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 separate reductions
   when all K cert
   threads to the right of the k-of-n cert are processed first.  This
   requires the opcode:

   (do push)

   to move the current (R-to-L) 5-tuple result to the top of the
   auxiliary stack.

   (do copy)

   copies the current 5-tuple from the top of the auxiliary stack to the
   top of the normal stack  and normal cert processing proceeds, up to
   the point where reduced values have the k-of-n cert would be required. same subject.  At this that
   point,
   another

   (do copy)

   fetches another copy of the right end of this thread (the merge
   point) and another cert thread is processed.

   When all K threads are processed, the k-of-n cert is presented, the
   auxiliary stack is popped, and the k-of-n cert combines with the K reduced 5-tuples on the stack below it, to yield become 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

   By 5-tuple reduction, some chains of authorization statements will be
   reduced to the form:

   (self,X,D,A,V)

   where "self" represents the entity doing the verification, granting
   access, etc.  Such a 5-tuple says "Self says (I say) that X has
   authority (D,A) 5-tuple.

   The actual algorithm choices for validity period (or conditions) V".  In other
   words, self has decided what it can trust about X.

   Any authorization chain not reducing to a 5-tuple with self as issuer
   isn't relevant to decisions by self.

   Therefore, any authorization chain which is to be used by self to do
   trust management must have self as a root.  Since self is doing this
   chain reduction depend on
   whether one wants to reduce left-to-right or right-to-left and is therefore at the receiving end of the chain as
   well, that makes all useful authorization chains loops.

7.7 how
   much storage a verifier has.

8.7 Certificate Result Certificates

   In cases where the verifier, Self, has access to a private key, once
   it has reduced a chain of certificate bodies down to the form:

   (Self,X,D,A,V)

   it can sign that generated body, using its private key, producing an
   SPKI certificate.  That certificate will have a validity period no
   larger that of any certificate in the loop which formed it, but
   during that validity period it can be used by the prover instead of
   the full chain, when speaking to that particular verifier.  It is
   good only at that verifier (or at another which trusts that verifier,
   Self, to delegate the authorization A).  Therefore, one option by the
   verifier is to sign and return the result 5-tuple to the caller for
   this later use.

   If it isn't important for any other verifier to accept this "result
   certificate", it can even be signed by a symmetric key (an HMAC with
   secret key private to the verifier). verifier), although such keys are not
   defined in this standard.

   The certificates which made up the loop forming this result 5-tuple
   could have been of any variety, including X.509v1, X.509v3, SET or
   DNSSEC.  They could also be PGP signed keys processed by an enriched
   trust engine (one capable of dealing with the PGP web of trust
   rules).  If the verifier, Self, were to be trusted to delegate the
   resulting authorization, its certificate result certificate then
   becomes a mapping of these other forms.  This may prove especially
   useful if a given certificate chain includes multiple forms or if the
   result certificate is to be used by a computationally limited device
   (such as a Smart-Card) which can not afford the code space to process
   some of the more complex certificate formats.

8.

9. Full BNF

8.1

   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
   grouped by kind of definition.  The top level objects defined are:

   <5-tuple>: an object defined for documentation purposes only.  The
   actual contents of a 5-tuple are implementation dependent.

   <acl>: an object for local use which might be implementation
   dependent.  An ACL is not expected to be communicated from machine to
   machine.

   <crl>, <delta-crl> and <reval>: objects returned from on-line tests.

   <sequence>: the object carrying keys and keys, certificates and on-line test
   results from machine prover to
   machine.

8.2 verifier.

9.2 Alphabetical List of BNF Rules

   <5-tuple>:: <issuer5> <subject5> <deleg5> <tag-body5> <valid5> ;
   <acl-entry>:: "(" "entry" <subj-obj> <deleg>? <tag> <valid>?
   <comment>? ")" ;
   <acl>:: "(" "acl" <version>? <acl-entry>* ")" ;
   <byte-string>:: <bytes> | <display-type> <bytes> ;
   <bytes>:: <decimal> ":" {binary byte string of that length} ;
   <cert-display>:: "(" "display" <byte-string> ")" ;
   <cert>:: "(" "cert" <version>? <cert-display>? <issuer> <issuer-loc>?
   <subject> <subject-loc>? <deleg>? <tag> <valid>? <comment>? ")" ;
   <comment>::  "(" "comment" <byte-string> ")" ;
   <crl>:: "(" "crl" <version> <version>? <hash-list> <valid-basic> ")" ;
   <date>:: <byte-string> ;
   <ddigit>:: "0" | <nzddigit> ;
   <decimal>:: <nzddigit> <ddigit>* | "0" ;
   <deleg5>:: "t" | "f" ;
   <deleg>:: "(" "propagate" ")" ;
   <delta-crl>:: "(" "delta-crl" <version> <version>? <hash-of-crl> <hash-list>
   <valid-basic> ")" ;
   <display-type>:: "[" <bytes> "]" ;
   <fq-name5>:: "(" "name" <key5> <names> ")" ;
   <fq-name>:: "(" "name" <principal> <names> ")" ;
   <general-op>:: "(" "do" <byte-string> <s-part>* ")" ;
   <gte>:: "g" | "ge" ;
   <hash-alg-name>:: "md5" | "sha1" | <uri> ;
   <hash-list>:: "(" "canceled" <hash>* ")" ;
   <hash-of-crl>:: <hash> ;
   <hash-of-key>:: <hash> ;
   <hash-op>:: "(" "do" "hash" <hash-alg-name> ")" ;
   <hash-value>:: <byte-string> ;
   <hash>:: "(" "hash" <hash-alg-name> <hash-value> <uri>? ")" ;
   <i-name5>:: "(" "name" <key5> <name> <uris> ")" ;
   <issuer-loc>:: "(" "issuer-info" <uri>* <uris> ")" ;
   <issuer-name>:: "(" "issuer" "(" "name" <principal> <byte-string> ")"
   ")" ;
   <issuer5>:: <key5> | <i-name5> | "self" ;
   <issuer>:: "(" "issuer" <principal> ")" ;
   <k-val>:: <byte-string> ;
   <key5>:: <pub-key> | <sec-key> ;
   <keyholder-obj>:: <principal> | <name> ;
   <keyholder>:: "(" "keyholder" <keyholder-obj> ")" ;
   <low-lim>:: <gte> <byte-string> ;
   <lte>:: "l" | "le" ;
   <n-val>:: <byte-string> ;
   <name-cert>:: "(" "cert" <version>? <cert-display>? <issuer-name>
   <subject> <valid> <comment> <comment>? ")" ;
   <name>:: <relative-name> | <fq-name> ;
   <names>:: <byte-string>+ ;
   <not-after>:: "(" "not-after" <date> ")" ;
   <not-before>:: "(" "not-before" <date> ")" ;
   <nzddigit>:: "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
   <obj-hash>:: "(" "object-hash" <hash> ")" ;
   <one-valid>:: "(" "one-time" <byte-string> ")" ;
   <online-test>:: "(" "online" <online-type> <uri> <uris> <principal> <s-
   part>* ")" ;
   <online-type>:: "crl" | "reval" | "one-time" ;
   <op>:: <hash-op> | <general-op> ;
   <principal>:: <pub-key> | <hash-of-key> ;
   <pub-key>:: "(" "public-key" <pub-sig-alg-id> <s-expr>* <uri>* <uris> ")" ;
   <pub-sig-alg-id>:: "rsa-pkcs1-md5" | "rsa-pkcs1-sha1" | "rsa-pkcs1" |
   "dsa-sha1" | <uri> ;
   <range-ordering>:: "alpha" | "numeric" | "time" | "binary" | "date" ;
   <relative-name>:: "(" "name" <names> ")" ;
   <reval-body>:: <one-valid> | <valid-basic> ;
   <reval>:: "(" "reval" <version> <version>? <subj-hash> <reval-body> ")" ;
   <s-expr>:: "(" <byte-string> <s-part>* ")" ;
   <s-part>:: <byte-string> | <s-expr> ;
   <sec-key>:: "(" "secret-key" <sec-sig-alg-id> <s-expr>* <uri>* ")" ;
   <sec-sig-alg-id>:: "hmac-md5" | "hmac-sha1" | "des-cbc-mac" | <uri> ;
   <seq-ent>:: <cert> | <name-cert> | <pub-key> | <signature> | <op> |
   <reval> | <crl> | <delta-crl> ;
   <sequence>:: "(" "sequence" <seq-ent>* ")" ;
   <sig-val>:: <s-part> ;
   <signature>:: "(" "signature" <hash> <principal> <sig-val> ")" ;
   <simple-tag>:: "(" <byte-string> <tag-expr>* ")" ;
   <subj-hash>:: "(" "cert" <hash> ")" ;
   <subj-obj>:: <principal> | <name> | <obj-hash> | <sec-key> | <keyholder> | <subj-thresh> <subj-
   thresh> ;
   <subj-thresh>:: "(" "k-of-n" <k-val> <n-val> <subj-obj>* ")" ;
   <subject-loc>:: "(" "subject-info" <uri>* <uris> ")" ;
   <subject5>:: <key5> | <fq-name5> | <obj-hash> | <keyholder> | <subj-
   thresh> ;
   <subject>:: "(" "subject" <subj-obj> ")" ;
   <tag-body5>:: <tag-expr> | "null" ;
   <tag-expr>:: <simple-tag> | <tag-set> | <tag-string> ;
   <tag-prefix>:: "(" "*" "prefix" <byte-string> ")" ;
   <tag-range>:: "(" "*" "range" <range-ordering> <low-lim>? <up-lim>?
   ")" ;
   <tag-set>:: "(" "*" "set" <tag-expr>* ")" ;
   <tag-star>:: "(" "tag" "(*)" ")" ;
   <tag-string>:: <byte-string> | <tag-range> | <tag-prefix> ;
   <tag>:: <tag-star> | "(" "tag" <tag-expr>  ")" ;
   <up-lim>:: <lte> <byte-string> ;
   <uri>:: <byte-string> ;
   <uris>:: "(" "uri" <uri>* ")" ;
   <valid-basic>:: <not-before>? <not-after>? ;
   <valid5>:: <valid-basic> | "null" | "now" ;
   <valid>:: <valid-basic> <online-test>? <online-test>* ;
   <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

   [Ab97] Abadi, Martin, "On SDSI's Linked Local Name Spaces", to appear
   in the
   Proceedings of the 10th IEEE Computer Security Foundations Workshop
   (June 1997).

   [BFL] Matt Blaze, Joan Feigenbaum and Jack Lacy, "Distributed Trust
   Management", Proceedings 1996 IEEE Symposium on Security and Privacy.

   [CHAUM] D. Chaum, "Blind Signatures for Untraceable Payments",
   Advances in Cryptology -- CRYPTO '82, 1983.

   [DvH] J. B. Dennis and E. C. Van Horn, "Programming Semantics for
   Multiprogrammed Computations", Communications of the ACM 9(3), March
   1966

   [ECR] Silvio Micali, "Efficient Certificate Revocation", manuscript,
   MIT LCS.

   [HARDY] Hardy, Norman, "THE KeyKOS Architecture", Operating Systems
   Review, v.19 n.4, October 1985. pp 8-25.

   [IDENT] Carl Ellison, "Establishing Identity Without Certification
   Authorities", USENIX Security Symposium, July 1996.

   [IWG] McConnell and Appel, ``Enabling Privacy, Commerce, Security and
   Public Safety in the Global Information Infrastructure'', report of
   the Interagency Working Group on Cryptography Policy, May 12, 1996;
   (quote from paragraph 5 of the Introduction)

   [KEYKOS] Bomberger, Alan, et al., "The KeyKOS(r) Nanokernel
   Architecture", Proceedings of the USENIX Workshop on Micro-Kernels
   and Other Kernel Architectures, USENIX Association, April 1992. pp
   95-112 (In addition, there are KeyKOS papers on the net available
   through http://www.cis.upenn.edu/~KeyKOS/#bibliography)

   [KOHNFELDER] Kohnfelder, Loren M., "Towards a Practical Public-key
   Cryptosystem", MIT S.B. Thesis, May. 1978.

   [LAMPSON] B. Lampson, M. Abadi, M. Burrows, and E. Wobber,
   "Authentication in distributed systems: Theory and practice", ACM
   Trans. Computer Systems 10, 4 (Nov.  1992), pp 265-310.

   [LANDAU] Landau, Charles, "Security in a Secure Capability-Based
   System", Operating Systems Review, Oct 1989 pp 2-4

   [LEVY] Henry M. Levy, "Capability-Based Computer Systems", Digital
   Press, 12 Crosby Dr., Bedford MA 01730, 1984

   [LINDEN] T. A. Linden, "Operating System Structures to Support
   Security and Reliable Software", Computing Surveys 8(4), December
   1976.

   [PKCS1] PKCS #1: RSA Encryption Standard, RSA Data Security, Inc., 3
   June 1991, Version 1.4.

   [PKLOGIN] David Kemp, "The Public Key Login Protocol", working draft,
   06/12/1996.

   [RFC1321] R. Rivest, "The MD5 Message-Digest Algorithm", April 16
   1992.

   [RFC1780] J. Postel, "Internet Official Protocol Standards", March
   1995.

   [RFC2045] N. Freed and N. Borenstein, "Multipurpose Internet Mail
   Extensions (MIME) Part One: Format of Internet Message Bodies", Dec 2
   1996.

   [RFC2046] N. Freed and N. Borenstein, "Multipurpose Internet Mail
   Extensions (MIME) Part Two: Media Types", Dec 2 1996.

   [RFC2047] K. Moore, "MIME (Multipurpose Internet Mail Extensions)
   Part Three: Message Header Extensions for Non-ASCII Text", Dec 2
   1996.

   [RFC2065] D. Eastlake and C. Kaufman, "Proposed Standard for DNS
   Security", Jan 1997.

   [RFC2104] H. Krawczyk, M. Bellare and R. Canetti, "HMAC: Keyed-
   Hashing for Message Authentication", Feb 1997.

   [SDSI] Ron Rivest and Butler Lampson, "SDSI - A Simple Distributed
   Security Infrastructure [SDSI]",
   http://theory.lcs.mit.edu/~cis/sdsi.html

   [SEXP] Ron Rivest, code and description of S-expressions,
   http://theory.lcs.mit.edu/~rivest/sexp.html .

   [SRC-070] Abadi, Burrows, Lampson and Plotkin, "A Calculus for Access
   Control in Distributed Systems", DEC SRC-070, revised August 28,
   1991.

Acknowledgments

   Several independent contributions, published elsewhere on the net or
   in print, worked in synergy with our effort.  Especially important to
   our work were: [SDSI], [BFL] and [RFC2065].  The inspiration we
   received from the notion of CAPABILITY in its various forms (SDS-940,
   Kerberos, DEC DSSA, [SRC-070], KeyKOS [HARDY]) can not be over-rated.

   Significant contributions to this effort by the members of the SPKI
   mailing list and especially the following persons (listed in
   alphabetic order) are gratefully acknowledged: Steve Bellovin, Mark
   Feldman, John Gilmore, Phill Hallam-Baker, Bob Jueneman, David Kemp,
   Angelos D. Keromytis, Paul Lambert, Jon Lasser, Jeff Parrett, Bill
   Sommerfeld, Simon Spero.

Authors' Addresses

   Carl M. Ellison
   CyberCash, Inc.
   207 Grindall Street
   Baltimore MD 21230-4103 USA

   Telephone:      +1 410-727-4288
                   +1 410-727-4293(FAX)
                   +1 703-620-4200(main office, Reston, Virginia, USA)
   EMail:          cme@cybercash.com
                   cme@acm.org
   Web:            http://www.clark.net/pub/cme

   Bill Frantz
   Electric Communities
   10101 De Anza Blvd.
   Cupertino CA 95014

   Telephone:      +1 408-342-9576
   Email:          frantz@netcom.com

   Butler Lampson
   Microsoft
   180 Lake View Ave
   Cambridge MA 02138

   Telephone:      +1 617-547-9580 (voice + FAX)
   EMail:          blampson@microsoft.com
   Ron Rivest
   Room 324, MIT Laboratory for Computer Science
   545 Technology Square
   Cambridge MA 02139

   Telephone:      +1-617-253-5880
                   +1-617-258-9738(FAX)
   Email:          rivest@theory.lcs.mit.edu
   Web:            http://theory.lcs.mit.edu/~rivest

   Brian Thomas
   Southwestern Bell
   One Bell Center, Room 23Q1
   St. Louis MO 63101 USA

   Telephone:      +1 314-235-3141
                   +1 314-331-2755(FAX)
   EMail:          bt0008@entropy.sbc.com

   Tatu Ylonen
   SSH Communications Security Ltd.
   Tekniikantie 12
   FIN-02150 ESPOO
   Finland

   E-mail:         ylo@ssh.fi

Expiration and File Name

   This draft expires 26 May 18 September 1998.

   Its file name is draft-ietf-spki-cert-structure-03.txt draft-ietf-spki-cert-structure-05.txt