Mitigating Server Breaches in Password-Based Authentication: Secure and Efficient Solutions

Abstract

Password-Authenticated Key Exchange allows users to generate a strong cryptographic key based on a shared “human-memorable” password without requiring a public-key infrastructure. It is one of the most widely used and fundamental cryptographic primitives. Unfortunately, mass password theft from organizations is continually in the news and, even if passwords are salted and hashed, brute force breaking of password hashing is usually very successful in practice.

In this paper, we propose two efficient protocols where the password database is somehow shared among two servers (or more), and authentication requires a distributed computation involving the client and the servers. In this scenario, even if a server compromise is doable, the secret exposure is not valuable to the adversary since it reveals only a share of the password database and does not permit to brute force guess a password without further interactions with the parties for each guess. Our protocols rely on smooth projective hash functions and are proven secure under classical assumption in the standard model (i.e. do not require idealized assumption, such as random oracles).

1 Introduction

Authenticated Key Exchange protocols enable two parties to establish a shared cryptographically strong key over an insecure network under the complete control of an adversary. This primitive is one of the most widely used and fundamental cryptographic primitives and it obviously requires the parties to have authentication means, e.g. (public or secret) cryptographic keys or short (i.e., low-entropy) secret keys.

PAKE, for Password-Authenticated Key Exchange, allows users to generate a strong cryptographic key based on a shared “human-memorable” password without requiring a public-key infrastructure. In this setting, an adversary controlling all communication in the network should not be able to mount an offline dictionary attack. More precisely, an eavesdropper should not obtain enough information to be able to brute force guess a password without further interactions with the parties for each guess. Note that online dictionary attacks in which an adversary simply attempts to log-in repeatedly, trying each possible low-entropy password can be dealt with using other computer security methods (such as limiting the number of attempts). In particular, strong security can be obtained even using passwords chosen from a small set of possible values (a four-digit pin, for example).

Incidents of sensitive customer information “hacking” (including leaking of passwords) in e-commerce systems are frequently revealed in the newspaper. In addition to major reputational damage, a company with a significant data breach may be sued by its clients for the breach and may be suspended or disqualified from future public sector or government work.

To alleviate the threat that stored passwords are revealed immediately in case of a server compromise, many servers adopt the approach for storing passwords in a hashed form with a random salt. When the database of hashed password is compromised, the offline dictionary attack requires a more important computational effort but remains usually possible. The notion of Verifier-based PAKE, where the client owns a password ${ \textsf {pw}}$ and the server knows a one-way transformation v of the password only were proposed by Bellovin and Merritt [BM92]. The two players eventually agree on a common high entropy secret if and only if ${ \textsf {pw}}$ and v match together. It prevents massive password recovering in case of server corruption and it forces the attacker who breaks into the server and is willing to recover passwords to perform an additional costly offline dictionary attack.

We consider an alternative approach inspired by the multi-party computation paradigm (and first suggested by Ford and Kaliski [FK00]). The password database on the server side is somehow shared among two servers (or more, but we focus here on two for sake of simplicity), and authentication requires a distributed computation involving the client – who still does not need an additional cryptographic device capable of storing high-entropy secret keys – and the two servers who will use some additional shared secret information. The interaction is performed using a gateway that does not know any secret information and ends up in the gateway and the client sharing a common key. The lifetime of the protocol is divided into distinct periods (for simplicity, one may think of these time periods as being of equal length; e.g. one day) and at the beginning of each period, the two servers interact and update their sharing of the password database. Similarly to proactive schemes in multi-party computation, we allow the adversary multiple corruptions of each server, limiting only the corruptions to one server for each period. The user does not need to update his password nor to perform any kind of computations and its interaction with the two servers (performed using the gateway) remains the same for the lifetime of the protocol. In this scenario, even if a server compromise is doable, the secret exposure is not valuable to the adversary since it reveals only a share of the password database and does not permit to run an offline dictionary attack.

The goal of our paper is to present practical realizations based on classical cryptographic assumptions in the standard security model.

Related Work. EKE (Encrypted Key Exchange) is the most famous instantiation of Password-Authenticated Key Exchange. It has been proposed by Bellovin and Merritt [BM92] and consists of a Diffie-Hellman key exchange [DH76], where the flows are symmetrically encrypted under the shared password.

A first formal security model was proposed by Bellare, Pointcheval and Rogaway [BPR00] (the BPR model), to deal with offline dictionary attacks. It essentially says that the best attack should be the online exhaustive search, consisting in trying all the passwords by successive executions of the protocol with the server. Several variants of EKE with BPR-security proofs have been proposed in the ideal-cipher model or the random-oracle model (see the survey [Poi12] for details). Katz, Ostrovsky and Yung [KOY01] proposed the first practical scheme, provably secure in the standard model under the Decision Diffie-Hellman assumption ($\textsf {DDH}$). It has been generalized by Gennaro and Lindell [GL03], making use of smooth projective hash functions.

As mentioned above, Ford and Kaliski [FK00] were the first to propose to distribute the capability to test passwords over multiple servers. Building on this approach, several such protocols were subsequently proposed in various settings (e.g. [Jab01, MSJ02, BJKS03, DG06, SK05, KMTG12, ACFP05, KM14]) and it is worth noting that the protocol from [BJKS03] is commercially available as EMC’s RSA Distributed Credential Protection. Recently, Camenisch, Enderlein and Neven [CEN15] revisited this approach and proposed a scheme in the universal composability framework [Can01] (which has obvious advantages for password-based protocols since users often use related passwords for many providers). Camenisch et al. gave interesting details about the steps that need to be taken when a compromise actually occurs. Unfortunately, due to the inherent difficulties of construction of the simulator in the universal composability framework, their scheme is inefficient since users and servers have to perform a few hundred exponentiations each.

Our Contributions. In order to achieve practical constructions in the standard security model, we consider the variant of the BPR model¹ in the distributed setting proposed by Katz, MacKenzie, Taban and Gligor in [KMTG12]. In this security model, we assume that the communication between the client and the authentication servers, is carried on a basically insecure network. Messages can be tapped and modified by an adversary and the communication between the clients and the servers is asynchronous. The adversary should not be able to brute force guess a password without further interactions with the client for each guess even if he corrupts and impersonates a server in an active way.

