A Provably Secure ID-Based Mutual Authentication and Key Agreement Scheme for Mobile Multi-Server Environment Without ESL Attack

Abstract

In mobile multi-server authentication, a client can access different servers over an insecure channel like Internet and wireless networks for numerous online applications. In the literature, several multi-server authentication schemes for mobile clients have been devised. However, most of them are insecure against ephemeral secret leakage (ESL) attack and other vulnerabilities. For mutual authentication and key agreement, mobile client and server used ephemeral secrets (random numbers) and leakage of these secrets may be possible in practice. Since these are generated by an external source that may be controlled by an adversary. Also they are generally pre-computed and stored in insecure devices. Thus, if the secrets are leaked then the session key would turn out to be known and the private keys of client and server may be compromised from the eavesdropped messages. This phenomenon is called ESL attack. To defeat the weaknesses, in this paper, we design an ESL attack-free identity-based mutual authentication and key agreement scheme for mobile multi-server environment. The proposed scheme is analyzed and proven to be provably secure in the random oracle model under the Computational Diffie–Hellman assumption.

1 Introduction

With the tremendous development of Network technologies and the availability of portable mobile devices (e.g., PDA, mobile phone, notebook PC), people are accessing a number of servers using their mobile devices for different purpose like online shopping, online pay-TV, online bill payment, online banking transaction, file sharing, online game, distributed electronic medical records system, etc. [1–3]. In order to get access remote server, a mutual authentication with session key agreement scheme is required in which a client first authenticates himself/herself to the server and then the client verifies the legitimacy of the server. After mutual authentication, both the client and the remote server compute a common session key, which will be used for secure information exchange between them in subsequent communications. To achieve this goal, various single server authentication systems [4–8] have been proposed in the literature. However, this architecture is not always suitable in some situation if client wants service from numerus servers. Based on single server authentication architecture, it is very difficult for a client to register himself/herself to multiple servers with different secrets (e.g., password or private key). To address these issues, varieties of multi-server authentication architecture have been proposed by the research community [9–13]. In this architecture, client(s) and remote server(s) first register to a registration center (RC) and then client(s) accesses all the servers using only one secret over Internet and wireless networks. It is known that the Internet and wireless networks are prone to errors and insecure since no integrated security mechanisms are available from their inception. Also the energy resources, storage and computing capability of mobile devices are very limited, therefore the design of a efficient and secure multi-server authentication scheme suitable for mobile environment is a challenging task.

1.1 Related Studies

In 2008, Tsai [9] proposed a mutual authentication and key agreement (MAKA) scheme for multi-server environment using hash function, which is shown to be insecure against impersonation attack and forward security [14]. In order to achieve client’s anonymity, Geng and Zhang [10] proposed a dynamic ID-based MAKA protocol for multi-server environment based on password and bilinear pairing. In 2009, Liao and Wang [11] proposed another dynamic ID-based MAKA protocol for multi-server environment based on password. Later on, Hsiang and Shih [12] found which the scheme [11] is vulnerable to insider attack, masquerade attack, server spoofing attack and registration center spoofing attack. To overcome these weaknesses, Hsiang and Shih proposed an improved scheme that is also found to be susceptible to the masquerade attack and the server spoofing attack [15]. In 2011, Lee et al. [13] analyzed that Hsiang et al.’s MAKA scheme [12] does not provide mutual authentication and resilience against masquerade attack, server spoofing attack, and is not easily repairable. To overcome these weaknesses, Lee et al. proposed an improved scheme. Furthermore, Sood et al. [16] proposed an improved dynamic ID-based MAKA scheme over Hsiang et al.’s scheme and claimed that their protocol provides desired securities. However, Li et al. [17] showed that Sood et al.’s protocol is still vulnerable to leak-of-verifier attack, stolen smart card attack and impersonation attack. Besides, the authentication and session key agreement phase of Sood et al.’s protocol is incorrect. Li et al. [17] then proposed an improved protocol. However, Han [18] demonstrated the protocol [17] is unsuitable for practical applications and insecure against password guessing attack, impersonation attack and replay attack.

In 2013, Li et al. [19] design a smart card and dynamic ID-based MAKA scheme for multi-server environment, which is proven to be insecure against stolen smart card and off-line password guessing attack, replay attack, impersonation attack and server spoofing attack [20]. In 2013, Wang and Ma [21] proposed a password and smart card based MAKA scheme for multi-server environment and demonstrated that their scheme could overcome various attacks. However, He and Wu [22] analyzed that the scheme is vulnerable to the server spoofing attack, the impersonation attack, the privileged insider attack and the off-line password guessing attack. In 2012, Chuang and Tseng [23] proposed a provably secure ID-MAKA protocol for multi-server environment in the random oracle model using elliptic curve bilinear pairing and IBC. In the same year, Han and Zhu [24] proposed an efficient and pairing-free ID-MAKA protocols for multi-server environment using elliptic curve cryptography (ECC) and IBC. They proved that their sachem is provably secure in the random oracle model under the CDH assumption. However, all the scheme discussed in this paper and the newly proposed schemes [23, 24] are vulnerable to ESL attack which is proven in the Sect. 6.

1.2 Motivations and Contributions

In the literature, three types of multi-server authentication schemes using password or certificate authority-based public key cryptography (CA-PKC) or identity-based cryptosystem (IBC) have been proposed. In the password based schemes, servers generally maintain the password tables. In addition to that, these schemes are susceptible to the risk of modifying the password table and are insecure against different attacks including online/offline password guessing attack, stolen-verifier attack, denial of service attack, user’s impersonation attack, server’s masquerade attack [12, 14–16, 18, 20, 25]. Furthermore, in the login phase of password-based schemes, authentication server communicates with RC for client authentication and it incurs many rounds and additional communication costs.

On the other hand, CA-PKC based protocols have some other limitations such as it needs a certificate authority (CA), which uses a global public key infrastructure (PKI) to maintain the certificates for users’ public keys. For a large number of users, CA requires huge storage space and complex certificate management process to keep up and store the public keys and certificates, and users need to verify the corresponding certificate of others for which extra computations are involved. These problems degrade the overall performance of the system and thus, the CA-PKC based protocols are not suitable for resource constrained mobile devices. However, IBC based schemes removes the problem of CA-PKC based protocols. In IBC setting, user’s publicly known identity e.g., email address, rather than a random number, is used as public key and the corresponding private key is generated key by the system’s trusted authority, called private key generator (PKG) based on the user’s public key and PKG’s secret key [26, 27].

In the schemes mentioned above, the mobile client and server used ephemeral secrets/random numbers for mutual authentication and session key generation. If the ephemeral secret keys are leaked, an adversary can reveal the session key and the secrets of server and client from the eavesdropped messages. This attack is called ephemeral secret leakage (ESL) attack [28–31] or known session-specific temporary information attack (KSSTIA) [32–37]. Leakage of these secrets is possible in practical applications since they are generally pre-computed and stored in insecure memory devices and these secrets are generated by an external source that may be controlled by an adversary. If the ephemeral secret is not deleted completely after the protocol execution, an adversary may hijack the sender’s computer and get the same [38].

Another most important security requirement of multi-server authentication system is client’s anonymity. Most of the multi-server authentication systems available in the literature are designed for either general client [9, 21, 40, 41] or anonymous client [10–13, 16, 17, 19] i.e., they are not suitable for both purpose. In some situation (electronic voting, secret online-order placement, pay TV), client’s anonymity (secrecy) is required, otherwise some personal information about the client may be leaked from the static identity. In addition, the security of most of the multi-server authentication schemes are not provably secure in the random oracle model [39] and thus they vulnerable to different known attacks. Thus, the designing of anonymous/dynamic ESL attack-free MAKA scheme based on IBC for both the general and anonymous mobile client [23, 24] in the random oracle model is of great concern. In this paper, we designed an ESL attack-free ID-MAKA scheme using elliptic curve bilinear pairing [27, 42, 43] for mobile multi-server environments. The security of the proposed scheme is analyzed in our security model and shown to be provably secure under the Computational Diffie–Hellman (CDH) assumption.

