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