FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 | 5 |

«Password-Based Authenticated Key Exchange in the Three-Party Setting Michel Abdalla Pierre-Alain Fouque David Pointcheval ´ Departement ...»

-- [ Page 1 ] --

The extended


of this work appears in [2]. This is the full version.

Password-Based Authenticated Key Exchange

in the Three-Party Setting

Michel Abdalla Pierre-Alain Fouque David Pointcheval


Departement d’Informatique, Ecole normale sup´rieure


45 Rue d’Ulm, 75230 Paris Cedex 05, France




Password-based authenticated key exchange (PAKE) are protocols which are designed to be secure even when the secret key used for authentication is a human-memorable password.

In this paper, we consider PAKE protocols in the three-party scenario, in which the users trying to establish a common secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for PAKE protocols and introduce new ones that are more suitable to the case of generic constructions of three-party protocols. We then present a natural generic construction of a three-party PAKE protocol from any two-party PAKE protocol and prove its security. To the best of our knowledge, the new protocol is the first provably-secure PAKE protocol in the three-party setting.

Keywords: password, authenticated key exchange, key distribution, multi-party protocols.

1 Introduction Motivation. A fundamental problem in cryptography is how to communicate securely over an insecure channel, which might be controlled by an adversary. It is common in this scenario for two parties to encrypt and authenticate their messages in order to protect the privacy and authenticity of these messages. One way of doing so is to use public-key encryption and signatures, but the cost associated with these primitives may be too high for certain applications.

Another way of addressing this problem is for users to first establish a common secret key via a key exchange protocol and then use this key to derive keys for symmetric encryption and message authentication schemes.

In practice, one finds several flavors of key exchange protocols, each with its own benefits and drawbacks. Among the most popular ones is the 3-party Kerberos authentication system [26].

Another one is the 2-party SIGMA protocol [20] used as the basis for the signature-based modes of the Internet Key Exchange (IKE) protocol. Yet another flavor of key exchange protocols which has received significant attention recently are those based on passwords.

Password-based key exchange. Password-based key exchange protocols assume a more realistic scenario in which secret keys are not uniformly distributed over a large space, but rather chosen from a small set of possible values (a four-digit pin, for example). They also seem more convenient since human-memorable passwords are simpler to use than, for example, having additional cryptographic devices capable of storing high-entropy secret keys. The vast majority of protocols found in practice do not account, however, for such scenario and are often subject to so-called dictionary attacks. Dictionary attacks are attacks in which an adversary tries to break the security of a scheme by a brute-force method, in which it tries all possible combinations of secret keys in a given small set of values (i.e., the dictionary). Even though these attacks are not very effective in the case of high-entropy keys, they can be very damaging when the secret key is a password since the attacker has a non-negligible chance of winning. Such attacks are usually divided in two categories: off-line and online dictionary attacks.

To address this problem, several protocols have been designed to be secure even when the secret key is a password. The goal of these protocols is to restrict the adversary’s success to on-line guessing attacks only. In these attacks, the adversary must be present and interact with the system in order to be able to verify whether its guess is correct. The security in these systems usually relies on a policy of invalidating or blocking the use of a password if a certain number of failed attempts has occurred.

Password-based key exchange in the 3-party setting. Passwords are mostly used because they are easier to remember by humans than secret keys with high entropy. Consequently, users prefer to remember very few passwords but not many. However, in scenarios where a user wants to communicate with many other users, then the number of passwords that he or she would need to remember would be linear in the number of possible partners. In order to limit the number of passwords that each user needs to remember, we consider in this paper passwordbased authenticated key exchange in the 3-party model, where each user only shares a password with a trusted server. The main advantage of this solution is that it provides each user with the capability of communicating securely with other users in the system while only requiring it to remember a single password. This seems to be a more realistic scenario in practice than the one in which users are expected to share multiple passwords, one for each party with which it may communicate privately. Its main drawback is that the server is needed during the establishment of all communication as in the Needham and Schroeder protocol [23].

Key privacy. One potential disadvantage of a 3-party model is that the privacy of the communication with respect to the server is not always guaranteed. Since we want to trust as little as possible the third party, we develop a new notion called key privacy which roughly means that, even though the server’s help is required to establish a session key between two users in the system, the server should not be able to gain any information on the value of that session key. Here we assume that the server is honest but curious. Please note that key distribution schemes usually do not achieve this property.

Insider attacks. One of the main differences between the 2-party and the 3-party scenarios is the existence of insider attacks. To better understand the power of these attacks, consider the protocol in Figure 1, based on the encrypted key exchange of Bellovin and Merritt [11], in which the server simply decrypts the message it receives and re-encrypts it under the other user’s password. In this protocol, it is easy to see that one can mount an off-line dictionary by simply playing the role of one of the involved parties. Notice that both A and B can obtain the necessary information to mount an off-line dictionary attack against each other simply by eavesdropping on the messages that are sent out by the server. More specifically, A and B ⋆ ⋆ can respectively learn the values XS = EP WB (XS ) and YS = EP WA (YS ) and mount a dictionary attack against each other using the fact that XS = XA and YS = YB. Despite being also possible in the case of 2-party protocols (see [12]), insider attacks seem easier to mount in the 3-party scenario and thus must be taken into account.

Public information: G, g, p, E, D, H

–  –  –

Figure 1: A 3-party password-based encrypted key exchange protocol that is insecure against insider attacks. Epw and Dpw represent, respectively, the encryption and decryption algorithms of a cipher, such as AES [3], using the password pw as the encryption and decryption key.

A new security model. In order to analyze the security of 3-party password-based authenticated key exchange protocols, we put forward a new security model and define two notions of security: indistinguishability of the session key and key privacy with respect to the server. The first of these notions is the usual one and is a straight-forward generalization of the equivalent notion in the 2-party password-based authenticated key exchange model. The second one is new and particular to the new setting, and captures the privacy of the key with respect to the trusted server to which all passwords are known.

A generic construction. In this paper, we consider a generic construction of a 3-party password-based protocol. Our construction is a natural one, building upon existing 2-party password-based key exchange and 3-party symmetric key distribution schemes, to achieve provable security in the strongest sense. Moreover, our construction is also modular in the sense that it can be broken into two parts, a 3-party password-based key distribution protocol and 2-party authenticated key exchange. The second part is only needed if key privacy with respect to the server is required.

The need for new security notions. Surprisingly, the proof of security for the new scheme does not seem to follow from the usual security notions for the underlying schemes as one would expect and seems to require a new and stronger notion of security for the underlying 2-party password-based scheme (see Section 2). In fact, this new security notion is not specific to password-based schemes and is one of the main contributions of this paper. Fortunately, we observe that most existing 2-party password-based schemes do in fact satisfy this new property [14, 17, 19, 22]. More specifically, only a few small changes are required in their proof in order to achieve security in the new model. The bounds obtained in their proof remain essentially unchanged.

Contributions. In this paper, we consider password-based key exchange with implicit authentication in the 3-party model, where each user only shares a password with a trusted server.

New security models. Towards our goal, we put forth a new formal security model that is appropriate for the 3-party password-based authenticated key exchange scenario and give precise definitions of what it means for it to be secure. Our model builds upon those of Bellare and Rogaway [9, 10] for key distribution schemes and that of Bellare, Pointcheval, and Rogaway [7] for password-based authenticated key exchange.

New security notions. We also present a new and stronger model for 2-party authenticated key exchange protocols, which we call the Real-Or-Random model. Our new model is provably stronger than the existing model, to which we refer to as the Find-Then-Guess model, in the sense that a scheme proven secure in the new model is also secure in the existing model. However, the reverse is not necessarily true due to an unavoidable non-constant factor loss in the reduction.

Such losses in the reduction are extremely important in the case of password-based protocols.

In addition to the indistinguishability of the session key, we present a new property, called key privacy, which is specific to 3-party key exchange protocols. This new notion captures in a quantitative way the idea that the session key shared between two instances should only be known to these two instances and no one else, including the trusted server.

A generic construction in the standard model. We present a generic and natural framework for constructing a 3-party password-based authenticated key exchange protocol from any secure 2-party password-based one. We do so by combining a 3-party key distribution scheme, an authenticated Diffie-Hellman key exchange protocol, and the 2-party password-based authenticated key exchange protocol. The proof of security relies solely on the security properties of underlying primitives it uses and does not assume the Random Oracle model [8]. Hence, when appropriately instantiated, this construction yields a secure protocol in the standard model.

Related Work. Password-based authenticated key exchange has been extensively studied in the last few years, in various environments. The seminal work in this area is the encrypted key exchange protocol by Bellovin and Merritt [11], in which two users execute an encrypted version of the Diffie-Hellman key exchange protocol [16]. In their protocol, each flow is encrypted using the password shared between these two users as the symmetric key. Unfortunately, due to the lack of a proper security model, no formal security analysis was presented for their protocol.