1.3 Organization of the Paper

The rest of the paper is organized as follows. The bilinear pairing and the related computational problem and its assumption are briefly described in Sect. 2. The Sect. 3 describes the adversarial model of ID-MAKA scheme. The proposed ESL attack-free ID-MAKA scheme for multi-server mobile client is described in Sect. 4. The correctness analysis and provable security analysis of the proposed ESL attack-free ID-MAKA scheme are given in Sect. 5. The comparative analysis of our scheme with others are addressed in Sect. 6. Finally, Sect. 7 concludes the paper.

2 Preliminaries

This section discussed the basics of elliptic curve bilinear pairing and related computational hard problems frequently used in modern cryptography.

2.1 Bilinear Pairing

Let $G_q$ is a subgroup of the additive group of points on an elliptic curve over a finite field $E/F_{q}$ and $G_m$ is a cyclic subgroup of the multiplicative group over a finite field $F_{q}$. We also assume that both $G_q$ and $G_m$ have the same order $q$ ($q$ is a large prime number, where $q\ge 2^{k}$ and $k$ is a security parameter). The bilinear map $e:G_q\times G_q\rightarrow G_m$ is called admissible bilinear map if it has the following properties:

• (1) Bilinearity: For any $(P, Q)\in G_{q}$ and $a, b\in Z_{q}^{*}$, we have $e(aP, bQ)=e(P, Q)^{ab}$.

• (2) Non-degenerate: For all $(P, Q)\in G_{q}$ such that $e(P, Q)\ne 1_{m}$ must hold, where $1_{m}$ is the identity element of $G_{m}$. It means all the pairs in $G_q\times G_q$ do not map to the identity element in $G_{m}$, i.e. if $P$ and $Q$ are two generators of $G_{q}$ then $e(P, Q)$ is a generator of $G_{m}$.

• (3) Computability: There must be an efficient algorithm that can compute $e(P, Q)$ for any $(P, Q)\in G_{q}$.

The map $e$ will be derived either from the modified Weil pairing or Tate pairing over a finite field [27].

2.2 Computational Problems

In this section, we described the Computational Diffie–Hellman (CDH) Problem on elliptic curve that is are assumed to be intractable by a polynomial-time bounded algorithm. It is to noted that the security of the proposed scheme relies on the difficulty of CDH assumption.

Definition 1

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

Definition 2

(Computational Diffie–Hellman (CDH) problem) Given a random instance $(P, aP, bP)$, where $P \in G_{q}$, and $a, b \in Z_{q}^{*}$, computation of $abP$ is computationally hard by a polynomial-time bounded algorithm. The probability that a polynomial time-bounded algorithm $\mathcal {A}$ can solve the CDH problem is defined as $Adv^{CDH}_{\mathcal {A}, G_{q}}=Pr[\mathcal {A}(P, aP, bP)=abP: P\in G_q; a, b\in Z_{q}^{*}]$.

Definition 3

(Computational Diffie–Hellman assumption) For any probabilistic polynomial time-bounded algorithm $\mathcal {A}$, $Adv^{CDH}_{\mathcal {A}, G_{q}}$ is negligible.

3 Attack Model of ID-MAKA Scheme

Based on the concept of [23, 24, 28], a security model for ID-MAKA scheme for multi-server environment is presented in this section. In this adversarial model three roles are involved, called a trusted registration center ($RC$), $n$ mobile clients $\mathcal {U}=\{U_{i}: 1\le i\le n\}$ with identitites $ID_{Ui}$ ($1\le i\le n$) and $m$ authentication servers $\mathcal {S}=\{S_{j}: 1\le i\le m\}$ with identititiess $ID_{Sj}$ ($1\le j\le m$). Here we assume that the public parameters and identities $\mathcal {ID}=\{ID_{Ui}$, $ID_{Sj}$: $U_i\in \mathcal {U}$, $S_j\in \mathcal {S}\}$ are known to everyone and each client $U_i$ executes the scheme repeatedly with each server $S_j$. Instances of $U_i$ (or $S_j$) model distinct executions of the scheme. We denote $\Pi ^{s}_{i}$ is an $s^{th}$ instance of the participant $ID_i\in \mathcal {ID}$. We also assume that a probabilistic polynomial time bounded adversary $\mathcal {A}$ controls the communication channel, i.e., $\mathcal {A}$ can intercept, block, inject, remove, or modify, any messages transmitted in the media. In other words, we can say that all the messages between $U_i$ and $S_j$ are transmitted via $\mathcal {A}$. In order to violate the security of the scheme, adversary $\mathcal {A}$ can ask the following polynomial number of queries:

• Extract($ID_{i}$): With this query, $\mathcal {A}$ registers a public key $P_i$ on behalf of any client $ID_i$ of his choice.

• Send($\Pi _{i}^{t}, m$): Through this query, $\mathcal {A}$ can send a message $m$ to the oracle $\Pi _{i}^{t}$. On receiving $m$, the oracle $\Pi _{i}^{t}$ performs some calculation and replies to $\mathcal {A}$ according to the proposed scheme.

• $H_{0}(x_{0}$): Through this query, $\mathcal {A}$ can ask a $H_{0}$ hash query for the input $x_{0}$ to the oracle $\Pi _{i}^{t}$. Then $\Pi _{i}^{t}$ chooses a number $y_{0}\in _{R}Z_{q}^{*}$, outputs $y_{0}$ and then incorporates the tuple $\langle x_{0}, y_{0}\rangle$ to the initial-empty list $L^{list}_{H0}$.

• $H_{1}(x_{1}$): Through this query, $\mathcal {A}$ can ask a $H_{1}$ hash query for the input $x_{1}$ to the oracle $\Pi _{i}^{t}$. Then $\Pi _{i}^{t}$ chooses a number $y_{1}\in _{R}Z_{q}^{*}$, outputs $y_{1}P$ and then incorporates the tuple $\langle x_{1}, y_{1}P\rangle$ to the initial-empty list $L^{list}_{H1}$.

• $H_{2}(x_{2}$): Through this query, $\mathcal {A}$ can ask a $H_{2}$ hash query for the input $x_{2}$ to the oracle $\Pi _{i}^{t}$. Then $\Pi _{i}^{t}$ chooses a number $y_{2}\in _{R}Z_{q}^{*}$, outputs $y_{2}$ and then incorporates the tuple $\langle x_{2}, y_{2}\rangle$ to the initial-empty list $L^{list}_{H2}$.

• Reveal($\Pi _{i}^{t}$): This query is executed by $\mathcal {A}$ to obtain a session key $SK$ from the oracle $\Pi _{i}^{t}$. Now $\Pi _{i}^{t}$ returns the corresponding session key $SK$ if it is accepted, otherwise it outputs a null value.

• Corrupt($ID_{i}$): Through this query, $\mathcal {A}$ can corrupt a client $ID_{i}$ and can get the identity-based private key of the corrupted client.

• Test($\Pi _{i}^{t}$:) The adversary $\mathcal {A}$ is allowed to send a Test query to the oracle $\Pi _{i}^{t}$. On receiving a Test query, $\Pi _{i}^{t}$ chooses a bit $b\in \{0, 1\}$ and returns the session key if $b=1$, otherwise outputs a random string $SK\in _{R}Z_{q}^{*}$ as the session key.

Definition 4

(Partnership) Two oracles $\Pi ^{t}_{i}$ and $\Pi ^{s}_{j}$, where $i\in \mathcal {U}$ and $j\in \mathcal {S}$, are said to be partners if they mutually authenticates each other and computes a common session key between them.

Definition 5

(Freshness) An oracle $\Pi ^{t}_{i}$ with its partner $\Pi ^{s}_{j}$ is said fresh i.e., the participants $i\in \mathcal {U}$ and $j\in \mathcal {S}$ hold a fresh key $SK$ if the following two conditions hold:

• (1) Both the oracles $\Pi ^{t}_{i}$ and $\Pi ^{s}_{j}$ accept $SK$ as session key, but the Reveal query has not been invoked by $i$ and $j$.

• (2) It is allowed to ask the Send($\Pi ^{t}_{i}$) query or Send($\Pi ^{s}_{j}$) query after the Corrupt query is executed.

Definition 6

(Unforgeability and AKA security) An ID-MAKA scheme for multi-server environment offers existential unforgeability and maintains session key secrecy against adaptive chosen identity attacks if no polynomial tome bounded adversary $\mathcal {A}$ has a non-negligible advantage in the following game played between $\mathcal {A}$ and infinite set of oracles $\Pi ^{t}_{i}$ for $ID_{i}\in \mathcal {ID}$.

• (1) A private key is assigned to each client and server through the initialization phase related to the security parameter.

• (2) $\mathcal {A}$ may ask several queries and get back the results from the corresponding oracles.

• (3) There is no Reveal($\Pi ^{t}_{i}$) query or Corrupt($ID_{i}$) query being asked before the Test($\Pi ^{t}_{i}$) query has been asked.

• (4) $\mathcal {A}$ may ask other queries during asking the Test($\Pi ^{t}_{i}$) query where $\Pi ^{t}_{i}$ is fresh. $\mathcal {A}$ outputs its guess bit $b^{\prime }$ for the bit $b$ which is chosen in the Test($\Pi ^{t}_{i}$) query eventually and the game is terminated.

Definition 7

The authenticated key agreement (AKA) advantage $Adv^{AKA}_{\mathcal {P}}(\mathcal {A})=|2Pr[\mathcal {A}~$ $\text{ Succeeds }]-1|$ of the adversary $\mathcal {A}$ is defined as the success of probability to win the above game by violating the AKA security of an execution of a protocol $\mathcal {P}$, if $\mathcal {A}$ asks a single Test($\Pi ^{t}_{i}$) query and correctly guesses a bit $b$, which is selected by Test($\Pi ^{s}_{j}$) query.

Definition 8

The protocol $\mathcal {P}$ is AKA-secure if $Adv^{AKA}_{\mathcal {P}}(\mathcal {A})\le \epsilon$, for some negligible function $\epsilon$.

4 The Proposed ESL Attack-Free ID-MAKA Scheme

In this section, we presented an efficient ESL attack-free ID-MAKA scheme for mobile multi-server environment using elliptic curve cryptography and bilinear pairing. The description of the proposed scheme is given below:

4.1 Setup Phase

For given a security parameter $k\in Z^{+}$, the following actions are taken:

Step 1.:

$RC$ chooses a k-bit prime number $q$ and the tuple $\langle F_{q}, E/E_{q}, G_{q}, P\rangle$.

Step 2.:

$RC$ chooses $x\in Z_{q}^{*}$ as his master key and $P_{pub}=xP$ as his public key.

Step 3.:

$RC$ selects a bilinear map $e:G_{q}\times G_{q}\rightarrow G_{m}$ and three secure one-way hash functions $H_{0}:\{0, 1\}^{*}\rightarrow Z_{q}^{*}$, $H_{1}:\{0, 1\}^{*}\rightarrow G_{q}$ and $H_{2}:\{0, 1\}^{*}\rightarrow Z_{q}^{*}$.

Step 4.:

$RC$ publishes $\Omega =\langle F_{q}, E/F_{q}, e, G_{q}, P, P_{pub}, H_{0}, H_{1}, H_{2}\rangle$ as system’s parameter.

4.2 Extract Phase

Case 1: In this phase, a authentication server $S_j$, $(1\le j\le m)$ registers himself/herself to the $RC$ to get his identity-based private key. For this purpose, $S_j$ sends his/her identity $ID_{Sj}$ to $RC$ and then the $RC$ performs the followings:

Step 1. :

$RC$ chooses a number $y_{Sj}\in _{R}Z_{q}^{*}$ and computes $Y_{Sj}=y_{Sj}P$.

Step 2. :

$RC$ computes $l_{Sj}=H_{0}(ID_{Sj}, Y_{Sj})$ and $d_{Sj}=(y_{Sj}+xl_{Sj}) \text{ mod } q$.

Step 3. :

$RC$ delivers $\langle d_{Sj}, Y_{Sj}\rangle$ to $S_{j}$ over a out of band (secure) channel. Here, the following approaches are be used:

(a) Off-line mode: :

In this approach, $RC$ inserts $\langle d_{Sj}, Y_{Sj}\rangle$ into a smartcard and returns it to $S_j$ through a secure channel.

(b) On-line mode: :

In this approach, $S_{j}$ connects to $RC$ over Internet and then $RC$ uses Secure Socket Layer (SSL) in the https mode to deliver $\langle d_{Sj}, Y_{Sj}\rangle$ to $S_{j}$.

Step 4. :

On receiving $\langle d_{Sj}, Y_{Sj}\rangle$, $S_j$ validates it by checking whether the equation $Y_{Sj}+H_{0}(ID_{Sj}, Y_{Sj})P_{pub}=d_{Sj}P$ holds. The private key $d_{Sj}$ is valid if the above equation holds and vice-versa. Since we have

$$\begin{aligned} Y_{Sj}+H_{0}(ID_{Sj}, Y_{Sj})P_{pub}&= y_{Sj}P+(l_{Sj})xP \\&= (y_{Sj}+xl_{Sj})P \\&= d_{Sj}P \end{aligned}$$

Step 5. :

Finally, $S_j$ computes his/her public key as $P_{Sj}=d_{Sj}P$.

Case 2: The client registration phase is quite different from the server’s registration phase. According to [23, 24], we first list the different validity periods as follows:

Scenario 1 (Long validity period): :

In this case, a client $U_i$ ($1\le i\le n$) generally holds a long validity period and $RC$ maintains an identity revocation list (IDRL) to manage the member revocations connected with the system.

Scenario 2(Anonymous and short validity period): :

In this situation, a client $U_i$ ($1\le i\le n$) can access anonymously the services (i.e. prepaid mobile phone cards, online prepaid services, guest temporary security cards, etc.) offered by the server $S_j$ ($1\le j\le m$).

Similar to the $S_j$’s registration phase, for the Scenario 1, $U_i$ ($1\le i\le n$) sends his/her identity $ID_{Ui}$ to $RC$ and obtains his/her private key as follows:

Step 1.:

$RC$ chooses a number $y_{Ui}\in _{R}Z_{q}^{*}$ and computes $Y_{Ui}=y_{Ui}P$.

Step 2.:

$RC$ computes $l_{Ui}=H_{0}(ID_{Ui}, Y_{Ui}, \text{ validity } \text{ period })$ and $d_{Ui}=(y_{Ui}+xl_{Ui}) \text{ mod } q$.

Step 3.:

$RC$ delivers $\langle d_{Ui}, Y_{Ui}, \text{ validity } \text{ period }\rangle$ to $U_{i}$ using either off-line or on-line mode as described earlier.

Step 4.:

Now $U_{i}$ verifies his/her private key $d_{Ui}$ by checking whether the equation $d_{Ui}P=Y_{Ui}+H_{0}(ID_{Ui}, Y_{Ui}, \text{ validity } \text{ period })P_{pub}$ holds and then computes the corresponding public key as $P_{Ui}=d_{Ui}P$.

For the Scenario 2, $U_i$ ($1\le i\le n$) sends a registration requests to $RC$ and obtains his/her private key as follows:

Step 1.:

$RC$ chooses two numbers $x_{Ui}, y_{Ui}\in _{R}Z_{q}^{*}$ and computes $Y_{Ui}=y_{Ui}P$, anonymous identity $AID_{Ui}=H_{0}(x_{i})$ for the client $U_i$.

Step 2.:

$RC$ computes $l_{Ui}=H_{0}(AID_{Ui}, Y_{Ui}, \text{ validity } \text{ period })$ and $d_{Ui}=(y_{Ui}+xl_{Ui}) \text{ mod } q$.

Step 3. :

