Cas Cremers

Operational Semantics and Verification of Security Protocols

Security protocols are widely used to ensure secure communications over insecure networks, such as the internet or airwaves. These protocols use strong cryptography to prevent intruders from reading or modifying the messages. However, using cryptography is not enough to ensure their correctness. Combined with their typical small size, which suggests that one could easily assess their correctness, this often results in incorrectly designed protocols.

The authors present a methodology for formally describing security protocols and their environment. This methodology includes a model for describing protocols, their execution model, and the intruder model. The models are extended with a number of well-defined security properties, which capture the notions of correct protocols, and secrecy of data. The methodology can be used to prove that protocols satisfy these properties. Based on the model they have developed a tool set called Scyther that can automatically find attacks on security protocols or prove their correctness. In case studies they show the application of the methodology as well as the effectiveness of the analysis tool.

The methodology's strong mathematical basis, the strong separation of concerns in the model, and the accompanying tool set make it ideally suited both for researchers and graduate students of information security or formal methods and for advanced professionals designing critical security protocols.

A Formal Security Analysis of the Signal Messaging Protocol

Signal is a new security protocol that provides end-to-end encryption for instant messaging. It has recently been adopted by WhatsApp, Facebook Messenger and Google Allo among many others; the first two of these have at least 1 billion active users. Signal includes several uncommon security properties (such as ``future secrecy'' or ``post-compromise security''), enabled by a novel technique called ratcheting in which session keys are updated with every message sent. Despite its importance and novelty, there has been little to no academic analysis of the Signal protocol.

We conduct the first security analysis of Signal's Key Agreement and Double Ratchet as a multi-stage key exchange protocol. We extract from the implementation a formal description of the abstract protocol, define a security model which can capture the ``ratcheting'' key update structure, and prove the security of Signal's core in our model. Our presentation and results can serve as a starting point for other analyses of this widely adopted protocol.

Component-Based Formal Analysis of 5G-AKA: Channel Assumptions and Session Confusion

The 5G mobile telephony standards are nearing completion; upon adoption these will be used by billions across the globe. Ensuring the security of 5G communication is of the utmost importance, building trust in a critical component of everyday life and national infrastructure. We perform fine-grained formal analysis of 5G's main authentication and key agreement protocol (AKA), and provide the first models to explicitly consider all parties defined by the protocol specification. Our analysis reveals that the security of 5G-AKA critically relies on unstated assumptions on the inner workings of the underlying channels. In practice this means that following the 5G-AKA specification, a provider can easily and `correctly' implement the standard insecurely, leaving the protocol vulnerable to a security-critical race condition. We provide the first models and analysis considering component and channel compromise in 5G, whose results further demonstrate the fragility and subtle trust assumptions of the \aka protocol. We propose formally verified fixes to the encountered issues, and have worked with 3GPP to ensure these fixes are adopted.

On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees

Secure Authentication in the Grid: A Formal Analysis of DNP3 SAv5

Most of the world’s power grids are controlled remotely. Their control messages are sent over potentially insecure channels, driving the need for an authentication mechanism. The main communication mechanism for power grids and other utilities is defined by an IEEE standard, referred to as DNP3; this includes the Secure Authentication v5 (SAv5) protocol, which aims to ensure that messages are authenticated.

We provide the first security analysis of the complete DNP3: SAv5 protocol. Previous work has considered the message-passing sub-protocol of SAv5 in isolation, and considered some aspects of the intended security properties. In contrast, we formally model and analyse the complex composition of the protocol’s sub-protocols. In doing so, we consider the full state machine, the protocol’s asymmetric mode, and the possibility of cross-protocol attacks. Furthermore, we model fine-grained security properties that closely match the standard’s intended security properties. For our analysis, we leverage the TAMARIN prover for the symbolic analysis of security protocols.

Our analysis shows that the core DNP3: SAv5 design meets its intended security properties. Notably, we show that a previously reported attack does not apply to the standard. However, our analysis also leads to several concrete recommendations for improving future versions of the standard.

Abstractions for security protocol verification

A Comprehensive Symbolic Analysis of TLS 1.3

DECIM: Detecting Endpoint Compromise In Messaging

We present DECIM, an approach to solve the challenge of detecting endpoint compromise in messaging. DECIM manages and refreshes encryption/decryption keys in an automatic and transparent way: it makes it necessary for uses of the key to be inserted in an append-only log, which the device owner can interrogate in order to detect misuse.

We propose a multi-device messaging protocol that exploits our concept to allow users to detect unauthorised usage of their device keys. It is co-designed with a formal model, and we verify its core security property using the Tamarin prover. We present a proof-of-concept implementation providing the main features required for deployment. We find that DECIM messaging is efficient even for millions of users.

The methods we introduce are not intended to replace existing methods used to keep keys safe (such as hardware devices, careful procedures, or key refreshment techniques). Rather, our methods provide a useful and effective additional layer of security.

Secure Authentication in the Grid: A Formal Analysis of DNP3: SAv5

Most of the world's power grids are controlled remotely. Their control messages are sent over potentially insecure channels, driving the need for an authentication mechanism. The main communication mechanism for power grids and other utilities is defined by an IEEE standard, referred to as DNP3; this includes the Secure Authentication v5 (SAv5) protocol, which aims to ensure that messages are authenticated.

