RFC 9804

Simple Public Key Infrastructure (SPKI) S-Expressions

📅 published June 2025, from ietf

RFC 9804: Simple Public Key Infrastructure (SPKI) S-Expressions 🎀

okay bestie, this one is a specification for how to write down structured data (the S-expression format that SPKI certificates are built on) 🧚 it's Informational, not Standards Track, so it's published for info and not as a must-follow protocol standard. 💅

Authors: R. Rivest (MIT CSAIL) and D. Eastlake 3rd (Independent) ✨ Date: June 2025 🌸 ISSN: 2070-1721 💜 Obsoletes / Updates: the title block doesn't list any, so nothing is obsoleted or updated here 🙈

Abstract 💖

this memo specifies the data structure representation that was devised to support Simple Public Key Infrastructure (SPKI) certificates, as detailed in RFC 2692, with the intent that it be more widely applicable. it has been and is being used elsewhere, and 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 describes an "advanced" format for display to people. 🦋

Status of This Memo 📜

this document is not an Internet Standards Track specification; it is published for informational purposes. 🌈

this document is a product of the Internet Engineering Task Force (IETF). it represents the consensus of the IETF community. it has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). not all documents approved by the IESG are candidates for any level of Internet Standard; see Section 2 of RFC 7841. ✨

information about the current status of this document, any errata, and how to provide feedback on it may be obtained at https://www.rfc-editor.org/info/rfc9804. 💅

Copyright (c) 2025 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. ⭐

Table of Contents 🗂️

1.  Introduction
  1.1.  Uses of S-Expressions
  1.2.  Formalization
  1.3.  Historical Note
  1.4.  Conventions Used in This Document
2.  S-expressions -- Informal Introduction
3.  Character Set
4.  Octet-String Representation Types
  4.1.  Verbatim Representation
  4.2.  Quoted-String Representation
  4.3.  Token Representation
  4.4.  Hexadecimal Representation
  4.5.  Base-64 Representation of Octet-Strings
  4.6.  Display-Hints and Internationalization
  4.7.  Comparison of Octet-Strings
5.  Lists
6.  S-Expression Representation Types
  6.1.  Base-64 Representation of S-Expressions
  6.2.  Canonical Representation
  6.3.  Basic Transport Representation
  6.4.  Advanced Transport Representation
7.  ABNF of the Syntax
  7.1.  ABNF for Advanced Transport
  7.2.  ABNF for Canonical
  7.3.  ABNF for Basic Transport
8.  Restricted S-Expressions
9.  In-Memory Representations
  9.1.  List-Structure Memory Representation
  9.2.  Array-Layout Memory Representation
    9.2.1.  Octet-String
    9.2.2.  Octet-String with Display-Hint
    9.2.3.  List
10. Security Considerations
11. IANA Considerations
12. References
  12.1.  Normative References
  12.2.  Informative References
Appendix A.  Implementations
Acknowledgements
Contributors
Authors' Addresses

1. Introduction ✨

this memo specifies the data structure representation that was devised to support Simple Public Key Infrastructure (SPKI) certificates [RFC2692], with the intent that it be more widely applicable (see Section 1.3, "Historical Note"). it's 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 describes 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 octet-strings or lists of simpler S-expressions. here's a sample S-expression:

(snicker "abc" (#03# |YWJj|))

it's 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# (which represents a one-octet-long octet-string with the value of that octet being 0x03) and the base-64 constant |YWJj| (which represents the same octet-string as "abc")

this document specifies how to construct and use these S-expressions. 🎀

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.
  • Transportability: 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.

for implementors of new applications and protocols, other technologies also worthy of consideration include the following: XML [XML], CBOR [RFC8949], and JSON [RFC8259]. 🍓

1.1. 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 the Libgcrypt library [Libgcrypt], and there are other implementations (see Appendix A). 🔥

S-expressions are also 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 [CDDL-freezer]. 🧚

1.2. Formalization 🦋

[Formal] is an Internet-Draft that shows a formal model of SPKI S-expressions and formally demonstrates that the examples and ABNF in this document are correct. 💅

1.3. Historical Note 📜

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 "netstrings" [BERN], which were developed contemporaneously. 🌈

Although a specification was 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 clarified and modernized version of that document.

1.4. 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. an octet-string may be zero length. 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"

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:

  • 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 specifies 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
{  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
'  single-quote (apostrophe)
,  comma
<  less than
>  greater than
?  question mark

4. Octet-String Representation Types 💜

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 an octet-string may have length zero. 🫶

4.1. Verbatim Representation

okay so the verbatim encoding of an octet-string is made of three parts, bestie 🎀

  • the length (number of octets) of the octet-string, written in decimal with the most significant digit first and no leading zeros 💅
  • a colon ":" 🫶
  • the octet-string itself, verbatim ✨

there are no blanks or whitespace between the parts, and no "escape sequences" get interpreted inside the octet-string. this one is also called a "binary" or "raw" encoding 🦋

here are some sample verbatim encodings, iykyk 🌸

3:abc
7:subject
4:::":
12:hello world!
10:abcdefghij
0:

4.2. Quoted-String Representation

the quoted-string representation of an octet-string is giving structured 💜

  • an optional decimal length field
  • an initial double-quote (")
  • the octet-string with the C programming language [C88] escape conventions (\n, etc.)
  • a final double-quote (")

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 [C88] includes, and the length does not count such an octet. no cap, that's a detail people mess up 🙈

the length is optional 🌈

the escape conventions inside the quoted string follow the C programming language [C88] conventions, with an extension for ignoring line terminators of just CR, LF, CRLF, or LFCR, and with 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 line-feed to be ignored.
\<carriage-return><line-feed>   -- causes
          CRLF to be ignored.
\<line-feed><carriage-return>   -- causes
          LFCR to be ignored.

the octal one is a must: all three digits MUST be present ✨ same for hex, where both digits MUST be present 🔥

here are some examples of quoted-string encodings, slay 👑

"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."
""

4.3. Token Representation

an octet-string that meets these conditions can be written 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 following eight "pseudo-alphabetic" punctuation marks:
-  .  /  _  :  *  +  =
  • it is length 1 or greater.

note: upper and lower case are not equivalent 💀 and a token may begin with punctuation, including ":" 🌸

here are some examples of token representations 🍓

subject
not-before
:=..
class-of-1997
//example.net/names/smith
*

4.4. Hexadecimal Representation

an octet-string may be represented with a hexadecimal encoding made 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 final sharp-sign "#"

there may be whitespace inserted in the middle of the hex encoding wherever, and it gets 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

4.5. Base-64 Representation of Octet-Strings

an octet-string may be represented in a base-64 encoding [RFC4648] made of:

  • an (optional) decimal length of the octet-string
  • a vertical bar "|"
  • the base-64 [RFC4648] encoding of the octet-string.
  • a final vertical bar "|"

base-64 encoding makes four characters of output for every three octets of input. when the length of the input is divided by three:

  • if the remainder is one, it produces an output block of length four ending in two equals signs.
  • if the remainder is two, it produces an output block of length four ending in one equals sign.

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 middle of the base-64 encoding is ignored, and 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 👀

4.6. Display-Hints and Internationalization

an octet-string can hold any type of data you can represent with a finite octet-string, like text, a fixed or variable-length integer, or an image 🌸 normally, the application producing and/or consuming S-expressions understands their structure, the data type, and the encoding of the octet-strings inside them. if the octet-string is text, using UTF-8 encoding is RECOMMENDED [RFC2130] [RFC3629] 💜

the purpose of a display-hint is to tell you how to display an octet-string to a user. that's it, it has no other function 🦋 lots of the media types [RFC2046] work here ✨

a display-hint is an octet-string representation wrapped in square brackets. there may be whitespace between the display hint octet-string and the surrounding brackets. any of the legal octet-string representations can be used for the display-hint string, but a display-hint may not be applied to a display-hint string. in other words, display-hints may not be nested 🙅

here's a display-hint that works for UTF-8-encoded text, where the octet-string represents "böb☺", which is "bob" with an umlaut over the "o", followed by the Unicode [Unicode] character WHITE SMILING FACE (U+263A) 🌷

["text/plain; charset=utf-8"]"b\xC3\xB7b\xE2\x98\xBA"

every octet-string representation is or is not preceded by a single display-hint. there may be whitespace between the close square bracket and the octet-string the hint applies to 🫶

here are some other display-hint examples 🎀

[image/gif]
[charset=unicode-1-1]
[  text/richtext  ]
["text/plain; charset=iso-8859-1"]
[application/postscript]
[audio/basic]
["http://example.com/display-types/funky.html"]

an octet-string with no display-hint may be considered to have a media type [RFC2046] specified by the application or use. if nothing like that is specified, the default is:

[application/octet-stream]

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, and the default display-hint is not included in the representation for an octet-string without a display-hint 🧚

4.7. Comparison of Octet-Strings

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, if no such specification exists, the general default display-hint specified in Section 4.6 🌈

5. Lists

just like with octet-strings, there are variations in how you represent a list 🎀 whitespace may be used to separate list elements, but it's only required to separate two octet-strings when they'd otherwise be read as one, like when one token follows another. to be precise, an octet-string represented as a token (Section 4.3) MUST be separated by whitespace 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 🫶 whitespace may also follow the initial left parenthesis or precede the final right parenthesis of a list 💅

here are some examples of list encodings 🦋

(a bob c)

( a ( bob c ) ( ( d e ) ( e f ) )  )

(11:certificate(6:issuer3:bob)(7:subject5:alice))

(|ODpFeGFtcGxlIQ==| "1997" murphy 3:XC+)

()

6. S-Expression Representation Types

there are three "types" of representation:

  • canonical
  • basic transport
  • advanced transport

the first two MUST be supported by any implementation, and the last is OPTIONAL 🔥 as part of the basic representation, the base-64 [RFC4648] representation of an S-expression may be used, as described in Section 6.1 💖

6.1. Base-64 Representation of S-Expressions

an S-expression may be represented in a base-64 encoding [RFC4648] made of:

  • an opening curly brace "{"
  • the base-64 [RFC4648] encoding of the S-expression
  • a final closing curly brace "}"

base-64 encoding makes four characters of output for every 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 middle 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 ✨

6.2. Canonical Representation

okay so this is the canonical form, and it's giving pure precision 🔥 It's used for digital signatures and for transport over channels that aren't sensitive to specific octet values 💅 Each S-expression has exactly one canonical representation 💖 It's not pretty to look at, but that's not the point, bestie 🙈 It's meant to be super easy to parse, reasonably economical, and unique for every S-expression ✨ See [CANON1] and [CANON2].

The "canonical" form represents each octet-string in verbatim mode, and every list has no blanks separating its elements from each other or from the surrounding parentheses 🎀 See also Section 7.2.

Here are some canonical examples, iconic 👑

(6:issuer3:bob) (4:icon[12:image/bitmap]9:xxxxxxxxx) (7:subject(3:ref5:alice6:mother)) 10:foo)]}>bar 0:

6.3. Basic Transport Representation

okay so there are two forms of "basic transport" 🦋

  1. The canonical representation
  2. A base-64 [RFC4648] representation of the canonical representation, surrounded by braces (see Section 6.1)

Basic transport representations (see Section 7.3) are meant to be a universal way to represent S-expressions when sending them from one machine to another 🌸 The base-64 version is the one you'd want if the channel might be sensitive to octets with special values, like an octet of all zero bits (NULL) or an octet of all one bits (DEL), or if the channel is sensitive to "line length" so that occasional line-ending whitespace is needed 🧚

Here are two examples of the same S-expression in basic transport mode 💜

(1:a1:b1:c)

{KDE6YTE6YjE 6Yyk= }

The second one is the same S-expression as the first, just base-64 encoded ✨

6.4. Advanced Transport Representation

The "advanced transport" representation is meant to be more flexible and readable for documentation, design, debugging, and (in some cases) user interfaces 💖 It's giving main character energy 😭

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 🫶 See Section 7.1.

  1. ABNF of the Syntax

ngl this section is the grammar part, and it's the real deal 🔥 ABNF is the Augmented Backus-Naur Form for syntax specifications, as defined in [RFC5234] 💅 The ABNF for advanced representation of S-expressions comes first, and the basic and canonical forms are derived from it 🌈 The rule names in all capital letters are defined in Appendix B.1 of [RFC5234] ✨

7.1. 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] simple-string

display        =  "[" *whitespace simple-string *whitespace "]"
                  *whitespace

simple-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)

7.2. ABNF for Canonical

c-sexp         =  c-string / ("(" *c-sexp ")")

c-string       =  [ "[" verbatim "]" ] verbatim

7.3. ABNF for Basic Transport

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
  1. Restricted S-Expressions

okay so this section is about restricting how you use S-expressions, and it's giving "pick your lane" 🛣️ This document described S-expressions in their general form 🎀 Applications may want to restrict their use in various ways, and to specify a different default display-hint too 💅 Here are some 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 🫶 So advanced representation can only be used in applications that mandate its support, or where a capability discovery mechanism indicates support 🧚

  1. In-Memory Representations

for processing, the S-expression would usually get parsed and stored in memory in a form that's easier to process efficiently 💻 This document suggests two alternatives 💖

  • "list-structure"
  • "array-layout"

These are only sketched here, since they're just suggestive ✨ The code in [SexpCode] shows these styles in more detail 🦋

9.1. List-Structure Memory Representation

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 💅 A record is a fairly small block of memory and, except for simple-string, might have pointers in it to other records 🫶 This is a pretty conventional representation, as discussed in Section 4 of [LISP2] 👑

9.2. Array-Layout Memory Representation

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 it would be fixed for a given implementation, since 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, they're easy to fill 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 ✨

9.2.1. Octet-String

This is represented as follows:

01 <length> <octet-string>

For example (here, k = 2):

01 0003 a b c

9.2.2. Octet-String with Display-Hint

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

9.2.3. List

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
  1. Security Considerations

okay this one is serious, bestie 😭🔥 As a pure data representation format, S-expressions have few security considerations 💀 A canonical form is required for creating and verifying digital signatures consistently, and that's provided in Section 6.2 🔐

The default display-hint (see Section 4.6) can be specified for an application 🎀 Heads up: if S-expressions containing untyped octet-strings represented for that application get processed by a different application, those untyped octet-strings may be treated as if they had a different display-hint ⚠️

  1. IANA Considerations

no IANA actions for this one 🌸 This document has no IANA actions 🫶

  1. References

12.1. Normative References

[C88]      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,
           <https://www.rfc-editor.org/info/rfc20>.

[RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
           Requirement Levels", BCP 14, RFC 2119,
           DOI 10.17487/RFC2119, March 1997,
           <https://www.rfc-editor.org/info/rfc2119>.

[RFC3629]  Yergeau, F., "UTF-8, a transformation format of ISO
           10646", STD 63, RFC 3629, DOI 10.17487/RFC3629, November
           2003, <https://www.rfc-editor.org/info/rfc3629>.

[RFC4648]  Josefsson, S., "The Base16, Base32, and Base64 Data
           Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
           <https://www.rfc-editor.org/info/rfc4648>.

[RFC5234]  Crocker, D., Ed. and P. Overell, "Augmented BNF for Syntax
           Specifications: ABNF", STD 68, RFC 5234,
           DOI 10.17487/RFC5234, January 2008,
           <https://www.rfc-editor.org/info/rfc5234>.

[RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
           2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
           May 2017, <https://www.rfc-editor.org/info/rfc8174>.

12.2. Informative References 📚✨

okay bestie, here's the reading list 🎀 these aren't required to implement the spec, but they're the good stuff for going deeper 💅

[BERN] Bernstein, D. J., "Netstrings", Work in Progress, Internet-Draft, draft-bernstein-netstrings-02, 1 January 1997, <https://datatracker.ietf.org/doc/html/draft-bernstein-netstrings-02>.

[CANON1] Wikipedia, "Canonical S-expressions", <https://en.wikipedia.org/wiki/Canonical_S-expressions>.

[CANON2] Grinberg, R., "Csexp - Canonical S-expressions", 24 March 2023, <https://github.com/ocaml-dune/csexp>.

[CDDL-freezer] Bormann, C., "A feature freezer for the Concise Data Definition Language (CDDL)", Work in Progress, Internet-Draft, draft-bormann-cbor-cddl-freezer-15, 28 February 2025, <https://datatracker.ietf.org/doc/html/draft-bormann-cbor-cddl-freezer-15>.

[Formal] Petit-Huguenin, M., "A Formalization of Symbolic Expressions", Work in Progress, Internet-Draft, draft-petithuguenin-ufmrg-formal-sexpr-06, 4 May 2025, <https://datatracker.ietf.org/doc/html/draft-petithuguenin-ufmrg-formal-sexpr-06>.

[GnuPG] GnuPG, "The GNU Privacy Guard", <https://www.gnupg.org/>.

[Inferno] "Inferno S-expressions", Inferno Manual Page, <https://man.cat-v.org/inferno/6/sexprs>.

[Libgcrypt] GnuPG, "The Libgcrypt Library", Libgcrypt version 1.10.2, 6 April 2023, <https://www.gnupg.org/documentation/manuals/gcrypt/>.

[LISP] McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T. P., and M. Levin, "LISP 1.5 Programmer's Manual", ISBN-13 978-0-262-12011-0, ISBN-10 0262130114, 15 August 1962, <https://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf>.

[LISP2] McCarthy, J., "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", April 1960, <https://people.cs.umass.edu/~emery/classes/cmpsci691st/readings/PL/LISP.pdf>.

[RFC2046] Freed, N. and N. Borenstein, "Multipurpose Internet Mail Extensions (MIME) Part Two: Media Types", RFC 2046, DOI 10.17487/RFC2046, November 1996, <https://www.rfc-editor.org/info/rfc2046>.

[RFC2130] Weider, C., Preston, C., Simonsen, K., Alvestrand, H., Atkinson, R., Crispin, M., and P. Svanberg, "The Report of the IAB Character Set Workshop held 29 February - 1 March, 1996", RFC 2130, DOI 10.17487/RFC2130, April 1997, <https://www.rfc-editor.org/info/rfc2130>.

[RFC2692] Ellison, C., "SPKI Requirements", RFC 2692, DOI 10.17487/RFC2692, September 1999, <https://www.rfc-editor.org/info/rfc2692>.

[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, <https://www.rfc-editor.org/info/rfc2693>.

[RFC3259] Ott, J., Perkins, C., and D. Kutscher, "A Message Bus for Local Coordination", RFC 3259, DOI 10.17487/RFC3259, April 2002, <https://www.rfc-editor.org/info/rfc3259>.

[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, <https://www.rfc-editor.org/info/rfc3275>.

[RFC8259] Bray, T., Ed., "The JavaScript Object Notation (JSON) Data Interchange Format", STD 90, RFC 8259, DOI 10.17487/RFC8259, December 2017, <https://www.rfc-editor.org/info/rfc8259>.

[RFC8949] Bormann, C. and P. Hoffman, "Concise Binary Object Representation (CBOR)", STD 94, RFC 8949, DOI 10.17487/RFC8949, December 2020, <https://www.rfc-editor.org/info/rfc8949>.

[Ribose] Ribose Group Inc., "Open-source projects for developers and designers", <https://open.ribose.com/>.

[RNPGP_SEXPP] "S-Expressions parser and generator library in C++ (SEXP in C++)", Version 0.9.2, commit 249c6e3, 22 March 2025, <https://github.com/rnpgp/sexpp>.

[SDSI] Rivest, R. and B. Lampson, "A Simple Distributed Security Architecture", Working document for SDSI version 1.1, 2 October 1996, <https://people.csail.mit.edu/rivest/pubs/RL96.ver-1.1.html>.

[SexpCode] "SEXP---(S-expressions)", commit 4aa7c36, 10 June 2015, <https://github.com/jpmalkiewicz/rivest-sexp>.

[SEXPP] "SexpProcessor", commit a90f90f, 11 April 2025, <https://github.com/seattlerb/sexp_processor>.

[SFEXP] "Small Fast X-Expression Library", commit b7d3bea, 24 March 2023, <https://github.com/mjsottile/sfsexp>.

[SPKI] Rivest, R., "SPKI/SDSI 2.0 A Simple Distributed Security Infrastructure", <https://people.csail.mit.edu/rivest/pubs/RL96.slides-maryland.pdf>.

[Unicode] The Unicode Consortium, "The Unicode Standard", <https://www.unicode.org/versions/latest/>.

[XML] Bray, T., Paoli, J., Sperberg-McQueen, C.M., Maler, E., and F. Yergeau, "Extensible Markup Language (XML) 1.0", W3C Recommendation, 26 November 2008, <https://www.w3.org/TR/2008/REC-xml-20081126/>. Latest version available at <https://www.w3.org/TR/REC-xml/>.

Appendix A. Implementations 🧚💜

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:

  • 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]
  • S-expression Processor [SEXPP] in Ruby
  • Canonical S-expressions [CANON2] (OCAML)

Acknowledgements 🫶

Special thanks to Daniel K. Gillmor for his extensive comments 🌸

The comments and suggestions of the following are gratefully acknowledged: John Klensin and Caleb Malchik. 💖

Contributors 🎀

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 draft versions of this document:

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

that's the whole spec, bestie!! 🌈👑 it was SO worth the read 😭✨

📦 where this page comes from