Our first construction uses a similar approach to the schemes from [Jab01, MSJ02, BJKS03, DG06, SK05, KMTG12, ACFP05, KM14]: the user generates information theoretic shares of his password and sends them to the servers. In the authentication phase, the parties run a dedicated protocol to verify that the provided password equals the priorly shared one. Our solution then consists in some sort of three-party $\textsf {PAKE}$, in which (1) the user implicitly checks (using a smooth projective hash function) that its password is indeed the sum of the shares owned by the two servers, and (2) each server implicitly checks that its share is the difference of the password owned by the user and the share owned by the other server. Contrary to the popular approach initiated in [KOY01, GL03] for $\textsf {PAKE}$, we cannot use two smooth projective hash functions (one for the client and one for the server) so we propose a technique in order to combine in a secure way six smooth projective hash functions. This new method (which may be of independent interest) allows us to prove the security of this construction under classical cryptographic assumptions (namely the $\textsf {DDH}$ assumption) in the standard security model from [KMTG12] (without any idealized assumptions).

The main weakness of this first solution is that at each time period, the servers have to refresh the information-theoretic sharing of the password of all users. This can be handled easily using well-known techniques from proactive multi-party computation but if the number of users is large, this can be really time-consuming (in particular if the time period is very short). Our second construction (which is the main contribution of the paper) is built on the ideas from the first one but passwords are now encrypted using a public-key encryption scheme where the corresponding secret key is shared among the servers. At the beginning of each time period, the servers only need to refresh the sharing of this secret key but the password database is not modified (and can actually be public). Password verification and the authenticated key exchange is then carried out without ever decrypting the database. A secure protocol is run to verify that the password sent by the user matches the encrypted password. It is similar to the protocol we design for the first construction except that the user encrypts its password and the parties implicitly check (using in this case five smooth projective hash functions) that the message encrypted in this ciphertext is the same as the message encrypted in the database (using the secret key shared upon the servers). Both constructions consist in only two flows (one from the client and one from the servers) and a (private) flow from the servers to the gateway.

2 Preliminaries

In this section we recall various classical definitions, tools used throughout this paper. We use classical notions and notations and the familiar reader may skip this section.

Public-Key Encryption Scheme. An encryption scheme $\mathcal {E}$ is described by four algorithms $( \textsf {Setup}, \textsf {KeyGen}, \textsf {Encrypt}, \textsf {Decrypt})$:

• $\textsf {Setup}(1^\mathfrak {K})$, where $\mathfrak {K}$ is the security parameter, generates the global parameters $\textsf {param}$ of the scheme;

• $\textsf {KeyGen}( \textsf {param})$ outputs a pair of keys, a (public) encryption key $\textsf {ek}$ and a (private) decryption key $\textsf {dk}$;

• $\textsf {Encrypt}(\textsf {ek},M;\rho )$ outputs a ciphertext $\mathcal {C}$, on the message M, under the encryption key $\textsf {ek}$, with randomness $\rho$;

• $\textsf {Decrypt}(\textsf {dk},\mathcal {C})$ outputs the plaintext M, encrypted in the ciphertext $\mathcal {C}$ or $\bot$.

Such encryption scheme is required to have the classical properties, Correctness and Indistinguishability under Chosen Plaintext Attack $\textsf {IND\text {-}CPA}$ [GM84]: One might want to increase the requirements on the security of an encryption, in this case the $\textsf {IND\text {-}CPA}$ notion can be strengthened into Indistinguishability under Adaptive Chosen Ciphertext Attack $\textsf {IND\text {-}CCA}$ (see the full version [BCV16] for formal definitions).

Smooth Projective Hash Functions. SPHF [CS02] were introduced by Cramer and Shoup. A projective hashing family is a family of hash functions that can be evaluated in two ways: using the (secret) hashing key, one can compute the function on every point in its domain, whereas using the (public) projected key one can only compute the function on a special subset of its domain. Such a family is deemed smooth if the value of the hash function on any point outside the special subset is independent of the projected key.

Smooth Projective Hashing System: A Smooth Projective Hash Function over a language $\mathcal {L}\subset X$, onto a set $\mathbb {G}$, is defined by five algorithms $( \textsf {Setup}, \textsf {HashKG}, \textsf {ProjKG}, \textsf {Hash}, \textsf {ProjHash})$:

• $\textsf {Setup}(1^\mathfrak {K})$ where $\mathfrak {K}$ is the security parameter, generates the global parameters $\textsf {param}$ of the scheme, and the description of an $\mathcal {NP}$ language $\mathcal {L}$;

• $\textsf {HashKG}(\mathcal {L}, \textsf {param})$, outputs a hashing key $\textsf {hk}$ for the language $\mathcal {L}$;

• $\textsf {ProjKG}(\textsf {hk},(\mathcal {L}, \textsf {param}),W)$, derives the projection key $\textsf {hp}$, possibly depending on the word W [GL03, ACP09] thanks to the hashing key $\textsf {hk}$.

• $\textsf {Hash}(\textsf {hk},(\mathcal {L}, \textsf {param}),W)$, outputs a hash value $v\in \mathbb {G}$, thanks to the hashing key $\textsf {hk}$, and W

• $\textsf {ProjHash}(\textsf {hp},(\mathcal {L}, \textsf {param}),W,w)$, outputs the hash value $v' \in \mathbb {G}$, thanks to the projection key $\textsf {hp}$ and the witness w that $W \in \mathcal {L}$.

In the following, we consider $\mathcal {L}$ as a hard-partitioned subset of X, i.e. it is computationally hard to distinguish a random element in $\mathcal {L}$ from a random element in $X \setminus \mathcal {L}$. A Smooth Projective Hash Function $\textsf {SPHF}$ should satisfy the following properties:

• Correctness: Let $W \in \mathcal {L}$ and w a witness of this membership. For all hashing keys $\textsf {hk}$ and associated projection keys $\textsf {hp}$ we have $\textsf {Hash}(\textsf {hk},(\mathcal {L}, \textsf {param}),W) = \textsf {ProjHash}(\textsf {hp},(\mathcal {L}, \textsf {param}),W,w)$.

• Smoothness: For all $W \in X \setminus \mathcal {L}$ the following distributions are statistically indistinguishable:

  
  

• Pseudo-Randomness: If $W \in \mathcal {L}$, then without a witness of membership the two previous distributions should remain computationally indistinguishable.

Classical Instantiations. For our needs, we consider discrete-logarithm based encryption schemes and related smooth projective hash functions. The underlying setting is a group $\mathbb {G}$ (denoted multiplicatively) of prime order p and we denote g a random generator of $\mathbb {G}= \langle g \rangle$. The security of our constructions will rely on the standard Decisional Diffie Hellman problems in $\mathbb {G}$:

Decisional Diffie Hellman ( $\textsf {DDH}$ ) [Bon98]: The Decisional Diffie-Hellman hypothesis states that in a group $(p,\mathbb {G},g)$ (written in multiplicative notation), given $(g^\mu , g^\nu ,g^\psi )$ for unknown $\mu ,\nu \mathop {\leftarrow }\limits ^{{}_\$}\mathbb {Z}_p$, it is hard to decide whether $\psi ={\mu \nu }$.

ElGamal encryption [ElG84] is defined by the following four algorithms:

• $\textsf {Setup}(1^\mathfrak {K})$: The scheme needs a multiplicative group $(p,\mathbb {G},g)$. The global parameters $\textsf {param}$ consist of these elements $(p,\mathbb {G},g)$.

• $\textsf {KeyGen}( \textsf {param})$: Chooses one random scalar $\alpha \mathop {\leftarrow }\limits ^{{}_\$}\mathbb {Z}_p$, which define the secret key $\textsf {dk}= \alpha$, and the public key $\textsf {pk}= h = g^{\alpha }$.

• $\textsf {Encrypt}(\textsf {pk}=h,M;r)$: For a message $M\in \mathbb {G}$ and a random scalar $r \mathop {\leftarrow }\limits ^{{}_\$}\mathbb {Z}_p$, computes the ciphertext as $C=\big (c_1 = h^{r} M, c_2 = g^{r}\big )$.

• $\textsf {Decrypt}(\textsf {dk}=\alpha ,C=(c_1,c_2))$: One computes $M = c_1 / (c_2^{\alpha })$.

As shown by Boneh [Bon98], this scheme is $\textsf {IND\text {-}CPA}$ under the hardness of $\textsf {DDH}$.

Cramer-Shoup encryption scheme [CS98] is an $\textsf {IND\text {-}CCA}$ version of the ElGamal Encryption.

• $\textsf {Setup}(1^\mathfrak {K})$ generates a group $\mathbb {G}$ of order p, with a generator g

• $\textsf {KeyGen}( \textsf {param})$ generates $(g_1,g_2)\mathop {\leftarrow }\limits ^{{}_\$}\mathbb {G}^2$, $\textsf {dk}=(x_1,x_2,y_1,y_2,z)\mathop {\leftarrow }\limits ^{{}_\$}\mathbb {Z}_p^5$, and sets, $c = g_1^{x_1}g_2^{x_2}$, $d = g_1^{y_1}g_2^{y_2}$, and $h = g_1^{z}$. It also chooses a Collision-Resistant hash function ${\mathfrak {H}_K}$ in a hash family $\mathcal {H}$ (or simply a Universal One-Way Hash Function). The encryption key is $\textsf {ek}=(g_1,g_2,c,d,h,{\mathfrak {H}_K})$.

• $\textsf {Encrypt}(\textsf {ek},M;r)$, for a message $M\in \mathbb {G}$ and a random scalar $r\in \mathbb {Z}_p$, the ciphertext is $C=(\mathbf {u}=(g_1^r,g_2^r),e=M\cdot h^r, v=(cd^\xi )^r)$, where v is computed afterwards with $\xi ={\mathfrak {H}_K}(\mathbf {u},e)$.

• $\textsf {Decrypt}(\ell ,\textsf {dk},C)$: one computes $\xi ={\mathfrak {H}_K}(\mathbf {u},e)$ and checks whether $u_1^{x_1 +\xi y_1} \cdot u_2^{x_2 +\xi y_2} \mathop {=}\limits ^{{}_?}v$. If the equality holds, one computes $M = e/(u_1^{z})$ and outputs M. Otherwise, one outputs $\bot$.

The security of the scheme is proven under the $\textsf {DDH}$ assumption and the fact the hash function used is a Universal One-Way Hash Function (see [CS98]).

3 Security Model

Distributed PAKE. In a distributed PAKE system, we consider as usual a client (owning a password) willing to interact with a gateway, such as a website. The difference compared to a non-distributed system is that the gateway itself interacts with two servers, and none of the three owns enough information to be able to recover the passwords of the clients on its own². Such a scheme is correct if the interaction between a client with a correct password and the gateway succeeds. An honest execution of a distributed PAKE protocol should result in the client holding a session key $K_\mathsf {U}$ and the gateway holding a session key $K_\mathsf {G}= K_\mathsf {U}$.

We propose in this paper two settings that describe well this situation. In a first setting, we consider that the passwords of the clients are shared information-theoretically between the servers, such as $\pi =\pi _1+\pi _2$ (if the password $\pi$ belongs to an appropriate group) or with the help of any secret sharing protocol. At the beginning of each time period, the shares are updated, in a probabilistic way, using a public function Refresh, depending on the sharing protocol used.

In a second setting, we consider that the gateway owns a database of encrypted passwords (which can be considered public), and the servers each own a share of the corresponding private keys (obtained by a secret sharing protocol). At the beginning of each time period, the shares are updated, in a probabilistic way, using a public function Refresh, depending on the sharing protocol used.

