Subject: Re: [tcpm] RFC 5925 SNE algorithm concern

From: [email-masked]
Date: Tue, 5 May 2020 10:25:12 +0300

Hello,

And there seems to be a minor parenthesis mismatch in the pseudo-code
of the improved algorithm I sent earlier. Here is a new fixed version
below for the record.

Improved algorithm suggestion pseudo-code:
     PRE = 0;
     // set the flag when the SEG.SEQ first rolls over
     if ((RCV.SNE_FLAG == 0)
        && (RCV.PREV_SEQ > 0x7fffffff) && (SEG.SEQ < 0x7fffffff)) {
          RCV.SNE = RCV.SNE + 1;
          RCV.SNE_FLAG = 1;
     }
     // decide which SNE to use after incremented,
     // pre-increment is used for retransmits
     if ((RCV.SNE_FLAG == 1) && (SEG.SEQ > 0x7fffffff)) {
        SNE = RCV.SNE - 1; // use the pre-increment value
        PRE = 1;
     } else {
        SNE = RCV.SNE; // use the current value
     }
     // reset the flag in the *middle* of the window,
     // include SEG.SEQ equals half so that we do not miss
     // that edge case
     if (PRE == 0) {
        if(RCV.PREV_SEQ < 0x7fffffff && SEG.SEQ >= 0x7fffffff) {
           RCV.SNE_FLAG = 0;
        }
        // save the current SEQ for the next time through the code,
        // if we are not retransmitting
        RCV.PREV_SEQ = SEG.SEQ;
     }

BR,
--
 Juhamatti

