Replay protection window

Deep dive

How it works

In: seq from the message header and the authentication result · Out: accept or drop · State: top (highest authenticated number) and a ring of M 64-bit words, W = (M−1)·64 · Cost: O(1) per message, at most M words cleared on an advance

1. Sender: one counter per key, starting at 1, +1 per message, never reused under that key.
2. Receiver check(seq), no mutation: seq == 0 or top − seq ≥ W → drop; seq > top → pass; otherwise pass only if bit seq mod 64 of word (seq/64) mod M is 0.
3. Authenticate (MAC verify or AEAD open). Failure → drop, state untouched.
4. update(seq): if seq > top, zero the words the window enters (at most M, no bit shifting), set top = seq. Set the bit; if it was already set, report a duplicate.
5. The ring holds M words but promises (M−1)·64 bits: the spare word is where the window moves into (RFC 6479).

If only the low 32 bits travel (ESP with ESN), the receiver infers the high half from top (esn_seq, RFC 4303 App. A2.2); the high half enters the MAC input untransmitted.

Code

/// RFC 6479-style window: M words of 64 bits in a ring, supported window (M-1)*64.
/// Sequence numbers start at 1; 0 is never accepted. M must be a power of two.
pub struct ReplayWindow<const M: usize> {
    top: u64,        // highest authenticated sequence number so far (0 = none)
    bits: [u64; M],  // ring of words; slot = (seq / 64) % M
}

impl<const M: usize> ReplayWindow<M> {
    pub const WINDOW: u64 = (M as u64 - 1) * 64;
    pub fn new() -> Self { assert!(M.is_power_of_two() && M >= 2); Self { top: 0, bits: [0; M] } }

    /// Cheap pre-check, BEFORE the MAC/AEAD. Never mutates.
    pub fn check(&self, seq: u64) -> bool {
        if seq == 0 { return false; }
        if seq > self.top { return true; }
        if self.top - seq >= Self::WINDOW { return false; } // too old: dropped unseen
        self.bits[(seq >> 6) as usize & (M - 1)] >> (seq & 63) & 1 == 0
    }

    /// Call ONLY after the packet authenticated. Returns false if it lost a race
    /// with a duplicate (or was too old), so callers can treat it as a drop.
    pub fn update(&mut self, seq: u64) -> bool {
        if seq == 0 { return false; }
        if seq > self.top {
            let (wt, ws) = (self.top >> 6, seq >> 6);
            // zero the words the window enters; a jump of >= M words clears the ring
            for i in 1..=(ws - wt).min(M as u64) {
                self.bits[((wt + i) as usize) & (M - 1)] = 0;
            }
            self.top = seq;
        } else if self.top - seq >= Self::WINDOW {
            return false;
        }
        let w = &mut self.bits[(seq >> 6) as usize & (M - 1)];
        let seen = *w >> (seq & 63) & 1 == 1;
        *w |= 1 << (seq & 63);
        !seen
    }
}

/// check -> authenticate -> update. `verify` is the MAC / AEAD open.
pub fn receive<const M: usize>(win: &mut ReplayWindow<M>, seq: u64, verify: impl FnOnce() -> bool) -> bool {
    win.check(seq) && verify() && win.update(seq)
}

/// Rebuild the 64-bit number from the 32 bits on the wire (same result as RFC 4303 App. A2.2):
/// the smallest value >= the window base whose low 32 bits are `seql`.
pub fn esn_seq(top: u64, w: u32, seql: u32) -> Option<u64> {
    let base = top.saturating_sub(w as u64 - 1);
    let c = (base & !0xFFFF_FFFF) | seql as u64;
    if c < base { c.checked_add(1 << 32) } else { Some(c) }
}

fn main() {
    let mut w = ReplayWindow::<4>::new();           // window = 192
    assert!(!w.check(0));
    assert!(receive(&mut w, 10, || true));
    assert!(!receive(&mut w, 10, || true));         // duplicate
    assert!(receive(&mut w, 7, || true));           // reordered, in window
    assert!(!receive(&mut w, 11, || false) && w.check(11)); // forged: not recorded
    assert!(receive(&mut w, 300, || true));         // jump: top-10 = 290 >= 192
    assert!(!w.check(10) && !w.check(7));           // too old now
    assert!(receive(&mut w, 300 + 1000, || true));  // jump > M words clears ring
    assert!(w.check(1200) && !w.check(1300));
    assert_eq!(esn_seq(0x1_0000_0005, 64, 0xFFFF_FFF0), Some(0xFFFF_FFF0)); // straddles wrap
    assert_eq!(esn_seq(0x1_FFFF_FFF0, 64, 0x0000_0002), Some(0x2_0000_0002));
}

Ran: the asserts above, and 2 million random sequence numbers per window size (M = 4 and 16; jumps, repeats, zero, stale) against a HashSet oracle with identical decisions.

