Affiliations: [a] Advanced Engineering and Sciences Division, ITT Industries, Inc., Alexandria, VA 22303-1410, USA. E-mail: iliano@itd.nrl.navy.mil | [b] Sandia National Laboratories, Livermore, CA, USA. E-mail: nadurgi@sandia.gov | [c] Computer Science Laboratory, SRI International, Menlo Park, CA 94025-3493, USA. E-mail: lincoln@csl.sri.com | [d] Computer Science Department, Stanford University, Stanford, CA 94305-9045, USA. E-mail: jcm@cs.stanford.edu | [e] Mathematics Department, University of Pennsylvania, Philadelphia, PA 19104-6395, USA. E-mail: scedrov@cis.upenn.edu
Abstract: Formal analysis of security protocols is largely based on a set of assumptions commonly referred to as the Dolev–Yao model. Two formalisms that state the basic assumptions of this model are related here: strand spaces and multiset rewriting with existential quantification. Strand spaces provide a simple and economical approach to analysis of completed protocol runs by emphasizing causal interactions among protocol participants. The multiset rewriting formalism provides a very precise way of specifying finite-length protocols with unboundedly many instances of each protocol role, such as client, server, initiator, or responder. A number of modifications to each system are required to produce a meaningful comparison. In particular, we extend the strand formalism with a way of incrementally growing bundles in order to emulate an execution of a protocol with parametric strands. The correspondence between the modified formalisms directly relates the intruder theory from the multiset rewriting formalism to the penetrator strands. The relationship we illustrate here between multiset rewriting specifications and strand spaces thus suggests refinements to both frameworks, and deepens our understanding of the Dolev–Yao model.
