diff options
Diffstat (limited to 'doc/rfc/rfc6256.txt')
| -rw-r--r-- | doc/rfc/rfc6256.txt | 955 |
1 files changed, 955 insertions, 0 deletions
diff --git a/doc/rfc/rfc6256.txt b/doc/rfc/rfc6256.txt new file mode 100644 index 0000000..9f89164 --- /dev/null +++ b/doc/rfc/rfc6256.txt @@ -0,0 +1,955 @@ + + + + + + +Internet Research Task Force (IRTF) W. Eddy +Request for Comments: 6256 MTI Systems +Category: Informational E. Davies +ISSN: 2070-1721 Folly Consulting + May 2011 + + + Using Self-Delimiting Numeric Values in Protocols + +Abstract + + Self-Delimiting Numeric Values (SDNVs) have recently been introduced + as a field type in proposed Delay-Tolerant Networking protocols. + SDNVs encode an arbitrary-length non-negative integer or arbitrary- + length bitstring with minimum overhead. They are intended to provide + protocol flexibility without sacrificing economy and to assist in + future-proofing protocols under development. This document describes + formats and algorithms for SDNV encoding and decoding, along with + notes on implementation and usage. This document is a product of the + Delay-Tolerant Networking Research Group and has been reviewed by + that group. No objections to its publication as an RFC were raised. + +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 Research Task Force + (IRTF). The IRTF publishes the results of Internet-related research + and development activities. These results might not be suitable for + deployment. This RFC represents the consensus of the Delay-Tolerant + Networking Research Group of the Internet Research Task Force (IRTF). + Documents approved for publication by the IRSG are not a candidate + for any level of Internet Standard; see Section 2 of RFC 5741. + + Information about the current status of this document, any errata, + and how to provide feedback on it may be obtained at + http://www.rfc-editor.org/info/rfc6256. + + + + + + + + + + + + + +Eddy & Davies Informational [Page 1] + +RFC 6256 Using SDNVs May 2011 + + +Copyright Notice + + Copyright (c) 2011 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 + (http://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. + +Table of Contents + + 1. Introduction ....................................................2 + 1.1. Problems with Fixed-Value Fields ...........................3 + 1.2. SDNVs for DTN Protocols ....................................4 + 1.3. SDNV Usage .................................................5 + 2. Definition of SDNVs .............................................6 + 3. Basic Algorithms ................................................8 + 3.1. Encoding Algorithm .........................................8 + 3.2. Decoding Algorithm .........................................9 + 3.3. Limitations of Implementations ............................10 + 4. Comparison to Alternatives .....................................10 + 5. Security Considerations ........................................13 + 6. Acknowledgements ...............................................13 + 7. Informative References .........................................14 + Appendix A. SDNV Python Source Code ...............................15 + +1. Introduction + + This document is a product of the Internet Research Task Force (IRTF) + Delay-Tolerant Networking (DTN) Research Group (DTNRG). The document + has received review and support within the DTNRG, as discussed in the + Acknowledgements section of this document. + + This document begins by describing the drawbacks of using fixed-width + protocol fields. It then provides some background on the Self- + Delimiting Numeric Values (SDNVs) proposed for use in DTN protocols, + and motivates their potential applicability in other networking + protocols. The DTNRG has created SDNVs to meet the challenges it + attempts to solve, and it has been noted that SDNVs closely resemble + certain constructs within ASN.1 and even older ITU protocols, so the + problems are not new or unique to DTN. SDNVs focus strictly on + numeric values or bitstrings, while other mechanisms have been + developed for encoding more complex data structures, such as ASN.1 + + + + + +Eddy & Davies Informational [Page 2] + +RFC 6256 Using SDNVs May 2011 + + + encoding rules and Haverty's Message Services Data Transmission + Protocol (MSDTP) [RFC0713]. Because of this focus, SDNVs can be + quickly implemented with only a small amount of code. + + SDNVs are tersely defined in both the Bundle Protocol [RFC5050] and + Licklider Transmission Protocol (LTP) [RFC5326] specifications, due + to the flow of document production in the DTNRG. This document + clarifies and further explains the motivations and engineering + decisions behind SDNVs. + +1.1. Problems with Fixed-Value Fields + + Protocol designers commonly face an optimization problem in + determining the proper size for header fields. There is a strong + desire to keep fields as small as possible, in order to reduce the + protocol's overhead and also allow for fast processing. Since + protocols can be used for many years (even decades) after they are + designed, and networking technology has tended to change rapidly, it + is not uncommon for the use, deployment, or performance of a + particular protocol to be limited or infringed upon by the length of + some header field being too short. Two well-known examples of this + phenomenon are the TCP-advertised receive window and the IPv4 address + length. + + TCP segments contain an advertised receive window field that is fixed + at 16 bits [RFC0793], encoding a maximum value of around 65 + kilobytes. The purpose of this value is to provide flow control, by + allowing a receiver to specify how many sent bytes its peer can have + outstanding (unacknowledged) at any time, thus allowing the receiver + to limit its buffer size. As network speeds have grown by several + orders of magnitude since TCP's inception, the combination of the 65 + kilobyte maximum advertised window and long round-trip times + prevented TCP senders from being able to achieve the high throughput + that the underlying network supported. This limitation was remedied + through the use of the Window Scale option [RFC1323], which provides + a multiplier for the advertised window field. However, the Window + Scale multiplier is fixed for the duration of the connection, + requires support from each end of a TCP connection, and limits the + precision of the advertised receive window, so this is certainly a + less-than-ideal solution. Because of the field width limit in the + original design however, the Window Scale is necessary for TCP to + reach high sending rates. + + An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note, + an early version of the IP header format specification in [IEN21] + used variable-length addresses in multiples of 8 bits up to 120 + bits). Due to the way that subnetting and assignment of address + blocks was performed, the number of IPv4 addresses has been seen as a + + + +Eddy & Davies Informational [Page 3] + +RFC 6256 Using SDNVs May 2011 + + + limit to the growth of the Internet [Hain05]. Two divergent paths to + solve this problem have been the use of Network Address Translators + (NATs) and the development of IPv6. NATs have caused a number of + other issues and problems [RFC2993], leading to increased complexity + and fragility, as well as forcing workarounds to be engineered for + many other protocols to function within a NATed environment. The + IPv6 solution's transitional work has been underway for several + years, but has still only just begun to have visible impact on the + global Internet. + + Of course, in both the case of the TCP receive window and IPv4 + address length, the field size chosen by the designers seemed like a + good idea at the time. The fields were more than big enough for the + originally perceived usage of the protocols, and yet were small + enough to allow the headers to remain compact and relatively easy and + efficient to parse on machines of the time. The fixed sizes that + were defined represented a trade-off between the scalability of the + protocol versus the overhead and efficiency of processing. In both + cases, these engineering decisions turned out to be painfully + restrictive in the longer term. + +1.2. SDNVs for DTN Protocols + + In specifications for the DTN Bundle Protocol (BP) [RFC5050] and + Licklider Transmission Protocol (LTP) [RFC5326], SDNVs have been used + for several fields including identifiers, payload/header lengths, and + serial (sequence) numbers. SDNVs were developed for use in these + types of fields, to avoid sending more bytes than needed, as well as + avoiding fixed sizes that may not end up being appropriate. For + example, since LTP is intended primarily for use in long-delay + interplanetary communications [RFC5325], where links may be fairly + low in capacity, it is desirable to avoid the header overhead of + routinely sending a 64-bit field where a 16-bit field would suffice. + Since many of the nodes implementing LTP are expected to be beyond + the current range of human spaceflight, upgrading their on-board LTP + implementations to use longer values if the defined fields are found + to be too short would also be problematic. Furthermore, extensions + similar in mechanism to TCP's Window Scale option are unsuitable for + use in DTN protocols since, due to high delays, DTN protocols must + avoid handshaking and configuration parameter negotiation to the + greatest extent possible. All of these reasons make the choice of + SDNVs for use in DTN protocols attractive. + + + + + + + + + +Eddy & Davies Informational [Page 4] + +RFC 6256 Using SDNVs May 2011 + + +1.3. SDNV Usage + + In short, an SDNV is simply a way of representing non-negative + integers (both positive integers of arbitrary magnitude and 0), + without expending much unnecessary space. This definition allows + SDNVs to represent many common protocol header fields, such as: + + o Random identification fields as used in the IPsec Security + Parameters Index or in IP headers for fragment reassembly (Note: + the 16-bit IP ID field for fragment reassembly was recently found + to be too short in some environments [RFC4963]). + + o Sequence numbers as in TCP or the Stream Control Transmission + Protocol (SCTP). + + o Values used in cryptographic algorithms such as RSA keys, Diffie- + Hellman key agreement, or coordinates of points on elliptic + curves. + + o Message lengths as used in file transfer protocols. + + o Nonces and cookies. + + As any bitfield can be interpreted as an unsigned integer, SDNVs can + also encode arbitrary-length bitfields, including bitfields + representing signed integers or other data types; however, this + document assumes SDNV encoding and decoding in terms of unsigned + integers. Implementations may differ in the interface that they + provide to SDNV encoding and decoding functions, in terms of whether + the values are numeric, bitfields, etc.; this detail does not alter + the representation or algorithms described in this document. + + The use of SDNVs rather than fixed-length fields gives protocol + designers the ability to ameliorate the consequences of making + difficult-to-reverse field-sizing decisions, as the SDNV format grows + and shrinks depending on the particular value encoded. SDNVs do not + necessarily provide optimal encodings for values of any particular + length; however, they allow protocol designers to avoid potential + blunders in assigning fixed lengths and remove the complexity + involved with either negotiating field lengths or constructing + protocol extensions. However, if SDNVs are used to encode bitfields, + it is essential that the sender and receiver have a consistent + interpretation of the decoded value. This is discussed further in + Section 2. + + To our knowledge, at this time, no IETF transport or network-layer + protocol designed for use outside of the DTN domain has proposed to + use SDNVs; however, there is no inherent reason not to use SDNVs more + + + +Eddy & Davies Informational [Page 5] + +RFC 6256 Using SDNVs May 2011 + + + broadly in the future. The two examples cited here, of fields that + have proven too small in general Internet protocols, are only a small + sampling of the much larger set of similar instances that the authors + can think of. Outside the Internet protocols, within ASN.1 and + previous ITU protocols, constructs very similar to SDNVs have been + used for many years due to engineering concerns very similar to those + facing the DTNRG. + + Many protocols use a Type-Length-Value method for encoding variable- + length fields (e.g., TCP's options format or many of the fields in + the Internet Key Exchange Protocol version 2 (IKEv2)). An SDNV is + equivalent to combining the length and value portions of this type of + field, with the overhead of the length portion amortized out over the + bytes of the value. The penalty paid for this in an SDNV may be + several extra bytes for long values (e.g., 1024-bit RSA keys). See + Section 4 for further discussion and a comparison. + + As is shown in later sections, for large values, the current SDNV + scheme is fairly inefficient in terms of space (1/8 of the bits are + overhead) and not particularly easy to encode/decode in comparison to + alternatives. The best use of SDNVs may often be to define the + Length field of a TLV structure to be an SDNV whose value is the + length of the TLV's Value field. In this way, one can avoid forcing + large numbers from being directly encoded as an SDNV, yet retain the + extensibility that using SDNVs grants. + +2. Definition of SDNVs + + Early in the work of the DTNRG, it was agreed that the properties of + an SDNV were useful for DTN protocols. The exact SDNV format used by + the DTNRG evolved somewhat over time before the publication of the + initial RFCs on LTP and BP. An earlier version (see the initial + version of LTP Internet Draft [BRF04]) bore a resemblance to the + ASN.1 [ASN1] Basic Encoding Rules (BER) [X.690] for lengths (Section + 8.1.3 of X.690). The current SDNV format is the one used by ASN.1 + BER for encoding tag identifiers greater than or equal to 31 (Section + 8.1.2.4.2 of X.690). A comparison between the current SDNV format + and the early SDNV format is made in Section 4. + + The format currently used is very simple. Before encoding, an + integer is represented as a left-to-right bitstring beginning with + its most significant bit and ending with its least significant bit. + If the bitstring's length is not a multiple of 7, then the string is + left-padded with zeros. When transmitted, the bits are encoded into + a series of bytes. The low-order 7 bits of each byte in the encoded + format are taken left-to-right from the integer's bitstring + + + + + +Eddy & Davies Informational [Page 6] + +RFC 6256 Using SDNVs May 2011 + + + representation. The most significant bit of each byte specifies + whether it is the final byte of the encoded value (when it holds a + 0), or not (when it holds a 1). + + For example: + + o 1 (decimal) is represented by the bitstring "0000001" and encoded + as the single byte 0x01 (in hexadecimal). + + o 128 is represented by the bitstring "10000001 00000000" and + encoded as the bytes 0x81 followed by 0x00. + + o Other values can be found in the test vectors of the source code + in Appendix A. + + To be perfectly clear, and avoid potential interoperability issues + (as have occurred with ASN.1 BER time values), we explicitly state + two considerations regarding zero-padding. (1) When encoding SDNVs, + any leading (most significant) zero bits in the input number might be + discarded by the SDNV encoder. Protocols that use SDNVs should not + rely on leading-zeros being retained after encoding and decoding + operations. (2) When decoding SDNVs, the relevant number of leading + zeros required to pad up to a machine word or other natural data unit + might be added. These are put in the most significant positions in + order to not change the value of the number. Protocols using SDNVs + should consider situations where lost zero-padding may be + problematic. + + The issues of zero-padding are particularly relevant where an SDNV is + being used to represent a bitfield to be transmitted by a protocol. + The specification of the protocol and any associated IANA registry + should specify the allocation and usage of bit positions within the + unencoded field. Unassigned and reserved bits in the unencoded field + will be treated as zeros by the SDNV encoding prior to transmission. + Assuming the bit positions are numbered starting from 0 at the least + significant bit position in the integer representation, then if + higher-numbered positions in the field contain all zeros, the + encoding process may not transmit these bits explicitly (e.g., if all + the bit positions numbered 7 or higher are zeros, then the + transmitted SDNV can consist of just one octet). On reception, the + decoding process will treat any untransmitted higher-numbered bits as + zeros. To ensure correct operation of the protocol, the sender and + receiver must have a consistent interpretation of the width of the + bitfield. This can be achieved in various ways: + + o the bitfield width is implicitly defined by the version of the + protocol in use in the sender and receiver, + + + + +Eddy & Davies Informational [Page 7] + +RFC 6256 Using SDNVs May 2011 + + + o sending the width of the bitfield explicitly in a separate item, + + o the higher-numbered bits can be safely ignored by the receiver + (e.g., because they represent optimizations), or + + o marking the highest-numbered bit by prepending a '1' bit to the + bitfield. + + The protocol specification must record how the consistent + interpretation is achieved. + + The SDNV encoding technique is also known as Variable Byte Encoding + (see Section 5.3.1 of [Manning09]) and is equivalent to Base-128 + Elias Gamma Encoding (see Section 5.3.2 of [Manning09] and Section + 3.5 of [Sayood02]). However, the primary motivation for SDNVs is to + provide an extensible protocol framework rather than optimal data + compression, which is the motivation behind the other uses of the + technique. [Manning09] points out that the key feature of this + encoding is that it is "prefix free" meaning that no code is a prefix + of any other, which is an alternative way of expressing the self- + delimiting property. + +3. Basic Algorithms + + This section describes some simple algorithms for creating and + parsing SDNV fields. These may not be the most efficient algorithms + possible, however, they are easy to read, understand, and implement. + Appendix A contains Python source code implementing the routines + described here. The algorithms presented here are convenient for + converting between an internal data block and serialized data stream + associated with a transmission device. Other approaches are possible + with different efficiencies and trade-offs. + +3.1. Encoding Algorithm + + There is a very simple algorithm for the encoding operation that + converts a non-negative integer (value n, of length 1+floor(log n) + bits) into an SDNV. This algorithm takes n as its only argument and + returns a string of bytes: + + o (Initial Step) Set a variable X to a byte sharing the least + significant 7 bits of n, and with 0 in the most significant bit, + and a variable Y to n, right-shifted by 7 bits. + + o (Recursion Step) If Y == 0, return X. Otherwise, set Z to the + bitwise-or of 0x80 with the 7 least significant bits of Y, and + append Z to X. Right-shift Y by 7 bits and repeat the Recursion + Step. + + + +Eddy & Davies Informational [Page 8] + +RFC 6256 Using SDNVs May 2011 + + + This encoding algorithm has a time complexity of O(log n), since it + takes a number of steps equal to ceil(n/7), and no additional space + beyond the size of the result (8/7 log n) is required. One aspect of + this algorithm is that it assumes strings can be efficiently appended + to new bytes. One way to implement this is to allocate a buffer for + the expected length of the result and fill that buffer one byte at a + time from the right end. + + If, for some reason, an implementation requires an encoded SDNV to be + some specific length (possibly related to a machine word), any + leftmost zero-padding included needs to properly set the high-order + bit in each byte of padding. + +3.2. Decoding Algorithm + + Decoding SDNVs is a more difficult operation than encoding them, due + to the fact that no bound on the resulting value is known until the + SDNV is parsed, at which point the value itself is already known. + This means that if space is allocated in advance to hold the value + that results from decoding an SDNV, in general, it is not known + whether this space will be large enough until it is 7 bits away from + being overflowed. However, as specified in Section 3.3, protocols + using SDNVs must specify the largest number of bits that an + implementation is expected to handle, which mitigates this problem. + + o (Initial Step) Set the result to 0. Set an index to the first + byte of the encoded SDNV. + + o (Recursion Step) Shift the result left 7 bits. Add the low-order + 7 bits of the value at the index to the result. If the high-order + bit under the pointer is a 1, advance the index by one byte within + the encoded SDNV and repeat the Recursion Step, otherwise return + the current value of the result. + + This decoding algorithm takes no more additional space than what is + required for the result (7/8 the length of the SDNV) and the pointer. + The complication is that before the result can be left-shifted in the + Recursion Step, an implementation needs to first make sure that this + will not cause any bits to be lost, and re-allocate a larger piece of + memory for the result, if required. The pure time complexity is the + same as for the encoding algorithm given, but if re-allocation is + needed due to the inability to predict the size of the result, + decoding may be slower. + + These decoding steps include removal of any leftmost zero-padding + that might be used by an encoder to create encodings of a certain + length. + + + + +Eddy & Davies Informational [Page 9] + +RFC 6256 Using SDNVs May 2011 + + +3.3. Limitations of Implementations + + Because of efficiency considerations or convenience of internal + representation of decoded integers, implementations may choose to + limit the number of bits in SDNVs that they will handle. To avoid + interoperability problems, any protocol that uses SDNVs must specify + the largest number of bits in an SDNV that an implementation of that + protocol is expected to handle. + + For example, Section 4.1 of [RFC5050] specifies that implementations + of the DTN Bundle Protocol are not required to handle SDNVs with more + than 64 bits in their unencoded value. Accordingly, integer values + transmitted in SDNVs have an upper limit and SDNV-encoded flag fields + must be limited to 64 bit positions in any future revisions of the + protocol unless the restriction is altered. + +4. Comparison to Alternatives + + This section compares three alternative ways of implementing the + concept of SDNVs: (1) the TLV scheme commonly used in the Internet + family, and many other families of protocols, (2) the old style of + SDNVs (both the SDNV-8 and SDNV-16) defined in an early stage of + LTP's development [BRF04], and (3) the current SDNV format. + + The TLV method uses two fixed-length fields to hold the Type and + Length elements that then imply the syntax and semantics of the Value + element. This is only similar to an SDNV in that the value element + can grow or shrink within the bounds capable of being conveyed by the + Length field. Two fundamental differences between TLVs and SDNVs are + that through the Type element, TLVs also contain some notion of what + their contents are semantically, while SDNVs are simply generic non- + negative integers, and protocol engineers still have to choose fixed- + field lengths for the Type and Length fields in the TLV format. + + Some protocols use TLVs where the value conveyed within the Length + field needs to be decoded into the actual length of the Value field. + This may be accomplished through simple multiplication, left- + shifting, or a look-up table. In any case, this tactic limits the + granularity of the possible Value lengths, and can contribute some + degree of bloat if Values do not fit neatly within the available + decoded Lengths. + + In the SDNV format originally used by LTP, parsing the first byte of + the SDNV told an implementation how much space was required to hold + the contained value. There were two different types of SDNVs defined + for different ranges of use. The SDNV-8 type could hold values up to + 127 in a single byte, while the SDNV-16 type could hold values up to + 32,767 in 2 bytes. Both formats could encode values requiring up to + + + +Eddy & Davies Informational [Page 10] + +RFC 6256 Using SDNVs May 2011 + + + N bytes in N+2 bytes, where N<127. The major difference between this + old SDNV format and the current SDNV format is that the new format is + not as easily decoded as the old format was, but the new format also + has absolutely no limitation on its length. + + The advantage in ease of parsing the old format manifests itself in + two aspects: (1) the size of the value is determinable ahead of time, + in a way equivalent to parsing a TLV, and (2) the actual value is + directly encoded and decoded, without shifting and masking bits as is + required in the new format. For these reasons, the old format + requires less computational overhead to deal with, but is also very + limited in that it can only hold a 1024-bit number, at maximum. + Since according to IETF Best Current Practices, an asymmetric + cryptography key needed to last for a long term requires using moduli + of over 1228 bits [RFC3766], this could be seen as a severe + limitation of the old style of SDNVs, from which the currently used + style does not suffer. + + Table 1 compares the maximum values that can be encoded into SDNVs of + various lengths using the old SDNV-8/16 method and the current SDNV + method. The only place in this table where SDNV-16 is used rather + than SDNV-8 is in the 2-byte row. Starting with a single byte, the + two methods are equivalent, but when using 2 bytes, the old method is + a more compact encoding by one bit. From 3 to 7 bytes of length + though, the current SDNV format is more compact, since it only + requires one bit per byte of overhead, whereas the old format used a + full byte. Thus, at 8 bytes, both schemes are equivalent in + efficiency since they both use 8 bits of overhead. Up to 129 bytes, + the old format is more compact than the current one, although after + this, limit it becomes unusable. + + + + + + + + + + + + + + + + + + + + + +Eddy & Davies Informational [Page 11] + +RFC 6256 Using SDNVs May 2011 + + + +-------+---------------+-------------+---------------+-------------+ + | Bytes | SDNV-8/16 | SDNV | SDNV-8/16 | SDNV | + | | Maximum Value | Maximum | Overhead Bits | Overhead | + | | | Value | | Bits | + +-------+---------------+-------------+---------------+-------------+ + | 1 | 127 | 127 | 1 | 1 | + | | | | | | + | 2 | 32,767 | 16,383 | 1 | 2 | + | | | | | | + | 3 | 65,535 | 2,097,151 | 8 | 3 | + | | | | | | + | 4 | 2^24 - 1 | 2^28 - 1 | 8 | 4 | + | | | | | | + | 5 | 2^32 - 1 | 2^35 - 1 | 8 | 5 | + | | | | | | + | 6 | 2^40 - 1 | 2^42 - 1 | 8 | 6 | + | | | | | | + | 7 | 2^48 - 1 | 2^49 - 1 | 8 | 7 | + | | | | | | + | 8 | 2^56 - 1 | 2^56 - 1 | 8 | 8 | + | | | | | | + | 9 | 2^64 - 1 | 2^63 - 1 | 8 | 9 | + | | | | | | + | 10 | 2^72 - 1 | 2^70 - 1 | 8 | 10 | + | | | | | | + | 16 | 2^120 - 1 | 2^112 - 1 | 8 | 16 | + | | | | | | + | 32 | 2^248 - 1 | 2^224 - 1 | 8 | 32 | + | | | | | | + | 64 | 2^504 - 1 | 2^448 - 1 | 8 | 64 | + | | | | | | + | 128 | 2^1016 - 1 | 2^896 - 1 | 8 | 128 | + | | | | | | + | 129 | 2^1024 - 1 | 2^903 - 1 | 8 | 129 | + | | | | | | + | 130 | N/A | 2^910 - 1 | N/A | 130 | + | | | | | | + | 256 | N/A | 2^1792 - 1 | N/A | 256 | + +-------+---------------+-------------+---------------+-------------+ + + Table 1 + + Suggested usages of the SDNV format that leverage its strengths and + limit the effects of its weaknesses are discussed in Section 1.3. + + Another aspect of the comparison between SDNVs and alternatives using + fixed-length fields is the result of errors in transmission. Bit- + errors in an SDNV can result in either errors in the decoded value, + + + +Eddy & Davies Informational [Page 12] + +RFC 6256 Using SDNVs May 2011 + + + or parsing errors in subsequent fields of the protocol. In fixed- + length fields, bit errors always result in errors to the decoded + value rather than parsing errors in subsequent fields. If the + decoded values from either type of field encoding (SDNV or fixed- + length) are used as indexes, offsets, or lengths of further fields in + the protocol, similar failures result. + +5. Security Considerations + + The only security considerations with regard to SDNVs are that code + that parses SDNVs should have bounds-checking logic and be capable of + handling cases where an SDNV's value is beyond the code's ability to + parse. These precautions can prevent potential exploits involving + SDNV decoding routines. + + Stephen Farrell noted that very early definitions of SDNVs also + allowed negative integers. This was considered a potential security + hole, since it could expose implementations to underflow attacks + during SDNV decoding. There is a precedent in that many existing TLV + decoders map the Length field to a signed integer and are vulnerable + in this way. An SDNV decoder should be based on unsigned types and + not have this issue. + +6. Acknowledgements + + Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell, + and other members of the IRTF DTN Research Group contributed to the + development and usage of SDNVs in DTN protocols. George Jones and + Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, Joel Halpern, + Peter TB Brett, Kevin Fall, and Elwyn Davies also contributed useful + comments on and criticisms of this document. DTNRG last call + comments on the document were sent to the mailing list by Lloyd Wood, + Will Ivancic, Jim Wyllie, William Edwards, Hans Kruse, Janico + Greifenberg, Teemu Karkkainen, Stephen Farrell, and Scott Burleigh. + Further constructive comments from Dave Crocker, Lachlan Andrew, and + Michael Welzl were incorporated. + + Work on this document was performed at NASA's Glenn Research Center, + in support of the NASA Space Communications Architecture Working + Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the + FAA/Eurocontrol Future Communications Study (FCS) in the 2005-2007 + time frame, while the editor was an employee of Verizon Federal + Network Systems. + + + + + + + + +Eddy & Davies Informational [Page 13] + +RFC 6256 Using SDNVs May 2011 + + +7. Informative References + + [ASN1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1). + Specification of Basic Notation", ISO/IEC 8824-1:2002, + 2002. + + [BRF04] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider + Transmission Protocol", Work in Progress, May 2004. + + [Hain05] Hain, T., "A Pragmatic Report on IPv4 Address Space + Consumption", Internet Protocol Journal Vol. 8, No. 3, + September 2005. + + [IEN21] Cerf, V. and J. Postel, "Specification of Internetwork + Transmission Control Program: TCP Version 3", Internet + Experimental Note 21, January 1978. + + [Manning09] Manning, c., Raghavan, P., and H. Schuetze, + "Introduction to Information Retrieval", Cambridge + University Press ISBN-13: 978-0521865715, 2009, + <http://informationretrieval.org/>. + + [RFC0713] Haverty, J., "MSDTP-Message Services Data Transmission + Protocol", RFC 713, April 1976. + + [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, + September 1981. + + [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, + RFC 793, September 1981. + + [RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions + for High Performance", RFC 1323, May 1992. + + [RFC2993] Hain, T., "Architectural Implications of NAT", RFC 2993, + November 2000. + + [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For + Public Keys Used For Exchanging Symmetric Keys", BCP 86, + RFC 3766, April 2004. + + [RFC4963] Heffner, J., Mathis, M., and B. Chandler, "IPv4 + Reassembly Errors at High Data Rates", RFC 4963, + July 2007. + + [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol + Specification", RFC 5050, November 2007. + + + + +Eddy & Davies Informational [Page 14] + +RFC 6256 Using SDNVs May 2011 + + + [RFC5325] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider + Transmission Protocol - Motivation", RFC 5325, + September 2008. + + [RFC5326] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider + Transmission Protocol - Specification", RFC 5326, + September 2008. + + [Sayood02] Sayood, K., "Lossless Data Compression", Academic + Press ISBN-13: 978-0126208610, December 2002, + <http://books.google.co.uk/books?id=LjQiGwyabVwC>. + + [X.690] ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1). + Encoding Rules: Specification of Basic Encoding Rules + (BER), Canonical Encoding Rules (CER) and Distinguished + Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Eddy & Davies Informational [Page 15] + +RFC 6256 Using SDNVs May 2011 + + +Appendix A. SDNV Python Source Code + + # This code may be freely copied. Attribution would be appreciated. + # + # sdnv_decode() takes a string argument (s), which is assumed to be + # an SDNV, and optionally a number (slen) for the maximum number of + # bytes to parse from the string. The function returns a pair of + # the non-negative integer n that is the numeric value encoded in + # the SDNV, and integer that is the distance parsed into the input + # string. If the slen argument is not given (or is not a non-zero + # number) then, s is parsed up to the first byte whose high-order + # bit is 0 -- the length of the SDNV portion of s does not have to + # be pre-computed by calling code. If the slen argument is given + # as a non-zero value, then slen bytes of s are parsed. The value + # for n of -1 is returned for any type of parsing error. + # + # NOTE: In python, integers can be of arbitrary size. In other + # languages, such as C, SDNV-parsing routines should take + # precautions to avoid overflow (e.g., by using the Gnu MP library, + # or similar). + # + def sdnv_decode(s, slen=0): + n = long(0) + for i in range(0, len(s)): + v = ord(s[i]) + n = n<<7 + n = n + (v & 0x7F) + if v>>7 == 0: + slen = i+1 + break + elif i == len(s)-1 or (slen != 0 and i > slen): + n = -1 # reached end of input without seeing end of SDNV + return (n, slen) + + # sdnv_encode() returns the SDNV-encoded string that represents n. + # An empty string is returned if n is not a non-negative integer + def sdnv_encode(n): + r = "" + # validate input + if n >= 0 and (type(n) in [type(int(1)), type(long(1))]): + flag = 0 + done = False + while not done: + # encode lowest 7 bits from n + newbits = n & 0x7F + n = n>>7 + r = chr(newbits + flag) + r + if flag == 0: + + + +Eddy & Davies Informational [Page 16] + +RFC 6256 Using SDNVs May 2011 + + + flag = 0x80 + if n == 0: + done = True + return r + + + # test cases from LTP and BP internet-drafts, only print failures + def sdnv_test(): + tests = [(0xABC, chr(0x95) + chr(0x3C)), + (0x1234, chr(0xA4) + chr (0x34)), + (0x4234, chr(0x81) + chr(0x84) + chr(0x34)), + (0x7F, chr(0x7F))] + + for tp in tests: + # test encoding function + if sdnv_encode(tp[0]) != tp[1]: + print "sdnv_encode fails on input %s" % hex(tp[0]) + # test decoding function + if sdnv_decode(tp[1])[0] != tp[0]: + print "sdnv_decode fails on input %s, giving %s" % \ + (hex(tp[0]), sdnv_decode(tp[1])) + +Authors' Addresses + + Wesley M. Eddy + MTI Systems + NASA Glenn Research Center + MS 500-ASRC; 21000 Brookpark Rd + Cleveland, OH 44135 + + Phone: 216-433-6682 + EMail: wes@mti-systems.com + + + Elwyn Davies + Folly Consulting + Soham + UK + + Phone: + EMail: elwynd@folly.org.uk + URI: + + + + + + + + + +Eddy & Davies Informational [Page 17] + |