Cryptographically Sound Analysis of Security Protocols

In this thesis, we show how formal methods can be used for the cryptographically sound verification of concrete implementations of security protocols in order to obtain trustworthy and meaningful proofs, and to eliminate human inaccuracies.

First, we show how to derive secure concrete implementations of a given abstract specification. The security proofs are essentially based on the well-established approach of bisimulation which can be formally verified yielding rigorous proofs. As an example, we present both a specification and a secure implementation of secure message transmission with ordered channels. Moreover, the example comprises a general methodology how secure implementation of arbitrary specifications can be obtained.

Thereafter, we concentrate on the actual goals the protocol should fulfill. Thus, we define integrity properties in our underlying model and we show that logic derivations among them carry over from the specification to the concrete implementation, which makes themaccessible for tool-assisted verification. As an example, we formally verify one concrete protocol using the theorem prover PVS yielding the first machine-aided and sound proof of a cryptographic protocol.

As additional properties of security protocols, we consider liveness and noninterference. The standard definition of these properties is not suited to cope with protocols involving real cryptographic primitives, so we introduce new definitions which are restricted to polynomial runs and include error probabilities. We show that both properties carry over from the specification to the concrete implementation, and we present two examples, one for each property, which we prove to fulfill our definitions.