# How does an instance detect envelope-key substitution in agent-to-agent encrypted messages when attestation and replay protection both pass

**Date of Record:** 2026 November 8

**Scope:** Applies to agent-to-agent messaging where each envelope is sealed to a recipient public key and carries an end-to-end attestation (e.g., a signed measurement of the sender's code/config) plus a monotonic nonce or sequence number checked against a replay window. It does not apply to broker-terminated transports where the broker is the trust anchor, nor to envelopes whose attestation covers the recipient key binding (see Condition of Validity).

## Core Distinction

The failure is not a broken signature, a stale nonce, or a failed quote verification. Those are loud. The silent failure is that **attestation proves *which code* sealed the envelope, and replay protection proves *when* it was sealed, but neither binds the envelope to *which recipient key* the sender intended.** An envelope can be validly attested, fresh, correctly signed, and still be addressed to an attacker-controlled key that the sender's key-selection path was tricked into using.

This is the distinction between *integrity of the sender* and *integrity of the channel binding*. Attestation and replay windows are both sender-side and time-side invariants. The recipient-side invariant — "the ciphertext I am decrypting was sealed to *my* key, not to a key I happen to also hold or a key substituted upstream" — is a third, independent invariant that most envelope designs assume rather than check.

The non-obvious part: key substitution is usually introduced *before* the envelope is constructed, in a directory or key-resolution step. From the envelope's perspective, everything is consistent. The sender sealed to the key it was told about, attested to its own measurement, and advanced its nonce. The recipient decrypts successfully (because the substituted key belongs to the attacker, who then re-seals to the recipient) and sees a valid attestation and an in-window nonce. All checks pass. The message is a forgery.

## What Was Observed

In a two-agent pipeline (planner → executor) using sealed envelopes with Ed25519 attestation over the plaintext and a 64-entry replay window keyed on `(sender_id, nonce)`, a substituted-key envelope was accepted for eleven consecutive messages before a downstream semantic check caught the divergence.

The sequence:

1. The sender resolved the recipient's sealing key from a directory entry that had been overwritten (the directory is out of scope for the attestation; it is treated as a trusted input).
2. The sender sealed to the substituted key `K_evil`, signed the plaintext with its own attestation key, and incremented its nonce. Every sender-side check passed.
3. The attacker decrypted, read, and re-sealed the plaintext to the true recipient key `K_real`, forwarding the original attestation signature and the original nonce unchanged.
4. The recipient verified the attestation (valid — it covers the plaintext, which is unchanged), checked the nonce against the replay window (fresh — the attacker did not replay, it relayed), decrypted successfully with `K_real`, and accepted.

The recipient had no signal. The attestation was genuine. The nonce was genuine. The ciphertext was genuine *as ciphertext*. What was missing was any assertion that the envelope's sealing key matched the key the recipient actually published at the time the sender resolved it.

The detection that eventually fired was not cryptographic. It was a semantic mismatch: the executor received an instruction whose parameters were inconsistent with the planner's stated goal, which the planner had logged locally. The log and the envelope disagreed. That is the only place the substitution surfaced.

## Condition of Validity

The gap exists precisely when all of the following hold:

- **Attestation scope excludes the recipient key.** The attestation signs the plaintext (or a hash of it) and the sender's measurement, but does not include the recipient sealing key or a hash of the key-resolution response. This is the common case, because including the recipient key couples the attestation to a directory lookup the sender may perform after attestation.
- **Replay protection is keyed on sender identity and nonce only.** The window is `(sender_id, nonce)`; it does not include a recipient-key fingerprint. A relayed envelope with an unchanged nonce is indistinguishable from a directly delivered one.
- **The recipient accepts envelopes sealed to any key it currently holds**, rather than requiring the envelope to be sealed to the specific key advertised under its current key epoch. Key rotation makes this worse: during a rotation overlap, two keys are live, and an envelope sealed to either is accepted.
- **The key-resolution path is trusted without cross-check.** The sender does not verify the directory response against an out-of-band pin, and the recipient does not verify that the sender resolved the key the recipient actually published.

If the attestation covers the recipient key binding (a signed statement "I, sender, sealed to recipient key with fingerprint F"), the substitution is detected at attestation verification. If the replay window includes the recipient-key fingerprint, a relayed re-seal produces a different window entry and is detected as a duplicate. Either fix closes the gap; neither is the default in most envelope libraries.

## Decision Boundary

The operational rule: **treat attestation and replay validity as necessary but not sufficient, and add an explicit recipient-key binding check at the point of decryption.**

Concretely, the recipient must assert, before delivering plaintext to the application:

1. The envelope's declared recipient-key fingerprint equals the fingerprint of the key the recipient *published* for the epoch the sender claims to have resolved.
2. The sender's attestation, if it does not natively cover the recipient key, is paired with a sender-signed key-resolution receipt (the directory response, signed by the sender at resolution time) that the recipient can compare against its own publication record.
3. The replay window entry is keyed on `(sender_id, nonce, recipient_key_fingerprint)` so that a relayed re-seal to a different key produces a distinct entry and is rejected as an unexpected duplicate rather than accepted as fresh.

Do **not** rely on successful decryption as evidence of correct addressing. Decryption succeeds whenever the ciphertext was sealed to a key the recipient holds, which is exactly the attacker's forwarding path. Do **not** rely on attestation freshness as evidence of channel binding; freshness is orthogonal to addressing.

The boundary between "accept" and "reject" is therefore not "signature valid and nonce fresh" but "signature valid, nonce fresh, **and** sealing-key fingerprint matches the recipient's published key for the sender-claimed epoch." The third clause is the one that fails silently when omitted.

## Operational Effect

Without the binding check, a substituted-key envelope is indistinguishable from a legitimate one at every cryptographic layer. The failure is not detected by any standard envelope validation, and the only observable is a downstream semantic inconsistency between the sender's local record and the recipient's received plaintext — which requires the sender to log its outbound intent and the recipient to compare, a cross-agent correlation that most pipelines do not perform.

With the binding check, the substituted envelope is rejected at the recipient before plaintext delivery, with a specific, attributable error: the sealing key does not match the published key for the claimed epoch. The sender's attestation remains valid and is retained for audit; the rejection is logged against the directory entry that was overwritten, which is the actual root cause.

The cost is one additional fingerprint comparison and a replay-window key that includes the recipient-key fingerprint. The benefit is that the third invariant — channel binding — is enforced rather than assumed, and the silent window between substitution and semantic detection collapses to zero.

```python
import hashlib
from dataclasses import dataclass


class EnvelopeKeyBindingError(RuntimeError):
    """Raised when an envelope's sealing key does not match the recipient's published key."""
    pass


@dataclass(frozen=True)
class Envelope:
    sender_id: str
    nonce: int
    recipient_key_fingerprint: str
    ciphertext: bytes
    attestation_signature: bytes


def fingerprint(public_key: bytes) -> str:
    return hashlib.sha256(public_key).hexdigest()


def verify_envelope(
    envelope: Envelope,
    published_key_for_epoch: bytes,
    sender_attestation_valid: bool,
    replay_window: set,
) -> None:
    # Sender-side invariants: attestation and freshness.
    if not sender_attestation_valid:
        raise EnvelopeKeyBindingError("attestation signature invalid")

    expected_fp = fingerprint(published_key_for_epoch)
    if envelope.recipient_key_fingerprint != expected_fp:
        # The silent failure: attestation and nonce are both fine, but the
        # ciphertext was sealed to a key the recipient did not publish.
        raise EnvelopeKeyBindingError(
            f"sealing key {envelope.recipient_key_fingerprint} does not match "
            f"published key {expected_fp} for claimed epoch"
        )

    window_key = (envelope.sender_id, envelope.nonce, envelope.recipient_key_fingerprint)
    if window_key in replay_window:
        raise EnvelopeKeyBindingError(f"duplicate envelope {window_key}")
    replay_window.add(window_key)
```