Equivalences and calculi for formal verification of cryptographic protocols

Security protocols are essential to the proper functioning of any distributed system running over an insecure network but often have flaws that can be exploited even without breaking the cryptography. Formal cryptography, the assumption that the cryptographic primitives are flawless, facilitates the construction of formal models and verification tools. Such models are often based on process calculi, small formal languages for modelling communicating systems. The spi calculus, a process calculus for the modelling and formal verification of cryptographic protocols, is an extension of the pi calculus with cryptography. In the spi calculus, security properties can be formulated as equations on process terms, so no external formalism is needed. Moreover, the contextual nature of observational process equivalences takes into account any attacker/environment that can be expressed in the calculus. We set out to address the problem of automatic verification of observational equivalence in an extension of the spi calculus: A channel-passing calculus with a more general expression language. As a first step, we study existing non-contextual proof techniques for a particular canonical contextual equivalence. In contrast to standard process calculi, reasoning on cryptographic processes must take into account the partial knowledge of the environment about transmitted messages. In the setting of the spi calculus, several notions of environment-sensitive bisimulation has been developed to treat this environment knowledge. We exhibit distinguishing examples between several of these notions, including ones previously believed to coincide. We then give a general framework for comparison of environment-sensitive relations, based on a comparison of the corresponding kinds of environment and notions of environment consistency. Within this framework we perform an exhaustive comparison of the different bisimulations, where every possible relation that is not proven is disproven. For the second step, we consider the question of which expression languages are suitable. Extending the expression language to account for more sophisticated cryptographic primitives or other kinds of data terms quickly leads to decidability issues. Two important problems in this area are the knowledge problem and an indistinguishability problem called static equivalence. It is known that decidability of static equivalence implies decidability of knowledge in many cases; we exhibit an expression language where knowledge is decidable but static equivalence is not. We then define a class of constructor-destructor expression languages and prove that environment consistency over any such language directly corresponds to static equivalence in a particular extension thereof. We proceed to place some loose constraints on deterministic expression evaluation, and redefine the spi calculus in this more general setting. Once we have chosen an expression language, we encounter a third problem, which is inherent in the operational semantics of message-passing process calculi: The possibility to receive arbitrary messages gives rise to infinite branching on process input. To mitigate this problem, we define a symbolic semantics, where the substitution of received messages for input variables never takes place. Instead, input variables are only subject to logical constraints. We then use this symbolic semantics to define a symbolic bisimulation that is sound and complete with respect to its concrete counterpart, extending the possibilities for automated bisimulation checkers.