INTERNET-DRAFT Greg Hudson Expires: March 1, 2000 ghudson@mit.edu MIT Simple Protocol Application Data Encoding draft-hudson-spade-03.txt 1. Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Please send comments to ghudson@mit.edu. 2. Abstract This document describes a simple scheme for encoding network protocol data and a simple notation for describing protocol data elements. All encodings are self-terminating (you know when you've reached the end) and assume that the decoder knows what type of protocol element it is expecting. 3. Encoding This encoding scheme uses the ASCII translation of characters into bytes except when otherwise noted. Protocol elements are encoded as follows: A byte: a byte encodes itself. So "a" encodes as "a" and so forth. An integer: a sequence of decimal digits followed by a colon. For instance, the number 27 encodes as "27:". Negative integers are preceded by a minus sign, so -27 encodes as "-27:". Excess leading zeroes are not allowed, and zero must be encoded as "0:" (not as "-0:"). Thus each integer has a single encoding. A symbol: a sequence of letters, numbers, and dashes, beginning with a letter, followed by a colon. Case is significant. For instance, the symbol "foo" encodes as "foo:". A list of : an integer giving the number of elements in the list, followed by the elements of the list. For instance, the list of numbers "1", "2", and "3" encodes as "3:1:2:3:". A structure: a collection of dissimilar elements can simply be concatenated together. For instance, a structure containing the number 3 and the list of bytes "ab" encodes as "3:2:ab". A union value: a symbol giving the type of element, an integer giving the length of the encoding of the element's data, and the data itself. For instance, an element of type "foo" with the same data as in the structure example above would be encoded as "foo:6:3:2:ab". If there is no data to be encoded, a data length of 0 should be given, e.g. "bar:0:". Of these types, the union value is the most complicated. It should be used where a protocol needs extensibility, such as for a command set, and avoided elsewhere if possible. Following is an ABNF (RFC 2234) for the wire encoding. The grammar is highly ambiguous, since the encoding assumes that the decoder has auxiliary type information: element = byte / integer / symbol / list / struct / union-val byte = OCTET unsigned = ("0" / PDIGIT *DIGIT) ":" integer = unsigned / ("-" PDIGIT *DIGIT ":") symbol = ALPHA *(ALPHA / DIGIT / "-") ":" list = unsigned *element ; unsigned determines the number of elements ; all elements must be of same type struct = 1*element ; number, type, and order depend on type union-val = symbol unsigned [element] ; unsigned is the length of the element ; unsigned is 0 if element is omitted PDIGIT = %x31-39 ; 1-9 4. Notation This notation gives a scheme for describing protocol element types and giving them names for the purpose of semantic descriptions. A variable declaration associates a name to be used in semantic descriptions with a type. Variable names are valid symbols beginning with a lowercase letter. Variable declarations end with a line break, and are written as follows: A byte: "Byte " An integer: "Integer " A symbol: "Symbol " A list of : "List[] " A structure named : " " A union named : " " As a notational short-hand, "String" may be used as a synonym for "List[Byte]". Structure and union names are valid symbols beginning with a capital letter. A structure definition is written as: structure { . . . } Unions are defined as: union { : . . . } As a special case, if there is no data for a particular union tag, "Null" can be written in place of a variable declaration. Here is an example of two structure definitions which might be used to describe a mail message: structure Header { String name String value } structure Message { List[Header] headers String body } Here is an example of a union definition which might be used together with the above structure definitions to describe a command set: union Command { send: Message m help: Null quit: Null } A quit command would be encoded as "quit:0:". If I have a message with two headers, one with name "From" and value "Greg" and another with name "To" and value "Bob", and the message body is "Test", then I would encode a command to send this message as: send:29:2:4:From4:Greg2:To3:Bob4:Test 5. Rationale The primary goal of this encoding scheme is simplicity. Protocol implementors should not have to read a book to understand how data is encoded. For want of a simple encoding scheme, IETF protocols have been turning to ASN.1's basic encoding rules, which are highly complicated and which have presented a barrier to implementation in practice. Two secondary goals of this encoding scheme are human readability and space efficiency. These goals are of course at odds; integers could be encoded more compactly by using more than ten values per byte, for instance, at the expense of making it more difficult to examine ASCII translations of protocol data. The tagged union encoding provides easy extensibility in most protocols. A protocol can find the end of the encoding of a tagged union element even if it doesn't know the data types for the individual tags. This encoding does not include a length field for structures or an overall length field for lists. Thus, it is impossible to skip to the end of a structure or list without decoding it. This decision was a tradeoff; it simplifies encoding and uses space more efficiently in return for making certain decoding situations more complicated. 6. Comparisons This section compares SPADE to several previous wire encodings, including XDR (RFC 1832), CDR (CORBA/IIOP 2.3 section 15.3), ABNF (RFC 2234), ASN.1 (ITU-T X.680-X.691), and XML (W3 REC-XML). XDR is similar in philosophy to SPADE: data can only be decoded with auxiliary type information, and simple schemes are used to encode structures and lists. However, XDR made tradeoffs which make the encoding more complex and less general than SPADE. Here are the major differences: * XDR uses a fixed-length binary encoding for integers (usually 32-bit) and enforces four-byte alignment on the encoding of all data types, so that a C implementation on most platforms can byte-swap an integer encoding and cast it to the appropriate type. As a result, there are two different sizes of integers, integers are constrained by any XDR-using protocol to a certain range, integer encodings are not human-readable in an ASCII protocol trace, and padding is required for the encoding and decoding of strings. * XDR needlessly distinguishes between "opaque data" (bytes) and "strings" (ASCII characters). * XDR's "discriminated union" does not provide the length field needed to extend the union in later revisions of a protocol. As a result, unions have less overhead, but it is harder to make a protocol extensible. * XDR does not provide symbols; instead, it provides enumerations which map symbols to numbers. In most cases, such mappings are unnecessary and a debugging hindrance. The discriminant of an XDR union must be a number. * XDR has more types: it provides floating point numbers, fixed-length lists, and optional data, and it distinguishes between signed and unsigned integers. CDR is similar to XDR in all of the respects noted above. It is slightly more complicated than XDR: it provides a wider variety of integral types, has different alignment constraints for different types, and allows integral types to be encoded in either little-endian or big-endian form (XDR always uses big-endian). ABNF is not really a wire encoding scheme at all; it is a scheme for describing syntaxes. It can be used to describe any wire encoding, but does not in itself nail down how integers, strings, lists, etc. should be encoded. As a notational device, it is not geared towards describing data types; the description of a data type would have to be intrinsically linked to its encoding, which is undesirable, and ABNF has no notion of counting, so it cannot link the length field of a list with the number of list elements provided. ASN.1 is a very large and complicated specification. Even third-party attempts to describe the ASN.1 basic and distinguished encoding rules tend to be long and difficult to understand. Some differences between ASN.1 with the Distinguished Encoding Rules (DER) and SPADE are: * The DER provide explicit type information in the encoding. As a result, a DER decoder can turn a wire encoding into a data structure with no auxiliary type information, but the encoding is space-inefficient and the encoding scheme becomes much more complex. Someone writing an encoder by hand for an ASN.1-using protocol will be constantly adding in magic numbers which are always the same. * The DER provide an overall length field for lists ("SEQUENCE OF"), but not an element count. So a decoder can easily skip over a list without parsing the elements, but it cannot allocate memory for the list elements until it has decoded the list. * The DER provide an overall length field for structures ("SEQUENCE"), making it easy to skip over structures without decoding their contents. The cost is a less space-efficient protocol. * The DER rely heavily on bit-packing to encode type tags and lengths, resulting in a very complex wire encoding which is nonetheless not space-efficient. * ASN.1 needlessly distingishes between "OCTET STRING", "IA5String" (ASCII), "PrintableString" (restricted ASCII), and "T61String" (extended ASCII). A wire encoding does not need to get into the interpretation of octets as characters. XML takes a different view of encoding protocol data than SPADE, ASN.1, or XDR. The only "primitive data type" is character data, which is arranged into a tree of elements according to a Document Type Definition (DTD). Protocol data is encoded in a markup language instead of being packed precisely according to rigid data types. Some resulting differences between XML and SPADE are: * An XML encoding will be much more verbose than a SPADE encoding (or even an ASN.1 DER encoding in most cases), due to the addition of element names. Of course, this makes it easier for a human reader of a protocol dump to guess the meaning of each data element. * Because XML uses markup rather than advance-length encoding, an encoder or decoder has more quoting issues to deal with. This and other facets of XML make XML a much more complicated specification than SPADE. * An XML DTD is generally not understandable to a reader not skilled in XML, whereas a SPADE or XDR or ASN.1 data type generally is. * Hand-coding an encoder or decoder for an XML-using protocol is probably a lost cause. 7. Security Considerations For maximum generality, this encoding scheme places no limits on the length of any data type. This could lead to denial of service attacks against implementations of protocols using this encoding ("here follows a string of length two gazillion"). It does not seem appropriate to choose limits in the wire encoding to prevent this sort of attack, so guarding against these attacks will have to be the responsibility of particular protocols or their implementations. 8. Acknowledgements Thanks to Elliot Schwartz for suggesting the name. Thanks to Chris Newman for providing the basis for the ABNF for the wire encoding, and other useful suggestions.