[tcpm] RFC 5925 SNE algorithm concern

[[e-mail]]

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