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

Michaël Rusinowitch; Mathieu Turuani

doi:10.1016/S0304-3975(02)00490-5

Journal articles

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

Michaël Rusinowitch ¹ Mathieu Turuani ¹

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

Document type :

Journal articles

Domain :

Computer Science [cs] / Cryptography and Security [cs.CR]

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 : Thursday, November 12, 2020 - 9:42:03 AM

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

Identifiers

Collections

Citation

Export

Metrics

302

Contact Legal Notice Personal Data

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

Identifiers

Collections

Citation

Export

Share

Metrics

302

Contact Legal Notice Personal Data