$RC$ sends $\langle d_{Ui}, Y_{Ui}, AID_{Ui}, \text{ validity } \text{ period }\rangle$ to $U_{i}$ through either off-line or on-line mode and accordingly $U_{i}$’computes his/her public key as $P_{Ui}=d_{Ui}P$.

4.3 Mutual Authentication and Key Agreement Phase

In this section, we described the mutual authentication and key agreement phase of our ESL attack-free ID-MAKA scheme. This phase is identical for Scenarios 1 and 2. The difference is only the transmitted identity. For simplicity, we use the client $U_i$ with the identity $ID_{Ui}$ throughout this phase. Without loss of generality, assume that the client $U_i$ wants to access the resources of the server $S_{j}$ whose identity is $ID_{Sj}$. The description of the phase is given as follows:

Step 1.:

$U_i$ chooses a number $r_{Ui}\in _{R}Z_{q}^{*}$ and a current timestamp $T_{Ui}$, then computes $R_{Ui}=r_{Ui}P$, $H_{Ui}=H_{1}(ID_{Ui}$, $ID_{Sj}$, $Y_{Ui}$, $R_{Ui}$, $T_{Ui}$, $\text{ validity } \text{ period })$ and $V_{Ui}=d_{Ui}H_{Ui}$. Then $U_i$ sends the message $\langle ID_{Ui}$, $Y_{Ui}$, $R_{Ui}$, $T_{Ui}$, $V_{Ui}$, $\text{ validity } \text{ period }\rangle$ to the authentication server $S_j$ over an open network.

Step 2.:

On receiving the message $\langle ID_{Ui}$, $Y_{Ui}$, $R_{Ui}$, $T_{Ui}$, $V_{Ui}$, $\text{ validity } \text{ period }\rangle$ at time $T_{Ui}^{\prime }$, $S_j$ checks whether valid period is overdue or not, whether $T_{Ui}^{\prime }-T_{Ui}\le \Delta T_{Ui}$ holds, and then checks whether $ID_{Ui}$ exists in the IDRL or not. If the valid period is overdue or $T_{Ui}$ is not fresh or $ID_{Ui}\in IDRL$, $S_j$ rejects $U_i$’s login request, else proceeds to the next step.

Step 3.:

$S_j$ computes $H_{Ui}=H_{1}(ID_{Ui}, ID_{Sj}, Y_{Ui}, R_{Ui}, T_{Ui}, \text{ validity } \text{ period })$, $P_{Ui}=Y_{Ui}+H_{0}(ID_{Ui}, Y_{Ui}, \text{ validity } \text{ period })P_{pub}$ and verifies whether the equation $e(V_{Ui}, P)=e(H_{Ui}, P_{Ui})$ holds. If it is invalid, $S_j$ terminates the session, otherwise $S_j$ authenticates $U_i$ and proceed to the next step.

Step 4.:

$S_j$ selects a number $r_{Sj}\in _{R}Z_{q}^{*}$ and a current timestamp $T_{Sj}$, then computes $R_{Sj}=r_{Sj}P$, $H_{Sj}=H_{1}(ID_{Ui}, ID_{Sj}, Y_{Sj}, R_{Sj}, T_{Sj}, \text{ validity } \text{ period })$ and $V_{Sj}=d_{Sj}H_{Sj}$. $S_j$ sends the message $\langle ID_{Sj}$, $Y_{Sj}$, $R_{Sj}$, $T_{Sj}$, $V_{Sj} \rangle$ to $U_i$ over an open network. Now $S_j$ computes $K_{ji}=(r_{Sj}+d_{Sj})(R_{Ui}+P_{Ui})$ and the session key as $SK_{ji}=H_{2}(ID_{Ui}$, $ID_{Sj}$, $R_{Ui}$, $R_{Sj}$, $T_{Ui}$, $T_{Sj}$, $K_{ji})$

Step 5.:

On receiving the message $\langle ID_{Sj}$, $Y_{Sj}$, $R_{Sj}$, $T_{Sj}$, $V_{Sj}\rangle$ at time $T_{Sj}^{\prime }$, $U_i$ checks whether $T_{Sj}^{\prime }-T_{Sj}\le \Delta T_{Sj}$ hold. If it is invalid, $U_i$ quits the session. Otherwise, $U_i$ goes to the next step.

Step 6.:

$U_i$ computes $H_{Sj}=H_{1}(ID_{Ui}, ID_{Sj}, Y_{Sj}, R_{Sj}, T_{Sj}, \text{ validity } \text{ period })$, $P_{Sj}=Y_{Sj}+H_{0}(ID_{Sj}, Y_{Sj})$, and checks whether the equation $e(V_{Sj}, P)=e(H_{Sj}, P_{Sj})$ holds. If this is invalid, $U_{i}$ terminates the session, otherwise authenticates the server $S_{j}$ and computes the session key as $SK_{ij}=H_{2}(ID_{Ui}$, $ID_{Sj}$, $R_{Ui}$, $R_{Sj}$, $T_{Ui}$, $T_{Sj}$, $K_{ij})$, where $K_{ij}=(r_{Ui}+d_{Ui})(R_{Sj}+P_{Sj})$.

5 Analysis of the Proposed ESL Attack-Free ID-MAKA Scheme

5.1 Correctness

The message $\langle ID_{Ui}$, $Y_{Ui}$, $R_{Ui}$, $T_{Ui}$, $V_{Ui}$, $\text{ validity } \text{ period }\rangle$ received by $S_j$ is correct and the client $U_i$ correctly authenticates the server $S_j$ provided $e(V_{Ui}, P)=e(H_{Ui}, P_{Ui})$ holds. Since we have

$$\begin{aligned} e(V_{Ui}, P)&= e(d_{Ui}H_{Ui}, P) \\&= e(H_{Ui}, d_{Ui}P) \\&= e(H_{Ui}, P_{Ui}) \end{aligned}$$

Accordingly the correctness of the message $\langle ID_{Sj}$, $Y_{Sj}$, $R_{Sj}$, $T_{Sj}$, $V_{Sj}\rangle$ and the authentication of the server $S_j$ are also correctly checky by the client $U_i$ through

$$\begin{aligned} e(V_{Sj}, P)&= e(d_{Sj}H_{Sj}, P) \\&= e(H_{Sj}, d_{Sj}P) \\&= e(H_{Sj}, P_{Sj}) \end{aligned}$$

Now, we claimed that both the client $U_i$ and the authentication server $S_j$ hold the same session key. Because we have

$$\begin{aligned} K_{ij}&= (r_{Ui}+d_{Ui})(R_{Sj}+P_{Sj}) \\&= (r_{Ui}+d_{Ui})(r_{Sj}P+d_{Sj}P) \\&= (r_{Ui}+d_{Ui})(r_{Sj}+d_{Sj})P \\&= (r_{Sj}+d_{Sj})(r_{Ui}+d_{Ui})P \\&= (r_{Sj}+d_{Sj})(R_{Ui}+P_{Ui}) \\&= K_{ji} \end{aligned}$$

Thus, $SK_{ij}=SK_{ji}$ hold.

5.2 Security Analysis

Theorem 1

In the random oracle model, our ESL attack-free ID-MAKA scheme is mutual authentication (MA)-secure i.e., it achieves server-to-client (S2C) authentication and client-to-server (C2S) authentication under the Computational Diffie–Hellman (CDH) assumption.

Proof

Assume that the adversary $\mathcal {A}$ violates S2C authentication of the proposed ESL attack-free ID-MAKA scheme, then we can develop a probabilistic polynomial time algorithm $\mathcal {C}$ that will solves an instance of CDH problem by interacting with $\mathcal {A}$. That is $\mathcal {C}$ will return $syP$ from a given instance $\langle P, sP, yP\rangle$. To responds quickly and to avoid the data inconsistency, $\mathcal {C}$ maintains the following initial-empty lists:

• Extract list $L_{Ex}^{list}$: This an initial empty list and it contains the tuples of the form $\langle ID_{i}, Y_{i}, d_{i}\rangle$.