On Thu, 30 Apr 2020 at 19:43, <[email-masked]> wrote:
>
>
> Hello Joe,
>
> Thanks for your reply. While I talk about retransmit, I refer actually to the other side retransmitting. So this is the receive side pseudo code. Does that change the situation?
>
> Thanks for the clarifications,
> --
>  Juhamatti
>
> to 30. huhtikuuta 2020 klo 17.31 Joseph Touch <[email-masked]> kirjoitti:
>>
>> Hi, Juhamatti,
>>
>> See embedded below:
>>
>> > On Apr 30, 2020, at 12:31 AM, [email-masked] wrote:
>> >
>> > Hello all,
>> >
>> > While working with RFC 5925, I have been checking the details of
>> > example SNE algorithm. I have a slight concern with the example
>> > algorithm proposed by the RFC.
>> >
>> > The idea of SNE is to simulate 64-bit sequence number with 32-bit
>> > sequences to prevent replay attacks. RFC 5925 proposes the following
>> > algorithm to implement 64-bit sequence numbering:
>> >
>> > Original algorithm pseudo-code in the RFC 5925 + errata:
>> >     /* set the flag when the SEG.SEQ first rolls over */
>> >     if ((RCV.SNE_FLAG == 0)
>> >        && (RCV.PREV_SEQ > 0x7fffffff) && (SEG.SEQ < 0x7fffffff)) {
>> >           RCV.SNE = RCV.SNE + 1;
>> >           RCV.SNE_FLAG = 1;
>> >     }
>> >     /* decide which SNE to use after incremented */
>> >     if ((RCV.SNE_FLAG == 1) && (SEG.SEQ > 0x7fffffff)) {
>> >        SNE = RCV.SNE - 1; # use the pre-increment value
>> >     } else {
>> >        SNE = RCV.SNE; # use the current value
>> >     }
>> >     /* reset the flag in the *middle* of the window */
>> >     if ((RCV.PREV_SEQ < 0x7fffffff) && (SEG.SEQ > 0x7fffffff)) {
>> >        RCV.SNE_FLAG = 0;
>> >     }
>> >     /* save the current SEQ for the next time through the code */
>> >     RCV.PREV_SEQ = SEG.SEQ;
>> >
>> > When looking into this in detail, to me it looks like there might be
>> > an issue when 32-bit sequence wraps back to the beginning and a
>> > retransmission occurs with the high sequence range.
>>
>> Retransmission should always use the value cached with that segment, so there should not be an issue.
>>
>> > Then SNE is
>> > increased unexpectedly and does not follow proper sequencing. A test
>> > case below:
>> >
>> > State:
>> > PREV_SEQ = 0xffffffe
>> > RCV.SNE = 0
>> > RCV.SNE_FLAG = 0
>> >
>> > New frame:
>> > SEG.SEQ = 0x0
>> > RCV.SNE => 1
>> > RCV.SNE_FLAG => 1
>> > PREV_SEQ => 0
>> >
>> > Retransmit:
>> > SEG.SEQ = 0xfffffffd
>> > RCV.SNE_FLAG => 0 - incorrectly updated
>> > PREV_SEQ => 0xfffffffd - incorrectly updated
>>
>> You’re using the pseudocode that creates new SNEs with a previously transmitted value. It’s acting like you’ve wrapped too quickly.
>>
>> >
>> > New frame:
>> > SEG.SEQ = 0x2
>> > RCV.SNE => 2 - incorrect value, should be 1 based on sequencing
>> > RCV.SNE_FLAG => 1
>> > PREV_SEQ => 0x2
>> >
>> > I could not figure out any reason why the above sequence would not be
>> > valid.
>>
>> Because retransmission should be using the values cached when the original transmission occurred.
>>
>> I don’t think the new code is needed - at least from this example.
>>
>> Joe
>>
>> > Even though it is mentioned in the RFC that the algorithm is
>> > just an example, the sequencing mismatch is unfortunate as mismatching
>> > SNEs on different sides will bring the authenticated TCP session down
>> > and cause data loss through timeout. Thus, for interoperability, it is
>> > crucial that correct sequencing is used on both ends.
>> >
>> > If above is really a real problem, then perhaps an improved algorithm
>> > could be as follows:
>> >
>> > Improved algorithm suggestion pseudo-code:
>> >     PRE = 0;
>> >     // set the flag when the SEG.SEQ first rolls over
>> >     if ((RCV.SNE_FLAG == 0)
>> >        && (RCV.PREV_SEQ > 0x7fffffff) && (SEG.SEQ < 0x7fffffff)) {
>> >          RCV.SNE = RCV.SNE + 1;
>> >          RCV.SNE_FLAG = 1;
>> >     }
>> >     // decide which SNE to use after incremented,
>> >     // pre-increment is used for retransmits
>> >     if ((RCV.SNE_FLAG == 1) && (SEG.SEQ > 0x7fffffff)) {
>> >        SNE = RCV.SNE - 1; # use the pre-increment value
>> >        PRE = 1;
>> >     } else {
>> >        SNE = RCV.SNE; # use the current value
>> >     }
>> >     // reset the flag in the *middle* of the window,
>> >     // include SEG.SEQ equals half so that we do not miss
>> >     // that edge case
>> >     if (PRE == 0) {
>> >        if(RCV.SNE_FLAG == 1 &&
>> >           RCV.PREV_SEQ < 0x7fffffff) && (SEG.SEQ >= 0x7fffffff)) {
>> >           RCV.SNE_FLAG = 0;
>> >        }
>> >        // save the current SEQ for the next time through the code,
>> >        // if we are not retransmitting
>> >        RCV.PREV_SEQ = SEG.SEQ;
>> >     }
>> >
>> > This passes the problematic case (and bunch of others I have tested).
>> > This also includes a small additional fix in the middle window
>> > handling where SEG.SEQ was missing one edge value (SEG.SEQ >
>> > 0x7fffffff => SEG.SEQ >= 0x7fffffff). I hope I have not missed
>> > anything else, but it is certainly possible, so comments are welcome.
>> >
>> > So, what do you think, is this a real concern? If it is a real issue,
>> > what would be the best way to handle this, perhaps an errata with an
>> > improved algorithm after throughout review of the new algorithm?
>> >
>> > Thank you,
>> > --
>> > Juhamatti
>> >
>> > _______________________________________________
>> > tcpm mailing list
>> > [email-masked]
>> > https://www.ietf.org/mailman/listinfo/tcpm
>>

---

From: Joseph Touch <[email-masked]>
Date: Wed, 6 May 2020 12:07:25 -0700

Hi, all,

Juhamatti pointed out a flaw in the pseudocode for receive-side SNE computation in RFC 5925.

The good news (in a sense) is that the code was not normative; 

   The implementation of SNEs is not specified in this document, but one
   possible way is described here that can be used for either RCV.SNE,
   SND.SNE, or both.

