Subject: [tcpm] RFC 5925 SNE algorithm concern

From: [email-masked]
Date: Thu, 30 Apr 2020 10:31:32 +0300

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

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

---

From: Joseph Touch <[email-masked]>
Date: Thu, 30 Apr 2020 07:31:18 -0700

Hi, Juhamatti,

See embedded below:

> On Apr 30, 2020, at 12:31 AM, [email-masked] wrote:
> 
> Hello all,
> 
> 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

You’re using the pseudocode that creates new SNEs with a previously transmitted value. It’s acting like you’ve wrapped too quickly. 

> 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
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: [email-masked]
Date: Thu, 30 Apr 2020 19:43:45 +0300

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:

> 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