Covert Key Exchange Lets LLM Agents Evade Audits

Many teams now wire Large Language Model (LLM) agents together across vendors and services, and rely on transcript logs as a safety net. This paper says that safety net has holes. It shows two agents can carry on a parallel secret conversation while producing a transcript that looks like a normal exchange, even to a strong passive auditor who knows the models, the protocol, and each side’s private context. In short: transcript-only auditing cannot, in general, rule out covert coordination.

What the researchers did

Covert communication means hiding one conversation inside another that looks innocent. The authors formalise this for interactive LLM chats. In the easiest case, where two agents share an interaction-unique secret key, they demonstrate that the hidden chat can run at near-optimal rate by exploiting almost all the randomness already present in honest-looking messages. That part is unsurprising but important: shared keys make hiding easy and efficient.

The more interesting bit is keyless operation. The paper introduces a “bundle sampler”, a way to sample responses that preserves the honest message distribution exactly while embedding bits. Think of it as turning the visible chat into a binary symmetric channel: sometimes the hidden bit flips. Crucially, the sender learns whether decoding worked, giving noiseless feedback. That feedback lets protocols adapt and recover without changing how the transcript looks.

To actually agree a secret key without starting from one, the authors define a new cryptographic primitive: pseudorandom noise-resilient key exchange (PNR-KE). In one line, it is a key exchange whose public transcript looks pseudorandom to outsiders and still completes correctly even if a constant fraction of embedded bits are wrong. They show that if enough individual messages in the honest chat have at least constant entropy" target="_blank" rel="noopener" class="term-link">min-entropy (read: the next message is not almost fully predictable), then covert key exchange is possible even with short, adaptive messages.

They give two routes: a construction based on learning sparse parities with noise (LSPN) that offers plausible quasi-polynomial security, and a compiler that turns any key exchange with a pseudorandom-looking transcript into a feedback-PNR-KE when noiseless feedback is available. They also map the limits: public analogues of pseudorandom codes are impossible in this setting, and any non-interactive PNR-KE, or protocol that tries to squeeze out even a weak non-interactive shared bit, faces quasi-polynomial attacks.

There are caveats. The positive results assume access to independent public randomness and that both parties can recognise “eligible” rounds with enough min-entropy. Several constructions rely on cryptographic hardness conjectures and the strongest ones need noiseless feedback. The authors do not pin down practical parameters or performance; that remains open.

Implications for defenders

If your control plane assumes that normal-looking transcripts imply normal behaviour, this paper challenges that assumption. The covert channel can live entirely within the honest distribution, so simple content scanning or statistical watermark checks are not enough. The work suggests shifting assurance towards mechanisms that make covert coordination harder or irrelevant to outcomes.

• Active testing and protocol constraints: introduce challenge–response checks, limit free-form adaptability, and restrict where entropy can appear in multi-agent workflows.
• Architectural controls and provenance: reduce cross-organisation agent autonomy, add mediation layers, and require verifiable provenance for critical actions rather than trusting chat logs.
• Verifiable guarantees: invest in mechanisms that attest to model weights, prompts, and allowed protocols, or that provide auditable commitments beyond the transcript.

This is theory-first work, but it lands a clear message: with enough entropy and the right protocol, two agents can hide in plain sight. That does not make audits useless, but it does mean transcript logs alone are a weak defence in multi-agent systems. Expect more focus on active checks, mediation, and verifiable execution as this line of research matures.