doc: Add RFC documents

1 files changed, 504 insertions, 0 deletions

diff --git a/doc/rfc/rfc9187.txt b/doc/rfc/rfc9187.txt
new file mode 100644
index 0000000..35723c7
--- /dev/null
+++ b/doc/rfc/rfc9187.txt
@@ -0,0 +1,504 @@
+
+
+
+
+Independent Submission                                          J. Touch
+Request for Comments: 9187                        Independent Consultant
+Category: Informational                                     January 2022
+ISSN: 2070-1721
+
+
+            Sequence Number Extension for Windowed Protocols
+
+Abstract
+
+   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.
+
+Status of This Memo
+
+   This document is not an Internet Standards Track specification; it is
+   published for informational purposes.
+
+   This is a contribution to the RFC Series, independently of any other
+   RFC stream.  The RFC Editor has chosen to publish this document at
+   its discretion and makes no statement about its value for
+   implementation or deployment.  Documents approved for publication by
+   the RFC Editor are not candidates for any level of Internet Standard;
+   see Section 2 of RFC 7841.
+
+   Information about the current status of this document, any errata,
+   and how to provide feedback on it may be obtained at
+   https://www.rfc-editor.org/info/rfc9187.
+
+Copyright Notice
+
+   Copyright (c) 2022 IETF Trust and the persons identified as the
+   document authors.  All rights reserved.
+
+   This document is subject to BCP 78 and the IETF Trust's Legal
+   Provisions Relating to IETF Documents
+   (https://trustee.ietf.org/license-info) in effect on the date of
+   publication of this document.  Please review these documents
+   carefully, as they describe your rights and restrictions with respect
+   to this document.
+
+Table of Contents
+
+   1.  Introduction
+   2.  Background
+   3.  Related Discussion
+   4.  Using SNE in Protocol Design
+   5.  Example Code
+   6.  Validation Suite
+   7.  Security Considerations
+   8.  IANA Considerations
+   9.  Informative References
+   Acknowledgments
+   Author's Address
+
+1.  Introduction
+
+   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 commonly
+   wrap around during long connections, reusing past values.
+
+   It can be useful for protocols to keep track of this wrap 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" in the TCP
+   Authentication Option (TCP-AO) [RFC5925].  The example provided there
+   was intended to introduce the concept, but the pseudocode provided is
+   not complete.
+
+   This document presents the formal requirements for Sequence 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.
+
+   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 be surprisingly complex.  This document
+   provides examples and test cases to simplify that process.
+
+   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 [RFC5925].  Use of extended
+   sequence numbers should be part of a protocol specification so that
+   both endpoints can ensure they comply with the requirements needed to
+   enable their use in both locations.
+
+   The remainder of this document describes how SNE 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.  Section 2 provides background on the
+   concept.  Section 3 discusses currently known uses of SNE.  Section 4
+   discusses how SNE is used in protocol design and how it differs from
+   in-band use of sequence numbers.  Section 5 provides a framework for
+   testing SNE implementations, including example code for the SNE
+   function, and Section 6 provides a sequence that can be used by that
+   code for validation.  Section 7 concludes with a discussion of
+   security issues.
+
+2.  Background
+
+   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.
+
+   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, inclusive.
+
+   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.
+
+   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.
+
+   The constraint requires that "forward" values advance the values by
+   less than half the sequence number space, ensuring that receivers
+   never experience a series of values that violate that rule.
+
+   We define a sequence space as follows:
+
+   *  An unsigned integer within the range of 0..(2^N)-1, i.e., for N
+      bits.
+
+   *  An operation that increments values in that space by K, where K <
+      2^(N-1), i.e., less than half the range.  This operation is used
+      exclusively by the transmitter.
+
+   *  An operation that compares two values in that space to determine
+      their order, e.g., where X < Y implies that X comes before Y.
+
+   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 protocol begins or coordinated before other messages are
+   exchanged (as with TCP Initial Sequence Numbers (ISNs) [RFC0793]).
+   It is assumed that the receiver always receives values that are
+   always within (2^N)-1, but the successive received values never jump
+   forward or backward by more than 2^(N-1)-1, i.e., just under half the
+   range.
+
+   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 than 2^(N-1)-1,
+   which is typically enforced either by assumption or by explicit
+   endpoint coordination.
+
+   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.
+
+   On the transmit side, SNE is trivially accomplished by incrementing a
+   local counter once each time the sequence number increment "wraps"
+   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 for Message Authentication Codes (MACs) in TCP-AO [RFC5925].
+
+   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:
+
+         SNE = compute_sne(seqno)
+
+   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
+   received SNE and seqno combination.  The concatenation of SNE and
+   seqno emulates the equivalent larger sequence number space that can
+   avoid wrap around.
+
+   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".
+
+3.  Related Discussion
+
+   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 [RFC1034][RFC1035].  The use of
+   wrapped sequence numbers for sliding windows in network protocols was
+   first described as a sequence number space [IEN74].
+
+   A more recent discussion describes this as "serial number arithmetic"
+   and defines a comparison operator it claimed was missing in IEN-74
+   [RFC1982].  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 to values 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.
+
+4.  Using SNE in Protocol Design
+
+   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.
+
+   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.  For example,
+   a field of 8 bits can reorder and detect losses of smaller than 2^7,
+   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.
+
+   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.  This
+   SNE is never transmitted in messages; the existing rules of sequence
+   numbers ensure both ends can keep track unambiguously -- both for new
+   messages and reordered messages.
+
+   The constraints required to use SNE have already been presented as
+   background in Section 2.  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.
+
+   SNEs are intended for use when it is helpful for both ends to
+   unambiguously determine whether the sequence number in a message has
+   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 unique MACs.
+
+   SNE does not extend the actual sequence space of a 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
+   [RFC7323] (which increases range at the expense of granularity).
+
+   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 never wrap around or because other fields
+   provide that disambiguation, such as timestamps.
+
+5.  Example Code
+
+   The following C code is provided as a verified example of SNE 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.
+
+   A correct test will indicate "OK" for each test.  An incorrect test
+   will indicate "ERROR" where applicable.
+
+   <CODE BEGINS> file "compute_sne.c"
+   #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 = "Input hex numbers only (0x is 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>
+
+6.  Validation Suite
+
+   The following numbers are used to validate 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 Section 5.
+
+   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.
+
+   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
+
+7.  Security Considerations
+
+   Sequence numbers and their extensions can be useful in a variety of
+   security contexts.  Because the extension part (most-significant
+   half) is determined by the previously exchanged sequence values
+   (least-significant half), the extension should not be considered as
+   adding entropy for the purposes of message authentication or
+   encryption.
+
+8.  IANA Considerations
+
+   This document has no IANA actions.
+
+9.  Informative References
+
+   [IEN74]    Plummmer, W., "Sequence Number Arithmetic", IEN-74,
+              September 1978.
+
+   [RFC0793]  Postel, J., "Transmission Control Protocol", STD 7,
+              RFC 793, DOI 10.17487/RFC0793, September 1981,
+              <https://www.rfc-editor.org/info/rfc793>.
+
+   [RFC1034]  Mockapetris, P., "Domain names - concepts and facilities",
+              STD 13, RFC 1034, DOI 10.17487/RFC1034, November 1987,
+              <https://www.rfc-editor.org/info/rfc1034>.
+
+   [RFC1035]  Mockapetris, P., "Domain names - implementation and
+              specification", STD 13, RFC 1035, DOI 10.17487/RFC1035,
+              November 1987, <https://www.rfc-editor.org/info/rfc1035>.
+
+   [RFC1982]  Elz, R. and R. Bush, "Serial Number Arithmetic", RFC 1982,
+              DOI 10.17487/RFC1982, August 1996,
+              <https://www.rfc-editor.org/info/rfc1982>.
+
+   [RFC5925]  Touch, J., Mankin, A., and R. Bonica, "The TCP
+              Authentication Option", RFC 5925, DOI 10.17487/RFC5925,
+              June 2010, <https://www.rfc-editor.org/info/rfc5925>.
+
+   [RFC7323]  Borman, D., Braden, B., Jacobson, V., and R.
+              Scheffenegger, Ed., "TCP Extensions for High Performance",
+              RFC 7323, DOI 10.17487/RFC7323, September 2014,
+              <https://www.rfc-editor.org/info/rfc7323>.
+
+Acknowledgments
+
+   The need for this document was first noted by Juhamatti Kuusisaari in
+   April 2020 during discussions of the pseudocode in RFC 5925.
+
+Author's Address
+
+   Joe Touch
+   Manhattan Beach, CA 90266
+   United States of America
+
+   Phone: +1 (310) 560-0334
+   Email: touch@strayalpha.com