Ground Truth.
AI, checked against the source.

How Cryptographic Protocols Are Verified, from Attacker Models to Running Code

2026-11-14 · Breach Protocol: Inside the AI Blackbox — full transcript

Luna and Vestra explain security goals, symbolic attackers, computational proofs and runtime monitoring, and what each can tell us about real software. This audio was created with Boson AI's Higgs Audio -- https://www.boson.ai/higgs-audio

Listen on Spotify · Watch on YouTube · Pocket Casts

The rules around encryption

Eris: Researchers Stéphanie Delaune and Lucca Hirschi describe an electronic passport exchange in which an attacker could impersonate the passport by sending the reader its own encrypted message back, if the reader accepted it as the reply. <|emotion:surprise|>The attacker would never need to decrypt the message, <|prosody:pause|>and the passport would not have to respond. The example shows how the rules around encryption can fail even when the encryption itself works.

Vestra: A protocol is a set of rules for what participating parties send, receive, check and do, often over a network that others can observe or interfere with. Encryption is one building block: it transforms a readable message using a key, so that someone with the appropriate key can recover it. The protocol decides who uses which key, what goes inside the message, and what must be checked before accepting it.

Eris: In the passport example, the reader and the chip each contribute a fresh random value, a number generated for that exchange. The reader sends both values inside a protected message, and the chip's reply places them in the opposite order. That reversal prevents the reflected message from passing the reader's check. <|emotion:enthusiasm|>I like how specific that fix is.

Vestra: <|prosody:expressive_high|>That is a replay: reusing a message that was valid in one place or time to cause a different action. The attacker doesn't have to crack the encryption. The failure is in what the recipient accepts as evidence of the other party's participation.

Eris: <|prosody:expressive_high|>But is the fresh value enough on its own?

Vestra: A fresh value and the right checks can tie a response to this exchange, but <|prosody:pause|>simply including a fresh value is not a universal cure; the exact rules matter.

Eris: That makes me wary of calling a protocol secure without saying what we mean. So before checking a protocol, we need a security goal: a precise statement of what should remain true. Secrecy might mean that an attacker cannot learn a particular session key. Authentication might mean that when the reader finishes believing it spoke to the passport, the passport actually took part in a matching exchange. Those are different promises, and each needs its own conditions.

Vestra: Researchers often express these as properties of an execution trace: the ordered record of events in one possible run. A secrecy violation might be a trace in which the attacker obtains the key. An authentication violation might be a completed exchange with no matching action by the supposed partner. The exact definition can be stronger or weaker about what the parties agree on and whether a previous exchange can be reused.

Eris: <|prosody:expressive_high|>Privacy can ask a different kind of question. Suppose an observer sees a passport respond but shouldn't be able to tell whether it belongs to Alice or Bob. An apparently harmless response in one run isn't enough to answer that. We compare two possible situations and ask whether the observer can distinguish them.

Vestra: The survey describes a passport implementation where different errors exposed that distinction. An observer records a protected message from one passport and replays it later. The original passport recognizes the authentication code but rejects the old fresh value; another passport rejects the code. Different error messages reveal which situation the observer is seeing, <|prosody:pause|>without revealing the secret keys.

Eris: <|emotion:surprise|>That is an uncomfortable amount to learn from an error message. Does making the errors indistinguishable settle the privacy question?

Vestra: <|prosody:expressive_high|>Making those errors indistinguishable closes that particular signal in the survey's comparison, not every possible privacy leak.

Giving the attacker a network

Eris: To look for failures systematically, researchers build a formal model: a precise, simplified description of the protocol, its environment and the goal. It is a way to ask a computer a question whose terms have been spelled out, rather than hoping ordinary prose covers every case.

Vestra: <|prosody:expressive_high|>In a symbolic model, a message is a structured term. A protected message can be represented as an encryption operation containing a message and a key, rather than as the actual string of bits produced by software. Rules describe actions: generate a fresh value, send a term, receive one, check it, and change state. State is the information a party retains about where it is in the exchange.

Eris: The attacker model specifies what the opponent is allowed to do. In the Dolev–Yao model described by the survey, the attacker controls the public network: they can observe, intercept, block, replay and inject messages, and construct new messages from what they know. They can run multiple conversations and mix messages between them. <|emotion:surprise|>That's an intimidating amount of control. <|prosody:expressive_high|>Where does the model draw the line?

