9. Nonce Construction

This section specifies the construction of nonces for AEAD encryption and decryption in PALISADE.

9.1 Nonce Construction

PALISADE uses a 96-bit nonce for AEAD encryption and decryption.

For each packet, the nonce is constructed as:

nonce = iv ⊕ (epoch_id || seq)

Where:

• iv is a 96-bit initialization vector derived from the key schedule (c2s_iv or s2c_iv, depending on direction).
• epoch_id is a 32-bit unsigned integer identifying the current epoch.
• seq is a 64-bit unsigned integer sequence number.
• (epoch_id || seq) denotes the concatenation of epoch_id and seq, encoded in big-endian byte order.
• ⊕ denotes bitwise XOR over 96 bits.

This construction is mandatory and MUST be implemented exactly as specified.

Nonce construction and uniqueness requirements apply independently to each traffic direction (client-to-server and server-to-client), as each direction uses independent keys and IVs.

9.2 Reference Algorithm and Examples (Non-Normative)

This section provides a reference algorithm and illustrative examples for implementers. It is non-normative; the normative definition of nonce construction is given in Section 9.1.

PALISADE uses a 96-bit (12-byte) nonce for ChaCha20-Poly1305, constructed as:

nonce = iv ⊕ (epoch_id || seq)

def construct_nonce(iv: bytes, epoch: int, sequence: int) -> bytes:
    """
    Construct ChaCha20-Poly1305 nonce from IV, epoch, and sequence.

    Args:
        iv: 12-byte initialization vector from key schedule
        epoch: 32-bit unsigned epoch counter
        sequence: 64-bit unsigned sequence counter

    Returns:
        12-byte nonce for AEAD encryption/decryption
    """
    assert len(iv) == 12, "IV must be exactly 12 bytes"
    assert 0 <= epoch < 2**32, "Epoch must be 32-bit unsigned"
    assert 0 <= sequence < 2**64, "Sequence must be 64-bit unsigned"

    # Encode epoch and sequence as big-endian bytes
    epoch_id = epoch.to_bytes(4, byteorder='big')
    seq = sequence.to_bytes(8, byteorder='big')

    # Concatenate epoch_id || seq (4 + 8 = 12 bytes)
    counter = epoch_id + seq

    # XOR with IV
    nonce = bytes(iv[i] ^ counter[i] for i in range(12))

    return nonce

Input:
  iv:       0x000102030405060708090A0B
  epoch:    0x00000001
  sequence: 0x0000000000000042

Step 1: Encode epoch and sequence
  epoch_bytes:    0x00000001
  sequence_bytes: 0x0000000000000042
  counter:        0x000000010000000000000042

Step 2: XOR with IV
  iv:      0x000102030405060708090A0B
  counter: 0x000000010000000000000042
  nonce:   0x000102020405060708090A49
           ^^^^epoch ^^^^^^^^seq

Result: nonce = 0x000102020405060708090A49

# Correct implementation (shown above)
counter = epoch_bytes + sequence_bytes
nonce = bytes(iv[i] ^ counter[i] for i in range(12))

9.3 Key Phase Selection

The key_phase flag in the PublicHeader indicates the sender's selected key phase for decrypting this packet. Receivers MUST treat key_phase as a hint for key selection and MUST NOT treat it as authentication. The key_phase flag is defined for version >= 0x12.

Semantics:

• key_phase=0: Decrypt using current epoch keyset
• key_phase=1: Decrypt using next epoch keyset (valid only during TRANSITION state)

Receiver Behavior:

• Receivers MUST first attempt decryption using the key phase indicated by the flag.
• Receivers MAY attempt decryption using the alternate key phase only if the session is in TRANSITION state and both key contexts exist.
• Receivers MUST NOT attempt more than 2 decryptions per packet.

Behavioral Constraints: key_phase MUST NOT trigger special behavior:

• key_phase=1 packets MUST NOT trigger epoch switches
• key_phase=1 MUST NOT open larger replay windows
• key_phase=1 MUST NOT bypass owner-backend policy
• key_phase=1 MUST NOT affect rate limiting decisions

Principle: key_phase selects a key to try, nothing more.

Security Rationale: An attacker can flip key_phase bits, but the only result is one failed decrypt and a drop—not amplification, not state changes, not resource exhaustion.

9.4 Sender Nonce State

For each direction, the sender maintains nonce state (epoch_id, seq) bound to the active epoch secret. The sender MUST allocate (epoch_id, seq) pairs in a linearizable manner such that no pair is ever reused with the same epoch secret.

Fail-Closed Recovery: If the sender cannot prove continuity of nonce state across restart (e.g., lost persistent state, unclean shutdown), it MUST NOT transmit protected packets using previously derived epoch secrets. The sender MUST perform a new handshake or rekey to obtain fresh epoch secrets before sending any protected traffic.

Acceptable Recovery Strategies:

• Strategy A (Fail-Closed): Memory-only state, force handshake on restart
• Strategy B (Lease Blocks): Allocate sequence blocks to stable storage, burn unused on crash
• Strategy C (Journal): Append-only persistence with periodic sync

If Strategy B or C is used, implementations MUST verify persistence before using epoch secrets. If persistence verification fails, the implementation MUST fall back to fail-closed behavior (force new handshake).

9.5 Nonce Uniqueness and Rekeying Rules

CRITICAL SECURITY REQUIREMENT: The tuple (epoch_id, seq) MUST NEVER repeat for a given direction's key.

MANDATORY Requirements:

1. Sequence Counter Reset on Epoch Increment:
   • Sequence counters MUST reset to 0 upon epoch increment
   • When transitioning from epoch N to epoch N+1, the sequence counter MUST be set to 0
   • This ensures that (epoch N+1, seq=0) is distinct from any (epoch N, seq) pair
2. Epoch Counter Increment Rules:
   • Epoch counters MUST NEVER increment without resetting sequence to 0
   • Epoch increment and sequence reset MUST be an atomic operation. Implementations MUST ensure that no packet is ever transmitted with a mixed (epoch_id, seq) state.
   • Implementations MUST NOT increment epoch while leaving sequence at a non-zero value
3. Sequence Number Uniqueness:
   • Sequence numbers MUST NOT repeat within an epoch
   • Sequence counters MUST be strictly monotonic (increment by exactly 1 for each packet)
   • seq MUST be strictly increasing for transmitted packets within an epoch (per direction)
   • Implementations MAY permit gaps (skipped values) due to packet drops or scheduling, provided uniqueness is preserved.
4. Sequence Monotonicity:
   • seq MUST increment by exactly 1 for each packet sent
   • Sequence counters MUST NOT wrap within an epoch (rekey before wrap)
5. Sequence Limit:
   • seq < 2^40 per epoch (enforce hard cap at 1,099,511,627,776 packets)
   • Rekey MUST occur before sequence counter reaches this limit
   • Although seq is encoded as a 64-bit value, Implementations MUST enforce a maximum of 2^40 packets per epoch as a conservative AEAD usage limit consistent with standard analyses for high-volume AEAD deployments (ChaCha20-Poly1305 and AES-GCM), independent of post-quantum considerations.
   • The maximum sequence number limit of 2⁴⁰ applies independently to each epoch. Sequence counters MAY reset to zero when transitioning to a new epoch, provided that a fresh epoch secret and traffic keys are in use.
   • Epoch overlap does not increase the allowable number of packets encrypted under a single epoch’s traffic keys. Implementations MUST enforce the per-epoch sequence limit independently for each epoch, regardless of overlap duration.
6. Rekey Trigger:
   • Force rekey when seq >= 2^40 - 2^30 (leaving safety margin)
   • This ensures sequence counter never approaches wrap
7. Epoch Increment:
   • On rekey, increment epoch_id by 1 and reset seq = 0 (atomic operation)
   • Both operations MUST occur together; partial transitions are forbidden
8. No Epoch Reuse:
   • MUST NOT: Decrement epoch_id or reuse previous epoch values
   • Epoch counters MUST be strictly monotonic (never decrease)
   • Once an epoch is used, it MUST NOT be reused even if keys are re-derived
9. Overflow Behavior: If epoch_id reaches 2^32 - 1, the session MUST be terminated and a new handshake performed. Wraparound is NOT permitted.

9.6 Receiver-Side Detection

While nonce uniqueness is the sender's responsibility, receivers MUST detect violations as defense-in-depth.

Duplicate Detection:

If a receiver successfully decrypts a packet with (epoch, seq) previously accepted within the replay window, it MUST discard the duplicate and SHOULD log the event.

Nonce Reuse Detection (Critical):

If a receiver observes two successfully authenticated packets with the same (epoch_id, seq) pair but different ciphertext or authentication tag, this indicates catastrophic nonce reuse by the sender. The receiver MUST immediately terminate the session, MUST log at CRITICAL level, and MUST NOT automatically reconnect.

Implementation Note: Nonce reuse detection requires caching recent (epoch, seq, tag) tuples. A sliding window of recent authentication tags is sufficient.

Misbehavior Threshold: If duplicate detection (not nonce reuse) exceeds a threshold (RECOMMENDED: 10 duplicates per 60 seconds), the receiver SHOULD terminate the session as this suggests sender state corruption.

9.7 Linearizability Requirements

For the purposes of this specification, epoch state operations are "linearizable" if:

1. Atomicity: Each operation appears to execute instantaneously
2. Isolation: No concurrent observer sees intermediate states
3. Total Order: All observers agree on the order of operations
4. Real-Time Consistency: If operation A completes before B starts, A appears before B in the total order

Required Linearizable Operations:

• allocate_nonce(): Allocates (epoch_id, seq) pair
• install_epoch(): Installs new epoch state (key, iv, epoch_id, seq=0)

Epoch Transition Linearizability Rule: Epoch transition MUST be linearizable with respect to packet encryption: an implementation MUST NOT produce any packet encrypted under epoch E_new with seq > 0 unless it has produced (or concurrently produces) a packet under epoch E_new with seq = 0 using the same epoch secret.

9.8 Epoch State Coupling

Key/Nonce Coupling Invariant: No packet shall be encrypted using a nonce derived from epoch E unless it is also encrypted using the key material (AEAD key and base IV) derived from epoch E's secret.

Structural Enforcement Recommendation: Implementations SHOULD bundle all epoch-dependent state (epoch_id, AEAD key, base IV, sequence counter) into an immutable snapshot that is installed atomically. The encryption function MUST obtain nonce and key material from the same snapshot reference.

Prohibited Pattern: Implementations MUST NOT advance epoch or sequence counters independently of key material installation. There MUST NOT exist any window where packets could be encrypted with a nonce from epoch E but key material from epoch E-1 or E+1.

9.9 Epoch Mutation Ownership

Single-Owner Principle: In multi-threaded implementations, only the session's designated I/O context (e.g., session goroutine, event loop handler) is permitted to perform epoch installation. Other contexts MAY request rekey but MUST NOT directly mutate epoch state.

Rekey Request Pattern: Control-plane components (timers, policy engines) that detect rekey conditions SHOULD signal the session owner via flag or message rather than directly installing new epochs. The session owner serializes all epoch mutations.

Rationale: This architectural constraint eliminates concurrency bugs by design rather than synchronization, making implementations easier to audit and verify.

Multi-Threaded Alternative: If single-owner is not feasible, implementations MUST protect epoch state with synchronization sufficient to guarantee linearizability (e.g., RWLock where encryption holds read lock and installation holds write lock).