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
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2003, Theoretical Computer Science, 1-3 (299), pp.451-475. 〈10.1016/S0304-3975(02)00490-5〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00103985
Contributeur : Mathieu Turuani <>
Soumis le : jeudi 5 octobre 2006 - 15:49:25
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09

Lien texte intégral

openaccess

Identifiants

Collections

INRIA | 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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

234

Contact


archive-ouverte@inria.fr