Internet Info 1997 December/Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso/drafts/draft_s_z/draft-ylonen-spki-binary-00.txt

Text File | 1997-07-25 | 54KB | 1,298 lines

Network Working Group                           Tatu Ylonen <[e-mail]>
INTERNET-DRAFT                               SSH Communications Security
draft-ylonen-spki-binary-00.txt                           April 23, 1997
Expires in six months


          Proposal for SPKI Certificate Formats and Semantics

Status of This memo

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 and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``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 ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast),
or ftp.isi.edu (US West Coast).

Abstract

This document is a proposal for certificate formats and their semantics
in SPKI.  This proposal it is not based on S-expressions.



























Tatu Ylonen <[e-mail]>                                        [page 1]

INTERNET-DRAFT                                            April 23, 1997

Table of Contents

1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . .  2
2.  Notation for Binary Data  . . . . . . . . . . . . . . . . . . . .  3
  2.1.  Basic Data Types  . . . . . . . . . . . . . . . . . . . . . .  3
    2.1.1.  byte  . . . . . . . . . . . . . . . . . . . . . . . . . .  3
    2.1.2.  uint32  . . . . . . . . . . . . . . . . . . . . . . . . .  3
    2.1.3.  vlint32   . . . . . . . . . . . . . . . . . . . . . . . .  3
    2.1.4.  string  . . . . . . . . . . . . . . . . . . . . . . . . .  4
    2.1.5.  boolean   . . . . . . . . . . . . . . . . . . . . . . . .  4
    2.1.6.  mpint   . . . . . . . . . . . . . . . . . . . . . . . . .  4
    2.1.7.  time  . . . . . . . . . . . . . . . . . . . . . . . . . .  5
  2.2.  Advanced Data Types   . . . . . . . . . . . . . . . . . . . .  5
    2.2.1.  PRESENTED: String with presentation Hints   . . . . . . .  5
    2.2.2.  NAME: Internal Names  . . . . . . . . . . . . . . . . . .  5
    2.2.3.  PUBLICKEY: Public Keys  . . . . . . . . . . . . . . . . .  6
    2.2.4.  PRINCIPAL: Key Reference  . . . . . . . . . . . . . . . .  7
3.  Generic SPKI Binary Object Format   . . . . . . . . . . . . . . .  8
4.  Signed Objects  . . . . . . . . . . . . . . . . . . . . . . . . .  9
  4.1.  Authorization Certificates  . . . . . . . . . . . . . . . . . 10
  4.2.  Signed Statements   . . . . . . . . . . . . . . . . . . . . . 11
5.  Certificate Chain Verification Rules  . . . . . . . . . . . . . . 12
  5.1.  Defining an Operation   . . . . . . . . . . . . . . . . . . . 12
  5.2.  Defining the Problem  . . . . . . . . . . . . . . . . . . . . 13
  5.3.  Certificate Semantics   . . . . . . . . . . . . . . . . . . . 13
  5.4.  Authorization Verification Algorithm  . . . . . . . . . . . . 14
6.  Additional Validity Constraints   . . . . . . . . . . . . . . . . 15
  6.1.  Explicit Validity Period Starting Date  . . . . . . . . . . . 15
  6.2.  Weekday Based Validity  . . . . . . . . . . . . . . . . . . . 16
  6.3.  Certificate Revocation Lists  . . . . . . . . . . . . . . . . 16
  6.4.  Online Checking   . . . . . . . . . . . . . . . . . . . . . . 17
  6.5.  Periodic Revalidation   . . . . . . . . . . . . . . . . . . . 18
7.  Authorizations  . . . . . . . . . . . . . . . . . . . . . . . . . 18
  7.1.  Name Certificates   . . . . . . . . . . . . . . . . . . . . . 18
  7.2.  SDSI Tags   . . . . . . . . . . . . . . . . . . . . . . . . . 19
  7.3.  Delegation by Internet Domain Names   . . . . . . . . . . . . 19
    7.3.1.  One Possible Organization of DNS Name Delegation  . . . . 19
    7.3.2.  Host/Service Keys   . . . . . . . . . . . . . . . . . . . 20
    7.3.3.  E-Mail Keys   . . . . . . . . . . . . . . . . . . . . . . 20
  7.4.  Login Access  . . . . . . . . . . . . . . . . . . . . . . . . 21
  7.5.  National Public Key Infrastructures   . . . . . . . . . . . . 21
8.  Ascii Representation of Binary Objects  . . . . . . . . . . . . . 21



1.  Introduction

This draft is a proposal for a simple binary format and semantics for
the SPKI (Simple Public Key Infrastructure) working group.

The proposal has the following features and goals.

o  SDSI-style naming with presentation hints and naming delegation


Tatu Ylonen <[e-mail]>                                        [page 2]

INTERNET-DRAFT                                            April 23, 1997

o  SDSI/SPKI style authorizations

o  Joint delegation

o  Clear and simple semantics, ease of implementation

o  Binary format, explicit typing, minimum number of choices

o  Easy to extend without central coordination.

This proposal is heavily based on ideas from SDSI, SPKI, and
PolicyMaker.  It attempts to implement equivalent or better
functionality, but is much simpler and has very different
representations.

2.  Notation for Binary Data

2.1.  Basic Data Types

This section lists the binary representations for the basic data types
used in this document.  No special alignment is required for any data
types.

Rationale: No explicit type tagging is used.  All types are used in a
context where the type is known.  This is an explicit design choice over
ASN.1-style type tags with explicit lengths.  The motivations for this
choice are simplicity, conciseness, and the need to limit implementation
alternatives.  The extension mechanism is explicitly defined, and type
tagging would not provide much more flexibility but would leave much
more room for open interpretation.  Loose semantics and too many
implementation choices lead to complexity and interoperability problems.

