idnits 2.17.00 (12 Aug 2021) /tmp/idnits62526/draft-irtf-dtnrg-sdnv-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (December 21, 2009) is 4533 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 664 -- Looks like a reference, but probably isn't: '1' on line 664 == Outdated reference: draft-irtf-dtnrg-ltp has been published as RFC 5326 == Outdated reference: A later version (-76) exists of draft-hixie-thewebsocketprotocol-68 -- Obsolete informational reference (is this intentional?): RFC 1323 (Obsoleted by RFC 7323) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group W. Eddy 3 Internet-Draft MTI Systems 4 Intended status: Informational December 21, 2009 5 Expires: June 24, 2010 7 Using Self-Delimiting Numeric Values in Protocols 8 draft-irtf-dtnrg-sdnv-05 10 Abstract 12 Self-Delimiting Numeric Values (SDNVs) have recently been introduced 13 as a field type in proposed Delay-Tolerant Networking protocols. 14 SDNVs encode an arbitrary-length non-negative integer or arbitrary- 15 length bit-string with minimum overhead. They are intended to 16 provide protocol flexibility without sacrificing economy, and to 17 assist in future-proofing protocols under development. This document 18 describes formats and algorithms for SDNV encoding and decoding, 19 along with notes on implementation and usage. This document is a 20 product of the Delay Tolerant Networking Research Group and has been 21 reviewed by that group. No objections to its publication as an RFC 22 were raised. 24 Status of this Memo 26 This Internet-Draft is submitted to IETF in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF), its areas, and its working groups. Note that 31 other groups may also distribute working documents as Internet- 32 Drafts. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 The list of current Internet-Drafts can be accessed at 40 http://www.ietf.org/ietf/1id-abstracts.txt. 42 The list of Internet-Draft Shadow Directories can be accessed at 43 http://www.ietf.org/shadow.html. 45 This Internet-Draft will expire on June 24, 2010. 47 Copyright Notice 48 Copyright (c) 2009 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 1.1. Problems with Fixed Value Fields . . . . . . . . . . . . . 3 65 1.2. SDNVs for DTN Protocols . . . . . . . . . . . . . . . . . 4 66 1.3. SDNV Usage . . . . . . . . . . . . . . . . . . . . . . . . 5 67 2. Definition of SDNVs . . . . . . . . . . . . . . . . . . . . . 7 68 3. Basic Algorithms . . . . . . . . . . . . . . . . . . . . . . . 8 69 3.1. Encoding Algorithm . . . . . . . . . . . . . . . . . . . . 8 70 3.2. Decoding Algorithm . . . . . . . . . . . . . . . . . . . . 8 71 4. Comparison to Alternatives . . . . . . . . . . . . . . . . . . 10 72 5. Security Considerations . . . . . . . . . . . . . . . . . . . 14 73 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 74 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16 75 8. Informative References . . . . . . . . . . . . . . . . . . . . 17 76 Appendix A. SNDV Python Source Code . . . . . . . . . . . . . . . 19 77 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 21 79 1. Introduction 81 This document is a product of the Internet Research Task Force (IRTF) 82 Delay-Tolerant Networking (DTN) Research Group (DTNRG). The document 83 has received review and support within the DTNRG, as discussed in the 84 Acknowledgements section of this document. 86 This document begins by describing a common problem encountered in 87 network protocol engineering. It then provides some background on 88 the Self-Delimiting Numeric Values (SDNVs) proposed for use in DTN 89 protocols, and motivates their potential applicability in other 90 networking protocols. One example of SDNVs being used outside of the 91 DTN protocols is in Hixie's Web Socket protocol 92 [I-D.hixie-thewebsocketprotocol], which includes a binary frame 93 length indicator field identical to an SDNV. The DTNRG has created 94 SDNVs to meet the challenges it attempts to solve, and it has been 95 noted that SDNVs closely resemble certain constructs within ASN.1 and 96 even older ITU protocols, so the problems are not new or unique to 97 DTN. SDNVs focus strictly on numeric values or bitstrings, while 98 other mechanisms have been developed for encoding more complex data 99 structures, such as ASN.1 encoding rules, and Haverty's MSDTP 100 [RFC0713]. Because of this focus, SDNVs are can be quickly 101 implemented with only a small amount of code. 103 SDNVs are tersely defined in both the bundle protocol [RFC5050] and 104 LTP [RFC5326] specifications, due to the flow of document production 105 in the DTNRG. This document clarifies and further explains the 106 motivations and engineering decisions behind SDNVs. 108 1.1. Problems with Fixed Value Fields 110 Protocol designers commonly face an optimization problem in 111 determining the proper size for header fields. There is a strong 112 desire to keep fields as small as possible, in order to reduce the 113 protocol's overhead, and also allow for fast processing. Since 114 protocols can be used many years (even decades) after they are 115 designed, and networking technology has tended to change rapidly, it 116 is not uncommon for the use, deployment, or performance of a 117 particular protocol to be limited or infringed upon by the length of 118 some header field being too short. Two well-known examples of this 119 phenomenon are the TCP advertised receive window, and the IPv4 120 address length. 122 TCP segments contain an advertised receive window field that is fixed 123 at 16 bits [RFC0793], encoding a maximum value of around 65 124 kilobytes. The purpose of this value is to provide flow control, by 125 allowing a receiver to specify how many sent bytes its peer can have 126 outstanding (unacknowledged) at any time, thus allowing the receiver 127 to limit its buffer size. As network speeds have grown by several 128 orders of magnitude since TCP's inception, the combination of the 65 129 kilobyte maximum advertised window and long round-trip times 130 prevented TCP senders from being able to acheive the high throughput 131 that the underlying network supported. This limitation was remedied 132 through the use of the Window Scale option [RFC1323], which provides 133 a multiplier for the advertised window field. However, the Window 134 Scale multiplier is fixed for the duration of the connection, 135 requires support from each end of a TCP connection, and limits the 136 precision of the advertised receive window, so this is certainly a 137 less-than-ideal solution. Because of the field width limit in the 138 original design however, the Window Scale is necessary for TCP to 139 reach high sending rates. 141 An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note, 142 an early version 0 IP header format specification in [IEN21] used 143 variable-length addresses in multiples of 8-bits up to 120-bits). 144 Due to the way that subnetting and assignment of address blocks was 145 performed, the number of IPv4 addresses has been seen as a limit to 146 the growth of the Internet [Hain05]. Two divergent paths to solve 147 this problem have been the use of Network Address Translators (NATs) 148 and the development of IPv6. NATs have caused a number of other 149 issues and problems [RFC2993], leading to increased complexity and 150 fragility, as well as forcing work-arounds to be engineered for many 151 other protocols to function within a NATed environment. The IPv6 152 solution's transitional work has been underway for several years, but 153 has still only just begun to have visible impact on the global 154 Internet. 156 Of course, in both the case of the TCP receive window and IPv4 157 address length, the field size chosen by the designers seemed like a 158 good idea at the time. The fields were more than big enough for the 159 originally perceived usage of the protocols, and yet were small 160 enough to allow the headers to remain compact and relatively easy and 161 efficient to parse on machines of the time. The fixed sizes that 162 were defined represented a tradeoff between the scalability of the 163 protocol versus the overhead and efficiency of processing. In both 164 cases, these engineering decisions turned out to be painfully 165 restrictive in the longer term. 167 1.2. SDNVs for DTN Protocols 169 In specifications for the DTN Bundle Protocol (BP) [RFC5050] and 170 Licklider Transmission Protocol (LTP) [RFC5326], SDNVs have been used 171 for several fields including identifiers, payload/header lengths, and 172 serial (sequence) numbers. SDNVs were developed for use in these 173 types of fields, to avoid sending more bytes than needed, as well as 174 avoiding fixed sizes that may not end up being appropriate. For 175 example, since LTP is intended primarily for use in long-delay 176 interplanetary communications [RFC5325], where links may be fairly 177 low in capacity, it is desirable to avoid the header overhead of 178 routinely sending a 64-bit field where a 16-bit field would suffice. 179 Since many of the nodes implementing LTP are expected to be beyond 180 the current range of human spaceflight, upgrading their on-board LTP 181 implementations to use longer values if the defined fields are found 182 to be too short would also be problematic. Furthermore, extensions 183 similar in mechanism to TCP's Window Scale option are unsuitable for 184 use in DTN protocols since due to high delays, DTN protocols must 185 avoid handshaking and configuration parameter negotiation to the 186 greatest extent possible. All of these reasons make the choice of 187 SDNVs for use in DTN protocols attractive. 189 1.3. SDNV Usage 191 In short, an SDNV is simply a way of representing non-negative 192 integers (both positive integers of arbitrary magnitude and 0), 193 without expending much unneccessary space. This definition allows 194 SDNVs to represent many common protocol header fields, such as: 196 o Random identification fields as used in the IPsec Security 197 Parameters Index or in IP headers for fragment reassembly (Note: 198 the 16-bit IP ID field for fragment reassembly was recently found 199 to be too short in some environments [RFC4963]), 201 o Sequence numbers as in TCP or SCTP, 203 o Values used in cryptographic algorithms such as RSA keys, Diffie- 204 Hellman key-agreement, or coordinates of points on elliptic 205 curves. 207 o Message lengths as used in file transfer protocols. 209 o Nonces and cookies. 211 o Etc. 213 As any bit-string can be interpreted as an unsigned integer, SDNVs 214 can also encode arbitrary-length bit strings, including bit-strings 215 representing signed integers or other data types; however, this 216 document assumes SDNV encoding and decoding in terms of unsigned 217 integers. Implementations may differ in the interface that they 218 provide to SDNV encoding and decoding functions, in terms of whether 219 the values are numeric, bit-strings, etc.; this detail does not alter 220 the representation or algorithms described in this document. 222 The use of SDNVs rather than fixed length fields gives protocol 223 designers the ability to ameliorate the consequences of making 224 difficult-to-reverse field-sizing decisions, as the SDNV format grows 225 and shrinks depending on the particular value encoded. SDNVs do not 226 necessarily provide optimal encodings for values of any particular 227 length, however they allow protocol designers to avoid potential 228 blunders in assigning fixed lengths, and remove the complexity 229 involved with either negotiating field lengths or constructing 230 protocol extensions. 232 To our knowledge, at this time, no IETF transport or network-layer 233 protocol designed for use outside of the DTN domain has proposed to 234 use SDNVs; however there is no inherent reason not to use SDNVs more 235 broadly in the future. The two examples cited here, of fields that 236 have proven too small in general Internet protocols, are only a small 237 sampling of the much larger set of similar instances that the authors 238 can think of. Outside the Internet protocols, within ASN.1 and 239 previous ITU protocols, constructs very similar to SDNVs have been 240 used for many years due to engineering concerns very similar to those 241 facing the DTNRG. 243 Many protocols use a Type-Length-Value method for encoding variable 244 length strings (e.g. TCP's options format, or many of the fields in 245 IKEv2). An SDNV is equivalent to combining the length and value 246 portions of this type of field, with the overhead of the length 247 portion amortized out over the bytes of the value. The penalty paid 248 for this in an SDNV may be several extra bytes for long values (e.g. 249 1024 bit RSA keys). See Section 4 for further discussion and a 250 comparison. 252 As is shown in later sections, for large values, the current SDNV 253 scheme is fairly inefficient in terms of space (1/8 of the bits are 254 overhead) and not particularly easy to encode/decode in comparison to 255 alternatives. The best use of SDNVs may often be to define the 256 Length field of a TLV structure to be an SDNV whose value is the 257 length of the TLV's Value field. In this way, one can avoid forcing 258 large numbers from being directly encoded as an SDNV, yet retain the 259 extensibility that using SDNVs grants. 261 2. Definition of SDNVs 263 An early definition of the SDNV format bore resemblance to the ASN.1 264 [ASN1] Basic Encoding Rules (BER) [ASN1-BER] for lengths (Section 265 8.1.3 of X.690). The current SDNV format is the one used by ASN.1 266 BER for encoding tag identifiers greater than or equal to 31 (Section 267 8.1.2.4.2 of X.690). A comparison between the current SDNV format 268 and the early SDNV format is made in Section 4. 270 The format currently used is very simple. Before encoding, an 271 integer is represented as a left-to-right bitstring beginning with 272 its most significant bit, and ending with its least signifcant bit. 273 When transmitted, the bits are encoded into a series of bytes. The 274 most significant bit of each byte specifies whether it is the final 275 byte of the encoded value (when it holds a 0), or not (when it holds 276 a 1). The remaining 7 bits of each byte in the wire format are taken 277 in order from the integer's bitstring representation. If the 278 bitstring's length is not a multiple of 7, then the string is left- 279 padded with 0s. 281 For example: 283 o 1 (decimal) is represented by the bitstring "0000001" and encoded 284 as the single byte 0x01 (in hexadecimal) 286 o 128 is represented by the bitstring "10000001 00000000" and 287 encoded as the bytes 0x81 followed by 0x00. 289 o Other values can be found in the test vectors of the source code 290 in Appendix A 292 To be perfectly clear, and avoid potential interoperability issues 293 (as have occurred with ASN.1 BER time values), we explicitly state 294 two considerations regarding zero-padding. (1) When encoding SDNVs, 295 any leading (most significant) zero bits in the input number might be 296 discarded by the SDNV encoder. Protocols that use SDNVs should not 297 rely on leading-zeros being retained after encoding and decoding 298 operations. (2) When decoding SDNVs, the relevant number of leading 299 zeros required to pad up to a machine word or other natural data unit 300 might be added. These are put in the most-significant positions in 301 order to not change the value of the number. Protocols using SDNVs 302 should consider situations where lost zero-padding may be 303 problematic. 305 3. Basic Algorithms 307 This section describes some simple algorithms for creating and 308 parsing SDNV fields. These may not be the most efficient algorithms 309 possible, however, they are easy to read, understand, and implement. 310 Appendix A contains Python source code implementing the routines 311 described here. 313 3.1. Encoding Algorithm 315 There is a very simple algorithm for the encoding operation that 316 converts a non-negative integer (value n, of length 1+floor(log_2 n) 317 bits) into an SDNV. This algorithm takes n as its only argument and 318 returns a string of bytes: 320 o (Initial Step) Set the return value to a byte sharing the least 321 significant 7 bits of n, and with 0 in the most significant bit, 322 but do not return yet. Right shift n 7 bits and use this as the 323 new n value. If implemented using call-by-reference rather than 324 call-by-value, make a copy of n for local use at the start of the 325 function call. 327 o (Recursion Step) If n == 0, return. Otherwise, take the byte 328 0x80, and bitwise-or it with the 7 least significant bits of n. 329 Set the return value to this result with the previous return 330 string appended to it. Shift n right 7 bits again. Repeat 331 Recursion Step. 333 This encoding algorithm can easily be seen to have time complexity of 334 O(log_2 n), since it takes a number of steps equal to ceil(n/7), and 335 no additional space beyond the size of the result (8/7 log_2 n) is 336 required. One aspect of this algorithm is that it assumes strings 337 can be efficiently appended to new bytes. One way to implement this 338 is to allocate a buffer for the expected length of the result and 339 fill that buffer one byte at a time from the right end. 341 If, for some reason, an implementation requires an encoded SDNV to be 342 some specific length (possibly related to a machine word), any 343 leftmost zero-padding included needs to properly set the high-order 344 bit in each byte of padding. 346 3.2. Decoding Algorithm 348 Decoding SNDVs is a more difficult operation than encoding them, due 349 to the fact that no bound on the resulting value is known until the 350 SDNV is parsed, at which point the value itself is already known. 351 This means that if space is allocated for decoding the value of an 352 SDNV into, it is never known whether this space will be overflowed 353 until it is 7 bits away from happening. 355 (Initial Step) Set the result to 0. Set a pointer to the beginning 356 of the SDNV. 358 (Recursion Step) Shift the result left 7 bits. Add the lower 7 bits 359 of the value at the pointer to the result. If the high-order bit 360 under the pointer is a 1, move the pointer right one byte and repeat 361 the Recursion Step, otherwise return the current value of the result. 363 This decoding algorithm takes no more additional space than what is 364 required for the result (7/8 the length of the SDNV) and the pointer. 365 The complication is that before the result can be left-shifted in the 366 Recursion Step, an implementation needs to first make sure that this 367 won't cause any bits to be lost, and re-allocate a larger piece of 368 memory for the result, if required. The pure time complexity is the 369 same as for the encoding algorithm given, but if re-allocation is 370 needed due to the inability to predict the size of the result, 371 decoding may be slower. 373 These decoding steps include removal of any leftmost zero-padding 374 that might be used by an encoder to create encodings of a certain 375 length. 377 4. Comparison to Alternatives 379 This section compares three alternative ways of implementing the 380 concept of SDNVs: (1) the TLV scheme commonly used in the Internet 381 family, and many other families of protocols, (2) the old style of 382 SDNVs (both the SDNV-8 and SDNV-16) defined in an early stage of 383 LTP's development [BRF04], and (3) the current SDNV format. 385 The TLV method uses two fixed-length fields to hold the Type and 386 Length elements that then imply the syntax and semantics of the Value 387 element. This is only similar to an SDNV in that the value element 388 can grow or shrink within the bounds capable of being conveyed by the 389 Length field. Two fundamental differences between TLVs and SDNVs are 390 that through the Type element, TLVs also contain some notion of what 391 their contents are semantically, while SDNVs are simply generic non- 392 negative integers, and protocol engineers still have to choose fixed 393 field lengths for the Type and Length fields in the TLV format. 395 Some protocols use TLVs where the value conveyed within the Length 396 field needs to be decoded into the actual length of the Value field. 397 This may be accomplished through simple multiplication, left- 398 shifting, or a look-up table. In any case, this tactic limits the 399 granularity of the possible Value lengths, and can contribute some 400 degree of bloat if Values do not fit neatly within the available 401 decoded Lengths. 403 In the SDNV format originally used by LTP, parsing the first byte of 404 the SDNV told an implementation how much space was required to hold 405 the contained value. There were two different types of SDNVs defined 406 for different ranges of use. The SDNV-8 type could hold values up to 407 127 in a single byte, while the SDNV-16 type could hold values up to 408 32,767 in 2 bytes. Both formats could encode values requiring up to 409 N bytes in N+2 bytes, where N<127. The major difference between this 410 old SDNV format and the current SDNV format is that the new format is 411 not as easily decoded as the old format was, but the new format also 412 has absolutely no limitation on its length. 414 The advantage in ease of parsing the old format manifests itself in 415 two aspects: (1) the size of the value is determinable ahead of time, 416 in a way equivalent to parsing a TLV, and (2) the actual value is 417 directly encoded and decoded, without shifting and masking bits as is 418 required in the new format. For these reasons, the old format 419 requires less computational overhead to deal with, but is also very 420 limited, in that it can only hold a 1024-bit number, at maximum. 421 Since according to IETF Best Current Practices, an asymmetric 422 cryptography key needed to last for a long term requires using moduli 423 of over 1228 bits [RFC3766], this could be seen as a severe 424 limitation of the old-style of SDNVs, which the currently-used style 425 does not suffer from. 427 Table 1 compares the maximum values that can be encoded into SDNVs of 428 various lengths using the old SDNV-8/16 method and the current SDNV 429 method. The only place in this table where SDNV-16 is used rather 430 than SDNV-8 is in the 2-byte row. Starting with a single byte, the 431 two methods are equivalent, but when using 2 bytes, the old method is 432 a more compact encoding by one bit. From 3 to 7 bytes of length 433 though, the current SDNV format is more compact, since it only 434 requires one bit per byte of overhead, whereas the old format used a 435 full byte. Thus, at 8 bytes, both schemes are equivalent in 436 efficiency since they both use 8 bits of overhead. Up to 129 bytes, 437 the old format is more compact than the current one, although after 438 this limit it becomes unusable. 440 +-------+---------------+-------------+---------------+-------------+ 441 | Bytes | SDNV-8/16 | SDNV | SDNV-8/16 | SDNV | 442 | | Maximum Value | Maximum | Overhead Bits | Overhead | 443 | | | Value | | Bits | 444 +-------+---------------+-------------+---------------+-------------+ 445 | 1 | 127 | 127 | 1 | 1 | 446 | | | | | | 447 | 2 | 32,767 | 16,383 | 1 | 2 | 448 | | | | | | 449 | 3 | 65,535 | 2,097,151 | 8 | 3 | 450 | | | | | | 451 | 4 | 2^24 - 1 | 2^28 - 1 | 8 | 4 | 452 | | | | | | 453 | 5 | 2^32 - 1 | 2^35 - 1 | 8 | 5 | 454 | | | | | | 455 | 6 | 2^40 - 1 | 2^42 - 1 | 8 | 6 | 456 | | | | | | 457 | 7 | 2^48 - 1 | 2^49 - 1 | 8 | 7 | 458 | | | | | | 459 | 8 | 2^56 - 1 | 2^56 - 1 | 8 | 8 | 460 | | | | | | 461 | 9 | 2^64 - 1 | 2^63 - 1 | 8 | 9 | 462 | | | | | | 463 | 10 | 2^72 - 1 | 2^70 - 1 | 8 | 10 | 464 | | | | | | 465 | 16 | 2^120 - 1 | 2^112 - 1 | 8 | 16 | 466 | | | | | | 467 | 32 | 2^248 - 1 | 2^224 - 1 | 8 | 32 | 468 | | | | | | 469 | 64 | 2^504 - 1 | 2^448 - 1 | 8 | 64 | 470 | | | | | | 471 | 128 | 2^1016 - 1 | 2^896 - 1 | 8 | 128 | 472 | | | | | | 473 | 129 | 2^1024 - 1 | 2^903 - 1 | 8 | 129 | 474 | | | | | | 475 | 130 | N/A | 2^910 - 1 | N/A | 130 | 476 | | | | | | 477 | 256 | N/A | 2^1792 - 1 | N/A | 256 | 478 +-------+---------------+-------------+---------------+-------------+ 480 Table 1 482 In general, it seems like the most promising use of SDNVs may be to 483 define the Length field of a TLV structure to be an SDNV whose value 484 is the length of the TLV's Value field. This leverages the strengths 485 of the SDNV format and limits the effects of its weaknesses. 487 Another aspect of comparison between SDNVs and alternatives using 488 fixed-length fields is the result of errors in transmission. Bit- 489 errors in an SDNV can result in either errors in the decoded value, 490 or parsing errors in subsequent fields of the protocol. In fixed- 491 length fields, bit errors always result in errors to the decoded 492 value rather than parsing errors in subsequent fields. If the 493 decoded values from either type of field encoding (SDNV or fixed- 494 length) are used as indexes, offsets, or lengths of further fields in 495 the protocol, similar failures result. 497 5. Security Considerations 499 The only security considerations with regards to SDNVs are that code 500 which parses SDNVs should have bounds-checking logic and be capable 501 of handling cases where an SDNV's value is beyond the code's ability 502 to parse. These precautions can prevent potential exploits involving 503 SDNV decoding routines. 505 Stephen Farrell noted that very early definitions of SDNVs also 506 allowed negative integers. This was considered a potential security 507 hole, since it could expose implementations to underflow attacks 508 during SDNV decoding. There is a precedent in that many existing TLV 509 decoders map the Length field to a signed integer and are vulnerable 510 in this way. An SDNV decoder should be based on unsigned types and 511 not have this issue. 513 6. IANA Considerations 515 This document has no IANA considerations. 517 7. Acknowledgements 519 Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell, 520 and other members of the IRTF DTN Research Group contributed to the 521 development and usage of SDNVs in DTN protocols. George Jones and 522 Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, Joel Halpern, 523 Peter TB Brett, Kevin Fall, and Elwyn Davies also contributed useful 524 comments on and criticisms of this document. DTNRG last call 525 comments on the draft were sent to the mailing list by Lloyd Wood, 526 Will Ivancic, Jim Wyllie, William Edwards, Hans Kruse, Janico 527 Greifenberg, Teemu Karkkainen, Stephen Farrell, and Scott Burleigh. 528 Further constructive comments were incorporated from Dave Crocker. 530 Work on this document was performed at NASA's Glenn Research Center, 531 in support of the NASA Space Communications Architecture Working 532 Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the 533 FAA/Eurocontrol Future Communications Study (FCS) in the 2005-2007 534 timeframe, while the editor was an employee of Verizon Federal 535 Network Systems. 537 8. Informative References 539 [ASN1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1). 540 Specification of Basic Notation", ISO/IEC 8824-1:2002, 541 2002. 543 [ASN1-BER] 544 ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1). 545 Encoding Rules: Specification of Basic Encoding Rules 546 (BER), Canonical Encoding Rules (CER) and Distinguished 547 Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002. 549 [BRF04] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 550 Transmission Protocol", 551 draft-irtf-dtnrg-ltp-00 (replaced), May 2004. 553 [Hain05] Hain, T., "A Pragmatic Report on IPv4 Address Space 554 Consumption", Internet Protocol Journal Vol. 8, No. 3, 555 September 2005. 557 [I-D.hixie-thewebsocketprotocol] 558 Hickson, I., "The Web Socket protocol", 559 draft-hixie-thewebsocketprotocol-68 (work in progress), 560 December 2009. 562 [IEN21] Cerf, V. and J. Postel, "Specification of Internetwork 563 Transmission Control Program: TCP Version 3", Internet 564 Experimental Note 21, January 1978. 566 [RFC0713] Haverty, J., "MSDTP-Message Services Data Transmission 567 Protocol", RFC 713, April 1976. 569 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 570 September 1981. 572 [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, 573 RFC 793, September 1981. 575 [RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions 576 for High Performance", RFC 1323, May 1992. 578 [RFC2993] Hain, T., "Architectural Implications of NAT", RFC 2993, 579 November 2000. 581 [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For 582 Public Keys Used For Exchanging Symmetric Keys", BCP 86, 583 RFC 3766, April 2004. 585 [RFC4963] Heffner, J., Mathis, M., and B. Chandler, "IPv4 Reassembly 586 Errors at High Data Rates", RFC 4963, July 2007. 588 [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol 589 Specification", RFC 5050, November 2007. 591 [RFC5325] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 592 Transmission Protocol - Motivation", RFC 5325, 593 September 2008. 595 [RFC5326] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider 596 Transmission Protocol - Specification", RFC 5326, 597 March 2008. 599 Appendix A. SNDV Python Source Code 601 # sdnv_decode() takes a string argument s, which is assumed to be an 602 # SDNV. The function returns a pair of the non-negative integer n 603 # that is the numeric value encoded in the SDNV, and and integer l 604 # that is the distance parsed into the input string. If the slen 605 # argument is not given (or is not a non-zero number) then, s is 606 # parsed up to the first byte whose high-order bit is 0 -- the 607 # length of the SDNV portion of s does not have to be pre-computed 608 # by calling code. If the slen argument is given as a non-zero 609 # value, then slen bytes of s are parsed. The value for n of -1 is 610 # returned for any type of parsing error. 611 # 612 # NOTE: In python, integers can be of arbitrary size. In other 613 # languages, such as C, SDNV-parsing routines should take 614 # precautions to avoid overflow (e.g. by using the Gnu MP library, 615 # or similar). 616 # 617 def sdnv_decode(s, slen=0): 618 n = long(0) 619 for i in range(0, len(s)): 620 v = ord(s[i]) 621 n = n<<7 622 n = n + (v & 0x7F) 623 if v>>7 == 0: 624 slen = i+1 625 break 626 elif i == len(s)-1 or (slen != 0 and i > slen): 627 n = -1 # reached end of input without seeing end of SDNV 628 return (n, slen) 630 # sdnv_encode() returns the SDNV-encoded string that represents n. 631 # An empty string is returned if n is not a non-negative integer 632 def sdnv_encode(n): 633 r = "" 634 # validate input 635 if n >= 0 and (type(n) in [type(int(1)), type(long(1))]): 636 flag = 0 637 done = False 638 while not done: 639 # encode lowest 7 bits from n 640 newbits = n & 0x7F 641 n = n>>7 642 r = chr(newbits + flag) + r 643 if flag == 0: 644 flag = 0x80 645 if n == 0: 646 done = True 648 return r 650 # test cases from LTP and BP internet-drafts, only print failures 651 def sdnv_test(): 652 tests = [(0xABC, chr(0x95) + chr(0x3C)), 653 (0x1234, chr(0xA4) + chr (0x34)), 654 (0x4234, chr(0x81) + chr(0x84) + chr(0x34)), 655 (0x7F, chr(0x7F))] 657 for tp in tests: 658 # test encoding function 659 if sdnv_encode(tp[0]) != tp[1]: 660 print "sdnv_encode fails on input %s" % hex(tp[0]) 661 # test decoding function 662 if sdnv_decode(tp[1])[0] != tp[0]: 663 print "sdnv_decode fails on input %s, giving %s" % \ 664 (hex(tp[0]), sdnv_decode(tp[1])) 666 Author's Address 668 Wesley M. Eddy 669 MTI Systems 670 NASA Glenn Research Center 671 MS 500-ASRC; 21000 Brookpark Rd 672 Cleveland, OH 44135 674 Phone: 216-433-6682 675 Email: wes@mti-systems.com