Message integrity, nonces & replay

Distinguish MACs from signatures, understand nonces and freshness, and learn how audience binding, purpose binding and domain separation combine to stop a validly authenticated message from being replayed in the wrong place, time or context.

Track

Fundamentals

Module

2 · Applied cryptography for agents

Prerequisites

Hash functions · Digital signatures

A MAC or a signature tells you a message is authentic and unmodified. That is necessary but not sufficient. A valid, unmodified message can still be captured and re-sent later (a replay), aimed at a service it was never meant for (wrong audience), or reused for a different operation than intended (wrong purpose). These attacks never break the cryptography — they abuse the gap between "authentic" and "appropriate right here, right now". Closing that gap is a matter of what you put inside the signed/authenticated bytes.

Both MACs and signatures provide integrity and authenticity, but the trust model differs sharply.

MAC (e.g. HMAC)

Symmetric: sender and verifier share one secret key. Fast and simple, but anyone who can verify can also forge, because verification needs the same secret. No third party can check it, and there is no non-repudiation.

Digital signature

Asymmetric: the private key signs, the public key verifies. Anyone can verify without any secret, and only the key holder could have produced it — giving third-party verifiability and non-repudiation. Slower than a MAC.

Nonce

A value used once: a counter, a random token, or a timestamp-plus-uniqueness. Included inside the authenticated message so each legitimate message is distinguishable and a re-sent copy is detectable.

Choose a MAC when both ends share a secret and no outside party must verify (e.g. a session token between two services). Choose a signature when a party that holds no secret must verify authorship, or when you need an auditable, non-repudiable record — the usual case across an agent authorization boundary.

Replay resistance is not a separate algorithm; it is achieved by binding context into the authenticated payload and checking it on receipt. A robust authenticated message carries, inside the signed bytes:

anti-replay envelope (what goes INSIDE the signed bytes)
signed = {
  payload : { action, args },
  nonce   : unique_once_value,     # freshness: never accept the same nonce twice
  iat     : issued_at_timestamp,
  exp     : expiry_timestamp,      # freshness: reject if now > exp
  aud     : "executor.vault-A",    # audience binding: who may act on this
  purpose : "transfer",            # purpose binding: what it authorizes
  domain  : "fleet:prod:v1"        # domain separation: which context/version
}
mac_or_sig = Sign(sk, canonical(signed))

# Verifier MUST check ALL of:
verify(pk, canonical(signed), sig)
  and now <= signed.exp
  and signed.aud  == MY_IDENTITY
  and signed.purpose in ALLOWED_FOR(caller)
  and signed.domain == MY_DOMAIN
  and seen.add(signed.nonce) succeeded   # i.e. nonce was not used before

Domain separation deserves emphasis: prefixing or tagging the input with a unique context label (protocol, version, chain, operation) ensures a value authenticated for one context cannot be lifted into another. The same technique prevents cross-protocol attacks where one message is reinterpreted as a different message type. RFC 8032-style schemes and many protocols bake domain separation into the hash input for exactly this reason.

1. 1Canonicalize the payload to exact bytes so signer and verifier hash the same thing.
2. 2Add a nonce (unique per message) and issued-at / expiry timestamps for freshness.
3. 3Add an audience field naming exactly which recipient may act, and a purpose field naming exactly what is authorized.
4. 4Add a domain/context tag (protocol + version + environment) for domain separation.
5. 5Sign or MAC the whole canonical envelope — never just the payload, or the context fields could be stripped or swapped.
6. 6On receipt, verify the authenticator, then check expiry, audience, purpose and domain, and finally record the nonce in a seen-set (with a TTL matching exp) so a replay is rejected.

synthetic — a captured order replayed three ways
# Legit, correctly signed order (no freshness/binding):
order = { action: "transfer", scope: "vault:A" }
sig   = Sign(sk, canonical(order))

# Attacker captures (order, sig) and:
#  1) RESENDS it tomorrow        -> no exp/nonce  => accepted again (replay)
#  2) sends it to executor B     -> no aud         => B acts on A's order
#  3) feeds it to the "refund" flow that reuses the same verify
#                                 -> no purpose/domain => reinterpreted

# Hardened order closes all three:
order2 = { action:"transfer", scope:"vault:A",
           nonce:N, exp:T, aud:"executor.A", purpose:"transfer", domain:"prod:v1" }

Every attack here succeeds against a signature that verifies perfectly. The cryptography is doing its job; the defect is that the signed statement failed to say when, for whom and for what. Adding and checking those fields is cheaper and more reliable than any downstream heuristic.

Agent systems are unusually exposed to replay because messages are machine-generated, high-volume, and often flow through queues, retries and logs where a copy is easy to capture. A signed tool-call or authorization that lacks freshness can be re-driven by a buggy retry or a malicious observer; one that lacks audience binding can be redirected to a more powerful executor; one that lacks domain separation can be replayed from staging into production or across versions. Binding nonce, expiry, audience, purpose and domain into every signed intent — and checking them before acting — is the practical core of safe delegation and is what the downstream signature-replay knowledge base entry covers in depth.

• ▸Signing only the payload and leaving context fields unauthenticated lets an attacker strip or alter them; always authenticate the whole envelope.
• ▸Nonce tracking needs real storage: an unbounded seen-set grows forever, so pair nonces with an expiry and evict after it — but ensure the window cannot be used to replay before eviction.
• ▸Timestamp-based freshness depends on clock sync; allow a small skew but keep expiry windows short, and remember a captured message is replayable until it expires.
• ▸A MAC gives no non-repudiation and cannot be verified by third parties; do not use it where auditability or cross-party verification is required.
• ▸Missing domain separation enables cross-protocol / cross-context reinterpretation even with perfect signatures — tag every context explicitly.
• ▸All of this assumes correct canonicalization; two "equal" objects that serialize differently break both verification and nonce matching.

Expected direction: nonce (+ seen-set) and exp/iat -> prevents replay of a re-sent copy; verifier rejects a seen nonce or an expired message. aud (audience) -> prevents redirecting the message to a different recipient; verifier checks aud == its own identity. purpose -> prevents reusing it for a different operation; verifier checks purpose is allowed for the caller. domain/context tag -> prevents cross-context/cross-version/cross-environment reinterpretation; verifier checks domain == its own. All fields must be inside the signed bytes, and every check must run before acting.

Why does a valid signature not prevent a replay attack?

Because the re-sent message is a genuine, unmodified, correctly signed copy. The signature says the bytes are authentic; it says nothing about whether they are fresh, so replay needs separate defenses (nonce, expiry).

When should you use a MAC instead of a signature, and what do you give up?

Use a MAC when both parties share a secret and no third party needs to verify — it is faster. You give up third-party verifiability and non-repudiation, since anyone who can verify can also forge.

What is domain separation and what attack does it stop?

Tagging the authenticated input with a unique context label (protocol/version/environment/operation) so a value authenticated for one context cannot be reused in another. It stops cross-protocol / cross-context reinterpretation of an otherwise valid message.