We provide the first security analysis of the complete DNP3: SAv5 protocol. Previous work has considered the message-passing sub-protocol of SAv5 in isolation, and considered some aspects of the intended security properties. In contrast, we formally model and analyse the complex composition of the protocol's three sub-protocols. In doing so, we consider the full state machine, and the possibility of cross-protocol attacks. Furthermore, we model fine-grained security properties that closely match the standard's intended security properties. For our analysis, we leverage the Tamarin prover for the symbolic analysis of security protocols.

Our analysis shows that the core DNP3: SAv5 design meets its intended security properties. Notably, we show that a previously reported attack does not apply to the standard. However, our analysis also leads to several concrete recommendations for improving future versions of the standard.

Automatically Detecting the Misuse of Secrets: Foundations, Design Principles, and Applications

We develop foundations and several constructions for security protocols that can automatically detect, without false positives, if a secret (such as a key or password) has been misused. Such constructions can be used, e.g., to automatically shut down compromised services, or to automatically revoke misused secrets to minimize the effects of compromise. Our threat model includes malicious agents, (temporarily or permanently) compromised agents, and clones.

Previous works have studied domain-specific partial solutions to this problem. For example, Google's Certificate Transparency aims to provide infrastructure to detect the misuse of a certificate authority's signing key, logs have been used for detecting endpoint compromise, and protocols have been proposed to detect cloned RFID/smart cards. Contrary to these existing approaches, for which the designs are interwoven with domain-specific considerations and which usually do not enable fully automatic response (i.e., they need human assessment), our approach shows where automatic action is possible. Our results unify, provide design rationales, and suggest improvements for the existing domain-specific solutions.

Based on our analysis, we construct several mechanisms for the detection of misuse. Our mechanisms enable automatic response, such as revoking keys or shutting down services, thereby substantially limiting the impact of a compromise.

In several case studies, we show how our mechanisms can be used to substantially increase the security guarantees of a wide range of systems, such as web logins, payment systems, or electronic door locks. For example, we propose and formally verify an improved version of Cloudflare's Keyless SSL protocol that enables key misuse detection.

Strengthening the security of authenticated key exchange against bad randomness

Recent history has revealed that many random number generators (RNGs) used in cryptographic algorithms and protocols were not providing appropriate randomness, either by accident or on purpose. Subsequently, researchers have proposed new algorithms and protocols that are less dependent on the RNG. One exception is that all prominent authenticated key exchange (AKE) protocols are insecure given bad randomness, even when using good long-term keying material. We analyse the security of AKE protocols in the presence of adversaries that can perform attacks based on chosen randomness, i.e., attacks in which the adversary controls the randomness used in protocol sessions. We propose novel stateful protocols, which modify memory shared among a user’s sessions, and show in what sense they are secure against this worst case randomness failure. We develop a stronger security notion for AKE protocols that captures the security that we can achieve under such failures, and prove that our main protocol is correct in this model. Our protocols make substantially weaker assumptions on the RNG than existing protocols.

A Formal Security Analysis of the Signal Messaging Protocol

Signal is a new security protocol that provides end-to-end encryption for instant messaging. It has recently been adopted by WhatsApp, Facebook Messenger and Google Allo among many others; the first two of these have at least 1 billion active users. Signal includes several uncommon security properties (such as ``future secrecy'' or ``post-compromise security''), enabled by a novel technique called ratcheting in which session keys are updated with every message sent. Despite its importance and novelty, there has been little to no academic analysis of the Signal protocol.

We conduct the first security analysis of Signal's Key Agreement and Double Ratchet as a multi-stage key exchange protocol. We extract from the implementation a formal description of the abstract protocol, define a security model which can capture the ``ratcheting'' key update structure, and prove the security of Signal's core in our model. Our presentation and results can serve as a starting point for other analyses of this widely adopted protocol.

Symmetric polynomial & CRT based algorithms for multiple frequency determination from undersampled waveforms

Frequency estimation, especially with sampling rates below the Nyquist rate, has abundant applications in engineering. Recently, Chinese remainder theorem(CRT)-based frequency reconstruction from undersampled complex-value waveforms becomes one of the frontier focuses in the fields of signal processing, electromagnetism and optics etc. In this paper, we present several CRT-based algorithms for determining multiple frequencies via symmetric polynomials. The computational complexity of these algorithms is in the polynomial class (P).

Design, Analysis, and Implementation of ARPKI: an Attack-Resilient Public-Key Infrastructure

The current Transport Layer Security (TLS) Public-Key Infrastructure (PKI) is based on a weakest-link security model that depends on over a thousand trust roots. The recent history of malicious and compromised Certification Authorities has fueled the desire for alternatives. Creating a new, secure infrastructure is, however, a surprisingly challenging task due to the large number of parties involved and the many ways that they can interact. A principled approach to its design is therefore mandatory, as humans cannot feasibly consider all the cases that can occur due to the multitude of interleavings of actions by legitimate parties and attackers, such as private key compromises (e.g., domain, Certification Authority, log server, other trusted entities), key revocations, key updates, etc. We present ARPKI, a PKI architecture that ensures that certificate-related operations, such as certificate issuance, update, revocation, and validation, are transparent and accountable. ARPKI efficiently supports these operations, and gracefully handles catastrophic events such as domain key loss or compromise. Moreover ARPKI is the first PKI architecture that is co-designed with a formal model, and we verify its core security property using the TAMARIN prover. We prove that ARPKI offers extremely strong security guarantees, where compromising even n-1 trusted signing and verifying entities is insufficient to launch a man-in-the-middle attack. Moreover, ARPKI’s use deters misbehavior as all operations are publicly visible. Finally, we present a proof-of-concept implementation that provides all the features required for deployment. Our experiments indicate that ARPKI efficiently handles the certification process with low overhead. It does not incur additional latency to TLS, since no additional round trips are required.

