Internet-Draft | SPKI S-Expressions | October 2024 |
Rivest & Eastlake | Expires 24 April 2025 | [Page] |
This memo specifies the data structure representation that was devised in 1996/1997 to support SPKI (RFC 2692) certificates with the intent that it be more widely applicable. It has been and is being used elsewhere. There are multiple implementations in a variety of programming languages. Uses of this representation are referred to in this document as "S-expressions". This memo makes precise the encodings of these SPKI S-expressions: it gives a "canonical form" for them, describes two "transport" representations, and also describe an "advanced" format for display to people.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
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."¶
This Internet-Draft will expire on 24 April 2025.¶
Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
This memo specifies the data structure representation that was devised in 1996/1997 to support SPKI [RFC2692] certificates with the intent that it be more widely applicable (see Section 1.3, History). It is suitable for representing arbitrary, complex data structures and has been and is being used elsewhere. Uses of this representation herein are referred to as "S-expressions".¶
This memo makes precise the encodings of these SPKI S-expressions: it gives a "canonical form" for them, describes two "transport" representations, and also describe an "advanced" format for display to people. There are multiple implementations of S-expressions in a variety of programming languages including Python, Ruby, and C (see Appendix A).¶
These S-expressions are either byte-strings ("octet-strings") or lists of simpler S-expressions. Here is a sample S-expression:¶
(snicker "abc" (#03# |YWJj|))¶
It is a list of length three containing the following:¶
This document specifies how to construct and use these S-expressions.¶
The design goals for S-expressions were as follows:¶
Implementors of new applications and protocols may wish to consider potential alternative representations to SPKI S-expressions such as [XML], CBOR [RFC8949], or JSON [RFC7159].¶
The S-expressions specified herein are in active use today between GnuPG [GnuPG] and Ribose's RNP [Ribose]. Ribose has implemented C++ software to compose and parse these S-expressions [RNPGP_SEXPP]. The GNU software is here [Libgcrypt] and there are other implementations (see Appendix A).¶
They are used or referenced in the following RFCs:¶
In addition, S-Expressions are the inspiration for the encodings in other protocols. For example, [RFC3259] or Section 6 of [CDDLfreezer].¶
An Internet Draft [formal] has been posted showing a formal model of SPKI S-Expressions and which formally demonstrates that the examples and ABNF in this document are correct.¶
The S-expressions described here were originally developed for "SDSI" (the Simple Distributed Security Infrastructure by Lampson and Rivest [SDSI]) in 1996, although their origins date back to McCarthy's [LISP] programming language. They were further refined and improved during the merger of SDSI and SPKI [SPKI] [RFC2692] [RFC2693] during the first half of 1997. S-expressions are more readable and flexible than, Bernstein's "net-strings" [BERN], which were developed contemporaneously.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
Informally, an S-expression is either:¶
An octet-string is a finite sequence of eight-bit octets. There may be many different but equivalent ways of representing an octet-string¶
abc -- as a token "abc" -- as a quoted string #616263# -- as a hexadecimal string 3:abc -- as a length-prefixed "verbatim" encoding |YWJj| -- as a base-64 encoding of the octet-string "abc" {MzphYmM=} -- as a base-64 encoding of the verbatim encoding (that is, an encoding of "3:abc")¶
The above encodings are all equivalent in that they all denote the same octet-string.¶
Details of these encodings are given below, and how to give a "display type" to a simple-string is also described in Section 4.6.¶
A list is a finite sequence of zero or more simpler S-expressions. A list is represented by using parentheses to surround the sequence of encodings of its elements, as in:¶
(abc (de #6667#) "ghi jkl")¶
As can be seen, there is variability possible in the encoding of an S-expression. In some applications, it is desirable to standardize or restrict the encodings; in other cases, it is desirable to have no restrictions. The following are the target cases these S-expressions aim to handle:¶
In this document, related encoding techniques for each of these uses are provided.¶
This document specifies encodings of S-expressions. Except when giving "verbatim" encodings, the character set used is limited to the following characters in ASCII [RFC0020]:¶
A B ... Z a b ... z¶
0 1 ... 9¶
space, horizontal tab, vertical tab, form-feed carriage-return, line-feed¶
- hyphen or minus . period / slash _ underscore : colon * asterisk + plus = equal¶
( left parenthesis ) right parenthesis [ left bracket ] right bracket { left brace } right brace | vertical bar # number sign " double quote & ampersand \ backslash¶
! exclamation point % percent ^ circumflex ~ tilde ; semicolon ' apostrophe , comma < less than > greater than ? question mark¶
This section describes in detail the ways in which an octet-string may be represented.¶
Recall that an octet-string is any finite sequence of octets, and that the octet-string may have length zero.¶
A verbatim encoding of an octet-string consists of three parts:¶
There are no blanks or whitespace separating the parts. No "escape sequences" are interpreted in the octet-string. This encoding is also called a "binary" or "raw" encoding.¶
Here are some sample verbatim encodings:¶
3:abc 7:subject 4::::: 12:hello world! 10:abcdefghij 0:¶
The quoted-string representation of an octet-string consists of:¶
The specified length is the length of the resulting string after any backslash escape sequences have been converted to the octet value they denote. The string does not have any "terminating NULL" that [C] includes, and the length does not count such an octet.¶
The length is optional.¶
The escape conventions within the quoted string are as follows (these follow the "C" [C] programming language conventions, with an extension for ignoring line terminators of just CR, LF, CRLF, or LFCR and more restrictive octal and hexadecimal value formats):¶
\a -- audible alert (bell) \b -- backspace \t -- horizontal tab \v -- vertical tab \n -- new-line \f -- form-feed \r -- carriage-return \" -- double-quote \' -- single-quote \? -- question mark \\ -- back-slash \ooo -- character with octal value ooo (all three digits MUST be present) \xhh -- character with hexadecimal value hh (both digits MUST be present) \<carriage-return> -- causes carriage-return to be ignored. \<line-feed> -- causes linefeed to be ignored. \<carriage-return><line-feed> -- causes CRLF to be ignored. \<line-feed><carriage-return> -- causes LFCR to be ignored.¶
Here are some examples of quoted-string encodings:¶
"subject" "hi there" 7"subject" "\xFE is the same octet as \376" 3"\n\n\n" "This has\n two lines." "This has \ one line." ""¶
An octet-string that meets the following conditions may be given directly as a "token":¶
Note: Upper and lower case are not equivalent. A token may begin with punctuation, including ":".¶
Here are some examples of token representations:¶
subject not-before :=.. class-of-1997 //microsoft.com/names/smith *¶
An octet-string may be represented with a hexadecimal encoding consisting of:¶
There may be whitespace inserted in the midst of the hexadecimal encoding arbitrarily; it is ignored. It is an error to have characters other than whitespace and hexadecimal digits.¶
Here are some examples of hexadecimal encodings:¶
#616263# -- represents "abc" 3#616263# -- also represents "abc" # 616 263 # -- also represents "abc" ## -- represents the zero-length string¶
An octet-string may be represented in a base-64 encoding [RFC4648] consisting of:¶
Base-64 encoding produces four characters of output for each three octets of input. If the length of the input divided by three leaves a remainder of one or two, it produces an output block of length four ending in two or one equals signs, respectively. These equals signs MUST be included on output but input routines MAY accept inputs where one or two equals signs are dropped.¶
Whitespace inserted in the midst of the base-64 encoding is ignored. It is an error to have characters other than whitespace and base-64 characters.¶
Here are some examples of base-64 encodings:¶
|YWJj| -- represents "abc" | Y W J j | -- also represents "abc" 3|YWJj| -- also represents "abc" |YWJjZA==| -- represents "abcd" |YWJjZA| -- also represents "abcd" || -- represents the zero-length string¶
Note the difference between this base-64 encoding of an octet-string using vertical bars ("| |") and the base-64 encoding of an S-expression using curly braces ("{ }") in Section 6.1.¶
The purposes of a display-hint is to provide information on how to display an octet-string to a user. It has no other function. Many of the MIME [RFC2046] types work here.¶
A display-hint is an octet-string representation surrounded by square brackets. There may be whitespace separating the display hint octet-string from the surrounding brackets. Any of the legal octet-string representations may be used for the display-hint string but a display-hint may not be applied to a display-hint string, that is, display-hints may not be nested.¶
Every octet-string representation is either preceded by a single display-hint or not so preceded. There may be white space between the close square bracket and the octet-string to which the hint applies.¶
Here are some examples of display-hints:¶
[image/gif] [charset=unicode-1-1] [ text/richtext ] ["text/plain; charset=iso-8859-1"] [application/postscript] [application/octet-stream] [audio/basic] ["http://example.com/display-types/funky.html"]¶
An octet-string that has no display-hint may be considered to have a MIME [RFC2046] type specified by the application or use. In the absence of such a specification, the default is as follows:¶
"text/plain; charset=iso-8859-1"¶
When an S-Expression is being encoded in one of the representations described in Section 6, any display-hint present is included. If a display-hint is the default, it is not suppressed nor is the default display-hint included in the representation for an octet-string without a display-hint.¶
It is RECOMMENDED that two octet-strings be considered equivalent for most computational and algorithmic purposes if and only if they have the same display-hint and the same data octet-strings. However, a particular application might need a different criterion. For example, it might ignore the display hint on comparisons.¶
Note that octet-strings are "case-sensitive"; the octet-string "abc" is not equal to the octet-string "ABC".¶
An octet-string without a display-hint may be compared to another octet-string (with or without a display hint) by considering it as an octet-string with the default display-hint specified for the applications or, in the absence of such specification, the general default display-hint specified in Section 4.6 .¶
Just as with octet-strings, there are variations in representing a list. Whitespace may be used to separate list elements, but they are only required to separate two octet-strings when otherwise the two octet-strings might be interpreted as one, as when one token follows another. To be precise, an octet-string represented as a token (Section 4.3) MUST be separated by white space from a following token, verbatim representation, or any of the following if they are prefixed with a length: quoted-string, hexadecimal, or base-64 representation. Also, whitespace may follow the initial left parenthesis, or precede the final right parenthesis of a list.¶
Here are some examples of encodings of lists:¶
(a bob c) ( a ( bob c ) ( ( d e ) ( e f ) ) ) (11:certificate(6:issuer3:bob)(7:subject5:alice)) ({ODpFeGFtcGxlIQ==} "1997" murphy 3:XC+) ()¶
There are three "types" of representation:¶
The first two MUST be supported by any implementation; the last is OPTIONAL. As part of both basic and advanced transport representations, the base-64 [RFC4648] representation of an S-expression may be used as described in Section 6.1.¶
An S-expression may be represented in a base-64 encoding [RFC4648] consisting of:¶
Base-64 encoding produces four characters of output for each three octets of input. If the length of the input divided by three leaves a remainder of one or two, it produces an output block of length four ending in two or one equals signs, respectively. These equals signs MUST be included on output but input routines MAY accept inputs where one or two equals signs are dropped.¶
Whitespace inserted in the midst of the base-64 encoding, after the opening curly brace, or before the closing curly brace is ignored. It is an error to have characters other than whitespace and base-64 characters.¶
Note the difference between this base-64 encoding of an S-expression using curly braces ("{ }") and the base-64 encoding of an octet-string using vertical bars ("| |") in Section 4.5.¶
This canonical representation is used for digital signature purposes and transport over channels not sensitive to specific octet values. It is uniquely defined for each S-expression. It is not particularly readable, but that is not the point. It is intended to be very easy to parse, to be reasonably economical, and to be unique for any S-expression. (See [CANON].)¶
The "canonical" form of an S-expression represents each octet-string in verbatim mode, and represents each list with no blanks separating elements from each other or from the surrounding parentheses (see also Section 7.2).¶
Here are some examples of canonical representations of S-expressions:¶
(6:issuer3:bob) (4:icon[12:image/bitmap]9:xxxxxxxxx) (7:subject(3:ref5:alice6:mother)) 10:foo)]}>bar 0:¶
There are two forms of the "basic transport" representation:¶
The basic transport representations (see Section 7.3) are intended to provide a universal means of representing S-expressions for transport from one machine to another. The base-64 encoding would be appropriate if the channel over which the S-expression is being sent might be sensitive to octets of some special values, such as an octet of all zero bits (NULL) or an octet of all one bits (DEL), or the channel is sensitive to "line length" such that occasional line terminating white space is needed.¶
Here are two examples of an S-expression represented in basic transport mode:¶
(1:a1:b1:c) {KDE6YTE6YjE 6YykK }¶
The second example above is the same S-expression as the first encoded in base-64.¶
The "advanced transport" representation is intended to provide more flexible and readable notations for documentation, design, debugging, and (in some cases) user interface.¶
The advanced transport representation allows all of the octet-string representation forms described above in Section 4: quoted strings, base-64, hexadecimal, tokens, representations of strings with omitted lengths, and so on. It also allows use of the base-64 representation of S-expressions. (See Section 7.1).¶
ABNF is the Augmented Backus-Naur Form for syntax specifications as defined in [RFC5234]. The ABNF for advanced representation of S-expressions is given first and the basic and canonical forms derived therefrom. The rule names below in all caps are defined in Appendix B.1 of [RFC5234].¶
sexp = *whitespace value *whitespace whitespace = SP / HTAB / vtab / CR / LF / ff vtab = %x0B ; vertical tab ff = %x0C ; form feed value = string / ("(" *(value / whitespace) ")") string = [display] *whitespace simple-string display = "[" *whitespace display-string *whitespace "]" display-string = verbatim / quoted-string / token / hexadecimal / base-64 verbatim = decimal ":" *OCTET ; the length followed by a colon and the exact ; number of OCTETs indicated by the length decimal = %x30 / (%x31-39 *DIGIT) quoted-string = [decimal] DQUOTE *(printable / escaped) DQUOTE printable = %x20-21 / %x23-5B / %x5D-7E ; All US-ASCII printable but double-quote and ; backslash escaped = backslash (%x3F / %x61 / %x62 / %x66 / %x6E / %x72 / %x74 / %x76 / DQUOTE / quote / backslash / 3(%x30-37) / (%x78 2HEXDIG) / CR / LF / (CR LF) / (LF CR)) backslash = %x5C quote = %x27 ; single quote token = (ALPHA / simple-punc) *(ALPHA / DIGIT / simple-punc) simple-punc = "-" / "." / "/" / "_" / ":" / "*" / "+" / "=" hexadecimal = [decimal] "#" *whitespace *hexadecimals "#" hexadecimals = 2(HEXDIG *whitespace) base-64 = [decimal] "|" *whitespace *base-64-chars [base-64-end] "|" base-64-chars = 4(base-64-char *whitespace) base-64-char = ALPHA / DIGIT / "+" / "/" base-64-end = base-64-chars / 3(base-64-char *whitespace) ["=" *whitespace] / 2(base-64-char *whitespace) *2("=" *whitespace) simple-string = verbatim / quoted-string / token / hexadecimal / base-64 / base-64-raw base-64-raw = "{" *whitespace *base-64-chars base-64-end "}" ; encodes an sexp, which has a minimum ; length of 2¶
c-sexp = c-string / ("(" *c-sexp ")") c-string = [ "[" verbatim "]" ] verbatim¶
b-sexp = c-sexp / b-base-64 b-base-64 = "{" *whitespace *base-64-chars base-64-end "}" ; encodes a c-sexp, which has a minimum ; length of 2¶
This document has described S-expressions in general form. Applications may wish to restrict their use of S-expressions in various ways as well as to specify a different default display-hint. Here are some possible restrictions that might be considered:¶
As provided in Section 6, conformant implementations will support canonical and basic representation but support for advanced representation is not generally required. Thus advanced representation can only be used in applications which mandate its support or where a capability discovery mechanism indicates support.¶
For processing, the S-expression would typically be parsed and represented in memory in a way that is more amenable to efficient processing. This document suggests two alternatives:¶
These are only sketched here, as they are only suggestive. The [SexpCode] code illustrates these styles in more detail.¶
Here there are separate records for simple-strings, strings, and lists or list nodes. An S-expression of the form ("abc" "de") could be encoded as two records for the simple-strings, two for the strings, and two for the list elements, where a record is a relatively small block of memory and, except for simple-string, might have pointers in it to other records. This is a fairly conventional representation as discussed in Section 4 of [LISP2].¶
Here each S-expression is represented as a contiguous array of octets. The first octet codes the "type" of the S-expression:¶
01 octet-string 02 octet-string with display-hint 03 beginning of list (and 00 is used for "end of list")¶
Each of the three types is immediately followed by a k-octet integer indicating the size (in octets) of the following representation. Here k is an integer that depends on the implementation, it might be anywhere from 2 to 8, but would be fixed for a given implementation; it determines the size of the objects that can be handled. The transport and canonical representations are independent of the choice of k made by the implementation.¶
Although the lengths of lists are not given in the usual S-expression notations, it is easy to fill them in when parsing; when you reach a right-parenthesis you know how long the list representation was, and where to go back to fill in the missing length.¶
This is represented as follows:¶
01 <length> <octet-string>¶
For example (here k = 2)¶
01 0003 a b c¶
This is represented as follows:¶
02 <length> 01 <length> <octet-string> /* for display-type */ 01 <length> <octet-string> /* for octet-string */¶
For example, the S-expression¶
[gif] #61626364#¶
would be represented as (with k = 2)¶
02 000d 01 0003 g i f 01 0004 61 62 63 64¶
This is represented as¶
03 <length> <item1> <item2> <item3> ... <item> 00¶
For example, the list (abc [d]ef (g)) is represented in memory as (with k = 2)¶
03 001b 01 0003 a b c 02 0009 01 0001 d 01 0002 e f 03 0005 01 0001 g 00 00¶
As a pure data representation format, there are few security considerations to S-expressions. A canonical form is required for the consistent creation and verification of digital signatures. This is provided in Section 6.2.¶
The default display-hint (see Section 4.6) can be specified for an application. Note that if S-expressions containing untyped octet-strings represented for that application are processed by a different application, those untyped octet-string may be treated as if they had a different display-hint.¶
This document requires no IANA actions.¶
At this time there are multiple implementations, many open source, available that are intended to read and parse some or all of the various S-expression formats specified here. In particular, see the following likely incomplete list:¶
RFC Editor Note: Please delete this section before publication.¶
This sub-section summarizes significant changes between the original 1997 -00 version of this document and the 2023 -00 version submitted to the IETF.¶
Trivial keep-alive update.¶
Minor ABNF fixes.¶
Special thanks to Daniel K. Gillmore for his extensive comments.¶
The comments and suggestions of the following are gratefully acknowledged: John Klensin and Caleb Malchik.¶
Special thanks to Marc Petit-Huguenin, particularly for his extensive work and advice on the ABNF and on locating and fixing unclear parts of earlier versions of this document:¶