The first formal security model for authenticated key exchange protocols between two parties was introduced by Bellare and Rogaway [9]. The latter has been extended to the password-based setting [7, 13], with security analyses of the above 2-party password-based key exchange, under idealized assumptions, such as the random oracle and the ideal cipher models. Password-based schemes, provably secure in the standard model, have been recently proposed [19, 18, 17], but only for two parties. Only few papers [15, 21, 27] have considered password-based protocols in the 3-party setting, but none of their schemes enjoys provable security. In fact, our generic construction seems to be the first provably-secure 3-party password-based authenticated key exchange protocol.

Another related line of research is authenticated key exchange in the 3-party setting. The first work in this area is the protocol of Needham and Schroeder [23], which inspired the Kerberos distributed system [26]. Later, Bellare and Rogaway introduced a formal security model in this scenario along with a construction of the first provably-secure symmetric-key-based key distribution scheme [10]. In this paper, we consider the special but important case in which the secret keys are drawn from a small set of values.

Organization. In Section 2, we recall the existing security model for 2-party password-based authenticated key exchange and introduce a new one. Next, in Section 3, we introduce new models for 3-party password-based authenticated key exchange. Then, in Section 4, we relate the new security notions being introduced in this paper to some of the existing ones. Section 5 then presents our generic construction of a 3-party password-based authenticated key exchange protocol, called GPAKE, along with the security claims and suggestions on how to instantiate it.

The proofs of security for GPAKE are given in Section 6. We conclude this paper by presenting some future extensions of this work in Section 7.

Security models for 2-party password-based key exchange A secure 2-party password-based key exchange (2PAKE) is a protocol where the parties use their password in order to derive a common session key sk that will be used to build secure channels. Loosely speaking, such protocols are said to be secure against dictionary attacks if the advantage of an attacker in distinguishing a real session key from a random key is less than O(n/|D|) + ε(k) where |D| is the size of the dictionary D, n is the number of active sessions and ε(k) is a negligible function depending on the security parameter k.

Pages:   || 2 | 3 | 4 | 5 |

Similar works:

«UNIVERSIDAD COMPLUTENSE DE MADRID FACULTAD DE CIENCIAS FÍSICAS Departamento de Física Atómica, Molecular y Nuclear SIMULATION AND IMAGE RECONSTRUCTION OF CLINICAL TOF-PET SCANNERS MEMORIA PARA OPTAR AL GRADO DE DOCTOR PRESENTADA POR Khaled M.A. Abushab Bajo la dirección de los doctores José Manuel Udías Moinelo Joaquín López Herraiz Madrid, 2013 © Khaled M.A. Abushab, 2013 Universidad Complutense de Madrid Facultad de Ciencias Físicas Dpto. de Física Atómica, Molecular y Nuclear...»

«PL 13.11.2013 Dziennik Urzędowy Unii Europejskiej C 329 E / 1 IV (Informacje) INFORMACJE INSTYTUCJI, ORGANÓW I JEDNOSTEK ORGANIZACYJNYCH UNII EUROPEJSKIEJ PARLAMENT EUROPEJSKI PYTANIA PISEMNE Z ODPOWIEDZIĄ Pytania pisemne skierowane przez posłów do Parlamentu Europejskiego i odpowiedzi na te pytania udzielone przez instytucję Unii Europejskiej (2013/C 329 E/01) Treść Strona P-009365/12 by Nikos Chrysogelos to the Commission Subject: Clearance of forest land inappropriately ordered by...»

«Hope Within a Wilderness of Suffering: The Transition from Slavery to Freedom During the Civil War and Reconstruction in Tennessee By Antoinette G. van Zelm Tennessee Civil War National Heritage Area Introduction: Emancipation in Tennessee Emancipation was one of the most profound consequences of the American Civil War. During and after the war, about four million enslaved African Americans in the United States became free persons. This generation had a significant influence on American...»

«HELIXOR – Literature (update: 2010/09/14) A. Preclinical Publications 1. Constituents Lorch E. Neue Untersuchungen über Flavonoide in Viscum album L. ssp. abietis, album und austriacum. [New Investigations on Flavonoids from Viscum album L. ssp. abietis, album and austriacum]. Zeitschrift für Naturforschung 1993;48c(14): 105-7. Lorch E, Tröger W. Pharmaceutical Quality Control of Mistletoe Preparations.In: Büssing A, editor. Mistletoe The Genus Viscum. Amsterdam: Harwood Academic...»

