7 Search Results for "Kremer, Steve"


Document
Knowledge Problems in Security Protocols: Going Beyond Subterm Convergent Theories

Authors: Saraid Dwyer Satterfield, Serdar Erbatur, Andrew M. Marshall, and Christophe Ringeissen

Published in: LIPIcs, Volume 260, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)


Abstract
We introduce a new form of restricted term rewrite system, the graph-embedded term rewrite system. These systems, and thus the name, are inspired by the graph minor relation and are more flexible extensions of the well-known homeomorphic-embedded property of term rewrite systems. As a motivating application area, we consider the symbolic analysis of security protocols, and more precisely the two knowledge problems defined by the deduction problem and the static equivalence problem. In this field restricted term rewrite systems, such as subterm convergent ones, have proven useful since the knowledge problems are decidable for such systems. However, many of the same decision procedures still work for examples of systems which are "beyond subterm convergent". However, the applicability of the corresponding decision procedures to these examples must often be proven on an individual basis. This is due to the problem that they don't fit into an existing syntactic definition for which the procedures are known to work. Here we show that many of these systems belong to a particular subclass of graph-embedded convergent systems, called contracting convergent systems. On the one hand, we show that the knowledge problems are decidable for the subclass of contracting convergent systems. On the other hand, we show that the knowledge problems are undecidable for the class of graph-embedded systems.

Cite as

Saraid Dwyer Satterfield, Serdar Erbatur, Andrew M. Marshall, and Christophe Ringeissen. Knowledge Problems in Security Protocols: Going Beyond Subterm Convergent Theories. In 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 260, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{dwyersatterfield_et_al:LIPIcs.FSCD.2023.30,
  author =	{Dwyer Satterfield, Saraid and Erbatur, Serdar and Marshall, Andrew M. and Ringeissen, Christophe},
  title =	{{Knowledge Problems in Security Protocols: Going Beyond Subterm Convergent Theories}},
  booktitle =	{8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-277-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{260},
  editor =	{Gaboardi, Marco and van Raamsdonk, Femke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2023.30},
  URN =		{urn:nbn:de:0030-drops-180148},
  doi =		{10.4230/LIPIcs.FSCD.2023.30},
  annote =	{Keywords: Term rewriting, security protocols, verification}
}
Document
Transforming Password Protocols to Compose

Authors: Céline Chevalier, Stéphanie Delaune, and Steve Kremer

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)


Abstract
Formal, symbolic techniques are extremely useful for modelling and analysing security protocols. They improved our understanding of security protocols, allowed to discover flaws, and also provide support for protocol design. However, such analyses usually consider that the protocol is executed in isolation or assume a bounded number of protocol sessions. Hence, no security guarantee is provided when the protocol is executed in a more complex environment. In this paper, we study whether password protocols can be safely composed, even when a same password is reused. More precisely, we present a transformation which maps a password protocol that is secure for a single protocol session (a decidable problem) to a protocol that is secure for an unbounded number of sessions. Our result provides an effective strategy to design secure password protocols: (i) design a protocol intended to be secure for one protocol session; (ii) apply our transformation and obtain a protocol which is secure for an unbounded number of sessions. Our technique also applies to compose different password protocols allowing us to obtain both inter-protocol and inter-session composition.

Cite as

Céline Chevalier, Stéphanie Delaune, and Steve Kremer. Transforming Password Protocols to Compose. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 204-216, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{chevalier_et_al:LIPIcs.FSTTCS.2011.204,
  author =	{Chevalier, C\'{e}line and Delaune, St\'{e}phanie and Kremer, Steve},
  title =	{{Transforming Password Protocols to Compose}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{204--216},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.204},
  URN =		{urn:nbn:de:0030-drops-33273},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.204},
  annote =	{Keywords: Security, cryptographic protocols, composition}
}
Document
Simulation based security in the applied pi calculus

Authors: Stéphanie Delaune, Steve Kremer, and Olivier Pereira

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)


Abstract
We present a symbolic framework for refinement and composition of security protocols. The framework uses the notion of ideal functionalities. These are abstract systems which are secure by construction and which can be combined into larger systems. They can be separately refined in order to obtain concrete protocols implementing them. Our work builds on ideas from the ``trusted party paradigm'' used in computational cryptography models. The underlying language we use is the applied pi calculus which is a general language for specifying security protocols. In our framework we can express the different standard flavours of simulation-based security which happen to all coincide. We illustrate our framework on an authentication functionality which can be realized using the Needham-Schroeder-Lowe protocol. For this we need to define an ideal functionality for asymmetric encryption and its realization. We show a joint state result for this functionality which allows composition (even though the same key material is reused) using a tagging mechanism.

Cite as

Stéphanie Delaune, Steve Kremer, and Olivier Pereira. Simulation based security in the applied pi calculus. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 169-180, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{delaune_et_al:LIPIcs.FSTTCS.2009.2316,
  author =	{Delaune, St\'{e}phanie and Kremer, Steve and Pereira, Olivier},
  title =	{{Simulation based security in the applied pi calculus}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{169--180},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2316},
  URN =		{urn:nbn:de:0030-drops-23163},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2316},
  annote =	{Keywords: Simulation based security, applied pi calculus, joint state theorem, authentication protocols}
}
Document
07421 Abstracts Collection – Formal Protocol Verification Applied