2.1.1.  byte

A byte represents an arbitrary 8-bit value.  Fixed length data is
sometimes represented as an array of bytes, written byte[n], where n is
the number of bytes in the array.

2.1.2.  uint32

A 32-bit unsigned integer, represented as four bytes, MSB first.

For example, the value 699921578 (0x29b7f4aa) is represented as 29 b7 f4
aa.

2.1.3.  vlint32

Most integers, e.g. string lengths, are short.  The normal
representation for 32-bit integers in this proposal is a variable-length
format.  It is stored as one to five bytes, depending on the value being
stored.

Bits 6 and 7 (the most significant bits) of the first byte determine the


Tatu Ylonen <[e-mail]>                                        [page 3]

INTERNET-DRAFT                                            April 23, 1997

number of additional bytes that follow, and are interpreted as follows.

  Bit7  Bit6    Number of bytes that follow
   0     0       0
   0     1       1
   1     0       2
   1     1       4

Bits 0-5 of the first byte and the following bytes contain the value of
the integer, MSB first.  The smallest possible number of bytes should be
used.

If bits 6-7 are both one, the remaining bits in the first byte are zero
(reserved for future extension).

For example, the value 7 is represented as 07, and the value 193913
(0x2f579) as 82 f5 79.

Rationale: Small integers are used in many places.  There are about 20
integers in each certificate.  Thus, it probably pays off to add a
little bit of complexity to reduce their size.  Parsing and generating
this format is still quite straightforward.

2.1.4.  string

A string here means an arbitrary length binary string.  Strings are
allowed to contain arbitrary binary data, including null characters and
8-bit characters.

A string is represented as a vlint32 containing its length, followed by
zero or more bytes that are the value of the string.  No terminating
null character is included in the string.

For example, the string "testing" is represented as 07 t e s t i n g.

2.1.5.  boolean

A boolean value is represented as a single byte.  The value 0 represents
FALSE, and the value 1 represents TRUE.  All non-zero values are
interpreted as true, but applications should not store values other than
0 and 1.

2.1.6.  mpint

Multiple precision integers are represented by the mpint type.

  vlint32        number of bits
  byte[n]        value, MSB first, n = floor((bits + 7) / 8)

The number of bits is exact (e.g., value 5 has 3 bits).  Any unused bits
are in the first value byte (MSB) and must be zero.

For example, the value 694531781388612263 (0x9a378f9b2e332a7) is


Tatu Ylonen <[e-mail]>                                        [page 4]

INTERNET-DRAFT                                            April 23, 1997

represented as 3c 09 a3 78 f9 b2 e3 32 a7.

2.1.7.  time

Time values are needed e.g. for expiration dates and timestamps.  In
this proposal, all times are represented as seconds from January 1,
1970, 00:00.  All times are in UTC (GMT).

  byte          0  (reserved)
  uint32        seconds since 1/1/1970

This format allows operation until year 2106.  However, space is
reserved for an extra byte that will allow operation until 36812 if
taken into use in future.  For now, all implementations are required to
store a zero in that byte, and to reject any certificates with a non-
zero value in the reserved byte.

 Rationale: Using 32-bit binary values allows easy processing and
comparison on existing 32-bit machines.  This makes implementation
easier and reduces errors.  Standard functions for processing times in
this format are available at least in C, C++, Java, and Perl, which are
the most important anticipated implementation languages in near future.
This format is much easier to parse, process, and is more compact than
ascii representations.

2.2.  Advanced Data Types

This section lists data types that are special to certificate-like data.
These can be thought of as macros; they are composed of the basic types.

2.2.1.  PRESENTED: String with presentation Hints

The definition allows giving presentation hints for strings that are
used to name things or that are otherwise likely to be displayed to the
user.  The representation is as follows:

  string        presentation hint
  string        value

The presentation hint is a MIME type.  It may be empty, in which case
"text/plain; charset=iso-8859-1" is assumed.  It is only a hint;
applications are allowed to ignore it when displaying data.  However,
the presentation hint takes part in comparisons, and case is significant
for comparison purposes.  The presentation hint should be written in all
lowercase, unless otherwise mandated by the MIME specification.

The value is the data to be presented, as binary data (MIME Content-
Transfer-Encoding: binary).  It may be a textual, directly printable
string, or something else.  However, it may also be arbitrary 8-bit
binary data.

2.2.2.  NAME: Internal Names



Tatu Ylonen <[e-mail]>                                        [page 5]

INTERNET-DRAFT                                            April 23, 1997

Names of algorithms, certificate types, etc. are used in several places
in this specification.  There is often need for experimenting with new
algorithms, or for adding custom algorithms for certain customers.

A basic name consists of alphanumeric characters a-z, A-Z, 0-9, and
hyphens ('-').  Only standards bodies can define new basic names.

Extended names consist of a basic name suffixed by "@domainname", where
domainname is a valid registered internet domain name of the
individual/organization defining the new name.  For example,
"[e-mail]" would be a valid extended name.  The domain name should
be in all lowercase.

When a name is used in this specification, it can be of either of these
formats.  Names are case-sensitive.  They are represented as a string.

Rationale: This allows short standard names for commonly used things,
and allows for easy extension without need for central registration or
fear of conflicts.

2.2.3.  PUBLICKEY: Public Keys

Public keys are represented as follows:

  NAME          key type
  string        type-specific key data
  string        location (URI)

Format of public keys depends on the algorithm used.  The level of
abstraction for key types is that the operation takes in an arbitrary-
length document (possibly in parts), and produces a binary blob that is
the signature.  In other words, it combines a hash, signature algorithm,
padding, and encoding.

