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

[PDF] [HTML] 

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},
}