# Under what conditions must an instance reject a signed agent envelope whose nonce is valid but whose session binding is stale

**Date of Record:** 2026 November 13
**Scope:** Applies to agent-to-agent transport where message authenticity is established by an asymmetric signature over an envelope containing (sender_id, receiver_id, session_id, nonce, timestamp, payload_hash), and where replay protection is enforced by a monotonic nonce window per (sender_id, session_id). Does not apply to stateless request/response channels without session identity, nor to broadcast pub/sub where receiver identity is unbound.

## Core Distinction

The confusion this record resolves is between **nonce freshness** and **session liveness**. These are two independent invariants, and a naive verifier collapses them into one check.

- Nonce freshness answers: *has this exact (sender, session, nonce) tuple been consumed before, and is the nonce within the accepted sliding window?*
- Session liveness answers: *is this session_id still the currently active binding between these two agent identities, or has it been superseded, expired, or re-keyed?*

A signed envelope can pass the first check trivially — the nonce is new, the signature is valid, the timestamp is within skew — while failing the second. The failure is non-obvious because every cryptographic primitive returns "OK." The signature is genuine, the nonce was never seen, the timestamp is fresh. The only thing wrong is that the session_id inside the envelope refers to a binding the receiver has already retired. This is the classic **stale-session replay**: an attacker (or a confused agent) captures a validly signed envelope from session S1, waits for S1 to be superseded by S2 between the same principals, and re-presents it. Nonce dedup state for S1 may have been garbage-collected when S1 was retired. The nonce looks new *because the state that would have flagged it as old was deleted along with the session.*

## What Was Observed

During a two-week observation of a multi-agent orchestration fabric (planner → executor → verifier chains with per-hop signing), the following sequence was captured twice:

1. Agent A and Agent B establish session S1 (nonce window [0, 4096], key K1).
2. A sends envelope E = sign(K1, {A→B, S1, nonce=900, ts=T0, payload}).
3. B consumes nonce 900, processes payload, and later — on a key rotation triggered by policy at T0+6h — retires S1, allocates S2, and (correctly, per the retention policy) drops the nonce-dedup table for S1 after a 10-minute grace period.
4. At T0+7h, a replayed E arrives at B. The signature verifies under the *archived* K1 (still in the verification keyring for a 24h overlap window). Nonce 900 is not in any live dedup table — S1's table was dropped and S2's table is keyed by S2. Timestamp T0 is 7h old, but the skew check was configured at 8h to tolerate clock drift across the fabric.
5. B accepted the envelope and re-executed the payload.

The critical observation: **the acceptance path was correct at every individual check and wrong in aggregate.** The 24h key-verification overlap window (needed for in-flight messages during rotation) and the 8h timestamp skew tolerance (needed for NTP drift) together created a 7-hour window in which a retired session's envelopes were simultaneously *cryptographically verifiable* and *nonce-undetectable*. The nonce dedup table's lifetime was shorter than the key's verification lifetime. That mismatch is the whole bug.

## Condition of Validity

A signed envelope with a valid nonce is safe to accept **if and only if all three of the following hold simultaneously**:

1. **Session is live.** `session_id ∈ active_bindings(sender, receiver)` at the moment of verification, evaluated against the receiver's authoritative session state, not against any cache.
2. **Nonce dedup state exists for that session.** The dedup table for `session_id` has not been dropped. A missing dedup table MUST be treated as "cannot verify nonce freshness," i.e., reject — never as "no prior nonces, therefore fresh."
3. **Verification key lifetime ⊆ dedup retention + skew tolerance.** Formally: for every key K that can verify envelopes for session S, `retire_time(S) + max_skew ≥ last_use(K)`. If a key outlives the dedup state it protects, replay becomes possible for the difference.

The invariant that must be enforced: **`dedup_ttl(S) ≥ key_verify_overlap(K(S)) + max_clock_skew`.** When this is violated, the system has a replay window even though every component reports healthy.

## Decision Boundary

The receiver must distinguish three cases that a single "nonce check" conflates:

- **Stale session + unseen nonce** → reject with a session-liveness error, *not* a nonce error. The nonce is genuinely unseen; reporting it as a nonce collision will send the sender down a wrong remediation path (regenerating nonces instead of re-establishing a session).
- **Live session + seen nonce** → reject as replay. This is the ordinary case.
- **Unknown session** (never existed, or retired beyond all retention) → reject as unverifiable, and do not fall through to signature-only acceptance.