• $H_{0}$ list $L_{H0}^{list}$: This is an initial-empty list, and it contains the tuples of the form $\langle ID_{i}$, $Y_{i}$, $l_{i}\rangle$.

• $H_{1}$ list $L_{H1}^{list}$: This is an initial-empty list and it contains the tuples of the form $\langle ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period }$, $y_{i}P\rangle$.

• $H_{2}$ list $L_{H2}^{list}$: This is an initial-empty list and it contains the tuples of the form $\langle ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij}, SK_{ij}\rangle$.

Case 1: Now we will present a challenge-response game, which is described below, played interactively by $\mathcal {C}$ and $\mathcal {A}$ to breach S2C authentication of the proposed ESL attack-free ID-MAKA scheme. In this game, we assume that $q_{U}$ number of clients may be involved with $q_{S}$ number of servers and the hash function $H_i$ $(i=0, 1, 2)$ closely behaves like true random oracle.

• Setup: In order to solve an instance of CDH problem, $\mathcal {C}$ picks at random $I\in \{1, 2, \ldots , q_{U}\}$, $J\in \{1, 2, \ldots , q_{S}\}$, sets $P_{pub}=sP$ and returns the system’s parameter $\Omega =\langle F_{q}, E/F_{q}, e, G_{q}, P, P_{pub}=sP, H_{0}, H_{1}, H_{2}\rangle$ to the adversary $\mathcal {A}$. Now, $\mathcal {C}$ responds with $\mathcal {A}$’s as given below:

• Hash queries to $H_{0}$: When $\mathcal {A}$ submits a $H_{0}$ query with $\langle ID_{i}$, $Y_{i}\rangle$, $\mathcal {C}$ then searches $L_{H0}^{list}$ and responds with the previous value $l_{i}$ if there is a tuple $\langle ID_{i}, Y_{i}, l_{i}\rangle$, otherwise, choose a number $l_{i}\in _{R}Z_{q}^{*}$ such that there is no tuple of the form $\langle \cdot , \cdot , l_{i}\rangle$ in $L_{H0}^{list}$, outputs $l_{i}$ as the answer and inserts the tuple $\langle ID_{i}, Y_{i}, l_{i}\rangle$ to $L_{H0}^{list}$.

• Hash queries to $H_{1}$: When $\mathcal {A}$ asked this query with $\langle ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period }\rangle$, $\mathcal {C}$ then responds with $y_{i}P$ if a tuple of the form $\langle ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period }$, $y_{i}P\rangle$ is found in $L_{H1}^{list}$. Otherwise, $\mathcal {C}$ selects a number $y_i\in _{R}Z_{q}^{*}$ and returns $y_{i}P$ to $\mathcal {A}$ such that there is no tuple $\langle \cdot , \cdot , \cdot , \cdot , \cdot , \cdot , y_{i}P\rangle$ in $L_{H1}^{list}$. Now, $\mathcal {C}$ includes the tuple $\langle ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period }$, $y_{i}P\rangle$ to $L_{H0}^{list}$.

• Hash queries to $H_{2}$: When $\mathcal {A}$ asked this query with $\langle ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij}\rangle$, $\mathcal {C}$ then responds with $SK_{ij}$ if a tuple $\langle ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij}$, $SK_{ij}\rangle$ is found in $L_{H2}^{list}$. Otherwise, $\mathcal {C}$ selects a number $SK_{ij}\in _{R}Z_{q}^{*}$ and returns it to $\mathcal {A}$ such that there is no tuple $\langle \cdot , \cdot , \cdot , \cdot , \cdot , \cdot , \cdot , SK_{ij}\rangle$ in $L_{H2}^{list}$. Now, $\mathcal {C}$ includes the tuple $\langle ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij}$, $SK_{ij}\rangle$ to $L_{H2}^{list}$.

• Extract($ID_{i}$) queries: When $\mathcal {C}$ received a Extract($ID_{i}$) query, $\mathcal {C}$ returns $d_i$ if a tuple $\langle ID_{i}, Y_{i}, d_{i}\rangle$ is found in the list $L_{Ex}^{list}$. Otherwise, $\mathcal {C}$ does as follows:

  • If $ID_{i}\in \{ID_{U_I}, ID_{S_J}\}$, $\mathcal {C}$ stops the protocol execution.

  • Else, $\mathcal {C}$ selects two numbers $l_{i}, a_{i}\in _{R}Z_{q}^{*}$, sets $d_{i}\leftarrow a_{i}$, $H_{0}(ID_{i}, Y_{i})\leftarrow l_{i}$ and $Y_{i}\leftarrow a_{i}P-l_{i}P_{pub}$. Note that $d_{i}=a_{i}$ satisfies the equation $Y_{i}+H_{0}(ID_{i}, Y_{i})P_{pub}=d_{i}P$. $\mathcal {C}$ returns $d_i$ to $\mathcal {A}$ and adds the tuples $\langle ID_{i}, Y_{i}, d_{i}\rangle$ and $\langle ID_{i}$, $Y_{i}$, $l_{i}\rangle$ to $L_{Ex}^{list}$ and $L_{H0}^{list}$, respectively.

• Corrupt($ID_{i}$) queries: When $\mathcal {C}$ received a Corrupt($ID_{i}$) query from $\mathcal {A}$, $\mathcal {C}$ does as follows:

  • $\mathcal {C}$ stops the simulation If $ID_{i}\in \{ID_{U_I}, ID_{S_J}\}$.

  • Else, $\mathcal {C}$ searches the lists $L^{list}_{Ex}$ and returns the private key $d_{i}$ if there is a tuple $\langle ID_{i}, Y_{i}, d_{i}\rangle$. Otherwise, $\mathcal {C}$ executes $H_0(ID_{i})$ and Extract($ID_{i}$) queries for the tuples $\langle ID_{i}, Y_{i}, l_{i}\rangle$ and $\langle ID_{i}$, $Y_{i}$, $d_{i}\rangle$, then outputs $d_{i}$ as the private key. $\mathcal {C}$ adds the tuples $\langle ID_{i}, Y_{i}, d_{i}\rangle$ and $\langle ID_{i}$, $Y_{i}$, $l_{i}\rangle$ to $L_{Ex}^{list}$ and $L_{H0}^{list}$, respectively.

