RFC 9187

Sequence Number Extension for Windowed Protocols

📅 published January 2022, from ietf

RFC 9187 🎀: Sequence Number Extension for Windowed Protocols

okay bestie, let's get into RFC 9187 💅 It's titled Sequence Number Extension for Windowed Protocols, and it's an Independent Submission by J. Touch of Independent Consultant. The category is Informational and the date is January 2022. Its ISSN is 2070-1721. The header doesn't list anything it obsoletes or updates 🦋

Abstract ✨

Sliding window protocols use finite sequence numbers to figure out where each segment goes and what order it's in 📦 Those numbers wrap around and get reused while the protocol is running. This document shows how the endpoints can extend the size of those numbers, so the wrap-and-reuse thing stops mattering, and it doesn't need any extra info in the packet header 🌸 The extended numbers can then go into encryption and authentication algorithms, so the input bit patterns never repeat over the whole life of a connection 🔐

Status of This Memo

this one's not an Internet Standards Track spec, it's just published for information 📚

It's an independent contribution to the RFC Series, separate from any other RFC stream. The RFC Editor picked to publish it at their discretion, and they make zero claims about whether it's worth implementing or deploying 🙈 Anything the RFC Editor approves for publication isn't eligible for any level of Internet Standard. (Check Section 2 of RFC 7841 for the details.)

For the current status, any errata, and how to send feedback, head to https://www.rfc-editor.org/info/rfc9187 💜

Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved 🎀

This document is subject to BCP 78 and to the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info), as they stand on the publication date. Read those carefully, because they spell out your rights and restrictions for 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 💖

okay so protocols use sequence numbers to keep things in order, and in sliding window systems they also control how much unacknowledged stuff can be floating around at once 🪟 These numbers are finite, so they wrap around during long connections and end up reusing old values 🔄

It can be super useful for protocols to track that wrap-around in a separate counter. Then the sequence number and the counter together make a number space that is effectively equivalent and never has to wrap 🧚 This idea was introduced as "Sequence Number Extension" in the TCP Authentication Option (TCP-AO) [RFC5925]. The example there was meant to introduce the concept, but the pseudocode it gives isn't complete 🙈

This document brings the formal requirements for Sequence Number Extension (SNE), a code example, and a check sequence that you can use to validate this implementation and any alternate ones 🦋 Sequence numbers show up in lots of protocols to support loss detection, reordering, flow control, and congestion control ✨ But because the size of a sequence number field is limited, those capabilities can only be supported in certain ways 💅

Under certain conditions, both endpoints of a protocol can track sequence number rollover and effectively extend the sequence number space, without changing the sequence number field used in messages 🌈 Those conditions assume that received sequence numbers never vary by more than half the size of the field's space. In other words, they never hop forward or backward by more than half that space 🎀 This constraint is typical for sliding window protocols, TCP being a prime example. Still, even though both ends can track rollover unambiguously, it can get surprisingly complex, so this document gives examples and test cases to make that process easier 🫶

This document is for protocol designers who want larger sequence numbers at the endpoints without having to extend the sequence number field in messages. Authentication protocols are a good example, such as TCP-AO [RFC5925] 🔐 Using extended sequence numbers should be part of a protocol specification, so that both endpoints can make sure they meet the requirements needed to use them in both places 👑

Here's the roadmap 🗺️ The rest of this document explains how SNE can be supported, and gives pseudocode showing how received messages can unambiguously work out the right extension value, as long as reordering is constrained. Section 2 gives background on the concept. Section 3 covers currently known uses of SNE. Section 4 explains 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 the code can use for validation. Section 7 wraps up with a discussion of security issues 💀

2. Background 🌸

Protocols use sequence numbers to keep messages in order 📬 The transmitter usually increments them either once per message or by the length of the message. The receiver uses them to reorder messages and to detect gaps that point to inferred loss 🔍

Sequence numbers are represented inside those messages (for example, in the headers) as values from a finite, unsigned number space 🧮 That space is usually represented as a fixed-length bit string, with values ranging from 0..(2^N)-1, inclusive.

Using finite representations has consequences for how these values get used at both the transmitter and the receiver ⚠️ Without extra constraints, once the number space "wraps around", the receiver couldn't tell apart two uses of the same value 😭

So extra constraints are needed. Transmitters are typically required to limit reuse until they can assume receivers will successfully tell the two uses of a value apart 🫶 The receiver always reads the values it sees on the assumption that successive values never differ by just under half the number space. The receiver can't detect an error in that sequence, but it will read numbers incorrectly if reordering breaks this constraint 🙃

The constraint says "forward" values advance by less than half the sequence number space. That way, receivers never see a series of values that breaks the rule 🦋

We define a sequence space like this:

  • An unsigned integer within the range of 0..(2^N)-1, meaning N bits.
  • An operation that increments values in that space by K, where K < 2^(N-1), meaning less than half the range. Only the transmitter uses this operation 📤
  • An operation that compares two values in that space to determine their order, for example where X < Y means that X comes before Y 🔢

We assume both sides begin with the same initial value, which can be anywhere in the space 🎀 That value is either assumed (for example, 0) before the protocol starts, or coordinated before other messages get exchanged, like TCP Initial Sequence Numbers (ISNs) [RFC0793]. The receiver is assumed to always receive values that are always within (2^N)-1, but successive received values never jump forward or backward by more than 2^(N-1)-1, meaning just under half the range 💖

