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:
- ProVerif is used to handle the core protocol logic, with length functions stripped to ensure termination.
- 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