• Send queries: This query can be executed interactively between $\mathcal {A}$ and $\mathcal {C}$ in the following ways:

  • When $\mathcal {A}$ makes a Send($\Pi ^{t}_{i}, ``Start''$), $\mathcal {C}$ responds as follows. If $ID_{i}\notin \{ID_{U_I}, ID_{S_J}\}$, $\mathcal {C}$ chooses a number $r_{i}\in _{R}Z_{q}^{*}$, a fresh timestamp $T_{i}$ and computes $R_{i}\leftarrow r_{i}P$, $H_{i}\leftarrow H_{1}(ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period })$, $V_{i}\leftarrow d_{i}H_{i}$. $\mathcal {C}$ then returns $M_{1}=\langle ID_{i}$, $Y_{i}$, $R_{i}$, $T_{i}$, $V_{i}$, $\text{ validity } \text{ period }, r_{i}\rangle$. If $ID_{i}\in \{ID_{U_I}, ID_{S_J}\}$, $\mathcal {C}$ generates random numbers $r_i, k_{i}, y_{i}$, a timestamp $T_{i}$, then sets $R_{i}\leftarrow r_{i}P$, $H_{i}\leftarrow H_{1}(ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period })\leftarrow y_{i}P$ and $V_{i}\leftarrow k_{i}H_{i}$ (Since $\mathcal {C}$ cannot compute correct $V_{i}$ without $ID_{i}$’s private key) and responds with $M_{1}=\langle ID_{i}$, $Y_{i}$, $R_{i}$, $T_{i}$, $V_{i}$, $\text{ validity } \text{ period }, r_{i}\rangle$.

  • When $\mathcal {A}$ makes a Send($\Pi ^{s}_{j}, M_{1}$) query (here $\Pi ^{s}_{j}$ is a partner oracle of $\Pi ^{t}_{i}$), $\mathcal {C}$ responds as follows. If $ID_{i}\notin \{ID_{U_I}, ID_{S_J}\}$, $\mathcal {C}$ checks the freshness of $T_{i}$ and the validity of the message $M_{1}$ according to the proposed scheme. If the result is positive, $\mathcal {C}$ chooses a random number $r_{j}\in _{R}Z_{q}^{*}$, a current timestamp $T_{j}$ then computes $R_{j}\leftarrow r_{j}P$, $H_{j}\leftarrow H_{1}(ID_{i}, ID_{j}, Y_{j}, R_{j}, T_{j}, \text{ validity } \text{ period })$ and $V_{j}\leftarrow d_{j}H_{j}$, and responds with the message $M_{2}=\langle ID_{j}$, $Y_{j}$, $R_{j}$, $T_{j}$, $V_{j}, r_{j}\rangle$. Then, $\mathcal {C}$ computes $K_{ji}=(r_{j}+d_{j})(R_{i}+P_{i})$ and the session key as $SK_{ji}=H_{2}(ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ji})$.

  • When $\mathcal {A}$ makes a Send($\Pi ^{t}_{i}, M_{2}$) query, $\mathcal {C}$ responds as follows. If $ID_{i}\notin \{ID_{U_I}, ID_{S_J}\}$, $\mathcal {C}$ checks the freshness of $T_{j}$ and the validity of the message $M_{2}$ according to the proposed scheme. If the result is positive, $\mathcal {C}$ computes $K_{ij}=(r_{i}+d_{i})(R_{j}+P_{j})$ and the session key as $SK_{ij}=H_{2}(ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij})$.

  Finally, $\mathcal {A}$ stops the protocol simulation and outputs a valid message $\langle ID_{U_{I}}$, $Y_{U_{I}}$, $R_{U_{I}}$, $T_{U_{I}}$, $V_{U_{I}}$, $\text{ validity } \text{ period }, r_{I}\rangle$ with a hash value $H_{U_I}$ of the client $U_I$ to login to the remote server $S_J$. The tuple $\langle Y_{U_{I}}$, $R_{U_{I}}$, $V_{U_{I}}$, $r_{I}\rangle$ can be considered as the signature of $\langle ID_{U_{I}}$, $Y_{U_{I}}$, $R_{U_{I}}$, $T_{U_{I}}$, $\text{ validity } \text{ period }, r_{I}\rangle$. According to the forking lemma [44], if $\mathcal {A}$ repeats the above queries by keeping the same random tape, then $\mathcal {C}$ looks into the lists $L_{Hi}^{list}$($i=0, 1, 2,$) and outputs another valid signature $\langle Y_{U_{I}}, R_{U_{I}}, V_{U_{I}}^{*}, r_{I}\rangle$ with different hash value $H_{U_I}^{*}$ such that $H_{U_I}\ne H_{U_I}^{*}$ on the same message $\langle ID_{U_{I}}$, $Y_{U_{I}}$, $R_{U_{I}}$, $T_{U_{I}}$, $\text{ validity } \text{ period }\rangle$. Therefore we can write

  $$\begin{aligned} e(V_{U_I}^{*}, P)&= e(H_{U_I}^{*}, P_{U_I})\end{aligned}$$

  (1)
  $$\begin{aligned} e(V_{U_I}, P)&= e(H_{U_I}, P_{U_I}) \end{aligned}$$

  (2)

  From the Eqs. (1) and (2), we can derived

  $$\begin{aligned} e(V_{U_I}^{*}-V_{U_I}, P)&= e(H_{U_I}^{*}-H_{U_I}, P_{U_I}) \end{aligned}$$

  (3)

  Let $H_{U_I}^{*}=y_{1}P$, $H_{U_I}=y_{2}P$, $y=(y_{1}-y_{2})$, $P_{U_I}=Y_{U_I}+l_{U_I}P_{pub}$ and $P_{pub}=sP$. Therefore from the Eq. (3), we have

  $$\begin{aligned} e(V_{U_I}^{*}-V_{U_I}, P)&= e(y_{1}P-y_{2}P, Y_{U_I}+l_{U_I}sP) \nonumber \\&= e(yP, Y_{U_I}+l_{U_I}sP) \nonumber \\&= e(yP, Y_{U_I})e(yP, l_{U_I}sP) \nonumber \\&= e(P, yY_{U_I})e(l_{U_I}syP, P) \end{aligned}$$

  (4)

  From the Eq. (4), we have

  $$\begin{aligned} e(l_{U_I}syP, P)&= e(V_{U_I}^{*}-V_{U_I}, P)e(P, yY_{U_I})^{-1} \nonumber \\&= e(V_{U_I}^{*}-V_{U_I}, P)e(yY_{U_I}, P) \nonumber \\&= e(V_{U_I}^{*}-V_{U_I}+yY_{U_I}, P) \end{aligned}$$

  (5)

The events $ID_{i}=ID_{U_I}$ and $ID_{j}=ID_{S_J}$ occur with the probability $\frac{1}{q_{U}}$ and $\frac{1}{q_{S}}$. Therefore, $\mathcal {C}$ solves an instance of CDH problem as $syP=\frac{1}{l_{U_I}}[V_{U_I}^{*}-V_{U_I}+yY_{U_I}]$ with probability $\frac{\epsilon }{q_{U}q_{S}}$, which is negligible.

Case 2: Our protocol is symmetric, that is, the server $S_j$ computes and responds similar to the client $U_i$. Thus, the S2C authentication can be proved in the same way as done in Case 1.$\square$

Theorem 2

The proposed ESL attack-free ID-MAKA scheme is AKA secure in the random oracle model under the Computational Diffie–Hellman assumption.

Proof

Assume an adversary $\mathcal {A}$ correctly output the guess bit $b$ which is chosen in the Test query, then there must a polynomial time bounded algorithm $\mathcal {C}$ that can solve the the Computational Diffie–Hellman problem.

Similar to the previous theorem, $\mathcal {C}$ maintains the initial-empty lists $L_{Ex}^{list}$ and $L_{Hi}^{list}$ ($i=0, 1,2$) to responds quickly and to avoid the data inconsistency. Let $q_U$, $q_S$, $q_{Se}$, and $q_{hi}$($i=0, 1,2$) be the total number of client, number of server, number of session and number hash queries. Suppose $\mathcal {A}$ is challenged with a CDH problem instance ($P$, $P_1=aP$, $P_2=bP$) and is tasked to compute $abP$. $\mathcal {A}$ picks $P_0\in G_{q}$, $l_{1}, l_{2}\in \{1, 2, \ldots , q_{Se}\}$, $I\in \{1, 2, \ldots , q_{U}\}$, $J\in \{1, 2, \ldots , q_{S}\}$ at random, and gives the system’s parameter $\Omega =\langle F_ {q}, E/F_{q}, e, G_{q}, P, P_{pub}=P_{0}, H_{0}, H_{1}, H_{2}\rangle$ to the adversary $\mathcal {A}$ and then responds to $\mathcal {A}$’s queries in the following ways:

• Hash queries to $H_{0}$: When $\mathcal {A}$ submits a $H_{0}$ query with $\langle ID_{i}$, $Y_{i}\rangle$, $\mathcal {C}$ then searches $L_{H0}^{list}$ and responds with the previous value $l_{i}$ if there is a tuple $\langle ID_{i}, Y_{i}, l_{i}\rangle$, otherwise, choose a number $l_{i}\in _{R}Z_{q}^{*}$ such that there is no tuple of the form $\langle \cdot , \cdot , l_{i}\rangle$ in $L_{H0}^{list}$, outputs $l_{i}$ as the answer and inserts the tuple $\langle ID_{i}, Y_{i}, l_{i}\rangle$ to $L_{H0}^{list}$.