Complexity and constants

• Time O(1); clearing is amortized O(1) (each word is cleared once per 64 numbers). State W/8 bytes: 1 KiB for WireGuard's 8192-bit ring.
• Measured on an Apple M4 Pro, rustc -O, M = 128, 50 million numbers: 0.63-0.76 ns/message in order, 1.8-2.1 ns for random order inside blocks of 32 (mispredicts on advance), 0.48 ns for a duplicate rejected by check (two runs).
• Cost drivers: the window's cache line, a lock when cores share it, a flash write if the counter is persisted.

Efficiency

• Cost: about 1-2 ns and one cache line per message (measured), small against the MAC.
• Levers:
  • word ring instead of shifting — an advance clears whole words, not W bits per packet (RFC 6479) — W above 64-128, multi-core
  • check before the MAC — a duplicate costs 0.5 ns, not an AEAD (measured) — flooded receivers; DTLS 1.3 checks after deprotection to avoid a timing signal (RFC 9147 §4.5.1)
  • reserve-ahead persistence — write the sender counter every N messages — flash/EEPROM devices
• Naive → standard → state of the art:
  • set of every number ever seen · memory grows with traffic
  • shift a W-bit window per advance (RFC 4303) · O(W/64) word moves
  • ring of words cleared on entry (RFC 6479) · O(1), one word per packet

Implementation notes

• Order is the invariant: WireGuard decrypts first, then one locked test-and-set; DTLS 1.3 forbids updating before deprotection. A forged packet must never move top: it would make the receiver drop real traffic.
• Several cores: check and update race, so update reports "already set" atomically and the caller drops on false.
• Counter width: 64 bits never wrap in practice (2^64 messages at 10^9/s is about 584 years); WireGuard rekeys at 2^60. With 32 bits the sender must rekey before the cycle (RFC 4303 §3.3.3).
• Restarts, sender: persist a high-water mark (counter + N) before using N numbers and resume from it, or use a fresh key per boot. Receiver: a RAM-only window is empty after reboot, so old packets under the old key are accepted again; rekey on reboot, or persist top and resume at top + W + N. DTLS keeps one window per epoch, since each epoch resets the numbers (RFC 9147 §4.5.1).

Time-based variant for request APIs

With no per-key counter (many clients signing requests or webhooks), sign a timestamp with the body. The verifier accepts if |now − ts| ≤ τ and keeps each nonce or event id in a set for 2τ, rejecting repeats. Stripe's libraries check the signed timestamp against a default tolerance of 5 minutes; that bounds replay but leaves it possible inside τ, and a nonce cache closes the gap. Memory = rate × 2τ × id size: 1 kHz, τ = 300 s, 16-byte ids is 600,000 ids, order of 10 MB.

Pitfalls

• Updating before authentication: one forged high number is a denial of service.
• W too small for parallel decryption (RFC 6479 §1: above 64-128 on multi-core) or multipath: good packets fall off the left edge.
• Counter reuse after a crash under a persisted key: with an AEAD it also repeats a nonce and breaks confidentiality.
• Wrong ESN high bits after a long outage: all packets fail the MAC until resynchronized (RFC 4303 App. A3).

Variants and alternatives

In production

• VPNs: IPsec ESP/AH (Linux xfrm_replay.c; strongSwan configures it), WireGuard (Linux counter_validate: 8192-bit ring, comment "This is RFC6479"), BoringTun (Rust, 16 words = 1024 packets).
• Real-time media: SRTP/SRTCP (libsrtp srtp_rdbx_*), DTLS in WebRTC.
• Payments and IoT: chip cards send an incrementing transaction counter the issuer checks; LoRaWAN-style networks reject uplinks whose frame counter did not increase (strict-counter variants; per the EMV and LoRaWAN specifications, not re-checked here).
• Game UDP protocols carry a sequence number plus a 32-bit bitmap of recent receipts, the same structure (Fiedler); webhook receivers use timestamp tolerance plus event-id dedupe.

Implementations

Sources

• Kent, IP Encapsulating Security Payload (ESP), RFC 4303, 2005 (§3.4.3, App. A). RFC
• Zhang, Tsou, IPsec Anti-Replay Algorithm without Bit Shifting, RFC 6479, 2012. RFC
• Baugher et al., The Secure Real-time Transport Protocol (SRTP), RFC 3711, 2004 (§3.3.2). RFC
• Rescorla, Tschofenig, Modadugu, The Datagram Transport Layer Security (DTLS) Protocol Version 1.3, RFC 9147, 2022 (§4.5.1). RFC
• Donenfeld, WireGuard: Next Generation Kernel Network Tunnel, NDSS 2017. paper · code
• Glenn Fiedler, Reliability, Ordering and Congestion Avoidance over UDP, Gaffer On Games. article
• Stripe documentation, Webhooks: preventing replay attacks. docs