An efficient client–client password-based authentication scheme with provable security

Abstract

Recently, Tso proposed a three-party password-based authenticated key exchange (3PAKE) protocol. This protocol allows two clients to authenticate each other and establish a secure session key through a server over an insecure channel. The main security goals of such protocols are authentication and privacy. However, we show that Tso’s protocol achieves neither authentication goal nor privacy goal. In this paper, we indicate that the privacy and authentication goals of Tso’s protocol will be broken by off-line password guessing attack and impersonation attack, respectively. To overcome the weaknesses, we propose an improved 3PAKE protocol to achieve more security and performance than related protocols. The security of the proposed improved protocol is proved in random oracle model.

1 Introduction

Authenticated key exchange (AKE) protocols (e.g., [1–10]) help communicating entities, who are communicating over an insecure network, to establish a secret session key to be used for protecting their subsequent communication. Password-based authenticated key exchange (PAKE) protocol is a type of AKE protocols which enables two or more communication entities, who only share a weak, low-entropy and easily memorable passwords, to authenticate each other and establish a high-entropy secret session key.

PAKE protocols were first proposed in the two-party setting (2PAKE) which are quite suitable for the client–server architecture (e.g., [11–18]). However, these protocols are very inconvenient for large-scale client–client communication environments. Since each client needs to remember different password for each partner who communicates with, for a large network, it may strain the storage capacity of the clients. To avoid this problem, PAKE protocols in the three-party setting (3PAKE) are developed. In a 3PAKE protocol, a trusted server mediates between two communication clients and each client only needs to share a password with the server.

1.1 Related works

In order to design a secure and practicable 3PAKE, many protocols have been proposed. The main security threats for the 3PAKE protocols are password guessing attacks. To protect these protocols against dictionary attacks, there are three main approaches: using the server public key (e.g., [19–22]), using symmetric cryptosystems (e.g., [23–25]), and without using server public keys and symmetric cryptosystems (e.g., [26–30, 30–42]). The 3PAKE protocols using symmetric cryptosystems requires a stronger assumption ”the ideal cipher model” to prove the security [30]. Recently, Xiong et al. [25] demonstrated that all of the 3PAKE protocols without server public keys are not secure against Key Compromise Impersonation (KCI) attack. Therefore, the 3PAKE protocols which uses only server public keys to prevent password guessing attacks are more secure and applicable than the other two approaches.

In 2009, Huang [38] proposed a 3PAKE protocol without server public key and symmetric cryptosystems. However, Yoon and Yoo [39] demonstrated that Huang’s 3PAKE protocol is vulnerable to undetectable online password guessing attacks and off-line password guessing attacks by any other user. Based on the Yoon and Yoo’s attacks, Wu et al. [40] showed that Huang’s protocol is also vulnerable to key compromise impersonation attack and proposed an enhanced protocol which uses server public key. In 2011, Chang et al. [41] applied XOR operations to removed both the server public keys and the symmetric cryptosystem for constructing a communication efficient 3PAKE protocol. However, Wu et al. [30] pointed out that Chang et al.’s 3PAKE is insecure against password guessing attacks and proposed an improved protocol. To overcome the security problems of the Chang et al.’s scheme, Tso [42] also proposed an improved scheme without using the server public key or symmetric cryptosystems. Recently, Xiong et al. [25] demonstrated that the Wu et al.’s 3PAKE protocol is vulnerable to key compromise impersonation (in short, KCI) attack.

1.2 Contribution

The contribution of this paper is twofold. First, the paper indicates that Tso’s protocol [42] not only is still vulnerable to off-line password guessing attack, but also is insecure against impersonation attack. Second, it proposes a more secure and efficient 3PAKE protocol to overcome the security flaws of the related protocols.

1.3 Organization

The rest of this paper is organized as follows. In Sect. 2, we review the Tso’s 3PAKE protocol. In Sect. 3, we show the vulnerabilities of Tso’s protocol. An enhanced 3PAKE protocol is proposed in Sect. 4. We analyze the security and performance of the proposed scheme in Sects. 5 and 6, respectively. Finally, we conclude our paper in Sect. 7.

2 A brief review of Tso’s 3PAKE protocol

This section briefly reviews Tso’s 3PAKE protocol [42].

2.1 Notations

The notations used throughout this paper are summarized in Table 1.

Table 1 The notations

2.2 Protocol description

For a detailed analysis, we review Tso’s 3PAKE protocol [42]. The details of this protocol, shown in Fig. 1, are as follows:

• Step 1: $A$ sends the identities $id_{A}$ and $id_{B}$ to $S$ as initial request.

• Step 2: Upon receiving the messages {$id_{A}$, $id_{B}$}, $S$ chooses two random numbers $e_{S1}, e_{S2} \in _{R} \mathbb {Z}^{*}_{q}$, computes

  $$\begin{aligned} R_{S1}&= g^{e_{S1}+pw_{A}} \hbox {mod}\, p, \\ R_{S2}&= g^{e_{S2}+pw_{B}} \hbox {mod}\, p, \end{aligned}$$

  and sends {$R_{S1}$, $R_{S2}$} to $A$.

• Step 3: After receiving the message {$R_{S1}$, $R_{S2}$}, $A$ firstly retrieves $g^{e_{S1}}$ by computing $(R_{S1}/g^{pw_{A}})\,\,\hbox {mod}\, p$. $A$ then chooses a random number $e_{A} \in _{R} \mathbb {Z}^{*}_{q}$ to compute

  $$\begin{aligned} R_{A}&= g^{e_{A}} \hbox {mod}\, p, \\ R_{AS}&= (g^{e_{S1}})^{e_{A}} \hbox {mod}\, p, \\ Auth_{AS}&= h(R_{AS},g^{e_{S1}}, id_{A}, id_{B}), \end{aligned}$$

  and sends {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R_{S2}$} to $B$.

• Step 4: After receiving the message {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R_{S2}$}, $B$ retrieves $g^{e_{S2}}$ by computing $(R_{S2}/g^{pw_{B}})$ $\hbox {mod}\, p$. $B$ then chooses a random number $e_{B} \in _{R} \mathbb {Z}^{*}_{q}$ to compute

  $$\begin{aligned} R_{B}&= g^{e_{B}} \hbox {mod}\, p, \\ R_{BS}&= (g^{e_{S2}})^{e_{B}} \hbox {mod}\, p, \\ K_{B}&= R_{A}^{e_{B}} \hbox {mod}\, p, \\ Auth_{BS}&= h(R_{BS},g^{e_{S2}}, id_{A}, id_{B}), \\ Auth_{BA}&= h(K_{B},R_{A}), \end{aligned}$$

  and sends {$R_{A}$, $Auth_{AS}$, $R_{B}$, $Auth_{BS}$, $Auth_{BA}$} to $S$.

• Step 5: After receiving the message {$R_{A}$, $Auth_{AS}$, $R_{B}$, $Auth_{BS}$, $Auth_{BA}$}, $S$ authenticates $A$ and $B$, separately. To authenticate $A$, $S$ computes $R_{SA} = R_{A}^{e_{S1}} \hbox {mod}\, p$ and verifies $h(R_{SA}$, $g^{e_{S1}}$, $id_{A}$, $id_{B}) ?= Auth_{AS}$. To authenticate $B$, $S$ computes $R_{SB} = R_{B}^{e_{S2}} \hbox {mod}\, p$ and verifies $h(R_{SB},g^{e_{S2}}, id_{A}, id_{B}) ?= Auth_{BS}$. If the two results are positive, $S$ computes $Auth_{SA} = h(R_{SA},R_{B})$ and $Auth_{SB} = h(R_{SB},R_{A})$. Then $S$ sends {$R_{B}$, $Auth_{SA}$, $Auth_{BA}$, $Auth_{SB}$} to $A$.

• Step 6: After receiving the message {$R_{B}$, $Auth_{SA}$, $Auth_{BA}$, $Auth_{SB}$}, $A$ checks if $h(R_{AS},R_{B}) ?=Auth_{SA}$. If it holds, $S$ is authenticated by $A$; then $A$ computes $K_{A} = R_{B}^{e_{A}} \hbox {mod}\, p$, and verifies $h(K_{A},R_{A}) ?= Auth_{BA}$. If it holds, $B$ is authenticated by $A$. Then, $A$ computes$Auth_{AB} = h(K_{A},R_{B})$ and sends {$Auth_{SB}$, $Auth_{AB}$} to $B$. Finally, $A$ computes the session key as $SK = h(K_{A} , id_{A}, id_{B}) = h(g^{e_{A}e_{B}}, id_{A}, id_{B})$.

• Step 7: After receiving the message {$Auth_{SB}$, $Auth_{AB}$}, $B$ checks if $h(R_{BS},R_{A}) ?$ $=Auth_{SB}$. If it holds, $S$ is authenticated by $B$; then $B$ verifies $h(K_{B},R_{B}) ?= Auth_{AB}$. If it holds, $A$ is authenticated by $B$. Finally, $B$ computes the session key as $SK = h(K_{B} , id_{A}, id_{B}) = h(g^{e_{A}e_{B}}, id_{A}, id_{B})$.

Fig. 1

Tso’s 3PAKE protocol [42]

3 Cryptanalysis of Tso’s protocol

The main security goals of 3PAKE protocols are authentication and privacy. However, this section indicates that Tso’s protocol [42] does not achieve the security goals. We Show that Tso’s protocol is vulnerable to off-line password guessing attack and impersonation attack.

3.1 Off-line password guessing attack

Here, we show that an active adversary can successfully guess the users’ correct passwords which leads to completely breaking Tso’s protocol [42]. The details of the proposed off-line password guessing attack, outlined in Fig. 2, are as follows:

• Step 1: When the user $A$ wishes to communicate with the user $B$ through the server $S$, and sends the initial message {$id_{A}$, $id_{B}$} to $S$, the active adversary $\fancyscript{C}$ intercepts the message and chooses two random numbers $e'_{S1}, e'_{S2} \in _{R} \mathbb {Z}^{*}_{q}$ to computes

  $$\begin{aligned} R'_{S1}&= g^{e'_{S1}} \hbox {mod}\, p, \\ R'_{S2}&= g^{e'_{S2}} \hbox {mod}\, p. \end{aligned}$$

  $\fancyscript{C}$ then returns {$R'_{S1}$, $R'_{S2}$} to $A$.

