CS Paper Radar

Mutable State in Enrich-by-Need Security Protocol Analysis

Joshua D Guttman, Paul D Rowe, Eben Blaisdell

cs.CR ·submitted 2026-11-18 20:21 UTC · v1

Abstract

Security protocol analysis has emphasized message-passing, as this is how different principals interact in authentication, key exchange, and similar functionalities. However, in many protocols a principal also maintains mutable state that limits what actions its local sessions may take; this cross-session state is altered by other local sessions. In this paper we show how to represent this cross-session mutable state in the strand space approach to symbolic protocol analysis, and how to implement the resulting ideas in the Cryptographic Protocol Shapes Analyzer CPSA. The key theory is expressed in two axioms characterizing state, plus protocol-specific rules. It leads to tight, specific characterizations of protocol behavior in relevant cases, and aids in developing correct protocols relying on cross-session mutable state.

Comment
34 pages

Closest papers

Nearest neighbours by meaning across the whole index.

From Specs to Apps: Verifying and Monitoring Models of Signal and WhatsApp

cs.CR ·2026-09-10 ·Moustafa Said, Aurora Naska, Kevin Morio, Robert Künnemann
top venue similarity 0.60
Abstract · 16 pages, 3 figures, 4 tables. Full version of the corresponding ACM CCS '26 paper

The Signal protocol is a prominent messaging protocol that secures communication for billions of users. It powers WhatsApp, the most widely used messaging application worldwide, and the Signal app, popular among privacy-conscious users. Extensive research in the computational and Dolev-Yao settings provides strong formal security guarantees for the protocol itself. However, a gap remains between the guarantees of the protocol specification and the implementation's actual behavior at runtime. In this work, we bridge this gap by applying SpecMon, a recently proposed runtime monitor, to check whether observed executions conform to formal protocol models. To this end, we instrument two applications (WhatsApp Web and Signal Desktop) to capture their interactions with the network and the cryptographic components. Using this instrumentation, we develop two multiset-rewrite models that are compatible with Tamarin, thus enabling verification. We derive the first model of WhatsApp Web's implementation of the Signal protocol and the most detailed model to date of Signal's original protocol. Monitoring establishes that observed executions conform to these models, relative to the trusted event extraction and the symbolic abstraction. For the core components of the Signal protocol, we verify authentication and secrecy properties. Finally, monitoring reveals previously undocumented differences between the original libsignal library and WhatsApp's fork. We evaluate our methodology and demonstrate its reproducibility. Developing the WhatsApp Web model, instrumenting the app, adding fuzzing, and running the experiments took three person-weeks. We also demonstrate efficient monitoring of real-world applications and detection of deliberately injected security faults, with low overhead in our measured setting.

0.56

Closing the Loop: Bidirectional Fully Encrypted Protocols

cs.CR ·2026-09-15 ·Baigang Chen, Nicholas Hopper
similarity 0.58
Abstract

Fully encrypted protocols (FEPs) provide encrypted channels that make all protocol-generated bytes computationally indistinguishable from uniform random strings. Several previous works have explored security definitions and constructions of unidirectional FEPs: protocols in which one party acts only as a sender, and the other acts only as a receiver. However, most applications require two-way information exchange, and a network adversary can observe communication in both directions and their shared lifetime. Because the semantics of bidirectional channels involve more complex shared state, it is possible that the ``naïve'' composition of two unidirectional channels can result in a two-way protocol that can be detected based on dependencies between the two directions, such as traffic imbalance, channel closure, failures, or connection tear-down. To address this issue, we introduce new formal security definitions for bidirectional FEPs that capture exact shaping, delivery, protocol-state integrity, private half-close, and cross-direction isolation, while revealing a public ``sending schedule'' and ``closing epoch'' that may be randomized. We show that the trivial composition fails to meet these definitions, leading to practical detection attacks. We then construct provably secure bidirectional FEPs (BiFEPs) for both the datastream and datagram settings. For datastream, we combine two direction-separated FEPs with a ``wrapper'' layer that prevents detection based on the mismatch between uni- and bi-directional connection states. For datagram, we add encrypted DATA/FIN/ACK with replay protection and loss-tolerant close. We validate the design through a Rust implementation and show that none of the surveyed deployed protocols provides the full set of BiFEP security properties.