Since the security of our schemes is not analyzed in the universal composability framework (contrary to the recent paper [CEN15]), the Refresh procedure can be handled easily using classical techniques from computational proactive secret sharing (see [OY91, HJKY95] for instance).

Security Model. We consider the classical model [BPR00] for authenticated key-exchange, adapted to the two-server setting by [ACFP05, KMTG12]. In the latter model, the authors assume that every client in the system shares its password with exactly two servers. We loosen this requirement here, depending on the setting considered, as described above. We refer the interested reader to these articles for the details and we give the high-level ideas in [BCV16].

4 Our Simple Protocol

In this first setting, we consider a client $\mathsf {U}$ owning a password $\pi$ and willing to interact with a gateway $\mathsf {G}$. The gateway interacts with two servers $\mathsf {S}_1$ (owning $\pi _1$) and $\mathsf {S}_2$ (owning $\pi _2$), such that $\pi =\pi _1+\pi _2$. It should be noted that only the client’s password is assumed to be small and human-memorable. The two “passwords” owned by the servers can be arbitrarily big. The aim of the protocol is to establish a shared session key between the client and the gateway.

A simple solution to this problem consists in considering some sort of three-party $\textsf {PAKE}$, in which the client implicitly checks (using an $\textsf {SPHF}$) whether its password is the sum of the shares owned by the two servers, and the servers implicitly check (also using an $\textsf {SPHF}$) whether their share is the difference of the password owned by the client and the share owned by the other server. For sake of simplicity, we denote the client $\mathsf {U}$ as $\mathsf {S}_0$ and its password $\pi$ as $\pi _0$.

4.1 Building Blocks

Cramer-Shoup Encryption and SPHF. We consider Cramer-Shoup encryption as described in Sect. 2. The public key is denoted by $\textsf {ek}=(g_1,g_2,c,d,h,{\mathfrak {H}_K})$ and the private key by $\textsf {dk}=(x_1,x_2,y_1,y_2,z)\mathop {\leftarrow }\limits ^{{}_\$}\mathbb {Z}_p^5$. The public parameters $(\mathbb {G},p,g,\textsf {ek})$ are given as a common reference string.

We denote the ciphertext of a message $M\in \mathbb {G}$ with the scalar $r\in \mathbb {Z}_p$ by $\mathcal {C}= \textsf {CS}_\textsf {ek}(M;r) = (u_1,u_2,e,v)$, with $v = cd^\xi$ and $\xi ={\mathfrak {H}_K}(u_1,u_2,e)$.

