Nov 23, 2025 - 6 Min read

The Missing Primitives for Trustworthy AI Agents

This installment continues our series on the primitives required to make agent systems safe, predictable, and production ready:

Secure Multi-Agent Protocols (Part 10)

Multi-agent systems are becoming a common architecture: one agent plans, another fetches data, another executes tools, another enforces policy. But the communication layer between them is typically nothing more than raw JSON posted over HTTP.

There is no authenticated sender, no signature verification, no nonce, no version handshake, and no schema enforcement. In short: We are running autonomous agents on top of the least secure messaging pattern possible.

Inter-agent communication is a security boundary. Without a formal protocol, a malicious or compromised agent can impersonate others, inject false state transitions, or manipulate downstream tool executions.

This post defines the missing primitive: a secure, typed, authenticated, encrypted, and versioned protocol for multi-agent communication.

Why Multi-Agent Communication Must Be Secured

Agent-to-agent communication must deliver the same guarantees expected of modern distributed systems:

Strong identity: SPIFFE-based cryptographic identity ensures you know exactly which agent sent a message.
Integrity: Messages must be signed to detect tampering.
Schema guarantees: Loose JSON creates ambiguity, injection vectors, and inconsistent interpretation.
Replay protection: Messages cannot be processed twice or accepted out of temporal order.
Version negotiation: Agents evolve independently; they need a safe way to negotiate capabilities.
End-to-end confidentiality: Message contents must remain encrypted even on shared hosts or through intermediary hops.

A secure multi-agent protocol unifies all these requirements.

Primitive 1: Authenticated Identity + Signed Messages

Each inter-agent message must include:

a verifiable SPIFFE identity (Part 3)
a canonical serialized payload
a timestamp
a cryptographically unique nonce
a signature over the entire envelope

Canonicalization matters

Before signing, the message must be serialized with sorted keys so that signature verification is stable across environments. Without canonicalization, trivial JSON differences break signatures.

Example: Hardened Sign + Verify Logic

import json
import time
from cryptography.hazmat.primitives import serialization, hashes
from cryptography.hazmat.primitives.asymmetric import padding

class MessageVerificationError(Exception):
    pass


def sign_message(message: dict, private_key) -> dict:
    """
    Create a signed message envelope with canonical serialization.
    """
    envelope = {
        "payload": message,
        "timestamp": time.time(),
        "nonce": f"nonce-{int(time.time() * 1e9)}",
        "sender": "spiffe://example.com/agent/planner"
    }

    serialized = json.dumps(envelope, sort_keys=True).encode()

    signature = private_key.sign(
        serialized,
        padding.PSS(
            mgf=padding.MGF1(hashes.SHA256()),
            salt_length=padding.PSS.MAX_LENGTH,
        ),
        hashes.SHA256(),
    )

    envelope["signature"] = signature.hex()
    return envelope


def verify_message(envelope: dict, public_key):
    """
    Verify authenticity and integrity with controlled errors.
    Raises MessageVerificationError on failure.
    """
    try:
        sig = bytes.fromhex(envelope["signature"])
        body = {k: envelope[k] for k in envelope if k != "signature"}
        serialized = json.dumps(body, sort_keys=True).encode()

        public_key.verify(
            sig,
            serialized,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()),
                salt_length=padding.PSS.MAX_LENGTH,
            ),
            hashes.SHA256(),
        )

        return envelope["payload"]

    except Exception:
        raise MessageVerificationError("Invalid signature or tampered message")

Primitive 2: Strong, Typed Message Schemas

Protocols must define strict message types and reject malformed content. Typed schemas prevent inconsistent interpretation across agents.

Example: Pydantic schema

from pydantic import BaseModel, Field
from typing import Literal

class AgentMessage(BaseModel):
    version: Literal["v1"]
    type: Literal["task", "result", "error"]
    request_id: str
    sender: str
    payload: dict = Field(default_factory=dict)

Enforcing the schema

def validate_message(raw: dict) -> AgentMessage:
    """
    Enforces the strong message schema, raising a validation error on failure.
    """
    return AgentMessage(raw)

Typed message validation forms the “contract boundary” between agents.

Primitive 3: Message-Level Encryption + Authenticated Key Exchange

