An NP Decision Procedure for Protocol Insecurity with XOR

Yannick Chevalier 1 Ralf Küsters 2 Michaël Rusinowitch 1 Mathieu Turuani 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We provide a method for deciding the insecurity of cryptographic protocols in presence of the standard Dolev-Yao intruder (with a finite number of sessions) extended with so-called oracle rules, i.e., deduction rules that satisfy certain conditions. As an instance of this general framework, we obtain that protocol insecurity is in NP for an intruder that can exploit the properties of the exclusive or (XOR) operator. This operator is frequently used in cryptographic protocols but cannot be handled in most protocol models. An immediate consequence of our proof is that checking whether a message can be derived by an intruder (using XOR) is in PTIME. We also apply our framework to an intruder that exploits properties of certain encryption modes such as cipher block chaining (CBC).
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2005, Theoretical Computer Science, 338 (1-3), pp.247-274
Liste complète des métadonnées

https://hal.inria.fr/inria-00103807
Contributeur : Mathieu Turuani <>
Soumis le : jeudi 5 octobre 2006 - 16:51:32
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09

Identifiants

  • HAL Id : inria-00103807, version 1

Citation

Yannick Chevalier, Ralf Küsters, Michaël Rusinowitch, Mathieu Turuani. An NP Decision Procedure for Protocol Insecurity with XOR. Theoretical Computer Science, Elsevier, 2005, Theoretical Computer Science, 338 (1-3), pp.247-274. 〈inria-00103807〉

Partager

Métriques

Consultations de la notice

513