The corrections that Juhamatti posted don’t address the key issue, which is that there are several possible interpretations of any received SEQ. There is no simple way to fix this except to handle all the cases (which the code below does - I believe minimally):

	- it is in-order
		- moving the receive window forward
		- incrementing the SNE if it wraps the number space
	- it is out-of-order
		- which might use either the current SNE or SNE-1, depending on whether it is pre-wrap of the number space

Because the number space wraps, all received SEQ could be interpreted as in-order or out-of-order; the only way to know the difference is the distance between the two — which cannot be larger than 0x7FFF FFFF (half the number space minus 1).

The following is code that covers the cases and passes all current tests. Given this is not as obvious as it might seem and might be more useful than for just RFC 5925 and the SNE alg in 5925 is “not specified” anyway, I propose to submit this as a stand-alone doc.

So here are the ways forward:

	1) have that doc “UPDATE” RFC 5925
		this is the cleanest because it would more definitely be caught by implementers
		but it requires the new alg be standards-track, which seems odd (though we could say what SNE is as a standard
		and still leave its implementation as informative rather than normative)

	2) publish that doc as informational
		then we could issue an errata on 5925 to point to the new RFC

	3) issue the new alg as an errata to 5925 only

Any thoughts?

Joe

——

PS - here’s the alg:

#DEFINE HALF (0x80000000)

SNE = RCV_SNE;                               // use current SNE (as default)
if (distance(SEG_SEQ,RCV_PREV_SEQ) < HALF) { // both in same SNE range?
  if ((SEG_SEQ >= HALF) 
      && (RCV_PREV_SEQ < HALF)) {            // jumps fwd over N/2?
    RCV_SNE_FLAG = 0;                        // reset wrap increment flag
  }
  RCV_PREV_SEQ = MAX(SEG_SEQ,RCV_PREV_SEQ);  // move prev forward if needed
} else {                                     // both in diff SNE ranges
  if (SEG_SEQ < HALF) {                      // jumps forward over zero?
    RCV_PREV_SEQ = SEG_SEQ;                  // 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
      SNE = RCV_SNE;                         // use updated SNE value
    }
  } else {                                   // jump backward over zero
    SNE = RCV_SNE - 1;                       // use pre-rollover SNE value
  }
}

---

From: Joseph Touch <[email-masked]>
Date: Wed, 6 May 2020 12:15:04 -0700

PS - 

#define distance(x,y)   (((x)<(y))?((y)-(x)):((x)-(y)))

The idea is that if we treat the two values as if they’re in the same SNE, would they be valid (i.e., jump less than half). If so, they’re in the same SNE. If not, then they must be in different SNEs (and then their distance would be less than half).

Joe

> On May 6, 2020, at 12:07 PM, Joseph Touch <[email-masked]> wrote:
> 
> Hi, all,
>

---

From: Joseph Touch <[email-masked]>
Date: Wed, 6 May 2020 12:36:22 -0700

Here’s a full version, with everything including initialization and definitions. 

// compute the distance from x to y assuming they are in the same SNE
#define DIST(x,y) (((x)<(y))?((y)-(x)):((x)-(y)))
#define HALF      (0x80000000)              // shorthand used in the code below

// variables, with inits where required
unsigned long RCV_SNE = 0;                  // high-watermark SNE, init per RFC5925
int           RCV_SNE_FLAG = 1;             // set during first half of rollover
unsigned long RCV_PREV_SEQ;                 // high-watermark SEQ, init by ISN
unsigned long SEG_SEQ;                      // input - received SEQ
unsigned long SNE;                          // output - SNE corresponding to received SEQ

if (SYN == 1) {                             // SYN or SYN-ACK initialization
  RCV_PREV_SEQ = RECV_ISN;
}                                           // after SYN or SYN-ACK
if (DIST(SEG_SEQ,RCV_PREV_SEQ) < HALF) {    // both in same SNE range?

---

From: [email-masked]
Date: Thu, 7 May 2020 09:00:34 +0300

Hello,

+1 for below algorithm.

The earlier improved algorithm I suggested did not handle middle-range
retransmissions correctly, this one does. It also passes other tests I
have (which found the original issues).

Thank you,
--
 Juhamatti