«Password-Based Authenticated Key Exchange in the Three-Party Setting Michel Abdalla Pierre-Alain Fouque David Pointcheval ´ Departement ...»
of this work appears in . 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 ﬁrst 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 ﬁrst 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 ﬁnds several ﬂavors of key exchange protocols, each with its own beneﬁts and drawbacks. Among the most popular ones is the 3-party Kerberos authentication system .
Another one is the 2-party SIGMA protocol  used as the basis for the signature-based modes of the Internet Key Exchange (IKE) protocol. Yet another ﬂavor of key exchange protocols which has received signiﬁcant 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 eﬀective 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: oﬀ-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 .
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 diﬀerences 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 , 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 oﬀ-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 oﬀ-line dictionary attack against each other simply by eavesdropping on the messages that are sent out by the server. More speciﬁcally, 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 ), 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 , 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 deﬁne two notions of security: indistinguishability of the session key and key privacy with respect to the server. The ﬁrst 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 speciﬁc 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 speciﬁcally, 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 deﬁnitions 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  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 speciﬁc 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 Diﬃe-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 . 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 , in which two users execute an encrypted version of the Diﬃe-Hellman key exchange protocol . In their protocol, each ﬂow 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 ﬁrst formal security model for authenticated key exchange protocols between two parties was introduced by Bellare and Rogaway . 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 ﬁrst 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 ﬁrst work in this area is the protocol of Needham and Schroeder , which inspired the Kerberos distributed system . Later, Bellare and Rogaway introduced a formal security model in this scenario along with a construction of the ﬁrst provably-secure symmetric-key-based key distribution scheme . 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.