Network Working Group R. Rivest Internet-Draft MIT CSAIL Intended status: Informational D. Eastlake Expires: 17 October 2024 Independent 15 April 2024 SPKI S-Expressions draft-rivest-sexp-06 Abstract This memo specifies a data structure representation that is suitable for representing arbitrary, complex data structures. It was devised in 1996/1997 to support SPKI (RFC 2692) certificates with the intent that it be more widely spplicable and has been used elsewhere. There are many implementations in a variety of languages. Uses of this representation herein are referred to as "S-expressions". This memo make precise the encodings of these S-expressions: it gives a "canonical form" for them, describes two "transport" representations, and also describe an "advanced" format for display to people. Status of This Memo 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 17 October 2024. Copyright Notice 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 Rivest & Eastlake Expires 17 October 2024 [Page 1] Internet-Draft SPKI S-Expressions April 2024 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. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Historical Note . . . . . . . . . . . . . . . . . . . . . 4 1.2. Uses of S-Expressions . . . . . . . . . . . . . . . . . . 4 1.3. Conventions Used in This Document . . . . . . . . . . . . 5 2. S-expressions -- informal introduction . . . . . . . . . . . 5 3. Character set . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Octet string representations . . . . . . . . . . . . . . . . 7 4.1. Verbatim representation . . . . . . . . . . . . . . . . . 7 4.2. Quoted-string representation . . . . . . . . . . . . . . 8 4.3. Token representation . . . . . . . . . . . . . . . . . . 9 4.4. Hexadecimal representation . . . . . . . . . . . . . . . 10 4.5. Base-64 representation . . . . . . . . . . . . . . . . . 10 4.6. Display hint . . . . . . . . . . . . . . . . . . . . . . 11 4.7. Equality of octet-strings . . . . . . . . . . . . . . . . 12 5. Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6. Representation types . . . . . . . . . . . . . . . . . . . . 12 6.1. Canonical representation . . . . . . . . . . . . . . . . 13 6.2. Basic transport representation . . . . . . . . . . . . . 13 6.3. Advanced transport representation . . . . . . . . . . . . 14 7. ABNF for syntax . . . . . . . . . . . . . . . . . . . . . . . 14 7.1. ABNF for canonical transport . . . . . . . . . . . . . . 14 7.2. ABNF for basic transport . . . . . . . . . . . . . . . . 14 7.3. ABNF for advanced transport . . . . . . . . . . . . . . . 15 8. In-memory representations . . . . . . . . . . . . . . . . . . 16 8.1. List-structure memory representation . . . . . . . . . . 16 8.2. Array-layout memory representation . . . . . . . . . . . 17 8.2.1. Octet string . . . . . . . . . . . . . . . . . . . . 18 8.2.2. Octet-string with display-hint . . . . . . . . . . . 18 8.2.3. List . . . . . . . . . . . . . . . . . . . . . . . . 18 9. Restricted S-expressions . . . . . . . . . . . . . . . . . . 19 10. Security Considerations . . . . . . . . . . . . . . . . . . . 19 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 12. Normative References . . . . . . . . . . . . . . . . . . . . 20 13. Informative References . . . . . . . . . . . . . . . . . . . 20 Appendix A. Implementations . . . . . . . . . . . . . . . . . . 22 Appendix B. Change History . . . . . . . . . . . . . . . . . . . 23 B.1. -00 Changes . . . . . . . . . . . . . . . . . . . . . . . 23 B.2. Changes from -00 to -01 . . . . . . . . . . . . . . . . . 23 B.3. Changes from -01 to -02 . . . . . . . . . . . . . . . . . 24 B.4. Changes from -02 to -03 . . . . . . . . . . . . . . . . . 24 B.5. Changes from -03 to -04 . . . . . . . . . . . . . . . . . 24 Rivest & Eastlake Expires 17 October 2024 [Page 2] Internet-Draft SPKI S-Expressions April 2024 B.6. Changes from -04 to -05 . . . . . . . . . . . . . . . . . 24 B.7. Changes from -05 to -06 . . . . . . . . . . . . . . . . . 24 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 25 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25 1. Introduction This memo specifies a data structure representation that is suitable for representing arbitrary, complex data structures. It was devised in 1996/1997 to support SPKI [RFC2692] certificates with the intent that it be more widely spplicable (see Section 1.1, History) and has been used elsewhere. Uses of this representation herein are referred to as "S-expressions". This memo make precise the encodings of these 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 many implementations of S-expression in a variety of 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: * the octet-string "snicker" * the octet-string "abc" * a sub-list containing two elements: the hexadecimal constant #03# (i.e., 0x03) and the base-64 constant |YWJj| (which is the same as "abc") This document specifies how to construct and use these S-expressions. They are independent of any particular application. The design goals for S-expressions were as follows: generality: S-expressions should be good at representing arbitrary data. readability: It should be easy for someone to examine and understand the structure of an S-expression. economy: S-expressions should represent data compactly. Rivest & Eastlake Expires 17 October 2024 [Page 3] Internet-Draft SPKI S-Expressions April 2024 tranportability: S-expressions should be easy to transport over communication media (such as email) that are known to be less than perfect. flexibility: S-expressions should make it relatively simple to modify and extend data structures. canonicalization: It should be easy to produce a unique "canonical" form of an S-expression, for digital signature purposes. efficiency: S-expressions should admit in-memory representations that allow efficient processing. Section 1.1 below has notes of this history of this document. Section 1.2 describes some current uses. Implementors of new applications/protocols should consider representations such as CBOR [RFC8949], JSON [RFC7159], and [XML] as potential alternatives to S-expressions. 1.1. Historical Note The S-expression technology described here was originally developed for "SDSI" (the Simple Distributed Security Infrastructure by Lampson and Rivest [SDSI]) in 1996, although the origins clearly date back to McCarthy's [LISP] programming language. It was further refined and improved during the merger of SDSI and SPKI [SPKI] [RFC2692] [RFC2693] during the first half of 1997. S-expressions are similar to, but more readable and flexible than, Bernstein's "net-strings" [BERN]. | Although made publicly available as a file named draft-rivest- | sexp-00.txt on 4 May 1997, that file was never actually | submitted to the IETF. This document is a modernized and more | polished version of that document. 1.2. Uses of S-Expressions 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/referenced in the following RFCs: * [RFC3275] XML-Signature Syntax and Processing Rivest & Eastlake Expires 17 October 2024 [Page 4] Internet-Draft SPKI S-Expressions April 2024 * [RFC2693] for [SPKI] In addition, S-Expressions are the inspiration for the encodings in other protocols. For example, Section 6 of [CDDLfreezer] or [RFC3259]. 1.3. Conventions Used in This Document 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. 2. S-expressions -- informal introduction Informally, an S-expression is either: * an octet-string, or * a finite list of simpler S-expressions. 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 {MzphYmM=} -- as a base-64 encoding of the verbatim encoding (that is, an encoding of "3:abc") |YWJj| -- as a base-64 encoding of the octet-string "abc" The above encodings are all equivalent; they all denote the same octet string. Details of these encodings are given later on, and how to give a "display type" to a simple-string is also described. 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") Rivest & Eastlake Expires 17 October 2024 [Page 5] Internet-Draft SPKI S-Expressions April 2024 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: * a "transport" or "basic" encoding for transporting the S-expression between computers. * a "canonical" encoding, used when signing the S-expression. * an "advanced" encoding used for input/output to people. * an "in-memory" encoding used for processing the S-expression in the computer. In this document, related encoding techniques for each of these uses are provided. 3. Character set This document describes encodings of S-expressions. Except when giving "verbatim" encodings, the character set used is limited to the following characters in ASCII [RFC0020]: Alphabetic: A B ... Z a b ... z Numeric: 0 1 ... 9 Whitespace: space, horizontal tab, vertical tab, form-feed carriage-return, line-feed The following graphics characters, which are called "pseudo- alphabetic" in this document: - hyphen or minus . period / slash _ underscore : colon * asterisk + plus = equal The following graphics characters, which are "reserved punctuation": ( left parenthesis ) right parenthesis [ left bracket ] right bracket Rivest & Eastlake Expires 17 October 2024 [Page 6] Internet-Draft SPKI S-Expressions April 2024 { left brace } right brace | vertical bar # number sign " double quote & ampersand \ backslash The following characters are unused and unavailable, except in "verbatim" and "quoted string" encodings: ! exclamation point % percent ^ circumflex ~ tilde ; semicolon ' apostrophe , comma < less than > greater than ? question mark 4. Octet string representations 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. 4.1. Verbatim representation A verbatim encoding of an octet string consists of three parts: * the length (number of octets) of the octet-string, given in decimal, most significant digit first, with no leading zeros. * a colon ":" * the octet string itself, verbatim. 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: Rivest & Eastlake Expires 17 October 2024 [Page 7] Internet-Draft SPKI S-Expressions April 2024 3:abc 7:subject 4::::: 12:hello world! 10:abcdefghij 0: 4.2. Quoted-string representation The quoted-string representation of an octet-string consists of: * an optional decimal length field * an initial double-quote (") * the octet string with "C" [C] escape conventions (\n, etc.) * a final double-quote (") The specified length is the length of the resulting string after any escape sequences have been handled. The string does not have any "terminating NULL" that [C] includes, and the length does not count such a character. 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 LF, CRLF, or LFCR and more restrictive octal and hexadecimal value formats): Rivest & Eastlake Expires 17 October 2024 [Page 8] Internet-Draft SPKI S-Expressions April 2024 \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) \ -- causes carriage-return to be ignored. \ -- causes linefeed to be ignored. \ -- causes CRLF to be ignored. \ -- causes LFCR to be ignored. Here are some examples of quoted-string encodings: "subject" "hi there" 7"subject" "\xFE\o176 is the same byte value twice" 3"\n\n\n" "This has\n two lines." "This has \ one." "" 4.3. Token representation An octet string that meets the following conditions may be given directly as a "token". * it does not begin with a digit * it contains only characters that are: alphabetic (upper or lower case); numeric; or one of the eight "pseudo-alphabetic" punctuation marks: - . / _ : * + = Rivest & Eastlake Expires 17 October 2024 [Page 9] Internet-Draft SPKI S-Expressions April 2024 (Note: upper and lower case are not equivalent.) (Note: A token may begin with punctuation, including ":"). Here are some examples of token representations: subject not-before class-of-1997 //microsoft.com/names/smith * 4.4. Hexadecimal representation An octet-string may be represented with a hexadecimal encoding consisting of: * an (optional) decimal length of the octet string * a sharp-sign "#" * a hexadecimal encoding of the octet string, with each octet represented with two hexadecimal digits, most significant digit first. There MUST be an even number of such digits. * a sharp-sign "#" 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" 4.5. Base-64 representation An octet-string may be represented in a base-64 encoding [RFC4648] consisting of: * an (optional) decimal length of the octet string * a vertical bar "|" * the base-64 [RFC4648] encoding of the octet string. Rivest & Eastlake Expires 17 October 2024 [Page 10] Internet-Draft SPKI S-Expressions April 2024 * a final vertical bar "|" The base-64 encoding produces four characters of output for each three octets of input. If 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. This specification requires that the equals signs 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" 4.6. Display hint Any octet string may be preceded by a single "display hint". The purposes of the display hint is to provide information on how to display the 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 surrounded by square brackets. There may be whitespace separating the octet string from the surrounding brackets. Any of the legal formats may be used for the octet string. Here are some examples of display-hints: [image/gif] [URI] [charset=unicode-1-1] [text/richtext] ["text/plain; charset=iso-8859-1"] [application/postscript] [application/octet-stream] [audio/basic] ["http://abc.com/display-types/funky.html"] Rivest & Eastlake Expires 17 October 2024 [Page 11] Internet-Draft SPKI S-Expressions April 2024 Unless some other type is specified for the application of use, an octet-string that has no display-hint may be considered to have a pre-specified "default" MIME [RFC2046] type as follows: "application/octet-stream" 4.7. Equality of octet-strings Two octet strings are considered to be "equal" if and only if they have the same display hint and the same data octet strings. Note that octet-strings are "case-sensitive"; the octet-string "abc" is not equal to the octet-string "ABC". An untyped octet-string can be compared to another octet-string (typed or not) by considering it as a typed octet-string with the default type specified for the applications or, in the absence of such specificaion, the default type specified in Section 4.6 . 5. Lists Just as with octet-strings, there are several ways to represent 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. Also, whitespace may follow the initial left parenthesis, or precede the final right parenthesis. 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+) 6. Representation types There are three "types" of representations: * canonical * basic transport * advanced transport Rivest & Eastlake Expires 17 October 2024 [Page 12] Internet-Draft SPKI S-Expressions April 2024 The first two MUST be supported by any implementation; the last is OPTIONAL. 6.1. Canonical representation This canonical representation is used for digital signature purposes and transport over channels not sensitive to specific byte 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.1). 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)) 6.2. Basic transport representation There are two forms of the "basic transport" representation: * the canonical representation * an [RFC4648] base-64 representation of the canonical representation, surrounded by braces. The transport representations (see Section 7.2) 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 bytes of some special values such as a byte of all zero bits (NULL) or a byte of all one bits (DEL). Here are two examples of an S-expression represented in basic transport mode: (1:a1:b1:c) {KDE6YTE6YjE6YykK} Rivest & Eastlake Expires 17 October 2024 [Page 13] Internet-Draft SPKI S-Expressions April 2024 The second example above is the same S-expression as the first encoded in base-64. There is a difference between the brace notation for base-64 used here and the || notation for base-64'd octet-strings described above. Here the base-64 contents are converted to octets, and then re- scanned as if they were given originally as octets. With the || notation, the contents are just turned into an single octet-string. 6.3. Advanced transport representation 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 representation forms described above in Section 4, include quoted strings, base-64 and hexadecimal representation of strings, tokens, representations of strings with omitted lengths, and so on (see Section 7.3). 7. ABNF for syntax ABNF is the Augmented Backus-Naur Form for syntax specifications as defined in [RFC5234]. Separate ABNF's are given for canonical, basic, and advanced forms of S-expressions. The rules below in all caps are defined in Appendix A of [RFC5234]. 7.1. ABNF for canonical transport c-sexp = raw / ("(" *c-sexp ")") raw = decimal ":" *OCTET ; the length followed by a colon and the exact ; number of OCTET indicated by the length decimal = %x30 / (%x31-39 *DIGIT) 7.2. ABNF for basic transport Rivest & Eastlake Expires 17 October 2024 [Page 14] Internet-Draft SPKI S-Expressions April 2024 b-sexp = canonical / base-64-raw canonical = raw / ("(" *canonical ")") raw = decimal ":" *OCTET ; the length followed by a colon and the exact ; number of OCTET indicated by the length decimal = %x30 / (%x31-39 *DIGIT) base-64-raw = "{" 3*base-64-char "}" base-64-char = ALPHA / DIGIT / "+" / "/" / "=" 7.3. ABNF for advanced transport 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 simple-string *whitespace "]" simple-string = raw / token / base-64 / base-64-raw / hexadecimal / quoted-string raw = decimal ":" *OCTET ; the length followed by a colon and the exact ; number of OCTET indicated by the length decimal = %x30 / (%x31-39 *DIGIT) token = (ALPHA / simple-punc) *(ALPHA / DIGIT / simple-punc) simple-punc = "-" / "." / "/" / "_" / ":" / "*" / "+" / "=" base-64 = [decimal] "|" *(base-64-char / whitespace) "|" base-64-char = ALPHA / DIGIT / "+" / "/" / "=" Rivest & Eastlake Expires 17 October 2024 [Page 15] Internet-Draft SPKI S-Expressions April 2024 base-64-raw = [decimal] "{" 1*(base-64-char / whitespace) "}" ; at least 3 base-64-char hexadecimal = [decimal] "#" *(HEXDIG / whitespace) "#" ; even number of hexadecimal digits quoted-string = [decimal] DQUOTE *(printable / escaped) DQUOTE 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 printable = %x20-21 / %x23-5B / %x5D-7E ; All US-ASCII printable but double-quote ; and backslash quote = %x27 ; single quote 8. In-memory representations 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: * "list-structure" * "array-layout" These are only sketched here, as they are only suggestive. The [SexpCode] code illustrates these styles in more detail. 8.1. List-structure memory representation Here there are separate records for simple-strings, strings, and lists. 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 as illustrated below. This is a fairly conventional representation. Rivest & Eastlake Expires 17 October 2024 [Page 16] Internet-Draft SPKI S-Expressions April 2024 List: Location +-----------------------------------+ | pointer to 13 | pointer to 21 | 10 +-----------------------------------+ +-----------------------------------+ | list end flag | pointer to 24 | 13 +-----------------------------------+ Strings: +-----------------------------------+ | no display hint | pointer to 29 | 21 +-----------------------------------+ +-----------------------------------+ | no display hint | pointer to 92 | 24 +-----------------------------------+ Simple-Strings: +------------------------------+ | "abc" | 29 +------------------------------+ +-------------------------+ | "de" | 92 +-------------------------+ 8.2. Array-layout memory representation Here each S-expression is represented as a contiguous array of bytes. The first byte 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-byte integer indicating the size (in bytes) 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. Rivest & Eastlake Expires 17 October 2024 [Page 17] Internet-Draft SPKI S-Expressions April 2024 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. 8.2.1. Octet string This is represented as follows: 01 For example (here k = 2) 01 0003 a b c 8.2.2. Octet-string with display-hint This is represented as follows: 02 01 /* for display-type */ 01 /* 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 8.2.3. List This is represented as 03 ... 00 For example, the list (abc [d]ef (g)) is represented in memory as (with k = 2) Rivest & Eastlake Expires 17 October 2024 [Page 18] Internet-Draft SPKI S-Expressions April 2024 03 001b 01 0003 a b c 02 0009 01 0001 d 01 0002 e f 03 0005 01 0001 g 00 00 9. Restricted S-expressions This document has described S-expressions in general form. Application writers 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: * no advanced representations (only canonical and basic) * no display-hints * no lengths on hexadecimal, quoted-strings, or base-64 encodings * no empty lists * no empty octet-strings * no lists having another list as its first element * no base-64 or hexadecimal encodings * fixed limits on the size of octet-strings 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. 10. Security Considerations As a pure data representation format, there are few security considerations to S-expressions. A canonical form is required for the reliable verification of digital signatures. This is provided in Section 6.1. Rivest & Eastlake Expires 17 October 2024 [Page 19] Internet-Draft SPKI S-Expressions April 2024 11. IANA Considerations This document requires no IANA actions. 12. Normative References [C] Kernighan, B. and D. Ritchie, "The C Programming Language", ISBN 0-13-110370-9, 1988. [RFC0020] Cerf, V., "ASCII format for network interchange", STD 80, RFC 20, DOI 10.17487/RFC0020, October 1969, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, . [RFC5234] Crocker, D., Ed. and P. Overell, "Augmented BNF for Syntax Specifications: ABNF", STD 68, RFC 5234, DOI 10.17487/RFC5234, January 2008, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 13. Informative References [BERN] Bernstein, D., "Netstrings", Work in progress, 1 February 1997, . [CANON] Wikipedia, "Canonical S-expressions", . Grinberg, R., "Csexp - Canonical S-expressions", 24 March 2023, . [CDDLfreezer] Borman, C., "A feature freezer for the Concise Data Definition Language (CDDL)", work in progress, 12 September 2023, . Rivest & Eastlake Expires 17 October 2024 [Page 20] Internet-Draft SPKI S-Expressions April 2024 [GnuPG] Free Software Foundation, Inc., "The GNU Privacy Guard", . [Inferno] Uriel, "Inferno S-expressions", . [Libgcrypt] GnuPG, "The Libgcrypt Library", Libgcrypt version 1.10.2, 6 April 2023, . [LISP] Levin, M. and J. McCarthy, "LISP 1.5 Programmer's Manual", ISBN-13 978-0-262-12011-0, ISBN-10 0262130114, 15 August 1962. [RFC2046] Freed, N. and N. Borenstein, "Multipurpose Internet Mail Extensions (MIME) Part Two: Media Types", RFC 2046, DOI 10.17487/RFC2046, November 1996, . [RFC2692] Ellison, C., "SPKI Requirements", RFC 2692, DOI 10.17487/RFC2692, September 1999, . [RFC2693] Ellison, C., Frantz, B., Lampson, B., Rivest, R., Thomas, B., and T. Ylonen, "SPKI Certificate Theory", RFC 2693, DOI 10.17487/RFC2693, September 1999, . [RFC3259] Ott, J., Perkins, C., and D. Kutscher, "A Message Bus for Local Coordination", RFC 3259, DOI 10.17487/RFC3259, April 2002, . [RFC3275] Eastlake 3rd, D., Reagle, J., and D. Solo, "(Extensible Markup Language) XML-Signature Syntax and Processing", RFC 3275, DOI 10.17487/RFC3275, March 2002, . [RFC7159] Bray, T., Ed., "The JavaScript Object Notation (JSON) Data Interchange Format", RFC 7159, DOI 10.17487/RFC7159, March 2014, . [RFC8949] Bormann, C. and P. Hoffman, "Concise Binary Object Representation (CBOR)", STD 94, RFC 8949, DOI 10.17487/RFC8949, December 2020, . Rivest & Eastlake Expires 17 October 2024 [Page 21] Internet-Draft SPKI S-Expressions April 2024 [Ribose] Ribose Group Inc., "Open-source projects for developers and designers", 13 April 2023, . [RNPGP_SEXPP] RNP, R., "S-Expressions parser and generator library in C++ (SEXP in C++)", version 0.8.7, 28 June 2023, . [SDSI] Rivest, R. and B. Lampson, "A Simple Distributed Security Architecture", working document, SDSI version 1.1, 2 October 1996, . [SexpCode] Malkiewicz, J., "SEXP---(S-expressions)", 10 June 2015, . [SEXPP] Davis, R., "SexpProcessor", 10 June 2015, . [SFEXP] Sottile, M., "Small Fast X-Expression Library", 24 March 2023, . [SPKI] Rivest, R., "SPKI/SDSI 2.0 A Simple Distributed Security Infrastructure", . [XML] Bray, T., Paoli, J., Sperberg-McQueen, C.M., Maler, E., and F. Yergeau, "Extensible Markup Language (XML) 1.0", 26 November 2008, . Appendix A. Implementations At this time there 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: * Project GNU's [Libgcrypt]. * Ribose's RNP [RNPGP_SEXPP] in C++. * Github project of J. P. Malkiewicz [SexpCode] in C. * The Inferno implementation [Inferno]. * Small Fast X-Expression Library [SFEXP]. Rivest & Eastlake Expires 17 October 2024 [Page 22] Internet-Draft SPKI S-Expressions April 2024 * S-expression Processor [SEXPP] in Ruby. * Canonical S-expressions [CANON] (OCAML). Appendix B. Change History RFC Editor Note: Please delete this section before publication. B.1. -00 Changes This sub-section summarizes significant changes between the original 1997 -00 version of this document and the 2023 -00 version submitted to the IETF. 1. Convert to XML v3. 2. Update Ron Rivest author information and, with his permission, add Donald Eastlake as an author. 3. Add minimal "IANA Considerations" and "Security Considerations" sections. 4. Since implementation requirements terminology is used, add the usual paragraph about it as a sub-section of Section 1 and add references to [RFC2119] and [RFC8174]. 5. Divide references into Normative and Informational and update base-64 reference to be to [RFC4648]. 6. Add a couple of sentences to the "Historical note" section about the history of -00 versions of the draft. B.2. Changes from -00 to -01 1. Fix glitches and errors in the BNF. 2. Add Acknowledgements section to list Marc Petit-Huguenin (who provided BNF improvements) and John Klensin. 3. Update code references in Appendix A and add to Informative References section. Note: The code in the Malkiewicz github repository may be the code that was originally at http://theory.lcs.mit.edu/~rivest/sexp.html 4. Add this Change History Appendix. 5. Move "Historical Notes" which were formerly a separate section at the end of the document up to be a sub-section of Section 1. Rivest & Eastlake Expires 17 October 2024 [Page 23] Internet-Draft SPKI S-Expressions April 2024 6. Add references to [LISP], [RFC2692], and [RFC2693]. 7. Add simple security considerations. 8. Minor editorial fixes/improvements. B.3. Changes from -01 to -02 1. Change default MIME Type in Section 4.6 to have charset=utf-8 [RFC4648]. 2. Change BNF to ABNF and add reference to [RFC5234]. 3. Move Marc Petit-Huguenin to a Contributors section for his work on the ABNF. B.4. Changes from -02 to -03 1. Add current S-expression usage Section 1.2. 2. Add the white book [C] as a reference. 3. Add reference to the Ribose RNP code [RNPGP_SEXPP]. 4. Minor editorial improvements. B.5. Changes from -03 to -04 Trivial keep-alive update. B.6. Changes from -04 to -05 1. Add reference to Inferno implementation. 2. Eliminate remaining references to being a "proposal". 3. Emphasize that a particular application can specify a different default display hint. 4. Add reference to RFC 0020 for ASCII. 5. Minor editorial improvements. B.7. Changes from -05 to -06 1. Move implementations listd to Appendix A. Add numerous implementations. Rivest & Eastlake Expires 17 October 2024 [Page 24] Internet-Draft SPKI S-Expressions April 2024 2. Change default display-hint to "application/octet-stream". 3. Expand Abstract and include most of Abstract in the Introduction. 4. Use different tokens for the top level rule in the three ABNF encodings so that the rules would not collide if all were used. Fix ABNF for "printable". 5. Add an illustration of list-structure memory representation. 6. Editorial improvements. Acknowledgements 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. Contributors Special thanks to the following contributor: Marc Petit-Huguenin Impedance Mismatch LLC Email: marc@petit-huguenin.org Authors' Addresses Ronald L. Rivest MIT CSAIL 32 Vassar Street, Room 32-G692 Cambridge, Massachusetts 02139 United States of America Email: rivest@mit.edu URI: https://www.csail.mit.edu/person/ronald-l-rivest Donald E. Eastlake 3rd Independent 2386 Panoramic Circle Apopka, Florida 32703 United States of America Phone: +1-508-333-2270 Email: d3e3e3@gmail.com Rivest & Eastlake Expires 17 October 2024 [Page 25]