Replay Protection

1. Overview

PALISADE provides replay protection through a combination of:

1. Epoch/Sequence Anti-Replay Window (MANDATORY) - Primary mechanism
2. Timestamp Validation (OPTIONAL) - Defense-in-depth, disabled by default

This appendix focuses on the mandatory epoch/sequence-based mechanism, which does not require clock synchronization.

2. Epoch/Sequence Anti-Replay Window

Window Structure:

• Each direction (client-to-server, server-to-client) maintains a separate replay window
• The replay window tracks (epoch_id, seq) pairs
• During epoch overlap, implementations MUST maintain independent replay windows for the current epoch and the immediately preceding epoch
• Window size: 1024 packets (default, configurable 64-4096)
• Early data uses a separate, independent replay window keyed to (epoch_id=0xFFFFFFFF, seq)

Window Operation:

Critical Rule: Receivers MUST NOT promote current_epoch based on observing a higher epoch_id in a packet header. Epoch promotion MUST be gated on authenticated rekey events or successful decryption under an already-armed next-epoch key.

The following promotion logic applies ONLY after the next epoch has been armed via authenticated CTRL_REKEY. Unarmed epochs MUST NOT be promoted.

For each received packet with (epoch_id, seq):
  1. If epoch_id < current_epoch:
     → Reject (packet from old epoch)
  
  2. If epoch_id > current_epoch:
     → If epoch_id == current_epoch + 1 AND next epoch is armed (via authenticated CTRL_REKEY):
       - Attempt decryption with next epoch keys
       - If decryption succeeds:
         * Promote epoch_id to current_epoch (only after successful authentication)
         * Retain previous epoch replay window until overlap expires
         * Initialize new replay window for the new epoch_id
         * Accept packet
       - If decryption fails:
         * Reject packet (unauthenticated epoch jump)
     Else:
       - Reject packet (unexpected epoch jump or unarmed epoch)
  
  3. If epoch_id == current_epoch:
     a. If seq > last_seen_seq:
        → Slide window forward
        → Mark seq as seen
        → Accept packet
     b. If seq <= last_seen_seq:
        → Check if seq is within window
        → If already seen: REJECT (replay detected)
        → If not seen: Mark as seen, ACCEPT

Deterministic Decryption (v1.2): PALISADE v1.2 uses deterministic decryption based on the key_phase flag. The receiver attempts decryption with a small range of sequence numbers (0 to replay window size) to handle minor reordering, but this is bounded and deterministic.

Decryption Attempt Limit: Receivers MUST NOT attempt more than 2 decryptions per packet (one per key phase context, and only if session is in TRANSITION state for the fallback attempt).

• In STEADY state: exactly 1 decrypt attempt (current epoch, indicated key_phase)
• In TRANSITION state: at most 2 decrypt attempts (indicated key_phase first, then alternate if first fails)
• Sequence search range: Up to replay window size (default 1024) to handle minor reordering within the window

Rationale: This limit eliminates nonce-search DoS amplification. Previous implementations attempted up to 200 decryptions per packet. The bounded sequence search handles legitimate reordering while preventing DoS attacks.

Replay Window Advancement: Replay window advancement for a given epoch MUST occur only upon successful authentication of a packet under that epoch's keys. Replay windows MUST be maintained independently per epoch.

• Failed decryption attempts MUST NOT advance any replay window
• Successful decryption of epoch N packet advances only epoch N's replay window
• Early data replay window (epoch 0xFFFFFFFF) is independent from application data replay windows

3. Window Size Recommendations

Default: 1024 packets per direction

Rationale:

• Tolerates moderate packet reordering (up to 1024 packets)
• Prevents replay of recent packets
• Memory efficient: ~128 bytes per direction (1024 bits)

Configurable Range:

• Minimum: 64 packets (for constrained devices)
• Maximum: 4096 packets (for high-reordering networks)
• Recommended: 1024 packets (balance of security and performance)

4. Epoch Transitions

Critical Rule: When epoch increments, the replay window MUST be reset. However, epoch transitions MUST occur only via explicit, ordered protocol steps under non-early traffic keys. A receiver MUST NOT advance epoch state based solely on observing epoch_id in a packet header.

Epoch promotion MUST be gated on authenticated rekey events (CTRL_REKEY) or successful decryption under an already-armed next-epoch key.

On epoch transition (epoch_new > epoch_current):
  PREREQUISITE: Next epoch must be armed via authenticated CTRL_REKEY
  
  1. Attempt decryption with next epoch keys
  2. If decryption succeeds (authenticated):
     - current_epoch = epoch_new
     - last_seen_seq = 0
     - window_bitmap = zeros(1024 bits)
     - Accept packet (first packet of new epoch)
  3. If decryption fails:
     - Reject packet (unauthenticated epoch jump)

Security Property: Epoch transitions provide natural replay protection boundaries. Packets from previous epochs cannot be replayed in new epochs. However, transitions must be authenticated to prevent desync attacks.

5. Epoch Overlap Configuration

Extension Type: 0x0005 (epoch_overlap_config)

Purpose: Negotiates epoch overlap window parameters for rekeying transitions.

Extension Data:

EpochOverlapConfig =
    overlap_duration_ms (2 bytes, uint16)
    max_out_of_order_packets (2 bytes, uint16)

Fields:

• overlap_duration_ms: Duration in milliseconds that both old and new epoch keys remain valid
  • Range: 1000-60000 ms (1 second to 1 minute)
  • Default: 5000 ms (5 seconds)
  • Recommendation: Higher values for high-latency networks
• max_out_of_order_packets: Maximum number of packets that can arrive out-of-order during transition. The max_out_of_order_packets value MUST NOT exceed the replay window size. If it does, implementations MUST cap it to the effective replay window size.
  • Range: 10-1000 packets
  • Default: 100 packets
  • Recommendation: Higher values for networks with significant reordering

Negotiation Protocol:

1. Client → Server (ClientHello):
   • Client includes epoch_overlap_config extension with proposed values
   • If extension absent, server assumes defaults
2. Server → Client (ServerHello):
   • Server MUST include epoch_overlap_config in response
   • Server MAY reduce client's proposed values based on policy
   • Server MUST NOT increase client's proposed values
   • Final values = min(client_proposal, server_policy)
3. Both endpoints:
   • MUST use server's final values for entire session lifetime
   • MUST NOT change overlap parameters mid-session

Example:

Client proposes: overlap_duration_ms=10000, max_out_of_order=200
Server policy: overlap_duration_ms<=8000, max_out_of_order<=150
Final values: overlap_duration_ms=8000, max_out_of_order=150

Security Considerations:

• Longer overlap windows slightly increase window for replay attacks
• Implementations SHOULD enforce maximum overlap_duration_ms of 60000ms
• Overlap window MUST NOT affect forward secrecy (old keys erased after expiry)

6. Sequence Number Validation

Requirements:

• For each sending endpoint and traffic direction, sequence numbers MUST be strictly increasing and MUST NOT repeat within an epoch
• Sequence numbers MUST reset to 0 on epoch increment
• Regular epochs: Sequence 0 is valid (first packet in epoch)
• Early data: Sequence 0 is invalid; early data MUST use seq ≥ 1 (Section 12.8)

Validation Logic:

if epoch == current_epoch:
    // Sequence 0 is valid for regular epochs (sequences start at 0)
    // Early data (epoch_id=0xFFFFFFFF) MUST use seq >= 1, enforced separately
    
    if seq <= last_seen_seq:
        → Check if within window
        → If outside window: Reject (too old)
        → If within window and not seen: Accept
        → If within window and seen: Reject (replay)
    if seq > last_seen_seq:
        → Accept (new packet)
        → Slide window forward

Note: The implementation allows sequence 0 for regular epochs. Early data packets (epoch_id=0xFFFFFFFF) are validated separately by EarlyDataReplayWindow, which enforces seq ≥ 1.

7. Implementation Example (Pseudocode)