0.36

Understanding the Usability of Cryptographic Verification Tools

cs.CR ·2026-09-14 ·Tarikul Islam, Yasin Islam, Khandakar Ashrafi Akbar, Imtiaz Karim
similarity 0.56
Abstract

Cryptographic protocol verification tools are widely used to analyze the security of complex protocols, yet how users interact with these tools remains comparatively understudied. We present an exploratory human-centered study of experienced users of Tamarin, ProVerif, and related protocol verifiers. Our survey included researchers, graduate students, and practitioners with hands-on experience using Tamarin, ProVerif, or related tools. The findings reveal usability barriers across the verification workflow, including difficulties debugging non-termination and performance issues, and the lack of systematic methods for validating formal models against real protocols. When proofs fail without concrete attacks, users commonly simplify models, add helper lemmas, and revisit modeling abstractions. Participants also called for actionable diagnostics, clearer explanations of results, visualization, and automation for recurring proof tasks. Our findings suggest that persistent usability challenges arise from the gap between protocol-level reasoning and the verifier's formal model, proof procedures, and diagnostic output. We derive concrete design priorities for improving the accessibility, interpretability, and usability of cryptographic protocol verification tools.

0.31

Global Surveillance Under the Lens: Reconstructing Passive Dolev-Yao Intruders

cs.CR cs.SE ·2026-11-04 ·Paolo Modesti
similarity 0.56
Abstract · 50 pages, 7 figures

Global surveillance systems record large volumes of network traffic for retrospective analysis, but packet captures alone reveal little about protocol-level semantics. This paper presents an automated, specification-guided methodology for reconstructing passive Dolev-Yao intruder executions from captured network traffic and validating the reconstructed executions against a formal protocol specification. The framework takes a PCAP capture, an AnBx specification, and the associated deployment metadata; it extracts Java-serialised objects from TCP streams, reconstructs protocol sessions and channel-to-step assignments, and generates a passive intruder that evaluates the Dolev-Yao derived checks produced by the AnBx compiler. Three reconstruction challenges are addressed: multiple serialised objects and object references within a TCP stream, ambiguity in mapping interleaved connections to concurrent protocol sessions, and semantic validation of candidate reconstructions. We evaluate the methodology on 121 protocols from the AnBx test suite. For single-session captures, the standard JDK cryptographic provider recovers 97.8% of expected objects and achieves 94.2% successful reconstruction, where success requires complete object recovery and a clean passive-intruder execution. For the 112 parallel-capable protocols, the toolchain achieves 89.3% successful reconstruction for both two and three concurrent sessions, while recovering approximately 97.2% of expected objects. Experiments with mismatched protocol-role mappings and deliberately mutated traces show that the generated Dolev-Yao checks respond to semantic inconsistencies. By making the reconstruction step explicit, the solution produces protocol-level observations on which assessments of protocol resilience and the design of defensive countermeasures can be built.

0.27

CoordX Types: A Trustless, Swappable Type System for Shared Records

cs.CR ·2026-11-12 ·David Hyland-Wood, Rob Ewin, Peter Robinson
similarity 0.56
Abstract · 15 pages, 1 image, 8 tables, 1 code block

The CoordX Protocol carries signed and encrypted entries between parties. It proves who wrote each entry and who had permission to write it. It does not say what an entry means. That task belongs above the protocol layer. This paper describes the CoordX type system, the layer that gives entries a meaning. A type is a short document that says how to read one part of a shared record: which entries count, what each position means, what a party may do there, and what a party must do next. The type system has two key properties. It is trustless: a type is an ordinary signed object fixed by its digest, and every party evaluates it for itself over entries that the CoordX Protocol has already verified. No party has to trust a server, a registry or another party's software. It is swappable: a type names the interpreter it is written for, so many interpreters, of different capabilities and designs, can be used side by side in one record. We describe how to write type schemas, and we define the expressive power of the schema language. Payloads form a regular language. Entry structure forms a regular tree language. Every rule and every computed value is a total function in the primitive recursive class, so evaluation always halts. We compare this with KQML, FIPA-ACL and CBCL, and we relate it to language-theoretic security.