• Hash queries to $H_{1}$: When $\mathcal {A}$ asked this query with $\langle ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period }\rangle$, $\mathcal {C}$ then responds with $y_{i}P$ if a tuple of the form $\langle ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period }$, $y_{i}P\rangle$ is found in $L_{H1}^{list}$. Otherwise, $\mathcal {C}$ selects a number $y_i\in _{R}Z_{q}^{*}$ and returns $y_{i}P$ to $\mathcal {A}$ such that there is no tuple $\langle \cdot , \cdot , \cdot , \cdot , \cdot , \cdot , y_{i}P\rangle$ in $L_{H1}^{list}$. Now, $\mathcal {C}$ includes the tuple $\langle ID_{i}$, $ID_{j}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period }$, $y_{i}P\rangle$ to $L_{H0}^{list}$.

• Hash queries to $H_{2}$: When $\mathcal {A}$ asked this query with $\langle ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij}\rangle$, $\mathcal {C}$ then responds with $SK_{ij}$ if a tuple $\langle ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij}$, $SK_{ij}\rangle$ is found in $L_{H2}^{list}$. Otherwise, $\mathcal {C}$ selects a number $SK_{ij}\in _{R}Z_{q}^{*}$ and returns it to $\mathcal {A}$ such that there is no tuple $\langle \cdot , \cdot , \cdot , \cdot , \cdot , \cdot , \cdot , SK_{ij}\rangle$ in $L_{H2}^{list}$. Now, $\mathcal {C}$ includes the tuple $\langle ID_{i}$, $ID_{j}$, $R_{i}$, $R_{j}$, $T_{i}$, $T_{j}$, $K_{ij}$, $SK_{ij}\rangle$ to $L_{H2}^{list}$.

• Extract($ID_{i}$) queries: When $\mathcal {C}$ received a Extract($ID_{i}$) query, $\mathcal {C}$ returns $d_{i}$ to $\mathcal {A}$ if a tuple $\langle ID_{i}, Y_{i}, d_{i}\rangle$ is found in $L_{Ex}^{list}$. Otherwise, $\mathcal {C}$ does as follows:

  • If $ID_i=ID_{U_I}$, $\mathcal {C}$ chooses $l_{i}\in _{R}Z_{q}^{*}$, sets $Y_{i}\leftarrow aP-l_{i}P_{0}$, $d_i\leftarrow \perp$ and then returns $d_i$ to $\mathcal {A}$.

  • If $ID_i=ID_{S_J}$, $\mathcal {C}$ chooses $l_{i}\in _{R}Z_{q}^{*}$, computes $Y_{i}\leftarrow bP-l_{i}P_{0}$, $d_i\leftarrow \perp$ and then returns $d_i$ to $\mathcal {A}$.

  • Else, $\mathcal {C}$ chooses $d_i, l_{i}\in _{R}Z_{q}^{*}$, computes $Y_{i}\leftarrow d_{i}P-l_{i}P_{0}$, and then returns $\langle ID_{i}, Y_{i}, d_i\rangle$ to $\mathcal {A}$.

  Finally, $\mathcal {C}$ inserts $\langle ID_i, Y_i, l_i\rangle$ and $\langle ID_i, Y_i, d_i\rangle$ into the lists $L_{H0}^{list}$ and $L_{Ex}^{list}$.

• Send($\Pi ^{s}_{i}, M$) queries: When $\mathcal {A}$ asks a Send query, $\mathcal {C}$ responds in the following ways:

  • If $\Pi ^{s}_{i}=\Pi ^{l_{1}}_{U_{I}}$ and $M=\lambda$, $\mathcal {C}$ chooses $r_i, y_{i}\in _{R}Z_{q}^{*}$ and then sets $R_i\leftarrow r_{i}P+P_1$, $H_{i}\leftarrow H_{1}(ID_{U_{i}}$, $ID_{S_{j}}$, $Y_{i}$, $R_{i}$, $T_{i}$, $\text{ validity } \text{ period })\leftarrow y_{i}P$, $V_i\leftarrow y_{i}P_{1}$. $\mathcal {C}$ then outputs $M_{1}=\langle ID_{U_{i}}$, $Y_{i}$, $R_{i}$, $T_{i}$, $V_{i}$, $\text{ validity } \text{ period }, r_{i}\rangle$, where $T_{i}$ represents the current timestamp.

  • Else, if $\Pi ^{s}_{i}=\Pi ^{l_{2}}_{S_{J}}$ and $M=M_1$, $\mathcal {A}$ verifies whether the equation $e(V_i, P)=e(H_{i}, P_{i})$ holds. $\mathcal {C}$ aborts the simulation if the $e(V_i, P)\ne (H_{i}, P_{i})$, otherwise selects $r_{j}, y_{j}\in _{R}Z_{q}^{*}$ and then sets $R_j\leftarrow r_{j}P+P_2$, $H_{j}\leftarrow H_{1}(ID_{U_{i}}$, $ID_{S_{j}}$, $Y_{j}$, $R_{j}$, $T_{j})\leftarrow y_{j}P$, $V_j\leftarrow y_{j}P_{2}$. $\mathcal {C}$ then outputs $M_{2}=\langle ID_{S_{j}}$, $Y_{j}$, $R_{j}$, $T_{j}$, $V_{j}$, $r_{j}\rangle$, where $T_{j}$ represents the current timestamp.

  • Else, If $\Pi ^{s}_{i}=\Pi ^{l_{1}}_{U_{I}}$ and $M=M_2$, $\mathcal {A}$ verifies whether the equation $e(V_i, P)=e(H_{i}, P_{i})$ holds. $\mathcal {C}$ aborts the simulation if the $e(V_i, P)\ne (H_{i}, P_{i})$, otherwise $\mathcal {C}$ accepts the session.

  • Else, $\mathcal {C}$ answers $\mathcal {A}$’s queries according to the proposed protocol.

• Corrupt($ID_{i}$) queries: When $\mathcal {C}$ received a Corrupt($ID_{i}$) query, $\mathcal {C}$ does as follows:

  • $\mathcal {C}$ stops the simulation if $ID_{i}\in \{ID_{U_I}, ID_{S_J}\}$.

  • Else, $\mathcal {C}$ returns the private key $d_{i}$ if there is a tuple $\langle ID_{i}, Y_{i}, d_{i}\rangle$ in the list $L^{list}_{Ex}$. Otherwise $\mathcal {C}$ executes $H_0(ID_{i})$ and Extract($ID_{i}$) queries for the tuples $\langle ID_{i}, Y_{i}, l_{i}\rangle$ and $\langle ID_{i}$, $Y_{i}$, $d_{i}\rangle$, then outputs $d_{i}$ as the private key. $\mathcal {C}$ adds the tuples $\langle ID_{i}, Y_{i}, d_{i}\rangle$ and $\langle ID_{i}$, $Y_{i}$, $l_{i}\rangle$ to $L_{Ex}^{list}$ and $L_{H0}^{list}$, respectively.

• Reveal($\Pi ^{s}_{i}$) queries: If $\Pi ^{s}_{i}=\Pi ^{l_{1}}_{U_{I}}$ or $\Pi ^{s}_{i}=\Pi ^{l_{2}}_{S_{J}}$, $\mathcal {C}$ aborts the execution. If $\Pi ^{s}_{i}$ is not accepted, $\mathcal {C}$ returns a null value, otherwise searches the list $L_{H2}^{list}$ and returns the session key.

• Test($\Pi ^{s}_{i}$) queries: At some point, $\mathcal {C}$ will ask a Test query on some oracle. If $\mathcal {C}$ does not choose one of the oracles $\Pi ^{l_{1}}_{U_{I}}$ to ask the Test query, then $\mathcal {C}$ aborts. Otherwise, $\mathcal {C}$ chooses a bit $b\in \{0, 1\}$ and returns the correct session key if $b=1$, otherwise outputs a random string $SK_{ij}\in _{R}Z_{q}^{*}$ as the session key.

