Automated Verification of Equivalence Properties of Cryptographic Protocols - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport Technique) Année : 2012

Automated Verification of Equivalence Properties of Cryptographic Protocols

Résumé

Indistinguishability properties are essential in formal verification of cryptographic protocols. They are needed to model anonymity properties, strong versions of confidentiality and resistance against offline guessing attacks, which can be conveniently modeled using process equivalences. We present a novel procedure to verify equivalence properties for a bounded number of sessions of cryptographic protocols. As in the applied pi-calculus, our protocol specification language is parametrized by a first-order sorted term signature and an equational theory which allows formalization of algebraic properties of cryptographic primitives. Our procedure is able to verify trace equivalence for determi-nate cryptographic protocols. On determinate protocols, trace equivalence coincides with observational equivalence which can therefore be automatically verified for such processes. When protocols are not determinate our procedure can be used for both under-and over-approximations of trace equivalence, which proved successful on examples. The procedure can handle a large set of cryptographic primitives, namely those that can be modeled by an optimally reducing convergent rewrite system. The procedure is based on a fully abstract modelling of the traces of a bounded number of sessions of the protocols into first-order Horn clauses on which a dedicated resolution procedure is used to decide equivalence properties. We have shown that our procedure terminates for the class of subterm convergent equational theories. Moreover, the procedure has been implemented in a prototype tool A-KiSs (Active Knowledge in Security Protocols) and has been effectively tested on examples. Some of the examples were outside the scope of existing tools, including checking anonymity of an electronic voting protocol.
Fichier principal
Vignette du fichier
equivalence.pdf (712.97 Ko) Télécharger le fichier
equivalence (1).pdf (716.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00632564 , version 1 (14-10-2011)
inria-00632564 , version 2 (28-03-2012)
inria-00632564 , version 3 (12-06-2015)
inria-00632564 , version 4 (16-12-2015)

Identifiants

Citer

Rohit Chadha, Vincent Cheval, Stefan Ciobaca, Steve Kremer. Automated Verification of Equivalence Properties of Cryptographic Protocols. [Technical Report] Inria. 2012. ⟨inria-00632564v3⟩
406 Consultations
733 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More