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},
  OPTmonth =         {},
  number =        {5},
  pages =         {583-616},
  publisher =     {{IOS} Press},
  title =         {Automated analysis of security protocols with global state},
  volume =        {24},
  year =          {2016},
  OPTnmonth =        {},
  url =           {https://hal.inria.fr/hal-01351388},
}