We narrow the gap between concrete implementations of cryptographic protocols and their verified models. We develop and verify a small functional implementation of the Transport Layer Security protocol (TLS 1.0). We make use of the same executable code for interoperability testing against mainstream implementations for automated symbolic cryptographic verification and automated computational cryptographic verification. We rely on a combination of recent tools and also develop a new tool for extracting computational models from executable code. We obtain strong security guarantees for TLS as used in typical deployments.  There has been much recent progress in formal methods and tools for cryptography, enabling the automated verification of complex security protocols. In practice, however, these methods and tools remain difficult to apply. Often, verification occurs independently of the development process, rather than during design, prototyping, and testing. Also, as a protocol or its implementations evolve, it is difficult to carry over security guarantees from past formal verification. Moreover, the verification of a system that uses a given protocol involves more than the cryptographic verification of an abstract model; it may rely as well on more standard analyses of code (e.g., to ensure memory safety) and system configuration (e.g., to enforce policy). For these reasons, we are interested in the integration of modern cryptographic protocol verifiers into the arsenal of software testing and verification tools. Implementations vs. Abstract Models. Protocol specifications include many details, most of which (but not all) are of no importance for security. In the process of distilling a formal cryptographic model, most of these details are discarded. When is a protocol model oversimplified? In contrast with formal guarantees proved within the model, the relevance of the model relies on the experience of the formalist. The problem is compounded when considering protocol implementations. Thus, we propose to verify detailed protocol implementations and deployments, as far as possible, rather than handwritten abstract models. By using automated tools based on sound-proof techniques, the details can either be safely erased or dealt with by brute-force analysis. Bhargavan et al. [2006] verify protocol implementations written in F#, a dialect of ML for the .NET runtime, by compilation to symbolic models in ProVerif [Blanchet 2001] . Their approach verifies as much protocol code as possible while providing handwritten models for the rest, such as the core libraries that provide cryptographic primitives, using bitstrings for concrete execution and symbolic terms for verification. In this work, we rely on their tools for symbolic verification and also experiment with direct computational cryptographic verifications of protocol implementations by compilation to CryptoVerif, a recent tool for computational cryptography [Blanchet 2008] . Our Approach. Figure 1 illustrates our general approach to developing, testing, and verifying a reference implementation of a protocol, plus a typical application. In contrast with the use of specialized modeling languages for cryptographic protocols, our use of a standard development platform enables early testing to disambiguate the specification, confirm functional correctness, and experiment with potential attacks, among other advantages. Verification consists of selecting a part of the implementation and writing additional verification harness code that specifies the attacker model, the cryptographic assumptions, and the target security properties, and then compiling their combination to some automated prover. Since the verification tool chain is automated, one can easily re-verify the code base as it evolves, much like regression testing. In our experience, symbolic and computational verifications are complementary. Computational verification is more precise but also more difficult to achieve; we obtain results only for the cryptographic core of the protocol implementation. Symbolic verification typically applies to the whole protocol, sometimes even including the application, but does not detect low-level cryptographic errors. Overall, we believe that the overhead of formal verification is getting affordable in comparison with design, development, and testing. The next generation of tools could enable their integration in the development process. Implementing and Verifying TLS. As an extended case study, this article considers implementations of TLS 1.0, one of the most widely deployed communications protocols. Due to its popularity, many systems embed an implementation of TLS and rely on its security for communications. As well as being of practical importance, TLS is a wellunderstood protocol with a carefully written, self-contained specification, a series of successive versions, and a large body of related verification work, providing a detailed history of security vulnerabilities and improvements. TLS is not an academic protocol, optimized (or designed) for verification purposes. This sometimes complicates its security analysis, but also provides a good benchmark for assessing verification techniques. (1) We program a small, functional implementation of TLS in F#. Using simple client and server code, we confirm that it interoperates with mainstream implementations. (2) Relying on a combination of model-extraction and verification tools, we obtain a range of positive security results, covering both symbolic and computational cryptographic aspects of the protocol. We thus provide security guarantees for code as it is used in typical deployments of TLS. (3) To support computational verification, we develop a new tool for extracting cryptographic models from F# code. To our knowledge, this enables the first automated verification of executable code under standard cryptographic assumptions. (4) We review known weaknesses for earlier variants of TLS, and confirm that they are exposed as we attempt to verify the corresponding weakened variants of our code. Contents. Section 2 recalls the main security features of TLS. Section 3 discusses reference protocol implementations in ML. Section 4 outlines our implementation for TLS, describes its main modules, of TLS and reports on interoperability. Section 5 presents our results using symbolic models; it also discusses formal security issues
Such translations have been used to symbolically and computationally analyze TLS implementations REF .
Verified Cryptographic Implementations for TLS
TSEC
Computer Science