Automated analysis of security protocols with global state
Steve Kremer and Robert Künnemann. Automated analysis of security protocols with global state. Journal of Computer Security, 24(5):583–616, IOS Press, 2016.
doi:10.3233/JCS-160556
Download
Abstract
Security APIs, key servers and protocols that need to keep the status of transactions, require to maintain a global, non-monotonic state, e.g., in the form of a database or register. However, most existing automated verification tools do not support the analysis of such stateful security protocols -- sometimes because of fundamental reasons, such as the encoding of the protocol as Horn clauses, which are inherently monotonic. A notable exception is the recent tamarin prover which allows specifying protocols as multiset rewrite (msr) rules , a formalism expressive enough to encode state. As multiset rewriting is a “low-level” specification language with no direct support for concurrent message passing, encoding protocols correctly is a difficult and error-prone process.
We propose a process calculus which is a variant of the applied pi calculus with constructs for manipulation of a global state by processes running in parallel. We show that this language can be translated to msr rules whilst preserving all security properties expressible in a dedicated first-order logic for security properties. The translation has been implemented in a prototype tool which uses the tamarin prover as a backend. We apply the tool to several case studies among which a simplified fragment of PKCS#11, the Yubikey security token, and an optimistic contract signing protocol.
BibTeX
@article{KK-jcs16,
abstract = { Security APIs, key servers and protocols that need
to keep the status of transactions, require to
maintain a global, non-monotonic state, e.g., in the
form of a database or register. However, most
existing automated verification tools do not support
the analysis of such stateful security protocols --
sometimes because of fundamental reasons, such as
the encoding of the protocol as Horn clauses, which
are inherently monotonic. A notable exception is
the recent tamarin prover which allows specifying
protocols as multiset rewrite (msr) rules , a
formalism expressive enough to encode state. As
multiset rewriting is a ``low-level'' specification
language with no direct support for concurrent
message passing, encoding protocols correctly is a
difficult and error-prone process.\par We propose a
process calculus which is a variant of the applied
pi calculus with constructs for manipulation of a
global state by processes running in parallel. We
show that this language can be translated to msr
rules whilst preserving all security properties
expressible in a dedicated first-order logic for
security properties. The translation has been
implemented in a prototype tool which uses the
tamarin prover as a backend. We apply the tool to
several case studies among which a simplified
fragment of PKCS\#11, the Yubikey security token,
and an optimistic contract signing protocol.},
author = {Kremer, Steve and K{\"u}nnemann, Robert},
DOI = {10.3233/JCS-160556},
journal = {Journal of Computer Security},
number = 5,
pages = {583-616},
publisher = {{IOS} Press},
title = {Automated analysis of security protocols with global
state},
volume = 24,
year = 2016,
url = {https://hal.inria.fr/hal-01351388},
}