In this game, $\mathcal {A}$’s simulation is perfectly indistinguishable from the proposed protocol except that the forgeries of the signatures $\langle Y_{U_{I}}$, $R_{U_{I}}$, $V_{U_{I}}$, $r_{I}\rangle$ and $\langle Y_{S_{J}}$, $R_{S_{J}}$, $V_{S_{J}}$, $r_{J}\rangle$ are not possible in the Send queries. As we have shown in the previous theorem that the success probabilities of the forgeries of these signatures are negligible. The adversary $\mathcal {A}$ does not aborted this game as he chooses $\Pi ^{l_{1}}_{U_{I}}$ as the Test oracle and the oracles Reveal($\Pi ^{l_{1}}_{U_{I}}$) or Reveal($\Pi ^{l_{2}}_{S_{J}}$) have not been asked. The probability that $\mathcal {A}$ chooses Test $\Pi ^{l_{1}}_{U_{I}}$ as Test oracle is $\frac{1}{q_{Se}}$. If $\mathcal {A}$ can win this game, then he must have made the corresponding $H_2$ hash query of the form $\langle ID_{U_I}$, $ID_{S_J}$, $R_{U_I}$, $R_{S_J}$, $T_{U_I}$, $T_{S_J}$, $K_{IJ}\rangle$ if $\Pi ^{l_{1}}_{U_{I}}$ is the initiator oracle. Thus, $\mathcal {A}$ can find the corresponding item in the list $L^{list}_{H2}$ and outputs $abP=K_{IJ}-r_{I}r_{J}P-r_{I}P_2-r_{J}P_1$ as the solution to the CDH problem.

Thus, the advantage of $\mathcal {C}$ solving the CDH problem is such that

$$\begin{aligned} Adv^{CDH}_{\mathcal {C}}(k)&\ge \frac{1}{q_{Se}}\times \frac{1}{q_{U}}\times \frac{1}{q_{S}}\times \frac{1}{q_{H2}}\times Adv^{ID-MAKA}_{\mathcal {A}}(k) \end{aligned}$$

Here $Adv^{CDH}_{\mathcal {C}}(k)$ denotes the success probability of breaching the CDH problem by the challenge $\mathcal {C}$.$\square$

6 Performance Comparison of the Proposed Scheme with Others

Similar to the schemes [23, 24], the proposed scheme is also designed for both the general and dynamic clients. Thus, we evaluate the security and computation cost efficiency of the proposed scheme with them. The multi-server authentication schemes proposed in the literature are vulnerable to ESL attack since they computed their session key using only ephemeral secrets chosen by client and server. Thus, the leakage of these ephemeral secrets leads to the compromise of the session key. Compared to others, the schemes [23, 24] are most efficient in terms of computation and security, however we argued that they are also vulnerable to ESL attack. In these schemes, if ephemeral secrets are leaked to an outsider then he/she can compute the session key easily. Now, we illustrates the ESL attack on these scheme as follows:

• In [23], client $U_i$ and server $S_j$ compute the following:

  • $U_i$ chooses a number $a_{i}\in _{R}Z_{q}^{*}$ and computes $q_j=H(ID_{Sj})$, $t_i=g^{a_i}$, $h_i=H_{1}(t_i)$, $v_i=H_{1}(h_i)$, $Q_j=P_{pub}+q_{j}P$, $X_i=a_{i}Q_{j}$ and $Y_i=(a_i+h_i)DID_{U_i}$. Then $U_i$ sends $\langle ID_{U_i}, X_{i}, Y_i, v_i, \text{ validity } \text{ period }\rangle$ $S_j$.

  • $S_j$ selects a number $b_j\in _{R}Z_{q}^{*}$ and computes $X_j=b_{j}Q_{j}$, $t_i=e(X_i, DID_{S_j})$ and $z_j=H_{1}(t_i\parallel X_i\parallel X_j\parallel Y_i )$. Now $S_j$ sends $\langle z_j, X_j\rangle$ to $U_j$.

  • $U_i$ and $S_j$ compute the session key as $SK_{ij}=SK_{ji}=H_{1}(t_i\parallel K\parallel X_{i} \parallel Y_{j}\parallel z_{j})$, where $K=a_{i}X_{j}=b_{j}X_{i}=a_{i}b_{j}Q_{j}$.

  Therefore, if $a_i$ and $b_j$ are leaked, then the outsider easily figure out the session key $SK_{ij}$. Furthermore, $U_i$’s secret key can be computed as $DID_{U_i}=(a_i+h_i)^{-1}Y_{i}$.

• In [24], client $U_i$ and server $S_j$ compute the following:

  • $U_i$ chooses a number $a_{U_i}\in _{R}Z_{q}^{*}$, computes $X_{U_i}=a_{U_i}P$, $b_{U_i}=H_{3}(ID_{U_i}\parallel ID_{S_j}\parallel R_{U_i}\parallel X_{U_i}\parallel T_{U_i}\parallel \text{ valid } \text{ period })$ and $s_{U_i}=(a_{U_i}+b_{U_i})^{-1}x_{U_i}$, where $T_{U_i}$ is the current timestamp. Then $U_i$ send $\langle ID_{U_i}$, $R_{U_i}$, $X_{U_i}$, $s_{U_i}$, $T_{U_i}$, $\text{ valid } \text{ period }\rangle$ to $S_j$.

  • $S_j$ chooses a number $b_{S_j}\in _{R}Z_{q}^{*}$, computes $X_{S_j}=a_{S_j}P$, $b_{S_j}=H_{4}(ID_{U_i}\parallel ID_{S_j}\parallel R_{U_i}\parallel X_{U_i}\parallel \text{ valid } \text{ period }\parallel R_{S_j}\parallel X_{S_j}\parallel T_{S_j})$ and $s_{S_j}=(a_{S_j}+b_{S_j})^{-1}x_{S_j}$, where $T_{S_j}$ is the current timestamp. Then $S_j$ send $\langle ID_{S_j}$, $R_{S_j}$, $X_{S_j}$, $s_{S_j}$, $T_{S_j}\rangle$ to $U_i$.

  • Now $U_i$ and $S_{j}$ compute the session key as $SK_{ij}=SK_{ji}=H_{5}(ID_{U_i}\parallel ID_{S_j}\parallel X_{U_i}\parallel X_{S_j}\parallel K)$ where $K=a_{U_i}X_{S_j}=a_{S_j}X_{U_i}=a_{U_i}a_{S_j}P$.

  It is to be noted that if $a_{U_i}$ and $a_{S_j}$ are compromised, then the session key $SK_{ij}$ will be compromised to the outsider. Furthermore, the secret keys of $U_i$ and $S_j$ can be computed as $x_{U_i}=s_{U_i}(a_{U_i}+b_{U_i})$ and $x_{S_j}=s_{S_j}(a_{S_j}+b_{S_j})$.

For the performance comparison with respect to computation cost, we define following notations [37]:

• $t_{m}$: Time required for modular multiplication.

• $t_{e}$: Time required for modular exponentiation operation, $t_{e}\approx 240t_{m}$.

• $t_{s}$: Time required for elliptic curve scalar point multiplication operation, $t_{s}\approx 29t_{m}$.

• $t_{p}$: Time required for bilinear pairing operation, $t_{p}\approx 87t_{m}$.

• $t_{i}$: Time required for modular inversion operation, $t_{i}\approx 11.6t_{m}$.

It is to be noted that the mutual authentication with session key agreement phase is the dominating process in terms of computation cost than setup and extract phases as they are executed only once. Thus, we consider only the mutual authentication with session key agreement phase and accordingly compare the proposed scheme with [23, 24]. We demonstrated the comparative result in Table 1. The proposed scheme bears lower computation cost than [23] and slightly increases the same over [24]. However, only the proposed scheme provides resilience against ESL attack whereas others do not.

Table 1 Computation cost comparison of the proposed scheme with others

7 Conclusion

In this paper, we proposed an ID-MAKA scheme for mobile multi-server environment. The proposed scheme is suitable for both the general and dynamic mobile clients. The earlier schemes do not resist the ESL attack whereas our scheme fulfills this objective. The security analysis of the proposed scheme is done in the random oracle model and proven to be provably secure under the Computational Diffie–Hellman assumption.