On Post-Compromise Security

In this work we study communication with a party whose secrets have already been compromised. At first sight, it may seem impossible to provide any type of security in this scenario. However, under some conditions, practically relevant guarantees can still be achieved. We call such guarantees ``post-compromise security''.

We provide the first informal and formal definitions for post-compromise security, and show that it can be achieved in several scenarios. At a technical level, we instantiate our informal definitions in the setting of authenticated key exchange (AKE) protocols, and develop two new strong security models for two different threat models. We show that both of these security models can be satisfied, by proposing two concrete protocol constructions and proving they are secure in the models.

Our work leads to crucial insights on how post-compromise security can (and cannot) be achieved, paving the way for applications in other domains.

On Bitcoin Security in the Presence of Broken Crypto Primitives

Digital currencies like Bitcoin rely on cryptographic primitives to operate. However, past experience shows that cryptographic primitives do not last forever: increased computational power and advanced cryptanalysis cause primitives to break frequently, and motivate the development of new ones. It is therefore crucial for maintaining trust in a crypto currency to anticipate such breakage.

We present the first systematic analysis of the effect of broken primitives on Bitcoin. We identify the core cryptographic building blocks and analyze the various ways in which they can break, and the subsequent effect on the main Bitcoin security guarantees. Our analysis reveals a wide range of possible effects depending on the primitive and type of breakage, ranging from minor privacy violations to a complete breakdown of the currency.

Our results lead to several observations on, and suggestions for, the Bitcoin migration plans in case of broken cryptographic primitives.

Automated Analysis of TLS 1.3: 0-RTT, Resumption and Delayed Authentication

After a development process of many months, the TLS 1.3 specification is nearly complete. To prevent past mistakes, this crucial security protocol must be thoroughly scrutinised prior to deployment.

In this work we model and analyse revision 10 of the TLS 1.3 specification using the Tamarin prover, a tool for the automated analysis of security protocols. We specify and analyse the interaction of various handshake modes for an unbounded number of concurrent TLS connections. We show that revision 10 meets the goals of authenticated key exchange in both the unilateral and mutual authentication cases.

We extend our model to incorporate the desired delayed client authentication mechanism, a feature that is likely to be included in the next revision of the specification, and uncover a potential attack in which an adversary is able to successfully impersonate a client during a PSK-resumption handshake. This observation was reported to, and confirmed by, the IETF TLS Working Group.

Our work not only provides the first supporting evidence for the security of several complex protocol mode interactions in TLS 1.3, but also shows the strict necessity of recent suggestions to include more information in the protocol’s signature contents.

ASICS: Authenticated Key Exchange Security Incorporating Certification Systems

Most security models for authenticated key exchange (AKE) do not explicitly model the associated certification system, which includes the certification authority (CA) and its behaviour. However, there are several well-known and realistic attacks on AKE protocols which exploit various forms of malicious key registration and which therefore lie outside the scope of these models.

We provide the first systematic analysis of AKE security incorporating certification systems (ASICS). We define a family of security models that, in addition to allowing different sets of standard AKE adversary queries, also permit the adversary to register arbitrary bitstrings as keys. For this model family we prove generic results that enable the design and verification of protocols that achieve security even if some keys have been produced maliciously. Our approach is applicable to a wide range of models and protocols; as a concrete illustration of its power, we apply it to the CMQV protocol in the natural strengthening of the eCK model to the ASICS setting.

Improving the ISO/IEC 11770 standard for key management techniques

We provide the first systematic analysis of the ISO/IEC 11770 standard for key management techniques (2009, 2009), which describes a set of key establishment, key agreement, and key transport protocols. We analyse the claimed security properties, as well as additional modern requirements on key management protocols, for over 30 protocols and their variants. Our formal, tool-supported analysis of the protocols uncovers several incorrect claims in the standard. We provide concrete suggestions for improving the standard.

Improving the Security of Cryptographic Protocol Standards

Despite being carefully designed, cryptographic protocol standards often turn out to be flawed. Integrating unambiguous security properties, clear threat models, and formal methods into the standardization process can improve protocol security.

Know Your Enemy: Compromising Adversaries in Protocol Analysis

We present a symbolic framework, based on a modular operational semantics, for formalizing different notions of compromise relevant for the design and analysis of cryptographic protocols. The framework’s rules can be combined to specify different adversary capabilities, capturing different practically-relevant notions of key and state compromise. The resulting adversary models generalize the models currently used in different domains, such as security models for authenticated key exchange. We extend an existing security-protocol analysis tool, Scyther, with our adversary models. This extension systematically supports notions such as weak perfect forward secrecy, key compromise impersonation, and adversaries capable of state-reveal queries. Furthermore, we introduce the concept of a protocol-security hierarchy, which classifies the relative strength of protocols against different adversaries.

