ID2S Password Authenticated key Exchange Protocol

Abstract

Introduction

TO secure communications between two parties, an authenticated encryption key is required to agree on in advance. So far, two models have existed for authenticated key exchange. One model assumes that two parties already share some cryptographically-strong information: either a secret key which can be used for encryption/authentication of messages, or a public key which can be used for encryption/signing ofmessages. These keysare random and hard to remember. In practice, a user often keeps his keys in a personal device protected by a password/PIN. Another model assumes that users,without helpofpersonal devices,areonly capableofstoring“human-memorable”passwords. Bellovin and Merritt [4] were the first to introduce password-based authenticated key exchange (PAKE), where two parties, based only on their knowledge of a password, establish a cryptographic key by exchange of messages. A PAKE protocol has to be immune to on-line and off-line dictionary attacks. In an off-line dictionary attack, an adversary exhaustively tries all possible passwords in a dictionary in order to determine the password of the client on the basis of the exchanged messages.

In an on-line dictionary attack, an adversary simply attempts to login repeatedly, trying each possible password. By cryptographic means only, none of PAKE protocols can prevent on-line dictionary attacks. But on-line attacks can be stopped simply by setting a threshold to the number of login failures. Since Bellovin and Merritt [4] introduced the idea of PAKE, numerous PAKE protocols have been proposed. In general, there exist two kinds of PAKE settings, one assumes that the password of the client is stored in a single server and another assumes that the password of the client is distributed in multiple servers. PAKE protocols in the single-server setting can be classified into three categories as follows. Password-only PAKE: Typical examples are the “encrypted key exchange” (EKE) protocols given by Bellovin and Merritt [4], where two parties, who share a password, exchange messages encrypted by the password, and establish a common secret key. The formal model of security for PAKE was firstly given . Based on the security model, PAKE protocols have been proposed and proved to be secure. PKI-based PAKE: PKI-based PAKE protocol was first given by Gong et al. [17], where the client stores the server’s public key in addition to share a password with the server. Halevi and Krawczyk[18]were the first to provide form a ldefinitions and rigorous proofs of security for PKI-basedPAKE. ID-based PAKE: ID-based PAKE protocols were proposed by Yi et al.

where the client needs to remember a password in addition to the identity of the server, whereas the server keeps the password in addition to a private key related to its identity. ID-based PAKE can be thought as a trade-off between password-only and PKI-based PAKE. In the single-server setting, all the passwords necessary to authenticate clients are stored in a single server. If the server is compromised, due to, for example, hacking or even insider attacks, passwords stored in the server are all disclosed. This is also true to Kerberos [12], where a user authenticates against the authentication server with his username and password and obtains a token to authenticate against the service server.

To address this problem,the multi-server setting for PAKE was first suggested ,where the password of the client is distributed in n servers. PAKE protocols in the multi server setting can be classified into two categories as follows. Threshold PAKE: The first PKI-based threshold PAKE protocol was given by Ford and Kaliski [15], where n servers, sharing the password of the client, cooperate to authenticate the client and establish independent session keys with the client. As long as n1 or fewer servers are compromised, their protocol remains secure. Jablon [19] gave a protocol with similar functionality in the password-only setting. MacKenzie et al. proposed a PKI-based threshold PAKE protocol which requires only t out of n servers to cooperate in order to authenticate the client. Their protocol remains secure as long as t1 or fewer servers are compromised. Di Raimondo and Gennaro [26] suggested a password-only threshold PAKE protocol which requires fewer than 1/3 of the servers to be compromised. Two-server PAKE: Two-server PKI-based PAKE was first given by Brainard [9], where two servers cooperate to authenticate the client and the password remains secure if one server is compromised. A variant of the protocol was later proved to be secure . A two-server passwordonly PAKE protocol was given by Katz et al. , in which two servers symmetrically contribute to the authentication of the client. The protocol in the server side can run in parallel. Efficient protocolswere later proposed, where the front-end server authenticates the client with the help of the back-end server and only the front-end server establishes a session key with the client. These protocols are asymmetric in the server side and have to run in sequence. Yi et al. gave a symmetric solution [34] which is even more efficient than asymmetric protocols.

Recently, Yi et al. constructed an ID2S PAKE protocol with the identity-based encryption scheme (IBE) [35]. In this paper, we will consider the two-server setting for PAKE only. In two-server PAKE, a client splits its password and stores two shares of its password in the two servers, respectively, and the two servers then cooperate to authenticate the client without knowing the password of the client. Even if one server is compromised, the attacker is still unable topretendanyclienttoauthenticateagainstanotherserver. A typical example is the two-server PAKE protocol given by Katz et al. [23], which is built upon the two-party PAKE protocol (i.e.,the KOYprotocol [22]),wheretwo parties,who share a password, exchange messages to establish a common secret key. Their basic two-server protocol is secure against a passive (i.e., “honest-but-curious”) adversary who has access to one of the servers throughout the protocol execution, but cannot cause this server to deviate from its prescribed behavior. In [23], Katz et al. also showed how to modify their basic protocol so as to achieve security against an active adversary who may cause a corrupted server to deviate arbitrarily from the protocol.

