Ronald L. Rivest
Laboratory for Computer Science
Massachusetts Institute of
Technology
Cambridge, MA 02139
rivest@theory.lcs.mit.edu
http://theory.lcs.mit.edu/~rivest
Butler Lampson
Microsoft Corporation
blampson@microsoft.com
http://research.microsoft.com/lampson
Wednesday October 2 8:18 PM EDT
1996
This paper is a working document
defining SDSI version 1.1.
Check that you have the latest
version.
We propose a new distributed security infrastructure,
called SDSI (pronounced “Sudsy”). SDSI combines a simple public-key
infrastructure design with a means of defining groups and issuing
group-membership certificates. SDSI’s groups provides simple, clear terminology
for defining access-control lists and security policies. SDSI’s design emphasizes
linked local name spaces rather than a hierarchical global name space.
*. Introduction
*. Overview
*. Data Structures and Syntax
*.*. S-expressions
*.*.*. Character Sets.
*.*.*. Octet strings
*.*.*.*. Hexadecimal
*.*.*.*. Base-64
*.*.*.*. Tokens
*.*.*.*. Quoted Strings
*.*.*.*. Verbatim
*.*.*.*. Fragments
*.*.*.*. Presentation Hints
*.*.*. Lists
*.*. Numbers, Hash Values, and Dates
*.*. Compression
*.*. Object and message types
*. Standard SDSI Object Types
*.*. Keys and Encryption Parameters
*.*. Principals as public keys, and their servers
*.*. Encrypted objects
*.*. Signed objects
*. Local Names, Certificates, and Name/Value Bindings
*.*. Names
*.*. Name/Value Bindings
*.*. Certificates
*. Protocols
*.*. Queries with the “Get” protocol
*.*. Reconfirmation Queries
*.*. Auto-Certs
*.* Delegation Certificates
*.*. Transport mechanisms
*. Groups and ACLs
*.*. An algorithm for determining group membership
*.*. Membership queries
*.*. Access-Control Lists
*. Application Scenarios
*.*. Mail Reader
*.*. World-Wide Web
*.*. Kerberos-like tickets
*.*. Distributing signed code
*.*. Corporate database access
*.*. Access to medical records
*.*. Shared-secret key establishment
*.*. Multi-cast
*.*. Key Compromise
*. Conclusions
This paper was motivated by the perception that the existing proposals for a public-key infrastructure (such as X.509-based schemes that require global certificate hierarchies [4]) are both excessively complex and incomplete. Their complexity arises from a dependence on global name spaces and an attempt to formalize too many things. Their incompleteness can be immediately perceived if one tries to define a security policy (e.g. write a ACL) based on the scheme.
We were also motivated by similar corresponding design efforts, such as that of the IETF “SPKI” (Simple Public-Key Infrastructure) working group (in particular, Carl Ellison’s work), the work of Blaze, Feigenbaum, and Lacy [1], and work within the World-Wide Web Consortium’s security group. Our proposal borrows freely from these sources, and has benefited greatly from them.
Our goal is to provide ideas and techniques that facilitate the construction of secure systems. Issues regarding the liabilities and/or the legal interpretation of certificates are not addressed here. Because we feel security is enhanced by simple clear data structures, we emphasize clarity and readability at the expense of economical encodings, although SDSI includes means for efficiently representing its data structures.
We first give an “executive summary” of our proposal here, and then flesh it out in the following sections. A detailed specification suitable for as an implementation guide will appear in a companion paper.
Principals are public keys. Our system is “key-centric”: SDSI principals are public digital signature verification keys. These public keys are central; everything is based around them. The notion of an “individual” (e.g. person, corporation, process, or machine) is not required. Of course, such individuals will actually control the associated private keys, so that the public/private keys can be viewed as “proxies” for those individuals. In this paper, one should think of a “principal” as a public key, and concurrently as “one who speaks” (by signing statements that can be verified with that public key). Each principal is represented by a data structure that can be passed around, such as:
( Public-Key: ( RSA-with-SHA1: ( N: =Gt802Tbz9HKm067= ) ( E: &11 ) ) )
so a principal can also be the “value” of some name.
Egalitarian design-no global hierarchy necessary. Our proposal is egalitarian: each principal can make (signed) statements and requests on the same basis as any other principal. No hierarchical global infrastructure is required. Of course, in practice some principals would be more important than others, and SDSI allows for some principals to have special status as “special roots,” allowing SDSI to accomodate “global names.” But that is for convenience rather than necessity.
Each principal is a “certification authority.” In SDSI, certificates can be created and signed by anyone: everyone can be a “CA.” Which policies and procedures (if any) a principal follows when issuing certificates is up to that principal to choose: he may declare that he is following some industry-standard procedure, or he may issue certificates arbitrarily or capriciously.
Local name spaces. Each principal can create his own local names with which he can refer to other principals. These local names arbitrarily chosen; they may be derived from nicknames, email addresses, account numbers, etc.:
jim "Bob Jones, Jr." account-314568901387 WebCo-Vice-President-John-Smith joe@penguin.lcs.mit.edu( Accounting Bob-Smith )
There is no fixed “global” name space giving a unique name for principals. The principal you call alice-smith may be different from the principal I call alice-smith. An exception is made for a small set of “special root” principals, whom everyone calls by the same name.
Simple data structures. SDSI objects are represented by “S-expressions” (octet-strings and lists of simpler S-expressions) having a clean human-readable ASCII representation. “Presentation hints,” based on MIME content-types, enable octet-strings to be presented in italics, or as Unicode characters, or as photos, etc. There are also ways to transmit S-expressions efficiently.
Flexible signatures. SDSI signatures are exceptionally flexible: signatures may be appended to the objects being signed, or they may be detached from the signed objects. Objects may be co-signed by several signers. Signers may sign on behalf of someone else. Signatures may contain collections of relevant certificates. Signatures may have expiration dates, and may also require periodic re-confirmation.
Identity certificates have human-readable content. The term “certificate” is often used to denote a digitally signed statement. The best-known type of certificate is the “identity certificate” that attempts to assert a binding between an individual and his public key.
Identity certificates are often problematic, because it can be difficult to specify a name or other attributes that uniquely identify the desired individual. We feel that because of this difficulty, identity certificates must typically in the end be examined by people, to see if the name and other attributes given are consistent with the attributes known to the human reader. As a typical example, consider the problem of a security administrator who is trying to decide if a given certificate should be trusted as establishing the desired binding between some public key and some individual. We feel that human judgment is a necessary component in this process, and thus we feel that the function of an identity certificate can best be served by having the individual described by some free-form text (accompanied perhaps by a photo, and perhaps including some descriptive text describing how the given information was verified). For this reason, SDSI identity certificates may contain as little as a public key and some free-form text about the individual.
Manual process for creating identity certificates. We feel that the process of accepting another individual’s public key(s) and associating it with a local name is very important, and that it must therefore be a manual process. Judgment is required to evaluate the proposed evidence for the public-key’s owner, and to choose a meaningful local name. A typical user will not have to perform this operation very often (perhaps 5-20 times), as we shall see, because of the way name spaces can be linked.
Certificates also give name/value bindings and assert membership. SDSI certificates can also be used to bind a (local) name to a value (typically a principal), and to assert that a given principal belongs to some group. The three certificate types (identity certificate, name/value certificate, and membership certificate) have similar syntax and procedures; indeed, sometimes a single SDSI certificate can perform more than one function. SDSI certificates are also “extensible;” additional application-dependent data can be included in a certificate.
On-line Internet orientation. We assume that principals who issue certificates can provide on-line Internet service, or can arrange to provide such via a designated server. A SDSI principal may sign certificates off-line, and have a server distribute them upon request. Having such on-line capability permits considerable simplifications-for example, we eliminate “certificate revocation lists” in favor of on-line “reconfirmation.”
Linked local name spaces. SDSI does not utilize a global name space, but rather provides means for conveniently linking local name spaces. Each principal can “export” his name/value bindings to others, by issuing name/value certificates. Thus, if my local name bob refers to some principal, then I can refer to the principal that bob calls alice as
( ref: bob alice ) .
We suggest that the user interface supply a bit of syntactic sugar to represent this as
bob’s alice
Bob exports his binding by issuing a signed name/value certificate binding his local name alice to that particular principal. Bob’s server can distribute this certificate on demand.
It is not necessary to have a symbolic reference as the first argument to ref:; one can have an expression such as
( ref: <principal> alice )
where <principal> is an explicit principal (i.e., a public key, etc.). The syntactically sugared version of the above would be:
<principal>‘s alice .
However, we generally prefer the symbolic form, for clarity.
One can also have longer references, such as
bob’s alice’s mother ,
which is the syntactically sugared version of
( ref: bob alice mother ) .
This reference is well-defined (for me) if I have bound bob to some principal, who in turn has bound alice to some second principal, who in turn has bound mother to some third principal. Other examples of extended references (with syntactic sugar) are:
Visa’s account-314568901387 mit’s lcs’s rivest cmu’s eecs-dept’s search-committee’s chairman GE’s lighting-division’s vp-of-sales’s secretary’s assistant
As a detail, we note that ( ref: bob ) is equivalent to bob, since the first argument to ref: is always interpreted in the current name-space.
One can also give “symbolic definitions.” For example, my local name tim might denote mit’s Tim-Black. This means that my tim is defined to be the same principal as the one mit refers to as Tim-Black. If MIT changes the principal it calls Tim-Black then the principal I call tim changes as well. The pragmatics of how this works are described below.
To ensure that the object referenced is the intended one, one can wrap the ref: in an Assert-Hash:
( Assert-Hash: ( ref: Microsoft employee-list )
( SHA1 =hP+73N2Zr50/89jpio== ) )
This is equivalent to ref:, except that the retrieved value is hashed and compared to the given hash. An error occurs if they are not equal.
Accommodation for “standard roots” and global name spaces. We recognize that there are likely to be a set of standard “special root” principals that are “universally” recognized. These principals have SDSI reserved names ending with double exclamation marks (!!):
VeriSign!!
IAPR!! USPS!! DNS!!
There will be very few of these special roots, and their names are bound to the same principal in every name space. This is arranged with suitable procedures (appropriate publicity, manual installation, cross-checking, etc.); we do not try to describe this in more detail. This gives SDSI access to “standard” name spaces:
VeriSign!!’s MicroSoft’s Encarta-Division’s Susan-Smith DNS!!’s edu’s mit’s lcs’s theory’s Silvio-Micali USPS!!’s USA’s DOD’s DCI IAPR!!’s PCA-commerce’s DEC’s SRC’s abadi VeriSign!!’s Visa’s account-234156742
Each of these should be viewed as a global name that evaluates to the same principal in every name space, since the first name (e.g. VeriSign!!) always evaluates to the same principal, and all of the subsequent names are relative.
Although SDSI provides for special roots within a set of linked name spaces, this does not imply that each principal has a unique “global name.” A principal will have multiple global names if there are multiple paths from special roots to that principal. Thus,
VeriSign!!’s MicroSoft’s CEO DNS!!’s com’s microsoft’s "Bill Gates"
may refer to the same principal. (Of course, one can check whether these two names evaluate to give the same public key, if one wishes.)
DNS names have a special status. By special dispensation from its designers, SDSI includes custom treatment for DNS (Internet email) names, so that
Bob.Smith@penguin.microsoft.com
is equivalent to:
DNS!!’s com’s microsoft’s penguin’s Bob.Smith
-that is, to:
( ref: DNS!! com microsoft penguin Bob.Smith ) .
How this works is described later on.
Groups. A SDSI group is typically a set of principals. (The full notion is more general, and easily extends to sets of programs or web pages or other things.) Each group has a name and a set of members. The name is local to some principal, who is the “owner” of the group. The owner is the only one who may change the group definition. The definition may explicitly list the group’s members, or may define the group in terms of other groups (which may even belong to someone else).
There are good reasons why “groups” are a fundamental SDSI notion. For describing who is authorized to access certain data or to perform certain operations, it is usually simplest to define the group of authorized principals in one step, and then to place the group name on the appropriate access-control list(s) as a second step. This provides efficiency and reliability when the same group of principals is authorized on many different ACL’s. The group definition can be updated with a single modification without having to update many ACL’s. Also, the group can be given a meaningful name, so that auditing group definitions and ACL’s becomes simpler. For writing clear security implementations, it is extremely useful to refer to an authorized group of principals by an appropriate group name. Each principal can define his own groups, and export his definitions to others. Access-control lists for some resources might contain the following group names, for example.
friends mit’s biology-department’s faculty Massachusetts’s DMV’s drivers-96 john’s search-committee-members USA’s over-18
One can define a group by listing its members:
( Group: Tom Sam "Bill Gates" )
or by giving an algebraic expression in terms of the other groups or principals:
( Group: ( OR: faculty staff Bob-Smith ) )
We feel that the auditability of ACL’s specified in terms of simple group names, and the auditability of the group definitions, is very important when trying to implement an appropriate security policy.
Group membership assertions can play the roles of credentials, licenses, or ordinary paper certificates.
· An organization such as ACM can create a group members that I might refer to as acm’s members. A statement signed by acm might say that a given principal (i.e. a particular public key, not a name for that key) is a member of the group members. The “meaning” of this statement is entirely up to ACM, since it is ACM’s prerogative to define its groups any way it pleases. The definition of the group members, and the assertion that some principal is a member of it, are things that ACM may export.
· The Department of Motor Vehicles may issue certificates asserting that (the individual controlling) a specified public-key is over 18 and has a valid Massachusetts driver’s license for 1996 by issuing a signed statement that the principal is a member of DMV’s group called adult-drivers-1996.
Each such certificate also has an expiration date and other information. Membership certificates are very useful for dealing with large groups, where it is not reasonable to export the entire group definition.
Clean support for “roles”. Access control is often conveniently organized around “roles” (see Sandhu et al. [7]). SDSI supports roles in two different ways.
In the first method, an individual creates a public-key for each role he plays. Bob may create new principals (public keys) and give them appropriate names:
faculty-role bob-jones-travel-key "FudgeCo President" "Biology Department Search Committee Chair"
Bob can sign statements as the principal I call bob, or he can sign statements as the principal I would call bob’s faculty-role, and so on. I can distinguish these cases, and recognize when Bob is acting in his faculty role, as opposed to acting as Bob.
A second method by which SDSI can support roles is by having a group created for each role. The owner of the group is the principal who decides who should occupy that role. For example, a hospital administrator create a group for each role. The principal who is currently acting in that role can be made a member of that group. A hospital administrator can implement the role of head-nurse by creating a group with that name, and defining its (sole) member to be the principal of the head nurse.
These two methods differ according to who controls who is acting in the role. Also, there is no public-key for a group, so that the second method has the slight disadvantage that the principal playing that role signs with his full authority, rather than with the authority restricted to the permissions of his role.
Delegation certificates. SDSI includes the ability to delegate authority in two ways: by using groups, and by using “delegation certificates”. A delegation certificate gives the delegee the authority to sign statements of certain types on behalf of the delegator. For example, a server might have a delegation certificate allowing him to sign membership certificates on behalf of the delegator.
This concludes our brief overview of SDSI.
The following sections give some suggested details.
· Section 3 describes the common underlying data structures and syntax for SDSI, including the S-expression data structure and their representation as ASCII strings, hash values of an S-expression, dates, numbers, compression techniques, and the representation of object and message types.
· Section 4 describes some standard SDSI data types: cryptographic keys, principals (made from a public signature verification key and an internet address), encrypted objects, and signed objects (in three formats)
· Section 5 explains how each principal establishes his own local name space and how he can use certificates to export name/value bindings to other parties.
· Section 6 discusses protocols, gives the basic “query” protocol, gives the “reconfirmation” protocol, and discusses autocertificates (which can be viewed as the reply to a cryptographic “finger” operation).
· Section 7 explains the notion of a “group,” and shows how to use groups to specify authorization, how to define a group, how to determine whether a given principal is a member of some group, using the group definition and any available credentials, how to query a server to find out if a principal is a member of some remotely-defined group, and how to write ACLs in a simple manner.
· Section 8 gives examples of some typical application scenarios.
A companion paper will give precise specifications. This paper contains many suggestive details, but a fully worked-out proposal would be much lengthier. Although the first “S” in SDSI stands for “simple,” this proposal may appear complex. However, given the rather ambitious scope of its aims, we feel that it is remarkably simple.
This section presents a general syntax for representing octet-strings and lists, the data structures used by SDSI.
Our data structures are “S-expressions,” which may be:
· An octet-string: a sequence of zero or more 8-bit bytes. Each octet string may be preceded by an associated “presentation hint,” which is a sequence of 8-bit bytes surrounded by brackets. Examples of octet strings are:
"Digital Soup Kitchen" Tom-Hanks
An example of a presentation hint is
[image/gif]
·
A list of zero or more simpler
S-expressions. An example of a list is
( Algorithm: RSA-with-SHA1 ) .
This section describes how SDSI data structures can be represented in
US-ASCII for transmission or storage purposes.
Each S-expression has ASCII “external” representations for transmission or storage. Their readability may help diagnosis and auditing. These representations are not unique; one can choose maximum economy or maximum legibility. For high efficiency, there is a “verbatim” representation of octet strings, and short forms for common symbols (see Section 3.3).
SDSI representations use the US-ASCII character set; they may use alphanumeric characters, “special” printing characters:
~ ` ! @ # $ % ^ & * - _ + = { } ; : ‘ " < > [ ] , . / ? \ |
and whitespace (non-printing) characters (blanks, tabs,
newlines, carriage-returns, etc). SDSI is case-sensitive. In general, the
amount of whitespace between portions of the representation, and their
arrangement on different lines, is immaterial. We show nicely indented
structures for readability only; the indentation is not significant, and
parentheses are used for grouping.
Octet-strings are used for a variety of purposes:
· Object type names, such as Cert: .
· Attribute names, such as Date: .
·
Dates, such as 1996-02-14T11:46:05.046-0500.
· Context-specific flags, such as optional.
·
Names (such as Mary-Jones
or "Bob Smith") that
may denote principals, groups, or other SDSI objects). A name need not be an
octet-string; it may be an S-expression, such as
( ( Digital ) ( Accounting ) ( Robert Smith
) ) .
· Big numbers.
There are five external representations for variable-length octet-strings. There is no limit on the length of an octet string.
· Hexadecimal (e.g. &45facd57); this is an ampersand (&) followed by an even number of hex digits; each consecutive pair of hex digits represents one octet.
· Base-64 (e.g. =Ac0+Thj390==); this is an equals sign (=) followed by the base-64 encoding as defined in RFC-1521. This technique encodes each triple of octets with a block of four characters from the 64-character set A-Z a-z 0-9 + /. Octet-strings whose length is not a multiple of three have a representation whose last four-character block contains two or three base-64 characters and two or one equals signs as padding. The length of a base-64 encoding is thus always a multiple of four.
· A token (e.g. athena-server) is a sequence of printable (non-whitespace) characters other than parentheses, single or double quotes, square brackets, ampersands or hash marks, and which does not end with a minus sign. Decimal numbers (e.g. 45) are a subset of the tokens. A token that begins with a special character is called a “special token;” SDSI gives special treatment to some special tokens; they may not represent octet-strings at all, or may represent a different octet-string. (An example of such a case is the base-64 encodings, which start with an equals sign.)
Special tokens do not (necessarily) represent octet strings, but have special functions. At present, the only use SDSI makes of special tokens is for macros:
o Special tokens may represent macros, such as *S . Macros always start with a star * . A macro expands to an ordinary token. Note that "*S" is not a macro, and thus isn’t expanded; a macro must be represented as a special token and not as some other form of an octet string.
· Quoted strings (e.g. "Mary P. O’Connor") represent octet strings containing blanks and printable characters other than double-quotes. On input, a consecutive sequence of whitespace characters within the quotes is converted to a single blank. On output, a single blank may be converted to an arbitrary sequence of whitespace characters (e.g. carriage returns may be freely added at word breaks-these are “word-wrap strings”).
· Verbatim octet-strings, are used to transmit large octet-string most efficiently, at the cost of abandoning ASCII and human readability. They are represented by a length field, a colon, and then the octet-string verbatim. The length-field is represented as a sequence of base-256 digits, most significant digit first, with each digit preceded by a pound sign (#), and no unnecessary leading zero length digits. The result is may look something like #L:aaa or #L#L#L:aaaaaaaaaaaaa.
An octet-string may be written as a sequence of “fragments” by following each fragment but the last with a minus sign. Thus &0123- "b"- c- &0876 is the same as &012362630876. (Note that ASCII "b" is hexadecimal &62.) A long octet string can thus be fragmented for robust email transmission.
The various ways of expressing an octet-string are fully equivalent, as in the following example:
abc "abc" &616263 =YWJj&^C:abc (Here ^C denotes a single octet with value 3.)
a- b- "c"
A presentation hint (discussed further below) is represented as an octet string surrounded by square brackets. An example is [image/gif]. A presentation hint is a modifier or tag for the following octet string; it does not itself represent an octet string, but rather describes how the following octet string might best be presented to the user.
SDSI data structures may be sometimes be shown to people. In some cases, the rules above (such as those for “maximum legibility”) may be inappropriate or inadequate. For example, some data may be text in Unicode, or may represent a photo. SDSI provides “presentation hints” for handling such cases.
These hints apply to the following S-expression, which must be an octet-string. (Each octet string may be preceded by at most one such presentation hint.) Presentation hints are octet-strings surrounded by square brackets, as in:
[charset=unicode-1-1] &34518976aabcde
specifies that the
hexadecimal string &345...
represents Unicode text (see RFC 1641). In general, we propose that one can use
simple MIME Content-Types, such as
[text/richtext] [image/gif] [audio/basic] [application/postscript] [text/plain;charset=unicode-1-1]
The SDSI
specification will say which presentation hints must be supported. Multipart
MIME types are not supported. Other security-related types may be supported,
such as
[application/X.509v3]
for including X.509v3 certificates
within SDSI data structures. (Note that this is just a presentation hint for an
octet string; SDSI does not parse or give any meaning to such a certificate,
and such a certificate could be included as an octet string without any such
presentation hint.)
Presentation hints are only hints. A presentation program may ignore the hint, and present the data in some default mode. If used, the hint itself should be suppressed in the presentation; if ignored, the hint should be displayed.
A hint may be placed before any octet string. For other purposes they are effectively invisible or ignored. They should be considered as a “tag” for the following octet string, and carried around with that string. However, they do participate in hash computations.
An S-expression list can be represented in ASCII as an optional length field, a left parenthesis, an optional blank, the representations of the list elements separated by blanks, an optional final blank, and a right parenthesis. The optional length field gives the number of elements in the list in base-256, in the same format as for verbatim octet-strings (each base-256 digit preceded by a pound sign). A blank is required between two list elements only if both elements are octet-strings where the first is represented as a token, a hexadecimal value, or a base-64 value, and the second represented as a token; otherwise the separating blank is optional. On input, any sequence of white-space or non-printable characters not inside a verbatim octet-string is equivalent to a single blank. As an example of an S-expression:
( Get.Query: ( Template: ( Auto-Cert: ) ) ( Signed: ( Object-Hash: ( SHA1 &345678 ) ) ( Date: 1996-02-14T11:46:05.046-0500 ) ( Signature: &8dff4123 ) ) )
One can choose the representation of an S-expression according to the
purpose being served:
· For maximum legibility, optional blanks are always used, and octet-strings are printed in the first manner that works of: token, quoted string, or hexadecimal, and appropriate indentation is used.
· For maximum efficiency, optional blanks are never used, and the shortest possible representation of each octet string is chosen.
· For bullet-proof email transmission, fragmented base-64 encodings can be used, with line lengths limited to 76 characters.
· The “canonical” ASCII encoding of a SDSI object represents all octet-strings (including those within presentation hints) in verbatim mode. If an octet string has an associated presentation hint then the presentation hint precedes the octet-string. Lists are represented with no blanks next to parentheses or between items.
This section describes how (big) numbers, hash-values, and dates are represented as octet-strings.
Numbers. Integers are represented as an octet-string in two’s complement notation with the most-significant byte first. A number may be of any length.
Hash Values. The hash value H(S) of an S-expression S is obtained by applying a cryptographic hash algorithm, such as MD5 [6] or SHA1 [5], to S’s canonical ASCII representation. SDSI’s default hash algorithm is SHA1. A hash value is represented as a list containing the hash algorithm name and the hash value.
( SHA1 =67adhNPs8Y+/Uy34NhWp77CvULm= )
Dates and Time. Dates/times are represented as UTC time to the
millisecond, with a time-zone designation, as an octet-string in the following
format:
yyyy-mm-ddThh.mm.ss.mmm-xxzz 1996-02-14T11:46:05.046-0500
for February 14th, 1996 at 11:46:05
AM in Eastern Standard Time. Here yyyy
is the year, mm is the month, dd is the day, hh is the hour, mm
is the minutes, ss is the
seconds, mmm is milliseconds,
and xxzz is the time zone
expressed as a difference (either +
or -) of local time to UTC time
in hours (xx) and minutes (zz). This format follows the ISO 8601:1988
conventions. (However, the described format is required, with none of the
variations possible within that standard, except that the last n fields
(n < 6) and their preceding separators, may be omitted with the
understanding that the omitted items are understood to have a zero value.
Nonetheless, the full format is recommended, and signers should try to give a
distinct time to each message signed.)
This section (which should be skipped at first reading) describes compression techniques for sending SDSI data structures efficiently.
SDSI has a fairly expansive, human-readable syntax. For greater economy in transmission, SDSI has a simple “macro” capability, as well as “verbatim” encodings for octet-strings.
The form ‘<S>, for any S-expression <S>, is equivalent to the form ( Quote: <S> ).
If a special token begins with a star, then it is looked up in a fixed published standard table of substitutions. Each such special token can have some token as its defined value. For example,
*C ==> Cert:
*G ==> Get.Query:
*P ==> Principal:
*Sg ==> Signature: ...
All common SDSI tokens have such a “short form.”
Within a protocol message, the reserved macros *SENDER and *RECEIVER refer to the principal for the sender and the principal for the receiver. Thus, ( ref: *SENDER bob ) refers to the sender’s bob, while ( ref: *RECEIVER bob ) refers to receiver’s bob.
Star macros are only used for transmission. They are used to compress a message before transmission, and to decompress upon receipt. They only exist “on the wire”; they are not used for storage or presentation, and are never present when a hash computation is performed.
This section describes how lists are used to represent SDSI objects, and a particularly important kind of object: messages.
Nonempty lists are used to represent most SDSI objects. The first element (the head) of each list indicates the type of that object. The form of the rest of the list (its body), is determined by the object’s type.
SDSI has a simple type system. Basic types are indicated by a simple token. (SDSI normally ends these tokens with a colon, as in Date:). A (super-)type can also be defined as the union of other types: the type HASH-ALGORITHM might be defined as the union of types SHA1:, MD5, and RIPEMD-160, for example. Super-types are not used explicitly in SDSI, but help define its syntax. Some standard super-types are OCTET-STRING, TOKEN, ANY, PUBLIC-KEY-ALGORITHM.
The form of the body is one of three types, depending on the object type. The allowed forms are:
· An attribute/value pair. An object of this type has length exactly two. The head (the object type) can be thought of as the “attribute,” and the body contains just one element, which is the associate “value.” Here are some examples:
( Date: 1996-02-14T11:46 ) ( Ciphertext: &3487FFAB3C1022 ) ( Period: P1M ) ( SDSI-version: 1.1 )
Many SDSI objects will contain a
SDSI-version; we don’t show this attribute in our examples.
· A sequence has as a body a variable-length sequence of one or more elements, all of the same type (or super-type). Changing the order of the elements in the sequence may change the meaning of the object. Here are some examples:
( ref: tom bill mother ) ( OR: faculty staff students ) ( ACL: Ian.Fleming Q 007 Moneypenny )
·
A set has as a body of variable number
of lists representing objects of distinct basic types. That is, there may be at
most one subobject of any given type, with the exception of the subobject type Signed: which may appear multiple times.
The order of the subobjects within the object does not affect the meaning of
the object. (However, re-ordering the subobjects will affect how its hash is
computed.) Certificates are set-type objects:
( Cert: ( Signed: ( Object-Hash: ( SHA1: =78gBVKl8+94D/1QA ) ) ( Date: 1996-05-06T12:00:00 ) ( Signature: &FB47AC89001DA57798 ) ) ( Local-Name: grumpy ) ( Value: [image/gif] =3fGtHy781QhuNiVC ) )
Here the Cert: contains an subobject of type Signed:, which is also a set-type object.
The other object types illustrate (Object-Hash:,
Date:, Signature:, Local-Name:, and Value:)
are all attribute/value object types.
In general, the subobject types that may (or must) appear in the body of an object are constrained by the type of the object itself. SDSI programs should check that syntactic validity of the objects they are dealing with.
Messages are set-type objects; the type is representable as a token of the form
protocol-name.message-type:
that identifies the
type of the message transmitted during some two-party protocol. Each protocol
has a unique name, such as Get
or Electronic-Payment. Each
protocol consists of a back-forth exchange of messages, and each message has
its own name within the protocol, such as Query,
Reply, or Receipt. Thus, a message type may be
representable by a token such as:
Get.Reply: Electronic-Payment.Receipt:
A commonly used attribute in a
message might be the hash of the last message received from the other party:
( Your-Last-Message-Hash: ( SHA1 =YnK82Ab+Om0i/uBx+9ikHjdF9NV= ) )
All SDSI object-type names are “global.” Users who wish to coin new SDSI
object types are encouraged to use URL’s as unique names, to avoid conflicting
with names used by other users. The resource named may specify information
about the object type.
This section describes four standard SDSI object types: cryptographic keys, principals, encrypted objects, and signed objects.
Cryptographic keys are represented by an attribute/value object that gives the key type (one of Public-Key:, Private-Key: or Shared-Secret-Key:) with a sub set-type object whose type is the algorithm specified, and whose parts give associated parameters.
( Public-Key: ( RSA-with-SHA1: ( N: =Hi7KugV013Tv978d00vCpQ== ) ( E: &11 ) ) ) ( Private-Key: ( RSA-with-SHA1: ( N: =Hi7KugV013Tv978d00vCpQ== ) ( D: &43 ) ) ) ( Shared-Secret-Key: ( RC5-32/12/16-CBC: ( K: "ossifrage" ) ) )
Public keys are for signature verification and/or encryption (depending on
the algorithm), while private keys are for the corresponding operations of
signing and/or decryption. A public-key algorithm used for signing or signature
verification must specify a hash algorithm.
Shared secret keys can be used for encryption, decryption, or for computing MAC’s (message authentication codes). A shared secret key could be a shared password, for example. A shared secret key might also be a time-varying password (as obtained, say, from a Security Dynamics SecurID card).
This section describes the fundamental notion of a “principal,” defined in terms of a public signature verification key, and talks about simple interactions with a principal.
A SDSI principal is defined as a public signature verification key, one or more optional global names, and one or more optional internet addresses. The most important thing about a principal is its ability to verify signed statements; that is why a principal is defined in terms of its public key. We say that the principal “makes” the signed statements, even if its key is only verifying signatures made by the corresponding private key.
( Principal: ( Public-Key: ... ) ( Global-Name: ( ref: VeriSign!! WebMaster Bob-Jones ) ) ( Principal-At: "http://abc.webmaster.com/cgi-bin/sdsi-server/" ) ( Server-At: "http://xyz.webmaster.com/cgi-bin/sdsi-server/" ) )
The optional Global-Name:
field (a sequence) suggests one or more “global names” for the principal, each
starting from a SDSI special root. These names are merely suggestions as to how
one might obtain the relevant certificates if one wants to verify that the
global names are indeed correct.
The optional Principal-At: field (attribute/value) specifies an Internet address (typically as a partial URL) for the principal. Queries to the principal can be addressed there, although the principal’s servers (if any) should normally be tried first.
The optional Server-At: field (a sequence) specifies the Internet addresses of one or more “servers” who can distribute certificates and other signed statements on behalf of the principal. If more than one server is specified, it is understood that the servers are equivalent, and that a query could be addressed to any one of them. The servers should have high reliability and high on-line availability, whereas the principal may be frequently or even permanently off-line.
A server also distributes the principal’s “auto-certificate,” an object signed by the principal that gives additional information about that principal. Auto-cert service is similar to the standard “finger” service, except that the reply is a SDSI auto-certificate. We also imagine that there could be standard services similar to Alta Vista that might also be able locate an auto-cert given the public key.
Information in the principal other than the public key is considered as merely “advisory”; two principals are taken as being “the same” if and only if they have the same public key.
There are two reasons for keeping the object of type Principal: as short as possible by pushing as much information as possible into the auto-certificate:
· Information that may change should not be included in the Principal:, since a change would require re-issuing any certificates about that principal. Putting such information in the auto-cert enables it to be modified without changing any certificates other than the auto-cert itself.
· The Principal: object normally appears in every object signed by that principal, and so it is desirable to economize. Including a large GIF photo of oneself is reasonable in an auto-cert, but not in every message one signs.
Individuals who expect to utilize their Principal: object for a long time should choose their servers carefully, since reliability and longevity are critical. One needn’t specify one’s own machine as one’s server; indeed, this may be a poor choice. Organizations may provide servers for their members, or commercial services may provide servers for a fee. For short-term principals, such as many “roles”, using one’s own machine may be satisfactory.
This section describes how to represent an encrypted object within SDSI, as a list containing both a key indicator and the ciphertext.
The encryption of an object X is a set-type object whose parts indicate the encryption key (either a public key or a shared-secret key) used to encrypt the object and give the ciphertext resulting from encrypting an ASCII representation of X.
The ciphertext may be an arbitrary sequence of S-expressions; some encryption algorithms may find this convenient. For example, the IV and ciphertext can be represented as separate octet-strings.
The object type for an encrypted object is Encrypted:. An Encrypted: object should only be decrypted “as necessary” during other processing.
The encryption key is indicated by
· Giving it explicitly in a Key: (attribute/value) field:
( Encrypted: ( Key: ( Shared-Secret-Key: ... ) ) ( Ciphertext: =Yh87oKlqpBv8iY55+n== ... ) )
·
Giving its hash in a Key-Hash: (attribute/value) field:
( Encrypted: ( Key-Hash: ( SHA1 &241dc... ) ) ( Ciphertext: =Yh87oKlqpBv8iY55+n== ... ) )
·
Representing it explicitly as an encrypted
object itself:
( Encrypted: ( Key: ( Encrypted: ( Key-Hash: ( SHA1 &548... ) )( Ciphertext: &765... ) ) )
( Ciphertext: &345... ) )
Here &765... denotes the encryption of the message key by an
encryption key (public or shared-secret) with hash &548..., and &345...
is the encryption of the message object with the message key.
· Giving a ( ref: ... ) expression that evaluates to the key.
( Encrypted: ( Key: ( ref: *SENDER key-49 ) ) ( Ciphertext: ... ) )
Here the *SENDER macro is used.
In the last example, one way that the receiver might know what value the sender has for key49 is that the sender might previously have sent him an Encrypted: certificate including the definition:
( Cert: ( Local-Name: key-49 ) ( Value: ( Shared-Secret-Key: RC5 ... ) ) ( Signed: ... ) )
This section describes how to represent signed objects with three signature formats (wrapped-hash, wrapped-object, and signature appendix), and shows how to transform between these formats without performing cryptographic operations. It also shows objects can be “co-signed;” with either parallel co-signatures or cascaded co-signatures.
A signed object can be signed in either “wrapped” mode (where the signed-object contains the object being signed or its hash) or in “appendix” mode (where the signature is typically appended to the end of the signed object). One can creat cascaded co-signatures (in either mode) and parallel co-signatures (in appendix mode only).
In any case a signature is represented by a set-type object of type Signed:. An example of a minimal object of type Signed: is shown below:
( Signed: ( Object-Hash: ( SHA1: =7Yhd0mNcGFE071QTzXsap+q/uhb= ) ) ( Date: 1996-02-14T11:46:05.046-0500 ) ( Signature: &3421197655f0021cdd8acb21866b ) )
Such an object, by itself, is said to be a signature in
“wrapped-hash” format.
The mandatory Object-Hash: (attribute/value) field specifies the hash of the object being signed. An arbitrary set-type object may be signed, although this paper only talks about signed certificates or messages.
The mandatory Date: (attribute/value) field gives the (effective) date of signing. There is of course nothing to prevent a signer from pre-dating or post-dating his signatures.
The mandatory Signature: field (a sequence) gives the output produced by the signature algorithm, which can be an arbitrary sequence of S-expressions, obtained by hashing the entire Signed object, except for any subobjects of type Signature: or Object:, and then applying the signature algorithm to the result.
We now describe the optional fields for a Signed: object.
( Object: ... )
The optional Object:
(attribute/value) field explicitly gives the object being signed, whose hash is
given in the Object-Hash: field.
(The signature verification procedure must check this.) When this field is
included, the Signed: object is
said to be in “wrapped-object” format. This field is not hashed by the
signature algorithm, since its hash is already given in the (mandatory) Object-Hash: field, which is
hashed by the signature algorithm. This convention also enables transforming
between different signature formats, as described below, because the Object: field can be removed while leaving
the signature valid.
( Expiration-Date: 2000-01-01-00:00:00.000-0500 )
The optional Expiration-Date:
(attribute/value) field gives the date after which the signature is no longer
valid (even if reconfirmed by a server).
( Signer: ( Principal: ... ) )
This optional Signer:
(attribute/value) field specifies the signing principal. This field must be
included whenever the signed object might later be used in a context where it
is not obvious who the signer is, or if the signature requires periodic
reconfirmation. This field should be in the first signed message sent by each
party in a protocol, and may be omitted thereafter except for messages (such as
membership certificates) that will be kept around after the protocol.
( Signing-Key-Hash: ( SHA1: &7613445... ) )
The optional Signing-Key-Hash:
(attribute/value) field is used when the signature (here a MAC) is created with
a shared secret authentication key; it specifies the hash of the shared secret
key.
( Credentials: ... )
The optional Credentials:
field (a sequence) lists various “credentials” of the signer. These take the
form of certificates that may help to establish that the signer has the
appropriate authorizations, such as what might be needed to access data that is
restricted by an access-control list.
( Signing-For: ( Principal: ... ) )
The optional Signing-For:
(attribute/value) field is used when the signer is signing on behalf of someone
else. The most common situation occurs when a server is signing something (such
as a membership certificate) on behalf of a principal. When this field is
present there must also be a Credentials:
field present that demonstrates that the signer indeed has the authorization
necessary to sign for the other party.
( Re-confirm: ( Period: P1M ) ( Principal: ... ) )
The optional Re-confirm:
(set-type) field specifies that reconfirmation is required, and gives details.
In this example, this field says that one must periodically “re-confirm” the
signature every month. The period is specified according to ISO 8601:1988
format for periods without start or end. This begins with a P, followed by an optional time-period
indicated as so many years (Y), months (M), weeks (W), days (D), optionally
followed by a T, followed by so
many hours (H), minutes (M), and/or seconds (S). Thus, PT8H says that reconfirmation is required
every 8 hours, and P6WT4H3M says
that reconfirmation is required after 6 weeks, 4 hours, and 3 minutes. A
signature needs to be reconfirmed if its date (or the date of its last
reconfirmation) is more than re-confirmation period old.
The next optional value within the Re-confirm: field is the “reconfirmation principal,” given if different than the signing principal. (It might typically be a server.) Section 6.2 describes reconfirmation procedures.
An object of type Signed: by itself is a “wrapped” form of the signed object. It may or may not explicitly contain the object X being signed. In either case the hash of X is given. If X is also explicitly given, we say that the signature is in “wrapped-object” form. If only the hash of X is given, we say that it is in “wrapped-hash” form.
A signature in wrapped-object form can be “unwrapped” and converted into two objects: the object X itself and a Signed: object in wrapped-hash form that contains only the hash of X. Because the signature algorithm produces the same result whether or not the Object: field is present, this unwrapping operation does not require any cryptographic operations.
An object of type Signed: can be therefore be detached and managed separately (in wrapped-hash form) from the object itself. Many applications require this capability.
An S-expression that is a set-type object admits another signature format, which we call an appendix-mode signature. To create such a format the Signed: object in wrapped-hash form is added as an appendix to the end of the set-type object being signed, as in:
( Get.Query: ( Template: ( Auto-Cert: ) ) ( Signed: ( Object-Hash: ( SHA1: &345678 ) ) ( Date: 1996-02-14T11:46:05.046-0500 )( Signature: &8dff4123 ) ) )
Verifying the signature thus requires first removing the Signed: field in order to compute the hash
of the original list. (We note that the signature need not actually be at the
end, because a set-type object can have its subobjects in arbitrary order.)
Appendix mode is the “standard” signature mode for SDSI objects and messages because it is the only mode that also allows co-signatures. However, there there is no appendix format for signing octet-strings, so wrapped mode is mandatory for applications that must sign octet-strings representing word-processing documents, executable binary files, etc.
Because of the way the signature algorithm is defined, one can also transform easily between a wrapped-object form of a signed set-type object X and the appendix form of the signed object X. This requires only simple re-arrangement; no cryptographic operations are required. Thus
( Signed: ( Object-Hash: ( SHA1: &345678 ) ) ( Object: ( Get.Query: ( Template: ( Auto-Cert: ) ) ) ) ( Date: 1996-02-14T11:46:05.046-0500 ) ( Signature: &8dff4123 ) )
is equivalent to the previous example.
A set-type object can have more than one signature appendix; these are “parallel co-signatures” that sign everything except the other signature(s). Parallel co-signatures are the result of two or more signers independently signing an object, and appending their independent signatures to the end of the object.
( Get.Query: ( Template: ( Auto-Cert: ) ) ( Signed: ( Object-Hash: ( SHA1: &345678 ) ) ( Date: 1996-02-14T11:46:05.046-0500 ) ( Signer: ( Principal: ( Global-Name: VeriSign!!’s "Bob" ) ... ) ) ( Signature: &8dff4123 ) )( Signed:
( Object-Hash: ( SHA1: &345678 ) ) ( Date: 1996-03-19T07:00:11.341-0500 ) ( Signer: ( Principal: ( Global-Name: VeriSign!!’s "Alice" ) ... ) ) ( Signature: &a78300b3 ) ) )
Another form of multiple signature is the “cascaded co-signature” obtained
by adding a signature to the end of a Signed:
object. Cascaded co-signatures are cumulative; they effectively sign all
previous material. A cascaded co-signature is what you get if you sign the Signed: object at the end of a previously
signed list.
( Get.Query: ( Template: ( Auto-Cert: ) ) ( Signed: ( Object-Hash: ( SHA1: &345678 ) ) ( Date: 1996-02-14T11:46:05.046-0500 ) ( Signer: ( Principal: ( Global-Name: VeriSign!!’s "Bob" ) ... ) ) ( Signature: &8dff4123 ) ( Signed: ( Object-Hash: ( SHA1: &86731b ) ) ( Date: 1996-03-19T07:00:11.341-0500 ) ( Signer: ( Principal: ( Global-Name: VeriSign!!’s "Alice" ) ... ) )( Signature: &7830ca12 ) ) )
Because the second Signed:
object contains the hash ( SHA1 &86731b
) of the first Signed:
object, and the first Signed:
object contains the hash ( SHA1: &345678
) of the enclosing S-expression, Alice’s second signature effectively
signs both the original S-expression (
Get.Query: ... ) and Bob’s first signature. One can have cascaded
co-signatures in either wrapped or appendix mode.
An application of cascaded co-signatures is digital time-stamping, where the second signature provides evidence that the first signature had already been created at the time the second signature was applied.
Another use would be where an application program running on behalf of a principal signs the signature created by the principal, so that the server knows that the request not only came from an authorized principal, but from an authorized principal running the correct program.
This section describes how each principal may define his own local name space, and how he may issue certificates to export his local name/value bindings.
Each principal has its own local name-space.
A name may be represented in one of two ways: