| RFC 9804 | SPKI S-Expressions | June 2025 |
| Rivest & Eastlake 3rd | Informational | [Page] |
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. 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.¶
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 athttps://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.¶
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 (seeSection 1.3, "Historical Note"). 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 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 (seeAppendix A).¶
These S-expressions are either 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 theseS-expressions.¶
The design goals for S-expressions were as follows:¶
For implementors of new applications and protocols othertechnologies also worthy of consideration include the following: XML[XML], CBOR[RFC8949], and JSON[RFC8259].¶
The S-expressions specified herein are in active use today betweenGnuPG[GnuPG] and Ribose's RNP[Ribose].Ribose has implemented C++ software to compose and parse theseS-expressions[RNPGP_SEXPP]. The GNU software is the Libgcrypt library[Libgcrypt], and there are other implementations (seeAppendix A).¶
S-expressions are also used or referenced in the following RFCs:¶
In addition, S-expressions are the inspiration for the encodings inother protocols. For example,[RFC3259] orSection 6 of [CDDL-freezer].¶
[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.¶
The S-expressions described here were originally developed for"SDSI" (the Simple Distributed Security Infrastructure by Lampson andRivest[SDSI]) in 1996, although their origins dateback to McCarthy's[LISP] programming language. Theywere further refined and improved during the merger of SDSI and SPKI[SPKI][RFC2692][RFC2693] during the first half of 1997. S-expressions aremore 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.¶
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. Anoctet-string may be zero length. There may be many different butequivalent 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 thesame octet-string. Details of these encodings are given below, and howto give a "display type" to a simple-string is also described inSection 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 ofencodings of its elements, as in:¶
(abc (de #6667#) "ghi jkl")¶
As can be seen, there is variability possible in the encoding of anS-expression. In some applications, it is desirable to standardize orrestrict the encodings; in other cases, it is desirable to have norestrictions. The following are the target cases these S-expressionsaim to handle:¶
In this document, related encoding techniques for each of theseuses are provided.¶
This document specifies encodings of S-expressions. Except whengiving "verbatim" encodings, the character set used is limited to thefollowing 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¶
This section describes in detail the ways in which an octet-string maybe represented.¶
Recall that an octet-string is any finite sequence of octets andthat an 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 "escapesequences" are interpreted in the octet-string. This encoding is alsocalled 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 afterany backslash escape sequences have been converted to the octet valuethey denote. The string does not have any "terminating NULL" that[C88] includes, and the length does not count such anoctet.¶
The length is optional.¶
The escape conventions within the quoted string are as follows(these follow the C programming language[C88] conventions, with an extension for ignoring line terminators of justCR, LF, CRLF, or LFCR and more restrictive octal and hexadecimal valueformats):¶
\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.¶
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 givendirectly as a "token":¶
it contains only characters that are: alphabetic (upper or lower case), numeric, or one of the following eight "pseudo-alphabetic" punctuation marks:¶
- . / _ : * + =¶
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 //example.net/names/smith *¶
An octet-string may be represented with a hexadecimal encodingconsisting of:¶
There may be whitespace inserted in the midst of the hexadecimalencoding arbitrarily; it is ignored. It is an error to havecharacters 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 threeoctets of input. When the length of the input is divided by three:¶
These equals signsMUST be included on output, but input routinesMAY accept inputs whereone or two equals signs are dropped.¶
Whitespace inserted in the midst of the base-64 encoding isignored. It is an error to have characters other than whitespace andbase-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 anoctet-string using vertical bars ("| |") and the base-64 encoding ofan S-expression using curly braces ("{ }") inSection 6.1.¶
An octet-string can contain any type of data representable by afinite octet-string, e.g., text, a fixed or variable-lengthinteger, or an image. Normally, the application producing and/or consumingS-expressions will understand their structure, the data type, andthe encoding of the octet-strings within the S-expressions used by thatapplication. If the octet-string consists of text, use of UTF-8encoding isRECOMMENDED[RFC2130][RFC3629].¶
The purpose of a display-hint is to provide information on how todisplay an octet-string to a user. It has no other function. Many ofthe media types[RFC2046] work here.¶
A display-hint is an octet-string representation surrounded bysquare brackets. There may be whitespace separating the display hintoctet-string from the surrounding brackets. Any of the legaloctet-string representations may be used for the display-hint string,but a display-hint may not be applied to a display-hint string -- thatis, display-hints may not be nested.¶
A display-hint that can be used for UTF-8-encoded text is shown inthe following example where the octet-string represents "böb☺", that 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 singledisplay-hint. There may be whitespace betweenthe close square bracket and the octet-string to which the hintapplies.¶
Here are some other examples of display-hints:¶
[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 that has no display-hint may be considered to havea media type[RFC2046] specified by the application oruse. In the absence of such a specification, the default is asfollows:¶
[application/octet-stream]¶
When an S-expression is being encoded in one of the representationsdescribed inSection 6, any display-hint present isincluded. If a display-hint is the default, it is not suppressed noris the default display-hint included in the representation for anoctet-string without a display-hint.¶
It isRECOMMENDED that two octet-strings be considered equivalentfor most computational and algorithmic purposes if and only if theyhave the same display-hint and the same data octet-strings. However, aparticular 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 anotheroctet-string (with or without a display hint) by considering it as anoctet-string with the default display-hint specified for theapplications or, in the absence of such specification, the generaldefault display-hint specified inSection 4.6 .¶
Just as with octet-strings, there are variations in representing alist. Whitespace may be used to separate list elements, but they areonly required to separate two octet-strings when otherwise the twooctet-strings might be interpreted as one, as when one token followsanother. To be precise, an octet-string represented as a token (Section 4.3)MUST be separated by whitespace from a followingtoken, verbatim representation, or any of the following if they areprefixed with a length: quoted-string, hexadecimal, or base-64representation. Also, whitespace may follow the initial leftparenthesis 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 twoMUST be supported by any implementation; the last isOPTIONAL. As part of basic representation, the base-64[RFC4648] representation of an S-expression may be used asdescribed inSection 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 threeoctets of input. If the length of the input divided by three leaves aremainder of one or two, it produces an output block of length fourending in two or one equals signs, respectively. These equals signsMUST be included on output, but input routinesMAY accept inputs whereone or two equals signs are dropped.¶
Whitespace inserted in the midst of the base-64 encoding, after theopening curly brace, or before the closing curly brace is ignored. Itis an error to have characters other than whitespace and base-64characters.¶
Note the difference between this base-64 encoding of anS-expression using curly braces ("{ }") and the base-64 encoding of anoctet-string using vertical bars ("| |") inSection 4.5.¶
This canonical representation is used for digital signaturepurposes and transport over channels not sensitive to specific octetvalues. It is uniquely defined for each S-expression. It is notparticularly readable, but that is not the point. It is intended tobe very easy to parse, reasonably economical, and uniquefor any S-expression. See[CANON1] and[CANON2].¶
The "canonical" form of an S-expression represents eachoctet-string in verbatim mode, and represents each list with no blanksseparating elements from each other or from the surroundingparentheses. See alsoSection 7.2.¶
Here are some examples of canonical representations ofS-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 (seeSection 7.3)are intended to provide a universal means of representingS-expressions for transport from one machine to another. The base-64encoding would be appropriate if the channel over which theS-expression is being sent might be sensitive to octets of somespecial values, such as an octet of all zero bits (NULL) or an octetof all one bits (DEL), or if the channel is sensitive to "line length"such that occasional line terminating whitespace is needed.¶
Here are two examples of an S-expression represented in basictransport mode:¶
(1:a1:b1:c) {KDE6YTE6YjE 6Yyk= }¶The second example above is the same S-expression as the firstencoded in base-64.¶
The "advanced transport" representation is intended to provide moreflexible and readable notations for documentation, design, debugging,and (in some cases) user interface.¶
The advanced transport representation allows all of theoctet-string representation forms described above inSection 4: quotedstrings, base-64, hexadecimal, tokens, representations of strings withomitted lengths, and so on. SeeSection 7.1.¶
ABNF is the Augmented Backus-Naur Form for syntax specifications asdefined in[RFC5234]. The ABNF for advancedrepresentation of S-expressions is given first, and the basic andcanonical forms are derived therefrom. The rule names below in allcapital letters are defined inAppendix B.1 of [RFC5234].¶
sexp = *whitespace value *whitespacewhitespace = SP / HTAB / vtab / CR / LF / ffvtab = %x0B ; vertical tabff = %x0C ; form feedvalue = string / ("(" *(value / whitespace) ")")string = [display] simple-stringdisplay = "[" *whitespace simple-string *whitespace "]" *whitespacesimple-string = verbatim / quoted-string / token / hexadecimal / base-64verbatim = decimal ":" *OCTET ; the length followed by a colon and the exact ; number of OCTETs indicated by the lengthdecimal = %x30 / (%x31-39 *DIGIT)quoted-string = [decimal] DQUOTE *(printable / escaped) DQUOTEprintable = %x20-21 / %x23-5B / %x5D-7E ; All US-ASCII printable but double-quote and ; backslashescaped = backslash (%x3F / %x61 / %x62 / %x66 / %x6E / %x72 / %x74 / %x76 / DQUOTE / quote / backslash / 3(%x30-37) / (%x78 2HEXDIG) / CR / LF / (CR LF) / (LF CR))backslash = %x5Cquote = %x27 ; single quotetoken = (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)¶c-sexp = c-string / ("(" *c-sexp ")")c-string = [ "[" verbatim "]" ] verbatim¶b-sexp = c-sexp / b-base-64b-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 invarious ways as well as to specify a different default display-hint.Here are some possible restrictions that might be considered:¶
As provided inSection 6, conformantimplementations will support canonical and basic representation, butsupport for advanced representation is not generally required. Thus,advanced representation can only be used in applications that mandateits support or where a capability discovery mechanism indicatessupport.¶
For processing, the S-expression would typically be parsed andrepresented in memory in a way that is more amenable to efficientprocessing. This document suggests two alternatives:¶
These are only sketched here, as they are only suggestive. Thecode in[SexpCode] illustrates these styles in moredetail.¶
Here there are separate records for simple-strings, strings, andlists or list nodes. An S-expression of the form ("abc" "de") couldbe encoded as two records for the simple-strings, two for the strings,and two for the list elements where a record is a relatively smallblock of memory and, except for simple-string, might have pointers init to other records. This is a fairly conventional representation asdiscussed 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 integerindicating the size (in octets) of the following representation. Here,k is an integer that depends on the implementation. It might beanywhere from 2 to 8, but it would be fixed for a given implementation;it determines the size of the objects that can be handled. Thetransport and canonical representations are independent of the choiceof k made by the implementation.¶
Although the lengths of lists are not given in the usualS-expression notations, it is easy to fill them in when parsing; whenyou reach a right parenthesis, you know how long the listrepresentation was and where to go back to fill in the missinglength.¶
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 securityconsiderations to S-expressions. A canonical form is required for theconsistent creation and verification of digital signatures. This isprovided inSection 6.2.¶
The default display-hint (seeSection 4.6) can bespecified for an application. Note that if S-expressions containinguntyped octet-strings represented for that application are processedby a different application, those untyped octet-string may be treatedas if they had a different display-hint.¶
This document has 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 thevarious S-expression formats specified here. In particular, see thefollowing -- likely incomplete -- list:¶
Special thanks toDaniel K. Gillmor for his extensive comments.¶
The comments and suggestions of the following are gratefully acknowledged:John Klensin andCaleb Malchik.¶
Special thanks toMarc 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:¶