The core of their protocol is the KOY protocol. The client looks like running two KOY protocols with two servers in parallel. However, eachserver must perform a total of roughly 80 exponentiations (i.e.,each server’swork is increased by a factor of roughly six as compared to the basic protocol[23]) . In [35], a security model for ID2S PAKE protocol was given and a compiler that transforms any two-party PAKE protocol to an ID2S PAKE protocol was proposed on the basis of the Cramer-Shoup public key encryption scheme [13] and any identity-based encryption scheme, such as the Waters’ scheme [28]. Our contribution. In this paper, we propose a new compiler for ID2S PAKE protocol based on any identity-based signature scheme (IBS), such as the Paterson et al.’s scheme [25]. The basic idea is: The client splits its password into two shares and each server keeps one share of the password in addition to a private key related to its identity for signing. In key exchange, each server sends the client its public key for encryption with its identity-based signature on it. The signature can be verified by the client on the basis of the identity of the server. If the signature is genuine, the client submits to the server one share of the password encrypted with the public key of the server. With the decryption keys, both servers can derive the same one-time password, by which the two servers can run a two-party PAKE protocol to authenticate the client.

In addition, we generalize the compiler based on IBE in [35] by replacing the Cramer-Shoup public key encryption scheme with any public key encryption scheme. Unlike the compiler based on IBS, the compiler based on IBE assumes that each server has a private key related to its identity for decryption. In key exchange, the client sends to each server oneshareofthepasswordencryptedaccordingtotheidentity of the server. In addition, a one-time public key encryption scheme is used to protect the messages (containing the password information)from the servers to the client.Theone-time public key is generated by the client and sent to the servers along with the password information in the first phase. In the identity-based cryptography, the decryption key or the signing key of a server is usually generated by a Private Key Generator (PKG). Therefore the PKG can decrypt any messages encrypted with the identity of the server or sign any document on behalf of the server. As mentioned in [7], using standard techniques from threshold cryptography, the PKG can be distributed so that the master-key is never available in a single location. Like [35], our strategy is to employ multiple PKGs which cooperate to generate the decryption key or the signing key for the server. As long as one of the PKGs is honest to follow the protocol, the decryption key or the signing key for the server is known only to the server. Since we can assume that the two servers in twoserver PAKE never collude, we can also assume that at least one of the PKGs do not collude with other PKGs. Based on this assumption, we provide a rigorous proof of security for our compilers.

The two compilers do not rely on the random oracle model as long as the underlying primitives themselves do not rely on it. For example, by using the KOY protocol  and the Paterson et al.’s IBS scheme  and the Cramer-Shoup public key encryption scheme , the compiler based on IBS can construct an ID2S PAKE protocol with provable security in the standard model. By using the KOY protocol  and the Waters IBE scheme  and the Cramer-Shoup public key encryption scheme, the compiler based on IBE can construct an ID2S PAKE protocol with provable security in the standard model. We also compare our ID2S PAKE protocols with the Katz et al.’s two-server PAKE protocol [23] with provable security in the standard model. The Katz et al.’s protocol is password-only, where the client needs to remember the password only and refer to common public parameters, and each server, having a public and private key pair, and keeps a share of the password.

Our protocols are identity-based, where the client needs to remember the password in addition to the meaningful identities of the two servers, and refer to common public parameters, including the master public key, and each server, having a private key related to his identity, keeps a share of the password. In terms of the setting and the client performance, the Katz et al.’s protocol is superior to our protocols. However, in the Katz et al.’s protocol, each server performs approximately six times the amount of the work as the KOY protocol, whereas in our protocols, each server performs the same amount of work as the KOY protocol in addition to one identity-based decryption (or signature) and one public key encryption (or decryption). We have implemented our ID2S PAKE protocols. Our experiments show that our protocols save from 22 to 66 percent of computation in each server, compared with the Katz et al.’s protocol. The server performance is critical to the performance of the whole protocol when the servers provide services to a great number of clients concurrently. In addition, our experiments show that less than one second is needed for the client to execute our protocols.

Conclusion

In this ID2S Password-Authenticated Key Exchange Protocol paper, we present two efficient compilers to transform any two-party PAKE protocol to an ID2S PAKE protocol with identity-based cryptography. In addition, we have provided a rigorous proof of security for our compilers without random oracle. Our compilers are in particular suitable for the applications of password-based authentication where an identity-based system has already been established. Our future work is to construct an identity-based multiple-server PAKE protocol with any twoparty PAKE protocol.