HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 12:16:19 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Fri, 25 Jul 1997 13:53:00 GMT ETag: "3ddc76-d373-33d8afbc" Accept-Ranges: bytes Content-Length: 54131 Connection: close Content-Type: text/plain Network Working Group Tatu Ylonen 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 [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 [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 [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 [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 [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, "myhash@ssh.fi" 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 [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 "( 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. "( 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 [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 [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 foo@ssh.fi by N.N"; instead it can only say "it is an unknown object of type foo@ssh.fi". 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 [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 [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 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 ; 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 [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 [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 [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 [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 [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 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 [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 [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 [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 [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: "user@domain.name:algorithms", with the same wildcard conventions as for host keys (except that the '@' and ':' signs cannot be matched by Tatu Ylonen [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 "ylo@ssh.fi:*"), 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 [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 ************ ***** END OF SPKI CERTIFICATE DATA ***** An object sequence containing only certificates and signatures is represented as ***** SPKI SIGNATURE DATA ************ ***** 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 ********************** ***** 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 *********** ***** SPKI SIGNATURE DATA ************ ***** 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 [page 22]