Steve Kremer: Computing knowledge in security protocols under convergent equational theories

Computing knowledge in security protocols under convergent equational theories

Ștefan Ciobâcă, Stéphanie Delaune, and Steve Kremer. Computing knowledge in security protocols under convergent equational theories. Journal of Automated Reasoning, 48(2):219–262, Springer, 2012.
doi:10.1007/s10817-010-9197-7

Download

[PDF] [HTML]

Abstract

The analysis of security protocols requires reasoning about the knowledge an attacker acquires by eavesdropping on network traffic. In formal approaches, the messages exchanged over the network are modeled by a term algebra equipped with an equational theory axiomatizing the properties of the cryptographic primitives (e.g. encryption, signature). In this context, two classical notions of knowledge, deducibility and indistinguishability, yield corresponding decision problems.
We propose a procedure for both problems under arbitrary convergent equational theories. Since the underlying problems are undecidable we cannot guarantee termination. Nevertheless, our procedure terminates on a wide range of equational theories. In particular, we obtain a new decidability result for a theory we encountered when studying electronic voting protocols. We also provide a prototype implementation.

BibTeX

@article{CDK-jar10,
  abstract =      {The analysis of security protocols requires reasoning
                   about the knowledge an attacker acquires by
                   eavesdropping on network traffic. In formal
                   approaches, the messages exchanged over the network
                   are modeled by a term algebra equipped with an
                   equational theory axiomatizing the properties of the
                   cryptographic primitives (e.g. encryption,
                   signature). In this context, two classical notions of
                   knowledge, deducibility and indistinguishability,
                   yield corresponding decision problems.\par We propose
                   a procedure for both problems under arbitrary
                   convergent equational theories. Since the underlying
                   problems are undecidable we cannot guarantee
                   termination. Nevertheless, our procedure terminates
                   on a wide range of equational theories. In
                   particular, we obtain a new decidability result for a
                   theory we encountered when studying electronic voting
                   protocols. We also provide a prototype
                   implementation.},
  author =        {Ciob{\^a}c{\u{a}}, {\c{S}}tefan and
                   Delaune, St{\'e}phanie and Kremer, Steve},
  DOI =           {10.1007/s10817-010-9197-7},
  journal =       {Journal of Automated Reasoning},
  number =        {2},
  pages =         {219-262},
  publisher =     {Springer},
  title =         {Computing knowledge in security protocols under
                   convergent equational theories},
  volume =        {48},
  year =          {2012},
  url =           {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/CDK-jar10.pdf},
}