INTERNET-DRAFT draft-kwiatkowski-base85-for-xml-02.txt P. Kwiatkowski Category: Experimental Expires: November 2004 May 2004 A Base-85 Encoding Suitable for XML Status of this Memo This document is an Internet-Draft and is subject to 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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract This memo proposes a base-85 text encoding for arbitrary binary data that is suitable for use in XML documents. This encoding requires approximately 15/16 of the space of the MIME Base64 encoding that is currently supported as a primitive datatype in the XML Schema definition language. In a UTF-8 encoded XML entity, Base85 therefore has 3/4 of the overhead of Base64. Kwiatkowski Expires - March 2004 [Page 1] A Base-85 Encoding Suitable for XML November 2004 Table of Contents 1. Introduction...................................................2 2. Basic Encoding.................................................3 2.1 Digits.....................................................3 2.2 Mapping....................................................4 3. Additional Features............................................5 3.1 Padding....................................................5 3.2 Zero-Compression...........................................6 4. Detailed Example...............................................7 4.1 Encoding...................................................7 4.2 Decoding...................................................8 5. Implementation Specifics......................................10 6. Comparison with Base64........................................11 Security Considerations..........................................11 Normative References.............................................12 Informative References...........................................12 Acknowledgments..................................................12 Author's Address.................................................12 Intellectual Property Rights.....................................12 Full Copyright Notice............................................13 1. Introduction The XML Schema definition language includes "base64Binary" as a primitive datatype for representing arbitrary binary information as text. The data is encoded using MIME's Base64 Content-Transfer- Encoding [MIME]. MIME uses a 65-character subset of US-ASCII to fulfill the portability requirements of a mail encoding, but since XML documents must support all Unicode characters, there is no reason to limit the choice of characters so strictly in that context. Base-85 encodings are a well-understood technique to encode 4 octets of arbitrary data in 5 printable characters, using an alphabet of only 85 distinct characters. Examples include PostScript's ASCII85Encode Filter and the btoa/atob utilities. However, these both indiscriminately use a contiguous range of printable characters. Since certain characters must be escaped in XML content, a non- contiguous set of characters must be used to represent the 85 "digits" needed for the encoding, but these can easily be mapped to and from the numbers 0-84 in constant time. A similar approach is described in RFC 1924 [RFC1924], but it must be emphasized that while that document was an "April 1" satire, the present memo is a serious proposal. Kwiatkowski Expires - March 2004 [Page 2] A Base-85 Encoding Suitable for XML November 2004 MIME's Base64 also requires that the number of characters in the encoded text must always be a multiple of 4, and uses a special padding character if necessary. There is no analogous requirement in the present proposal, although an optional padding character is supported. The key words "MUST" and "MUST NOT" in this document are to be interpreted as described in RFC 2119 [RFC2119]. 2. Basic Encoding The two main design decisions for a binary-as-text encoding are the subset of printable characters used and the mapping between the binary octets and characters. 2.1 Digits The 85 characters chosen in this proposal to serve as "digits" in the encoded string are as follows: 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefg hijklmnopqrstuvwxy!#$()*+,-./:;=?@^`{|}~z_ This set, and certain aspects of the above ordering, have been selected carefully. Of the 95 printable ASCII characters (including the space character), all but 10 must be used. The alphanumeric characters are obvious candidates for inclusion, so 10 of the remaining 33 printable characters must be excluded. The XML standard places strict constraints on the choice of characters [XML]. The ampersand character (&) and the left angle bracket (<) are excluded since these must be escaped in XML attribute values. The right angle bracket (>) must be escaped when it appears in the string "]]>", so it is safest to exclude that character and therefore guarantee that Base85-encoded data can be used in any context. The single-quote character (') must be escaped in attribute values delimited by single-quotes, and the double-quote character (") must be escaped in attribute values delimited by double-quotes. To avoid constraining the choice of quote character for an attribute value containing a Base85-encoded string, both of these characters are excluded. The space character is excluded, since sequences of space characters are replaced by a single space character during attribute-value normalization. Finally, since parameter entity references can appear in general entity value literals, and use a percent-sign (%) as a leading delimiter, this character is also excluded. Kwiatkowski Expires - March 2004 [Page 3] A Base-85 Encoding Suitable for XML November 2004 Wrapping Base85-encoded data in a CDATA section would allow all of the above characters (and forbid use of the right square bracket). However requiring a CDATA wrapper around all Base85-encoded data is both undesirable and unnecessary. This leaves the following 26 printable ASCII characters, 3 more of which can be excluded: !#$()*+,-./:;=?@[\]^_`{|}~ The backslash (\) is a sensible choice for exclusion since it is often used as an escape character. Finally, the left square bracket ([) and right square bracket (]) can serve as useful delimiters for Base85-encoded data in the midst of text strings, and are therefore excluded from the set. This alphabet of 85 characters is mapped to the numbers 0-84 in the order shown above. Note that the characters for the decimal digits and the upper-case letters from A to F are deliberately mapped to the numbers they represent in hexadecimal. 2.2 Mapping As with other base-85 schemes, octets in the binary stream are divided into groups ("quanta") of four. Each quantum is then converted to a 32-bit unsigned integer, which is in turn repeatedly divided by 85. The remainders form the digits of the Base85 "number", and these digits in the range 0-84 are mapped to the alphabet of characters defined above. Two interesting, and independent, design decisions are the order in which the remainders are listed in the encoded string, and how the octets are converted to a single integer. While most encoded strings will not be human-readable, 32-bit integers with values less than 16 will result in recognizable strings if a big-endian format is used for the remainders. However, these 32-bit integers will only have values of interest if a) the binary data happens to represent 32-bit integers, and b) the system architecture's endianness matches that chosen for the octet-to-integer conversion. A big-endian format therefore seems sensible for the remainders, given that XML is intended to be human-readable when possible. As for the octet-to-integer conversion, Network Byte Ordering (big- endian) is the natural choice for an XML encoding. Since this is only to improve readability in rare cases, there is no good reason to parameterize an encoding with its endianness. Kwiatkowski Expires - March 2004 [Page 4] A Base-85 Encoding Suitable for XML November 2004 The following example shows 8 octets of data (in hex notation) and the corresponding 10 characters in the Base85-encoded string: [00, 00, 00, 01, 00, 00, 00, 0F] => "000010000F" If the number of octets to be encoded is not an integral multiple of 4, the trailing 3, 2 or 1 bytes are encoded using the same rules to 4, 3 or 2 characters respectively: [00, 00, 00, 01, 00, 00, 0F] => "00001000F" [00, 00, 00, 01, 00, 0F] => "0000100F" [00, 00, 00, 01, 0F] => "000010F" When a Base85-encoded string is to be decoded back into binary octets, it is assumed that the number of characters to be decoded is known (MIME's Base64 makes this assumption, too, as the padding character is not always present). The conversion of the last quantum is handled as a special case: if it is 5, 4, 3 or 2 characters in length, it is known to represent 4, 3, 2 or 1 octets, respectively. This encoding scheme does not support bit strings of arbitrary length. The bits to be encoded must comprise an integral number of octets. 3. Additional Features Base-85 encodings leverage the fact that 85^5 > 2^32. Actually, 83 * 85^4 and 84^2 * 85^3 are also larger than 2^32, so it is possible to reserve certain values for one or two Base85 digits and use those to convey additional information. 3.1 Padding Some applications might prefer Base85-encoded strings to be padded to a given fixed length. A character outside the Base85 alphabet could be used, but the application would then be responsible for trimming the extra characters before passing the string to a standard Base85 decoder. It is possible to instead use one of the 85 characters as a padding character by disallowing it as the least significant digit in an encoded quantum. So, the last digit is effectively in "base-84" and the encoding/decoding algorithms must divide/multiply by 84 once instead of 85. The padding character is therefore the character that maps to the value 84; the underscore (_) is chosen for this purpose. Kwiatkowski Expires - March 2004 [Page 5] A Base-85 Encoding Suitable for XML November 2004 (The choice of the underscore character deliberately contrasts with the use of the equals (=) character as padding in Base32 and Base64, to emphasize the different role of padding characters in Base85.) The following examples illustrate the range of possible encoded strings: "00000" => [00, 00, 00, 00] (see Section 3.2) "zL@33" => [FF, FF, FF, FF] (see Section 3.2) "0000_" => [00, 00, 00] "Rs$$_" => [FF, FF, FF] "000__" => [00, 00] "9FF__" => [FF, FF] "00___" => [00] "33___" => [FF] Any number of underscores can be appended to an encoded string without altering its value. To remove the padding, the decoder simply has to strip trailing underscores from the string. Optional padding implies that a round-trip conversion from text to binary and back again might not yield the original text. However, as long as a client that cares about round-trip preservation passes consistent desired lengths to the encoder, the encoded text will always be the same. An encoding with no padding can be considered the canonical form of a Base85-encoded string. 3.2 Zero-Compression The public-domain btoa/atob utilities use the 'z' character to represent the special case of a quantum of 4 zero bytes. Base85 can use the same trick, without having to reserve an 86th character, by disallowing 'z' as the most significant digit in an encoded quantum. This only affects the encoding/decoding of 5- character quanta, in which the most significant digit can have a maximum value of 83. The 'z' character is deliberately mapped to the value 83 in the Base85 alphabet. While the underscore normally represents the value 84, if it is used as the most significant digit of a 5-character quantum, it is mapped to 83 instead. If a decoder encounters a 'z' character at the beginning of a quantum, that character is interpreted as an entire quantum of 4 zero bytes. To ensure that round-trip conversions yield the same result, the quantum "00000" is considered an encoding violation. Kwiatkowski Expires - March 2004 [Page 6] A Base-85 Encoding Suitable for XML November 2004 The following examples incorporate this modification: "00000" => encoding violation "z" => [00, 00, 00, 00] "zL@33" => [00, 00, 00, 00, CA, C1, 73] "00001" => [00, 00, 00, 01] "_L@33" => [FF, FF, FF, FF] "0000_" => [00, 00, 00] "000__" => [00, 00] "00___" => [00] "zz00_" => [00, 00, 00, 00, 00, 00, 00, 00, 00] "_00zz" => [FF, 35, 5A, 1B] 4. Detailed Example This section walks through the encoding and decoding of a sample octet sequence in more detail. 4.1 Encoding Beginning with the octet sequence: [FF, 3E, 79, 5F, 00, 00, 00, 00, 3C, C3] we isolate the first quantum of four octets and convert them to a single unsigned integer: FF3E795F hex = 4282284383 decimal To obtain the least significant encoded digit, we divide by 84 and note the remainder: 4282284383 / 84 = 50979575 rem 83 To obtain the remaining digits, from least to most significant, we repeatedly divide by 85 and note the remainders: 50979575 / 85 = 599759 rem 60 599759 / 85 = 7055 rem 84 7055 / 85 = 83 rem 0 83 / 85 = 0 rem 83 (The last division is clearly unnecessary in practice.) This yields the following digits (shown in decimal): (83, 0, 84, 60, 83) Kwiatkowski Expires - March 2004 [Page 7] A Base-85 Encoding Suitable for XML November 2004 These values are then used as indices into the Base85 alphabet, observing the exception that a leading 83 is represented with an underscore, rather than the 'z' character. We obtain the string: "_0_yz" Proceeding to the next quantum, we find four zero bytes, which we represent with a single 'z' character. Our encoded string is now: "_0_yzz" For the remaining quantum of 2 octets, we use the same process as for the first quantum, but generate 3 encoded digits instead of 5: 3CC3 hex = 15555 decimal 15555 / 84 = 185 rem 15 185 / 85 = 2 rem 15 2 / 85 = 0 rem 2 These digits map straightforwardly to the string "2FF", yielding the final encoding string: "_0_yzz2FF" This can be padded with an arbitrary number of underscores. In this example, we'll assume the client wishes to pad it to a total of 16 characters: "_0_yzz2FF_______" 4.2 Decoding To decode the above string, we begin by stripping off all trailing underscore characters: "_0_yzz2FF" We then inspect the first character to see if it is a 'z'. Since it is not, we isolate the first quantum of 5 characters and map them to decimal values based on their position in the Base85 alphabet. Since this is a quantum of size 5, we observe the exception that a leading underscore maps to 83 instead of the usual 84 (note that leading underscores will only arise with quanta of size 5): (83, 0, 84, 60, 83) Kwiatkowski Expires - March 2004 [Page 8] A Base-85 Encoding Suitable for XML November 2004 We now convert this to a single integer by following a process that corresponds to the repeated division above: ((((83 * 85) + 0) * 85 + 84) * 85 + 60) * 84 + 83 = 4282284383 decimal = FF3E795F hex Performing a big-endian conversion to bytes, we have the initial octets: [FF, 3E, 79, 5F] Examining the remainder of the string: "z2FF" we note that the first character is now a 'z'. This is immediately consumed as a quantum and 4 zero bytes are appended to the decoded result: [FF, 3E, 79, 5F, 00, 00, 00, 00] The remainder of the string is a single quantum comprising 3 characters, since it does not begin with a 'z': "2FF" We map these characters to the decimal digits (2, 15, 15) and once again multiply and add repeatedly to obtain a single integer: ((2 * 85) + 15) * 84 + 15 = 15555 decimal = 3CC3 hex Applying a big-endian conversion and appending the resulting octets to the decoded data, we get the final result: [FF, 3E, 79, 5F, 00, 00, 00, 00, 3C, C3] Kwiatkowski Expires - March 2004 [Page 9] A Base-85 Encoding Suitable for XML November 2004 5. Implementation Specifics Section 2 of RFC 3548 provides several specific implementation recommendations for base encoded data [RFC3548]. In particular, it mandates that: Implementations MUST NOT add line feeds to base encoded data unless the specification referring to this document explicitly directs base encoders to add line feeds after a specific number of characters. and: Implementations MUST reject the encoding if it contains characters outside the base alphabet when interpreting base encoded data, unless the specification referring to this document explicitly states otherwise. Such specifications may, as MIME does, instead state that characters outside the base encoding alphabet should simply be ignored when interpreting data ("be liberal in what you accept"). Note that this means that any CRLF constitute "non alphabet characters" and are ignored. In general, implementations MUST follow the above recommendations for Base85, too, unless the specification referring to this document explicitly states otherwise. However, in the specific case of an XML document, it is reasonable to allow, and ignore, whitespace characters (space, CR, LF or TAB) in the midst of a Base85-encoded string. In Base85, padding is optional, but implementations should know when it might be present, given that it can affect round-trip behavior. Hence, this recommendation for Base85: Implementations MUST NOT include pad characters at the end of encoded data unless the specification referring to this document explicitly states otherwise. A C++ reference implementation of a Base85 encoder/decoder can be downloaded at: https://sourceforge.net/projects/base85-for-xml This source code has been released to the public domain. Kwiatkowski Expires - March 2004 [Page 10] A Base-85 Encoding Suitable for XML November 2004 6. Comparison with Base64 In a UTF-8 encoded XML entity, Base85-encoded data will be about 25 percent larger than the unencoded data. In other character encodings, such as UTF-16, Base85 may be far from optimal, but it will still compare favorably with Base64. Asymptotically, Base85 encoded data requires 15/16 (93.75%) of the storage needed by Base64. For long runs of zero bytes, the asymptote shrinks to 3/16 (18.75%). The comparison is slightly more favorable for shorter blocks of data. Ignoring zero-compression, data blocks of 1 to 32 bytes in length will require, on average, 89.84% of the space needed by Base64 (this is largely due to the padding requirement in Base64). In particular, 128-bit numbers can be represented with just 20 characters in Base85, compared to 24 in Base64, so the ratio is 83.33% for that common case. Put another way, Base85 asymptotically has only 3/4 of the overhead of Base64 (in a UTF-8 encoded entity). For a 128-bit number, it has 1/2 the overhead. Security Considerations When implementing base encoding and decoding, care should be taken not to introduce vulnerabilities to buffer overflow attacks, or other attacks on the implementation. A decoder should not break on invalid input including, for example, embedded NUL characters (ASCII 0). If invalid digits are ignored, instead of causing rejection of the entire encoding (as recommended), a covert channel that can be used to "leak" information is made possible. The implications of this should be understood in applications that do not follow the recommended practice. Whitespace in the midst of Base85-encoded data in XML documents can of course form such a covert channel. However, this is true for all whitespace in an XML document, so applications that read and write XML documents must be aware of this anyway. Base encoding visually hides otherwise easily recognized information, such as passwords, but does not provide any computational confidentiality. This has been known to cause security incidents when, for example, a user reports details of a network protocol exchange (perhaps to illustrate some other problem) and accidentally reveals the password because he or she is unaware that the base encoding does not protect the password. Kwiatkowski Expires - March 2004 [Page 11] A Base-85 Encoding Suitable for XML November 2004 Normative References [XML] Extensible Markup Language (XML) 1.0 (Second Edition), T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler (Eds.) http://www.w3.org/TR/2000/REC-xml-20001006, 6 October 2000. [RFC2119] Key words for use in RFCs to Indicate Requirement Levels, S. Bradner, BCP 14, RFC 2119, March 1997. Informative References [MIME] Multipurpose Internet Mail Extensions (MIME) Part One: Format of Internet Message Bodies, N. Freed, N. Borenstein, RFC 2045, November 1996. [RFC3548] The Base16, Base32, and Base64 Data Encodings, S. Josefsson, RFC 3548, July 2003. [RFC1924] A Compact Representation of IPv6 Addresses, R. Elz, RFC 1924, 1 April 1996. (Once again, the present memo is a serious proposal, despite the fact that it references an "April 1" RFC.) Acknowledgments I wish to thank Robert Elz for promptly answering my questions regarding his memo, and for commenting on this document. I also wish to thank Simon Josefsson for letting me re-use the text of RFC 3548's security section, and for his detailed responses to my questions about that document. Author's Address Paul Kwiatkowski PMB 785 15600 NE 8th Street, Suite B1 Bellevue, WA 98008 USA Email: paulkw@paulkw.com Intellectual Property Rights The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to Kwiatkowski Expires - March 2004 [Page 12] A Base-85 Encoding Suitable for XML November 2004 pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. Full Copyright Notice Copyright (C) The Internet Society (2003). All rights reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Kwiatkowski Expires - March 2004 [Page 13]