We use the $\textsf {SPHF}$ described in [BBC+13] for the language of the valid ciphertexts of M under the public key $\textsf {ek}$. Its main advantage is that it can be computed without using the associated ciphertext, and in particular before having seen it. This allows all the participants to send their ciphertext and their projected keys in only one flow. The classical use of this $\textsf {SPHF}$ is as follows: user U (owning a message M) and V (owning a message $M'$) are supposed to share a common message, so that $M=M'$. User U wants to implicitly check this equality. To this aim, user V sends an encryption $\mathcal {C}$ of $M'$ under randomness r. In order for U to implicitly check that $\mathcal {C}$ is a valid encryption of M, it chooses a hash key $\textsf {hk}$ and computes and sends a projection key $\textsf {hp}$ to V. If $M=M'$ and if the encryption was computed correctly, then the hash value H computed by U using the private value $\textsf {hk}$ is the same as the projected hash value $H'$ computed by V using the public value $\textsf {hp}$ and its private witness r. The $\textsf {SPHF}$ is described by the following algorithms.

It has been known to be correct, smooth and pseudo-random since [BBC+13].

Main Idea of the Construction. In our setting, we denote by ${ \textsf {pw}}_b = g^{\pi _b}$. The main idea of the protocol is depicted on Fig. 1. For sake of readability, the participants which have a real role in the computations are directly linked by arrows in the picture, but one should keep in mind that all the participants ($\mathsf {U}$, $\mathsf {S}_1$ and $\mathsf {S}_2$) only communicate with $\mathsf {G}$, which then broadcasts all the messages.

In a classical $\textsf {SPHF}$-based two-party key-exchange between $\mathsf {U}$ and $\mathsf {G}$, the client and the gateway would compute a Cramer-Shoup encryption of their password: $\mathcal {C}_0=\textsf {CS}_\textsf {ek}({ \textsf {pw}}_0;r_0)$ and $\mathcal {C}_\mathsf {G}=\textsf {CS}_\textsf {ek}({ \textsf {pw}}_\mathsf {G};r_\mathsf {G})$. The gateway would then send a projection key $\textsf {hp}_{\mathsf {G},0}$ in order to implicitly check via an $\textsf {SPHF}$ whether $\mathcal {C}_0$ is a valid Cramer-Shoup encryption of ${ \textsf {pw}}_\mathsf {G}$, and the client would send a projection key $\textsf {hp}_{0,\mathsf {G}}$ in order to implicitly check via an $\textsf {SPHF}$ whether $\mathcal {C}_\mathsf {G}$ is a valid Cramer-Shoup encryption of ${ \textsf {pw}}_0$.

Here, since $S_0$ owns ${ \textsf {pw}}_0 = { \textsf {pw}}_1 \cdot { \textsf {pw}}_2$, so that the players do not share the same password, we consider an $\textsf {SPHF}$ between each pair of players $(\mathcal {S}_i,\mathcal {S}_j)$, in which player $\mathcal {S}_i$ computes the ciphertext $\mathcal {C}_i = \textsf {CS}_\textsf {ek}({ \textsf {pw}}_i;r_i)$, the keys $\textsf {hk}_{i,j}$ and $\textsf {hp}_{i,j}$ and sends $(\mathcal {C}_i,\textsf {hp}_{i,j})$ to $\mathcal {S}_j$. It also computes the hash value $H_{i,j} = \textsf {Hash}(\textsf {hk}_{i,j},(\textsf {ek},{ \textsf {pw}}_i),\mathcal {C}_j)$ and the projected hash value $H'_{j,i} = \textsf {ProjHash}(\textsf {hp}_{j,i},(\textsf {ek},M_i),\mathcal {C}_i, r_i)$. Formally, for each pair of users $(\mathcal {S}_i,\mathcal {S}_j)$, the language checked on $\mathcal {S}_j$ by $\mathcal {S}_i$ is defined as follows: $\mathcal {C}_j \in \mathcal {L}_{i,j} = \{ \mathcal {C}= (u_1,u_2,e,v) \in \mathbb {G}^4 \ | \ \exists r\in \mathbb {Z}_p\text { such that } \mathcal {C}= \textsf {CS}_\textsf {ek}({ \textsf {pw}}_j;r)\}$ but it cannot be checked directly by a unique $\textsf {SPHF}$ since the passwords are different (and thus $\mathcal {S}_i$ does not know ${ \textsf {pw}}_j$). Rather, we combine in the protocol the six $\textsf {SPHF}$ described to globally ensure the correctness (each one remaining smooth and pseudo-random), as described in the next part. The correctness of the $\textsf {SPHF}$ for the pair $(\mathcal {S}_i,\mathcal {S}_j)$ implies that if everything was computed honestly, then one gets the equalities $H_{i,j} ({ \textsf {pw}}_i / { \textsf {pw}}_j)^{\lambda _i} = H'_{i,j}$ and $H_{j,i} ({ \textsf {pw}}_j / { \textsf {pw}}_i)^{\lambda _j} = H'_{j,i}$.

Fig. 1.

Main idea of the construction

4.2 Login Procedure

• Each participant $\mathsf {S}_b$ picks $r_b$ at random and computes a Cramer-Shoup encryption of its password $\mathcal {C}_b=\textsf {CS}_\textsf {ek}({ \textsf {pw}}_b;r_b)$, with $v_b = cd^{\xi _b}$.

  It also chooses, for $i \in \{0,1,2\}\setminus \{b\}$, a random hash key $\textsf {hk}_{b,i} = (\eta _{b,i}, \gamma _{b,i}, \theta _{b,i},\lambda _{b}, \kappa _{b,i})$ and sets $\textsf {hp}_{b,i}=(\textsf {hp}_{b,i;1}, \textsf {hp}_{b,i;2})=({g_1}^{\eta _{b,i}} {g_2}^{\theta _{b,i}} h^{\lambda _{b}} c^{\kappa _{b,i}}, {g_1}^{\gamma _{b,i}} d^{\kappa _{b,i}})$ as the projection key intended to the participant $\mathsf {S}_i$.

  It sends $(\mathcal {C}_b,(\textsf {hp}_{b,i})_{i \in \{0,1,2\}\setminus \{b\}})$ to the gateway $\mathsf {G}$, which broadcasts these values to the other participants.

• After receiving the first flow from the servers, the client computes, for $i\in \{1,2\}$, $H'_{i,0} = {\textsf {hp}_{i,0;1}}^{r_0} {\textsf {hp}_{i,0:2}}^{\xi _0 r_0}$. It also computes $H_{0}=H_{0,1} \cdot H_{0,2} \cdot {{ \textsf {pw}}_0}^{\lambda _0}$, and sets its session key $K_\mathsf {U}$ as $K_\mathsf {U}= K_0 = H'_{1,0} \cdot H'_{2,0} \cdot H_0$.

  After receiving the first flow from the other server and the client, the server $\mathsf {S}_b$ computes, for $i\in \{0,3-b\}$, $H'_{i,b} = {\textsf {hp}_{i,b;1}}^{r_b} {\textsf {hp}_{i,b;2}}^{\xi _b r_b}$. It also computes $H_{b}=H_{b,0} / (H_{b,3-b} \cdot { \textsf {pw}}_b^{\lambda _b})$, and sets its partial key $K_b$ as $K_b=H'_{0,b} \cdot H'_{3-b,b} \cdot H_b$. It privately sends this value $K_b$ to the gateway $\mathsf {G}$.

• The gateway finally sets $K_\mathsf {G}= K_1 \cdot K_2$.

Correctness. Recall that $H'_{i,j} = H_{i,j} ({ \textsf {pw}}_i/{ \textsf {pw}}_j)^{\lambda _i}$ for all pairs $(i,j)\in \{0,1,2\}^2$, so that the session key of the gateway is equal to $K_\mathsf {G}= K_1 \cdot K_2$, i.e.

$K_\mathsf {G}= \frac{H'_{0,1} H'_{2,1} H_{1,0}}{H_{1,2}{ \textsf {pw}}_1^{\lambda _1}} \frac{H'_{0,2} H'_{1,2} H_{2,0}}{H_{2,1}{ \textsf {pw}}_2^{\lambda _2}} = H_{0,1} H_{1,0} H_{0,2} H_{2,0} \left( \frac{1}{{ \textsf {pw}}_2}\right) ^{\lambda _1} \left( \frac{1}{{ \textsf {pw}}_1}\right) ^{\lambda _2} \left( \frac{({ \textsf {pw}}_0)^2}{{ \textsf {pw}}_1 { \textsf {pw}}_2} \right) ^{\lambda _0}$

while the session key of the client is $K_\mathsf {U}= H'_{1,0} \cdot H'_{2,0} \cdot H_0$, i.e.

$K_\mathsf {U}= H'_{1,0} \cdot H'_{2,0} \cdot H_{0,1} \cdot H_{0,2} \cdot {{ \textsf {pw}}_0}^{\lambda _0} = H_{0,1} H_{1,0} H_{0,2} H_{2,0} \left( \frac{{ \textsf {pw}}_1}{{ \textsf {pw}}_0}\right) ^{\lambda _1} \left( \frac{{ \textsf {pw}}_2}{{ \textsf {pw}}_0}\right) ^{\lambda _2} ({ \textsf {pw}}_0)^{\lambda _0}$

and these two values are equal as soon as ${ \textsf {pw}}_0 = { \textsf {pw}}_1 \cdot { \textsf {pw}}_2$.

Complexity. The following table sums up the number of group elements needed for each participant. It should be noted that in case one of the servers is the gateway, its communication costs are reduced.

Proof of Security. The proof follows the spirit of the proofs given in [KV11, BBC+13]. For lack of space, a sketch is given in [BCV16].

5 Our Efficient Protocol

In this second setting, we consider again a client $\mathsf {U}$ owning a password $\pi$ and willing to interact with a gateway $\mathsf {G}$. The gateway owns a public database of encrypted passwords, and it interacts with two servers $\mathsf {S}_1$ and $\mathsf {S}_2$, each owning a share of the secret key of the encryption scheme. The aim of the protocol is to establish a shared session key between the client and the gateway.

The idea is similar to the protocol described in the former section, except that only the client needs to compute a ciphertext, the other ciphertext being publicly available from the database. The participants implicitly check (using several $\textsf {SPHF}$) that the message encrypted in the ciphertext of the client is the same as the message encrypted in the database (using the secret key shared upon the servers).

5.1 Building Blocks

Cramer-Shoup Encryption and SPHF. We consider Cramer-Shoup encryption as the previous construction. We use here the simpler $\textsf {SPHF}$ described in [GL03] for the language of the valid ciphertexts of M under the public key $\textsf {ek}$, in which the participants need to see the ciphertext before being able to compute their projection keys. The $\textsf {SPHF}$ is described by the following algorithms.

It has been known to be correct, smooth and pseudo-random since [GL03].

El Gamal Encryption and SPHF. We consider El Gamal encryption as described in Sect. 2. The public key is denoted by $\textsf {pk}=h=g^\alpha$ and the private key by $\textsf {sk}=\alpha \mathop {\leftarrow }\limits ^{{}_\$}\mathbb {Z}_p$. The public parameters $(\mathbb {G},p,g,\textsf {pk})$ are given as a common reference string. We denote the ciphertext of a message $M\in \mathbb {G}$ with the scalar $r\in \mathbb {Z}_p$ by $\mathcal {C}= \textsf {EG}_\textsf {pk}(M;r) = (e, u) = (h^r M, g^r)$.

The regular SPHF used throughout the literature [CS02] on the language $\{ \mathcal {C}= (e,u) \in \mathbb {G}^2 \ |\ \exists r\in \mathbb {Z}_p\text { such that } \mathcal {C}= \textsf {EG}_\textsf {pk}(M;r)\}$ of the valid encryptions of M, with r being the witness of the word $\mathcal {C}$, usually allows a server to check whether the ciphertext was honestly computed on the value M by a client, by generating a pair of keys $(\textsf {hk},\textsf {hp})$ and sending $\textsf {hp}$ to the client.

Here, on the contrary, we now want a client to implicitly check that a server knows the decryption key of the encryption scheme. This means that the client computes both the ciphertext (or the ciphertext is publicly available in a database, as here) and the pair of keys $(\textsf {hk},\textsf {hp})$ and sends the ciphertext as well as $\textsf {hp}$ to the server, which now uses the decryption key as a witness. This implies the following modifications to the algorithms of the $\textsf {SPHF}$:

and we show that this $\textsf {SPHF}$ satisfies the usual properties:

• Correctness: if $\mathcal {C}\in \mathcal {L}$ with witness $\alpha$, one directly gets $H=H'$;

• Smoothness: assume $\mathcal {C}\notin \mathcal {L}$. It can then be parsed as $\mathcal {C}= (e, u)$ with $u = g^r$ and $e = h^r M' = g^{\alpha r} M g^{\delta _M}$ (with $M'\ne M$ and thus $\delta _M\ne 0$), so that $\textsf {hp}= u^\lambda g^\mu = g^{r\lambda +\mu }$ and $H = h^\mu (e/M)^\lambda = g^{\alpha \mu } g^{(\alpha r + \delta _M)\lambda }$.

  The smoothness is then easy to see by considering the following equality of matrices:

  $\left( \begin{array}{c} \log _g(\textsf {hp}) \\ \log _g(H) \end{array} \right) = \left( \begin{array}{c c} r &{} 1 \\ \alpha r + \delta _M \& \alpha \end{array} \right) \cdot \left( \begin{array}{c} \lambda \\ \mu \end{array} \right)$ which shows that as soon as the word is not a valid encryption of M, and so $\delta _M$ is not equal to 0, the Hash value H is not in the span of the projection key $\textsf {hp}$ so that the two distributions described in Sect. 2 are indistinguishable.

