Computational Soundness Results for ProVerif - Bridging the Gap from Trace Properties to Uniformity

Michael Backes, Esfandiar Mohammadi, Tim RuffingPOST 2014 · OpenReview

Abstract

Security protocol verification often relies on Dolev-Yao symbolic models, where cryptographic operations are treated as idealized black boxes. While these models facilitate automated verification through tools like ProVerif, a critical question remains: does symbolic security guarantee security against real-world computational attackers? This "Computational Soundness" (CS) has been well-established for trace properties like authentication, but remains elusive for equivalence properties, which are essential for proving privacy, anonymity, and strong secrecy. This paper introduces a general "self-monitoring" condition that allows CS results for trace properties to be extended to the uniformity of bi-processes in the applied $\pi$-calculus. By integrating length functions and combining the strengths of the ProVerif and APTE verifiers, the authors establish the first computationally sound, automated verification chain for equivalence properties involving public-key encryption and digital signatures.

Introduction

In the formal analysis of security protocols, two distinct paradigms exist. The symbolic world (Dolev-Yao) treats cryptography as a set of algebraic rules, enabling efficient automated proofs. The computational world views cryptography as operations on bitstrings, where security is defined by the inability of a polynomial-time attacker to succeed with more than negligible probability.

Bridging these worlds—a field known as Computational Soundness (CS)—is vital for ensuring that automated proofs are mathematically meaningful in the real world. While researchers have successfully bridged this gap for trace properties (e.g., "the attacker cannot learn a specific secret"), equivalence properties present a greater challenge. Equivalence properties are used to define privacy: they ask whether an attacker can distinguish between two different protocol executions (e.g., "Is User A or User B participating?"). ProVerif, a leading symbolic verifier, checks a specific form of equivalence called uniformity. However, until now, there was no general framework to prove that ProVerif’s uniformity results were computationally sound for a broad range of cryptographic primitives.

The Self-Monitoring Condition

The core theoretical contribution of this work is the identification of the self-monitoring condition. The authors demonstrate that if a symbolic model is sufficiently expressive, any computational attacker capable of distinguishing between two processes (an equivalence violation) can be used to construct a symbolic "monitor."

This monitor runs both versions of a protocol simultaneously and raises a "bad" flag if it detects a divergence in behavior. By doing so, the authors effectively transform a complex equivalence problem into a simpler trace property problem. They prove that for "uniformity-enforcing" protocols, if the model is computationally sound for trace properties and satisfies the self-monitoring condition, it is also computationally sound for uniformity.

Incorporating Physical Realities: Length Functions

A significant hurdle in computational soundness is that real-world ciphertexts often reveal the length of the plaintext they contain. A symbolic model that treats encryption as a perfect black box might claim two messages are indistinguishable, even if they have different lengths. In the computational world, an attacker would immediately see the difference.

To address this, the authors incorporate length functions into their symbolic model. They introduce a length destructor to the applied $\pi$-calculus, ensuring that the symbolic model accounts for the information leakage inherent in message sizes. This addition is crucial for achieving a result that holds up against real-world bitstring-level attacks.

Methodology and Tool Integration

The research extends the CoSP (Computationally Sound Protocols) framework, a modular system for establishing CS results. The authors prove their results within CoSP and show that existing embeddings of the applied $\pi$-calculus into CoSP can be reused for uniform bi-processes.

On the practical side, verifying protocols with length functions is computationally expensive. ProVerif often fails to terminate when dealing with recursive length definitions (represented via Peano numbers). To overcome this, the authors developed a hybrid verification chain:

  1. ProVerif is used to handle the core protocol logic, with length functions stripped to ensure termination.
  2. APTE, a specialized protocol verifier, is used to verify the specific trace equivalences related to message lengths.

This combination allows for the first fully automated, computationally sound verification of privacy properties in protocols using public-key encryption and digital signatures.

Key Results and Impact

  • Theorem 1 (The Bridge): Establishes that for a wide class of protocols, trace-level computational soundness combined with self-monitoring implies equivalence-level computational soundness.
  • Theorem 3 (Case Study): Provides a concrete CS result for a Dolev-Yao model containing digital signatures, public-key encryption, and length functions.
  • Automated Chain: Demonstrates a practical workflow using ProVerif and APTE to produce rigorous proofs of privacy that are valid in the computational model.

Limitations and Future Work

While this work represents a major step forward, some limitations remain. The focus is on uniformity, which is a stricter condition than the more general observational equivalence. Consequently, some protocols that are computationally secure might be rejected by this framework because they do not satisfy the strict uniformity requirement.

Furthermore, the current case study is limited to encryption and signatures. Future research is needed to extend these results to more complex primitives, such as Diffie-Hellman key exchanges or Zero-Knowledge Proofs (ZKPs), and to improve the efficiency of symbolic length representations.

Summary updated

Abstract

Dolev-Yao models of cryptographic operations constitute the foundation of many successful verification tools for security protocols, such as the protocol verifier ProVerif. Research over the past decade has shown that many of these symbolic abstractions are computationally sound, i.e., the absence of attacks against the abstraction entails the security of suitable cryptographic realizations. Most of these computational soundness (CS) results, however, are restricted to trace properties such as authentication, and the few promising results that strive for CS for the more comprehensive class of equivalence properties, such as strong secrecy or anonymity, either only consider a limited class of protocols or are not amenable to fully automated verification. In this work, we identify a general condition under which CS for trace properties implies CS for uniformity of bi-processes, i.e., the class of equivalence properties that ProVerif is able to verify for the applied π-calculus. As a case study, we show that this general condition holds for a Dolev-Yao model that contains signatures, public-key encryption, and corresponding length functions. We prove this result in the CoSP framework (a general framework for establishing CS results). To this end, we extend the CoSP framework to equivalence properties, and we show that an existing embedding of the applied π-calculus to CoSP can be re-used for uniform bi-processes. On the verification side, as analyses in ProVerif with symbolic length functions often do not terminate, we show how to combine the recent protocol verifier APTE with ProVerif. As a result, we establish a computationally sound automated verification chain for uniformity of bi-processes in the applied π-calculus that use public-key encryption, signatures, and length functions.
BibTeX
@inproceedings{backes2014computational,
  author = {Michael Backes and Esfandiar Mohammadi and Tim Ruffing},
  title = {{Computational Soundness Results for ProVerif - Bridging the Gap from Trace Properties to Uniformity}},
  booktitle = {POST},
  year = {2014},
  url = {https://openreview.net/forum?id=O73t1dEXoWH},
}
Figure