No other operations are supported. The transmitter isn't allowed to "back up", so values are always used in "increment" order 🚫 The receiver can't experience loss or gaps larger than 2^(N-1)-1, which is usually 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 make a larger number space that doesn't need to wrap around during a connection 🌈

On the transmit side, SNE is pretty straightforward. You increment a local counter each time the sequence number increment wraps around, or you keep a larger local sequence number whose least-significant part is the message sequence number, and whose most-significant part can be treated as the SNE 🧁 The transmitter usually doesn't need to maintain an SNE except when it's used in local computations, like Message Authentication Codes (MACs) in TCP-AO [RFC5925] 🔐

The goal of this document is to show that SNE can be done on the receiver side without sending any extra info in messages ✨ It defines the stateful function compute_sne() like this:

SNE = compute_sne(seqno)

The compute_sne() function takes the sequence number seen in a received message and works out the matching SNE 🧠 The function keeps persistent local state that tracks the largest SNE and seqno combination received so far. Put SNE and seqno together and you get the equivalent larger sequence number space that can avoid wrap-around 🎀

Note that the function defined here can take any series of seqno values and compute their correct SNE, as long as the series never "jumps" more than half the number space "backward" from the largest value seen "forward" 💅

The DNS uses sequence numbers to figure out when a Start of Authority (SOA) serial number is more recent than an earlier one, even when the sequence space wraps [RFC1034][RFC1035] 🌐 Using wrapped sequence numbers for sliding windows in network protocols was first described as a sequence number space in [IEN74] 🕰️

A more recent discussion calls this "serial number arithmetic" and defines a comparison operator that it says was missing from IEN-74 [RFC1982] 🧮 That document defines two operations: addition (presumably shifting the window forward) and comparison (defining the order of two values). Addition is limited in that document to values within the range of 0..windowsize/2-1. Comparison is defined there by a set of equations, but that document doesn't give a way for a receiver to compute the correct equivalent SNE. That gap is especially true once you account for sequence number reordering, which this document demonstrates 🔥

4. Using SNE in Protocol Design ✨

okay so, like I said in the intro, message sequence numbers are what make reordering, loss detection, flow control, and congestion control possible 💖 They also help tell apart messages that would otherwise look identical, especially when they keep repeating as part of a sequence or stream 🎀

Here's the big thing: the size of the sequence number field in transferred messages decides how much reordering and how many gaps a protocol can handle, and that's capped at half the space of that field 🦋 For example, an 8-bit field can reorder and detect losses of anything smaller than 2^7, which is 127 messages. So when we use sequence numbers for reordering, loss detection, flow control, and congestion control, the field size is literally the limit of what those can do 💅

Sequence numbers can also tell messages apart, and this is where it gets messy 🙈 If they repeat for messages that are otherwise identical, that can be a problem. Protocols are fine with the repetition because both endpoints know when the sequence number space rolls over 🌈 Sometimes it's useful to track that rollover and use the rollover count as an extension to the sequence number, e.g., to tell authentication MACs apart 🧚 This SNE is never sent in any message. The existing sequence number rules keep both ends in sync, for new messages and reordered ones too ✨

The constraints for using SNE were already covered 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 🫶 The receiver relies on that assumption to figure out whether a received number belongs to a pre-wrap sequence or a post-wrap sequence. ngl this is a big ask, because a receiver can't enforce or detect on its own if the transmitter breaks it 😭 So it depends on explicit coordination, like the exchange of acknowledgements, to keep this property true 🌸

SNEs are for when it's helpful for both ends to know, without any doubt, whether the sequence number in a message has wrapped, and whether a received message is pre-wrap or post-wrap for each wrap. Both endpoints can use this to make sure every message in an arbitrarily long sequence can be told apart, e.g., for unique MACs 👑

SNE does not extend the actual sequence space of a protocol, so it doesn't extend its tolerance to reordering or gaps either 🙅 It also can't improve the dynamic range for flow control or congestion control. There are other somewhat related methods that can, though, like window scaling [RFC7323] (which increases range at the expense of granularity) 🦋

SNE isn't needed if messages are already unique across the whole transfer sequence, e.g., because the sequence number field never wraps around, or because other fields provide that disambiguation, like timestamps 🍓

5. Example Code 🧑‍💻

The C code below is a verified example of SNE going from 16 to 32 bits 🔥 It includes both the framework used for validation and the compute_sne() function. The function is the part you can actually use operationally.

A correct test will print "OK" for each test. An incorrect test will print "ERROR" where that applies 💀

<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 🧪

These numbers are used to validate SNE variants, and they're listed in the order they could legitimately be received 💜 Each line is one 64-bit number, written as two 32-bit hexadecimal numbers with a space in between. They're formatted for use with the example code in Section 5.

A correctly working extended sequence number system should be able to receive the least-significant half (the right side) and compute the correct most-significant half (the left side) 🎯 This suite specifically checks 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 🔐

Okay, this section is serious bestie 😭 Sequence numbers and their extensions can be super useful in a bunch of security contexts. BUT the extension part (the most-significant half) is determined by the sequence values you already exchanged (the least-significant half). So the extension should not be considered as adding entropy for message authentication or encryption. Don't count on it for that 🚨

8. IANA Considerations 🌷

This document has no IANA actions. Nothing to register, nothing to update, just vibes ✨

9. Informative References 📚

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

📦 where this page comes from