In case studies, we use Scyther to analyse protocols and automatically construct protocol-security hierarchies in the context of our adversary models. Our analysis confirms known results and uncovers new attacks. Additionally, our hierarchies refine and correct relationships between protocols previously reported in the cryptographic literature.

Experiences in Developing and Delivering a Programme of Part-Time Education in Software and Systems Security

Abstract—We report upon our experiences in developing and delivering a programme of part-time education in Software and Systems Security at the University of Oxford. The MSc in Software and Systems Security is delivered as part of the Software Engineering Programme at Oxford — a collection of one-week intensive courses aimed at individuals who are responsible for the procurement, development, deployment and maintenance of large-scale software-based systems. We expect that our experiences will be useful to those considering a similar journey.

ARPKI: Attack Resilient Public-Key Infrastructure

We present ARPKI, a public-key infrastructure that ensures that certificate-related operations, such as certificate issuance, update, revocation, and validation, are transparent and accountable. ARPKI is the first such infrastructure that systematically takes into account requirements identified by previous research. Moreover, ARPKI is co-designed with a formal model, and we verify its core security property using the Tamarin prover. We present a proof-of-concept implementation providing all features required for deployment. ARPKI efficiently handles the certification process with low overhead and without incurring additional latency to TLS.

ARPKI offers extremely strong security guarantees, where compromising n-1 trusted signing and verifying entities is insufficient to launch an impersonation attack. Moreover, it deters misbehavior as all its operations are publicly visible.

Improving the ISO/IEC 11770 standard for key management techniques

We provide the first systematic analysis of the ISO/IEC 11770 standard for key management techniques, which describes a set of key exchange, key authentication, and key transport protocols. We analyse the claimed security properties, as well as additional modern requirements on key management protocols, for 30 protocols and their variants. Our formal, tool-supported analysis of the protocols uncovers several incorrect claims in the standard. We provide concrete suggestions for improving the standard.

Actor Key Compromise: Consequences and Countermeasures

Despite Alice's best efforts, her long-term secret keys may be revealed to an adversary. Possible reasons include weakly generated keys, compromised key storage, subpoena, and coercion. However, Alice may still be able to communicate securely with other parties, depending on the protocol used. We call the associated property resilience against Actor Key Compromise (AKC). We formalise this property in a symbolic model and identify conditions under which it can and cannot be achieved. In case studies that include TLS and SSH, we find that many protocols are not resilient against AKC. We implement a concrete AKC attack on the mutually authenticated TLS protocol.

Automated verification of group key agreement protocols

We advance the state-of-the-art in automated symbolic cryptographic protocol analysis by providing the first algorithm that can handle Diffie-Hellman exponentiation, bilinear pairing, and AC-operators. Our support for AC-operators enables protocol specifications to use multisets, natural numbers, and finite maps. We implement the algorithm in the TAMARIN prover and provide the first symbolic correctness proofs for group key agreement protocols that use Diffie-Hellman or bilinear pairing, loops, and recursion, while at the same time supporting advanced security properties, such as perfect forward secrecy or eCK-security. We automatically verify a set of protocols, including the STR, group Joux, and GDH protocols, thereby demonstrating the effectiveness of our approach.

Beyond eCK: Perfect Forward Secrecy under Actor Compromise and Ephemeral-Key Reveal

We show that it is possible to achieve perfect forward secrecy in two-message or one-round key exchange (KE) protocols even in the presence of very strong active adversaries that can reveal random values of sessions and compromise long-term secret keys of parties.

We provide two new game-based security models for KE protocols with increasing security guarantees, namely, eCK-w and eCK-PFS. The eCK-w model is a slightly stronger variant of the extended Canetti- Krawczyk (eCK) security model. The eCK-PFS model captures perfect forward secrecy in the presence of eCK-w adversaries. We propose a security-strengthening transformation (i.e., a compiler) from eCK-w to eCK-PFS that can be applied to protocols that only achieve security in a weaker model than eCK-w, which we call eCK-passive. We show that, given a two-message Diffie-Hellman type protocol secure in eCK-passive, our transformation yields a two-message protocol that is secure in eCK-PFS.

We demonstrate how our transformation can be applied to concrete KE protocols. In particular, our methodology allows us to prove the security of the first known one-round protocol that achieves perfect forward secrecy under actor compromise and ephemeral-key reveal.

ASICS: Authenticated Key Exchange Security Incorporating Certification Systems

Most security models for authenticated key exchange (AKE) do not explicitly model the associated certification system, which includes the certification authority (CA) and its behaviour. However, there are several well-known and realistic attacks on AKE protocols which exploit various forms of malicious key registration and which therefore lie outside the scope of these models.

We provide the first systematic analysis of AKE security incorporating certification systems (ASICS). We define a family of security models that, in addition to allowing different sets of standard AKE adversary queries, also permit the adversary to register arbitrary bitstrings as keys. For this model family we prove generic results that enable the design and verification of protocols that achieve security even if some keys have been produced maliciously. Our approach is applicable to a wide range of models and protocols; as a concrete illustration of its power, we apply it to the CMQV protocol in the natural strengthening of the eCK model to the ASICS setting.

The TAMARIN Prover for the Symbolic Analysis of Security Protocols

