Skip to Main content Skip to Navigation
Conference papers

DY* : A Modular Symbolic Verification Framework for Executable Cryptographic Protocol Code

Abstract : We present DY*, a new formal verification framework for the symbolic security analysis of cryptographic protocol code written in the F* programming language. Unlike automated symbolic provers, our framework accounts for advanced protocol features like unbounded loops and mutable recursive data structures, as well as low-level implementation details like protocol state machines and message formats, which are often at the root of real-world attacks. Our work extends a long line of research on using dependent type systems for this task, but takes a fundamentally new approach by explicitly modeling the global trace-based semantics within the framework, hence bridging the gap between trace-based and type-based protocol analyses. This approach enables us to uniformly, precisely, and soundly model, for the first time using dependent types, long-lived mutable protocol state, equational theories, fine-grained dynamic corruption, and trace-based security properties like forward secrecy and post-compromise security. DY* is built as a library of F* modules that includes a model of low-level protocol execution, a Dolev-Yao symbolic attacker, and generic security abstractions and lemmas, all verified using F*. The library exposes a high-level API that facilitates succinct security proofs for protocol code. We demonstrate the effectiveness of this approach through a detailed symbolic security analysis of the Signal protocol that is based on an interoperable implementation of the protocol from prior work, and is the first mechanized proof of Signal to account for forward and post-compromise security over an unbounded number of protocol rounds.
Complete list of metadata
Contributor : Bhargavan Karthikeyan <>
Submitted on : Tuesday, March 23, 2021 - 5:59:44 PM
Last modification on : Thursday, March 25, 2021 - 8:52:54 AM


Files produced by the author(s)


  • HAL Id : hal-03178425, version 1



Karthikeyan Bhargavan, Abhishek Bichhawat, Quoc Do, Pedram Hosseyni, Ralf Küsters, et al.. DY* : A Modular Symbolic Verification Framework for Executable Cryptographic Protocol Code. EuroS&P 2021 - 6th IEEE European Symposium on Security and Privacy, Sep 2021, Virtual, Austria. ⟨hal-03178425⟩



Record views


Files downloads