Logic in Computer Science (LICS 2003)

Paper: An NP Decision Procedure for Protocol Insecurity with XOR (at LICS 2003)

Authors: Yannick Chevalier Ralf Küsters Michaël Rusinowitch Mathieu Turuani

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 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 P. We also apply our framework to an intruder that exploits properties of certain encryption modes such as cipher block chaining (CBC).

BibTeX

  @InProceedings{ChevalierKstersRusi-AnNPDecisionProcedu,
    author = 	 {Yannick Chevalier and Ralf Küsters and Michaël Rusinowitch and Mathieu Turuani},
    title = 	 {An NP Decision Procedure for Protocol Insecurity with XOR},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003},
    year =	 2003,
    editor =	 {Phokion G. Kolaitis},
    month =	 {June}, 
    pages =      {261--270},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }