Tags:Dolev-Yao model, first-order theorem proving, protocol verification and security protocols

Abstract:

Symbolic verification of security protocols typically relies on an attacker model called the Dolev-Yao model, which does not model adequately various algebraic properties of cryptographic operators used in many real-world protocols. In this work we describe an integration of a state-of-the-art protocol verifier ProVerif, with automated first order theorem provers (ATP). The integration allows one to model directly algebraic properties of cryptographic operators as a first-order equational theory and the specified protocol can exported to a first-order logic specification in the standard TPTP format for ATP. An attack on a protocol corresponds to a refutation using the encoded first order clauses. We implement a tool that analyses this refutation and extracts an attack trace from it, and visualises the deduction steps performed by the attacker. We show that the combination of ProVerif and ATP can find attacks that cannot be found by ProVerif when algebraic properties are taken into account in the protocol verification.

Combining ProVerif and Automated Theorem Provers for Security Protocol Verification (System Description)