Homomorphisms and Minimality for Enrich-by-Need Security Analysis

Authors: Daniel Dougherty, Joshua Guttman and John Ramsdell

Paper Information

Title:Homomorphisms and Minimality for Enrich-by-Need Security Analysis
Authors:Daniel Dougherty, Joshua Guttman and John Ramsdell
Proceedings:FCS Informal Proceedings
Editors: Charles Morisset and Limin Jia
Keywords:Formal methods, Cryptographic protocols, Satisfiability Modulo Theories

ABSTRACT. A cryptographic protocol can be deployed in a variety of environments, but existing methods of protocol analysis focus only on the protocol, without being sensitive to assumptions about these environments.

We present LPA, a tool which analyzes protocols in context. LPA uses two programs, cooperating with each other: CPSA, a well-known system for protocol analysis, and Razor, a model-finder based on SMT technology. Our analysis follows the enrich-by-need paradigm, in which models of protocol execution are generated and examined.

The choice of which models to generate is important, and we develop a careful motivation and evaluation of LPA's strategy of building minimal models. In fact ``minimality'' can be defined with respect to either of two preorders, namely the homomorphism preorder and the embedding preorder (i.e. the preorder of injective homomorphisms); we discuss the merits of each. Our main technical contributions are algorithms for building homomorphism-minimal models and for generating a set-of-support for the models of a theory, in each case by scripting interactions with an SMT solver.

Talk:Jul 08 14:30 (Session 40E: Cryptography)