A Novel Chaotic Maps-Based User Authentication and Key Agreement Protocol for Multi-server Environments with Provable Security

Abstract

The widespread popularity of the computer networks has triggered concerns about information security. Password-based user authentication with key agreement protocols have drawn attentions since it provides proper authentication of a user before granting access right to services, and then ensure secure communication over insecure channels. Recently, Lee et al. pointed out different security flaws on Tsaur et al.’s multi-server user authentication protocol, and they further proposed an extended chaotic maps-based user authentication with key agreement protocol for multi-server environments. However, we observed that Lee et al.’s protocol has some functionality and security flaws, i.e., it is inefficient in detection of unauthorized login and it does not support password change mechanism. Besides, their protocol is vulnerable to registration center spoofing attack and server spoofing attack. In order to remedy the aforementioned flaws, we proposed a novel chaotic maps-based user authentication with key agreement protocol for multi-server environments. The proposed protocol is provably secure in the random oracle model under the chaotic-maps based computational Diffie-Hellman assumption. In addition, we analyzed our protocol using BAN logic model. We also compared our protocol with Lee et al.’s protocol in aspects of computation cost, functionalities and securities.

1 Introduction

Nowadays, benefit from the rapid development of the computer network and the popularization of internet, various services and remote communications can be accomplished by clicking the keyboard in front of the screen. It not only brings huge opportunities to the market, but also provides people with great convenience. However, the security of online transactions and information transmission over insecure networks have became an important issue. As a kind of basic security protocols, user authentication with key agreement protocol has been widely used in the protection of network and information security, which provides identity authentication of the user before he/she accesses to the remote services. In addition, user authentication scheme with key agreement guarantees confidential communication between user and server by negotiating a shared session key.

1.1 Related Studies

In 1981, the pioneering work of password-based user authentication for secure communication over insecure network was proposed by Lamport [1]. However, a password verifier-table is needed to authenticate the users in their scheme. Besides, the user has to reset the password periodically to ensure the security of the protocol. Since then researchers have done a lot of related works [2, 3]. Due to the silent features of smart card, including storage, computing, encryption and other excellent functions, many user authentication protocols based on password and smart card [4–12] were presented by researchers. In the early stage, most of the user authentication protocols are only applicable to the single server environments. However, the increase in the number of users and the types of services provided by the remote servers brought tremendous challenge to the single server environments. The traditional single server authentication is unable to meet the need of the applications, and then multi-server authentication become an inevitable choice for the users. Compared with the single server authentication, multi-server authentication can offer users with better and more extensive services. However, the more open environments and complex communications cause the users to more vulnerable to attacks. Generally, to get access to services provided by different servers securely, the user has to use different passwords for multiple registration. However, with the increase in the number of the servers, it is impossible for a user to remember so many passwords. Therefore, the protocols for single server environments cannot meet the requirements of multi-server applications. In 2001, Li et al. [13] first explored the multi-server authentication problem, and they designed a multi-server authentication protocol utilizing the neural networks. However, their protocol was found inefficient since huge computation and communication costs are needed to train the neural network [14].

In the year 2003, Lin et al. [14] designed an authentication protocol for multi-server environments based on the ElGamal digital signature and the intractability of the discrete logarithm problem (DLP). However, in their protocol, the user has to store large number of system parameters for each servers. In addition, this protocol does not achieve the mutual authentication. In order to eliminate these issues, Juang [15] presented a low-cost multi-server authentication protocol based on hash function and symmetric cryptographic operations. Chang and Lee [16] further analyzed the problem of Juang’s protocol, and they presented an enhanced protocol. However, the protocol [16] was found insecure against insider attack and spoofing attack [17]. Later, Tsaur et al. constructed two user authentication protocols [17, 18] for multi-server environments based on the Lagrange polynomial interpolation and digital signature standard (DSS). In 2008, Tsai [19] proposed a new multi-server authentication protocol based on the hash function, and demonstrated that their protocol can resist various attacks. Contemporaneity, some of the works on multi-server user authentication [20–22] were put forward by researchers. However, these protocols have security defects [23–25].

In many cases, user does not want to leak the identity when he/she accesses services, such as in applications of network game, network television and Internet banking. Therefore, user anonymity becomes an important feature of authentication protocol. However, most of the aforementioned multi-server authentication protocols are relied on the static identity, which can be traced by attacker. Thus, the design of an authentication protocols with user anonymity and other necessary functionalities become a hot topic in information security. In 2009, Liao and Wang [26] first presented a multi-server user authentication protocol with user anonymity based on dynamic identity mechanism. In their protocol, user’s identity of one session is different from those of other sessions, which provides user anonymity and keeps user’s identity from being tracked. Later, Liao and Wang’s protocol [26] was found vulnerable to various attacks [27]. Hsiang and Shih [27] gave an enhanced protocol against the defective protocol presented in [26]. However, the protocol in [27] was still insecure, and both Sood et al. [28] and Lee et al. [29] found some security flaws of the protocol in [27], respectively. Further, both of them independently proposed their enhanced protocols. Unfortunately, both the enhanced protocols in [28, 29] were still found vulnerable to some attacks [30, 31].

1.2 Motivation and Contribution

Due to the chaotic system’s excellent properties of diffusion and confusion, chaos theory based cryptography received much attentions in recent years, and many chaotic system based user authentication protocols [33, 34] and key agreement protocols [35–39] have been constructed by researchers. In 2012, Tsaur et al. [32] constructed a user authentication protocol for multi-server environments based on self-verified timestamp. This protocol is efficient since it only uses symmetric encryption and hash function. However, Lee et al. [33] pointed out that Tsaur et al.’s protocol suffers from the insider attack, known-plaintext attack, and it does not guarantee the user anonymity. Later, Lee et al. constructed a new authentication protocol for multi-server environments using extend chaotic maps. However, we have identified some functionality and security drawbacks of the protocol in [33] as follows: (1) it is inefficient in the detection of unauthorized login; (2) it does not support password change; (3) it is vulnerable to registration center spoofing attack; (4) it vulnerable to server spoofing attack. Therefore, we have designed a novel chaotic maps-based user authentication with key agreement protocol for multi-server environments to resolve the drawbacks of the protocol presented in [33]. We demonstrate the provable security analysis of our protocol in the random oracle model. In addition, the formal security of our protocol is validated using BAN logic model. We also analyze other functional features and security aspects of the presented protocol. Based on the functionality requirements and security aspects, we compare our protocol with the protocol in [33], which proved that our protocol is a more secure user authentication protocol for multi-server environments.

1.3 Outline of the Paper

The remaining part of this paper are arranged as follows. Section 2 described some preliminaries. The review of the protocol in [33] and its cryptanalysis are described in Sects. 3 and 4, respectively. Section 5 described the proposed chaotic maps-based user authentication protocol for multi-server environments. The provable security analysis in the random oracle model, the formal security validation using BAN logic model and informal security analysis of the proposed protocol are presented in Sect. 6. The performance analysis and comparison of our protocol with the protocol presented in [33] are described in Sect. 7. Finally, Sect. 8 summarized the paper.

2 Chebyshev Chaotic Maps

In this section, Chebyshev chaotic maps and two intractable problems are discussed.

Definition 1

Let n is an integer and x is a variable chooses from the interval $[-1,1]$. The Chebyshev polynomial $T_{n}(x): [-1, 1]\rightarrow [-1, 1]$ is defined as $T_{n}(x) = \mathrm{cos}(n\cdot \mathrm{arccos}(x))$.

From the Definition 1, the following recurrence relation of the Chebyshev polynomial can be derived:

$T_{n}(x) = 2xT_{n-1}(x)- T_{n-2}(x)$, $n \ge 2$,

where $T_0(x) = 1$ and $T_1(x) = x$.

Definition 2

(Chaotic property) When n > 1, the Chebyshev polynomial map $T_n(x) : [-1, 1] \rightarrow [-1, 1]$ of degree n is a chaotic map with invariant density $f^*(x) =1/(\pi \sqrt{1-x^2 })$ for positive Lyapunov exponent $\lambda = \mathrm{ln}n$ > 0.

Definition 3

(Semi-group property) This property can be described as follows:

$$\begin{aligned} T_r(T_s(x)) & = \mathrm{cos}(r \mathrm{cos}^{-1}(\mathrm{cos}(s \mathrm{cos}^{-1}(x))))\\& = \mathrm{cos}(rs \mathrm{cos}^{-1}(x))\\& = T_{sr}(x)\\& = T_s(T_r(x)) \end{aligned}$$

where r and s are two positive integers and $x\in [-1, 1]$.

In 2008, Zhang [40] further extended the semi-group property of Chebyshev polynomials to the interval $(-\infty , +\infty )$, i.e., for $T_n(x) = (2xT_{n-1}(x)-T_{n-2}(x))\hbox { mod }p$, where $n \ge 2$, $x\in (-\infty , +\infty )$ and p is a large prime. The equation $T_r(T_s(x)) \equiv T_{rs}(x) \equiv T_{sr}(x) \equiv T_s(T_r(x))\hbox { mod }p$ is also hold for $x\in (-\infty , +\infty )$.

2.1 Computational Problem and Assumption

Definition 4

(Negligible function) A function $\epsilon (k)$ is said to be negligible if, for every c > 0, there exists a $k_0$ such that $\epsilon (k)\le \frac{1}{k^{c}}$ for every $k\ge k_0$.

Definition 5

(Chaotic maps-based Discrete Logarithm Problem (DLP)) Given $\{x$, $T_{r}(x) \hbox { mod }p\}$, it is hard for a polynomial time bounded algorithm ${\mathcal {A}}$ to compute r. The probability that ${\mathcal {A}}$ can find the solution of the DLP problem is defined as $Adv^{DLP}({{\mathcal {A}}}) = Pr[{\mathcal {A}}(x, T_{r}(x)\hbox { mod }p) = r: r\in Z_{p}^{*}]$.

Definition 6

(Chaotic maps-based Diffie-Hellman (CDH) problem) Given a random tuple $\{ x$, $T_{r}(x)\hbox { mod }p$, $T_{s}(x)\hbox { mod }p\}$, it is hard for a polynomial time bounded algorithm ${\mathcal {A}}$ to compute $T_{rs}(x)\hbox { mod }p$. The probability that ${\mathcal {A}}$ can find the solution of the CDH problem is defined as $Adv^{CDH}({{\mathcal {A}}}) = Pr[{\mathcal {A}}(x, T_{r}(x)\hbox { mod }p, T_{s}(x)\hbox { mod }p) = T_{rs}(x)\hbox { mod }p : r, s\in Z_{p}^{*}]$.

Definition 7

(DLP assumption) The probability $Adv^{DLP}({{\mathcal {A}}})$ is negligible for any ${\mathcal {A}}$, i.e, $Adv^{DLP}({{\mathcal {A}}})\le \epsilon$, for some negligible function $\epsilon$.

Definition 8

(CDH assumption) The probability $Adv^{CDH}({{\mathcal {A}}})$ is negligible for any ${\mathcal {A}}$, i.e, $Adv^{CDH}({{\mathcal {A}}}\le \epsilon$, for some negligible function $\epsilon$.

Definition 9

According to [41], the period of Chebyshev polynomial $T_{n}(x)$ is the divisor of $p^{2}-1$. In other way, we can say that $p - 1$ or $p + 1$ is the period of $T_{n}(x)$. Here we use $p + 1$.

3 Review of the Protocol in [33]

In this part, we reviewed Lee et al.’s protocol [33]. In [33], there are three parties i.e., the registration center RC, user $U_i$ and server $S_j$. RC first selects a random number X, two random integers (r, s), and then RC computes $w = h(r||s)$ and $R \equiv T_{w}(X)\hbox { mod }p$. At last, RC keeps the master keys (r, s) secret, and shares w with $S_j$ secretly via a secure channel. The protocol given in [33] includes two phases, i.e. registration phase and login and session key agreement phase. Table 1 lists the symbols used throughout this paper. The overview of protocol in [33] are as follows:

Table 1 The notations used in this paper

3.1 Registration

• 1. $U_i\;\rightrightarrows\;RC$: $\{ID_i, h(PW_i)\oplus N\}$ $U_i$ selects $ID_i$, $PW_i$ and a nonce N. $U_i$ computes $h(PW_i)\oplus N\}$ and then sends $\{ID_i$, $h(PW_i)\oplus N\}$ to RC through a secure channel.

• 2. $RC \;\rightrightarrows\; U_i$: Smart card RC computes $v_i = h(ID_i\Vert P_i\Vert w)$ and $\mu _i = v_i\oplus h(PW_i)\oplus N$, and injects $ID_i$, $\{\mu _i$, $P_i$, R, X, $h(\cdot ), p\}$ into a new smart card. Then RC issues the smart card to $U_i$ secretly.

• 3. $U_i$ computes $\mu _i^{\prime } = \mu _i \oplus N$ and replaces $\mu _i$ with $\mu _i^{\prime }$ in the smart card.

3.2 Login and Session Key Agreement

In this phase, the smart card and $S_j$ will perform the followings:

• 1. $U_i\rightarrow S_{j}$: $\{M_{ij}, UID_i, C_1, P_i\}$ $U_i$ inserts the smart card and keys $ID_i$ and $PW_i$. Then the smart card computes $v_i = \mu _i^{\prime }\oplus h(PW_i)$ and picks a random integer $r_i$. Then it also calculates

  $$\begin{aligned} C_1 & \equiv T_{r_i}(X)\hbox { mod }p\\ C_2 & \equiv T_{r_i}(R)\hbox { mod }p\\ UID_i& = ID_i\oplus h(C_1\Vert C_2)\\ M_{ij}& = h(ID_i\Vert UID_i\Vert P_i\Vert v_i\Vert C_1\Vert C_2) \end{aligned}$$

  and submits $\{M_{ij}, UID_i, C_1, P_i\}$ as the login request to $S_j$ over a public channel.

• 2. $S_{j}\rightarrow U_i$: $\{M_{ji}, C_3, V_i\}$ Upon receiving the login request from $U_i$, $S_j$ calculates $C_2^{\prime } \equiv T_w(C_1)$ mod p, $ID_i^{\prime } = UID_i\oplus h(C_1\Vert C_2^{\prime })$, $v_i^{\prime } = h(ID_i^{\prime }\Vert P_i\Vert w)$, and checks $h(ID_i^{\prime }\Vert UID_i\Vert P_i\Vert v_i^{\prime }\Vert C_1\Vert C_2^{\prime })\overset{?}{=}M_{ij}$. If not, $S_j$ rejects the request. Otherwise, $S_j$ further checks whether the service period $P_i$ is expired. If $P_i$ is expired, $S_j$ terminates the session. On the contrary, $S_j$ updates $P_i$ with $P_i^{new} = P_{i} - 1$. Then $S_j$ picks a random integer $r_j$ and calculates $v_i^{new} = h(ID_{i}^{\prime }\Vert P_i^{new}\Vert w)$, $V_i = v_i^{\prime }\oplus v_i^{new}$, $C_3 \equiv T_{r_j}(X)$ mod p, $SK \equiv T_{r_j} (C_1) \equiv T_{{r_j}{r_i}}(X)$ mod p, and $M_{ji} = h(ID_i^{\prime }\Vert v_i^{\prime }\Vert v_i^{new}\Vert P_i^{new}\Vert C_2^{\prime }\Vert C_3\Vert SK)$. At last, $S_j$ sends $\{M_{ji}, C_3, V_i\}$ to $U_i$ over a public channel.

• 3. $U_i\rightarrow S_j$: $\{M_{sk}\}$ The smart card calculates $v_i^{new\prime } = V_i\oplus v_i$, $P_i^{new} = P_i-1$, $SK^{\prime } \equiv T_{r_i}(C_3) \equiv T_{{r_i}{r_j}}(X)$ mod p, and checks $h(ID_i\Vert v_i\Vert v_i^{new\prime }\Vert P_i^{new}\Vert C_2\Vert C_3\Vert SK^{\prime }) \overset{?}{=} M_{ji}$. If it is incorrect, the session will be stopped. Otherwise, the validity of $S_j$ is authenticated by $U_i$. Then, the smart card calculates $\mu _i^{new} = v_i^{new\prime }\oplus h(PW_i)$ and updates $\{\mu _i^{\prime }, P_i\}$ with $\{\mu _i^{new}, P_i^{new}\}$. At last, the smart card calculates $M_{sk} = h(C_2\Vert SK^{\prime })$ and sends it to $S_j$ over a public channel.

• 4. Upon receiving $\{M_{sk}\}$ from $U_i$, $S_j$ checks $h(C_2^{\prime }\Vert SK) \overset{?}{=} M_{sk}$. If they are not equal, the session will be terminated. Otherwise, $U_i$ is authenticated by $S_j$, and $U_i$ and $S_j$ agree on a session key SK.

4 Cryptanalysis of the Protocol in [33]

In this part, we point out the drawbacks of protocol in [33] from the aspects of functionality and security.

4.1 No Single Registration

One of the important features of multi-server user authentication protocol is that the user can access services provided by different servers with a single registration. The single registration helps the user to access different servers with a single password and identity. However, to access multiple servers in the protocol given in [33], $U_i$ has to repeatedly register to RC for each server $S_j$ to get $v_i$ and $\mu _i$. Therefore, the protocol given in [33] is not user friendly for multi-server environments.

4.2 Inefficient Detection of Unauthorized Login

In real applications, it is suggested that the user needs to set different passwords for diverse applications to guarantee the adequate security of network-based services. Then, the user may be confused by the different passwords for diverse services, and would be likely to input wrong password in the login stage. Therefore, it is plausible and an ideal feature that any unauthorized login launched by entering a wrong password must be detected by the smart card [42]. Otherwise, the protocol may suffer from DoS (Denial of Service) attack due to the server has to spend a lot of resources to check unauthorized login messages launched by the attacker.

Due to the absence of wrong password detection mechanism of the protocol given in [33], even if $U_i$ inputs an incorrect password by mistake in login stage, the processes of the protocol will still be performed until some wrong information is detected by $S_j$. The detailed descriptions of this situation are given below:

Assume that a wrong password $PW_i^{*}(\ne PW_i)$ is entered by $U_i$ when he/she initiates a session, then the following procedures would be executed by smart card of $U_i$ and $S_j$:

• 1. The smart card calculates $v_i^* = \mu _i^{\prime }\oplus h(PW_i^{*}) (= v_i\oplus h(PW_i)\oplus h(PW_i^{*}) \ne v_i = h(ID_i\Vert P_i\Vert w))$ and generates a random integer $r_i$. Then it calculates $C_1 \equiv T_{r_i}(X) \hbox { mod }p$, $C_2 \equiv T_{r_i}(R)$ mod p, $UID_i = ID_i\oplus h(C_1\Vert C_2)$, $M_{ij}^{*} = h(ID_i\Vert UID_i\Vert P_i\Vert v_i^*\Vert C_1\Vert C_2)$. At last, the message $\{M_{ij}^{*}, UID_i, C_1, P_i\}$ is submitted as the login request to $S_j$.

• 2. After receiving $\{M_{ij}^{*}, UID_i, C_1, P_i\}$ from $U_i$, $S_j$ first calculates $C_2^{\prime } \equiv T_w(C_1)\hbox { mod }p$, $ID_i^{\prime } = UID_i\oplus h(C_1\Vert C_2^{\prime })$, $v_i^{\prime } = h(ID_i^{\prime }\Vert P_i\Vert w)$, and it can be seen that $h(ID_i^{\prime }\Vert UID_i\Vert P_i\Vert v_i^{\prime }\Vert C_1\Vert C_2^{\prime }) \ne h(ID_i\Vert UID_i\Vert P_i\Vert v_i^{*}\Vert C_1\Vert C_2) = M_{ij}^{*}$ since $v_{i}^{*} \ne v_{i}^{\prime }$. Until now, the unauthorized login caused by wrong password was rejected by $S_j$.

Therefore, the protocol in [33] is inefficient to detect the unauthorized login, which was generated due to wrong password. It is illogical and will increase the communication and computational overheads on the full system. Furthermore, it may be utilized by an attacker to launch a DoS (Denial of Service) attack on the system.

4.3 No Support for Password Change

Periodically change of the password is not only convenient for the users, but also an important strategy to guarantee the security of the authentication protocol. Therefore, the password change is one of the most basic function and this facility must be incorporated in the password-based authentication protocol to provide more robustness. However, we found that the protocol in [33] does not support the update of the password. It is really not easy thing to add the password change function in [33] due to the absence of wrong password detection mechanism on smart card side. Therefore, the user has to adopt the face to face approach with the registration center to update the password, and it is undoubtedly a functional defect of the protocol in [33].

4.4 Registration Center Spoofing Attack

In [33], we clearly observed that RC shared the same secret key $w = h(r\Vert s)$ with all the servers, and it would introduce some security defects to the protocol. First, w becomes the actual master secret key of the system, and the securities of the system are relying on w. In order to reduce the risk of leakage, the master secret key should be held by RC only. However, in [33], w is known to all the servers except RC and the security of the system will collapse if any of the server is compromised. Therefore, sharing the secret key w with all servers is one of the most serious security flaws in the design of the protocol in [33].

Furthermore, in the registration phase of the protocol in [33], $U_i$’s secret information $v_i$ and $\mu _i$ are calculated by RC based on w only. Therefore, with the public information R, X, $h(\cdot )$ and the shared secret key w, any server $S_j\in \{S_1, S_2, \ldots , S_r\}$ can impersonate RC without knowing the secret information (r, s), therefore, the protocol in [33] is vulnerable to the registration center spoofing attack.

4.5 Server Spoofing Attack

Last but not least, since all the servers share the same secret key w and all the messages generated in login and session key agreement phase rely on w, any malicious server of the system can camouflage as any other servers. When $U_i$ transmits the login message $\{M_{ij}, UID_i, C_1, P_i\}$ to $S_j$, it can be intercepted by a malicious server, say $S_n$. Then, $S_n$ calculates $C_2^{\prime }, ID_i^{\prime }, v_i^{\prime }$ using w, and gets $h(ID_i^{\prime }\Vert UID_i\Vert P_i\Vert v_i^{\prime }\Vert C_1\Vert C_2^{\prime }) = M_{ij}$. Then, $S_n$ updates the service period $P_i$ with $P_i^{new} = P_i-1$ and computes $v_i^{new} = h(ID_i^{\prime }\Vert P_i^{new}\Vert w)$, $V_i = v_i^{\prime }\oplus v_i^{new}$. Then $S_n$ chooses a random integer $r_n$ and computes $C_3 \equiv T_{r_n}(X)\hbox { mod }p$, $SK \equiv T_{r_n}(C_1) \equiv T_{{r_n}{r_i}}(X)$ mod p. Finally, $S_n$ computes $M_{ni} = h(ID_i^{\prime }\Vert v_i^{\prime }\Vert v_i^{new}\Vert P_i^{new}\Vert C_2^{\prime }\Vert C_3\Vert SK)$ and transmits the message $\{M_{ni}, C_3, V_i\}$ to $U_i$. $U_i$’s smart card then computes $v_i^{new\prime } = V_i\oplus v_i$, $P_i^{new} = P_i-1$, $SK^{\prime } \equiv T_{r_i}(C_3) \equiv T_{{r_i}{r_n}}(X)$ mod p and gets $h(ID_i\Vert v_i\Vert v_i^{new\prime }\Vert P_i^{new}\Vert C_2\Vert C_3\Vert SK^{\prime }) = M_{ni}$. Then, the smart card calculates $\mu _i^{new} = v_i^{new\prime }\oplus h(PW_i)$ and updates $\{\mu _i^{\prime }, P_i\}$ with $\{\mu _i^{new}, P_i^{new}\}$. Finally, the smart card calculates $M_{sk} = h(C_2\Vert SK^{\prime })$ and transmits it to $S_n$. Upon receiving the message $\{M_{sk}\}$ from $U_i$, $S_n$ calculates $h(C_2^{\prime }\Vert SK)$ and gets $h(C_2^{\prime }\Vert SK) = M_{sk}$. At last, a session key SK is shared between $U_i$ and $S_n$. Therefore, any malicious server of the system can camouflage as other servers to cheat any registered user and accordingly, the protocol in [33] is suffered from the server spoofing attack.

5 The Proposed Protocol

In this part, we design a new multi-server authentication protocol utilizing the extended chaotic maps. There are also three parties in the designed protocol, i.e. registration center RC, server $S_j$ and user $U_i$. Here, we considered RC is a trusted entity and in charge of the selection of the system parameters, the registration of the users and the servers, and the authentication of the users. To initialize the system, RC first selects a random number X and a system master key w, and computes the public key $R \equiv T_w(X)$ mod p. In order to register to the system, $S_j$ transmits the unique identity $SID_j$ to RC in a secret manner. When receiving the registration request, RC computes $K_j = h(SID_j\Vert w)$ and transmits $\{K_j, X\}$ to $S_j$ in a secret manner. In the proposed protocol, there are three phases, namely registration, login and session key agreement, and password change. These three phases is described below:

5.1 Registration

If $U_i$ wants to enjoy the services provided by servers $\{S_1, S_2, \ldots , S_r\}$, he/she needs to register to RC in advance, and the following procedures should be executed.

• 1. $U_i \;\rightrightarrows\; RC$: $\{ID_i, e_i\}$ $U_i$ first selects the identity $ID_i$ and password $PW_i$. Then $U_i$ picks a random number $N_i$ and calculates $e_i = h(PW_i\Vert N_i)\}$, and transmits the registration request message $\{ID_i, e_i = h(PW_i\Vert N_i)\}$ to RC through a secure channel.

• 2. $RC \;\rightrightarrows\; U_i$: Smart card Upon receiving the registration request from $U_i$, RC calculates $f_i = h(ID_i\Vert w)$, $A_i = h(ID_i\Vert e_i)$, $B_i = e_i\oplus f_i$ and stores $\{A_i$, $B_i$, X, R, $h(\cdot ),p\}$ into the memory of a smart card. Then the smart card is issued by RC to $U_i$ through a reliable channel.

• 3. $U_i$ injects the random number $N_i$ into the smart card, and the random number $N_i$ is no longer need to be remembered by $U_i$. Finally, the smart card contains the information $\{A_i$, $B_i$, $N_{i}$, X, R, $h(\cdot )$, $p\}$.

We also illustrate the registration phase of our protocol in Fig. 1.

Fig. 1

The registration phase of the new protocol

5.2 Login and Session Key Agreement

In this phase, whenever $U_i$ wants to login to $S_j$, the following procedures should be executed among $U_i$, $S_j$ and RC.

• 1. $U_i\rightarrow S_j$: $\{UID_i, C_1, M_{ik}\}$ $U_i$ first chooses the identity $SID_j$ of $S_{j}$ on which he/she wants to access. $U_{i}$ inserts the smart card into a card reader and then keys $ID_i$ and $PW_i$. Then, the smart card calculates $e_i = h(PW_i\Vert N_i)$, $A_i^{\prime } = h(ID_i\Vert e_i)$ and checks $A_i^{\prime }\mathop {=}\limits ^{?}A_i$. If the equation does not hold, it means the inputted identity or password is invalid, and thus, the connection is stopped by the smart card. Otherwise, the smart card picks a random integer $r_i$ and calculates the followings:

  $$\begin{aligned} C_1 & \equiv T_{r_i}(X)\hbox { mod }p,\\ C_2 & \equiv T_{r_i}(R)\hbox { mod }p,\\ UID_i& = ID_i\oplus h(C_1\Vert C_2),\\ f_i& = B_i\oplus e_i,\\ M_{ik}& = h(ID_i\Vert SID_j\Vert f_i\Vert C_1\Vert C_2), \end{aligned}$$

  the login message $\{UID_i, C_1, M_{ik}\}$ is submitted to $S_j$ over an unreliable channel.

• 2. $S_j\rightarrow RC$: $\{UID_i, C_1, M_{ik}, SID_j, C_3, M_{jk}\}$ After receiving $\{UID_i, C_1, M_{ik}\}$, $S_j$ generates an random number $r_j$ and computes

  $$\begin{aligned} C_3 & \equiv T_{r_j}(X)\hbox { mod }p,\\ M_{jk}& = h(K_j\Vert C_3), \end{aligned}$$

  $S_j$ forwards $\{UID_i, C_1, M_{ik}, SID_j, C_3, M_{jk}\}$ to RC over an unreliable channel.

• 3. $RC\rightarrow S_j$: $\{D_i, M_{kj}, F_i, M_{ki}\}$ Upon receiving $\{UID_i, C_1, M_{ik}, SID_j, C_3, M_{jk}\}$, RC calculates $K_j^{\prime } = h(SID_j\Vert w)$, $M_{jk}^{\prime } = h(K_j^{\prime }\Vert C_3)$ and checks whether $M_{jk}^{\prime }$ equals to $M_{jk}$. If they are not equal, the session is rejected by RC. Otherwise, $S_j$ is authenticated by RC. Then, RC computes $C_2^{\prime } \equiv T_w(C_1)$ mod p, $ID_i^{\prime } = UID_i\oplus h(C_1\Vert C_2^{\prime })$, $f_i^{\prime } = h(ID_i^{\prime }\Vert w)$, $M_{ik}^{\prime } = h(ID_i^{\prime }\Vert SID_j\Vert f_i^{\prime }\Vert C_1\Vert C_2^{\prime })$ and checks $M_{ik}^{\prime } \mathop {=}\limits ^{?} M_{ik}$. If they are not equal, the session is rejected by RC. Otherwise, the validity of $U_i$ is confirmed by RC and then RC accepts the login request. For mutual authentication, RC picks a random number $r_k$ and calculates $D_i = K_j^{\prime }\oplus r_k$, $M_{kj} = h(K_j^{\prime }\Vert C_1\Vert C_3\Vert r_k)$, $E_i = h(K_j^{\prime }\Vert r_k)$, $F_i = E_i\oplus f_i^{\prime }\oplus C_2^{\prime }$, $M_{ki} = h( f_i^{\prime }\Vert F_i\Vert SID_j\Vert C_2^{\prime }\Vert C_3)$. Then, RC forwards the response message $\{D_i, M_{kj}, F_i, M_{ki}\}$ to server $S_j$ over an unreliable channel.

• 4. $S_j\rightarrow U_i$: $\{F_i, M_{ki}, C_3, M_{ji}\}$ Upon receiving the response message $\{D_i, M_{kj}, F_i, M_{ki}\}$ from RC, $S_j$ calculates $r_k^{\prime } = K_j\oplus D_i$, $M_{kj}^{\prime } = h(K_j\Vert C_1\Vert C_3\Vert r_k^{\prime })$ and checks $M_{kj}^{\prime } \mathop {=}\limits ^{?} M_{kj}$. If it does not hold, the session is rejected by $S_j$. Otherwise, RC is authenticated by $S_j$. Then, $S_j$ computes $E_i^{\prime } = h(K_j\Vert r_k^{\prime })$, $SK \equiv T_{r_j}(C_1)$ mod p, $M_{ji} = h(SID_j\Vert C_1\Vert C_3\Vert E_i^{\prime }\Vert SK)$ and forwards the message $\{F_i, M_{ki}, C_3, M_{ji}\}$ to $U_i$ over an unreliable channel.

• 5. $U_i\rightarrow S_j$: $\{M_{ij}\}$ Upon receiving the message $\{F_i, M_{ki}, C_3, M_{ji}\}$ from $S_j$, the smart card calculates $M_{ki}^{\prime } = h(f_i\Vert F_i\Vert SID_j\Vert C_2\Vert C_3)$ and checks $M_{ki}^{\prime } \mathop {=}\limits ^{?} M_{ki}$. If $M_{ki}^{\prime }\ne M_{ki}$, the session is rejected by $U_i$. Otherwise, the validity of RC is confirmed by $U_i$. Then, $U_i$ computes $E_i^{\prime \prime } = F_i\oplus f_i\oplus C_2$, $SK^{\prime } \equiv T_{r_i}(C_3)$ mod p, $M_{ji}^{\prime } = h(SID_j\Vert C_1\Vert C_3\Vert E_i^{\prime \prime }\Vert SK^{\prime })$ and checks $M_{ji}^{\prime } \mathop {=}\limits ^{?} M_{ji}$. If $M_{ji}^{\prime } \ne M_{ji}$, the session is also rejected by $U_i$. Otherwise, the validity of $S_j$ is confirmed by $U_i$. At last, $U_i$ calculates $M_{ij} = h(C_3\Vert E_i^{\prime \prime }\Vert SK^{\prime })$ and forwards it to $S_j$ over an unreliable channel.

• 6. On receiving the message $\{M_{ij}\}$, $S_j$ calculates $M_{ij}^{\prime } = h(C_3\Vert E_i^{\prime }\Vert SK)$ and checks $M_{ij}^{\prime } \mathop {=}\limits ^{?} M_{ij}$. If $M_{ij}^{\prime } \ne M_{ij}$, the connection is stopped by $S_j$. Otherwise, the validity of $U_i$ is confirmed by $S_j$.

At last, a session key $SK \equiv T_{r_j}(C_1)$ mod p $\equiv T_{{r_i}{r_j}}(X)$ mod $p \equiv T_{r_i}(C_3)$ mod $p = SK^{\prime }$ is agreed between $U_i$ and $S_j$, which can be used to securing the successive communication between $U_{i}$ and $S_{j}$.

We also illustrate the login and key agreement phase of our protocol in Fig. 2.

Fig. 2

The login and key agreement stage of the new protocol

5.3 Password Change

In our protocol, the password can be updated freely without any support from RC. In order to do it, $U_i$ first inserts the smart card into a card reader and then keys $ID_i$, $PW_i$, and requests to renew the password. Then, the smart card calculates $e_i = h(PW_i\Vert N_i)$, $A_i^{\prime } = h(ID_i\Vert e_i)$ and checks $A_i^{\prime } \mathop {=}\limits ^{?} A_i$. If $A_i^{\prime }\ne A_i$, it means one of the inputted user’s identity or password is invalid, and the password change phase is disconnected by the smart card. Otherwise, $U_i$ is permitted to input a new password $PW_i^{new}$. Then, the smart card calculates $e_i^{new} = h(PW_i^{new}\Vert N_i)$, $A_i^{new} = h(ID_i\Vert e_i^{new})$, $B_i^{new} = B_i\oplus e_i\oplus e_i^{new}$. At last, the smart card replaces $A_i$, $B_i$ with $A_i^{new}$, $B_i^{new}$, respectively.

6 Security Analysis

From the description of the presented protocol, the user can acquire different servers with single registration to RC. In this section, the security analysis of the our protocol is given. We show that our protocol is provably secure in the random oracle model against the hardness assumption of the Chaotic maps-based Diffie-Hellman (CDH) problem. Then, BAN logic model [43] is employed for formal security validation of our protocol. This analysis illustrates that the mutual authentication and session key established between $U_i$ and $S_j$ are correct and secure. In addition, we show the proposed chaotic maps-based multi-server authentication with key agreement protocol can resist many known attacks and can achieve many ideal functionalities.

6.1 Provable Security Analysis

6.1.1 Adversarial Model

In this section, we proposed a formal attack model of a password-based user authentication protocol [44–46] based on the following assumptions:

• RC and $S_{j}$ hold a common secret key $K_{j}$, RC holds a privatekey/public key pair $\{ w, T_{w}(X)\hbox { mod }p\}$ and $U_{i}$ holds a identity-password pair $\{ ID_{i}, PW_{i}\}$, where the low-entropy password $PW_{i}$ is chosen from an uniformly distributed small dictionary ${\mathcal {D}}$. In the registration phase, an injective transformation of $\{ ID_{i}$, w, $PW_{i}$, X, $N_{i}\}$ is stored into the smart card of $U_{i}$.

• We assume that ${\mathcal {A}}$ is a probabilistic polynomial time adversary. ${\mathcal {A}}$ and any protocol participant P (either $U_{i}$ or $S_{j}$ or RC) interacts by executing oracle queries, which give the capability of ${\mathcal {A}}$ to attack the authentication protocol. We denote $t$th instance of a participant P by $P^{t}$.

• ${\mathcal {A}}$ controls the communication channel. It implies that ${\mathcal {A}}$ can block, intercept, remove, inject, or modify, any messages passing through public channels, i.e., all the messages between $U^l_{i}$, $S_{j}^{m}$ and $RC^n$ are transmitted via ${\mathcal {A}}$ [47].

• ${\mathcal {A}}$ may either (a) steal $U_{i}$’s smart card and find the secret data from it by monitoring the power consumption, timing information and reverse engineering techniques as explained in [48–50] and then may apply some off-line procedure on the extracted data to successfully find the correct password $PW_{i}$ of $U_{i}$; or (b) directly obtain the password $PW_{i}$ of $U_{i}$. However, ${\mathcal {A}}$ cannot perform both (a) and (b) at the same time [46].

${\mathcal {A}}$ interacts with the protocol participants P via the following oracle queries that give the capabilities to ${\mathcal {A}}$ to model the real attack. To breach the security of the authentication protocol, ${\mathcal {A}}$ simulates the following queries:

• Execute($U_{i}^{l}, S_{j}^{m}, RC^{n}$): The Execute query helps ${\mathcal {A}}$ to launch passive attacks against the authentication protocol. This query outputs the messages that are exchanged during the actual execution of the protocol by the participants.

• Send($P^{t}, x$): The Send query gives the forgery capabilities to ${\mathcal {A}}$ for active attacks. ${\mathcal {A}}$ can send a message x through this oracle to $P^{t}$ and then $P^{t}$ returns some messages, that are computed by $P^{t}$ based on the protocol description, to ${\mathcal {A}}$.

• Reveal($P^{t}$): The Reveal query helps ${\mathcal {A}}$ to misuse of session keys. ${\mathcal {A}}$ can send a Reveal query to $P^{t}$ and then $P^{t}$ outputs the session key SK that is computed between $P^{t}$ and its partner provided that the session has accepted, otherwise returns a null value.

• Corrupt($P^{t}$, a): The Corrupt query models ${\mathcal {A}}$ to corrupt a protocol participant $P^{t}$, i.e. through this query ${\mathcal {A}}$ can get secret information about $P^{t}$. This query outputs in the following ways:

  • If $a = 1$, it returns $U_{i}$’s password $PW_{i}$ to ${\mathcal {A}}$.

  • If $a = 2$, it returns the information from $U_{i}$’s smart card.

• Test($P^{t}$): The semantic security of the session key SK is measured by this query. This oracle returns the session key if the session key is computed between $P^{t}$ and its partner, otherwise, returns a null value. ${\mathcal {A}}$ can send only a single Test query to $P^{t}$. On receiving a Test($P^{t}$) query, $P^{t}$ flips an unbiased coin b and outputs the actual session key SK computed between the protocol participants if $b = 1$. Otherwise, a random value is chosen from $\{0, 1\}^{*}$ and returns it as answer.

Definition 10

An instance $P^{t}$ is said to be accepted if it goes into an accept state after receiving the last expected protocol message.

Definition 11

The instances $P^{t}$ and $P^{u}$ are said to be partnered if (1) Both $P^{t}$ and $P^{u}$ is in the state accepted, i.e., they mutually authenticate each other and they have established the common session key; (2) Both $P^{t}$ and $P^{u}$ share the common sid; (3) $P^{t}$ is $P^{u}$’s partner and vice-versa. We denote the session identification (sid) of instance $P^{t}$ as the the concatenation of all messages sent and received by $P^{t}$.

Definition 12

An instance $P^{t}$ is called fresh if (1) $P^{t}$ is in the state accepted, i.e., $P^{t}$ and its partner mutually authenticate each other and generate the common session key (2) The Reveal queries are never submitted to $P^{t}$ or its partner; (3) Strictly less than two Corrupt-queries have been submitted to $P^{t}$, if P is a mobile user instance. Otherwise, strictly less than two Corrupt-queries have been submitted to $P^{t}$’s partner, if P is a foreign agent instance.

Definition 13

Let $Succ_{{\mathcal {A}}}$ denotes the event that ${\mathcal {A}}$ executes a single Test query to some fresh and terminated instance $P^{t}$, and eventually returns a guess bit $b^{\prime }$. The adversary breaks the semantics security of the user authentication protocol if $b^{\prime } = b$ holds and the advantage of ${\mathcal {A}}$ in violating the semantic security of authentication protocol is described as $Adv_{{\mathcal {A}}}(p) = 2Pr[Succ_{{\mathcal {A}}}]-1$, where the bit b was chosen during the execution of the Test query.

Definition 14

A password-based authentication protocol is said to be semantically secured if (1) in the presence of ${\mathcal {A}}$, $P^{t}$ and its partner are in accepted state and compute the common session key; (2) $Adv_{{\mathcal {A}}}(p)\le \epsilon$ for some negligible function $\epsilon$.

6.1.2 Provable Security Analysis

Theorem 1

Let $Adv_{C, {\mathcal {A}}}(t)$ denotes probability of success of the probabilistic polynomial time t adversary ${\mathcal {A}}$ in breaching the CDH problem, ${\mathcal {D}}$ be the small password dictionary, l denotes the security length, which is for hash values and ${\mathbb {P}}$ is our protocol. Assume that ${\mathcal {A}}$ can ask at most $q_{s}$ times Send queries, $q_{e}$ times Execute queries and $q_{h}$ times Hash queries to break the sematic security of the designed user authentication protocol and $Adv_{{\mathbb {P}}}({\mathcal {A}})$ is success probability of ${\mathcal {A}}$ in breaking the semantic security of the proposed protocol, then,

$$\begin{aligned} Adv_{{\mathbb {P}}}({\mathcal {A}})\le & \frac{q_{h}^{2}}{2^{l-1}}+\frac{(q_{s}+q_{e})^{2}}{p}+\frac{q_{s}}{2^{l-1}}+2\cdot \left(q_{h}\cdot Adv_{C, {\mathcal {A}}}(t)+\frac{q_{s}}{|{\mathcal {D}}|}\right) \end{aligned}$$

Proof

Assume that ${\mathcal {A}}$ tries to breach the proposed protocol, then we can build an algorithm ${\mathcal {C}}$ to break the security of the CDH problem, i.e. ${\mathcal {C}}$ outputs $T_{ab}(X)\hbox { mod }p$ from a given random tuple $\{ X$, $T_{a}(X)\hbox { mod }p$, $T_{b}(X)\hbox { mod }p\}$, where $a, b\in Z_{p}^{*}$. In this proof, we now define sequence of games $G_i$ $(0\le i\le 5)$ and for each game $G_i$, the event $E_i\, (0\le i\le 5)$ is also defined that ${\mathcal {A}}$ successfully guesses the bit b involved in Test query. We also define another event F (independent of the game $G_i$) that may occur during ${\mathcal {A}}$’s execution and F is detectable by ${\mathcal {C}}$. It can be noted that the game $G_i$ and $G_{i+1}$ are identical unless F occurs. Thus, we can write

$$\begin{aligned} |Pr[E_{i+1}]-Pr[E_{i}]|\le & Pr[F] \end{aligned}$$

(1)

Game $G_0$: The real attack in the random oracle model and the simulation of this game are same and thus, we can write

$$\begin{aligned} Adv_{{\mathbb {P}}}({\mathcal {A}}) = |2Pr[E_0]-1| \end{aligned}$$

(2)

Game $G_1$: This game simulates the has function $h(\cdot )$ by maintaining the hash list $L_{h}$. Thus, the real execution of the protocol and the simulation of this game are perfectly indistinguishable since the oracles including Hash, Execute, Reveal, Send, Corrupt and Test are also simulated as done in the real attack. The simulation of the different polynomial number of queries asked by ${\mathcal {A}}$ are given in Figs. 3, 4, 5, 6, 7 and 8. Thus, we have

$$\begin{aligned} Pr[E_1] = Pr[E_0] \end{aligned}$$

(3)

Fig. 3

Simulation of hash oracle queries

Fig. 4

Simulation of send oracle queries

Fig. 5

Simulation of execute oracle queries

Fig. 6

Simulation of corrupt oracle queries

Fig. 7

Simulation of reveal oracle queries

Fig. 8

Simulation of test oracle queries

Game $G_2$: The previous game and the simulation of this game are identical except that this game will be halted if a collision occurs during the the simulation of $\{ UID_{i}$, $C_{1}$, $M_{ik}\}$, $\{ UID_{i}$, $C_{1}$, $M_{ik}$, $SID_{j}$, $C_{3}$, $M_{jk}\}$, $\{ D_{i}$, $M_{kj}$, $F_{i}$, $M_{ki}\}$, $\{ F_{i}$, $M_{ki}$, $C_{3}$, $M_{ji}\}$ and $\{ M_{ij}\}$. Based on the birthday attack, probability of collisions of the simulation of $h(\cdot )$ oracle is at most $\frac{q_{h}^{2}}{2^{l+1}}$ [46, 51]. It can be noted that $r_i, r_j \in [1, p+1]$, $C_{1} \equiv T_{r_i}(X)$ $\text{ mod }~p$ and $C_{3} \equiv T_{r_j}(X)$ $\text{ mod }~p$ are chosen randomly from $Z_{p}^{*}$ and thus the probability of collisions in the transcripts simulation is at most $\frac{(q_{s}+q_{e})^{2}}{2p}$. Therefore, we have

$$\begin{aligned} |Pr[E_2]-Pr[E_1]|\le & \frac{q_{h}^{2}}{2^{l+1}}+\frac{(q_{s}+q_{e})^{2}}{2p} \end{aligned}$$

(4)

Game $G_3$: The simulations of this game and previous game are identical. The only exception is that this game will be aborted if ${\mathcal {A}}$ correctly guess the authentication values $M_{ik}$, $M_{jk}$, $M_{kj}$, $M_{ki}$, $M_{ji}$ and $M_{ij}$ without asking the oracle $h(\cdot )$. Thus, we can say that the simulations of this game and the previous game are identical unless any protocol instance rejects a valid authentication value. Thus, we have

$$\begin{aligned} |Pr[E_3]-Pr[E_2]|\le & \frac{q_{s}}{2^l} \end{aligned}$$

(5)

Game $G_4$: In this game, CDH problem is simulated. For this purpose, ${\mathcal {A}}$ queries CDH oracle with $\{ X$, $T_{a}(X)\hbox { mod }p$, $T_{b}(X)\hbox { mod }p\}$ to compute $CDH(T_{a}(X)\hbox { mod }p$, $T_{b}(X)\hbox { mod }p)$ = $T_{ab}(X)\hbox { mod }p$, where $a, b\in Z_{p}^{*}$. The session key is guessed without asking the corresponding oracle $h(\cdot )$, i.e. SK is completely independent from $h(\cdot )$ and $T_{r_{j}}(C_{1})$ mod p or $T_{r_{i}}(C_{3})$ mod p. Therefore, this game and the previous game are indistinguishable unless ${\mathcal {A}}$ queries $h(\cdot )$ on the common value $T_{r_{i}r_{j}}(X)$ mod p. Hence, $Adv_{C, {\mathcal {A}}}(p)\ge \frac{1}{q_{h}}\cdot |Pr[E_4]-Pr[E_3]|$ i.e., we have

$$\begin{aligned} |Pr[E_4]-Pr[E_3]|\le & q_{h}\cdot Adv_{C,{\mathcal {A}}}(t) \end{aligned}$$

(6)

Game $G_{5}$: The simulation of this game is identical with the simulation of the game $G_{4}$. However, the Test query of this game is terminated if ${\mathcal {A}}$ asks a $h(\cdot )$ query with $T_{r_{i}r_{j}}(X)$ mod p. ${\mathcal {A}}$ can get the session key SK by $h(\cdot )$ query with probability at most $\frac{q_{h}^{2}}{2p}$. Thus we have,

$$\begin{aligned} |Pr[E_5]-Pr[E_4]|\le & \frac{q_{h}^{2}}{2^{l+1}} \end{aligned}$$

(7)

The adversary ${\mathcal {A}}$ will not have any advantage in distinguishing the real session key from a random one if he doesn’t make any $h(\cdot )$ query with the correct input. Therefore, $Pr[E_5] = \frac{1}{2}$. Note that two Corrupt cannot be executed by ${\mathcal {A}}$. It means that if ${\mathcal {A}}$ executes the $Corrup(U_{i}, 2)$ query, however, he is not allowed to ask the password-corrupt query $(Corrup(U_{i}, 1))$. The success probability of ${\mathcal {A}}$ against the off-line password guessing attack is at most $\frac{q_{s}}{|{\mathcal {D}}|}$. Adding the Eqs. (2–7), we have

$$\begin{aligned} Adv_{{\mathbb {P}}}({\mathcal {A}})\le & \frac{q_{h}^{2}}{2^{l-1}}+\frac{(q_{s}+q_{e})^{2}}{p}+\frac{q_{s}}{2^{l-1}}+2\cdot (q_{h}\cdot Adv_{C, {\mathcal {A}}}(t)+\frac{q_{s}}{|{\mathcal {D}}|}) \end{aligned}$$

$\square$

6.2 Authentication Proof Based on the BAN Logic Model

The BAN logic model [43], a well-known formal security validation tool, plays a very important role in formal analysis to validate the security features of cryptographic protocols. In the following, we first show some basic notations and rules about BAN logic, where A and B are two entities involved in the protocol, and M, N are two messages, and K is a secret key.

• $A\mid \equiv M$: A believes M, i.e. A believes M is true.

• $A\;\lhd\;M$: A see M, i.e., a message containing M is sent to A by someone and M can be read by A.

• $A\mid\sim M$: A once said M, i.e., a message containing M once sent by A in some time.

• $A\Rightarrow M$: A control M, i.e., M is subject to the jurisdiction of A, and A is trusted for M.

• $\#(M)$: M is fresh, i.e., there is no any entity sent a message containing M at any time before the current session of protocol.

• $A\mathop {\longleftrightarrow }\limits ^{K}B$: K is shared between A and B, and can be used to secure the communication between them. K is called secure if any other entity cannot get K except A, B and the entity who is trusted by A or B.

• (M, N): M or N is a portion of message (M, N).

• $\{M, N\}_K$: M and N are encrypted with the key K.

• $(M, N)_K$: M and N are hashed by the key K.

• Rule 1. Message meaning rule: $\frac{A\mid \equiv A\mathop {\longleftrightarrow }\limits ^{K}B, A\;\lhd\; \{M\}_K}{A\mid \equiv B\mid \sim M}$, if A believes that he/she shared the key K with B, and A saw the message $\{M\}_K$, A trust that B once said X.

• Rule 2. Nonce verification rule: $\frac{A\mid \equiv \#(M), A\mid \equiv B\mid \sim M}{A\mid \equiv B\mid \equiv M}$, if A believes M is fresh and A believes B once said M, A believes B believes M.

• Rule 3. Jurisdiction rule: $\frac{A\mid \equiv B\Rightarrow M, A\mid \equiv B\mid \equiv M}{A\mid \equiv M}$, if A believes that B had jurisdiction right to message M and A believes B believes M, A believes M.

• Rule 4. Freshness conjuncatenation rule: $\frac{A\mid \equiv \#(M)}{A\mid \equiv \#(M, N)}$, if M as a portion of message (M, N) is fresh, message (M, N) is also fresh.

• Rule 5. Belief rule: $\frac{A\mid \equiv B\mid \equiv (M,N)}{A\mid \equiv B\mid \equiv (M)}$, if A believes B believes the message set (M, N), A also believes B believes the message M.

BAN logic [43] had widely be used to analyze the correctness of authentication with key agreement protocol. Protocol correctness means that both of the communication parties confirm that they shared a fresh session key with each other after mutual authentication. Thus, the user authentication with key agreement protocol should achieve the following goals:

• G 1: $U_i\mid \equiv (U_i \overset{SK}{\longleftrightarrow }S_j)$.

• G 2: $U_i\mid \equiv S_j\mid \equiv (U_i \overset{SK}{\longleftrightarrow } S_j)$.

• G 3: $S_j\mid \equiv (U_i \overset{SK}{\longleftrightarrow }S_j)$.

• G 4: $S_j\mid \equiv U_i\mid \equiv (U_i \overset{SK}{\longleftrightarrow } S_j)$.

First, the idealized form of the messages in our protocol are transformed according to the BAN logic notations:

• Message 1: $U_i\rightarrow RC$: $(ID_i,SID_j,U_i\overset{{\{X\}_{w\cdot r_i}}}{\longleftrightarrow } RC)_{h(ID_i\Vert w)}$

• Message 2: $S_j\rightarrow RC$: $(S_j\overset{h(SID_j\Vert w)}{\longleftrightarrow }RC)_{h(SID_j\Vert w)}$

• Message 3: $RC\rightarrow S_j$: $(C_1,C_3,S_j\overset{r_k}{\longleftrightarrow }RC)_{h(SID_j\Vert w)}$

• Message 4: $RC\rightarrow U_i$: $(SID_j, C_2, C_3,U_i\overset{{\{X\}_{w\cdot r_i}}}{\longleftrightarrow }RC)_{h(ID_i\Vert w)}$

• Message 5: $S_j\rightarrow U_i$: $(SID_j, C_1,U_i\overset{{SK}}{\longleftrightarrow }S_j)_{h(K_j\Vert r_k)}$

• Message 6: $U_i\rightarrow S_j$: $(C_3,U_i\overset{{SK}}{\longleftrightarrow } S_j)_{h(K_j\Vert r_k)}$

Second, some initial assumptions of our protocol are given below:

$$\begin{aligned} \begin{array}{ll} A_1.\ U_i\mid \equiv \# (r_i)& \quad A_8.\ S_j\mid \equiv S_j\overset{{h(SID_j\Vert w)}}{\longleftrightarrow } RC\\ A_2.\ S_j\mid \equiv \# (r_j)& \quad A_9.\ RC\mid \equiv S_j\overset{{h(SID_j\Vert w)}}{\longleftrightarrow } RC\\ A_3.\ RC\mid \equiv \# (r_k)& \quad A_{10}.\ S_j\mid \equiv U_i\overset{{h(K_j\Vert r_k)}}{\longleftrightarrow } S_j\\ A_4.\ U_i\mid \equiv \# (C_1)& \quad A_{11}.\ U_i\mid \equiv U_i \overset{{h(K_j\Vert r_k)}}{\longleftrightarrow } S_j\\ A_5.\ S_j\mid \equiv \# (C_3)& \quad A_{12}.\ U_i\mid \equiv S_j\Rightarrow (U_i\overset{{SK}}{\longleftrightarrow } S_j)\\ A_6.\ U_i\mid \equiv U_i\overset{{h(ID_i\Vert w)}}{\longleftrightarrow } RC& \quad A_{13}.\ S_j\mid \equiv U_i\Rightarrow (U_i\overset{{SK}}{\longleftrightarrow } S_j)\\ A_7.\ RC\mid \equiv U_i\overset{{h(ID_i\Vert w)}}{\longleftrightarrow } RC & \end{array} \end{aligned}$$

$A_1$, $A_2$ and $A_3$ mean that $U_i$, $S_j$ and RC generate fresh random numbers $r_i$, $r_j$ and $r_k$, respectively. Therefore, they assure their freshness, respectively. Since $C_1\equiv T_{r_i}(X)$ mod p, $C_3\equiv T_{r_j}(X)$ mod p, $A_4$ and $A_5$ are valid according to $A_1$ and $A_2$. $A_6-A_9$ are hold because the secret key is shared by one party and can be generate by the other party. With the assumptions $A_{10}$ and $A_{11}$, the secret $h(K_j\Vert r_k)$ can be generated by $U_i$ and $S_j$ from message 4 and message 3, respectively, and thus RC is trusted by both $U_i$ and $S_j$. Therefore, any other party cannot get the secret $h(K_j\Vert r_k)$ and the assumptions $A_{10}$ and $A_{11}$ are hold. The assumption $A_{12}$ ($A_{13}$) is also hold because once $U_i$ $(S_j)$ generates $r_i$ $(r_j)$ and submits $C_1$ $(C_3)$ to $S_j$ $(U_i)$, the final session key SK is determined by the random number $r_j$ $(r_i)$, which is generated by $S_j$ $(U_i)$ from the viewpoint of $U_i$ ($S_j$).

Then, we prove the idealized form of the proposed protocol using the initial assumptions and the rules of the BAN logic. The detailed descriptions of this are as follows:

• In accordance with the message 5, we can get

• $S_1$: $U_i\;\lhd\; (SID_j, C_1,U_i\overset{{SK}}{\longleftrightarrow } S_j)_{h(K_j\Vert r_k)}$.

• In accordance with $S_1$ and $A_{11}$, the following judgement can be obtained by applying the message meaning rule

• $S_2$: $U_i\mid \equiv S_j\mid \sim (SID_j, C_1,U_i\overset{{SK}}{\longleftrightarrow } S_j)$.

• In accordance with $S_2$ and $A_4$, the following judgement can be derived by applying the freshness conjuncatenation rule

• $S_3$: $U_i\mid \equiv \#(SID_j, C_1,U_i\overset{{SK}}{\longleftrightarrow } S_j)$.

• In accordance with $S_2$ and$S_3$, the following judgement can be obtained by applying the nonce verification rule

• $S_4$: $U_i\mid \equiv S_j\mid \equiv (SID_j, C_1,U_i\overset{{SK}}{\longleftrightarrow } S_j)$.

• In accordance with $S_4$, the following judgement can be derived by applying belief rule

  $$\begin{aligned} S_5: U_i\mid \equiv S_j\mid \equiv (U_i\overset{{SK}}{\longleftrightarrow }S_j). \end{aligned}$$

  (G 2)

• In accordance with $S_5$ and $A_{12}$, the following judgement can be obtained by applying jurisdiction rule

  $$\begin{aligned} S_6: U_i\mid \equiv (U_i\overset{{SK}}{\longleftrightarrow } S_j). \end{aligned}$$

  (G 1)

• In accordance with message 6, we can get

• $S_7$: $S_j\;\lhd\;(C_3,U_i\overset{{SK}}{\longleftrightarrow } S_j)_{h(K_j\Vert r_k)}$.

• In accordance with $S_7$ and $A_{10}$, the following judgement can be obtained by applying the message meaning rule

• $S_8$: $S_j\mid \equiv U_i\sim (C_3,U_i\overset{{SK}}{\longleftrightarrow } S_j)$.

• In accordance with $S_8$ and $A_5$, the following judgement can be derived by applying the freshness conjuncatenation rule

• $S_9$: $S_j\mid \equiv \#(C_3,U_i\overset{{SK}}{\longleftrightarrow } S_j)$.

• In accordance with $S_8$ and$S_9$, the following judgement can be obtained by applying the nonce verification rule

• $S_{10}$: $S_j\mid \equiv U_i\mid \equiv (C_3,U_i\overset{{SK}}{\longleftrightarrow } S_j)$.

• In accordance with $S_{10}$, the following judgement can be obtained by applying belief rule

  $$\begin{aligned} S_{11}: S_j\mid \equiv U_i\mid \equiv (U_i\overset{{SK}}{\longleftrightarrow } S_j). \end{aligned}$$

  (G 4)

• In accordance with $S_{11}$ and $A_{13}$, the following judgement can be obtained by applying jurisdiction rule

  $$\begin{aligned} S_{12}: S_j\mid \equiv (U_i\overset{{SK}}{\longleftrightarrow } S_j). \end{aligned}$$

  (G 3)

From the judgements $S_6$, $S_5$, $S_{12}$ and $S_{11}$, we can see that our protocol can achieve all the goals 1, 2, 3 and 4, and both of $U_i$ and $S_j$ believe that they shared a session key $SK\equiv T_{{r_i}{r_j}}(X)$ mod p with each other.

6.3 Further Discussions on Various Attacks

In this part, we demonstrated that our protocol meets all known functional properties and withstands various attacks.

6.3.1 Resist Insider Attack

In the registration stage of our protocol, $U_i$ submits the registration request $\{ID_i, e_i = h(PW_i\Vert N_i)\}$ to RC for registration, where the actual password $PW_i$ is masked by the random number $N_i$. Therefore, the privileged insider of RC cannot reveal $PW_i$ of $U_i$ without knowing $N_i$. Thus, the proposed protocol is free from insider attack.

6.3.2 Quick Detection of Unauthorized Login

In the login and session key agreement stage of the proposed protocol, $U_i$ keys $ID_i$, $PW_i$, and chooses the identity $SID_j$ of $S_j$. Then the smart card calculates $e_i = h(PW_i\Vert N_i)$, $A_i^{\prime } = h(ID_i\Vert e_i)$ and checks $A_i^{\prime } \mathop {=}\limits ^{?} A_i$. If $A_i^{\prime } \ne A_i$, it means one of the inputted user’s identity or password is invalid, and thus the login request is aborted by the smart card. Otherwise, it is asserted that the inputted identity and password are correct. Therefore, in our protocol, any unauthorized login due to wrong password or identity can be quickly detected in the smart card side, which is helpful to avoid network congestion and DoS attack.

6.3.3 Mutual Authentication Among Three Parties

In our protocol, RC is not only responsible for the initialization of the (i) system’s parameters, (ii) user registration and (iii) server registration, but also participates in the authentication process, which is needed in the multi-server architecture to enhanced the security of the system. In login and session key agreement stage of our protocol, $U_i$, $S_j$ and RC can authenticate each other.

• Mutual authentication between $S_j$ and RC: In step 1 of login and session key agreement stage, $U_i$’s login request $\{UID_i, C_1, M_{ik}\}$ was transmitted to the target server $S_j$. Then $S_j$ calculates some information and forwards the login request message $\{UID_i, C_1, M_{ik}, SID_j, C_3$, $M_{jk}\}$ to RC. Then RC can compute $K_j^{\prime } = h(SID_j\Vert w)$, $M_{jk}^{\prime } = h(K_j^{\prime }\Vert C_3)$ and authenticates $S_j$ by checking whether $M_{jk}^{\prime }$ equals to $M_{jk}$. On the contrary, when receiving RC’s response message $\{ID_i, M_{kj}, F_i, M_{ki}\}$ in step 4 of login and session key agreement stage, $S_j$ derives $r_k^{\prime } = K_j\oplus D_i$, $M_{kj}^{\prime } = h(K_j\Vert C_1\Vert C_3\Vert r_k^{\prime })$ and checks whether $M_{kj}^{\prime } = M_{kj}$. If they are equal, the validity of RC is authenticated by $S_j$. Since the shared secret key $K_j = h(SID_j\Vert w)$ between $S_j$ and RC is contained in their exchanged messages, any other entity cannot forged the valid messages without the secret information $h(SID_j\Vert w)$. Therefore, mutual authentication between $S_j$ and $R_C$ is achieved.

• Mutual authentication between $U_i$ and RC In our protocol, the mutual authentication between $U_i$ and RC relies on the shared secret information $f_i = h(ID_i\Vert w)$. In step 1 of login and session key agreement stage, $U_i$’s login request $\{UID_i, C_1, M_{ik}\}$ was transmitted to $S_j$. Then $S_j$ calculates some information and forwards the login request message $\{UID_i, C_1, M_{ik}, SID_j, C_3$, $M_{jk}\}$ to RC. RC derives $C_2^{\prime } \equiv T_w(C_1)$ mod p, $ID_i^{\prime } = UID_i\oplus h(C_1\Vert C_2^{\prime })$, $f_i^{\prime } = h(ID_i^{\prime }\Vert w)$, $M_{ik}^{\prime } = h(ID_i^{\prime }\Vert SID_j\Vert f_i^{\prime }\Vert C_1\Vert C_2^{\prime })$ and checks $M_{ik}^{\prime } \mathop {=}\limits ^{?} M_{ik}$. The validity of $U_i$ is authenticated by RC if $M_{ik}^{\prime }$ equals to $M_{ik}$. On the contrary, RC sends a response message $\{D_i, M_{kj}, F_i, M_{ki}\}$ to $S_j$, and $S_j$ forwards the mutual authentication message $\{F_i, M_{ki}, C_3, M_{ji}\}$ to $U_i$ in step 4. $U_i$ computes $M_{ki}^{\prime } = h(f_i\Vert F_i\Vert SID_j\Vert C_2\Vert C_3)$ and checks $M_{ki}^{\prime } \mathop {=}\limits ^{?} M_{ki}$. If $M_{ki}^{\prime } = M_{ki}$, the validity of RC is authenticated by $U_i$ since $f_i = h(ID_i\Vert w)$ is only known to $U_i$ and RC and any other entity cannot forged the valid messages exchanged between $U_i$ and RC. Therefore, $U_i$ and RC mutually authenticate each other in the proposed protocol.

• Mutual authentication between $U_i$ and $S_j$: In step 2 of login and session key agreement stage of our protocol, $S_j$ gets $C_1$ from $U_i$’s login request message $\{UID_i, C_1, M_{ik}\}$. In step 4, $S_j$ computes $r_k^{\prime } = K_j\oplus D_i$, $E_i^{\prime } = h(K_j\Vert r_k^{\prime })$, $SK \equiv T_{r_j}(C_1)$ mod p, $M_{ji} = h(SID_j\Vert C_1\Vert C_3\Vert E_i^{\prime }\Vert SK)$ and forwards the response message $\{F_i, M_{ki}, C_3, M_{ji}\}$ to $U_i$. Then in step 5, $U_i$ computes $E_i^{\prime \prime } = F_i\oplus f_i\oplus C_2$, $SK^{\prime } \equiv T_{r_i}(C_3)$ mod p, $M_{ji}^{\prime } = h(SID_j\Vert C_1\Vert C_3\Vert E_i^{\prime \prime }\Vert SK^{\prime })$ and authenticates $S_j$ by checking $M_{ji}^{\prime }\mathop {=}\limits ^{?} M_{ji}$. If they are equal, $S_j$ is authenticated by $U_i$, then $U_i$ computes $M_{ij} = h(C_3\Vert E_i^{\prime \prime }\Vert SK^{\prime })$ and submits the mutual authentication message $\{M_{ij}\}$ to $S_j$. When receiving $\{M_{ij}\}$, $S_j$ computes $M_{ij}^{\prime } = h(C_3\Vert E_i^{\prime }\Vert SK)$ and $U_i$ is authenticated by $S_j$ if $M_{ij}^{\prime } = M_{ij}$. Since $SK \equiv T_{{r_i}{r_j}}(X)$ mod p is shared between $U_i$ and $S_j$, and any other entity cannot forged the valid messages exchanged between $U_i$ and $S_j$ without knowing SK. Thus, our protocol achieved mutual authentication between $U_i$ and $S_j$.

6.3.4 Perfect Forward Secrecy

It is an valuable security feature for a password-based authentication with the session key agreement protocol. This property includes that the adversary cannot derive the previously established session keys even if he/she gets the system master secret key w. In the proposed protocol, $U_i$ and $S_j$ can share a session key $SK \equiv T_{{r_i}{r_j}}(X)$ mod p after mutual authentication, where SK has no relationship with the master secret key w. However, SK is only related to the random number $r_i$ and $r_j$ chosen by $U_i$ and $S_j$, respectively. Besides, the attacker cannot compute $r_i$, $r_j$ and $T_{{r_i}{r_j}}(X)$ from $C_1$, $C_2$ due to the discrete logarithm problem (DLP) or Diffie-Hellman problem (DHP). Therefore, the proposed protocol can provide perfect forward secrecy.

6.3.5 Known-Key Security

Known-key security is another important security feature for a password-based authentication with the session key agreement protocol. It states that the compromise of one session key should not be helpful to do harm for other session keys. In the proposed protocol, the session key $SK \equiv T_{{r_i}{r_j}}(X)$ mod p relies on the random numbers $r_i$ and $r_j$. Since the random numbers $r_i$ and $r_j$ are dynamically changing in each session, one session key is independent of the other session keys. Therefore, even if one session key $SK \equiv T_{{r_i}{r_j}}(X)$ mod p is compromised, the attacker cannot get the other session key $SK^{\prime } \equiv T_{{r_i^{\prime }}{r_j^{\prime }}}(X)$ mod p without knowing $r_i^{\prime }$ and $r_j^{\prime }$. Thus, the proposed protocol can provide known-key security.

6.3.6 Resist Registration Center and Server Spoofing Attacks

In [33], RC shares the master secret key w with all the servers, which not only increases the security risk of the authentication system, but also leads to the vulnerability of registration center and sever spoofing attacks. In the proposed protocol, the master secret key w is only held by RC. Since w is long enough and safeguarded by the secure hash function $h(\cdot )$, the adversary could not drive w from the communication messages transmitted over the public channel. Therefore, the attacker cannot impersonate RC, and accordingly, the registration center spoofing attack can be avoided in our protocol. In addition, each $S_j$ holds a secret key $h(SID_j\Vert w)$, which is different from those of other server’s. Therefore, without knowing $h(SID_j\Vert w)$, any attacker or even the legal but malicious server cannot impersonate other servers, and therefore, the proposed protocol can resist server spoofing attack.

6.3.7 Resist Replay Attack

In our protocol, $U_i$, $S_j$ and RC generate different random numbers $r_i$, $r_j$ and $r_k$, respectively, for each session, which ensures that the messages belonging to current session are valid only for this session, and different with the messages of other session’s. Therefore, the attacker has no chance to launch a replay attack to the proposed protocol, and our protocol is free from this kind of attack.

6.3.8 User Anonymity

In the proposed protocol, the masked identity $UID_i (= ID_i\oplus h(C_1\Vert C_2))$ replaced the real identity $ID_i$ to be contained in the login request message $\{UID_i, C_1, M_{ik}\}$. Note that RC holds the master secret key w and only he/she can derive $U_i$’s real identity $ID_{i}$ by computing $C_2^{\prime } \equiv T_w(C_1)$ mod p, and $ID_i^{\prime } = UID_i\oplus h(C_1\Vert C_2^{\prime })$. Any attacker who wants to reveal the real identity of $U_i$ has to face the DLP problem. Therefore, user anonymity is achieved in our protocol.

6.3.9 Resist Stolen Smart Card Attack

Smart card is widely in two-factor password-based user authentication. However, some studies have shown that the information stored in the smart card can be derived by some side channel attacks. Therefore, the stolen smart card attack should be considered in designing the authentication protocol. In this attack, the adversary captured a lost/stolen smart card of an authorized and then he/she may try to changed or guessed the password, or may try to utilized the smart card to login to the system to impersonate the user. In our protocol, if $U_i$’s lost/stolen smart card was captured by an adversary, then he/she can derive the information $\{A_i, B_i, X, R, h(\cdot ), N_i\}$ from the smart card, where $A_i = e_i\oplus f_i$, $e_i = h(PW_i\Vert N_i)$, $f_i = h(ID_i\Vert w)$, and $B_i = h(ID_i\Vert e_i)$. We can see that $A_i$ and $B_i$ are both related to $ID_i$ and $PW_i$, therefore, it is impossible for the adversary to guess $ID_i$ and $PW_i$ from the smart card’s information. Without knowing $ID_i$ and $PW_i$, the adversary cannot guess or change the password, and thus, he/she is unable to impersonate $U_{i}$. Therefore, our protocol is free from stolen smart card attack.

7 Comparisons on Functionality and Performance

In this subsection, the evaluations of the proposed protocol are given by comparing it with the protocol in [33] on functionality and performance aspects. The functionality comparison between our protocol and the protocol in [33] is listed in Table 2, from which we can assert that our protocol is more ideal and secure than the protocol in [33], because the proposed protocol can resist most of attacks and has additionally functionalities.

Table 2 Functionality comparisons

For performance evaluation, we have considered the followings:

• $T_{H}:$ Time required to compute hash function.

• $T_{C}:$ Time required to compute extended chaotic function.

Since the login and session key agreement phases should be executed in every time when the user access different servers, we only compare the computation costs of these phases in the comparison. The comparison results of our protocol and the protocol in [33] are summarized in Table 3. Table 3 shows that the presented protocol needs 8 additional hash operations than the protocol in [33]. Based on the system configuration (1) 3GB RAM and (2) Pentium IV 3.2 GHz processor, the experimental results executed in [52] and we have $t_{H}\approx 0.20~\text{ ms }$ and $t_{C}\approx 32.40~\text{ ms},$ respectively. We compared our protocol and the protocol in [33] against the execution time (millisecond) in Table 4.

In the proposed protocol, the registration center RC is involved in the authentication process, which helps avoid server and registration center spoofing attacks. Besides, our protocol owns a mechanism to verify the validity of the password in the beginning of login and session key agreement stage, which not only makes our protocol efficient to quickly detect the unauthorized login, but also allows users to freely change the password. Therefore, the addition of 8 hash operations is worthy to make our protocol more secure and achieve more ideal functions.

Table 3 Performance comparisons in login and session key agreement stage

Table 4 Execution time (ms) comparisons in login and session key agreement stage

8 Conclusion and Future Work

In this paper, we reviewed and analyzed the security drawbacks of an extended chaotic maps-based authentication multi-server protocol in [33]. We find the protocol in [33] is vulnerable to registration center and server spoofing attacks. These two attacks are possible due to the master secret key w is shared among RC and all servers. Additionally, the protocol in [33] does not support password change for users. Besides, there is no detection mechanism for unauthorized login in the protocol in [33], which causes unnecessary computations and communications, and induces DOS attack. To remedy the aforementioned drawbacks, a new extend chaotic map based multi-server authentication with key agreement protocol has been presented in this paper, where the user can enjoy different services provided by multiple servers with one time registration. The provable security analysis of the presented protocol is provided in the random oracle model. In addition, the formal security of our protocol is also validated using BAN logic model. Besides, the other functional features and security of presented protocol are discussed, and it only increase 8 hash operations to remedy the aforementioned flaws. Compared with the protocol in [33], the presented protocol is a more secure and ideal chaotic maps-based multi-server authentication protocol for practical use. In the future, we would like to establish a security model for chaotic based authentication and key agreement protocol, and design the authentication schemes with key agreement under this model. Furthermore, we will consider the privacy protection for the design of security protocols, and explore the effective method for user authentication and key agreement with privacy protection.