B2. Anti-Replay Window
The receiver will maintain an anti-replay window of size W. This window will limit how far out of order a packet can be, relative to the packet with the highest sequence number that has been authenticated so far. (No requirement is established for minimum or recommended sizes for this window, beyond the 32- and 64-packet values already established for 32-bit sequence number windows. However, it is suggested that an implementer scale these values consistent with the interface speed supported by an implementation that makes use of the ESN option. Also, the algorithm described below assumes that the window is no greater than 2^31 packets in width.) All 2^32 sequence numbers associated with any fixed value for the high-order 32 bits (Seqh) will hereafter be called a sequence number subspace. The following table lists pertinent variables and their definitions.
| Var. Name | Size (bits) | Meaning |
|---|---|---|
| W | 32 | Size of window |
| T | 64 | Highest sequence number authenticated so far, upper bound of window |
| Tl | 32 | Lower 32 bits of T |
| Th | 32 | Upper 32 bits of T |
| B | 64 | Lower bound of window |
| Bl | 32 | Lower 32 bits of B |
| Bh | 32 | Upper 32 bits of B |
| Seq | 64 | Sequence Number of received packet |
| Seql | 32 | Lower 32 bits of Seq |
| Seqh | 32 | Upper 32 bits of Seq |
When performing the anti-replay check, or when determining which high-order bits to use to authenticate an incoming packet, there are two cases:
- Case A: Tl >= (W - 1). In this case, the window is within one sequence number subspace. (See Figure 1)
- Case B: Tl < (W - 1). In this case, the window spans two sequence number subspaces. (See Figure 2)
In the figures below, the bottom line ("----") shows two consecutive sequence number subspaces, with zeros indicating the beginning of each subspace. The two shorter lines above it show the higher-order bits that apply. The "====" represents the window. The "****" represents future sequence numbers, i.e., those beyond the current highest sequence number authenticated (ThTl).
Th+1 *********
Th =======*****
--0--------+-----+-----0--------+-----------0--
Bl Tl Bl
(Bl+2^32) mod 2^32
Figure 1 -- Case A
Th ====**************
Th-1 ===
--0-----------------+--0--+--------------+--0--
Bl Tl Bl
(Bl+2^32) mod 2^32
Figure 2 -- Case B
B2.1. Managing and Using the Anti-Replay Window
The anti-replay window can be thought of as a string of bits where 'W' defines the length of the string. W = T - B + 1 and cannot exceed 2^32 - 1 in value. The bottom-most bit corresponds to B and the top-most bit corresponds to T, and each sequence number from Bl through Tl is represented by a corresponding bit. The value of the bit indicates whether or not a packet with that sequence number has been received and authenticated, so that replays can be detected and rejected.
When a packet with a 64-bit sequence number (Seq) greater than T is received and validated,
- B is increased by (Seq - T)
- (Seq - T) bits are dropped from the low end of the window
- (Seq - T) bits are added to the high end of the window
- The top bit is set to indicate that a packet with that sequence number has been received and authenticated
- The new bits between T and the top bit are set to indicate that no packets with those sequence numbers have been received yet.
- T is set to the new sequence number
In checking for replayed packets,
-
Under Case A: If Seql >= Bl (where Bl = Tl - W + 1) AND Seql <= Tl, then check the corresponding bit in the window to see if this Seql has already been seen. If yes, reject the packet. If no, perform integrity check (see Appendix B2.2 below for determination of SeqH).
-
Under Case B: If Seql >= Bl (where Bl = Tl - W + 1) OR Seql <= Tl, then check the corresponding bit in the window to see if this Seql has already been seen. If yes, reject the packet. If no, perform integrity check (see Appendix B2.2 below for determination of Seqh).
B2.2. Determining the Higher-Order Bits (Seqh) of the Sequence Number
Because only 'Seql' will be transmitted with the packet, the receiver must deduce and track the sequence number subspace into which each packet falls, i.e., determine the value of Seqh. The following equations define how to select Seqh under "normal" conditions; see Appendix B3 for a discussion of how to recover from extreme packet loss.
Under Case A (Figure 1):
- If Seql >= Bl (where Bl = Tl - W + 1), then Seqh = Th
- If Seql < Bl (where Bl = Tl - W + 1), then Seqh = Th + 1
Under Case B (Figure 2):
- If Seql >= Bl (where Bl = Tl - W + 1), then Seqh = Th - 1
- If Seql < Bl (where Bl = Tl - W + 1), then Seqh = Th
B2.3. Pseudo-Code Example
The following pseudo-code illustrates the above algorithms for anti-replay and integrity checks. The values for 'Seql', 'Tl', 'Th', and 'W' are 32-bit unsigned integers. Arithmetic is mod 2^32.
If (Tl >= W - 1) Case A
If (Seql >= Tl - W + 1)
Seqh = Th
If (Seql <= Tl)
If (pass replay check)
If (pass integrity check)
Set bit corresponding to Seql
Pass the packet on
Else reject packet
Else reject packet
Else
If (pass integrity check)
Tl = Seql (shift bits)
Set bit corresponding to Seql
Pass the packet on
Else reject packet
Else
Seqh = Th + 1
If (pass integrity check)
Tl = Seql (shift bits)
Th = Th + 1
Set bit corresponding to Seql
Pass the packet on
Else reject packet
Else Case B
If (Seql >= Tl - W + 1)
Seqh = Th - 1
If (pass replay check)
If (pass integrity check)
Set the bit corresponding to Seql
Pass packet on
Else reject packet
Else reject packet
Else
Seqh = Th
If (Seql <= Tl)
If (pass replay check)
If (pass integrity check)
Set the bit corresponding to Seql
Pass packet on
Else reject packet
Else reject packet
Else
If (pass integrity check)
Tl = Seql (shift bits)
Set the bit corresponding to Seql
Pass packet on
Else reject packet