• Step 2: After receiving the message {$R'_{S1}$, $R'_{S2}$}, $A$ chooses a random number $e_{A} \in _{R} \mathbb {Z}^{*}_{q}$ to compute

  $$\begin{aligned} R_{A}&= g^{e_{A}} \hbox {mod}\, p, \nonumber \\ R_{AS}&= (R'_{S1}/g^{pw_{A}})^{e_{A}} \hbox {mod}\, p, \\ Auth_{AS}&= h(R_{AS},(R'_{S1}/g^{pw_{A}}), id_{A}, id_{B}), \nonumber \end{aligned}$$

  (1)

  and sends {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R'_{S2}$} to $B$.

• Step 3: $\fancyscript{C}$ intercepts the message {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R'_{S2}$} and tries to guess $A$’s correct password $pw_{A}$. To do so, $\fancyscript{C}$ performs the following steps

  • 1. Guess a password $pw'_{A}$.

  • 2. Compute

    $$\begin{aligned} R'_{AS} = (R_{A}^{e'_{S1}}/R_{A}^{pw'_{A}}) \hbox {mod}\, p. \end{aligned}$$

    (2)

  • 3. Check if

    $$\begin{aligned} Auth_{AS} = h(R'_{AS},(R'_{S1}/g^{pw'_{A}}), id_{A}, id_{B}). \end{aligned}$$

    (3)

  • 4. If Eq. (3) holds, $\fancyscript{C}$ confirms that the guessed password $pw'_{A}$ is the correct one. Otherwise, $\fancyscript{C}$ chooses another password $pw'_{A}$ and repeatedly performs above steps to obtain the correct password.

Fig. 2

Off-line password guessing attack on Tso’s 3PAKE protocol

Proposition 1

Equation (3) holds for a correct guess of $pw'_{A} = pw_{A}$.

Proof

Firstly, we show that the Eqs. (1) and (2) are equal for $pw'_{A} = pw_{A}$ as follows:

$$\begin{aligned} R'_{AS}&= (R_{A}^{e'_{S1}}/R_{A}^{pw'_{A}}) \hbox {mod}\, p \\&= ((g^{e_{A}})^{e'_{S1}}/(g^{e_{A}})^{pw_{A}}) \hbox {mod}\, p \\&= ((g^{e'_{S1}})^{e_{A}}/(g^{pw_{A}})^{e_{A}}) \hbox {mod}\, p \\&= (g^{e'_{S1}}/g^{pw_{A}})^{e_{A}} \hbox {mod}\, p \\&= (R'_{S1}/g^{pw_{A}})^{e_{A}} \hbox {mod}\, p \\&= R_{AS}. \end{aligned}$$

Thus,

$$\begin{aligned} Auth_{AS}&= h(R_{AS},(R'_{S1}/g^{pw_{A}}), id_{A}, id_{B}) \\&= h(R'_{AS},(R'_{S1}/g^{pw'_{A}}), id_{A}, id_{B}). \end{aligned}$$

It fulfills the proof. $\square$

3.2 Impersonation attack

Here, we show that an adversary who obtained the correct password of a special user can easily masquerade as the legitimate server and another user. Suppose the adversary $\fancyscript{C}$ obtained $A$’s password $pw_{A}$. To impersonate the server $S$ and $B$, the adversary $\fancyscript{C}$ performs as follows (outlined in Fig. 3):

• Step 1: When the user $A$ wishes to communicate with the user $B$ through the server $S$, and sends the initial message {$id_{A}$, $id_{B}$} to $S$, the active adversary $\fancyscript{C}$ intercepts the message and chooses two random numbers $e'_{S1}, e'_{S2} \in _{R} \mathbb {Z}^{*}_{q}$ to computes

  $$\begin{aligned} R'_{S1}&= g^{e'_{S1}+pw_{A}} \hbox {mod}\, p, \\ R'_{S2}&= g^{e'_{S2}} \hbox {mod}\, p. \end{aligned}$$

  $\fancyscript{C}$ then returns {$R'_{S1}$, $R'_{S2}$} to $A$.

• Step 2: After receiving the message {$R'_{S1}$, $R'_{S2}$}, $A$ chooses a random number $e_{A} \in _{R} \mathbb {Z}^{*}_{q}$ to compute

  $$\begin{aligned} R_{A}&= g^{e_{A}} \hbox {mod}\, p, \nonumber \\ R_{AS}&= (R'_{S1}/g^{pw_{A}})^{e_{A}} \hbox {mod}\, p, \\ Auth_{AS}&= h(R_{AS},(R'_{S1}/g^{pw_{A}}), id_{A}, id_{B}), \nonumber \end{aligned}$$

  (4)

  and sends {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R'_{S2}$} to $B$.

• Step 3: $\fancyscript{C}$ intercepts the message {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R'_{S2}$} and tries to masquerade as both $B$ and $S$. To masquerade as $B$, $\fancyscript{C}$ chooses a random number $e'_{B} \in _{R} \mathbb {Z}^{*}_{q}$, and computes

  $$\begin{aligned} R'_{B}&= g^{e'_{B}} \hbox {mod}\, p, \\ K'_{B}&= R_{A}^{e'_{B}} \hbox {mod}\, p, \\ Auth'_{BA}&= h(K_{B},R_{A}). \end{aligned}$$

  To masquerade as $S$, $\fancyscript{C}$ computes

  $$\begin{aligned} R'_{SA}&= R_{A}^{e'_{S1}} \hbox {mod}\, p, \\ Auth'_{SA}&= h(R'_{SA},R'_{B}), \end{aligned}$$

  and chooses random string $Auth'_{SB}$. $\fancyscript{C}$ then sends {$R'_{B}$, $Auth'_{SA}$, $Auth'_{BA}$, $Auth'_{SB}$} to $A$.

• Step 4: After receiving the message {$R'_{B}$, $Auth'_{SA}$, $Auth'_{BA}$, $Auth'_{SB}$}, $A$ checks if

  $$\begin{aligned} h(R_{AS},R'_{B}) ?=Auth'_{SA}. \end{aligned}$$

  (5)

  If it holds, $A$ ensures that the received message was sent by $S$; then $A$ computes

  $$\begin{aligned} K_{A} = R_{B}^{e_{A}} \hbox {mod}\, p, \end{aligned}$$

  (6)

  and verifies

  $$\begin{aligned} h(K_{A},R_{A}) ?= Auth'_{BA}. \end{aligned}$$

  (7)

  If it holds, $A$ ensures that $Auth'_{BA}$ was generated by $B$, and computes $Auth_{AB} = h(K_{A},R_{B})$ and sends {$Auth'_{SB}$, $Auth_{AB}$} to $B$. Finally, $A$ computes the session key as $SK = h(K_{A}$, $id_{A}$, $id_{B})$.