Authors: Liqun Chen, Steve Kremer, and Mark D. Ryan

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
From 14/10/2007 to 19/10/2007, the Dagstuhl Seminar 07421 ``Formal Protocol Verification Applied'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Liqun Chen, Steve Kremer, and Mark D. Ryan. 07421 Abstracts Collection – Formal Protocol Verification Applied. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.07421.1,
  author =	{Chen, Liqun and Kremer, Steve and Ryan, Mark D.},
  title =	{{07421 Abstracts Collection – Formal Protocol Verification Applied}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.1},
  URN =		{urn:nbn:de:0030-drops-14196},
  doi =		{10.4230/DagSemProc.07421.1},
  annote =	{Keywords: Security protocols, formal verification, trusted computing, biometrics, security of mobile computing, electronic voting, payment systems}
}
Document
07421 Executive Summary – Formal Protocol Verification Applied

Authors: Liqun Chen, Steve Kremer, and Mark D. Ryan

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
Security protocols are a core part of distributed computing systems, and are part of our everyday life since they are used in web servers, email, mobile phones, bank transactions, etc. However, security protocols are notoriously difficult to get right. There are many cases of protocols which are proposed and considered secure for many years, but later found to have security flaws. Formal methods offer a promising way for automated security analysis of protocols. While there have been considerable advances in this area, most techniques have only been applied to academic case studies and security properties such as secrecy and authentication. The seminar brought together researchers deploying security protocols in new application areas, cryptographers, and researchers from formal methods who analyse security protocols. The interaction between researchers from these different communities aims to open new research topics, e.g., identify new security properties that need verification and refine abstractions of the abstract models of crytpographic primitives.

Cite as

Liqun Chen, Steve Kremer, and Mark D. Ryan. 07421 Executive Summary – Formal Protocol Verification Applied. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.07421.2,
  author =	{Chen, Liqun and Kremer, Steve and Ryan, Mark D.},
  title =	{{07421 Executive Summary – Formal Protocol Verification Applied}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.2},
  URN =		{urn:nbn:de:0030-drops-14186},
  doi =		{10.4230/DagSemProc.07421.2},
  annote =	{Keywords: Security protocols, formal verification, trusted computing, biometrics, security of mobile computing, electronic voting, payment systems}
}
Document
Complete Characterization of Security Protocols by Pattern Refinement

Authors: Cas Cremers

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
Recently, the notion of complete characterizations of security protocols was introduced by Guttman and Thayer. We provide an alternative definition of this concept, and extend an existing protocol verification tool (Scyther) to compute our notion of complete characterization. We present both notions of complete characterization, discuss their relative merits, and provide preliminary empirical results using an extended version of the Scyther tool.

Cite as

Cas Cremers. Complete Characterization of Security Protocols by Pattern Refinement. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{cremers:DagSemProc.07421.3,
  author =	{Cremers, Cas},
  title =	{{Complete Characterization of Security Protocols by Pattern Refinement}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.3},
  URN =		{urn:nbn:de:0030-drops-14173},
  doi =		{10.4230/DagSemProc.07421.3},
  annote =	{Keywords: Security protocols, Formal analysis, Verification, Tools}
}
Document
Zero-Knowledge in the Applied Pi-calculus and Automated Verification of the Direct Anonymous Attestation Protocol

Authors: Michael Backes, Matteo Maffei, and Dominique Unruh

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
We devise an abstraction of zero-knowledge protocols that is accessible to a fully mechanized analysis. The abstraction is formalized within the applied pi-calculus using a novel equational theory that abstractly characterizes the cryptographic semantics of zero-knowledge proofs. We present an encoding from the equational theory into a convergent rewriting system that is suitable for the automated protocol verifier ProVerif. The encoding is sound and fully automated. We successfully used ProVerif to obtain the first mechanized analysis of the Direct Anonymous Attestation (DAA) protocol. The analysis in particular required us to devise novel abstractions of sophisticated cryptographic security definitions based on interactive games.

Cite as

Michael Backes, Matteo Maffei, and Dominique Unruh. Zero-Knowledge in the Applied Pi-calculus and Automated Verification of the Direct Anonymous Attestation Protocol. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{backes_et_al:DagSemProc.07421.4,
  author =	{Backes, Michael and Maffei, Matteo and Unruh, Dominique},
  title =	{{Zero-Knowledge in the Applied Pi-calculus and Automated Verification of the Direct Anonymous Attestation Protocol}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--43},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.4},
  URN =		{urn:nbn:de:0030-drops-14153},
  doi =		{10.4230/DagSemProc.07421.4},
  annote =	{Keywords: Language-based security, zero-knowledge proofs, applied pi-calculus, direct anonymous attestation}
}
  • Refine by Author
  • 4 Kremer, Steve
  • 2 Chen, Liqun
  • 2 Delaune, Stéphanie
  • 2 Ryan, Mark D.
  • 1 Backes, Michael
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Automated reasoning
  • 1 Theory of computation → Equational logic and rewriting

  • Refine by Keyword
  • 3 Security protocols
  • 2 biometrics
  • 2 electronic voting
  • 2 formal verification
  • 2 payment systems
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 4 2008
  • 1 2009
  • 1 2011
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail