A Provably Secure Multi-server Based Authentication Scheme

Abstract

With the rapid growth of electronic commerce and demand on variants of Internet based applications, the system providing resources and business services often consists of many servers around the world. So far, a variety of authentication schemes have been published to achieve remote user authentication on multi-server communication environment. Recently, Pippal et al. proposed a multi-server based authentication protocol to pursue the system security and computation efficiency. Nevertheless, based on our analysis, the proposed scheme is insecure against user impersonation attack, server counterfeit attack, and man-in-the-middle attack. In this study, we first demonstrate how these malicious attacks can be invoked by an adversary. Then, a security enhanced authentication protocol is developed to eliminate all identified weaknesses. Meanwhile, the proposed protocol can achieve the same order of computation complexity as Pippal et al.’s protocol does.

1 Introduction

Following the advances in network technologies and the widespread distribution of remote system backup, lots of multi-server based applications have been deployed to make legitimate user access network service more conveniently and efficiently. As password based authentication scheme provides an efficient and accurate way to identify valid remote user and at the same time preserves the secrecy of communication, a lot of password based authentication mechanisms have been investigated in these years. However, once the scale of the networks becomes larger, the authentication scheme which supports the circumstance of single-server architecture does not suffice for users’ need anymore. This may limit the future development and pervasive usage of existing Internet based applications. For example, to pursue the reliability and efficiency in a resource acquiring process, the remote service system often consists of many servers located at different places. The single-server based authentication protocols will be in-efficient on multi-server communication architecture. In addition, a legal user, who intends to access distinct network services, must register with the services providers (or servers) in advance and memorize all corresponding identities and passwords. This inconvenience will impede the pervasive usage of such multi-server based application systems. Hence, providing a secure and efficient authentication mechanism compatible to multi-server architecture will be crucial for future service systems.

Due to the difficult tradeoff between security robustness and computation complexity, it is a particular challenge to design an authentication scheme which simultaneously possesses system reliability and performance efficiency. The research community has promptly focused on this research area in these years. In 2004, Juang [9] developed a key agreement based authentication protocol which allows legal remote user to register only once and then access network services from distinct servers efficiently. Later, Chang and Lee [4] presented an improved version of Juang’s protocol to pursue better system efficiency without losing any security robustness. Next year, Ku et al. [10] showed that Juang’s protocol cannot withstand insider attack and provide forward secrecy. Later, Liao and Wang [13] proposed a dynamic ID based remote user authentication scheme. However, Hsiang and Shih [8] demonstrated that Liao–Wang’s scheme is insecure against insider attack, impersonation attack, server spoofing attack and cannot provide mutual authentication. Later, Sood et al. [15] pointed out that Hsiang–Shih’s scheme cannot resist to replay attack, impersonation attack and stolen smart card attack. In addition, the authors proposed a security enhanced scheme. Nevertheless, this scheme is vulnerable to stolen smart card attack and leak of verifier attack [6, 12]. In 2012, Wang and Ma [17] presented a smart card based authentication scheme for multi-server architecture. The authors claimed that their scheme is able to resist replay attack, offline dictionary attack, server spoofing attack and impersonation attack. Unfortunately, the proposed scheme cannot withstand server spoofing attack, impersonation attack, privileged insider attack and off-line password guessing attack [7]. At the same year, Tsai et al. [16] introduced a multi-server based authentication scheme to withstand password guessing attack. The authors claimed that the proposed scheme can resist to undetectable on-line password guessing attack. However, the undetectable on-line password guessing attack is a natural weakness in password based authentication scheme [18]. Recently, Pippal et al. [14] proposed a smart card based authentication scheme for multi-server architecture. The authors claimed that their scheme can withstand various attacks such as user impersonation attack, server spoofing attack, replay attack, reflection and parallel session attacks, password guessing attack, insider attack, smart card loss attack, stolen verifier attack and known session key attack. Nevertheless, we find that Pippal et al.’s scheme is vulnerable to server counterfeit attack, user impersonation attack and man-in-the-middle attack. All of these weaknesses will be presented in the following sections.

2 Review of PTJ Scheme

In this section, we review the authentication process of Pippal et al.’s scheme [14].

2.1 Initialization Phase

The registration center RC selects two 1,024-bits prime numbers $p$ and $q$ and a generator $g \in Z_{N}^*$ and computes $N= p \times q$, where $Z_{N}^*=(g|1\le g \le N -1, gcd (g,N)=1)$. Next, RC generates $k$ random numbers ($r_{1}$, $r_{2}$, ..., $r_{k})$ for $k$ servers, respectively. Note that $gcd (r_{i}, r_{j})= 1,gcd (r_{i},\emptyset (N))=1$ , where $1 \le i,j\le k,i \ne j$ . After that, RC computes secret key $S_j=g^{{\Pi _{i=1, i\ne j}^K }r_j}mod \,\,N$ and $t=\frac{1}{g^{\mathop \prod \nolimits _{i=1}^k r_i } mod \,\,N}$ for every server $S_{j}$.

2.2 Server Registration Phase

In this phase, the server $S_{j}$ submits ${\textit{SID}}_{j}$ to RC over a secure channel. Once receiving the registration request from $S_{j}$, RC assigns $r_{j}$ to $S_{j}$ and sends {$r_{j}, t, g, N, h$(.)} to $S_{j}$ via a secure channel.

2.3 User Registration Phase

In this phase, the user $U_{i}$ submits {${\textit{UID}}_{i}, {\textit{PW}}_{i}$} to RC which then computes $P=h$(${\textit{UID}}_{i} \Vert {\textit{PW}}_{i} \Vert t)$ and issues a smart card to $U_{i}$. Note that {($s_{1}, s_{2}$, ..., $s_{k}), t, g, N, P, h$(.)} is stored in this smart card’s memory.

2.4 Login and Authentication Phase (Fig. 1)

When $U_{i}$ wants to access $S_{j}, U_{i}$ inserts his/her smart card into the card reader and inputs his/her identity ${\textit{UID}}_{i} ^{\prime }$ and password ${\textit{PW}}_{i} ^{\prime }$. The smart card then calculates $P^{\prime } =h ({\textit{UID}}_{i} ^{\prime }\Vert {\textit{PW}}_{i}^{\prime }\Vert t)$ and checks whether $P ^{\prime }$ equals to stored $P$ or not. If it holds, $U_{i}$ is authenticated. Next, the smart card generates a random nonce $a$, computes, $A=g^{a} mod \,\, N, M_{1}=(s_{j}^{{\textit{UID}}_{i} \times {{\textit{SID}}_{j}}} \times A)\, mod \,\, N$, and sends {${\textit{UID}}_{i}, M_{1}$} to $S_{j}$. Upon receiving {${\textit{UID}}_{i}, M_1$}, $S_{j}$ verifies ${\textit{UID}}_{i}$. If it is valid, $S_{j}$ generates a random nonce $b$, performs the computations of $B, K, {\textit{SKey}}_{(i,j)}$, and $M_2$. After that, $S_{j}$ sends the response {$B, M_{2}$} to $U_{i}$.

$$\begin{aligned} B&= g^{b\times r_j } mod\,\, N;\\ K&= \left( {\left( {M_1 ^{\left( {r_j } \right) }\times t^{\left( {{\textit{UID}}_i \times {\textit{SID}}_j } \right) }} \right) mod\,\, N} \right) ^{b}=g^{(a\times b\times r_j )} mod\,\, N;\\&{\textit{SKey}}_{(i, j)} =h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j );\\ M_2&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert B \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) . \end{aligned}$$

Once $U_{i}$ receives {$B, M_{2}$}, $U_{i}$ first performs the following computations and then checks whether computed $M_2 {^{\prime }}$ equals to received $M_2$ or not. If it holds, $S_{j}$ is authenticated.

$$\begin{aligned} K&= \left( B \right) ^{a} mod\,\, N=\left( {g^{b\times r_j }} \right) ^{a} mod \,\, N= g^{(a\times b\times r_j )} mod\,\, N;\\&{\textit{SKey}}_{(i, j)} =h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j );\\ {M_2^{{\prime }}}&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert B \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) \end{aligned}$$

Subsequently, $U_{i}$ computes $M_3$ and sends it to $S_{j}$. Finally, $S_{j}$ calculates $M_3 ^{{\prime }}$ and checks whether computed $M_3 ^{{\prime }}$ is equal to received $M_3$ or not. If it holds, mutal authentication is achieved. Both $U_{i}$ and $S_{j}$ agree upon a common session key ${\textit{SKey}}_{(i, j)}$.

$$\begin{aligned} M_3&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert {A\Vert B} \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) ;\\ M_3^{{\prime }}&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j\Vert {A\Vert B} \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) \end{aligned}$$

Fig. 1

PTJ scheme

2.5 Password Change Phase

When $U_{i}$ wants to change the password. $U_{i}$ inserts the smart card into the card reader and keys in ${\textit{UID}}_{i} ^{\prime }$ and ${\textit{PW}}_{i}^{{\prime }}$. The smart card computes $P^{{\prime }}=h( {\textit{UID}}_{i}^{{\prime }}\Vert {\textit{PW}}_{i}^{{\prime }}\Vert t)$ and checks whether $P^{\prime }$ equals to stored $P$ or not. If it holds, $U_{i}$ is legitimate. After that, $U_{i}$ is allowed to enter a new password ${\textit{PW}}_{\text {inew}}$, and the card reader computes $P_{new}=h({\textit{UID}}_{i}\Vert {\textit{PW}}_{\text {inew}}\Vert t)$ and stores $P_{new}$ in the smart card’s memory.

3 Vulnerabilities of PTJ Scheme

3.1 Server Counterfeit Attack

Suppose there exists a legal but malicious user $U_{k}$ possessing a smart card with {($s_{1}, s_{2}$, ..., $s_{k}), t, g, N, P_{k}, h(.)$}, where $P_{k}=h({\textit{UID}}_{k} \Vert {\textit{PW}}_{k}\Vert t)$. Once $U_{k}$ intends to launch a server counterfeit attack, $U_{k}$ can perform the following steps to cheat $U_{i}$ that he/she is $S_{j}$.

• Step 1: During a normal authentication session between $U_{i}$ and $S_{j}, U_{k}$ interrupts $\{{\textit{UID}}_{i}, M_1\}$, where $M_1 =(s_j^{{\textit{UID}}_i \times {\textit{SID}}_j } \times A) mod \,\, N$ and $A=g^{a} mod \,\, N$.

• Step 2: $U_{k}$ computes the following values.

  • 1. $B=g^{b} mod\,\, N$ with a random nonce $b$.

  • 2. $K=\left( {\left( {M_1 \times \frac{1}{s_j }^{\left( {{\textit{UID}}_i \times {\textit{SID}}_j } \right) }} \right) mod \,\, N} \right) ^{b}=g^{(a\times b)} mod \,\, N.$

  • 3. ${\textit{SKey}}_{(i, j)} =h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j ).$ Note that ${\textit{SID}}_{j}$ is a public value.

  • 4. $M_2 =h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert B \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right)$

  After that, $U_{k}$ pretends that he/she is $S_{j}$ and sends the response $\{B, M_{2}\}$ to $U_{i}$.

• Step 3: With $\{B, M_{2}\}$, $U_{i}$ performs the following verification.

  • 1. $K=\left( B \right) ^{a} mod \,\, N=\left( {g^{b}} \right) ^{a} mod \,\, N= g^{(a\times b)} mod \,\, N$

  • 2. ${\textit{SKey}}_{\left( {i, j} \right) } =h\left( {K\Vert {{\textit{UID}}_i } \Vert {\textit{SID}}_j } \right)$

  • 3. $M_2 ^{{\prime }}= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert B \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right)$

  • 4. Check $M_2 ^{{\prime }}=M_2 ?$

  It is obvious that this verification will be passed. Next, $U_{i}$ sends $M_3$ to $S_{j}$.

• Step 4: $U_{k}$ interrupts $M_3$. So far, $U_{i}$ misunderstands that he/she is communicating with $S_{j}$ (actually it is $U_{k})$. In addition, $U_{i}$ believes that he/she and $S_{j}$ share a session key ${\textit{SKey}}_{\left( {i, j} \right) } =h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j } \right)$, where $K= g^{(a\times b)} mod \,\, N$. However, this session key is shared between $U_{i}$ and $U_{k}$. Hence, we conclude that the server counterfeit attack can successfully be launched on PTJ scheme.

3.2 User Impersonation Attack

Suppose there exists a legal but malicious user $U_{k}$ possessing a smart card with {($s_{1}$, $s_{2}$, ..., $s_{k})$, $t, g, N, P_{k}, h$(.)}, where $P_{k}=h({\textit{UID}}_{k}\Vert {\textit{PW}}_{k}\Vert t)$. It is obvious that $U_{k}$ can easily cheat $S_{j}$ that he/she is $U_{i}$ with eavesdropped ${\textit{UID}}_{i}$. This is because $U_{k}$ possesses all the parameters {($s_{1}, s_{2}$, ..., $s_{k}), t, g, N, P_{k}, h$(.)}. With the eavesdropped ${\textit{UID}}_{i}, U_{k}$ has the ability to create any legal message involved with $U_{i}$. Note that as ${\textit{UID}}_{i}$ is transmitted in public, ${\textit{UID}}_{i}$ is easily to obtain. In more details, $U_{k}$ can choose a random nonce $a$, and compute $A=g^{a} mod \,\, N, M_1 =(s_j^{{\textit{UID}}_i \times {\textit{SID}}_j } \times A) mod \,\, N$, and impersonates $U_{i}$ to send {${\textit{UID}}_{i}, M_1$} to $S_{j}$. This cheating can easily be achieved as {($s_{1}, s_{2}$, ..., $s_{k}), t, g, N, P, h$(.)} is also stored in the memory of $U_{k}$’s smart card. Hence, we can conclude that the user impersonation attack cannot be avoided in PTJ scheme.

3.3 Man-in-the-Middle Attack

Suppose there exists a legal but malicious user $U_{k}$ possessing a smart card with {($s_{1}, s_{2}$, ..., $s_{k}), t, g, N$, $P_{k}, h$(.)}, where $P_{k}=h({\textit{UID}}_{k}\Vert {\textit{PW}}_{k}\Vert t)$. Now we utilize the following steps to demonstrate a man-in-the-middle attack. That is, $U_{k }$ can exploit its man-in-the-middle status to cheat $U_{i}$ and $S_{j}$ at the same time (Fig. 2).

Fig. 2

Man-in-the-middle attack on PTJ scheme

• Step 1: The smart card at $U_{i}$ side generates a random nonce $a$, computes $A=g^{a} mod \,\,N, M_1 =(s_j^{{\textit{UID}}_i \times {\textit{SID}}_j } \times A) mod \,\,N$, and sends {${\textit{UID}}_{i}, M_1$} to $S_{j}$.

• Step 2: $U_{k}$ interrupts {${\textit{UID}}_{i}, M_1$}, and generates a random nonce $a'$, computes $A{^{\prime }}=g^{a^{{\prime }}} mod \,\,N$, $M_1 ^{{\prime }}=(s_j^{{\textit{UID}}_i \times {\textit{SID}}_j } \times A{^{\prime }}) mod \,\,N$, and sends {${\textit{UID}}_{i}, M_1 ^{{\prime }}$} to $S_{j}$.

• Step 3: $S_{j}$ verifies ${\textit{UID}}_{i}$, and generates a random nonce $b$, computates values $B, K, {\textit{SKey}}_{(i, j)}$, and $M_2$. Next, $S_{j}$ sends the response {$B, M_{2}$} back to $U_{i}$.

  $$\begin{aligned} B&= g^{b\times r_j } mod \,\, N;\\ K&= \left( {\left( {M_1^{{{\prime }}{\left( {r_j } \right) }}\times t^{\left( {{\textit{UID}}_i \times {\textit{SID}}_j } \right) }} \right) mod \,\,N} \right) ^{b}=g^{({a^{{\prime }}}\times b\times r_j )} mod \,\,N;\\ {\textit{SKey}}_{(i, j)}&= h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j );\\ M_2&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert B \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) . \end{aligned}$$

• Step 4: $U_{k}$ interrupts {$B$, $M_{2}$}, and computes values $K, {\textit{SKey}}_{(i, j)}$, and $M_3 ^{{\prime }}$. Then, $U_{k}$ sends $M_3 ^{{\prime }}$ to $S_{j}$. Obviously, the verification of $M_3 ^{{\prime }}$ will be passed at the $S_{j}$ side.

  $$\begin{aligned} K&= \left( B \right) ^{a^{{\prime }}} mod \,\, N=\left( {g^{b\times r_j }} \right) ^{a^{{\prime }}} mod \,\,N= g^{(a^{{\prime }}\times b\times r_j )} mod \,\,N;\\&{\textit{SKey}}_{(i, j)} =h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j );\\ M_3 ^{{\prime }}&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert {A\Vert B} \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) \end{aligned}$$

  Now, $U_{k}$ and $S_{j}$ share a session key ${\textit{SKey}}_{(i, j)} =h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j )$, where $K=g^{(a^{{\prime }}\times b\times r_j )} mod \,\, N$.

• Step 5: $U_{k}$ computes values $B{^{\prime }}$, $K{^{\prime }}$, ${\textit{SKey}}_{(i, j)} {^{\prime }}$, and $M_2 ^{{\prime }}$. After that, $U_{k}$ sends {$B{^{\prime }}$, $M_2 ^{{\prime }}$} to $U_{i}$.

  $$\begin{aligned} B{^{\prime }}&= g^{b^{{\prime }}} mod \,\, N\,\, \hbox {with a random nonce} \,\,b';\\ K{^{\prime }}&= \left( {\left( {M_1 \times \frac{1}{s_j }^{\left( {{\textit{UID}}_i \times {\textit{SID}}_j } \right) }} \right) mod \,\,N} \right) ^{b^{{\prime }}}=g^{(a\times b^{{\prime }})} mod \,\,N;\\&{\textit{SKey}}_{\left( {i, j} \right) } {^{\prime }}=h(K{^{\prime }}\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j );\\ M_2 ^{{\prime }}&= h\left( {K{^{\prime }}\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert {B{^{\prime }}} \Vert {\textit{SKey}}_{\left( {i, j} \right) } {^{\prime }}} \right) . \end{aligned}$$

• Step 6: With {$B{^{\prime }}$, $M_2 ^{{\prime }}$}, $U_{i}$ performs the following verification.

  • $K^{{\prime }}=\left( {B^{{\prime }}} \right) ^{a} mod \,\,N=\left( {g^{b^{{\prime }}}} \right) ^{a} mod \,\,N= g^{\left( {a\times b^{{\prime }}} \right) } mod \,\,N$

  • ${\textit{SKey}}_{\left( {i, j} \right) } {^{\prime }}=h(K{^{\prime }}\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j )$

  • $M_2 ^{{\prime }{\prime }}=h\left( {K{\prime }\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert {B^{{\prime }}} \Vert {\textit{SKey}}_{\left( {i, j} \right) } {\prime }} \right)$

  • Check $M_2 ^{{\prime }{\prime }}=M_2^{\prime } ?$

  It is obvious that all the verifications will be passed. $U_{i}$ then computes $M_3$ and sends it back to $S_{j}$.

  $$\begin{aligned} M_3 =h\left( {K^{\prime }\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert {A\Vert B^{{\prime }}} \Vert {\textit{SKey}}_{\left( {i, j} \right) } {^{\prime }}} \right) \end{aligned}$$

• Step 7: $U_{k}$ interrupts $M_3$. Now $U_{k}$ and $U_{i}$ share a session key ${\textit{SKey}}_{\left( {i, j} \right) } ^{{\prime }}=h(K^{\prime }\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j )$, where $K^{\prime }=g^{\left( {a\times b^{{\prime }}} \right) } mod \,\,N$. Since $U_{k}$ shares two different session keys with $U_{i}$ and $S_{j}$, respectively, the man-in-the-middle attack is successfully performed.

4 The Proposed Scheme

In this section, we propose a novel protocol for multi-server architecture, where a trusted registration center RC exists. First, RC chooses two 1024-bits prime numbers $p$ and $q$ and a generator $g\in Z_N^*$ and computes $N=p\times q$, where $Z_N^*=(g|1\le g\le N-1, gcd \left( {g, N} \right) =1)$. Next, RC generates $k$ random numbers ($r_{1}$, $r_{2}$, ..., $r_{k})$ for $k$ servers, respectively. Note that $gcd \left( {r_i , r_j } \right) =1, gcd \left( {r_i , \phi (N)} \right) =1$, where $1\le i, j\le k, i\ne j$.

4.1 Server Registration Phase

In this phase, the server $S_{j}$ submits ${\textit{SID}}_{j}$ to RC over a secure channel. Once RC receives the request from $S_{j}$, RC assigns $r_{j}$ to $S_{j}$ and computes $h(r_{j}\Vert y_{RC})$, where $y_{RC}$ is a secret value chosen by RC. Next, RC sends {$r_{j}, t, h(r_{j}\Vert y_{RC}), g, N, h$(.)} to $S_{j}$ via a secure channel. Note that $t=\frac{1}{g^{\mathop \prod \nolimits _{i=1}^k r_i } mod \,\,N}$.

4.2 User Registration Phase

In this phase, the user $U_{i}$ submits {${\textit{UID}}_{i}, {\textit{PW}}_{i}$} to RC which then generates a random number $r_{i}$ and computes $P=h({\textit{UID}}_{i}\Vert {\textit{PW}}_{i}\Vert r_{i})$. Next, RC issues a smart card storing parameters {($s_{1\_i}$, $s_{2\_i}$, ..., $s_{k\_i})$, $r_{i}, g, N, P, h$(.)} to $U_{i}$. Note that $s_{j\_i} =g^{h({\textit{SID}}_j \Vert {\textit{UID}}_i \Vert h(r_j \Vert y_{RC} ))\times \mathop \prod \nolimits _{i=1, i\ne j}^k r_j } mod \,\,N$, where $y_{RC}$ is a secret value chosen by RC.

4.3 Login and Authentication Phase (Fig. 3)

When $U_{i}$ wants to login $S_{j}, U_{i}$ inserts his/her smart card into the card reader and inputs his/her identity ${\textit{UID}}_{i}^{{\prime }}$ and password ${\textit{PW}}_{i}^{{\prime }}$. The smart card then calculates $P^\prime = h({\textit{UID}}_{i}^{{\prime }}\Vert {\textit{PW}}_{i}^{{\prime }}\Vert r_{i})$ and checks whether $P^\prime$ equals to $P$or not. If it holds, $U_{i}$ is legal. Next, the smart card generates a random nonce $a$, computes $M_1 =(s_{j\_i} \times g^{a}) mod \,\,N$, and sends {${\textit{UID}}_{i}, M_{1}$} to $S_{j}$. Once $S_{j}$ receives {${\textit{UID}}_{i}, M_{1}$}, $S_{j}$ verifies ${\textit{UID}}_{i}$. If ${\textit{UID}}_{i}$ is valid, $S_{j}$ generates a random nonce $b$, and computes $B, K, {\textit{SKey}}_{(i, j)}$ and $M_2$. After that, $S_{j}$ sends {$B, M_{2}$} to $U_{i}$.

$$\begin{aligned} B&= g^{b\times h(r_j \Vert y_{RC} ) } mod \,\,N;\\ K&= \left( {M_1 ^{\left( {r_j } \right) }\times t^{h({\textit{SID}}_j \Vert {\textit{UID}}_i \Vert h(r_j \Vert y_{RC} ))}} \right) ^{b\times h(r_j \Vert y_{RC} )}=g^{a\times b\times h(r_j \Vert y_{RC} )} mod \,\,N;\\&{\textit{SKey}}_{(i, j)} =h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j );\\ M_2&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert B \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) . \end{aligned}$$

Once receiving {$B$, $M_{2}$}, $U_{i}$ calculates $K$, ${\textit{SKey}}_{(i, j)}$ and $M_2 ^{{\prime }}$, and checks whether $M_2 ^{{\prime }}$ equals to $M_2$ or not. If it holds, $S_{j}$ is authenticated.

$$\begin{aligned} K&= \left( B \right) ^{a} mod \,\,N=\left( {g^{b\times h(r_j \Vert y_{RC} \hbox {)}}} \right) ^{a} mod \,\,N= g^{a\times b\times h(r_j \Vert y_{RC} \hbox {)}} mod \,\,N;\\&{\textit{SKey}}_{(i, j)} =h(K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j );\\ M_2 ^{{\prime }}&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert B \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) \end{aligned}$$

After that, $U_{i}$ computes $M_3$ and sends $M_3$ to $S_{j}$. Upon getting $M_3$, $S_{j}$ calculates $M_3 ^{{\prime }}$ and checks whether $M_3 ^{{\prime }}$ is equal to $M_3$ or not. If it holds, mutal authentication is achieved. Both $U_{i}$ and$S_{j}$ agree upon a common session key ${\textit{SKey}}_{(i, j)}$.

$$\begin{aligned} M_3&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert {A\Vert B} \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) ; \\ M_3 ^{{\prime }}&= h\left( {K\Vert {\textit{UID}}_i \Vert {\textit{SID}}_j \Vert {A\Vert B} \Vert {\textit{SKey}}_{\left( {i, j} \right) } } \right) \end{aligned}$$

Fig. 3

Login and authentication phase of the proposed scheme

4.4 Password Change Phase

When $U_{i}$ wants to change the password. $U_{i}$ inserts the smart card into the card reader and keys in ${\textit{UID}}_{i}^{{\prime }}$ and ${\textit{PW}}_{i}^{{\prime }}$. The smart card computes $P^\prime = h({\textit{UID}}_{i}^{{\prime }}\Vert {\textit{PW}}_{i}^{{\prime }}\Vert r_{i})$ and checks whether $P^\prime$ equals to stored $P$ or not. It holds, $U_{i}$ is legitimate. After that, $U_{i}$ is allowed to enter a new password ${\textit{PW}}_{\text {inew}}$, and the card reader generates a new random number $r_{i}^{{\prime }}$ and computes $P_{new}=h({\textit{UID}}_{i}\Vert {\textit{PW}}_{\text {inew}}\Vert r_{i}^{{\prime }}$) and stores $P_{new}$ and $r_{i}^\prime$ in the smart card’s memory.

5 Security Analysis

In this section, we present the formal analysis of our proposed authentication scheme based on [1–3, 5].

5.1 Communication Model

In the communication model, we assume that a user $U_i$, intends to establish a session key ${\textit{SKey}}_{(i, j)}$ with a service provider $S_j$. Therefore, some definitions must be presented.

• Protocol Participants: there exists a non-empty set of users, called Client, and a non-empty set of service providers, i.e.Server, in the protocol $P$ in which the participant is either a user or a service provider. Each participant may possess several instances, called oracles, which are involved in distinctly concurrent executions of $P$. Here, ${\Pi }_U^i$ is denoted as the instance $i$ of a participant $U$.

• Long-term Secret Keys: For each $S_j \in Server$, it owns a secret value $r_{j}$ as its long-term secret key, and $y_{RC}$ is RC’s long-term secret key trusted by all $U_i \in Client$ and all $S_j \in Server$.

• Accepting and Terminating: There exists two states, $\hbox {ACC}\_{\Pi }_U^i$ and $\hbox {TERM}\_{\Pi }_U^i$, for oracle ${\Pi }_U^i$. $\hbox {ACC}\_{\Pi }_U^i$ is set to true when ${\Pi }_U^i$ is able to compute a valid session key, while $\hbox {TERM}\_{\Pi }_U^i$ will be set to true when ${\Pi }_U^i$ sends (or receives) the last message of the protocol, receives an unexpected message, or misses an expected message.

• Session and Partner Identities: the session identity (sid) is utilized for representating each unique session. We define sid for oracles ${\Pi }_{U_A }^i$ and ${\Pi }_{U_B }^i$ in the execution of a protocol as $sid\_{\Pi }_{U_A }^i =sid\_{\Pi }_{U_B }^i$={$Flows_{U_A U_B } |$all flows that ${\Pi }_{U_A }^i$ exchanges with ${\Pi }_{U_B }^i$ in the execution of a protocol}. In addition, $pid\_{\Pi }_{U_A }^i =U_B$ is defined as that the oracle ${\Pi }_{U_A }^i$believes that it has just exchanged a session key with an oracle of participant $U_B$.

5.2 Adversary Model

In this paper, we assume that the adversary is able to interact with the participants via oracles queries. The following major queries model the capabilities of the adversary.

• Send(${\Pi }_U^i$, $m)$: This query sends a message $m$ to an oracle ${\Pi }_U^i$, and gets the corresponding results.

• Reveal(${\Pi }_U^i )$: This query returns the session key of the oracle ${\Pi }_U^i$.

• Corrupt($U)$: This query returns the long-term secret key of $U$.

• Execute(${\Pi }_{U_A }^i$, ${\Pi }_{U_B }^i )$: This query models passive attacks in which the adversary can obtain the messages exchanged during the honest execution of the protocol between two oracles ${\Pi }_{U_A }^i$ and ${\Pi }_{U_B }^i$.

• Hash($m)$: The one-way hash function can be viewed as random functions with the appropriate range in the ideal hash model. Note that, if $m$ has never been queried before, it returns a truly random number $r$ to the adversary and stores $(r, m)$ in the hash table. Otherwise, it returns the previously generated result to the adversary.

• Test(${\Pi }_U^i )$: This query models the security of the session key, i.e., whether the real session key can be distinguished from a random string or not. For answering this question, a unbiased coin $b$ is flipped by the oracle ${\Pi }_U^i$. When the adversary issues a single Test query to ${\Pi }_U^i$, the adversary either obtains the real session key ${\textit{SKey}}_{(i, j)}$ if $b$= 1 or a random string if $b$= 0.

5.3 Security Properties

This subsection describes the security required in the proposed authentication.

• Freshness: An oracle ${\Pi }_U^i$ is fresh if the following conditions hold.

  • 1. $\hbox {ACC}\_{\Pi }_U^i$ is set to true.

  • 2. No Corrupt query has been issued by the adversary before $\hbox {ACC}\_{\Pi }_U^i$ is set to true.

  • 3. Neither ${\Pi }_U^i$ nor its partner has been issued a Reveal query.

  In general, a session key is fresh if, and only if, all oracles participated in current session were fresh.

• Partnering: In the protocol $P$, two oracles ${\Pi }_{U_i }^i$ and ${\Pi }_{S_j }^j$ are partnered if the following conditions hold.

  • 1. Both $\hbox {ACC}\_{\Pi }_{U_i }^i$ and $\hbox {ACC}\_{\Pi }_{S_j }^j$ have been set to true.

  • 2. A session key ${\textit{SKey}}_{(i, j)}$ has been agreed by ${\Pi }_{U_i }^i$ and ${\Pi }_{S_j }^j$.

  • 3. $sid\_{\Pi }_{U_i }^i = sid\_{\Pi }_{U_j }^i .$

  • 4. $pid\_{\Pi }_{U_i }^i = S_j .$

  • 5. $pid\_{\Pi }_{S_j }^i = U_i .$

• AKE Security (Session Key Security): The adversary tries to guess the hidden bit $b$ involved in a Test query via a guess $b'$. We say that the adversary wins the game of breaking session key security of an AKE (Authenticated Key Exchange) protocol $P$ if the adversary issues Test queries to a fresh oracle ${\Pi }_U^i$ and guesses the hidden bit $b$ successfully. The probability that the adversary wins the game is Pr[$b'=b$]. In brief, the advantage of an adversary $A$ in attacking protocol $P$ can be defined as $Adv_P^{{\textit{AKE}}} \left( A \right) =|2\times \Pr \left[ {b^{{\prime }}=b} \right] -1|$. In brief, $P$ is AKE-secure if $\textit{Adv}_P^{\textit{AKE}} \left( A \right)$ is negligible.

5.4 Formal Security Analysis

In this subsection, we formally analyze the security of our proposed authentication protocol. Notations and definition will be presented first, and the formal security analysis is then demonstrated. We define $T_{A}$ be the adversary’s total running time, and $q_{s}$, $q_{r}$, $q_{c}$, $q_{e}$ and $q_{h}$ are the number of Send, Reveal, Corrupt, Execute, and Hash queries, respectively.

Definition 1

(Computational Diffie-Hellman (CDH) Assumption) Let $G=\langle {g}\rangle$ be a multiplicative cyclic group of order $N$, and two random numbers $t$ and $k$, are chosen in $Z_N^*$. Given $g$, $g^{t}$, and $g^{k}$, the adversary $A$ has a negligible success probability $\textit{Succ}_G^{CDH} \left( A \right)$ for obtaining an element $z\in G$, such that $z=g^{tk}$ within polynomial time.

Theorem 1

Let $A$ be an adversary against the AKE security of our proposed authentication protocol within a time bound $T_{A}$, with less than $q_{s}$ Send queries with the communication entities, and asking $q_{h}$ times Hash queries. Then, $\hbox {Adv}_P^{\textit{AKE}} \left( {A, q_s , q_h } \right) \le q_h q_s \times \textit{Succ}_G^{\textit{CDH}} \left( {T_A^{\prime } } \right)$, where $T_A^{\prime }$ denotes the computational time for $\textit{Succ}_G^{\textit{CDH}}$ and $q_s =\mathop \sum \nolimits _{i=1}^4 q_{s\_i}$ is the sum of number of $\hbox {Send}_{1}, \hbox {Send}_{2}, \hbox {Send}_{3}$, and $\hbox {Send}_{4}$.

Proof

Let $A$ be an adversary which is able to get an advantage $\varepsilon$ to break an AKE-secure protocol within time $T_{A}$. We can construct a CDH attacker $B$ from $A$ to respond all of $A$’s queries and deal with the CDH problem, where $B$ is given a challenge $\Omega =(g^{t},\,\,g^{k})$ and outputs an element $z$ such that $z =g^{tk}$.

First, when $A$ issues $\hbox {Send}_{1}$ query as a start command, $B$ responds {${\textit{UID}}_{i}$, $M_{1}$} to $A$. Second, when $A$ issues Send$_{2}$ query, $B$ randomly chooses two integers $c_{1}$ and $c_{2}$ from [1, $q_{s\_2}$]. If $c_1 \ne c_2$, $B$ responds {$B$, $M_{2}$} to $A$. Otherwise, $B$ replaces the corresponding parameters of {$B$, $M_{2}$} with the element $g^{k}$ from ${\Omega }$ to generate a new and random message {$B$, $M_{2}$}$'$, and then responds the message {$B$, $M_{2}$}$'$ to $A$. Third, once $B$ receives the Send$_{3}$ query from $A$, $B$ answers the message {$M_3$} as the protocol. If the input of the query is from ${\Omega }, B$ generates a new message {$M_3$}$'$, and then responds {$M_3$}$'$ to $A$. Fourth, when $A$ issues the $\hbox {Send}_{4}$ query, $B$ answers a null string and then sets $\hbox {ACC}\_{\Pi }_{U_i }^i$, $\hbox {ACC}\_{\Pi }_{S_j }^j$, $\hbox {TERM}\_{\Pi }_{U_i }^i$ and $\hbox {TERM}\_{\Pi }_{S_j }^j$ to true.

On the other hand, when $A$ issues a Reveal(${\Pi }_{U_i }^i )$ or a Reveal(${\Pi }_{S_j }^j )$ query, $B$ checks whether the oracle has been accepted and is fresh or not. If the result is true, $B$ answers the session key ${\textit{SKey}}_{(i, j)}$ to $A$. Otherwise, if the session key has been constructed from the challenge ${\Omega }, B$ terminates. When $A$ issues Corrupt($U_{i})$, Corrupt($S_{j})$, Execute(${\Pi }_{U_i }^i$, ${\Pi }_{S_j }^j )$, Hash($m)$ queries, $B$ answers in a straightforward way. When $A$ issues a Test query, $B$ answers in a straightforward way. Otherwise, if the session key has been constructed from the challenge $\Omega , B$ answers $A$ with a random string with the length of the session key ${\textit{SKey}}_{(i, j)}$.

The above simulation is indistinguishable from any execution of the proposed protocol $P$ except for one execution which the challenge ${\Omega }$ is involved with. The probability ${\upgamma }$ that B correctly guesses the session key that A will make a Test query on is equal to the probability of $c_1 =c_2$. Hence, we have

$$\begin{aligned} {\gamma }=\frac{1}{q_{s\_2} }\ge \frac{1}{q_s } \end{aligned}$$

Assume that A issues a Test query to output $b^{{\prime }}$, where $b^{{\prime }}=b$. This means that A knows the session key, so there must be at least one Hash query that returns the session key. The probability $\lambda$ that B will choose the hash query correctly is

$$\begin{aligned} \lambda \ge \frac{1}{q_h } \end{aligned}$$

The successful probability $\textit{Succ}_G^{\textit{CDH}} \left( B \right)$ that B will expose $g^{kt}$ from the challenge $\Omega$ is thus

$$\begin{aligned} \textit{Succ}_G^{CDH} \left( B \right) = \varepsilon \times \gamma \times \lambda \ge \varepsilon \times \frac{1}{q_s }\times \frac{1}{q_h } \end{aligned}$$

Finally, the advantage of $A$ to break the AKE-security of the protocol $P$ is derived as follows.

$$\begin{aligned} \varepsilon =\hbox {Adv}_P^{\textit{AKE}} \left( {A, q_s , q_h } \right) \le q_h q_s \times \textit{Succ}_G^{\textit{CDH}} \left( {T_A^{\prime } } \right) \end{aligned}$$

$\square$

6 Security and Performance Comparison

To further investigate the advantage of our proposed authentication protocol, we compare the proposed scheme with five relevant multi-server authentication schemes [11, 12, 14, 15, 17] in terms of major security features. From the viewpoint of robustness (Table 1), our proposed authentication scheme is superior to all of these five protocols by supporting all the major security features. In particular, our protocol inherits the merit from PTJ scheme, i.e. providing mutual authentication without the support of RC. This design significantly improves the efficiency of the protocol round. In brief, it is clearly seen that our proposed authentication scheme keeps all the advantages and achieves the security requirements.

Table 1 Security comparison among our proposed protocol and other schemes

Performance evaluation is an important issue while designing a robust and efficient authentication schemes. This evaluation reflects the practicability of implementing the proposed authentication protocol in the real world. As study [14] had demonstrated the computation efficiency of their proposed authentication scheme is better than other related studies [11, 12, 15, 17]. Hence, here we only compare our proposed protocol with two most-relevant proposals, i.e. PTJ scheme [14] and WM scheme [17] in terms of protocol efficiency. The performance comparison among our proposed scheme and other two schemes has been listed in Table 2. The metrics are Hash Function (HF), Modular Multiplication (MM), Modular Exponentiation (ME), ECC Point Multiplication (PM) and Encryption/Decryption (E/D). Although our proposed scheme requires extra 2 one-way hash functions than PTJ scheme, our scheme is efficient. This is as the cost of performing one-way hash functions can be almost ignored in comparison with other heavy computation modules such as Modular Exponentiation, ECC Point Multiplication or E/D. Moreover, compared to PTJ scheme, as one ME is reduced, the efficiency is improved. It is obvious that our scheme can achieve the same order of computation complexity as PTJ scheme does.

Table 2 Performance comparison among our proposed protocol and other schemes

7 Conclusion

To efficiently protect a multi-server based service system is a particular challenge owing to the difficult tradeoff between system security and computation efficiency. One of the most promising directions is to implement an efficient authentication mechanism for multi-server architecture. A recent study proposed by Pippal et al. is one of the pioneers on this interesting research area. However, it has space for improvement. In this paper, we have demonstrated that Pippal et al.’s multi-server based authentication scheme fails to provide adequate security and is subject to user impersonation attack, server counterfeit attack, and man-in-the-middle attack. A novel authentication protocol is thus introduced for security enhancement. With the formal analysis and performance comparison, the security robustness and computation efficiency of our proposed protocol can be guaranteed. Therefore, we believe that our proposed authentication protocol is practical and secure for multi-server communication environment.