We present the TAMARIN prover for the symbolic analysis of security protocols. TAMARIN generalizes the backwards search used by the Scyther tool to enable protocol specification using multiset rewriting rules, property specification in a guarded fragment of first-order logic that allows quantification over messages and timepoints, and reasoning modulo equational theories. These features enable use of the tool to model protocols with mutable global state and complex control flow such as loops, and to specify complex security properties such as the eCK model. Additionally, they enable reasoning with respect to equational theories such as Diffie-Hellman and user-specified subterm-convergent theories. Similar to the Scyther tool, TAMARIN can analyze protocols with respect to an unbounded number of instances and fresh values.

TAMARIN provides an efficient, fully automatic mode to falsify or verify security protocols. Additionally, it provides a graphical, interactive mode, which enables users to explore proof states, inspect attack graphs, and combine manual proof guidance with automatic proof search.

Provably Repairing the ISO/IEC 9798 Standard for Entity Authentication

We formally analyze the family of entity authentication protocols defined by the ISO/IEC 9798 standard and find numerous weaknesses, both old and new, including some that violate even the most basic authentication guarantees. We analyze the cause of these weaknesses, propose repaired versions of the protocols, and provide automated, machine-checked proofs of the correctness of the resulting protocols. From an engineering perspective, we propose two design principles for security protocols that suffice to prevent all the weaknesses. Moreover, we show how modern verification tools can be used for falsification and certified verification of security standards. Based on our findings, the ISO working group responsible for the ISO/IEC 9798 standard has released an updated version of the standard.

Efficient Construction of Machine-Checked Symbolic Protocol Security Proofs

We embed an untyped security protocol model in the interactive theorem prover Isabelle/HOL and derive a theory for constructing proofs of secrecy and authentication properties. Our theory is based on two key ingredients. The first is a protocol-independent invariant that allows us to reason about the possible origin of messages. The second is a class of protocol-specific invariants that formalize type assertions about variables in protocol specifications. The resulting theory is well-suited for interactively constructing human-readable, protocol security proofs. We additionally give an algorithm that automatically generates Isabelle/HOL proof scripts based on this theory. In a number of case studies, we show that both interactive and automatic proof construction are efficient. The resulting proofs, constructed interactively or automatically, provide strong correctness guarantees since all proofs, including those deriving our theory from the security protocol model, are machine-checked.

Beyond eCK: Perfect Forward Secrecy under Actor Compromise and Ephemeral-Key Reveal

In this paper we show that it is possible to achieve perfect forward secrecy in two-message key exchange (KE) protocols that satisfy even stronger security properties than provided by the extended Canetti-Krawczyk (eCK) security model. In particular, we consider perfect forward secrecy in the presence of adversaries that can reveal the long-term secret keys of the actor of a session and reveal ephemeral secret keys.

We propose two new security models for KE protocols. First, we formalize a slightly stronger variant of the eCK security model that we call eCKw. Second, we integrate perfect forward secrecy into eCKw, which gives rise to the even stronger eCK-PFS model.

We propose a security-strengthening transformation (i.e., a compiler) between our new models. Given a two-message Diffie-Hellman type protocol secure in eCKw, our transformation yields a two-message protocol that is secure in eCK-PFS. As an example, we show how our transformation can be applied to the NAXOS protocol.

Automated Analysis of Diffie-Hellman Protocols and Advanced Security Properties

We present a general approach for the symbolic analysis of security protocols that use Diffie-Hellman exponentiation to achieve advanced security properties. We model protocols as multiset rewriting systems and security properties as first-order formulas. We analyze them using a novel constraint-solving algorithm that supports both falsification and verification, even in the presence of an unbounded number of protocol sessions. The algorithm exploits the finite variant property and builds on ideas from strand spaces and proof normal forms. We demonstrate the scope and the effectiveness of our algorithm on non-trivial case studies. For example, the algorithm successfully verifies the NAXOS protocol with respect to a symbolic version of the eCK security model.

Distance Hijacking Attacks on Distance Bounding Protocols

After several years of theoretical research on distance bounding protocols, the first implementations of such protocols have recently started to appear. These protocols are typically analyzed with respect to three types of attacks: Distance Fraud, Mafia Fraud, and Terrorist Fraud.

We define and analyze a fourth main type of attack on distance bounding protocols, called Distance Hijacking. This type of attack poses a serious threat in many practical scenarios. We show that many proposed distance bounding protocols are vulnerable to Distance Hijacking, and we propose solutions to make these protocols resilient to this type of attack.

We show that verifying distance bounding protocols using existing informal and formal frameworks does not guarantee the absence of Distance Hijacking attacks. We extend a formal framework for reasoning about distance bounding protocols to include overshadowing attacks. We use the resulting framework to prove the absence of all of the found attacks for protocols to which our countermeasures have been applied.

Distance Hijacking Attacks on Distance Bounding Protocols (Abstract)

Distance bounding protocols are typically analyzed with respect to three types of attacks: Distance Fraud, Mafia Fraud, and Terrorist Fraud. We define a fourth main type of attacks on distance bounding protocols, called Distance Hijacking attacks. We show that many proposed distance bounding protocols are vulnerable to these attacks, and we propose solutions to make these protocols resilient to Distance Hijacking. Additionally, we generalize Distance Hijacking to Location Hijacking, to which location verification protocols may be vulnerable.

Provably Repairing the ISO/IEC 9798 Standard for Entity Authentication