The location is optional, and specifies the location of the appropriate
key server(s) if present.

The rsa-md5-pkcs1 key type specifies RSA encryption, MD5 hashing of the
document, PKCS-1 padding and encoding for the data on which the
public/private key operation is performed, and PKCS-1 encoding for the
resulting signature.

The type-specific data is as follows.

  mpint         modulus
  mpint         exponent

An 1024-bit RSA key with exponent 33 and modulus 0x34...37 and empty URI
would be represented as a total of 149 bytes (line breaks and
indentation included only for clarity):

  0d r s a - m d 5 - p k c s 1
  40 84


Tatu Ylonen <[e-mail]>                                        [page 6]

INTERNET-DRAFT                                            April 23, 1997

    06 21
    44 00 34 ... 37
  00.

The dss-sha key type specifies DSA with SHA, with padding in accordance
to the DSS (Digital Signature Standard). XXX check the encoding; do we
need to refer to PKCS-1 or something else?

The ecp-elgamal-sha-p1363 key type specifies ECP-Elgamal with SHA and
P1363-conformant padding.  XXX Check encoding.  I'm not sure if P1363
specifies padding.

2.2.4.  PRINCIPAL: Key Reference

A principal is something that can be reduced to a key.  It always
specifies an explicit key, and may additionally specify a list of names
to follow to get the desired key.  The representation is as follows:

  PUBLICKEY      base key
  vlint32        name count (may be zero)
    PRESENTED      name  (repeat name count times)

This type is used to express SDSI-like name references of the form
"(<key> n1 n2 ... nk)".  Names are stored in the same order as they
appear in the SDSI S-expression (that is, n1 is the first name stored,
and refers to base key's namespace).

The names should be interpreted as constraints rather than functions:
each name may refer to multiple principals.  If something is asserted
about a principal using a name, it should be interpreted as asserting
about all principal with the given name (path).  Thus, if something is
delegated to a group, all members of the group receive that
authorization.  Delegating something to e.g. "(<key> group name)" would
have the semantics of delegating it to any principals for which any
member of the group has created the appropriate certificate for "name".

Rationale: SDSI defines the reference to refer to a single key, possibly
the newest.  However, this can cause problems.  Consider, for example,
the case that a user changes his/her key.  The old certificates will
linger around for some time, but the user starts making new certificates
with his new key.  Suppose someone has a name for the user; it should
now refer to both of the user's keys, as there may be valid certificates
around using both.  If it referred arbitrarily to either of them, some
certificates would mysteriously not work.  Most annoyingly, new
certificates issued by the user might not be considered valid even if
the user supplied the appropriate name certificates for the new key.

Bitwise comparison is used for names.  The presentation hint is
considered part of the name, and takes part in comparison.  However, if
the presentation hint is the empty string, it is expanded to the default
presentation type before comparison.

Rationale: Confusion and ambiguities are possible if the presentation


Tatu Ylonen <[e-mail]>                                        [page 7]

INTERNET-DRAFT                                            April 23, 1997

hint is not part of the comparison.  Suppose a CA assigns both names and
images using name certificates.  An image could have the same binary
representation as another principal's name, which would risk
accidentally delegating privileges to that other principal.  For similar
reasons (and tricky locality issues) names are also case-sensitive.
Implementations may do smart tricks in user interfaces; however,
certificate validation must use the strict rules.

SDSI has the concept of global names that are common to everyone.
However, when one starts considering key changes, compromises,
revocations, joint delegation, etc., there is no way to maintain the
mapping from everyone's local namespace to some global names.  What one
can do instead is to (possibly jointly) delegate naming to a centrally
managed key, and have it define names like DNS!!, and then consider all
global names relative to the principal's own key.

For example, assuming KEY is the key from the previous example, (KEY
DNS!! fi [text/plain; charset=us-ascii] ssh) would be represented as

  0d r s a - m d 5 - p k c s 1
  40 84
    06 21
    44 00 34 ... 37
  00
  03
    00
    05 D N S ! !
    00
    02 f i
    1c t e x t / p l a i n ; 20 c h a r s e t = u s - a s c i i
    03 s s h.

3.  Generic SPKI Binary Object Format

All SPKI objects follow the same generic pattern.  When passing keys and
certificates around, multiple such objects may be concatenated together,
and sent as a single unit.

Every SPKI object is of the following format:

  byte[4]       the characters "SPKI"
  NAME          object type
  string        object data

There is no maximum length for the object.  All implementations are
required to be able to process objects of at least 16384 bytes
(including magic number, object type, and object data).  Objects longer
than this may prevent communications with some implementations.

Rationale: Typically, the sender will send a number of certificates,
keys, and possibly other data to a receiver.  The receiver may not
understand all of these.  Because lengths are explicit, the receiver can
reliably walk through all received objects, and ignore those that it


Tatu Ylonen <[e-mail]>                                        [page 8]

INTERNET-DRAFT                                            April 23, 1997

does not understand.  New object types can also be added easily, without
need for central coordination.

SPKI objects may be keys, certificates, or some other types of data.
New object types may be added at any time.  Implementations are required
to ignore any objects they do not recognize.  This is the primary
extension mechanism in this proposal.  If new fields need to be added, a
new object type is defined.

Currently, the following object types have been specified:

  cert-1      Name/authorization delegation certificate
  sig-1       Signed statement on non-key
  crl-1       Certificate revocation list

Rationale: There is no separate type field within certificates or a
generic public key object type.  The motivation is simplicity: having
more type names, more options, more alternatives adds to implementation
complexity.  Implementations of the different object types will still
share code.  The main limitation due to this is that a user interface
cannot reliably say about an unknown object "it is an unknown
certificate of type [e-mail] by N.N"; instead it can only say "it is
an unknown object of type [e-mail]".

4.  Signed Objects

A certificate in SPKI terminology is any signed statement.  It can be a
signature on a document, a name certificate specifying naming or group
membership, or an authorization or some other statement about a key.

All signed objects begin with the data common to all objects, continue
with a shared part that is common to all certificate types, and
typically also contain type-specific data.  The common part has the
following format:

  PUBLICKEY     issuer
  time          time when issued
  time          expiration time
  string        additional validity data
  string        type-specific data
  string        comment
  string        signature

Rationale: Issuer key is stored directly in the certificate.  Another
alternative would be to store it indirectly, e.g. by hash.  However, a
typical certification path only includes each key twice (once as an
issuer and once as a subject).  An RSA key is about 150 bytes, and a
hash reference about 30 bytes (plus the key separately).  Thus, this is
about 210 bytes vs. 300 bytes in favor of hashes for 1024 bit RSA.  For
200-bit ECP-elgamal this would be more like 80 vs. 100 in favor of
direct storage.  More importantly, indirect storage adds substantial
complications to the logic for creating, maintaining, and verifying
certification paths.  Since the space overhead is not prohibitive, I've


Tatu Ylonen <[e-mail]>                                        [page 9]

INTERNET-DRAFT                                            April 23, 1997

chosen simplicity over minor space savings.  When certificates need to
be stored in limited space, standard compression algorithms can be used
to remove redundant keys from the certificates much more effectively
than hash references.

The comment field is not used for any automatic purpose.  However, it
may be displayed when specifically requested by a user interface.

The signature is computed over the concatenation of the object type
represented as a string (i.e., vlint32-coded length is included) and all
object data preceding the signature field.  The characters "SPKI" and
the length of the object data are not included in the signature.  No
additional data is allowed after the signature; any such certificates
should be rejected.

The meaning of other fields is defined in Sections ``Certificate
Semantics'' and ``Additional Validity Constraints''.

4.1.  Authorization Certificates

Authorization certificates are used to delegate names and authorizations
from one principal to another.  Delegation may be to a directly
specified key, or to a key specified indirectly by a name.

Delegation certificates have object type "cert-1" and the following
type-specific data:

  vlint32       number of alternative subjects
    PRINCIPAL     subject  (repeats as specified above)
  vlint32       number of subjects required
  boolean       may be delegated
  vlint32       number of authorizations
    NAME          domain of interpretation  ) repeated
    string        authorization             )