• Step 5: $\fancyscript{C}$ intercepts the message {$Auth'_{SB}$, $Auth_{AB}$} and computes the session key as $SK' = h(K'_{B}$, $id_{A}$, $id_{B})$.

Fig. 3

Impersonation attack on Tso’s 3PAKE protocol

Proposition 2

By performing the above steps, the adversary $\fancyscript{C}$ can successfully masquerade as the server $S$.

Proof

The user $A$ accepts the adversary $\fancyscript{C}$ as the server $S$ if Eq. holds. We show that it holds as follows:

$$\begin{aligned} h(R_{AS},R'_{B})&= h((R'_{S1}/g^{pw_{A}})^{e_{A}}), R'_{B}) \\&= h(((g^{e'_{S1}+pw_{A}})/g^{pw_{A}})^{e_{A}}), R'_{B}) \\&= h((g^{e'_{S1}e_{A}}), R'_{B}) \\&= h(R_{A}^{e'_{S1}}, R'_{B}) \\&= h(R'_{SA}, R'_{B}) \\&=Auth'_{SA}. \end{aligned}$$

$\square$

Proposition 3

By performing the above steps, the adversary $\fancyscript{C}$ can successfully masquerade as the user $B$.

Proof

The user $A$ accepts the adversary $\fancyscript{C}$ as the user $B$ if Eq. holds. We show that it holds as follows:

$$\begin{aligned} h(K_{A},R_{A})&= h((R'^{e_{A}}_{B}), R_{A}) \\&= h((g^{e'_{B}e_{A}}), R_{A}) \\&= h((R_{A}^{e'_{B}}), R_{A}) \\&= h(K'_{B},R_{A}) \\&=Auth'_{BA}. \end{aligned}$$

$\square$

Proposition 4

By performing the above steps, the adversary $\fancyscript{C}$ can successfully establish a common session key with the user $A$.

Proof

The session key $SK$ computed by $A$ is equal to the session key $SK'$ computed by the adversary $\fancyscript{C}$, since

$$\begin{aligned} SK&= h(K_{A}, id_{A}, id_{B}) \\&= h((R'^{e_{A}}_{B}), id_{A}, id_{B}) \\&= h((g^{e'_{B}e_{A}}), id_{A}, id_{B}) \\&= h((R_{A}^{e'_{B}}), id_{A}, id_{B}) \\{}&= h(K'_{B}, id_{A}, id_{B}) \\&=SK'. \end{aligned}$$

$\square$

According to the Propositions 2, 3 and 4, Tso’s protocol is vulnerable to impersonation attacks.

4 The proposed improved 3PAKE protocol

As can be clearly seen in Sect. 3, the vulnerabilities of Tso’s scheme is due to the computation of the parameters $R_{S1}$ and $R_{S2}$. To overcome the vulnerabilities, we change the computation of these parameters as $R_{S1} = g^{e_{S1}}+g^{pw_{A}}$ and $R_{S2} = g^{e_{S2}}+g^{pw_{B}}$. The details of the proposed improved scheme, shown in Fig. 4, are described in the following steps:

• Step 1: $A$ sends the identities $id_{A}$ and $id_{B}$ to $S$ as initial request.

• Step 2: Upon receiving the messages {$id_{A}$, $id_{B}$}, $S$ chooses two random numbers $e_{S1}, e_{S2} \in _{R} \mathbb {Z}^{*}_{q}$, computes

  $$\begin{aligned} R_{S1}&= g^{e_{S1}}+g^{pw_{A}} \hbox {mod}\, p, \\ R_{S2}&= g^{e_{S2}}+g^{pw_{B}} \hbox {mod}\, p, \end{aligned}$$

  and sends {$R_{S1}$, $R_{S2}$} to $A$.

• Step 3: After receiving the message {$R_{S1}$, $R_{S2}$}, $A$ firstly retrieves $g^{e_{S1}}$ by computing $(R_{S1} - g^{pw_{A}})$ $\hbox {mod}\, p$. $A$ then chooses a random number $e_{A} \in _{R} \mathbb {Z}^{*}_{q}$ to compute

  $$\begin{aligned} R_{A}&= g^{e_{A}} \hbox {mod}\, p, \\ R_{AS}&= (g^{e_{S1}})^{e_{A}} \hbox {mod}\, p, \\ Auth_{AS}&= h(R_{AS},g^{e_{S1}}, id_{A}, id_{B}), \end{aligned}$$

  and sends {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R_{S2}$} to $B$.

• Step 4: After receiving the message {$id_{A}$, $R_{A}$, $Auth_{AS}$, $R_{S2}$}, $B$ retrieves $g^{e_{S2}}$ by computing $(R_{S2} - g^{pw_{B}})$ $\hbox {mod}\, p$. $B$ then chooses a random number $e_{B} \in _{R} \mathbb {Z}^{*}_{q}$ to compute

  $$\begin{aligned} R_{B}&= g^{e_{B}} \hbox {mod}\, p, \\ R_{BS}&= (g^{e_{S2}})^{e_{B}} \hbox {mod}\, p, \\ K_{B}&= R_{A}^{e_{B}} \hbox {mod}\, p, \\ Auth_{BS}&= h(R_{BS},g^{e_{S2}}, id_{A}, id_{B}), \\ Auth_{BA}&= h(K_{B},R_{A}), \end{aligned}$$

  and sends {$R_{A}$, $Auth_{AS}$, $R_{B}$, $Auth_{BS}$, $Auth_{BA}$} to $S$.

• Step 5: After receiving the message {$R_{A}$, $Auth_{AS}$, $R_{B}$, $Auth_{BS}$, $Auth_{BA}$}, $S$ authenticates $A$ and $B$, separately. To authenticate $A$, $S$ computes $R_{SA} = R_{A}^{e_{S1}} \hbox {mod}\, p$ and verifies $h(R_{SA}$, $g^{e_{S1}}$, $id_{A}$, $id_{B}) ?= Auth_{AS}$. To authenticate $B$, $S$ computes $R_{SB} = R_{B}^{e_{S2}} \hbox {mod}\, p$ and verifies $h(R_{SB},g^{e_{S2}}, id_{A}, id_{B}) ?= Auth_{BS}$. If the two results are positive, $S$ computes $Auth_{SA} = h(R_{SA},R_{B})$ and $Auth_{SB} = h(R_{SB},R_{A})$. Then $S$ sends {$R_{B}$, $Auth_{SA}$, $Auth_{BA}$, $Auth_{SB}$} to $A$.

• Step 6: After receiving the message {$R_{B}$, $Auth_{SA}$, $Auth_{BA}$, $Auth_{SB}$}, $A$ checks if $h(R_{AS},R_{B}) ?=Auth_{SA}$. If it holds, $S$ is authenticated by $A$; then $A$ computes $K_{A} = R_{B}^{e_{A}} \hbox {mod}\, p$, and verifies $h(K_{A},R_{A}) ?= Auth_{BA}$. If it holds, $B$ is authenticated by $A$. Then, $A$ computes$Auth_{AB} = h(K_{A},R_{B})$ and sends {$Auth_{SB}$, $Auth_{AB}$} to $B$. Finally, $A$ computes the session key as $SK = h(K_{A} , id_{A}, id_{B}) = h(g^{e_{A}e_{B}}, id_{A}, id_{B})$.

• Step 7: After receiving the message {$Auth_{SB}$, $Auth_{AB}$}, $B$ checks if $h(R_{BS},R_{A}) ?$ $=Auth_{SB}$. If it holds, $S$ is authenticated by $B$; then $B$ verifies $h(K_{B},R_{B}) ?= Auth_{AB}$. If it holds, $A$ is authenticated by $B$. Finally, $B$ computes the session key as $SK = h(K_{B} , id_{A}, id_{B}) = h(g^{e_{A}e_{B}}, id_{A}, id_{B})$.

Fig. 4

The improved 3PAKE protocol

5 Security analysis of the improved protocol

In this section, we show that our improved protocol is secure in the random oracle model. We start with the formal security model and the algorithm assumption that will be used in our proof.

5.1 Security model

In order to make our scheme resist the known attacks to 3PAKE protocol, we use the method of provable security. The security proof is based on the model proposed by Abdalla and Pointcheval [43]. The model that we use is as follows.

5.1.1 Participants

A 3PAKE protocol $\Pi$ runs in a network of a number of interconnected participants where each participant is either a client $U \in \fancyscript{U}$ or a trusted server $S \in \fancyscript{S}$. The set $\fancyscript{S}$ is assumed to involve only a single server for simplicity. Each of the participants may have several instances called oracles involved in distinct executions of the protocol $\Pi$. We refer to $i$th instance of $U$ (resp. $S$) in a session as $\Pi ^{i}_{U}$ (resp. $\Pi ^{i}_{S}$). Every instance $\Pi ^{i}_{U}$ (resp. $\Pi ^{j}_{S}$) has a partner ID $pid^{i}_{U}$ (resp:$pid^{j}_{S}$), a session ID $sid^{i}_{U}$ (resp:$sid^{j}_{S}$), and a session key $sk^{i}_{U}$ (resp:$sk^{j}_{S}$). $pid^{i}_{U}$ (resp:$pid^{j}_{S}$) denotes the set of the identities that are involved in this instance. $sid^{i}_{U}$ (resp:$sid^{j}_{S}$) denotes the flows that are sent and received by the instance $\Pi ^{i}_{U}$ (resp. $\Pi ^{j}_{S}$). An instance $\Pi ^{i}_{U}$ (resp. $\Pi ^{i}_{S}$) is said to be accepted if it holds a session key $sk^{i}_{U}$ (resp:$sk^{j}_{S}$), a session identifier $sid^{i}_{U}$ (resp:$sid^{j}_{S}$), and a partner identifier $pid^{i}_{U}$ (resp:$pid^{j}_{S}$). Two instances $\Pi ^{i}_{U_{1}}$ and $\Pi ^{j}_{U_{2}}$ are considered partnered if and only if (1) both of them have accepted, (2) $pid^{i}_{U_{1}} = pid^{j}_{U_{2}}$, (3) $sid^{i}_{U_{1}} = sid^{j}_{U_{2}}$, (4) $sk^{i}_{U_{1}} = sk^{j}_{U_{2}}$.

5.1.2 Long-lived keys

Each client $U \in \fancyscript{U}$ holds a password $pw_{U}$. Each server $S \in \fancyscript{S}$ holds a vector $pw_{S}= \langle pw_{U} \rangle _{U \in \fancyscript{U}}$ with an entry for each client.

5.1.3 Adversary model

The communication network is assumed to be fully controlled by an adversary $\fancyscript{M}$, which schedules and mediates the sessions among all the parties. The adversary $\fancyscript{M}$ is allowed to issue the following queries in any order:

• Execute($\Pi ^{i}_{U_{1}}$, $\Pi ^{j}_{U_{2}}$, $\Pi ^{k}_{S}$): This query models passive attacks in which the attacker eavesdrops on honest executions among the client instances $\Pi ^{i}_{U_{1}}$ and $\Pi ^{j}_{U_{2}}$ and trusted server instance $\Pi ^{k}_{S}$. The output of this query consists of the messages that were exchanged during the honest execution of the protocol $\Pi$.

• SendClient($\Pi ^{i}_{U}$, $m$): The adversary makes this query to intercept a message and then modify it, create a new one, or simply forward it to the client instance $\Pi ^{i}_{U}$. The output of this query is the message that the client instance $\Pi ^{i}_{U}$ would generate upon receipt of message $m$. Additionally, the adversary is allowed to initiate the protocol by invoking SendClient($\Pi ^{i}_{U_{1}},(U_{1},Start)$).

• SendServer($\Pi ^{i}_{S}$, $m$): This query models an active attack against a server. The adversary makes this query to obtain the message that the server instance $\Pi ^{i}_{S}$ would generate on receipt of the message $m$.

• Reveal($\Pi ^{i}_{U}$): This query models the known session key attack. The adversary makes this query to obtain the session key of the instance $\Pi ^{i}_{U}$.

• Corrupt($U$): This query returns to the adversary the long-lived key $pw_{U}$ for participant $U$.

• Test($\Pi ^{i}_{U}$): Only one query of this form is allowed to be made by the adversary to a fresh oracle. To respond to this query, a random bit $b \in \{0,1\}$ is selected. If $b = 1$, then the session key held by $\Pi ^{i}_{U}$ is returned. Otherwise, a uniformly chosen random value is returned.

5.1.4 Fresh oracle

An oracle $\Pi ^{i}_{U}$ is called fresh if and only if the following conditions hold: (1) $\Pi ^{i}_{U}$ has accepted; (2) $\Pi ^{i}_{U}$ or its partner (if exists) has not been asked a Reveal query after their acceptance; and (3) the client who has a partner instance with $\Pi ^{i}_{U}$, has not been issued a Corrupt query.

5.1.5 3PAKE security

The security of a 3PAKE protocol $\Pi$ is modeled by the game $Game^{3pake}(\Pi ,\fancyscript{M})$. When playing this game, $\fancyscript{M}$ can make many queries mentioned earlier to $\Pi ^{i}_{U}$ and $\Pi ^{j}_{S}$. If $\fancyscript{M}$ asks a single test query, Test($\Pi ^{i}_{U}$), where $\Pi ^{i}_{U}$ has accepted and is fresh, then $\fancyscript{M}$ outputs a single bit $b'$. The aim of $\fancyscript{M}$ is correctly guessing the bit $b$ in the test session. More precisely, we define the advantage of $\fancyscript{M}$ as follows:

$$\begin{aligned} Adv^{3pake}_{\Pi ,D}(\fancyscript{M})=|2Pr[b'=b]- 1|. \end{aligned}$$

(8)

The protocol $\Pi$ is said to be 3PAKE-secure if $Adv^{3pake}_{\Pi ,D}(\fancyscript{M})$ only negligibly larger than $O(q_{send})/|D|$, where $q_{send}$ is the number of the Send queries, and $|D|$ is the size of the password dictionary.

5.2 Computational assumption

We define the decisional Diffie–Hellman (DDH) assumption which we use in the security proof of our scheme.

5.2.1 Decisional Diffie–Hellman (DDH)

The DDH assumption can be precisely defined by two experiments, $Exp^{cddh-real}_{\alpha ,p} (W)$ and $Exp^{cddh-rand}_{\alpha ,p} (W)$. An adversary $W$ is provided with $g^{u} \hbox {mod}\, p$, $g^{v} \hbox {mod}\, p$ and $g^{uv} \hbox {mod}\, p$ in the experiment $Exp^{cddh-real}_{\alpha ,p} (W)$, and $g^{u} \hbox {mod}\, p$, $g^{v} \hbox {mod}\, p$ and $g^{w} \hbox {mod}\, p$ in the experiment $Exp^{cddh-rand}_{\alpha ,p} (W)$, where $u$, $v$ and $w$ are drawn at random from $\mathbb {Z}^{*}_{q}$. Define the advantage of $W$ in violating the DDH assumption, $Adv^{cddh}_{\alpha ,p} (W)$, as follows:

$$\begin{aligned} Adv^{ddh}_{\alpha ,p} (W)&= \max \{| Pr[Exp^{ddh-real}_{\alpha ,p} (W) = 1]\\&- Pr[Exp^{cddh-rand}_{\alpha ,p} (W) = 1]|\}. \end{aligned}$$

5.3 Security proof

Theorem 1

Let $D$ be a uniformly distributed dictionary of size $|D|$. Let $\Pi$ describes the 3PAKE protocol defined in Fig. 4. Suppose that DDH assumption holds, then,

$$\begin{aligned} Adv^{3pake}_{\Pi ,D}(\fancyscript{M})&\le \frac{q^{2}_{h}}{2^{l}} + \frac{(q_{s}+q_{e})^{2}}{p^{2}} + 2q_{e} \cdot Adv^{DDH}(W)\\&+2\max \left\{ \frac{q_{h}}{p}, \frac{q_{s}}{|D|}+\frac{q_{s}}{2^{l}}\right\} \end{aligned}$$

where $q_{s}$ denotes the number of Send queries; $q_{e}$ denotes the number of Execute queries; $q_{h}$ denotes the number of hash queries to $h$.

Proof

This proof consists of a sequence of hybrid games, starting at the real attack $G_{0}$ and ending up at game $G_{4}$ where the adversary has no advantage. For each game $G_{i} (0\le i\le 4)$, we define $Succ_{i}$ as the event that $\fancyscript{M}$ correctly guesses the bit $b$ in the test session.

• Game $G_{0}$. This game is the real protocol, in the random-oracle model. In this game, all the instances of $A$ and $B$ and the trusted server $S$ are modeled as the real execution in the random oracle. By definition of event $Succ_{i}$, which means that the adversary correctly guesses the bit $b$ involved in the Test-query, we have

  $$\begin{aligned} Adv^{3pake}_{\Pi ,D}(\fancyscript{M})=2|\Pr [Succ_{0}]- \frac{1}{2}|. \end{aligned}$$

  (9)

• Game $G_{1}$. This game is as the same as the game $G_{0}$ except that we simulate the hash oracle $h$ as usual by maintaining hash list $h_{List}$ with entries of the form (Inp, Outp). On hash query $h$(Inp) for which there exists a record (Inp, Outp) in the list $h_{List}$, return Outp. Otherwise, randomly choose Outp $\in \{0,1\}^{l}$, send it to $\fancyscript{M}$ and store the new tuple (Inp, Outp) into $h_{List}$. We also simulate all the instances, as the real players would do, for the Send-query and for the Execute, SendClient, SendServer, Reveal, Corrupt and Test queries. From the viewpoint of the adversary, we easily see that the game is perfectly indistinguishable from the real attack. Hence,

  $$\begin{aligned} \Pr [Succ_{1}]=\Pr [Succ_{0}]. \end{aligned}$$

  (10)

• Game $G_{2}$. In this game, we simulate all the oracles in game $G_{1}$, except we cancel the game in which some collisions appear on the partial transcripts $(R_{A}, R_{S1})$, $(R_{B}, R_{S2})$ or $(R_{A}, R_{B})$ and on hash values. According to the birthday paradox, the probability of collisions in output of $h$ oracle is at most ${q^{2}_{h}}/{2^{l+1}}$, where $q_{h}$ denotes the maximum number of queries to $h$. Similarly, the probability of collisions in the transcripts is at most ${(q_{s}+q_{e})^{2}}/{(2p^{2})}$, where $q_{s}$ represents the number of queries to the SendClient and SendServer oracles and $q_{e}$ represents the number of queries to the Execute oracle. So we have

  $$\begin{aligned} |\Pr [Succ_{2}]-\Pr [Succ_{1}]|\le \frac{q^{2}_{h}}{2^{l+1}} + \frac{(q_{s}+q_{e})^{2}}{2p^{2}} .\end{aligned}$$

  (11)

• Game $G_{3}$. In this game, we change the simulation of queries to the SendClient oracle. First, we randomly select a session executed by some honest clients $A$ and $B$ for partner instances $\Pi ^{i}_{A}$ and $\Pi ^{j}_{B}$.

• When SendClient($\Pi ^{i}_{A}, (B,Start)$) is asked, we return $\{id_{A},id_{B}\}$ to $\fancyscript{M}$.

• When SendClient($\Pi ^{i}_{A}, (R_{S1}, R_{S2})$) is asked, we randomly select $u \in \mathbb {Z}^{*}_{q}$, and compute $R_{A} = g^{u} \hbox {mod}\, p$, $R_{AS} = (R_{S1} - g^{pw_{A}})^{u} \hbox {mod}\, p$ and $Auth_{AS}$ as the real protocol. Then, we return $\{id_{A}, R_{A}, Auth_{AS}, R_{S2}\}$ to $\fancyscript{M}$.

• When SendClient($\Pi ^{j}_{B}, (id_{A}, R_{A}, Auth_{AS}, R_{S2})$) is asked, we randomly choose $v \in \mathbb {Z}^{*}_{q}$, compute $R_{B} = g^{v} \hbox {mod}\, p$, $K_{B} = R_{A}^{v} = g^{uv} \hbox {mod}\, p$, $R_{BS}$, $Auth_{BS}$ and $Auth_{BA}$ like the real protocol, and return $\{R_{A}$, $Auth_{AS}$, $R_{B}$, $Auth_{BS}$, $Auth_{BA}$} to $\fancyscript{M}$.

• When SendClient $(\Pi ^{i}_{A}$, $(R_{B}$, $Auth_{SA}$, $Auth_{BA}$, $Auth_{SB}$)) is asked, we compute $K_{A}=R_{B}^{u} = g^{uv} \hbox {mod}\, p$, $Auth_{AB}$ and the session key $SK$ like the real protocol, and return $\{Auth_{SB}, Auth_{AB}\}$ to $\fancyscript{M}$.

So, it can be easily seen that this game is perfectly indistinguishable from the previous game $G_{2}$. Hence,

$$\begin{aligned} \Pr [Succ_{3}]=\Pr [Succ_{2}]. \end{aligned}$$

(12)

• Game $G_{4}$. In this game, we once again change the simulation of queries to the SendClient oracle for the selected session in game $G_{3}$. This time, we change the way we compute the values $K_{A}$ and $K_{B}$ so that they become independent of passwords and ephemeral keys. When SendClient $(\Pi ^{j}_{B}$, $(id_{A}, R_{A}, Auth_{AS}, R_{S2}))$ and SendClient $(\Pi ^{i}_{A}$, $(R_{B}$, $Auth_{SA}$, $Auth_{BA}$, $Auth_{SB}))$ are asked, we set $K_{A} = K_{B} = T_{w}(\alpha )$, where $w$ is selected from $\mathbb {Z}^{*}_{p}$ at random. The difference between the game $G_{4}$ and the game $G_{3}$ is as follows:

  $$\begin{aligned} |\Pr [Succ_{4}]-\Pr [Succ_{3}]|\le q_{exe} \cdot Adv_{\alpha ,p}^{DDH}(W). \end{aligned}$$

  (13)

$\square$

Proof

By assuming a successful adversary $\fancyscript{M}$ to distinguish $G_{3}$ and $G_{4}$, we construct a DDH solver $W$. The only difference between $G_{3}$ and $G_{4}$ is in the computation of $K_{A}$ and $K_{B}$ for the selected session. First time, $W$ obtains a DDH tuple $(g^{u},g^{v},Z)$. As $G_{3}$ and $G_{4}$, the solver $W$ selects a matching session for $\Pi ^{i}_{A}$ and $\Pi ^{j}_{B}$ executed by the honest clients $A$ and $B$. Then, when SendClient($\Pi ^{i}_{A}, (R_{S1}, R_{S2})$) is asked, the solver $W$ sets $R_{A} = g^{u} \hbox {mod}\, p$. Also, when SendClient($\Pi ^{j}_{B}, (id_{A}, R_{A}, Auth_{AS}, R_{S2})$) and SendClient($\Pi ^{i}_{A}$, $(R_{B}$, $Auth_{SA}$, $Auth_{BA}$, $Auth_{SB}$)) are asked, the solver $W$ sets $R_{B} = g^{v} \hbox {mod}\, p$ and $K_{A} = K_{B} = Z$. For all other queries, the solver $W$ treats as $G_{3}$ and $G_{4}$.

The probability that the distinguisher $\fancyscript{M}$ picks the selected session as the test session, (i.e., the adversary asks Test $(\Pi ^{i}_{A})$ or Test($\Pi ^{j}_{B}$)) is ${1}/{q_{exe}}$. So, the solver $W$ simulates all oracle queries without knowing $u$ and $v$. From the obtained information, the distinguisher $\fancyscript{M}$ can compute ($R_{A} = g^{u} \hbox {mod}\, p$, $R_{B} = g^{v} \hbox {mod}\, p$) but cannot compute $K_{A} = K_{B}$. In the case of $Z = g^{uv} \hbox {mod}\, p$, this environment for the distinguisher is equivalent to $G_{3}$. In the case of $Z = g^{w} \hbox {mod}\, p$, this environment for the distinguisher is equivalent to $G_{4}$.

Finally, if the distinguisher decides that he interacted with $G_{3}$, then the solver $W$ decides that $Z= g^{uv} \hbox {mod}\, p$. And, if the distinguisher decides that he interacted with $G_{4}$, then the solver $W$ decides that $Z\ne g^{uv} \hbox {mod}\, p$. Hence,

$$\begin{aligned} |\Pr [Succ_{4}]-\Pr [Succ_{3}]|\le q_{exe} \cdot Adv_{\alpha ,p}^{DDH}(W). \end{aligned}$$

$\square$

In game $G_{4}$, Diffie–Hellman keys $K_{A}$ and $K_{B}$ are random and independent with passwords and ephemeral keys. So, there are three possible cases where the adversary distinguishes the real session key and the random key as follows:

• Case 1. The adversary queries $(g^{w}, id_{A}, id_{B})$ to $h$. The probability that this event occurs is $q_{h}/l$.

• Case 2. The adversary asks SendClient query except SendClient($\Pi ^{j}_{B}$, $m$) and successfully impersonates $A$ to $B$. The adversary is allowed to reveal the static key $pw_{B}$ of $B$ but it is not allowed to reveal static key $pw_{A}$ of $A$. Thus, in order to impersonate $A$, the adversary has to obtain some information of the password $pw_{A}$ of $A$. The probability is $1/|D|$. If the adversary just makes an attempt at random to impersonate $A$ by computing $R_{AS}$ and succeeds, it will make the difference but the probability is less than $1/2^{l}$. Since there are at most $q_{s}$ sessions of this kind, the probability that this event occurs is lower than $q_{s}/|D|+q_{s}/2^{l}$

• Case 3. The adversary asks SendClient query except SendClient($\Pi ^{i}_{A}$, $m$) and successfully impersonates $B$ to $A$. Similar to Case 1, the probability that this event occurs is lower than $q_{s}/|D|+q_{s}/2^{l}$.

As a conclusion,

$$\begin{aligned} \Pr [Succ_{4}]=\frac{1}{2}+\max \left\{ \frac{q_{H}}{p}, \frac{q_{s}}{|D|}+\frac{q_{s}}{2^{l}}\right\} . \end{aligned}$$

(14)

Combining all the above equations, one gets the announced result as follows:

$$\begin{aligned} Adv^{3pake}_{\Pi ,D}(\fancyscript{M})&= 2|\Pr [Succ_{0}]- \frac{1}{2}|\\&= 2\left| \Pr [Succ_{0}]- \Pr [Succ_{4}]+\max \left\{ \frac{q_{h}}{l}, \frac{q_{s}}{|D|}+\frac{q_{s}}{2^{l}}\right\} \right| \\&\le 2\left( |\Pr [Succ_{0}]- \Pr [Succ_{4}]|+\max \left\{ \frac{q_{h}}{l}, \frac{q_{s}}{|D|}+\frac{q_{s}}{2^{l}}\right\} \right) \\&\le 2\left( |\Pr [Succ_{1}]- \Pr [Succ_{2}]| + |\Pr [Succ_{3}]- \Pr [Succ_{4}]|\right. \\&\left. +\max \left\{ \frac{q_{h}}{p}, \frac{q_{s}}{|D|}+\frac{q_{s}}{2^{l}}\right\} \right) \\&\le \frac{q^{2}_{h}}{2^{l}} + \frac{(q_{s}+q_{e})^{2}}{p^{2}} + 2q_{e} \cdot Adv^{DDH}(W)\\&+2\max \left\{ \frac{q_{h}}{p}, \frac{q_{s}}{|D|}+\frac{q_{s}}{2^{l}}\right\} \end{aligned}$$

6 Performance and security comparison

We evaluate the performance and security of our proposed protocol and make comparisons with some 3PAKE protocols which use neither symmetric key cryptography nor server public key. Table 2 shows the performance comparisons of our protocol and Chang et al.’s protocol [41] and Tso’s protocol [42]. Two main operations are adopted in this analysis and they are defined as follows. $H$: the hash function operation; $_{M}$: the modular exponentiation operation. In the proposed protocol, we assume that the server computes and stores $g^{pw_{U}} \hbox {mod}\, p$ for each user $U$ in the registration phase. Thus, when the server wants to use $g^{pw_{U}}$, it is not needed to compute a modular exponentiation. According to this assumption, the computational cost of our protocol is same as Tso’s protocol and equal to 12M + 14H.

Table 2 Computation comparison

Table 3 lists the security comparisons among our proposed protocol and other related protocols. It demonstrates that our protocol has many excellent features and is more secure than other related protocols.

Table 3 Security comparison

7 Conclusions

In this paper, we briefly reviewed Tso’s 3PAKE protocol. We demonstrated that Tso’s scheme is vulnerable to off-line password guessing attack. Additionally, we pointed out that Tso’s scheme also suffers from impersonation attack. Therefore, we proposed an improved scheme to overcome the security weaknesses of the related schemes and proved its security in the random oracle model.