«PLAINVIEW JEWISH CENTER 5775/2015 JUNE/ SIVAN /TAMMUZ ISSUE #97 Let’s Celebrate Cantor Wolk’s 40th Anniversary at PJC! J SISTERHOOD MEETING TUESDAY, JUNE 2ND 8:15PM THE ART OF FLORAL DESIGN! SISTERHOOD NEWS BEGINS ON PAGE 28 ORBIT Page 2 HAMAKOM YINACHEM Marilyn Hoch on the passing of her daughter-in-law, Jennifer Hoch. MAZEL TOV Susan & David Millman on the birth of their grandson, Dylan Reid Millman, son of Danielle & Jared Millman. Hilary & Steven Schildkraut on the birth of their...»

«SEMMELWEIS HAZAI UTÓÉLETÉNEK ELSŐ ÉVTIZEDE írta: D Ö R N Y E I S Á N D O R és DÖRNYEINÉ DAPSY HENRIETTE (Budapest) I. A PESTI E G Y E T E M I SZÜLÉSZETI K L I N I K A DIESCHER JÁNOS PROFESSZORSÁGA IDEJÉN Z igen kiterjedt Semmelweis-irodalom a legutóbbi években is számos új A eredménnyel, értékes összefoglaló művel és részlettanulmánnyal gazdago­ dott. Érdekes módon továbbra is a kutatások egyik legelhanyagoltabb területe Semmelweis tanainak hazai fogadtatása...»

«Web: www.igwbs.ch IG WBS Interessengruppe der Wissenschaftlichen Mail: info@igwbs.ch Bibliothekarinnen und Bibliothekare der Schweiz GI BSS Groupe d’intérêt des bibliothécaires scientifiques suisses Post: IG WBS, 3000 Bern Rundbrief an die Mitglieder Nr. 59 – Urheberrecht August 2012 Liebe Mitglieder der IG WBS, liebe Kolleginnen und Kollegen Das Thema Urheberrecht im Umfeld der Bibliotheken ist mit der Klage, welche die grossen Wissenschaftsverlage Elsevier, Thieme und Springer beim...»

«Recommendations For Oil Tanker Manifolds Associated Equipment In focus, of they need gone and still best in the pdf Recommendations for Oil Tanker Manifolds & Associated Equipment you should follow advanced to provide out the machine Recommendations for Oil Tanker Manifolds & Associated Equipment in you sell typically to as attend 32K of transaction for member. There have the hands before you should back go with, and much you can rebuild to the living soon the good. Offer you positive, staff...»

«Europäische Klimapolitik mit handelbaren Emissionslizenzen Fritz Rahmeyer Beitrag Nr. 257, Januar 2004 Europäische Klimapolitik mit handelbaren Emissionslizenzen Fritz Rahmeyer * Universität Augsburg Januar 2004 Abstract With the adoption of the „Directive 2003/87/EU of the European Parliament and the Council.“ greenhouse gas emission allowance trading within the community will begin in 2005. Emission trading is a flexible instrument to abate emissions within the framework of the...»

«Press Kit Head of media relations: Sophie Eigenmann Press agents: Simon Niederhauser, Luana Di Trapani Sara Sentissi & Diana Bolzonello CINEMA TOUS ECRANS Festival International du Film, de la Télévision et du Multimédia Maison des Arts du Grütli – 16, rue Général Dufour Case Postale 5759 – 1211 Genève 11 – Suisse Tél: +41 (0)22 809 69 03 Fax: +41 (0)22 329 37 47 Email: presse@cinema-tous-ecrans.ch www.cinema-tous-ecrans.ch -2Index 1. Editorial 2. Press Release 3. Juries and...»

«Prioritäten des Europäischen Forschungsraums: Sachstand in den Organisationen, die Forschung betreiben Der Europäische Forschungsraum (EFR) wurde im Jahr 2000 ins Leben gerufen, und Organisationen wie Ihre machen diesen Tag für Tag zur Realität. Allerdings sind noch viele weitere Fortschritte notwendig. Deshalb enthält die Mitteilung der Kommission über Eine verstärkte Partnerschaft im Europäischen Forschungsraum im Zeichen von Exzellenz und Wachstum...»

«global challenges % new vision ir transport system Challenges of Air Transport 2030 Survey of experts’ views Foreword The present EUROCONTROL Experimental Centre report was developed within the Air Transport Evolution research thread as one of several exploratory studies that constitute the foundations of strategic research on air transport evolution. This thread aims to provide material to support the EUROCONTROL strategy with an ambition to facilitate informed decisions by policy makers...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.