Rationale: The only form of certificate supported is a joint delegation
certificate.  A normal certificate has only one alternative subject.
This case has a two-byte overhead over a simple certificate without the
counts.  However, joint delegation is important for avoiding single
points of trust.  Having the basic certificate be the joint delegation
certificate forces every implementation to support joint delegation from
the beginning.  This adds some complication to code, but not very much
(see Section ``''.  Also, this way there is only one certificate format
to support.

In the simple case of only one subject, the specified authorizations are
delegated to the subject key.  In the case of N subjects of which M are
required, the authority is delegated to all subjects in such a manner
that M of them need to confirm an operation for it to be authorized.
This is explained in more detail in Section ``Authorization
Verification''.

The number of alternative subjects should be between 1 and 100,


Tatu Ylonen <[e-mail]>                                       [page 10]

INTERNET-DRAFT                                            April 23, 1997

inclusive; the number of subjects required must be between 1 and the
number of alternative subjects, inclusive.

The "may be delegated" flag indicates whether the subject(s) may further
delegate the authorization.

Number of authorizations specifies how many times the domain of
interpretation and authorization fields are repeated (they are repeated
in pairs, first both fields once, then both fields another time etc).
The semantics of multiple authorizations in a single certificate are
equivalent to that of multiple certificates with a single authorization
in each.

Rationale: Multiple authorizations are allowed in a single certificate,
because it is common to have a name certificate together with some
authorization for that name.  For example, within DNS, one might have a
name certificate for a subdomain's key together with delegation of host
key and email key authorizations to that key.  The overhead is one byte
for certificates that have only one authorization.

The domain of interpretation specifies the ruleset according to which
authorization is interpreted.  The authorization can be arbirary binary
data, and is given meaning only by the domain.  See Section
``Authorizations'' for more information.

Rationale: There is no separate name certificate.  Name certificates are
normal certificates with domain "name" and specially formatted
authorization.

A sample certificate object might look like the following:

  S P K I
  06 c e r t - 1
  xx1               ; len of object data
    <public key for issuer>
    00 2D 20 C9 80  ; time of issue
    00 37 12 34 56  ; expiration time
    00              ; additional validity
    xx2             ; len of type-spec data
      01            ; number of subjects
      <public key for subject> ; subj1 base key
      00            ; subj1 number of names
      01            ; number of subjects required
      01            ; may be delegated
      01            ; number of authorizations
      04 n a m e    ; domain of interpretation
      0d            ; authorization len
        00          ; presentation hint len
        0b J o h n 20 M . 20 D o e
    00              ; comment
    10 <16 bytes for MD5 hash>.




Tatu Ylonen <[e-mail]>                                       [page 11]

INTERNET-DRAFT                                            April 23, 1997

4.2.  Signed Statements

A signed statement may refer to an object, or may be used for some other
purpose.  Signed statements have the object type "sig-1" and the
following type-specific data:

  NAME        domain of interpretation
  PRESENTED   statement

The domain of interpretation identifies the ruleset according to which
the statement is to be interpreted.  Currently, the following domains
have been defined:

  natural        human-readable natural language
  sha1           detached SHA-1 hash of object
  md5            detached MD5 hash of object

The natural domain specifies that the statement is intended to be
processed by humans, and is written in some human-readable language.  No
automatic processing is attempted.

The sha1 and md5 domains specify that the statement is the respective
hash of some detached object.  The actual object reference should be by
some external means (such as by being attached in the same e-mail
message).  The presentation hint should be empty, and value should
contain the hash of the object in binary (16 bytes for MD5, 20 bytes for
SHA-1).

5.  Certificate Chain Verification Rules

The source of all authorization is the entity performing
certificate/authorization verification.  Typically, this is a computer
program, and it is locally configured to delegate authorization to some
key or keys.

The concept of certificate chain verification is somewhat misleading in
authorization-based key infrastrucures.  The real issue is determining
whether a principal is authorized to do something (e.g., read a web
page, use a bank account, connect to a computer, sign a specific
purchase order).  This translates to "have I delegated to this principal
the authorization to do this?"

5.1.  Defining an Operation

When we talk about authorization, we need to specify what we are
authorizing.  We say that we authorize some operation.  There are
several issues related to authorizing an operation:

o  There is some entity requesting the operation.  Only some entities
   are allowed to do certain things.  We assume that the entity has a
   key representing it, and include the entity's key CLIENTKEY in the
   definition of the operation.



Tatu Ylonen <[e-mail]>                                       [page 12]

INTERNET-DRAFT                                            April 23, 1997

o  The operation is a request to some entity to do something (a
   computation or a physical operation).  The same request might be sent
   to different entities, and they would perform the operation on
   different objects.  Thus, both the entity and the request are part of
   the specification of the operation.  We assume that the entity has a
   key representing it.  We represent this by including the entity's key
   SERVERKEY and the request REQUEST in the definition of the operation.

o  Authorization relates to a particular instance of an operation.  This
   implies that authorization is bound to time, but time alone is not a
   sufficient.  With online checking, only one of two simultaneous
   identical operations might be approved.  We include time TIME and
   instance INSTANCE in the specification of an operation.  (Time is
   included separately because it is usually sufficient to determine
   authorization.  INSTANCE is a unique random identifier.)

An operation OPERATION is represented by the tuple (CLIENTKEY,
SERVERKEY, REQUEST, TIME, INSTANCE).  This answers the questions "Who
does, what does, and when does?".  It is assumed that the entity
requesting the operation proves it identity (i.e., possession of
CLIENTKEY) using some suitable mechanism.

CLIENTKEY might actually also be a set of keys that are jointly
performing some operation.  This may make sense with joint delegation.
This does not substantially change the algorithms.

5.2.  Defining the Problem

The authorization problem is "Does SERVERKEY authorize OPERATION?",
where SERVERKEY represents the entity on which the operation is
performed.

For some operations this definition may seem superficial.  For example,
consider the naming problem: "does (BASE n1 n2 ... nk) refer to KEY?"
Here, the act is being a representative of a name, and the question
becomes "Does BASE authorize KEY to be called (BASE n1 n2 ... nk)".
Dressed as an operation, this is the same as "Does BASE authorize (KEY,
BASE, "name: n1 n2 ... nk", TIME, INSTANCE)".