The ISO/IEC 9798 standard defines a family of entity authentication protocols. We formally analyze these protocols and find numerous weaknesses, including some that violate even the most basic authentication guarantees. We show how these weaknesses can be uniformly remedied by following prudent design principles and we repair the protocols using these principles. We provide automated, machine-checked proofs of the correctness of the resulting protocols by extending a state-of-the-art method for generating machine-checked protocol proofs. Our analysis and recommendations have been acknowledged by the responsible ISO working group and an update to the standard will be released.

Key Exchange in IPsec revisited: Formal Analysis of IKEv1 and IKEv2

The IPsec standard aims to provide application-transparent end-to-end security for the Internet Protocol. The security properties of IPsec critically depend on the underlying key exchange protocols, known as IKE (Internet Key Exchange).

We provide the most extensive formal analysis so far of the current IKE versions, IKEv1 and IKEv2. We combine recently introduced formal analysis methods for security protocols with massive parallelization, allowing the scope of our analysis to go far beyond previous formal analysis. While we do not find any significant weaknesses on the secrecy of the session keys established by IKE, we find several previously unreported weaknesses on the authentication properties of IKE.

Examining Indistinguishability-Based Security Models for Key Exchange Protocols: The case of CK, CK-HMQV, and eCK

Many recent key exchange (KE) protocols have been proven secure in the CK, CK-HMQV, or eCK security models. The exact relation between these security models, and hence the relation between the security guarantees provided by the protocols, is unclear. We show first that the CK, CK-HMQV, and eCK security models are formally incomparable. Second, we show that these models are also practically incomparable, by providing for each model attacks on protocols from the literature that are not considered by the other models. Third, our analysis enables us to find previously unreported flaws in protocol security proofs from the literature. We identify the causes of these flaws and show how they can be avoided.

Session-state Reveal is stronger than eCK's Ephemeral Key Reveal: Using automatic analysis to attack the NAXOS protocol

In the paper Stronger Security of Authenticated Key Exchange, a new security model for authenticated key exchange protocols (eCK) is proposed. The new model is suggested to be at least as strong as previous models for key exchange protocols, such as the CK model. The model includes a new notion of an ephemeral-key reveal adversary query, which is claimed to be at least as strong as the session-state reveal query.
We investigate the relation between the two models by focusing on the difference in adversary queries. We formally model the NAXOS protocol and a variant of the eCK model, called eCK', in which the ephemeral-key reveal query is replaced by the session-state reveal query. Using Scyther, a formal protocol analysis tool, we automatically find attacks on the protocol, showing that the protocol is insecure in the eCK' model.
Our attacks prove that the session-state reveal query is stronger than the ephemeral-key reveal query and that the eCK security model is incomparable to the CK model, disproving several claims made in the literature.

Keeping Data Secret under Full Compromise using Porter Devices

We address the problem of confidentiality in scenarios where the attacker is not only able to observe the communication between principals, but can also fully compromise the communicating parties (their devices, not only their long term secrets) after the confidential data has been exchanged. We formalize this problem and explore solutions that provide confidentiality after the full compromise of devices and user passwords. We propose two new solutions that use explicit key deletion and forward-secret protocols combined with key storage on porter devices. Our solutions provide the users with full control over their privacy. We analyze the proposed solutions using an automatic verification tool. We also implement a prototype using a mobile phone as porter device to illustrate how the solution can be realized on modern platforms.

Modeling and Analyzing Security in the Presence of Compromising Adversaries

We present a framework for modeling adversaries in security protocol analysis, ranging from a Dolev-Yao style adversary to more powerful adversaries who can reveal different parts of principals' states during protocol execution. Our adversary models unify and generalize many existing security notions from both the computational and symbolic settings.

We extend an existing symbolic protocol-verification tool with our adversary models, resulting in the first tool that systematically supports notions such as weak perfect forward secrecy, key compromise impersonation, and adversaries capable of state-reveal queries. In case studies, we automatically find new attacks and rediscover known attacks that previously required detailed manual analysis.

Degrees of Security: Protocol Guarantees in the Face of Compromising Adversaries

(This paper builds on the adversary models presented in the ESORICS 2010 paper.)

We introduce the concept of a protocol-security hierarchy, which classifies the relative strength of protocols against different forms of compromise. In case studies, we use Scyther to automatically construct protocol-security hierarchies that refine and correct relationships between protocols previously reported in the cryptographic literature.

Strong Invariants for the Efficient Construction of Machine-Checked Protocol Security Proofs

We embed an operational semantics for security protocols in the interactive theorem prover Isabelle/HOL and derive two strong protocol-independent invariants. These invariants allow us to reason about the possible origin of messages and justify a local typing assumption for the otherwise untyped protocol variables. The two rules form the core of a theory that is well-suited for interactively constructing natural, human-readable, correctness proofs. Moreover, we develop an algorithm that automatically generates proof scripts based on these invariants. Both interactive and automatic proof construction are faster than competing approaches. Moreover, we have strong correctness guarantees since all proofs, including those deriving the underlying theory from the semantics, are machine checked.

Session-state Reveal is stronger than Ephemeral Key Reveal: Attacking the NAXOS key exchange protocol