TLS encrypts the transport, not the message. With queues, sidecars, proxies, or multi-hop routing, message-level encryption remains necessary for confidentiality.

Authenticated ECDHE (Ephemeral Diffie-Hellman)

The industry-standard method for deriving session keys is Ephemeral Diffie-Hellman key exchange tied to authenticated SPIFFE identities. Each session produces a fresh symmetric key unique to that communication window.

This ensures:

strong forward secrecy
authenticated identity binding
unique keys per agent-pair session

Example: Encryption with session key

from cryptography.fernet import Fernet

def encrypt_message(serialized: bytes, session_key: bytes) -> bytes:
    """
    Encrypt canonical payload using the per-session symmetric key.
    """
    return Fernet(session_key).encrypt(serialized)

def decrypt_message(ciphertext: bytes, session_key: bytes) -> bytes:
    """
    Decrypt using the symmetric session key derived via ECDHE.
    """
    return Fernet(session_key).decrypt(ciphertext)

Primitive 4: Replay Protection via Cryptographic Nonces

Replay protection is often implemented incorrectly. Old implementations used timestamps, but timestamps fail due to:

clock drift (sender and receiver clocks differ)
race conditions (close timestamps collide)
imprecision (floating point timestamps rarely match)
guessability (timestamps are trivial to predict)

Therefore:

Replay protection must rely on cryptographically unique message IDs (nonces), not timestamps.

Timestamps exist only for staleness checks.

Updated replay logic

from collections import deque
import time

replay_cache = deque(maxlen=1000)

def is_replay(unique_id: str, timestamp: float) -> bool:
    """
    Checks both staleness (old messages) and duplication (nonce reuse).
    """
    now = time.time()

    # 1. Staleness check
    if now - timestamp > 5:
        return True

    # 2. Duplication check (nonce or hash)
    if unique_id in replay_cache:
        return True

    replay_cache.append(unique_id)
    return False

Every message must include a nonce or message hash.

Primitive 5: Version Negotiation + Capability Discovery

Agents evolve independently. A secure protocol needs:

version negotiation
capability introspection
safe deprecation windows
explicit compatibility requirements

Otherwise, agents silently drift apart.

Example: capability handshake

class CapabilityRequest(BaseModel):
    version: Literal["v1"]
    type: Literal["capability_request"]
    request_id: str
    sender: str

class CapabilityResponse(BaseModel):
    version: Literal["v1"]
    type: Literal["capability_response"]
    request_id: str
    sender: str
    capabilities: dict

Primitive 6: Formal Specification + Replay Integration

A protocol is a state machine, and like all state machines, it can be formally verified (Part 9).

A secure protocol must therefore be defined in a machine-readable format that allows symbolic reasoning, ensuring that the protocol itself can be proven safe.

A rigorous specification should include invariants such as:

no state transition shall result from an unauthenticated message
every decrypted payload must pass schema validation
session keys must be derived from verified identities
nonce reuse must never be accepted

When a solver like Z3 finds a counterexample to one of these invariants:

It outputs concrete variable assignments (nonce, sender, identity, etc).

These can be converted into a deterministic replay trace (Part 8).
Engineers can reproduce the violating message exchange step-by-step.
Formal verification + deterministic replay = full forensic transparency.

Summary Before Next Steps

By combining authenticated identities, strict schemas, message-level encryption, cryptographic nonces, version negotiation, and a formally specified protocol, we transform multi-agent communication from an informal best-effort pattern into a robust, verifiable, and governable distributed system. These primitives give agent teams the confidence that inter-agent communication cannot be hijacked, forged, replayed, or misinterpreted - crucial for any production-grade autonomous environment.

Practical Next Steps

Mandate SPIFFE-based identity for all agents
Require message signing + canonical serialization
Enforce Pydantic or Protobuf schemas
Use authenticated ECDHE to derive per-session keys
Require nonce-based replay protection
Add formal invariants for protocol correctness
Integrate protocol events into deterministic replay

Part 11 will focus on Agent Lifecycle Management - versioning, deployment pipelines, safe deprecation, and the operational realities of running agents at scale.

Trustworthy AI Agents: Secure Multi-Agent Protocols