• Pseudo-Randomness. Since El Gamal encryption is $\textsf {IND\text {-}CPA}$, it is impossible to distinguish between a real encryption and a random value without knowing the decryption key. Since the decryption key is the witness of the $\textsf {SPHF}$, without knowing the witness, the two distributions remain indistinguishable.

Main Idea of the Construction. Again, we denote the client $\mathsf {U}$ as $\mathsf {S}_0$ and its password $\pi$ as $\pi _0$. In our setting, we denote by ${ \textsf {pw}}_k = g^{\pi _k}$ for all k. The database contains El Gamal encryptions of each ciphertext ${ \textsf {pw}}_{\mathsf {U}_i}$, under randomness $s_{\mathsf {U}_i}$: $\mathcal {C}^{db}_{\mathsf {U}_i} = \textsf {EG}_\textsf {pk}({ \textsf {pw}}_{\mathsf {U}_i};s_{\mathsf {U}_i}) = (h^{s_{\mathsf {U}_i}} { \textsf {pw}}_{\mathsf {U}_i}, g^{s_{\mathsf {U}_i}})$, so that here, $\mathcal {C}^{db}_\mathsf {U}= \textsf {EG}_\textsf {pk}({ \textsf {pw}}_\mathsf {U};s_\mathsf {U}) = (h^{s_\mathsf {U}} { \textsf {pw}}_\mathsf {U}, g^{s_\mathsf {U}})$. The client computes a Cramer-Shoup encryption of its password: $\mathcal {C}_0=\textsf {CS}_\textsf {ek}({ \textsf {pw}}_0;r_0) = (u_1, u_2, e, v)$ with $v = cd^\xi$. The execution of the protocol should succeed if these encryptions are correct and ${ \textsf {pw}}_0 = { \textsf {pw}}_\mathsf {U}$. Recall that the server $\mathcal {S}_i$ knows $\alpha _i$ such that $\alpha = \alpha _1 + \alpha _2$ is the decryption key of the El Gamal encryption.

The main idea is depicted on Fig. 2. For sake of readability, the participants which have a real role in the computations are directly linked by arrows in the picture, but one should keep in mind that all the participants ($\mathsf {U}$, $\mathsf {S}_1$ and $\mathsf {S}_2$) only communicate with $\mathsf {G}$, which then broadcasts all the messages.

In a classical $\textsf {SPHF}$-based two-party key-exchange between $\mathsf {U}$ and $\mathsf {G}$, the gateway would check whether $\mathcal {C}_0$ is a valid Cramer-Shoup encryption of ${ \textsf {pw}}_\mathsf {U}$. Since here the password ${ \textsf {pw}}_\mathsf {U}$ is unknown to the servers $\mathsf {S}_1$ and $\mathsf {S}_2$, this is done in our setting by two $\textsf {SPHF}$, using $\textsf {hp}^{\mathrm {CS}}_1$ (sent by $\mathsf {S}_1$) and $\textsf {hp}^{\mathrm {CS}}_2$ (sent by $\mathsf {S}_2$), where the servers use the first term of the public encryption $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}$ ($h^{s_\mathsf {U}} { \textsf {pw}}_\mathsf {U}$) in order to cancel the unknown ${ \textsf {pw}}_\mathsf {U}$.

In a classical $\textsf {SPHF}$-based two-party key-exchange between $\mathsf {U}$ and $\mathsf {G}$, the client would also check whether $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}$ is a valid El Gamal encryption of its password ${ \textsf {pw}}_0$, i.e. whether the gateway knows a witness for its ciphertext $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}$ ($s_\mathsf {U}$ in the usual constructions, $\alpha$ here). Since $\alpha$ is unknown to the gateway, this is done in our setting by the combination of three $\textsf {SPHF}$, using $\textsf {hp}^{\mathrm {EG}}_0$ (sent by the client), $\textsf {hp}^{\mathrm {EG}}_1$ (sent by $\mathsf {S}_1$) and $\textsf {hp}^{\mathrm {EG}}_2$ (sent by $\mathsf {S}_2$). These three $\textsf {SPHF}$ allow the client and the servers to implicitly check that the servers know $\alpha _1$ and $\alpha _2$ such that $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}$ can be decrypted (using the decryption key $\alpha = \alpha _1 + \alpha _2$) to the same password ${ \textsf {pw}}_0$ than the one encrypted in $\mathcal {C}_0$ sent by the client. Formally, the languages checked are as follows:

• by the client:

  $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}\in \mathcal {L}_0 = \{ \mathcal {C}= (e,u) \in \mathbb {G}^2 \ | \ \exists \alpha \in \mathbb {Z}_p\text { such that } h = g^\alpha \text { and } e / u^\alpha = { \textsf {pw}}_0 \}$

• by server $\mathcal {S}_i$ (with respect to the client $\mathcal {S}_0$ and server $\mathcal {S}_j$):

  $\mathcal {C}_0 \in \mathcal {L}_{i,0} = \{ \mathcal {C}= (u_1,u_2,e,v) \in \mathbb {G}^4 \ | \ \exists r\in \mathbb {Z}_p\text { such that } \mathcal {C}= \textsf {CS}_\textsf {ek}({ \textsf {pw}}_\mathsf {U};r)$ and $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}\in \mathcal {L}_{i,j} = \{ \mathcal {C}= (e,u) \in \mathbb {G}^2 \ | \ \exists \alpha _{j}\in \mathbb {Z}_p\text { such that } h = g^{\alpha _i + \alpha _{j}}\} \text { and }e / u^{\alpha _i + \alpha _{j}} = { \textsf {pw}}_\mathsf {U}\}$

but they cannot be checked directly by a unique $\textsf {SPHF}$ since the value ${ \textsf {pw}}_\mathsf {U}$ appearing in the languages is unknown to the verifier $\mathcal {S}_i$. Rather, the server $\mathcal {S}_i$ will use the first term of the public encryption $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}$ ($h^{s_\mathsf {U}} { \textsf {pw}}_\mathsf {U}$) in order to cancel this unknown ${ \textsf {pw}}_\mathsf {U}$. To achieve this goal, we combine the five $\textsf {SPHF}$ described to globally ensure the correctness (each one remaining smooth and pseudo-randomness), as described in the next part.

Fig. 2.

Main idea of the construction

5.2 Login Procedure

• The client $\mathsf {U}=\mathsf {S}_0$ chooses $r_0$ at random and computes a Cramer-Shoup encryption of its password $\mathcal {C}_0=\textsf {CS}_\textsf {ek}({ \textsf {pw}}_0;r_0) = (u_1, u_2, e, v)$ with $v = cd^\xi$.

  It also chooses a random (El Gamal) hash key $\textsf {hk}^{\mathrm {EG}}_0=(\lambda _0, \mu _0)$ and computes the corresponding projected key on the ciphertext $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}= \textsf {EG}_\textsf {pk}({ \textsf {pw}}_\mathsf {U};s_\mathsf {U}) = (h^{s_\mathsf {U}} { \textsf {pw}}_\mathsf {U}, g^{s_\mathsf {U}})$ contained in the database: $\textsf {hp}^{\mathrm {EG}}_0 = g^{s_\mathsf {U}\lambda _0} g^{\mu _0}$.

  It sends $(\mathcal {C}_0,\textsf {hp}^{\mathrm {EG}}_0)$ to the gateway, which broadcasts these values to the servers.

