Generic Compilers for Authenticated Key Exchange

Tibor Jager, Florian Kohlar, Sven Schäge, Jörg Schwenk

Published Jan 1, 2012• 0 citations

Abstract

So far, all solutions proposed for authenticated key agreement combine key agreement and authentication into a single cryptographic protocol. However, in many important application scenarios, key agreement and entity authentication are clearly separated protocols. This fact enables efficient attacks on the naïve combination of these protocols. In this paper, we propose new compilers for two-party key agreement and authentication, which are provably secure in the standard Bellare-Rogaway model. The constructions are generic: key agreement is executed first and results (without intervention of the adversary) in a secret session key on both sides. This key (or a derived key) is handed over, together with a transcript of all key exchange messages, to the authentication protocol, where it is combined with the random challenge(s) exchanged during authentication.

Related papers

Pairing-Based Two-Party Authenticated Key Agreement Protocol.

Rongxing Lu, Zhenfu Cao, Renwang Su +1 more

Abstract. To achieve secure data communications, two parties should be authenticated by each other and agree on a secret session key by exchanging messages over an insecure channel. In this paper, based on the bilinear pairing, we present a new two-party authenticated key agreement protocol, and use the techniques from provable security to examine the security of our protocol within Bellare-Rogaway model. 1

Jan 1, 20056 citations

Strongly Secure Authenticated Key Exchange in the Standard Model

Zheng Yang

Nowadays many crucial network applications rely on the existence of a confidential channel established by authenticated key exchange (AKE) protocols over public networks.With the rapid development of cyber technology, novel attacks to cryptosystem emerge in an endless stream.This has also led to the development of AKE solutions to provide increasingly stronger security guarantees.In this thesis we focus on provision of practical constructions for AKE protocols which are provably secure in a strong sense without resorting to random oracles.We first we present three new efficient compilers to generically turn passively secure key exchange protocols (KE) into authenticated key exchange protocols (AKE) where security also holds in the presence of active adversaries.Our compilers are not only a useful tool for the design of new AKE systems with many additional security properties in a modular and less error-prone fashion, but they also help to relax the assumptions on existing, practical key exchange mechanisms which are not known to be provably secure AKE protocols.Security of our compilers is shown in a strong modified CK model where the adversary is allowed to reveal either long-term secret key or state information of the protocol participants.On the second, we study the open problem on constructing eCK secure two party AKE protocol without random oracles and NAXOS trick.A generic construction satisfying those requirements is given based on well-known cryptographic primitives following the guideline of efficiency.Then a concrete protocol is proposed which is the first eCK secure protocol in the standard model under both standard assumptions and post-specified peer setting (i.e.without knowing any cryptographic information about its communication peer).Both proposed schemes can be more efficiently implemented with secure device than previous works which are eCK secure in the standard model, where the secure device might be normally used to store the long-term private key and to implement codes of protocol which need to be resilience of state leakage.Finally, we generalize our one-round two party AKE construction to group case that yields an efficient tripartite AKE protocol based on bilinear maps and a candidate group AKE protocol (with more than three members) based on multilinear maps.Up to now they are the first solutions which can be proved secure in the g-eCK model without random oracles.Meanwhile we make first step to show how to simplify the security proof for one-round group AKE under g-eCK model.i

Jan 1, 20130 citations

Future-Proofing Key Exchange Protocols

Jacqueline Brendel