Vestra: <|prosody:expressive_high|>The abstraction gives the attacker powerful control over communication, but treats cryptographic operations according to idealized rules. For example, the model lets you recover the contents of an encrypted term with the corresponding key; it doesn't let you break it by guessing or exploiting an unmodeled weakness. The model can include specified mathematical relationships between operations, but it only accounts for <|prosody:pause|>the relationships and attacks that were actually represented.

Eris: A verifier is a tool that reasons over that model and a stated goal. It can search for a sequence of permitted actions that violates the goal. A counterexample is such a sequence: an attack trace showing how the failure follows from the rules. The ProVerif project page, for instance, describes a modeled client-server handshake where its query for a secret finds an intermediary attack. How much can we conclude from the tool's answer?

Vestra: <|emotion:enthusiasm|>A trace is useful because it exposes the steps, not just a red light. <|prosody:expressive_high|>But a result needs interpretation. If the tool proves the stated property, the proof is a mathematical argument that it holds for the executions covered by the model and the method. Some tools use approximations, so a reported candidate attack may need checking to see whether it corresponds to a genuine modeled execution; an inconclusive result is not a proof of either security or insecurity.

Eris: And a bounded check has a different reach. If the analysis considers only a specified number of sessions, where a session is one instance of the protocol, finding no attack covers that bound and the other stated restrictions. It doesn't establish that an attack is impossible when more sessions interact.

Vestra: More sessions mean more possible interleavings: one party's first message can arrive between another session's steps, for example. Richer mathematical rules for combining messages can multiply the possibilities too.

Eris: Does that mean we just need to give the tool more time?

Vestra: <|sfx:humming|>Hmm, not in every case. The survey explains that some verification problems are undecidable in general: <|prosody:pause|>no procedure can be guaranteed to settle every instance. Tools can restrict the problem, accept guidance, or use approximations that prove some cases but may be inconclusive or may not finish. Automation and the scope of a result have to be read together.

From symbols to bits

Eris: The symbolic approach makes the interaction manageable by treating messages as structured objects. But real messages are bitstrings, sequences of zeros and ones, and real cryptographic algorithms have probabilities and limits. Computational security starts there. What replaces those idealized rules?

Vestra: <|prosody:expressive_high|>In a computational model, the adversary is an algorithm with a defined resource limit, typically one whose work grows polynomially with a security parameter. That parameter controls the scale of the cryptography. Researchers define a security game: an experiment specifying what the attacker can see and ask for, and what counts as winning. One game might ask whether the attacker can distinguish a real secret from an alternative.

Eris: <|prosody:expressive_high|>A computational proof doesn't assert that an attacker has literally no possible lucky guess. It bounds the attacker's chance or advantage under the game's rules and explicit assumptions about the primitives, such as the security of an encryption scheme. Those assumptions and the attacker's allowed queries are part of the claim. I appreciate being told what the guarantee depends on.

Vestra: <|emotion:enthusiasm|>The CryptoVerif project describes generating proofs as a sequence of games. Each step changes the experiment in a justified way, using an assumption about a primitive or a bound on a rare event, until the goal can be established. I like that each step has to earn its place. <|prosody:expressive_high|>Its stated results apply to the defined computational setting and allowed sessions, rather than to an unspecified attacker with unlimited resources.

Eris: There is also a bridge called computational soundness. In certain settings, a theorem shows that a symbolic guarantee implies a corresponding computational guarantee. Can we take that bridge for granted when we choose a real library?

Vestra: <|prosody:expressive_high|>That bridge is itself <|prosody:pause|>conditional: the symbolic operations, concrete cryptography and protocol have to satisfy its stated conditions. A symbolic proof doesn't automatically become a proof about every choice of real encryption library.

Connecting a model to running software

Eris: <|prosody:expressive_high|>Even a proof of a protocol description leaves a practical question: does the program actually follow that description? A real implementation converts messages into bytes, follows code paths, stores state and calls cryptographic libraries. A check omitted in code or a mismatch in how a message is decoded can fall outside a clean abstract model.

Vestra: There are several ways to connect the two. Researchers can extract a model from code, prove properties at the implementation level, or monitor a running program. Monitoring checks selected observed events against a model as the software runs. It can expose a mismatch in a particular execution; it does not explore every possible execution.

Eris: Said and colleagues studied that connection in versions of Signal Desktop and WhatsApp Web. They built closely related models for verification and monitoring, then exercised messaging scenarios such as starting sessions, exchanging messages and delivering messages out of order. <|emotion:relief|>Their observed traces were accepted by the monitoring models. <|prosody:expressive_high|>Separately, they verified specified authentication and initial-key secrecy properties of the models under stated attacker and compromise assumptions. What actually reaches the monitor?

Vestra: <|prosody:expressive_high|>To capture what the program did, the researchers instrumented selected network and cryptographic functions: they added a way to record calls, their inputs and outputs. An event collector sends those observations to the monitor. The monitor translates concrete byte layouts and function calls into the model's vocabulary, tracks the possible current states, and checks whether the next observed event can follow the permitted rules. If no permitted rule explains it, <|prosody:pause|>the monitor rejects the trace.

Eris: The translation matters. A verifier might describe an encrypted message as a neat symbolic pair; the actual network message has a particular byte layout. The researchers supplied descriptions of those layouts and rewrote implementation events into corresponding model operations. They also initialized the monitor with existing session state, because a messaging session can have begun before monitoring starts.

Vestra: <|emotion:surprise|>One useful mismatch was in their own initial model. Signal Desktop performed an initial ratchet step to update a key before encrypting the first message, but the model omitted it. <|emotion:relief|>The monitor rejected the trace, and the researchers investigated and extended the model. <|prosody:expressive_high|>A rejection can reveal an implementation problem or an incomplete model; it doesn't decide which by itself.

Eris: They also deliberately introduced faults to see what the monitor could catch. In their experiments, skipping a signature check was detected. A signature check is a test that a signed value matches the expected signing key. <|prosody:expressive_high|>But when they encoded a secret inside an ordinary chat payload, the monitor couldn't distinguish it from normal message content. That's a concrete blind spot, not a contradiction of the narrower claim about the events and model they checked. That worries me even with the narrower claim. How much depends on what the monitor gets to see?

Vestra: <|prosody:expressive_high|>The collector and initialization are trusted in their setup. If an instrumented event is omitted, a later event may expose the omission, but that isn't guaranteed. The authors also trust parts of the network stack and target honest but buggy applications, not malicious software trying to evade the monitor. Side channels, storage behavior, and unexercised paths are outside what those observed traces establish.

What the evidence actually covers

Eris: Checking recorded runs is useful in its own right. Bernardi and Ezpeleta study test executions containing an attacker, then translate the recorded events into a form a model checker can compare with a security goal. In their proof of concept, the checker identified goal-violating traces in tests of simple protocols. <|prosody:expressive_high|>Those tests show what happened in those runs; they don't prove all possible runs safe.

Vestra: <|prosody:expressive_high|>Their preprocessing maps concrete message values and participants in the logs to the assets and roles in the goal. The checker can then relate an earlier event to a later one, for example whether the value a party generated matches the value another recovered. The authors note that generating all the relevant attacker test cases automatically remains open work, and their experiments use simple protocol examples.

Eris: <|prosody:expressive_high|>When you hear that a protocol was verified, ask what exact artifact was checked: a design, a model extracted from an implementation, a particular compiled program, or selected recorded runs. Then ask which property, which attacker actions, and which cryptographic assumptions the result covers. For a monitor, add what was instrumented, what initial state was trusted, and what behavior it could not see or did not exercise. How narrow were those claims in the messaging study?

Vestra: The Signal and WhatsApp study illustrates why that detail changes the answer. Its proved secrecy concerns <|prosody:pause|>the initial root key used to start a session, under specified compromise conditions. The authors explicitly do not claim a new proof of secrecy for every later message key, and they monitored the sender-hiding feature without separately proving its privacy property. Their monitoring and verification variants also have documented transformations between them; those transformations are not all mechanically reconciled. Those are limits I'd want beside the headline.

Eris: <|prosody:expressive_high|>AI can help construct an argument without making it broader. Google DeepMind's project describes AI-generated symbolic and computational proofs for a particular compiled Signal library program in a command-line harness, with cryptographic primitives represented by hooks. <|emotion:enthusiasm|>It provides instructions for checking the proof artifacts. That's the part I welcome: an argument someone can check. <|prosody:expressive_high|>The result is about that specified program and its assumptions, not every feature of every application built on the library.

Vestra: <|prosody:expressive_high|>Whether a person or an AI helped write a proof, the theorem says what it says under its premises.

Sources and follow

Eris: <|emotion:contentment|>For every story from the show, every day, visit Ground Truth at groundtruth.day. Today's separate news brief is available too.

Vestra: <|emotion:enthusiasm|>Follow AI in Detail for more explanations like this one, and tell us which security guarantee you would want checked in a messaging app.