• After receiving this flow from the client, the servers $\mathsf {S}_1$ and $\mathsf {S}_2$ also choose a random (El Gamal) hash key $\textsf {hk}^{\mathrm {EG}}_b=(\lambda _b, \mu _b)$ and compute the corresponding projected key on the ciphertext $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}$ contained in the database: $\textsf {hp}^{\mathrm {EG}}_b = g^{s_\mathsf {U}\lambda _b} g^{\mu _b}$.

  The servers $\mathsf {S}_1$ and $\mathsf {S}_2$ also choose a random (Cramer-Shoup) hash key $\textsf {hk}^{\mathrm {CS}}_{b} = (\eta _{b}, \theta _{b}, \lambda _{b}, \kappa _{b})$ (with the same value $\lambda _b$) and compute the corresponding projected key on the ciphertext $\mathcal {C}_0$ sent by the client: $\textsf {hp}^{\mathrm {CS}}_{b} =({g_1}^{\eta _{b}} {g_2}^{\theta _{b}} h^{\lambda _{b}} (c d^\xi )^{\kappa _{b}})$.

  Each server sends $(\textsf {hp}^{\mathrm {EG}}_b, \textsf {hp}^{\mathrm {CS}}_b)$ to the gateway $\mathsf {G}$, which broadcasts these values to the other participants.

• After receiving the projected keys from the servers, the client computes, for $i\in \{1,2\}$, $H'_{i,0} = (\textsf {hp}^{\mathrm {CS}}_{i})^{r_0}$. It also computes $H_0 = (h^{s_\mathsf {U}} { \textsf {pw}}_\mathsf {U}/ { \textsf {pw}}_0)^{\lambda _0} h^{\mu _0}$ by dividing the first term of the ciphertext $\mathcal {C}^{\mathrm {DB}}_\mathsf {U}$ contained in the database by its password ${ \textsf {pw}}_0$. It finally sets its session key $K_\mathsf {U}$ as $K_\mathsf {U}= K_0 = H'_{1,0} \cdot H'_{2,0} \cdot H_0$.

  After receiving the first flow from the other server and the client, the server $\mathsf {S}_b$ computes, for $i\in \{0,3-b\}$, $H'_{i,b} = (\textsf {hp}^{\mathrm {EG}}_i)^{\alpha _b}$.

  It also computes $H_{b,0} = (u_1)^{\eta _b} (u_2)^{\theta _b} [e / (h^{s_\mathsf {U}} { \textsf {pw}}_\mathsf {U})]^{\lambda _b} v^{\kappa _b}$ and $H_b = H_{b,0} \cdot (\textsf {hp}^{\mathrm {EG}}_b)^{\alpha _b} / h^{\mu _b}$, and sets its partial key $K_b$ as $K_b=H'_{0,b} \cdot H'_{3-b,b} \cdot H_b$. It privately sends this value $K_b$ to the gateway $\mathsf {G}$.

• The gateway finally sets $K_\mathsf {G}= K_1 \cdot K_2$.

Correctness. Due to the correctness of the Cramer-Shoup SPHF, we have the equalities $H'_{b,0} = H_{b,0} \left( \frac{h^{s_\mathsf {U}} { \textsf {pw}}_\mathsf {U}}{{ \textsf {pw}}_0}\right) ^{\lambda _b}$ for $b\in \{1,2\}$. The session key of the gateway is thus equal to $K_\mathsf {G}= K_1 \cdot K_2 = (H'_{0,1} \cdot H'_{2,1} \cdot H_1) \cdot (H'_{0,2} \cdot H'_{1,2} \cdot H_2)$ where, after computation, $K_b = h^{(\lambda _0+\lambda _1+\lambda _2) \alpha _b} g^{(\mu _0+\mu _1+\mu _2)\alpha _b} H'_{b,0} ({ \textsf {pw}}_0 / { \textsf {pw}}_\mathsf {U})^{\lambda _b} h^{-s_\mathsf {U}\lambda _b} h^{-\mu _b}$.

If ${ \textsf {pw}}_0 = { \textsf {pw}}_\mathsf {U}$, $h = g^{\alpha }$ and $\alpha = \alpha _1 + \alpha _2$, $K_\mathsf {G}= h^{s_\mathsf {U}\lambda _0} h^{\mu _0} H'_{1,0} H'_{2,0}$, which is equal to the session key of the client $K_\mathsf {U}= K_0 = H'_{1,0} \cdot H'_{2,0} \cdot H_0 = H'_{1,0} \cdot H'_{2,0} \cdot h^{s_\mathsf {U}\lambda _0} h^{\mu _0}$.

Complexity. The following table sums up the number of group elements needed for each participant. It should be noted that in case one of the servers is the gateway, its communication costs are reduced.

Compared to [KMTG12], the communication complexity of our protocol is decreased by more than 50 % (9 group elements instead of 20 group elements). For efficiency, as in [KMTG12], we count exponentiations only, and assume a multi-exponentiation with up to 5 bases can be computed at the cost of at most 1.5 exponentiations. The client performs the equivalent of 8 full exponentiations, while each server performs 7 exponentiations (instead of 15 and 13 respectively in [KMTG12]).

Proof of Security. The proof follows the idea of the former one. For lack of space, a sketch is given in [BCV16].

6 Conclusion

We presented two constructions of distributed Password-Authenticated Key Exchange between a user and several servers. We focused on presenting them in a classical group setting (with only two servers). Very efficient implementations of our protocols can be readily obtained using standard cryptographic libraries and do not require pairings.

Our methods can be generalized to the setting where n servers share the (encryption of the) password. $\textsf {SPHF}$ can further handle polynomials of variables and the use of secret sharing techniques à la Shamir, allows to share polynomials evaluation between n servers and to provide a threshold distributed PAKE such that security is ensured as long as less than a certain arbitrary threshold $t \in \{1,\dots ,n\}$ of servers are compromised (contrary to the protocol from [DG06] which requires an honest majority of the servers).

Smooth projective hashing is mostly used in a classical discrete-logarithm-based setting (or pairing-based setting) but constructions were also proposed for Paillier encryption [CS02] and for LWE encryption [KV09]. These $\textsf {SPHF}$ would allow a readily adaptation of our techniques to other classical settings of cryptography.