In the paper Stronger Security of Authenticated Key Exchange [1, 2], a new security model for authenticated key exchange protocols (eCK) is proposed. The new model is suggested to be at least as strong as previous models for key exchange protocols. The model includes a new notion of an Ephemeral Key Reveal adversary query, which is claimed to be at least as strong as the Session-state Reveal query. We show that Session-state Reveal is stronger than Ephemeral Key Reveal, implying that the eCK security model is incomparable to the CK model [5, 6]. In particular we show that the proposed NAXOS protocol from [1, 2] does not meet its security requirements if the Session-state Reveal query is allowed in the eCK model. We discuss the implications of our result for some related protocols proven correct in the eCK model, and discuss the interaction between Session-state Reveal and protocol transformations.

Comparing State Spaces in Automatic Security Protocol Analysis

There are several automatic tools available for the symbolic analysis of security protocols. The models underlying these tools differ in many aspects. Some of the differences have already been formally related to each other in the literature, such as difference in protocol execution models or definitions of security properties. However, there is an important difference between analysis tools that has not been investigated in depth before: the explored state space. Some tools explore all possible behaviors, whereas others explore strict subsets, often by using so-called scenarios.

We identify several types of state space explored by protocol analysis tools, and relate them to each other. We find previously unreported differences between the various approaches. Using combinatorial results, we determine the requirements for emulating one type of state space by combinations of another type.

We apply our study of state space relations in a performance comparison of several well-known automatic tools for security protocol analysis. We model a set of protocols and their properties as homogeneously as possible for each tool. We analyze the performance of the tools over comparable state spaces. This work enables us to effectively compare these automatic tools, i.e., using the same protocol description and exploring the same state space. We also propose some explanations for our experimental results, leading to a better understanding of the tools.

Unbounded Verification, Falsification, and Characterization of Security Protocols by Pattern Refinement

We present a new verification algorithm for security protocols that allows for unbounded verification, falsification, and complete characterization. The algorithm provides a number of novel features, including: (1) Guaranteed termination, after which the result is either unbounded correctness, falsification, or bounded correctness. (2) Efficient generation of a finite representation of an infinite set of traces in terms of patterns, also known as a complete characterization. (3) State-of-the-art performance, which has made new types of protocol analysis feasible, such as multi-protocol analysis.

The Scyther Tool: Verification, Falsification, and Analysis of Security Protocols

CAV tool paper that provides an overview of the Scyther tool.

On the Protocol Composition Logic PCL

A recent development in formal security protocol analysis is the Protocol Composition Logic (PCL). We identify a number of problems with this logic as well as with extensions of the logic, as defined in [9, 13, 14, 17, 20, 21]. The identified problems imply strong restrictions on the scope of PCL, and imply that some claimed PCL proofs cannot be proven within the logic, or make use of unsound axioms. This includes the proofs of the CR protocol from [13, 14] and the SSL/TLS and IEEE 802.11i protocols from [20, 21]. Where possible, we propose solutions for these problems.

Comparing State Spaces in Automatic Security Protocol Verification

Many tools exist for automatic security protocol verification, and most of them have their own particular language for specifying protocols and properties. Several protocol specification models and security properties have been already formally related to each other. However, there is an important difference between verification tools, which has not been investigated in depth before: the explored state space. Some tools explore all possible behaviors, whereas others explore strict subsets, often by using so-called scenarios. Ignoring such differences can lead to wrong interpretations of the output of a tool. We relate the explored state spaces to each other and find previously unreported differences between the various approaches. We apply our study of state space relations in a performance comparison of several well-known automatic tools for security protocol verification. We model a set of protocols and their properties as homogeneously as possible for each tool. We analyze the performance of the tools over comparable state spaces. This work enables us to effectively compare these automatic tools, i.e. using the same protocol description and exploring the same state space. We also propose some explanations for our experimental results, leading to a better understanding of the tools.

(This paper is subsumed by the 2009 LNCS article Comparing State Spaces in Automatic Security Protocol Analysis with P. Lafourcade and P. Nadeau, found above.)

A framework for compositional verification of security protocols

Automatic security protocol analysis is currently feasible only for small protocols. Since larger protocols quite often are composed of many small protocols, compositional analysis is an attractive, but non-trivial approach. We have developed a framework for compositional analysis of a large class of security protocols. The framework is intended to facilitate automatic as well as manual verification of large structured security protocols. Our approach is to verify properties of component protocols in a multi-protocol environment, then deduce properties about the composed protocol. To reduce the complexity of multi-protocol verification, we introduce a notion of protocol independence and prove a number of theorems that enable analysis of independent component protocols in isolation. To illustrate the applicability of our framework to real-world protocols, we study a key establishment sequence in WiMAX consisting of three subprotocols. Except for a small amount of trivial reasoning, the analysis is done using automatic tools.

Injective synchronisation: an extension of the authentication hierarchy

Authentication is one of the foremost goals of many security protocols. It is most often formalised as a form of agreement, which expresses that the communicating partners agree on the values of a number of variables. In this paper we formalise and study an intensional form of authentication which we call synchronisation. Synchronisation expresses that the messages are transmitted exactly as prescribed by the protocol description. Synchronisation is a strictly stronger property than agreement for the standard intruder model, because it can be used to detect pre-play attacks. In order to prevent replay attacks on simple protocols, we also define injective synchronisation. Given a synchronising protocol, we show that a sufficient syntactic criterion exists that guarantees that the protocol is injective as well.

A Family of Multi-Party Authentication Protocols