Key exchange protocols, first introduced by Diffie and Hellman in 1976, are one of the most widely-deployed cryptographic protocols. They allow two parties, that have never interacted before, to establish shared secrets. These shared cryptographic keys may subsequently be used to establish a secure communication channel. Use cases include the classic client-server setting that is for example at play when browsing the internet, but also chats via end-to-end-encrypted instant messaging applications. Security-wise, we generally demand of key exchange protocols to achieve key secrecy and authentication. While, informally, authentication ensures that the communicating parties have confidence in the identity of their peers, key secrecy ensures that any shared cryptographic key that is established via the key exchange protocol is only known to the participants in the protocol and can be used securely in cryptographic protocols, i.e., is sufficiently random. In 1993, Bellare and Rogaway gave a first formalization of key exchange protocol security that captures these properties with respect to powerful adversaries with full control over the network. Their model constitutes the basis of the many subsequent treatments of authenticated key exchange security, including the models presented in this thesis. The common methodological approach underlying all of these formalizations is the provable security paradigm, which has become a standard tool in assessing the security of cryptographic protocols and primitives. So-called security models specify the expected security guarantees of the scheme in question with regards to a well-defined class of adversaries. Proofs that validate these security claims do so by reducing the security of the overall scheme to the security of the underlying cryptographic primitives and hardness assumptions. However, advances in computational power and more sophisticated cryptanalytic capabilities often render exactly these components insecure. Especially the advent of quantum computers will have a devastating effect on much of today's public key cryptography. This is especially true for key exchange protocols since they rely crucially on public-key algorithms. In this thesis, our focus in future-proofing key exchange protocols is two-fold. First, we focus on extending security models for key exchange protocols to capture the (un)expected break of cryptographic primitives and hardness assumptions. The aim is to gain assurances with respect to future adversaries and to investigate the effects of primitive failures on key exchange protocols. More specifically, we explore how key exchange protocols can be safely transitioned to new, post-quantum secure algorithms with hybrid techniques. Hybrids combine classical and post-quantum algorithms such that the overall key agreement scheme remains secure as long as one of the two base schemes remains secure. For this, we introduce security notions for key encapsulation mechanisms that account for adversaries with varying levels of quantum capabilities and present three new constructions for hybrid key encapsulation mechanisms. Our hybrid designs are practice-inspired and for example capture draft proposals for hybrid modes in the Transport Layer Security (TLS) protocol, which is one of the most widely-deployed cryptographic protocols that enables key agreement. Furthermore, our notion of breakdown resilience for key exchange protocols allows to gauge the security of past session keys in the event of a failure of a cryptographic component in the key exchange. We exercise our model on variants of the post-quantum secure key exchange protocol NewHope by Alkim et al. Thereby, we confirm the intuition that, in order to guard against adversaries that only have access to quantum computing power in the (more distant) future, it is sufficient to use classically-secure authentication mechanisms alongside post-quantum key agreement to achieve authenticated key exchange. As with any mathematical statement, theorems in the provable security paradigm are only as valid as the underlying assumptions. A careful consideration of any newly made assumption is thus essential to ensure the meaningfulness of the statement itself and make the assumption a viable tool for future analyses. Thus, secondly, we systematically classify the PRF-ODH assumption, a complexity-theoretic hardness assumption that has been used in key exchange security analyses of such prominent protocols as TLS, Signal, and Wireguard. In particular, we give a unified, parametrized definition of the assumption encompassing different variants that are present in the literature. We relate the resulting parametrized notions in terms of their strength and show where these assumptions fit in the collection of well-understood related hardness assumptions. We finally sketch our result on the impossibility of instantiating this assumption in the standard model, thereby disposing of the uncertainty in the community whether PRF-ODH is in fact a standard model assumption, i.e., removes the usage of some idealized assumptions in key exchange protocol proofs.

Jan 1, 20190 citations

Analysis and Improvement of Authenticated Group Key Agreement Protocol Compiler

HE Da-ke

Authenticated Group Key Agreement(AGKA) protocol allows a group of users in a public network to share a session key which may be used to achieve desirable secure communication.The protocol compiler proposed by Abdalla et al transforms any provably secure authenticated 2-party key establishment into a provably secure AGKE with two more rounds of communication.This paper points out an impersonation attack against the protocol compiler that two malicious users can impersonate an entity to agree some session keys in a new group if these two malicious users have the previous commitment transcripts of the entity.The improvement to eliminate the security leaks is proposed.

Jisuanji gongchengJan 1, 20090 citations

Scalable Protocols for Authenticated Group Key Exchange.

Jonathan I. Katz, Moti M. Yung

We consider the problem of authenticated group key exchange among n parties communicating over an insecure public network. A number of solutions to this problem have been proposed; however, all prior provably-secure solutions do not scale well and, in particular, require O (n) rounds. Our main contribution is the first scalable protocol for this problem along with a rigorous proof of security in the standard model under the DDH assumption; our protocol uses a constant number of rounds and requires only O (1) \full modular exponentiations per user. Toward this goal (and adapting work of Bellare, Canetti, and Krawczyk), we first present an efficient compiler that transforms any ngroup key-exchange protocol secure against a passive eavesdropper to an authenticated protocol which is secure against an active adversary who controls all communication in the network. This compiler adds only one round and O (1) communication (per user) to the original scheme. We then prove secure | against a passive adversary | a variant of the two-round group key-exchange protocol of Burmester and Desmedt. Applying our compiler to this protocol results in a provably-secure three-round protocol for authenticated group key exchange which also achieves forward secrecy.

Jan 1, 20037 citations

Authentication in Key-Exchange: Definitions, Relations and Composition

Cyprien Delpech de Saint Guilhem, Marc Fischlin, Bogdan Warinschi

We present a systematic approach to define and study authentication notions in authenticated key-exchange protocols. We propose and use a flexible and expressive predicate-based definitional framework. Our definitions capture key and entity authentication, in both implicit and explicit variants, as well as key and entity confirmation, for authenticated key-exchange protocols. In particular, we capture critical notions in the authentication space such as key-compromise impersonation resistance and security against unknown key-share attacks. We first discuss these definitions within the Bellare-Rogaway model and then extend them to Canetti-Krawczyk-style models. We then show two useful applications of our framework. First, we look at the authentication guarantees of three representative protocols to draw several useful lessons for protocol design. The core technical contribution of this paper is then to formally establish that composition of secure implicitly authenticated key-exchange with subsequent confirmation protocols yields explicit authentication guarantees. Without a formal separation of implicit and explicit authentication from secrecy, a proof of this folklore result could not have been established.

IEEE Computer Security Foundations Workshop (CSFW)Jun 1, 202032 citations