Search

Deniable message authentication has drawn significant attention since it was first formalized by Dwork, Naor, and Sahai (STOC 1998). Since then, multiple notions of deniability have been introduced that vary in the considered adversary model and the required level of deniability. Most of the previous works concentrate on fairly strong notions of deniability, allowing the prover to even dispute that an interaction took place. In practice, however, weaker forms of deniability may suffice, such as being able to deny that a certain message has been transmitted at a certain point in time. Our work here thus introduces alternative notions of deniable message authentication, including for example content deniability (where one can deny the actual message) and context deniability (where one can claim that the allegedly transmitted message is taken out of context). We then analyze existing approaches, carving out the deniability properties these protocols achieve. In particular, we investigate the off-the-record messaging protocol (OTR) of Borisov, Goldberg, and Brewer (WPES 2004), which lists deniability of authentication as one of its explicit goals, but escapes the strong notions of deniability in the literature.

The Internet Engineering Task Force (IETF) is currently developing the next version of the Transport Layer Security (TLS) protocol, version 1.3. The transparency of this standardization process allows comprehensive cryptographic analysis of the protocols prior to adoption, whereas previous TLS versions have been scrutinized in the cryptographic literature only after standardization. This is even more important as there are two related, yet slightly different, candidates in discussion for TLS 1.3, called draft-ietf-tls-tls13-05 and draft-ietf-tls-tls13-dh-based. We give a cryptographic analysis of the primary ephemeral Diffie-Hellman-based handshake protocol, which authenticates parties and establishes encryption keys, of both TLS 1.3 candidates. We show that both candidate handshakes achieve the main goal of providing secure authenticated key exchange according to an augmented multi-stage version of the Bellare-Rogaway model. Such a multi-stage approach is convenient for analyzing the design of the candidates, as they establish multiple session keys during the exchange. An important step in our analysis is to consider compositional security guarantees. We show that, since our multi-stage key exchange security notion is composable with arbitrary symmetric-key protocols, the use of session keys in the record layer protocol is safe. Moreover, since we can view the abbreviated TLS resumption procedure also as a symmetric-key protocol, our compositional analysis allows us to directly conclude security of the combined handshake with session resumption. We include a discussion on several design characteristics of the TLS 1.3 drafts based on the observations in our analysis.

The traditional approach to build a secure connection is to run a key exchange protocol and, once the key has been established, to use this key afterwards in a secure channel protocol. The security of key exchange and channel protocols, and to some extent also of the composition of both, has been scrutinized extensively in the literature. However, this approach usually falls short of capturing some key exchange protocols in which, due to practical motivation, the originally separated phases become intertwined and keys are established continuously. Two prominent examples of such protocols are TLS (with resumption), and Google's recently proposed low-latency protocol QUIC. In this work we revisit the previous security of model of Brzuska et al. (CCS'11) and expand it into a multi-stage key exchange model in the style of Bellare and Rogaway. In our model, parties can establish multiple keys in different stages and use these keys between stages, even to establish the next key. The advantage of using the formalization of Brzuska et al. is that it has been designed with the aim to provide compositional guarantees. Hence, we can, too, give sufficient conditions under which multi-stage key exchange protocols compose securely with any symmetric-key application protocol, like a secure channel protocol. We then exercise our model for the case of the QUIC protocol. Basically, we show that QUIC is an adequately secure multi-stage key exchange protocol and meets the suggested security properties of the designers. We continue by proposing some slight changes to QUIC to make it more amenable to our composition result and to allow reasoning about its security as a combined connection establishment protocol when composed with a secure channel protocol.

Distance-bounding protocols prevent man-in-the-middle attacks by measuring response times. The four attacks such protocols typically address, recently formalized in [10], are: (1) mafia fraud, where the adversary must impersonate to a verifier in the presence of an honest prover; (2) terrorist fraud, where the adversary gets some offline prover support to impersonate; (3) distance fraud, where provers claim to be closer to verifiers than they really are; and (4) impersonations, where adversaries impersonate provers during lazy phases. Durholz et al. [10] also formally analyzed the security of (an enhancement of) the Kim-Avoine protocol [14].In this paper we quantify the security of the following well-known distance-bounding protocols: Hancke and Kuhn [13], Reid et al. [16], the Swiss-Knife protocol [15], and the very recent proposal of Yang et al. [17]. Concretely, our main results show that (1) the usual terrorist-fraud countermeasure of relating responses to a long-term secret key may enable socalled key-learning mafia fraud attacks, where the adversary flips a single time-critical response to learn a key bit-by-bit; (2) though relating responses may allow mafia fraud, it sometimes enforces distance-fraud resistance by thwarting the attack of Boureanu et al. [5]; (3) none of the three allegedly terrorist-fraud resistant protocols, i.e. [15, 16, 17], is in fact terrorist fraud resistant; for the former two schemes this is a matter of syntax, attacks exploiting the strong formalization of [10]; the attack against the latter protocol of [17], however, is almost trivial; (4) unless key-update is done regardless of protocol completion, the protocol of Yang et al. is vulnerable to Denial-of-Service attacks. In light of our results, we also review definitions of terrorist fraud, arguing that, while the strong model in [10] may be at the moment more appropriate than mere intuition, it could be too strong to capture terrorist attacks.

In this paper we examine composability properties for the fundamental task of key exchange. Roughly speaking, we show that key exchange protocols secure in the prevalent model of Bellare and Rogaway can be composed with arbitrary protocols that require symmetrically distributed keys. This composition theorem holds if the key exchange protocol satisfies an additional technical requirement that our analysis brings to light: it should be possible to determine which sessions derive equal keys given only the publicly available information. What distinguishes our results from virtually all existing work is that we do not rely, neither directly nor indirectly, on the simulation paradigm. Instead, our security notions and composition theorems exclusively use a game-based formalism.We thus avoid several undesirable consequences of simulation-based security notions and support applicability to a broader class of protocols. In particular, we offer an abstract formalization of game-based security that should be of independent interest in other investigations using game-based formalisms.