5.3.  Certificate Semantics

A certificate contains a set of authorizations.  The semantics of having
multiple authorizations in a single certificate are the same as having
multiple otherwise identical certificates, each containing one
authorization from the set.  To simplify the notation, we consider all
certificates to have only a single authorization AUTH.

A certificate CERT can be represented as (ISSUER, Tissue, Texpire,
VALIDITY, SUBJECTS, DELEGATE, AUTH)".

A certificate is valid at time TIME for instance INSTANCE if it has a
correct signature by ISSUER, Tissue <= TIME <= Texpire, and VALIDITY is
fully understood and indicates the certificate is valid at time TIME for


Tatu Ylonen <[e-mail]>                                       [page 13]

INTERNET-DRAFT                                            April 23, 1997

instance INSTANCE.

SUBJECTS is a tuple ({(K, NAMES)}, M), where K is a key and NAMES is a
(possibly empty) sequence of names.  Normally, there is only one subject
in the set, and M = 1.  However, with joint delegation there may be
multiple subjects, and in this case delegation is to at least M of the
subjects jointly.

AUTH is a constraint on the possible requests that the subject may
perform.  It is a tuple (DOI, AUTHDATA).

A valid certificate means: ISSUER allows SUBJECTS to perform requests
permitted by AUTH on ISSUER.  Furthermore, if DELEGATE is TRUE, ISSUER
also allows allows those allowed by SUBJECTS to perform f(AUTH, REQUEST)
on themselves, to perform operations permitted by AUTH on ISSUER.  The
function f(AUTH, REQUEST) is a transformation to be performed on REQUEST
at every delegation step; for names, it strips the first name component
from REQUEST.

Rationale: The semantics of joint delegation is that M of the subjects
need to allow the operation.  Different subjects can delegate the
authorization via different paths.

Rationale: The function f must have knowledge about all authorizations
processed in the application.  Also, a function is needed to determine
whether REQUEST is permitted by AUTH.  No other understanding of AUTH or
REQUEST is needed by the logic for verifying authorizations or names.
In most cases, both of these functions are very simple.  The function
can be defined separately for each domain of interpretation.

Authorizations in different domains are completely independent.
Authorizations and requests must be in the same domain to be relevant
for each other.

5.4.  Authorization Verification Algorithm

Let us now consider the authorization question "Does a set of
certificates CERTS state that SERVERKEY authorizes OPERATION?", where
OPERATION = (CLIENTKEY, SERVERKEY, REQUEST, TIME, INSTANCE).

1. If CLIENTKEY and SERVERKEY are the same key, the operation is
   trivially allowed.

2. Otherwise, the operation is allowed if there is a certificate CERT in
   CERTS such that:

o  CERT is valid at time TIME for INSTANCE.

o  CERT.ISSUER and SERVERKEY are the same key.

o  REQUEST is permitted by CERT.AUTH.

o  There are at least M tuples (K, NAMES) in CERT.SUBJECTS for which all


Tatu Ylonen <[e-mail]>                                       [page 14]

INTERNET-DRAFT                                            April 23, 1997

   of the following hold:

o  There is a key SUB for which CERTS state that K authorizes (SUB, K,
   "name: NAMES", TIME, INSTANCE).  (This verifies that SUB is a valid
   representative for the given name.  Some additional syntax may be
   needed in reality to make a valid request from NAMES.  When NAMES is
   empty, SUB equals K.)

o  Either SUB equals CLIENTKEY (is in CLIENTKEY if CLIENTKEY is allowed
   to be a set), or DELEGATE is TRUE and CERTS state that SUB authorizes
   (CLIENTKEY, SUB, f(AUTH, REQUEST), TIME, INSTANCE).

Rationale: Joint certificates, name certificates, and all other
certificates are handled by the same algorithm.  The algorithm is
reasonably simple.

Revalidation and CRLs are handled as part of the "is valid" phrase.
They might involve recursive calls to the same algorithm.

This definition has one interesting consequence for names: if something
is delegated to the name (BASE n1 n2 ... nk), it is delegated to all of
the keys BASE, (BASE n1), ..., (BASE n1 ... nk).

Rationale: At first sight this might seem very wrong; however, BASE can
anyway create a new key and name certificate for n1, n2, etc., and can
thus effectively make the delegation go to any key desired.  This is a
fundamental property of trusting someone's name space.  It is better to
acknowledge the trust relationship openly than to claim that no
authorization was delegated to the naming keys.  Besides, the resulting
verification algorithm is simpler.  The alternative would be to define a
third domain-dependent function to process authorizations that hold only
for the terminal node.

6.  Additional Validity Constraints

The additional validity data in signed objects can be used to specify
additional validity conditions in addition to requiring the time to be
between the issue date and the expiration date.

The additional validity data consists of string pairs, and has the
following format:

  NAME      condition name
  string    data
(Above repeats as many times as needed)

A certificate should be rejected if it contains a validity condition
that is not understood.

6.1.  Explicit Validity Period Starting Date

An explicit validity period starting time may be provided.  The
condition name is "not-before", and data contains


Tatu Ylonen <[e-mail]>                                       [page 15]

INTERNET-DRAFT                                            April 23, 1997

  time      validity period start

This specifies that certificate is not valid until the validity period
starts, regardless of the time of issue.

6.2.  Weekday Based Validity

Some certificates may be valid at only certain times of the week.  This
is represented by the condition name "weekday", and data containing

  string     validity times

Validity times is an ascii string containing semicolon-separated time
specifications, each of the format "weekday@start-end", where weekday is
a comma-separated list of day numbers 0-6 (0 = Sunday), and start and
end are times of the format "hour:minute".

For example, "1,2,3,4,5@9:00-17:00;6@9:00-14:00" would specify that the
certificate is valid Mon-Fri 9 am to 5 pm, and Saturdays 9 am to 2 pm.

6.3.  Certificate Revocation Lists

Many applications require certificates to be verified against a
periodically published certificate revocation list (CRL).  This is
indicated by a condition name "crl", and the following data:

  PUBLICKEY     CRL signer key
  string        location of CRL (URI)

The certificate is to be accepted only if the verifier has a valid CRL
available from the given signer, and the certificate is not listed in
the CRL.

The CRL is an SPKI object of type "crl-1", and has the following object
data:

  PUBLICKEY     CRL signer key
  time          time when issued
  time          recheck time
  time          expiration date
  string        location of next crl (URI)
  boolean       is delta crl
  time          issue time of base crl
  NAME          revocation format
  vlint32       number of revocations
  <variable number revocation entries>
  string        signature

If no CRL is available, one can be requested using the location
specified in the original certificate.  If a CRL is already available,
the next one should be requested using the location in the previous CRL.
The location there may contain information about the time of the
previous CRL, and may return a delta to the previous CRL.


Tatu Ylonen <[e-mail]>                                       [page 16]

INTERNET-DRAFT                                            April 23, 1997

The signature is computed over the object type (including length) and
all data of the CRL preceding the signature.  The CRL should be ignored
if it does not have a valid signature.

The "time when issued" field identifies the CRL.  The "recheck time"
indicates the time after which the verifier should attempt to fetch a
new CRL.  However, the CRL remains valid after this time.  "Expiration
time" specifies the time after which the CRL expires; it is no longer
valid after this time.
The "is delta crl" field is TRUE if this is a delta to some previous
CRL.  The "issue time of base crl" contains the timestamp of that CRL;
if that does not match the issue time of the previous CRL that the
verifier has, it should request a completely new CRL using the location
in the original certificate.  The "issue time of base crl" field is
ignored if the CRL is not a delta.  A full CRL should also be requested
if "revocation format" changes.

Delta CRLs should be merged into the previous CRL.  Revocations listed
in the delta with the "rm" reason should be removed.  Other revocations
should be merged into the old CRL.  The new issue time and location
should be taken from the delta.

The format of each revocation entry depends on the revocation format
field.  The values "sha1" and "md5" are defined, and have the following
encoding for each revocation, with the respective hash used.

  string        hash of the entire certificate object
  time          revocation time
  NAME          reason

The reason indicates why the certificate was revoked.  It may be empty
if no reason is specified.  The following values are defined; other
values are possible and should be interpreted as cancelling the
certificate.

  keyc            subject key was compromised
  affc            affiliation changed
  sup             superseded by a new certificate
  cessation       cessation of operation
  call            on hold; call certificate issuer
  rm              remove from crl