class EpochReplayWindow:
    def __init__(self, window_size=1024):
        self.window_size = window_size
        self.current_epoch = 0
        self.last_seen_seq = 0
        self.bitmap = [0] * (window_size // 64)  # 64-bit words
    
    def check(self, epoch, seq):
        # Epoch transition: reset window
        # CRITICAL: Only promote if next epoch is armed and decryption succeeds
        # Reject large forward jumps to prevent state exhaustion
        if epoch > self.current_epoch:
            # Next epoch must be armed via authenticated CTRL_REKEY
            if epoch == self.current_epoch + 1 and self.next_epoch_armed:
                # Attempt decryption with next epoch keys
                if self.decrypt_with_next_epoch():
                    self.current_epoch = epoch
                    self.last_seen_seq = 0
                    self.bitmap = [0] * (self.window_size // 64)
                    return True  # Accept first packet of new epoch
                else:
                    return False  # Decryption failed, reject
            else:
                return False  # Unarmed epoch or unexpected jump

        
        # Old epoch: reject
        if epoch < self.current_epoch:
            return False  # Reject
        
        # Same epoch: check sequence
        # Note: Sequence 0 is valid for regular epochs (sequences start at 0)
        # Early data (epoch_id=0xFFFFFFFF) MUST use seq >= 1, enforced separately
        
        if seq > self.last_seen_seq:
            # New packet: slide window forward
            delta = seq - self.last_seen_seq
            if delta > self.window_size:
                # Gap too large: reject
                return False
            self.slide_window(delta)
            self.last_seen_seq = seq
            self.mark_seen(seq)
            return True
        
        # Packet within window: check if seen
        if seq + self.window_size < self.last_seen_seq:
            return False  # Too old
        
        if self.is_seen(seq):
            return False  # Replay detected
        
        self.mark_seen(seq)
        return True

8. Security Properties

Replay Protection Guarantees:

1. Within-Epoch Replay: Detected by bitmap check (packets already seen are rejected)
2. Cross-Epoch Replay: Prevented by epoch comparison (old epoch packets rejected)
3. Long-Term Replay: Prevented by window size (packets outside window are rejected)

Limitations:

• Window size limits how far back replay detection works
• Packets whose sequence numbers fall outside the replay window are rejected. Sequence number wrap is forbidden by Section 9 and MUST result in rekeying or session termination before wrap occurs.
• Mitigation: Use timestamps (optional) for long-term replay protection

Combined with deterministic nonce construction and epoch-scoped keys, this replay mechanism ensures that any accepted packet corresponds to a unique AEAD nonce and unique key epoch.

9. Early Data Replay Protection (Section 12.10)

Early data packets use a separate, independent replay window as required by Section 12.10. This window is keyed to (epoch_id=0xFFFFFFFF, seq) and MUST be discarded upon completion of resumption.

Key Requirements:

• Early data replay window MUST be independent from application-data replay windows
• Early data packets MUST use seq ≥ 1 (sequence 0 is invalid for early data)
• Early data replay window MUST be discarded upon resumption completion
• Early data is replayable and MUST be treated as advisory only

Implementation: EarlyDataReplayWindow is a separate structure from EpochReplayWindow. Early data packets are validated against the early data replay window, while application data packets are validated against the epoch replay window.

10. Timestamps (OPTIONAL)

This section is informative. Timestamp fields are negotiated and enabled exclusively via the Timestamp extension defined in Section 16.

timestamp: A 32-bit unsigned integer representing time in Unix epoch format (seconds since 1970-01-01 00:00:00 UTC) or seconds since session start. Timestamps are OPTIONAL and disabled by default (see Section 7.6).

Status: OPTIONAL feature, disabled by default. When disabled, implementations MUST set timestamp = 0.

Usage contexts (when enabled):

• Packet timestamps: Wall-clock time or session-relative time used for replay protection (Section 7.6)
• Ticket expiration: Wall-clock time used for ticket validity windows (Section 11)
• Migration timestamps: Wall-clock time used for migration replay protection (Section 12)

Implementation requirements (when enabled):

• Implementations MAY use synchronized clocks (NTP or equivalent)
• Implementations MAY accept timestamps within ±5 minutes of local time
• Implementations MAY reject connections with timestamp skew > 15 minutes
• Implementations MUST NOT use timestamps as sole source of entropy
• Implementations MUST NOT rely solely on timestamps for replay protection (use epoch/sequence window)

Security note: Timestamp-based replay protection assumes reasonably synchronized clocks. For networks with poor time synchronization, implementations may increase tolerance windows but MUST NOT exceed ±1 hour. The primary replay protection mechanism is the epoch/sequence anti-replay window (Section 8, Appendix D).

epoch_id: A session-relative counter incremented on each rekeying operation. This is NOT a wall-clock timestamp. See Section 10 (Rekeying) for details.

11. Comparison of Default with Timestamp-Based Protection

Recommendation: Use epoch/sequence window as primary mechanism. Enable timestamps only if long-term replay protection is required and clock synchronization is available.

12. Configuration Guidelines

For Standard Deployments:

• Window size: 1024 packets
• Timestamps: Disabled (default)

For High-Reordering Networks:

• Window size: 2048-4096 packets
• Timestamps: Optional (if clock sync available)

For Constrained Devices:

• Window size: 64-256 packets
• Timestamps: Disabled (reduce complexity)

For High-Security Deployments:

• Window size: 1024 packets
• Timestamps: Enabled (defense-in-depth)