0.43

SeriCrypt: An LLM-Driven Context-Aware Serialization Framework for Cryptographic Protocols

cs.CR ·2026-08-25 ·Maosong Chen, Xi Chen, Mengcheng Ju, Dongliang Zhao, Chunxiang Gu
similarity 0.56
Abstract

Constructing syntactically correct and cryptographically valid message sequences is essential for protocol state machine learning, conformance testing, and fuzzing. Unlike plaintext protocols, cryptographic protocols involve complex cross-message state dependencies and cryptographic computation constraints. Existing automated approaches predominantly target text-based or plaintext protocols, leaving cryptographic message construction largely manual. We present SeriCrypt, an LLM-driven, context-aware serialization framework for cryptographic protocols. It employs a large language model to extract field constraints, state dependencies, and cryptographic computation rules from unstructured protocol specifications into a unified structured intermediate representation, formally characterized by a domain-specific language for cryptographic protocols (CDSL). A protocol-agnostic execution engine parses CDSL declarations, automating field value resolution, cryptographic primitive invocation, and byte-stream serialization. As case studies in protocol security testing, we use the framework to construct violation messages targeting specification-defined security constraints and to support protocol fuzzing, evaluating it on mainstream implementations of TLS 1.2/1.3, IKEv1/v2, SSH, and TLCP. SeriCrypt generated message sequences accepted by all evaluated implementations and completed handshakes in every scenario. Security constraint testing revealed five specification violations, and fuzzing reached deeper protocol states with higher code coverage than mainstream fuzzers under the same time budget, demonstrating the framework's practical value for cryptographic protocol security testing.

0.16

LLM-Assisted Automatic Security Proofs for Cryptographic Protocols: How Far Are We?

cs.CR cs.SE ·2026-09-28 ·Tianjian Liu, Shicheng Feng, Jin'ao Shang, Xiaoting Lyu, Bin Wang +3 more
similarity 0.55
Abstract · 12 pages, 12 figures

Large language models (LLMs) have shown strong potential for assisting software and security analysis tasks, yet their effectiveness in cryptographic symbolic protocol verification remains insufficiently understood. In this paper, we conduct the first systematic evaluation of the capability of state-of-the-art LLMs in cryptographic symbolic protocol verification. To quantify this capability, we propose \textsc{CRoST} (Coverage Rate of Solve Tree), a proof-based metric derived from the verifier's proof skeleton that measures the similarity between generated lemmas and reference lemmas. We then establish the rationale of \textsc{CRoST} through both theoretical analysis and empirical validation. The evaluation results show that state-of-the-art models achieve 38.82\% coverage on average, with 14.4\% of generated lemmas exceeding 80\% coverage, indicating that LLMs can already generate useful lemmas to a certain extent. However, they still exhibit non-trivial failure modes on complex multi-phase protocols, show diminishing returns under naive scaling, and incur substantial verification overhead. These findings clarify the practical potential and limitations of LLMs for protocol verification and motivate future work on complex real-world protocols.

0.22

Verification of Security Properties of Cryptographic Protocols

cs.CR ·2026-11-06 ·Simona Bernardi, Joaquín Ezpeleta
published similarity 0.53
Abstract

Developing cryptographic protocols that are free from vulnerabilities is very challenging, as evidenced by numerous design flaws and implementation bugs in widely used protocols. Recent work has leveraged model checking to generate negative test cases, that is test cases that include the behavior of Dolev-Yao attacker. In this paper, we address the problem of analyzing execution traces produced by testing protocol implementations with such negative test cases. We propose a method for detecting violations of security properties by model-checking execution traces. Our approach employs a model checker based on DLTL, a Linear Temporal Logic with freeze operators, and supports automation of the testing process through pre- and post-processing steps. These steps, respectively, bridge the gap between different levels of abstraction and synthesize the results produced by the model checker.We present experimental results as a proof of concept for the feasibility of the proposed method.

0.33