Search
 
loader loading subjects...
cover
Verifying a bounded number of sessions and its complexity
Michael Rusinowitch, Mathieu Turuani
13 - 34
10.3233/978-1-60750-714-7-13
Cryptology and Information Security Series
Volume 5: Formal Models and Techniques for Analyzing Security Protocols
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 asymetric and 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.

$35.00 / €27.50 / £22.00
Add PDF to cart