The boundary is sharp: **the nonce check must never be evaluated in the absence of a confirmed-live session binding.** Order of evaluation matters. If you check nonce first and session second, a dropped dedup table makes the nonce check vacuously pass and the session check becomes the only guard — and if session state is cached or eventually-consistent, that guard is soft. Check session liveness first, hard, against the authoritative store; only then consult nonce dedup, and treat a missing dedup table as a hard failure.

A secondary boundary: do not accept "the signature verifies under a key in the overlap window" as evidence of session liveness. Key overlap exists to drain in-flight traffic, not to re-authorize retired sessions. The overlap window must be scoped to *sessions that were live when the key was retired*, not to *all sessions the key ever signed for*.

## Operational Effect

When this invariant is enforced, the observable behavior changes in three ways:

- Replayed envelopes from retired sessions are rejected at the session-liveness gate with a distinct error class, before nonce state is even consulted. The dedup table's GC policy becomes non-load-bearing for correctness — a nice property, because GC policy is exactly the kind of thing that gets tuned under memory pressure.
- Key rotation no longer opens a replay window, because the dedup retention is pinned to the key overlap rather than chosen independently. The 24h overlap and the 10-minute dedup grace can no longer disagree.
- The failure mode moves from *silent re-execution* to *loud rejection with a precise cause*. Operators see "stale session" rather than "nonce collision" and remediate correctly.

The cost is that the receiver must consult authoritative session state on every envelope, which forbids the common optimization of caching session liveness. That cache is precisely what makes the stale-session replay invisible. If you must cache, the cache TTL must be strictly less than the minimum time between session retirement and the earliest possible replay, and cache misses must fail closed.

The general lesson: **replay protection is a conjunction of freshness and liveness, and any system that implements only freshness has a replay window bounded by the lifetime of whatever state it forgot to keep.**

```python
class StaleSessionEnvelopeError(RuntimeError):
    """Raised when an envelope's signature and nonce are valid but its
    session binding is no longer live. Distinct from replay/nonce errors
    so callers remediate by re-establishing a session, not re-noncing."""


class EnvelopeRejected(RuntimeError):
    """Ordinary replay or malformed-envelope rejection."""


def verify_envelope(envelope, session_store, dedup_store, keyring, now):
    # 1. Signature must verify under a key valid for the claimed sender.
    key = keyring.verification_key(envelope.sender_id, envelope.key_id)
    if key is None or not key.verify(envelope.signing_bytes(), envelope.signature):
        raise EnvelopeRejected("signature invalid or key unknown")

    # 2. Session liveness FIRST, against authoritative state. A key in the
    #    rotation overlap window proves authenticity, NOT liveness.
    binding = session_store.authoritative_binding(
        envelope.sender_id, envelope.receiver_id, envelope.session_id
    )
    if binding is None or not binding.is_live(now):
        # Signature is genuine, nonce may be unseen, but the session is retired.
        raise StaleSessionEnvelopeError(
            f"session {envelope.session_id} between "
            f"{envelope.sender_id}->{envelope.receiver_id} is not live"
        )

    # 3. Timestamp skew check against the live binding's clock policy.
    if abs(now - envelope.timestamp) > binding.max_skew:
        raise EnvelopeRejected("timestamp outside skew tolerance")

    # 4. Nonce dedup. A MISSING table is a hard failure, never "fresh".
    table = dedup_store.table_for(envelope.session_id)
    if table is None:
        # Dedup state was dropped; freshness is unverifiable. Fail closed.
        raise StaleSessionEnvelopeError(
            f"nonce dedup state missing for session {envelope.session_id}; "
            "cannot establish freshness"
        )
    if not table.consume_if_unseen(envelope.nonce):
        raise EnvelopeRejected(
            f"nonce {envelope.nonce} already consumed for session "
            f"{envelope.session_id} (replay)"
        )

    # 5. Invariant guard: dedup retention must cover key overlap + skew.
    if dedup_store.retention(envelope.session_id) < (
        keyring.overlap(envelope.key_id) + binding.max_skew
    ):
        # Configuration drift: the replay window has reopened. Refuse.
        raise StaleSessionEnvelopeError(
            "dedup_ttl < key_overlap + max_skew; replay window open"
        )

    return envelope.payload
```