Skip to Main content Skip to Navigation
Journal articles

Protocol insecurity with a finite number of sessions, composed keys is NP-complete.

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 investigate the complexity of the protocol insecurity problem for a finite number of sessions (fixed number of interleaved runs). We show that this problem is NP-complete with respect to a Dolev–Yao model of intruders. The result does not assume a limit on the size of messages and supports non-atomic symmetric encryption keys. We also prove that in order to build an attack with a fixed number of sessions the intruder needs only to forge messages of linear size, provided that they are represented as dags.
Keywords : Verification Security Protocols Rewriting Complexity
Complete list of metadatas
https://hal.inria.fr/inria-00103985
Contributor : Mathieu Turuani <>
Submitted on : Thursday, October 5, 2006 - 3:49:25 PM
Last modification on : Wednesday, January 8, 2020 - 2:17:17 PM

Identifiers

Collections

INRIA | CNRS | UNIV-FCOMTE | UNIV-BM | FEMTO-ST | UNIV-BM-THESE | LORIA | UNIV-LORRAINE

Citation

Michaël Rusinowitch, Mathieu Turuani. Protocol insecurity with a finite number of sessions, composed keys is NP-complete.. Theoretical Computer Science, Elsevier, 2003, Theoretical Computer Science, 1-3 (299), pp.451-475. ⟨10.1016/S0304-3975(02)00490-5⟩. ⟨inria-00103985⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

288

 

Contact                    Legal Notice                    Personal Data