The reason "call" instructs that the verifier should either reject the
certificate or call the issuer to verify its status.  The code "rm" is
only used in delta CRLs, and is used to list keys that were on the
preceding crl, but are no longer on the latest delta.  All other reasons
simply cause the matching certificate to be rejected.

XXX should we have delegatable authorization "crl" that would permit the
CRL key to delegate the authority to make CRLs?

6.4.  Online Checking



Tatu Ylonen <[e-mail]>                                       [page 17]

INTERNET-DRAFT                                            April 23, 1997

Online checking is specified by a condition name "online".  XXX specify
contents and protocol later.

6.5.  Periodic Revalidation

XXX specify later.  New authorization "revalidate", with certificate
hash included in authorization.  Recursive call to verification logic.
One practical advantage of revalidation as opposed to CRLs is that the
client can retrieve the revalidation certificate, whereas CRLs need to
be retrieved by servers.  This brings extra overhead and complication to
servers.

7.  Authorizations

This section lists some sample authorizations.  Except for name
certificates, the definitions are still quite preliminary.

7.1.  Name Certificates

Name certificates are used to specify names and group membership.  These
concepts are identical; one may give the same name to multiple
principals or have groups of one member if one likes.  It is normal for
people to have two keys for short periods of time while they are in the
process of changing keys.

Each named thing has a key.  The name certificate alone does not
delegate any rights to the key.  It only specifies a name.

Name certificates have domain of interpretation "name".  Authorization
is binary data, formatted as follows:

  PRESENTED     name

Rationale: Name certificates are just ordinary certificates to simplify
verification logic.  Keys are cheap, so there is no real need for groups
without keys.  Also, name certificates do not imply delegation; thus,
there is no need for constraining what is delegated to a name.  If
delegation to the name is desired, it must be done explicitly with a
separate authorization (possibly in the same certificate).  The client
typically supplies the needed certificates, so there is normally no need
for fetching extra certs because of this naming scheme.  Also, if both
name and delegation are put in the same certificate, signature checking
overhead is reduced.

There is also no distinction between different types of information,
such as nicknames, full names, social security numbers, customer
numbers, pictures, etc.  One can define multiple certificates to support
these.  The type of the name can implied by the presentation hint (e.g.,
"image/jpeg" or "text/x-fi-socid").

Name certificates where both representation and value are empty strings
have special meaning.  They indicate that the subject's name space is
merged into the issuer's name space.  Essentially it delegates all


Tatu Ylonen <[e-mail]>                                       [page 18]

INTERNET-DRAFT                                            April 23, 1997

naming authority for the issuer to the subject.  They do not
automatically delegate anything else than naming.

Rationale: merging namespaces is useful.  For example, an organization
might centrally define certain standard names, such as DNS!!, and have
all end-user and host keys merge the name space from that key into their
keys.  That way, changes in the appropriate root keys can be managed
centrally.  Also, in a traditional naming-based CA hierarchy one only
wants to configure the root key into clients, and may want to merge the
namespaces of the subordinate CAs into the namespace of the root CA.

The function f(AUTH, REQUEST) for name certificates is defined as
stripping the first name component from REQUEST.  The resulting new
request is returned.  However, in the case that AUTH has both
presentation and value as empty strings, this returns the original
request instead.

For name certificates, AUTH permits REQUEST if the presentation hint and
value are bitwise equal to those in the first name component of REQUEST
(after filling in the default presentation).  However, in the case that
auth has both presentation and value as empty strings, AUTH always
permits REQUEST.

7.2.  SDSI Tags

SDSI-style S-expression tags may be used as authorizations.  They are
represented by domain of interpretation "sdsi", and the authorization is
the tag S-expression in SDSI format.

7.3.  Delegation by Internet Domain Names

Many applications (e.g., host keys, e-mail) need keys where naming and
authorization is delegated hierarchially.  However, one does not want to
trust the root keys in the hands of any single organization.  One
possible solution for such infrastructures is presented here, with
examples of particular types of keys at the end.

7.3.1.  One Possible Organization of DNS Name Delegation

There is no single key for the domain name hierarchy.  Instead, there
are four keys, three of which are required to sign each top-level
domain.  The keys are each held by a trusted organization in the US, in
EU, in Japan, and by some other suitable organization.

The public keys of the root keys are widely published.  Each
organization configures its machines and applications to jointly trust
three out of four of these central servers.  (If some organization
wishes to have a different trust model, it has the opportunity to do
this.)  The configuration can most conveniently by done by delegating
trust within the orgnization to a central key (or jointly to a few keys)
from each machine, and delegating it jointly to the root keys from this
key (or from each of these keys).



Tatu Ylonen <[e-mail]>                                       [page 19]

INTERNET-DRAFT                                            April 23, 1997

Each top-level domain may decide for itself whether it wants to have a
single key that can delegate to subdomains, or whether it prefers to use
joint delegation.  If single key delegation is used, all root keys
delegate to this key.  If joint delegation is preferred, all root keys
delegate jointly to these keys.

Each top-level domain key gets the right to delegate host keys for that
domain.  For example, ".fi" domain key could delegate host and e-mail
keys for "*.fi".  These would be separate delegations (but might both be
created automatically by the same application).

Each organization again has a key for its domain name.  For most
organizations, a single key is suitable to reduce administrative burden.
For multinational corporations and other very large or security-
conscious organizations, using joint delegation may again be warranted.

An additional complication for organizations is that they may have
machines with the name of the organization directly.  For example, the
key for "ssh.fi" should be authorized to delegate both "ssh.fi" and
"*.ssh.fi".

XXX An alternative approach to host keys is to suggest that every
principal has name DNS!! pointing to the DNS root key, and have the name
at each level be just one component of the name.  Which is better?

7.3.2.  Host/Service Keys

One common application for a public key infrastructure is hierarchial
delegation of host key/user key certification.  In many lightweight
applications, wide deployment requires that certification can be taken
very far down in the organization.  One needs to delegate certification
by internet domain names, and possibly even within domains.  One may
want to have different keys for different services to prevent an
untrusted service from having access to the host key used by some
critical service.  Services are identified by TCP/IP port numbers.

For host/service keys, description is of the format "domain.name:port-
number", where '*' and '?' may be used as wildcards in any position to
match an arbirary number of characters or any single character,
respectively.  However, they do not match the colon (':').

For example, "*.niksula.hut.fi:*" would delegate the subject the
authority to certify host keys for any service on machines whose name
matches "*.niksula.hut.fi".  A host master key might have e.g.
"joker.niksula.hut.fi:*" as the description.  A per-service key might
have the description "joker.cs.hut.fi:80".

7.3.3.  E-Mail Keys

E-mail key delegation is similar to host key delegation.  However, the
description has slightly different format:
"[e-mail]:algorithms", with the same wildcard conventions as for
host keys (except that the '@' and ':' signs cannot be matched by


Tatu Ylonen <[e-mail]>                                       [page 20]

INTERNET-DRAFT                                            April 23, 1997

wildcards).  For example, "*@*.hut.fi:*" would give the key the
authority to assign keys to any e-mail addresses within the hut.fi
domain.

The algorithms field is used to specify the encryption algorithms and
other options that the recipient supports.  It is a comma-separated
list, where each element begins with an algorithm/option name as
specified earlier, optionally followed by a space and printable other
than comma.  No valid names have been specified at this time, but
examples could include e.g. "smime-rsa1024-3des", "smime-rsa512-rc4-40".
The idea of the algorithms field is to allow the sender to know which
algorithms the recipient supports, so that it can choose the best
algorithms supported by both parties.  Note that in practice this might
be implemented so that delegation is allowed by the end user's e-mail
key (e.g., with the form "[e-mail]:*"), and the user (or user's e-mail
application, to be accurate) would then delegate the right to either the
same key or another key that is to be used, and specify the algorithms
it is willing to receive.

7.4.  Login Access

These certificates would probably contain the name of the user, the host
to access, and possibly some additional flags e.g. regarding privileges.
No delegation hierarchy is needed.

7.5.  National Public Key Infrastructures

National public key infrastructure work has traditionally been based on
X.509.  X.509 is fairly well suited for this kind of applications, as it
provides a well-understood rigid hierarchy.  Certification is delegated
by to a number of hierarchial certification authorities.  There may be a
single root CA, or root CAs may cross-sign each other's keys.

Each root CA may have a different policy about the semantics of its
certificates and the form of authentication they require.  For example,
one CA might give certificates that mean "the key of this
person/organization is NNN", and might have the policy of requiring two
independent forms of identification before they issue a certificate.

There is typically no way to constrain which entities each CA can create
certificates for (though there might be policy constraints, but these
are not enforced technically).  The root CA delegates to all subordinate
CAs the right to create any key-name mappings.
The verifier normally does not want to care about names on the path from
the root to the final CA.  Thus, the intermediate name delegations
should probably use an empty name, so that all naming is delegated to
the subordinate CA.

If authorization delegation is also desired, the CA can create both a
name certificate and a delegation certificate delegating the appropriate
rights to the end user key.




Tatu Ylonen <[e-mail]>                                       [page 21]

INTERNET-DRAFT                                            April 23, 1997

8.  Ascii Representation of Binary Objects

A standard ASCII representation is needed for SPKI objects.

An object sequence containing only certificates is represented as

***** SPKI CERTIFICATE DATA ************
<base64 encoding of SPKI objects, specified in RFC1521>
***** END OF SPKI CERTIFICATE DATA *****

An object sequence containing only certificates and signatures is
represented as

***** SPKI SIGNATURE DATA ************
<base64 encoding of SPKI objects, specified in RFC1521>
***** END OF SPKI SIGNATURE DATA *****

All other object sequences are represented as follows.  This
representation is always allowed, even when the above alternatives
apply.  However, implementations are encouraged to use the appropriate
headers to help users understand what kind of data it is.

***** SPKI DATA **********************
<base64 encoding of SPKI objects, specified in RFC1521>
***** END OF SPKI DATA ***************

Furthermore, the following format is used to specify both a textual
document that is to be hashed and SPKI data that contains a signature
(and possibly certificates) for that document.

***** SPKI SIGNED DOCUMENT ***********
<document in cleartext>
***** SPKI SIGNATURE DATA ************
<base64 encoding of SPKI objects, specified in RFC1521>
***** END OF SPKI SIGNATURE DATA *****

For hashing purposes, the document in cleartext is considered to have
all newlines replaced by a single newline, and to have all trailing
spaces and tabs at ends of lines removed.  Before wrapping the document
into this format, all lines starting with "***** SPKI " are changed to
start with "* ***** SPKI ".  Hashing is done without this
transformation.  XXX what other transformations or provisions need to be
made for reliable e-mail transmission?

Rationale: When passing objects around in e-mail or other similar media,
it is convenient to roughly specify the type of the object to help the
user understand what it contains.  The special format for signed
documents is included to define a readable way to sign documents, e.g.
for transmission in e-mail.  Experience from PGP suggests that '-' is a
bad character for starting lines, as it is quoted by very many
applications, and '=' is a bad character in base-64 encoding as it is
clobbered by some MIME implementations.


Tatu Ylonen <[e-mail]>                                       [page 22]