idnits 2.17.1 draft-touch-sne-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- -- The document has an IETF Trust Provisions (28 Dec 2009) Section 6.c(i) Publication Limitation clause. 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 date (April 12, 2021) is 1103 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 ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 793 (Obsoleted by RFC 9293) Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 TCPM J. Touch 2 Internet Draft Independent consultant 3 Intended status: Informational April 12, 2021 4 Expires: October 2021 6 Sequence Number Extension for Windowed Protocols 7 draft-touch-sne-00.txt 9 Status of this Memo 11 This Internet-Draft is submitted in full conformance with the 12 provisions of BCP 78 and BCP 79. This document may not be modified, 13 and derivative works of it may not be created, except to format it 14 for publication as an RFC or to translate it into languages other 15 than English. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six 23 months and may be updated, replaced, or obsoleted by other documents 24 at any time. It is inappropriate to use Internet-Drafts as 25 reference material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html 33 This Internet-Draft will expire on October 12, 2021. 35 Copyright Notice 37 Copyright (c) 2021 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with 45 respect to this document. Code Components extracted from this 46 document must include Simplified BSD License text as described in 47 Section 4.e of the Trust Legal Provisions and are provided without 48 warranty as described in the Simplified BSD License. 50 Abstract 52 Sliding window protocols use finite sequence numbers to determine 53 segment placement and order. These sequence number spaces wrap 54 around and are reused during the operation of such protocols. This 55 document describes a way to extend the size of these sequence 56 numbers at the endpoints to avoid the impact of that wrap and reuse 57 without transmitting additional information in the packet header. 58 The resulting extended sequence numbers can be used at the endpoints 59 in encryption and authentication algorithms to ensure input bit 60 patterns do not repeat over the lifetime of a connection. 62 Table of Contents 64 1. Introduction...................................................2 65 2. Background.....................................................3 66 3. Related Discussion.............................................4 67 4. Example Code...................................................5 68 5. Validation Suite...............................................8 69 6. Security Considerations........................................9 70 7. IANA Considerations............................................9 71 8. References.....................................................9 72 8.1. Normative References......................................9 73 8.2. Informative References....................................9 74 9. Acknowledgments................................................9 76 1. Introduction 78 Protocols use sequence numbers to maintain ordering and, in sliding 79 window systems, to control the amount of outstanding unacknowledged 80 information. These sequence numbers are finite and thus commonly 81 wrap-around during long connections, reusing past values. 83 It can be useful for protocols to keep track of this wrap-around in 84 a separate counter, such that the sequence number and counter 85 together form an equivalent number space that does not wrap. This 86 technique was introduced as "sequence number extension" in TCP-AO 87 [RFC5925]. The example provided there was intended to introduce the 88 concept, but the pseudocode provided is not complete. 90 This document presents the formal requirements for sequence number 91 extension (SNE), a code example, and a check sequence that can be 92 used to validate this and alternate implementations. Section 2 93 provides background on the concept, Section 3 discusses currently 94 known uses of SNE. Section 4 provides a framework for testing SNE 95 implementations, including example code for the SNE function, and 96 Section 5 provides a sequence that can be used by that code for 97 validation. Section 6 concludes with a discussion of security 98 issues. 100 2. Background 102 Protocols use sequence numbers to maintain message order. The 103 transmitter typically increments them either once per message or by 104 the length of the message. The receiver uses them to reorder 105 messages and detect gaps due to inferred loss. 107 Sequence numbers are represented within those messages (e.g., in the 108 headers) as values of a finite, unsigned number space. This space is 109 typically represented in a fixed-length bit string, whose values 110 range from [0..(2^N-1)], inclusive. 112 The use of finite representations has repercussions on the use of 113 these values at both the transmitter and receiver. Without 114 additional constraints, when the number space "wraps around", it is 115 be impossible for the receiver to distinguish between the uses of 116 the same value. This would defeat their use for reordering. 118 As a consequence, additional constraints are required. Transmitters 119 are typically required to limit reuse until they can confirm that 120 receivers would successfully differentiate the two uses of the same 121 value. This is accomplished by defining "forward" as values that 122 advance the values by less than half the sequence number space, and 123 ensuring that receivers never experience a series of values that 124 violate that rule. 126 We define a sequence space as follows: 128 o An unsigned integer range from 0..(2^N)-1, i.e., for N bits 130 o An operation that increments values in that space by K, where K < 131 2^(N-1), i.e., less than half the range. This operation is used 132 exclusively by the transmitter. 134 o An operation that compares two values in that space to determine 135 their order, e.g., where X < Y implies that X comes before Y 137 We assume that both sides begin with the same initial value, which 138 can be anywhere in the space. That value is either assumed (e.g., 0) 139 before the protocol begins, or coordinated before other messages are 140 exchanged (as with TCP Initial Sequence Numbers, i.e., ISNs 141 [RFC793]). The receiver is assumed to always receive values that are 142 always within 2^(N-1), i.e., half the range. 144 No other operations are supported. The transmitter is not permitted 145 to "backup", such that values are always used in "increment" order. 146 The receiver cannot experience loss or gaps larger than 2^(N-1)-1, 147 which is typically enforced either by assumption or by explicit 148 endpoint coordination. 150 A sequence number extension (SNE) is a separate number space that 151 can be combined with the sequence number to create a larger number 152 space that does not wrap around during a connection. 154 On the transmit side, SNE is trivially accomplished by incrementing 155 a local counter once each time the sequence number increment "wraps" 156 around, or by keeping a larger local sequence number whose least- 157 significant part is the message sequence number and most-significant 158 part can be considered the SNE. The transmitter typically does not 159 need to maintain a SNE except when used in local computations, such 160 as for HMACs in TCP-AO [RFC5925]. 162 The goal of this document is to demonstrate that SNE can be 163 accomplished on the receiver side without transmitting additional 164 information in messages. It defines the stateful function 165 compute_sne() as follows: 167 SNE = compute_sne(seqno) 169 Compute_sne() accepts the sequence number seen in a received message 170 and computes the corresponding SNE. The function includes persistent 171 local state that tracks the largest currently received SNE, seqno 172 combination. The concatenation of SNE and seqno emulates the 173 equivalent larger sequence number space that can avoid wrap around. 175 Note that the function defined here is capable of receiving any 176 series of seqno values and computing their correct corresponding 177 SNE, as long as the series never "jumps" more than half the number 178 space "backward" from the largest value seen "forward". 180 3. Related Discussion 182 The DNS uses sequence numbers to determine when a SOE serial number 183 is more recent than a previous one, even considering sequence space 184 wrap [RFC1034][RFC1035]. The use of wrapped sequence numbers for 185 sliding windows in network protocols was first described as a 186 sequence number space [IEN74]. 188 A more recent discussion describes this as "serial number 189 arithmetic" and defines a comparison operator it claimed was missing 190 in IEN74 [RFC1982]. That document defines two operations: addition 191 (presumably shifting the window forward) and comparison (defining 192 the order of two values). Addition is defined in that document as 193 limited to value of 0..windowsize/2-1. Comparison is defined in that 194 document by a set of equations therein, but that document does not 195 provide a way for a receiver to compute the correct equivalent SNE, 196 especially including the potential for sequence number reordering, 197 as is demonstrated in this document. 199 4. Example Code 201 The following C code is provided as a verified example of sequence 202 number extension. The code includes both the framework used for 203 validation and the compute_sne() function, the latter of which can 204 be used operationally. 206 A correct test will indicate "OK" for each test. An incorrect test 207 will indicate "ERROR" where applicable. 209 #include 210 #include 212 #define distance(x,y) (((x)<(y))?((y)-(x)):((x)-(y))) 214 #define SNEDEBUG 1 216 // This is the core code, stand-alone, to compute SNE from seqno 217 // >> replace this function with your own code to test alternates 218 unsigned long compute_sne(unsigned long seqno) { 219 // INPUT: 32-bit unsigned sequence number (low bits) 220 // OUTPUT: 32-bit unsigned SNE (high bits) 222 // variables used in this code example to compute SNE: 223 static unsigned long 224 RCV_SNE = 0; // high-watermark SNE 225 static int 226 RCV_SNE_FLAG = 1; // set during first half rollover 227 // (prevents re-rollover) 228 static unsigned long 229 RCV_PREV_SEQ = 0; // high-watermark SEQ 230 unsigned long 231 holdSNE; // temp copy of output 233 holdSNE = RCV_SNE; // use current SNE to start 234 if (distance(seqno,RCV_PREV_SEQ) < 0x80000000) { 235 // both in same SNE range? 236 if ((seqno >= 0x80000000) && (RCV_PREV_SEQ < 0x80000000)) { 237 // jumps fwd over N/2? 238 RCV_SNE_FLAG = 0; // reset wrap increment flag 239 } 240 RCV_PREV_SEQ = MAX(seqno,RCV_PREV_SEQ); 241 // move prev forward if needed 242 } else { 243 // both in diff SNE ranges 244 if (seqno < 0x80000000) { 245 // jumps forward over zero? 246 RCV_PREV_SEQ = seqno; // update prev 247 if (RCV_SNE_FLAG == 0) { 248 // first jump over zero? (wrap) 249 RCV_SNE_FLAG = 1; 250 // set flag so we increment once 251 RCV_SNE = RCV_SNE + 1; 252 // increment window 253 holdSNE = RCV_SNE; 254 // use updated SNE value 255 } 256 } else { 257 // jump backward over zero 258 holdSNE = RCV_SNE - 1; 259 // use pre-rollover SNE value 260 } 261 } 262 #ifdef SNEDEBUG 263 fprintf(stderr,"state RCV_SNE_FLAG = %1d\n", 264 RCV_SNE_FLAG); 265 fprintf(stderr,"state RCV_SNE = %08lx\n", RCV_SNE); 266 fprintf(stderr,"state RCV_PREV_SEQ = %08lx\n", RCV_PREV_SEQ); 267 #endif 268 return holdSNE; 269 } 270 int main() { 271 // variables used as input and output: 272 unsigned long SEG_SEQ; // input - received SEQ 273 unsigned long SNE; // output - SNE corresponding 274 // to received SEQ 276 // variables used to validate the computed SNE: 277 unsigned long SEG_HIGH; // input - xmitter side SNE 278 // -> SNE should match this value 279 unsigned long long BIG_PREV; // prev 64-bit total seqno 280 unsigned long long BIG_THIS = 0; // current 64-bit total seqno 281 // -> THIS, PREV should never jump 282 // more than half the SEQ space 284 char *prompt = "Hex input (2 groups of 8 hex chars with a 285 space): "; 287 fprintf(stderr,"Input hex numbers only (0x is optional)\n\n"); 289 fprintf(stderr,"%s\n",prompt); 291 while (scanf("%lx %lx",&SEG_HIGH,&SEG_SEQ) == 2) { 292 BIG_PREV = BIG_THIS; 293 BIG_THIS = (((unsigned long long)SEG_HIGH) << 32) 294 | ((unsigned long long)SEG_SEQ); 296 // given SEG_SEQ, compute SNE 297 SNE = compute_sne(SEG_SEQ); 299 fprintf(stderr," SEG_SEQ = %08lx\n", SEG_SEQ); 300 fprintf(stderr," SNE = %08lx\n", SNE); 301 fprintf(stderr," SEG_HIGH = %08lx %s\n",SEG_HIGH, 302 (SEG_HIGH == SNE)? " - OK" : " - ERROR !!!!!!!"); 303 fprintf(stderr,"\t\tthe jump was %16llx %s %s\n", 304 distance(BIG_PREV,BIG_THIS), 305 ((BIG_PREV < BIG_THIS)?"+":"-"), 306 (((distance(BIG_PREV,BIG_THIS)) > 0x7FFFFFFF) 307 ? "ILLEGAL JUMP" : ".")); 308 fprintf(stderr,"\n"); 309 fprintf(stderr,"\n"); 310 fprintf(stderr,"%s\n",prompt); 312 } 313 } 315 5. Validation Suite 317 The following numbers are used to validate sequence number extension 318 variants, and are shown in the order they legitimately could be 319 received. Each line represents a single 64-bit number, represented 320 as two hexadecimal 32-bit numbers with a space between. The numbers 321 are formatted for use in the example code provided in Section 4. 323 A correctly operating extended sequence number system can receive 324 the least-significant half (the right side) and compute the correct 325 most-significant half (the left side) correctly. It specifically 326 tests both forward and backward jumps in received values that 327 represent legitimate reordering. 329 00000000 00000000 330 00000000 30000000 331 00000000 90000000 332 00000000 70000000 333 00000000 a0000000 334 00000001 00000001 335 00000000 e0000000 336 00000001 00000000 337 00000001 7fffffff 338 00000001 00000000 339 00000001 50000000 340 00000001 80000000 341 00000001 00000001 342 00000001 40000000 343 00000001 90000000 344 00000001 b0000000 345 00000002 0fffffff 346 00000002 20000000 347 00000002 90000000 348 00000002 70000000 349 00000002 A0000000 350 00000003 00004000 351 00000002 D0000000 352 00000003 20000000 353 00000003 90000000 354 00000003 70000000 355 00000003 A0000000 356 00000004 00004000 357 00000003 D0000000 359 6. Security Considerations 361 Sequence numbers and their extensions can be useful in a variety of 362 security contexts. Because the extension part (most significant 363 half) is determined by the previously exchanged sequence values 364 (least significant half), the extension should not be considered as 365 adding entropy for the purposes of message authentication or 366 encryption. 368 7. IANA Considerations 370 This document contains no IANA issues. This section should be 371 removed upon publication as an RFC. 373 8. References 375 8.1. Normative References 377 8.2. Informative References 379 [IEN74] Plummmer, W., "Sequence Number Arithmetic," IEN 74, Sept. 380 1978. 382 [RFC793] Postel, J., "Transmission Control Protocol," RFC 793, 383 September 1981. 385 [RFC1034] Mockapetris, P., "Domain Names - Concepts and Facilities," 386 RFC 1034, Nov. 1987. 388 [RFC1035] Mockapetris, P., "Domain Names - Implementation and 389 Specification," Nov. 1987. 391 [RFC1982] Elz, R., Bush, R., "Serial Number Arithmetic," RFC 1982, 392 Aug. 1996. 394 [RFC5925] Touch, J., A. Mankin, R. Bonica, "The TCP Authentication 395 Option," RFC 5925, June 2010. 397 9. Acknowledgments 399 The need for a fix to the pseudocode in RFC5825 was first noted by 400 Juhamatti Kuusisaari in April 2020. 402 This document was prepared using 2-Word-v2.0.template.dot. 404 Authors' Addresses 406 Joe Touch 407 Manhattan Beach, CA 90266 USA 409 Phone: +1 (310) 560-0334 410 Email: touch@strayalpha.com