idnits 2.17.1 draft-touch-sne-02.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 (November 24, 2021) is 882 days in the past. Is this intentional? 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 (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 ISE Stream J. Touch 2 Internet Draft Independent consultant 3 Intended status: Informational November 24, 2021 4 Expires: May 2022 6 Sequence Number Extension for Windowed Protocols 7 draft-touch-sne-02.txt 9 Abstract 11 Sliding window protocols use finite sequence numbers to determine 12 segment placement and order. These sequence number spaces wrap 13 around and are reused during the operation of such protocols. This 14 document describes a way to extend the size of these sequence 15 numbers at the endpoints to avoid the impact of that wrap and reuse 16 without transmitting additional information in the packet header. 17 The resulting extended sequence numbers can be used at the endpoints 18 in encryption and authentication algorithms to ensure input bit 19 patterns do not repeat over the lifetime of a connection. 21 Status of this Memo 23 This document is not an Internet Standards Track specification; it 24 is published for informational purposes. This is a contribution to 25 the RFC Series, independently of any other RFC stream. 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. This document may not be modified, 29 and derivative works of it may not be created, except to format it 30 for publication as an RFC or to translate it into languages other 31 than English. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF), its areas, and its working groups. Note that 35 other groups may also distribute working documents as Internet- 36 Drafts. 38 Internet-Drafts are draft documents valid for a maximum of six 39 months and may be updated, replaced, or obsoleted by other documents 40 at any time. It is inappropriate to use Internet-Drafts as 41 reference material or to cite them other than as "work in progress." 43 The list of current Internet-Drafts can be accessed at 44 http://www.ietf.org/ietf/1id-abstracts.txt 45 The list of Internet-Draft Shadow Directories can be accessed at 46 http://www.ietf.org/shadow.html 48 This Internet-Draft will expire on May 24, 2022. 50 Copyright Notice 52 Copyright (c) 2021 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with 60 respect to this document. Code Components extracted from this 61 document must include Simplified BSD License text as described in 62 Section 4.e of the Trust Legal Provisions and are provided without 63 warranty as described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction...................................................2 68 2. Background.....................................................4 69 3. Related Discussion.............................................5 70 4. Using SNE in Protocol Design...................................6 71 5. Example Code...................................................7 72 6. Validation Suite..............................................10 73 7. Security Considerations.......................................11 74 8. IANA Considerations...........................................11 75 9. References....................................................11 76 9.1. Normative References.....................................11 77 9.2. Informative References...................................11 78 10. Acknowledgments..............................................12 80 1. Introduction 82 Protocols use sequence numbers to maintain ordering and, in sliding 83 window systems, to control the amount of outstanding unacknowledged 84 information. These sequence numbers are finite and thus commonly 85 wrap-around during long connections, reusing past values. 87 It can be useful for protocols to keep track of this wrap-around in 88 a separate counter, such that the sequence number and counter 89 together form an equivalent number space that need not wrap. This 90 technique was introduced as "sequence number extension" in TCP-AO 92 [RFC5925]. The example provided there was intended to introduce the 93 concept, but the pseudocode provided is not complete. 95 This document presents the formal requirements for sequence number 96 extension (SNE), a code example, and a check sequence that can be 97 used to validate this and alternate implementations. Sequence 98 numbers are used in a variety of protocols to support loss 99 detection, reordering, flow control, and congestion control. 100 Limitations in the size of a sequence number protocol field can 101 limit the ways in which these capabilities can be supported. 103 Under certain conditions, it is possible for both endpoints of a 104 protocol to keep track of sequence number rollover and effectively 105 extend the sequence number space without requiring modification of 106 the sequence number field used within protocol messages. These 107 conditions assume that the received sequence numbers never vary by 108 more than half the size of the space of the field used in messages, 109 i.e., they never hop forward or backward by more than half that 110 space. This constraint is typical in sliding window protocols, such 111 as TCP. However, although both ends can track rollover 112 unambiguously, doing so can be surprizingly complex. This document 113 provides examples and test cases to simplify that process. 115 This document is intended for protocol designers who seek to use 116 larger sequence numbers at the endpoints without needing to extend 117 the sequence number field used in messages, such as for 118 authentication protocols, e.g., TCP-AO [RFC5925]. Use of extended 119 sequence numbers should be part of a protocol specification, so that 120 both endpoints can ensure they comply with the requirements needed 121 to enable their use in both locations. 123 The remainder of this document describes how sequence number 124 extension can be supported and provides the pseudocode to 125 demonstrate how received messages can unambiguously determine the 126 appropriate extension value, as long as the reordering is 127 constrained. Section 2 provides background on the concept, Section 128 3 discusses currently known uses of SNE. Section 4 discusses how SNE 129 is used in protocol design and how it differs from in-band use of 130 sequence numbers. Section 5 provides a framework for testing SNE 131 implementations, including example code for the SNE function, and 132 Section 6 provides a sequence that can be used by that code for 133 validation. Section 7 concludes with a discussion of security 134 issues. 136 2. Background 138 Protocols use sequence numbers to maintain message order. The 139 transmitter typically increments them either once per message or by 140 the length of the message. The receiver uses them to reorder 141 messages and detect gaps due to inferred loss. 143 Sequence numbers are represented within those messages (e.g., in the 144 headers) as values of a finite, unsigned number space. This space is 145 typically represented in a fixed-length bit string, whose values 146 range from [0..(2^N)-1], inclusive. 148 The use of finite representations has repercussions on the use of 149 these values at both the transmitter and receiver. Without 150 additional constraints, when the number space "wraps around", it 151 would be impossible for the receiver to distinguish between the uses 152 of the same value. 154 As a consequence, additional constraints are required. Transmitters 155 are typically required to limit reuse until they can assume that 156 receivers would successfully differentiate the two uses of the same 157 value. The receiver always interprets values it sees based on the 158 assumption that successive values never differ by just under half 159 the number space. A receiver cannot detect an error in that 160 sequence, but it will incorrectly interpret numbers if reordering 161 violates this constraint. 163 The constraint requires that "forward" values advance the values by 164 less than half the sequence number space and ensuring that receivers 165 never experience a series of values that violate that rule. 167 We define a sequence space as follows: 169 o An unsigned integer range from 0..(2^N)-1, i.e., for N bits 171 o An operation that increments values in that space by K, where K < 172 2^(N-1), i.e., less than half the range. This operation is used 173 exclusively by the transmitter. 175 o An operation that compares two values in that space to determine 176 their order, e.g., where X < Y implies that X comes before Y 178 We assume that both sides begin with the same initial value, which 179 can be anywhere in the space. That value is either assumed (e.g., 0) 180 before the protocol begins, or coordinated before other messages are 181 exchanged (as with TCP Initial Sequence Numbers, i.e., ISNs 182 [RFC793]). The receiver is assumed to always receive values that are 183 always within (2^N)-1 but that successive received values never jump 184 forward or backward by more than 2^(N-1)-1, i.e., just under half 185 the range. 187 No other operations are supported. The transmitter is not permitted 188 to "backup", such that values are always used in "increment" order. 189 The receiver cannot experience loss or gaps larger than 2^(N-1)-1, 190 which is typically enforced either by assumption or by explicit 191 endpoint coordination. 193 A sequence number extension (SNE) is a separate number space that 194 can be combined with the sequence number to create a larger number 195 space that need not wrap around during a connection. 197 On the transmit side, SNE is trivially accomplished by incrementing 198 a local counter once each time the sequence number increment "wraps" 199 around, or by keeping a larger local sequence number whose least- 200 significant part is the message sequence number and most-significant 201 part can be considered the SNE. The transmitter typically does not 202 need to maintain an SNE except when used in local computations, such 203 as for MACs in TCP-AO [RFC5925]. 205 The goal of this document is to demonstrate that SNE can be 206 accomplished on the receiver side without transmitting additional 207 information in messages. It defines the stateful function 208 compute_sne() as follows: 210 SNE = compute_sne(seqno) 212 Compute_sne() accepts the sequence number seen in a received message 213 and computes the corresponding SNE. The function includes persistent 214 local state that tracks the largest currently received SNE, seqno 215 combination. The concatenation of SNE and seqno emulates the 216 equivalent larger sequence number space that can avoid wrap around. 218 Note that the function defined here is capable of receiving any 219 series of seqno values and computing their correct corresponding 220 SNE, as long as the series never "jumps" more than half the number 221 space "backward" from the largest value seen "forward". 223 3. Related Discussion 225 The DNS uses sequence numbers to determine when a Start of Authority 226 (SOA) serial number is more recent than a previous one, even 227 considering sequence space wrap [RFC1034][RFC1035]. The use of 228 wrapped sequence numbers for sliding windows in network protocols 229 was first described as a sequence number space [IEN74]. 231 A more recent discussion describes this as "serial number 232 arithmetic" and defines a comparison operator it claimed was missing 233 in IEN74 [RFC1982]. That document defines two operations: addition 234 (presumably shifting the window forward) and comparison (defining 235 the order of two values). Addition is defined in that document as 236 limited to value of 0..windowsize/2-1. Comparison is defined in that 237 document by a set of equations therein, but that document does not 238 provide a way for a receiver to compute the correct equivalent SNE, 239 especially including the potential for sequence number reordering, 240 as is demonstrated in this document. 242 4. Using SNE in Protocol Design 244 As noted in the introduction, message sequence numbers enable 245 reordering, loss detection, flow control, and congestion control. 246 They are also used to differentiate otherwise potentially identical 247 messages that might repeat as part of a sequence or stream. 249 The size of sequence number field used within transferred messages 250 defines the ability of a protocol to tolerate reordering and gaps, 251 notably limited to half the space of that field. E.g., a field of 8 252 bits can reorder and detect losses of smaller than 2^7, i.e., 127 253 messages. When used for these purposes - reordering, loss detection, 254 flow control, and congestion control - the size of the field defines 255 the limits of those capabilities. 257 Sequence numbers are also used to differentiate messages; when used 258 this way, they can be problematic if they repeat for otherwise 259 identical messages. Protocols using sequence numbers tolerate that 260 repetition because they are aware of the rollover of these sequence 261 number spaces at both endpoints. In some cases, it can be useful to 262 track this rollover and use the rollover count as an extension to 263 the sequence number, e.g., to differentiate authentication MACs. 264 This sequence number extension (SNE) is never transmitted in 265 messages; the existing rules of sequence number ensure both ends can 266 keep track unambiguously - both for new messages and reordered 267 messages. 269 The constraints required to use SNE have already been presented as 270 background in Section 2. The transmitter must never send messages 271 out of sequence beyond half the range of the sequence number field 272 used in messages. A receiver uses this assumption to interpret 273 whether received numbers are part of pre-wrap sequences or post-wrap 274 sequences. Note that a receiver cannot enforce or detect if the 275 transmitter has violated these assumptions on its own; it relies on 276 explicit coordination to ensure this property is maintained, such as 277 the exchange of acknowledgements. 279 SNE are intended for use when it is helpful for both ends to 280 unambiguously determine whether the sequence number in a message has 281 wrapped, and whether a received message is pre-wrap or post-wrap for 282 each such wrap. This can be used by both endpoints to ensure all 283 messages of arbitrarily long sequences can be differentiated, e.g., 284 ensuring unique message authentication codes (MACs). 286 SNE does not extend the actual sequence space of a protocol, or 287 (thus) its tolerance to reordering or gaps. It also cannot improve 288 its dynamic range for flow control or congestion control, although 289 there are other somewhat related methods that can, such as window 290 scaling [RFC7323] (which increases range at the expense of 291 granularity). 293 SNE is not needed if messages are already unique over the entirety 294 of a transfer sequence, e.g., either because the sequence number 295 field used in its messages never wraparound or because other fields 296 provide that disambiguation, such as timestamps. 298 5. Example Code 300 The following C code is provided as a verified example of sequence 301 number extension from 16 to 32 bits. The code includes both the 302 framework used for validation and the compute_sne() function, the 303 latter of which can be used operationally. 305 A correct test will indicate "OK" for each test. An incorrect test 306 will indicate "ERROR" where applicable. 308 309 #include 310 #include 312 #define distance(x,y) (((x)<(y))?((y)-(x)):((x)-(y))) 314 #define SNEDEBUG 1 316 // This is the core code, stand-alone, to compute SNE from seqno 317 // >> replace this function with your own code to test alternates 318 unsigned long compute_sne(unsigned long seqno) { 319 // INPUT: 32-bit unsigned sequence number (low bits) 320 // OUTPUT: 32-bit unsigned SNE (high bits) 322 // variables used in this code example to compute SNE: 324 static unsigned long 325 RCV_SNE = 0; // high-watermark SNE 326 static int 327 RCV_SNE_FLAG = 1; // set during first half rollover 328 // (prevents re-rollover) 329 static unsigned long 330 RCV_PREV_SEQ = 0; // high-watermark SEQ 331 unsigned long 332 holdSNE; // temp copy of output 334 holdSNE = RCV_SNE; // use current SNE to start 335 if (distance(seqno,RCV_PREV_SEQ) < 0x80000000) { 336 // both in same SNE range? 337 if ((seqno >= 0x80000000) && (RCV_PREV_SEQ < 0x80000000)) { 338 // jumps fwd over N/2? 339 RCV_SNE_FLAG = 0; // reset wrap increment flag 340 } 341 RCV_PREV_SEQ = MAX(seqno,RCV_PREV_SEQ); 342 // move prev forward if needed 343 } else { 344 // both in diff SNE ranges 345 if (seqno < 0x80000000) { 346 // jumps forward over zero? 347 RCV_PREV_SEQ = seqno; // update prev 348 if (RCV_SNE_FLAG == 0) { 349 // first jump over zero? (wrap) 350 RCV_SNE_FLAG = 1; 351 // set flag so we increment once 352 RCV_SNE = RCV_SNE + 1; 353 // increment window 354 holdSNE = RCV_SNE; 355 // use updated SNE value 356 } 357 } else { 358 // jump backward over zero 359 holdSNE = RCV_SNE - 1; 360 // use pre-rollover SNE value 361 } 362 } 363 #ifdef SNEDEBUG 364 fprintf(stderr,"state RCV_SNE_FLAG = %1d\n", 365 RCV_SNE_FLAG); 366 fprintf(stderr,"state RCV_SNE = %08lx\n", RCV_SNE); 367 fprintf(stderr,"state RCV_PREV_SEQ = %08lx\n", RCV_PREV_SEQ); 368 #endif 369 return holdSNE; 370 } 372 int main() { 373 // variables used as input and output: 374 unsigned long SEG_SEQ; // input - received SEQ 375 unsigned long SNE; // output - SNE corresponding 376 // to received SEQ 378 // variables used to validate the computed SNE: 379 unsigned long SEG_HIGH; // input - xmitter side SNE 380 // -> SNE should match this value 381 unsigned long long BIG_PREV; // prev 64-bit total seqno 382 unsigned long long BIG_THIS = 0; // current 64-bit total seqno 383 // -> THIS, PREV should never jump 384 // more than half the SEQ space 386 char *prompt = "Hex input (2 groups of 8 hex chars with a 387 space): "; 389 fprintf(stderr,"Input hex numbers only (0x is optional)\n\n"); 391 fprintf(stderr,"%s\n",prompt); 393 while (scanf("%lx %lx",&SEG_HIGH,&SEG_SEQ) == 2) { 394 BIG_PREV = BIG_THIS; 395 BIG_THIS = (((unsigned long long)SEG_HIGH) << 32) 396 | ((unsigned long long)SEG_SEQ); 398 // given SEG_SEQ, compute SNE 399 SNE = compute_sne(SEG_SEQ); 401 fprintf(stderr," SEG_SEQ = %08lx\n", SEG_SEQ); 402 fprintf(stderr," SNE = %08lx\n", SNE); 403 fprintf(stderr," SEG_HIGH = %08lx %s\n",SEG_HIGH, 404 (SEG_HIGH == SNE)? " - OK" : " - ERROR !!!!!!!"); 405 fprintf(stderr,"\t\tthe jump was %16llx %s %s\n", 406 distance(BIG_PREV,BIG_THIS), 407 ((BIG_PREV < BIG_THIS)?"+":"-"), 408 (((distance(BIG_PREV,BIG_THIS)) > 0x7FFFFFFF) 409 ? "ILLEGAL JUMP" : ".")); 410 fprintf(stderr,"\n"); 411 fprintf(stderr,"\n"); 413 fprintf(stderr,"%s\n",prompt); 415 } 416 } 417 419 6. Validation Suite 421 The following numbers are used to validate sequence number extension 422 variants, and are shown in the order they legitimately could be 423 received. Each line represents a single 64-bit number, represented 424 as two hexadecimal 32-bit numbers with a space between. The numbers 425 are formatted for use in the example code provided in Section 5. 427 A correctly operating extended sequence number system can receive 428 the least-significant half (the right side) and compute the correct 429 most-significant half (the left side) correctly. It specifically 430 tests both forward and backward jumps in received values that 431 represent legitimate reordering. 433 00000000 00000000 434 00000000 30000000 435 00000000 90000000 436 00000000 70000000 437 00000000 a0000000 438 00000001 00000001 439 00000000 e0000000 440 00000001 00000000 441 00000001 7fffffff 442 00000001 00000000 443 00000001 50000000 444 00000001 80000000 445 00000001 00000001 446 00000001 40000000 447 00000001 90000000 448 00000001 b0000000 449 00000002 0fffffff 450 00000002 20000000 451 00000002 90000000 452 00000002 70000000 453 00000002 A0000000 454 00000003 00004000 455 00000002 D0000000 456 00000003 20000000 457 00000003 90000000 458 00000003 70000000 459 00000003 A0000000 460 00000004 00004000 461 00000003 D0000000 463 7. Security Considerations 465 Sequence numbers and their extensions can be useful in a variety of 466 security contexts. Because the extension part (most significant 467 half) is determined by the previously exchanged sequence values 468 (least significant half), the extension should not be considered as 469 adding entropy for the purposes of message authentication or 470 encryption. 472 8. IANA Considerations 474 This document contains no IANA issues. This section should be 475 removed upon publication as an RFC. 477 9. References 479 9.1. Normative References 481 9.2. Informative References 483 [IEN74] Plummmer, W., "Sequence Number Arithmetic," IEN 74, Sept. 484 1978. 486 [RFC793] Postel, J., "Transmission Control Protocol," RFC 793, 487 September 1981. 489 [RFC1034] Mockapetris, P., "Domain Names - Concepts and Facilities," 490 RFC 1034, Nov. 1987. 492 [RFC1035] Mockapetris, P., "Domain Names - Implementation and 493 Specification," Nov. 1987. 495 [RFC1982] Elz, R., Bush, R., "Serial Number Arithmetic," RFC 1982, 496 Aug. 1996. 498 [RFC5925] Touch, J., A. Mankin, R. Bonica, "The TCP Authentication 499 Option," RFC 5925, June 2010. 501 [RFC7323] Borman, D., D. Braden, V. Jacobson, R. Scheffenegger, Ed., 502 "TCP Extensions for High Performance" RFC 7323, Sep. 2014. 504 10. Acknowledgments 506 The need for this document was first noted by Juhamatti Kuusisaari 507 in April 2020 during discussions of the pseudocode in RFC 5925. 509 This document was prepared using 2-Word-v2.0.template.dot. 511 Authors' Addresses 513 Joe Touch 514 Manhattan Beach, CA 90266 USA 516 Phone: +1 (310) 560-0334 517 Email: touch@strayalpha.com