We introduce a family of multi-party authentication protocols and discuss six novel protocols, which are members of this family. The first three generalize the well-known Needham-Schroeder-Lowe public-key protocol, the Needham-Schroeder private-key protocol, and the Bilateral Key Exchange protocol. The protocols satisfy injective synchronisation, which is a strong authentication property, and establish agreement over the nonces. These protocols make use of delegated authentication to keep the protocols small and efficient. For each of these protocols we define a strengthened version that does not rely on delegated authentication. All instantiations of the protocol family consist of 2p-1 messages for p parties, which we show to be the minimal number of messages required to achieve the desired security properties in the presence of a Dolev-Yao style intruder with compromised agents.

Feasibility of multi-protocol attacks

Formal modeling and verification of security protocols typically assumes that a protocol is executed in isolation, without other protocols sharing the network. We investigate the existence of multi-protocol attacks on protocols described in literature. Given two or more protocols, that share key structures and are executed in the same environment, are new attacks possible? Out of 30 protocols from literature, we find that 23 are vulnerable to multi-protocol attacks. We identify two likely attack patterns and sketch a tagging scheme to prevent multi-protocol attacks.

Compositionality of security protocols: a research agenda

The application of formal methods to security protocol analysis has been extensively researched during the last 25 years. Several formalisms and (semi-)automatic tools for the verification of security protocols have been developed. However, their applicability is limited to relatively small protocols that run in isolation. Many of the protocols that are in use today cannot be verified using these methods. One of the main reasons for this is that these protocols are composed of several sub-protocols. Such a composition of protocols is not addressed in the majority of formalisms. In this paper we identify a number of issues that are relevant to applying formal methods to the problem of security protocol composition. Additionally, we describe what research needs to be done to meet this challenge.

Operational semantics of security protocols

Based on a concise domain analysis we develop a formal semantics of security protocols. Its main virtue is that it is a generic model, in the sense that it is parameterized over e.g. the intruder model. Further characteristics of the model are a straightforward handling of parallel execution of multiple protocols, locality of security claims, the binding of local constants to role instances, and explicitly defined initial intruder knowledge. We validate our framework by analysing the Needham-Schroeder-Lowe protocol.

A syntactic criterion for injectivity of authentication protocols

Injectivity is essential when studying the correctness of authentication protocols, because non-injective protocols may suffer from replay attacks. The standard ways of verifying injectivity either make use of a counting argument, which only seems to be applicable in a verification methodology based on model-checking, or draw conclusions on the basis of the details of the data-model used. We propose and study a property, the loop property, that can be syntactically verified and is sufficient to guarantee injectivity. Our result is generic in the sense that it holds for a wide range of security protocol models, and does not depend on the details of message contents or nonce freshness.

Checking secrecy by means of partial order reduction

We propose a partial order reduction for model checking security protocols for the secrecy property. Based on this reduction we develop an automatic tool that can check security protocols for secrecy, given a finite execution scenario. We compare this tool to several other tools.

Defining authentication in a trace model

In this paper we define a general trace model for security protocols which allows to reason about various formal definitions of authentication. In the model, we define a strong form of authentication which we call synchronization. We present both an injective and a non-injective version. We relate synchronization to a formulation of agreement in our trace model and contribute to the discussion on intensional vs. extensional specifications.

When the Crypto in Cryptocurrencies Breaks: Bitcoin Security under Broken Primitives

Symbolically analyzing security protocols using tamarin

Evaluation of ISO/IEC 9798 Protocols

This report provides a security evaluation of the authentication protocol families described in parts 2, 3, and 4 of the ISO-IEC 9798 standard. Our analysis includes recommended amendments to the standard.

On the Limits of Authenticated Key Exchange Security with an Application to Bad Randomness

State-of-the-art authenticated key exchange (AKE) protocols are proven secure in game-based security models. These models have considerably evolved in strength from the original Bellare-Rogaway model. However, so far only informal impossibility results, which suggest that no protocol can be secure against stronger adversaries, have been sketched. At the same time, there are many different security models being used, all of which aim to model the strongest possible adversary. In this paper we provide the first systematic analysis of the limits of game-based security models. Our analysis reveals that different security goals can be achieved in different relevant classes of AKE protocols. From our formal impossibility results, we derive strong security models for these protocol classes and give protocols that are secure in them. In particular, we analyse the security of AKE protocols in the presence of adversaries who can perform attacks based on chosen randomness, in which the adversary controls the randomness used in protocol sessions. Protocols that do not modify memory shared among sessions, which we call stateless protocols, are insecure against chosen-randomness attacks. We propose novel stateful protocols that provide resilience even against this worst case randomness failure, thereby weakening the security assumptions required on the random number generator.

One-round Strongly Secure Key Exchange with Perfect Forward Secrecy and Deniability

Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand, using implicit authentication along the lines of MQV and descendants sacrifices perfect forward secrecy in one round and achieves only weak perfect forward secrecy instead.

We show that by reintroducing signatures, it is possible to satisfy both a strong key-exchange security notion as well as a strong form of deniability, in one-round key exchange protocols. Our security notion for key exchange is stronger than, e.g., the extended-CK model, and captures perfect forward secrecy. Our notion of deniability, which we call peer-and-time deniability, is stronger than that offered by, e.g., the SIGMA protocol.

We propose a concrete protocol and prove that it satisfies our definition of key-exchange security in the random oracle model as well as peer-and-time deniability. The protocol combines a signed-Diffie-Hellman message exchange with an MQV-style key computation, and offers a remarkable combination of advanced security properties and efficiency.