<?xmlversion='1.0' encoding='utf-8'?>version="1.0" encoding="UTF-8"?> <!DOCTYPE rfcSYSTEM "rfc2629.dtd"[ <!ENTITYRFC793 SYSTEM "https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.0793.xml">nbsp " "> <!ENTITYRFC1034 SYSTEM "https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.1034.xml">zwsp "​"> <!ENTITYRFC1035 SYSTEM "https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.1035.xml">nbhy "‑"> <!ENTITYRFC1982 SYSTEM "https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.1982.xml"> <!ENTITY RFC5925 SYSTEM "https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.5925.xml"> <!ENTITY RFC7323 SYSTEM "https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.7323.xml">wj "⁠"> ]> <rfcsubmissionType="IETF"xmlns:xi="http://www.w3.org/2001/XInclude" docName="draft-touch-sne-02" number="9187" submissionType="independent" category="info"ipr="trust200902">ipr="trust200902" obsoletes="" updates="" xml:lang="en" symRefs="true" sortRefs="true" tocInclude="true" version="3"> <!-- xml2rfc v2v3 conversion 3.12.0 --> <!-- Generated by id2xml 1.5.0 on 2021-12-09T00:38:40Z --><?rfc strict="yes"?> <?rfc compact="yes"?> <?rfc subcompact="no"?> <?rfc symrefs="yes"?> <?rfc sortrefs="no"?> <?rfc text-list-symbols="o*+-"?> <?rfc toc="yes"?><front> <title abbrev="Sequence Number Extension">Sequence Number Extension for Windowed Protocols</title> <seriesInfo name="RFC" value="9187"/> <author initials="J." surname="Touch" fullname="Joe Touch"> <organization abbrev="Independentconsultant"></organization>Consultant"/> <address> <postal><street></street><street/> <city>Manhattan Beach</city> <region>CA</region> <code>90266</code><country>USA</country><country>United States of America</country> </postal> <phone>+1 (310) 560-0334</phone> <email>touch@strayalpha.com</email> </address> </author> <dateyear="2021" month="December"/>year="2022" month="January"/> <workgroup>ISE Stream</workgroup><!-- [rfced] Please insert any keywords (beyond those that appear in the title) for use on https://www.rfc-editor.org/search. --> <keyword>example</keyword> <abstract><t><keyword>TCP-AO</keyword> <keyword>TCP</keyword> <abstract> <t> Sliding window protocols use finite sequence numbers to determine segment placement and order. These sequence number spaces wrap around and are reused during the operation of such protocols. This document describes a way to extend the size of these sequence numbers at the endpoints to avoid the impact of that wrap and reuse without transmitting additional information in the packet header. The resulting extended sequence numbers can be used at the endpoints in encryption and authentication algorithms to ensure input bit patterns do not repeat over the lifetime of a connection.</t> </abstract> </front> <middle> <sectiontitle="Introduction" anchor="sect-1"><t>anchor="sect-1" numbered="true" toc="default"> <name>Introduction</name> <t> Protocols use sequence numbers to maintain ordering and, in sliding window systems, to control the amount of outstanding unacknowledged information. These sequence numbers are finite and thus commonlywrap-aroundwrap around during long connections, reusing past values.</t> <t> It can be useful for protocols to keep track of thiswrap-aroundwrap around in a separate counter, such that the sequence number and counter together form an equivalent number space that need not wrap. This technique was introduced as"sequence number extension""Sequence Number Extension" inTCP-AOthe TCP Authentication Option (TCP-AO) <xreftarget="RFC5925"/>.target="RFC5925" format="default"/>. The example provided there was intended to introduce the concept, but the pseudocode provided is not complete.</t> <t> This document presents the formal requirements forsequence number extensionSequence Number Extension (SNE), a code example, and a check sequence that can be used to validate this and alternate implementations. Sequence numbers are used in a variety of protocols to support loss detection, reordering, flow control, and congestion control. Limitations in the size of a sequence number protocol field can limit the ways in which these capabilities can be supported.</t> <t> Under certain conditions, it is possible for both endpoints of a protocol to keep track of sequence number rollover and effectively extend the sequence number space without requiring modification of the sequence number field used within protocol messages. These conditions assume that the received sequence numbers never vary by more than half the size of the space of the field used in messages, i.e., they never hop forward or backward by more than half that space. This constraint is typical in sliding window protocols, such as TCP. However, although both ends can track rollover unambiguously, doing so can besurprizinglysurprisingly complex. This document provides examples and test cases to simplify that process.</t> <t> This document is intended for protocol designers who seek to use larger sequence numbers at the endpoints without needing to extend the sequence number field used in messages, such as for authentication protocols, e.g., TCP-AO <xreftarget="RFC5925"/>.target="RFC5925" format="default"/>. Use of extended sequence numbers should be part of a protocolspecification,specification so that both endpoints can ensure they comply with the requirements needed to enable their use in both locations.</t> <t> The remainder of this document describes howsequence number extensionSNE can be supported and provides the pseudocode to demonstrate how received messages can unambiguously determine the appropriate extension value, as long as the reordering is constrained. <xreftarget="sect-2"/>target="sect-2" format="default"/> provides background on theconcept,concept. <xreftarget="sect-3"/>target="sect-3" format="default"/> discusses currently known uses of SNE. <xreftarget="sect-4"/>target="sect-4" format="default"/> discusses how SNE is used in protocol design and how it differs from in-band use of sequence numbers. <xreftarget="sect-5"/>target="sect-5" format="default"/> provides a framework for testing SNE implementations, including example code for the SNE function, and <xreftarget="sect-6"/>target="sect-6" format="default"/> provides a sequence that can be used by that code for validation. <xreftarget="sect-7"/>target="sect-7" format="default"/> concludes with a discussion of security issues.</t> </section> <sectiontitle="Background" anchor="sect-2"><t>anchor="sect-2" numbered="true" toc="default"> <name>Background</name> <t> Protocols use sequence numbers to maintain message order. The transmitter typically increments them either once per message or by the length of the message. The receiver uses them to reorder messages and detect gaps due to inferred loss.</t> <t> Sequence numbers are represented within those messages (e.g., in the headers) as values of a finite, unsigned number space. This space is typically represented in a fixed-length bit string, whose values range from[0..(2^N)-1],0..(2<sup>N</sup>)-1, inclusive.</t> <t> The use of finite representations has repercussions on the use of these values at both the transmitter and receiver. Without additional constraints, when the number space "wraps around", it would be impossible for the receiver to distinguish between the uses of the same value.</t> <t> As a consequence, additional constraints are required. Transmitters are typically required to limit reuse until they can assume that receivers would successfully differentiate the two uses of the same value. The receiver always interprets values it sees based on the assumption that successive values never differ by just under half the number space. A receiver cannot detect an error in that sequence, but it will incorrectly interpret numbers if reordering violates this constraint.</t> <t> The constraint requires that "forward" values advance the values by less than half the sequence numberspace andspace, ensuring that receivers never experience a series of values that violate that rule.</t> <t> We define a sequence space as follows:</t><t><list style="symbols"><t>An<ul spacing="normal"> <li>An unsigned integer within the rangefrom 0..(2^N)-1,of 0..(2<sup>N</sup>)-1, i.e., for Nbits</t> <t>Anbits.</li> <li>An operation that increments values in that space by K, where K <2^(N-1),2<sup>(N-1)</sup>, i.e., less than half the range. This operation is used exclusively by thetransmitter.</t> <t>Antransmitter.</li> <li>An operation that compares two values in that space to determine their order, e.g., whereX < YX < Y implies that X comes beforeY</t> </list> </t>Y.</li> </ul> <t> We assume that both sides begin with the same initial value, which can be anywhere in the space. That value is either assumed (e.g., 0) before the protocolbegins,begins or coordinated before other messages are exchanged (as with TCP Initial SequenceNumbers, i.e., ISNsNumbers (ISNs) <xreftarget="RFC0793"/>). The receivertarget="RFC0793" format="default"/>). It is assumedtothat the receiver alwaysreceivereceives values that are always within(2^N)-1(2<sup>N</sup>)-1, butthatthe successive received values never jump forward or backward by more than2^(N-1)-1,2<sup>(N-1)</sup>-1, i.e., just under half the range.</t> <t> No other operations are supported. The transmitter is not permitted to "backup", such that values are always used in "increment" order. The receiver cannot experience loss or gaps larger than2^(N-1)-1,2<sup>(N-1)</sup>-1, which is typically enforced either by assumption or by explicit endpoint coordination.</t> <t>A sequence number extension (SNE)An SNE is a separate number space that can be combined with the sequence number to create a larger number space that need not wrap around during a connection.</t> <t> On the transmit side, SNE is trivially accomplished by incrementing a local counter once each time the sequence number increment "wraps"around,around or by keeping a larger local sequence number whose least-significant part is the message sequence number and most-significant part can be considered the SNE. The transmitter typically does not need to maintain an SNE except when used in local computations, such as forMACsMessage Authentication Codes (MACs) in TCP-AO <xreftarget="RFC5925"/>.</t>target="RFC5925" format="default"/>.</t> <t> The goal of this document is to demonstrate that SNE can be accomplished on the receiver side without transmitting additional information in messages. It defines the stateful function compute_sne() as follows:</t><figure><artwork><![CDATA[ SNE<t indent="6">SNE =compute_sne(seqno) ]]></artwork> </figure> <t> Compute_sne()compute_sne(seqno)</t> <t>The compute_sne() function accepts the sequence number seen in a received message and computes the corresponding SNE. The function includes persistent local state that tracks the largest currently receivedSNE,SNE and seqno combination. The concatenation of SNE and seqno emulates the equivalent larger sequence number space that can avoid wrap around.</t> <t> Note that the function defined here is capable of receiving any series of seqno values and computing their correct corresponding SNE, as long as the series never "jumps" more than half the number space "backward" from the largest value seen "forward".</t> </section> <sectiontitle="Related Discussion" anchor="sect-3"><t>anchor="sect-3" numbered="true" toc="default"> <name>Related Discussion</name> <t> The DNS uses sequence numbers to determine when a Start of Authority (SOA) serial number is more recent than a previous one, even considering sequence space wrap <xreftarget="RFC1034"/><xref target="RFC1035"/>.target="RFC1034" format="default"/><xref target="RFC1035" format="default"/>. The use of wrapped sequence numbers for sliding windows in network protocols was first described as a sequence number space <xreftarget="IEN74"/>.</t>target="IEN74" format="default"/>.</t> <t> A more recent discussion describes this as "serial number arithmetic" and defines a comparison operator it claimed was missing inIEN74IEN-74 <xreftarget="RFC1982"/>.target="RFC1982" format="default"/>. That document defines two operations: addition (presumably shifting the window forward) and comparison (defining the order of two values). Addition is defined in that document as limited tovaluevalues within the range of 0..windowsize/2-1. Comparison is defined in that document by a set of equations therein, but that document does not provide a way for a receiver to compute the correct equivalent SNE, especially including the potential for sequence number reordering, as is demonstrated in this document.</t> </section> <sectiontitle="Usinganchor="sect-4" numbered="true" toc="default"> <name>Using SNE in ProtocolDesign" anchor="sect-4"><t>Design</name> <t> As noted in the introduction, message sequence numbers enable reordering, loss detection, flow control, and congestion control. They are also used to differentiate otherwise potentially identical messages that might repeat as part of a sequence or stream.</t> <t> The size of the sequence number field used within transferred messages defines the ability of a protocol to tolerate reordering and gaps, notably limited to half the space of that field.E.g.,For example, a field of 8 bits can reorder and detect losses of smaller than2^7,2<sup>7</sup>, i.e., 127 messages. When used for these purposes--- reordering, loss detection, flow control, and congestion control--- the size of the field defines the limits of those capabilities.</t> <t> Sequence numbers are also used to differentiate messages; when used this way, they can be problematic if they repeat for otherwise identical messages. Protocols using sequence numbers tolerate that repetition because they are aware of the rollover of these sequence number spaces at both endpoints. In some cases, it can be useful to track this rollover and use the rollover count as an extension to the sequence number, e.g., to differentiate authentication MACs. Thissequence number extension (SNE)SNE is never transmitted in messages; the existing rules of sequencenumbernumbers ensure both ends can keep track unambiguously--- both for new messages and reordered messages.</t> <t> The constraints required to use SNE have already been presented as background in <xreftarget="sect-2"/>.target="sect-2" format="default"/>. The transmitter must never send messages out of sequence beyond half the range of the sequence number field used in messages. A receiver uses this assumption to interpret whether received numbers are part of pre-wrap sequences or post-wrap sequences. Note that a receiver cannot enforce or detect if the transmitter has violated these assumptions on its own; it relies on explicit coordination to ensure this property is maintained, such as the exchange of acknowledgements.</t> <t>SNESNEs are intended for use when it is helpful for both ends to unambiguously determine whether the sequence number in a message haswrapped,wrapped and whether a received message is pre-wrap or post-wrap for each such wrap. This can be used by both endpoints to ensure all messages of arbitrarily long sequences can be differentiated, e.g., ensuring uniquemessage authentication codes (MACs).</t>MACs.</t> <t> SNE does not extend the actual sequence space of aprotocol,protocol or (thus) its tolerance to reordering or gaps. It also cannot improve its dynamic range for flow control or congestion control, although there are other somewhat related methods that can, such as window scaling <xreftarget="RFC7323"/>target="RFC7323" format="default"/> (which increases range at the expense of granularity).</t> <t> SNE is not needed if messages are already unique over the entirety of a transfer sequence, e.g., either because the sequence number field used in its messages neverwraparoundwrap around or because other fields provide that disambiguation, such as timestamps.</t> </section> <sectiontitle="Example Code" anchor="sect-5"><t>anchor="sect-5" numbered="true" toc="default"> <name>Example Code</name> <t> The following C code is provided as a verified example ofsequence number extensionSNE from 16 to 32 bits. The code includes both the framework used for validation and the compute_sne() function, the latter of which can be used operationally.</t> <t> A correct test will indicate "OK" for each test. An incorrect test will indicate "ERROR" where applicable.</t><figure><artwork><![CDATA[ <CODE BEGINS><sourcecode name="compute_sne.c" type="c" markers="true"><![CDATA[ #include <stdio.h> #include <sys/param.h> #define distance(x,y) (((x)<(y))?((y)-(x)):((x)-(y))) #define SNEDEBUG 1 // This is the core code, stand-alone, to compute SNE from seqno // >> replace this function with your own code to test alternates unsigned long compute_sne(unsigned long seqno) { // INPUT: 32-bit unsigned sequence number (low bits) // OUTPUT: 32-bit unsigned SNE (high bits) // variables used in this code example to compute SNE: static unsigned long RCV_SNE = 0; // high-watermark SNE static int RCV_SNE_FLAG = 1; // set during first half rollover // (prevents re-rollover) static unsigned long RCV_PREV_SEQ = 0; // high-watermark SEQ unsigned long holdSNE; // temp copy of output holdSNE = RCV_SNE; // use current SNE to start if (distance(seqno,RCV_PREV_SEQ) < 0x80000000) { // both in same SNE range? if ((seqno >= 0x80000000) && (RCV_PREV_SEQ < 0x80000000)) { // jumps fwd over N/2? RCV_SNE_FLAG = 0; // reset wrap increment flag } RCV_PREV_SEQ = MAX(seqno,RCV_PREV_SEQ); // move prev forward if needed } else { // both in diff SNE ranges if (seqno < 0x80000000) { // jumps forward over zero? RCV_PREV_SEQ = seqno; // update prev if (RCV_SNE_FLAG == 0) { // first jump over zero? (wrap) RCV_SNE_FLAG = 1; // set flag so we increment once RCV_SNE = RCV_SNE + 1; // increment window holdSNE = RCV_SNE; // use updated SNE value } } else { // jump backward over zero holdSNE = RCV_SNE - 1; // use pre-rollover SNE value } } #ifdef SNEDEBUG fprintf(stderr,"state RCV_SNE_FLAG = %1d\n", RCV_SNE_FLAG); fprintf(stderr,"state RCV_SNE = %08lx\n", RCV_SNE); fprintf(stderr,"state RCV_PREV_SEQ = %08lx\n", RCV_PREV_SEQ); #endif return holdSNE; } int main() { // variables used as input and output: unsigned long SEG_SEQ; // input - received SEQ unsigned long SNE; // output - SNE corresponding // to received SEQ // variables used to validate the computed SNE: unsigned long SEG_HIGH; // input - xmitter side SNE // -> SNE should match this value unsigned long long BIG_PREV; // prev 64-bit total seqno unsigned long long BIG_THIS = 0; // current 64-bit total seqno // -> THIS, PREV should never jump // more than half the SEQ space char *prompt ="Hex input (2 groups of 8 hex chars with a space): "; fprintf(stderr,"Input"Input hex numbers only (0x isoptional)\n\n");optional)\n\n") "\tHex input\n" "\t(2 hex numbers separated by whitespace," "each with 8 or fewer digits)"; fprintf(stderr,"%s\n",prompt); while (scanf("%lx %lx",&SEG_HIGH,&SEG_SEQ) == 2) { BIG_PREV = BIG_THIS; BIG_THIS = (((unsigned long long)SEG_HIGH) << 32) | ((unsigned long long)SEG_SEQ); // given SEG_SEQ, compute SNE SNE = compute_sne(SEG_SEQ); fprintf(stderr," SEG_SEQ = %08lx\n", SEG_SEQ); fprintf(stderr," SNE = %08lx\n", SNE); fprintf(stderr," SEG_HIGH = %08lx %s\n",SEG_HIGH, (SEG_HIGH == SNE)? " - OK" : " - ERROR !!!!!!!"); fprintf(stderr,"\t\tthe jump was %16llx %s %s\n", distance(BIG_PREV,BIG_THIS), ((BIG_PREV < BIG_THIS)?"+":"-"), (((distance(BIG_PREV,BIG_THIS)) > 0x7FFFFFFF) ? "ILLEGAL JUMP" : ".")); fprintf(stderr,"\n"); fprintf(stderr,"\n"); fprintf(stderr,"%s\n",prompt); } }<CODE ENDS> ]]></artwork> </figure>]]></sourcecode> </section> <sectiontitle="Validation Suite" anchor="sect-6"><t>anchor="sect-6" numbered="true" toc="default"> <name>Validation Suite</name> <t> The following numbers are used to validatesequence number extension variants,SNE variants and are shown in the order they legitimately could be received. Each line represents a single 64-bit number, represented as two hexadecimal 32-bit numbers with a space between. The numbers are formatted for use in the example code provided in <xreftarget="sect-5"/>.</t>target="sect-5" format="default"/>.</t> <t> A correctly operating extended sequence number system can receive the least-significant half (the right side) and compute the correct most-significant half (the left side) correctly. It specifically tests both forward and backward jumps in received values that represent legitimate reordering.</t><figure><artwork><![CDATA[<sourcecode name="sne_testvectors.txt" type="test-vector"><![CDATA[ 00000000 00000000 00000000 30000000 00000000 90000000 00000000 70000000 00000000 a0000000 00000001 00000001 00000000 e0000000 00000001 00000000 00000001 7fffffff 00000001 00000000 00000001 50000000 00000001 80000000 00000001 00000001 00000001 40000000 00000001 90000000 00000001 b0000000 00000002 0fffffff 00000002 20000000 00000002 90000000 00000002 70000000 00000002 A0000000 00000003 00004000 00000002 D0000000 00000003 20000000 00000003 90000000 00000003 70000000 00000003 A0000000 00000004 00004000 00000003 D0000000]]></artwork> </figure>]]></sourcecode> </section> <sectiontitle="Security Considerations" anchor="sect-7"><t>anchor="sect-7" numbered="true" toc="default"> <name>Security Considerations</name> <t> Sequence numbers and their extensions can be useful in a variety of security contexts. Because the extension part(most significant(most-significant half) is determined by the previously exchanged sequence values(least significant(least-significant half), the extension should not be considered as adding entropy for the purposes of message authentication or encryption.</t> </section> <sectiontitle="IANA Considerations" anchor="sect-8"><t> Thisanchor="sect-8" numbered="true" toc="default"> <name>IANA Considerations</name> <t>This documentcontainshas no IANAissues. This section should be removed upon publication as an RFC.</t>actions.</t> </section> </middle> <back><references title="Informative References"><references> <name>Informative References</name> <referenceanchor="IEN74"><front>anchor="IEN74"> <front> <title>Sequence Number Arithmetic</title> <author initials="W." surname="Plummmer"fullname="W.fullname="William W. Plummmer"> </author> <date month="September" year="1978"/> </front><seriesInfo name="IEN" value="74"/><refcontent>IEN-74</refcontent> </reference>&RFC793; &RFC1034; &RFC1035; &RFC1982; &RFC5925; &RFC7323;<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.0793.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.1034.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.1035.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.1982.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.5925.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.7323.xml"/> </references> <sectiontitle="Acknowledgments" anchor="sect-10"><t>anchor="sect-10" numbered="false" toc="default"> <name>Acknowledgments</name> <t> The need for this document was first noted byJuhamatti Kuusisaari<contact fullname="Juhamatti Kuusisaari"/> in April 2020 during discussions of the pseudocode in RFC 5925.</t><t> This document was prepared using 2-Word-v2.0.template.dot.</t></section> </back> </rfc>