# Chebyshev Polynomial-Based Authentication Scheme in Multiserver Environment

Authors: Toan-Thinh Truong; Minh-Triet Tran; Anh-Duc Duong
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Nowadays, communication technologies are more and more strongly advanced, such as 4G or 5G. There are many useful online applications, and one of them is the telecare medical information system (TMIS). If the TMIS is widely deployed, patients and doctors will have more frequently connection. Clearly, this enhances our quality of life. One of the most important modules securely constructing this convenient TMIS is the user-authentication scheme. We should prevent user identity and related information from the adversary’s eavesdropping. Therefore, the authentication scheme could provide user anonymity and concern some kinds of attacks, such as impersonation or password-guessing attacks. Common solutions are a combination of hash function and public-key cryptosystem (RSA or elliptic curve cryptosystem, ECC), but current schemes do not consider identity protection as one main task necessary for medical information environment. In this paper, our results consist of some important analyses of previous works and a multiserver user-authentication scheme suitable for TMIS using Chebyshev polynomial with two models: random oracle and BAN-logic.


---

## Body

## 1. Introduction

With evolutionary changes in technological fields, all aspects of modern life are influenced positively, especially in medical online-service systems. Internet gives us a chance of providing convenience to our customers. Instead of directly coming to the medical centre or hospital, many people like to experience anytime. Nowadays, people use wearable devices, such as smart watch or bracelet, and make connections with the online medical system to quickly receive some doctors’ advises. It can be said that remote services are an inevitable trend to satisfy remote experiences. In such services, we need to protect the users’ profiles from illegitimate accesses. All exchanged messages between the user and server in a working session need keeping secret. In any application, the user and server must know if their partner is real or fake. Therefore, the authentication scheme is necessary to provide security and privacy for both sides.Storing a password list to verify the user’s identity is a popular method, and this is not a secure one (PAP/CHAP). This list may be stolen, and then another adversary can launch a password dictionary attack. Furthermore, the information exchanged between the user and server must be kept secure. We need to propose an efficient scheme to overcome some existing limitations. To achieve this goal, we should design an authentication scheme combined with some cryptographic primitives and hard problems to resist some common kinds of attacks. However, many authors prefer the password-based approach to others because it is simple and easily deployed. Some schemes [1–5] can resist some kinds of attacks at this phase, such as stolen-verifier attack or replay attack. In 2010, Wu et al. [6] proposed a scheme with precomputing phase enhancing the security. The remarkable point of this idea is that a set of prestored random values provides a strong user’s anonymity. Furthermore, authors also use some cryptographic primitives, such as hash function, symmetric encryption scheme, and logarithm problem. Then, Debiao [7] pointed out that Wu’s scheme did not combine the user’s identity with secret information, and this results in impersonation attack. What Debiao claimed is true, but his improved scheme still has this pitfall. Next, Wei [8] discovered that both Debiao and Wu are vulnerable to offline password-guessing attack, and he also proposed improved version to overcome this attack. In 2012, Zhu claimed that Wei’s scheme is still vulnerable to what Wei claimed. Zhu combined the password with a secret key to enhance the difficulty of password verification. Although Zhu’s scheme [9] overcame previous limitations, his scheme transmitted identity information without protection. Therefore, his scheme is not suitable for some privacy environments. Especially, Pu’s plugin scheme [10] can plug any two-party password authentication protocol, 2PAKE with elliptic curve cryptography, to enhance security and save computational cost. However, this scheme also needs to be reconsidered because of unreasonable computation workloads with two session keys. In case of leaking the centre’s master key and the users’ authentication key, the scheme should protect previous exchanged messages between the user and server. That is why session-key perfect forward secrecy (PFS) is one of the standards evaluating a strong scheme. Known-key attack is also a popular one at the authentication phase that receives many attentions. In this kind of attack, leaking another session key may result in attacking another session key. In 2013, Li et al. [11] proposed a scheme in multiserver environment with many improvements, in which each server has its own key. However, leaking smart card’s information may result in password-guessing attack. In 2014, Qu and Tan [12] proposed a different ECC-based scheme. Although they used elliptic curve cryptosystem, leaking the user’s identity may result in impersonation attack. Clearly, this decreases the scheme’s reality because the identity’s nature is public. In 2015, Amin and Biswas [13] proposed a scheme in telecare medicine environment. Their scheme can resist three-factor attack, including password + smart card + biometrics. However, their scheme is still vulnerable to PFS. In 2018, Qiu et al. [14] and Xu et al. [15] proposed a scheme using ECC with untraceability property suitable for the medical services. Also, in 2019, Qiu et al. [16] proposed an ECC-based improved version using automated validation of Internet security protocol and application software. So, it can be said that this scheme has a high reliability.Client-server authentication is simple and time-efficient, but in such medical or financial systems, we need continuous connections between their servers. Furthermore, in single-server environment, the customer needs many credentials for various services. Recently, using Chebyshev polynomial receives attentions from many authors. In 2016, Li et al. [17] proposed a chaotic map-based authentication scheme in multiserver environment with provable security. Their work is truly impressive because it is based on BAN-logic and random oracle models, which are tools suitable for provable authentication schemes. Their design is a three-party participation in authentication process, so its time-consuming is high. In 2017, Jangirala et al. [18] proposed a multiserver environment scheme based on dynamic ID. Although the correctness of their scheme is correctly proved based BAN-logic, it is not applied with any hard problems. Therefore, it is hard to be a strong scheme. In the same year, Han et al. [19] and Irshad et al. [20] proposed a chaotic map-based scheme. Han et al.’s result is a combination between hard problem (chaotic map) and cryptographic primitives, such as hash function and symmetric encryption scheme. However, we see their scheme uses three-way challenge-response handshake technique with timestamp. In our experience, we only need two three-way challenge-response handshake techniques needed if using timestamp. Irshad’s scheme is similar to Li’s because it is designed with three-party architecture. Therefore, it also takes much time to authenticate. In 2018, Alzahrani et al. [21] proposed a secure and efficient TMIS-based scheme. Their scheme provides TMIS environment with chaotic map-based scheme, but they need to extend in multiserver environment. Especially, in the same year, Wang et al. [22] proposed a security model accurately capturing the adversary’s practical capabilities. We hope their model will be favourable and common soon. In this paper, we will analyse typical works [11–13, 18, 20, 21] to have some information needed to propose a new Chebyshev polynomial-based scheme in multiserver environment. Also, we have a work [23] but in the client-server environment.The rest of our paper is organized as follows. InSection 2, we present the background of Chebyshev polynomial. Section 3 reviews some recently typical results and analyses them on security aspect. Then, in Section 4, we propose an improved scheme in multiserver environment using Chebyshev polynomial [24] in the modular prime number field. In Section 5, we analyse our proposed scheme on two aspects, security and efficiency. Finally, the conclusion is presented in Section 6.


## 2. Background

Chebyshev polynomial [24] is a chaotic map in field ℝ, Ta: [−1, 1] ⟶ [−1, 1] (∀a ∈ ℕ): Ta (x) = cos (a × arcos (x)), ∀x ∈ [−1, 1].And it can be rewritten in recursion form as follows:(1)T1x=x,T2x=2x2−1,T3x=4x3−3x,T4x=8x4−8x2+1,⋮Ta+1x=2x×Tax−Ta−1x,∀a∈N.In 2005, Bergamo et al. [25] analysed Chebyshev polynomial in real field and concluded that we can find r′ ≠ r, such that Tr′x = Trx. In 2008, Zhang [24] extended Chebyshev polynomial to ∞ and proved that its property in real field is also right in modular prime number field ℤp, p ∈ ℙ. This result allows to construct public-key cryptography and related hard problems. Chebyshev polynomial in ℤp can be rewritten in recursion form as in ℝ:(2)T0x=1,T1x=x,⋮Tnx=2x×Tn−1x−Tn−2xmodp,∀n≥2.With properties in Chebyshev polynomial, a public-key cryptography is proposed. To construct this one, we need to choose p ∈ ℙ and x ∈ [0, p − 1] and then compute with formula Tn (x) mod p, ∀n ∈ ℕ. Furthermore, there are also two related hard problems in this public-key cryptography [26], such as chaotic map discrete logarithm problem (CMDLP) and chaotic map Diffie–Hellman problem (CMDHP):(i)
Chaotic map discrete logarithm problem (CMDLP): givenp ∈ ℙ and x, y ∈ [0, p − 1], it is hard to find r ∈ ℕ such that Tr (x) = y mod p(ii)
Chaotic map Diffie–Hellman problem (CMDHP): givenp ∈ ℙ, x ∈ [0, p − 1], Ta (x) mod p and Tb (x) mod p, it is hard to find Ta×b (x) mod p, where a, b ∈ ℕ


## 3. Cryptanalysis of Some Typical Schemes

This section presents and analyses on some typical schemes.


### 3.1. Li et al.’s Scheme

This scheme [11] uses hash function combined with random values, including four phases: registration, login, authentication, and password-update phases. Because designed for multiserver environment, the registration centre constructs the master key h (x || y) for itself and the submaster key h (SIDj || h (y)) for each service provider. Table 1 presents some notations used in this scheme.Table 1
Notations used in the scheme [11].
NotationsDescriptionUi, Sj, RCith user, jth server, registration centreIDi, PWiIdentity and password ofUiSIDj, CIDiSj’s identity, Ui’s dynamic identityx, yMaster key and secret value ofRCh (.), ⊕, ||Hash function, XOR, and concatenation⇒/⟶Secure/public channels


#### 3.1.1. Registration Phase

Ui registers with RC as follows:(i)
Ui chooses IDi, PWi, and random value b and computes Ai = h (b ⊕ PWi). Then, Ui sends IDi and Ai to RC through a secure channel.(ii)
On receiving {IDi, Ai} from Ui, RC computes Bi = h (IDi || x), Ci = h (IDi || h (y) || Ai), Di = h (Bi || h (x || y)), and Ei = Bi ⊕ h (x || y).(iii)
RC saves {Ci, Di, Ei, h (.), h (y)} into a smart card and sends to Ui via a secure channel.(iv)
Ui inputs b into the smart card, and finally, Ui has {Ci, Di, Ei, b, h (.), h (y)}.In the registration phase, we see that the author used common keyh (y), and this is dangerous because the adversary can exploit this to launch an impersonation attack if the smart card’s information is leaked or stolen. Figure 1 describes all steps in this phase.Figure 1
User registration phase of Li et al.’s scheme.


#### 3.1.2. Login Phase

When logging into service,Ui performs as follows:(i)
Ui provides his/her smart card and inputs IDi and PWi. Then, the smart card computes Ai = h (b ⊕ PWi) and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. If this holds, Ui continues. Otherwise, the smart card terminates the session.(ii)
The smart card randomly chooses valuesNi and computes Pij = Ei ⊕ (h (h) (SIDj || h (y)) || Ni), CIDi = Ai ⊕ (h (D)i || SIDj || Ni), M1 = h (P)ij || CIDi || Di || Ni), and M2 = h (SIDj ||h (y)) ⊕ Ni.(iii)
Ui sends {Pij, CIDi, M1, M2} to Sj through a public channel.At this phase, the random valueNi can be easily computed because it is only protected by h (y). This decreases the challenge from the user and makes the scheme unbalanced.


#### 3.1.3. Authentication Phase

In this phase, the server also chooses the random valueNj and only the valid user (who has Ai) can recompute this Nj and send a correct response. Figure 2 describes all steps in this phase.Figure 2
User authentication phase of Li et al.’s scheme.WhenSj receives {Pij, CIDi, M1, M2} from Ui, Sj, and Ui, it performs the following steps:(i)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(ii)
Sj computes h (Pij || CIDi || Di || Ni) and compares it with M1. If two values are unequal, Sj rejects the login message and terminates the session. Otherwise, Sj accepts login message. Then, Sj randomly chooses Nj and computes M3 = h (Di || Ai || Nj || SIDj) and M4 = Ai ⊕ Ni ⊕ Nj. Finally, Sj sends {M3, M4} to Ui through a public channel.(iii)
When receiving {M3, M4} from Sj, Ui computes Nj = Ai ⊕ Ni ⊕ M4 and h (Di || Ai || Nj || SIDj) and then compares it with M3. If two values are unequal, Ui rejects the message and terminates the session. Otherwise, Ui successfully authenticates with Sj. Then, Ui computes M5 = h (Di || Ai || Ni || SIDj) and sends {M5} to Sj through a public channel.(iv)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj  || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(v)
When receiving {M5} from Ui, Sj computes h (Di || Ai || Ni || SIDj) and compares it with M5. If two values are equal, Sj successfully authenticates with Ui and authentication phase completes.(vi)
Next,Ui and Sj compute a common session key SK = h (Di || Ai || Ni || Nj || SIDj) used to encrypt later transactions.


#### 3.1.4. Password-Update Phase

This phase is performed whenUi changes PWi into PWinew without interacting with RC:(i)
Ui inputs IDi and PWi and provides his/her smart card at the terminal.(ii)
The smart card computesAi = h (b ⊕ PWi) and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. Is this does not hold, the smart card rejects password-update request. Otherwise, Ui inputs PWinew and random number bnew.(iii)
The smart card computesAinew = h (bnew ⊕ PWinew) and Cinew = h (IDi || h (y) || Ainew).(iv)
Finally, the smart card replacesCi with Cinew and terminates the session.


#### 3.1.5. The Scheme’s Cryptanalysis

IfUi loses his/her smart card, it can result in impersonation attack. Furthermore, another attacker Ua can exploit Sj to guess the password through session key. Therefore, Li’s scheme is also vulnerable to two-factor attack. Below are some steps to launch an impersonation and password-guessing attacks:(i)
Ua computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Ni), where Ei is extracted from the smart card. SIDj, h (y), and Ni are easily computed by Ua because they are public information.(ii)
NextUa computes CIDi = Ai ⊕ h (Di || SIDj || Ni), M1 = h (Pij || CIDi || Di || Ni), and M2 = h (SIDj || h (y)) ⊕ Ni, where Ai = h (b ⊕ PWi) is Ua’s value and Di is extracted from Ui’s smart card.(iii)
Ua sends {Pij, CIDi, M1, M2} to Sj. When receiving, Sj will perform the following steps to verify.(iv)
Sj extracts Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(v)
Sj sees M1 = h (Pij || CIDi || Di || Ni), so Sj randomly chooses Nj and computes M3 = h (Di || Ai || Nj || SIDj) and M4 = Ai ⊕ Ni ⊕ Nj. Sj sends {M3, M4} to Ua.(vi)
When receiving {M3, M4}, Ua computes M5 = h (Di || Ai || Ni || SIDj) and sends to Sj.(vii)
Sj sees M5 = h (Di || Ai || Ni || SIDj) and accepts Ua.(viii
)Finally,Ua and Sj compute a common session key SK = h (Di || Ai || Ni || Nj || SIDj).BecauseEi is extracted from Ui’s smart card, the values Bi and Di also belong to Ui. However, in Li’s scheme, Ai is separated from other values, so Ua can exploit this limitation to insert his/her information. Furthermore, if Ua captures previous transactions between Ui and Sj, he/she will launch Ui’s password-guessing attack. Assuming Ua has Ui’s M5 = h (Di || Ai || Ni || SIDj), so Ua can construct h (Di || h (b ⊕ guess) || Ni || SIDj) = M5 and use the password dictionary to search “guess” until success. Note that Ui’s Ni is easily found by computing Ni = M2 ⊕ h (SIDj || h (y)), in which SIDj and h (y) are those Ua easily computes.


### 3.2. Qu and Tan’s Scheme

Qu and Tan’s scheme [12] uses ECC, and it is secure against some popular kinds of attacks as they claimed. However, we will prove their scheme is vulnerable to impersonation attack. This scheme includes five phases: initialization, registration, login, authentication, and password-update phases. Table 2 presents some notations used in this scheme.Table 2
Notations used in the scheme [12].
NotationsDescriptionS, U, (qS, QS)Server/user, key-pair ofSIDU, PWUIdentity and password ofUH1Hash function {0, 1}∗ ⟶ GpH2Hash functionGp × Gp ⟶ ℤp∗H3|Hash function {0, 1}∗ × Gp × Gp ⟶ {0, 1}krU, rSSecret values ofU and SFp, EP (Fp)Finite field, elliptic curve defined overFpGGroup of points inEP (Fp), G = n ∈ ℙPBase pointP is a generator of G


#### 3.2.1. System Initialization

In this phase, the system initializes some parameters:(i)
S chooses the elliptic curve EP (a, b) and base point P with big prime order n(ii)
S chooses qS ∈ [1, n − 1] and computes the public key QS = qS × P(iii)
S chooses three hash functions, H1 (.), H2 (.), and H3 (.), described in Table 2(iv)
S published {EP (a, b), P, QS, H1 (.), H2 (.), H3 (.)}In this phase, we see thatH1 (.) is special because it receives any string and outputs a point belonging to the elliptic curve.


#### 3.2.2. Registration Phase

When registering,U must follow following steps:(i)
U chooses IDU, PWU, and random numbers bU ∈ [1, n − 1] and then U provides IDU and H1 (PWU || bU) × P to S through a secure channel(ii)
When receiving {IDU, H1 (PWU || bU) × P} from U, S computes AIDU = (qS + 1) × H1 (PWU || bU) × P and BIDU = H2 (H1 (IDU) || H1 (PWU || bU) × P)(iii)
S saves {AIDU, BIDU} into the smart card and then sends to U via a secure channel(iv)
When receiving,U inputs bU into the smart card. Finally, U has {AIDU, BIDU, bU}At this phase,S attaches U’s personal information with S’s master key qS to create the user’s authentication key by using H1 (.). Figure 3 describes all steps in this phase.Figure 3
User registration phase of Qu et al.’s scheme.


#### 3.2.3. Login Phase

WhenU logins into S, U provides IDU, PWU, and his/her smart card into the terminal. Then, the smart card performs the following steps:(i)
The smart card computesBIDU′ = H2 (H1 (IDU) || (H1 (PWU || bU) × P)) and checks if BIDU′ = BIDU (BIDU is stored in the smart card). If this holds, U provides correct information. Otherwise, the smart card will terminate the session.(ii)
U randomly chooses rU ∈ [1, n − 1] and computes TIDU = AIDU − H1 (PWU || bU) × P, M = rU × QS, CIDU = IDU × H2 (M || TIDU), DIDU = M + H1 (PWU || bU) × P, and EIDU = H3 (IDU || M || R), where R = rU × P.(iii)
The smart card sendsM1 = {CIDU, DIDU, EIDU, R} to S through a public channel.In this phase, identity is not attached withU’s authentication key, so this is a weak point that another adversary can exploit to launch an impersonation attack. Figure 4 describes all steps in this phase and authentication phase.Figure 4
User authentication phase of Qu et al.’s scheme.


#### 3.2.4. Authentication Phase

When receiving the login message fromU, S performs as follows:(i)
S computes M′ = qS × R, H1 (PWU || bU) × P = DIDU − M′, TIDU′ = qS × H1 (PWU || bU) × P, and IDU = CIDU ⊕ H2 (M′ || TIDU′). Then, S checks if H3 (IDU ||M′ || R) = EIDU. If this holds, S successfully authenticates with U. Otherwise, the session is terminated.(ii)
S chooses rS ∈ [1, n − 1] and then computes S = rS × P, T = S + M′, and HS = H2 (S || TIDU′).(iii)
S sends M2 = {T, HS} to U through a public channel.(iv)
When receivingM2 = {T, HS} from S, U computes S = T – M and HS′ = H2 (S || H1 (PWU || bU) × QS) and checks if HS′ = HS. If this holds, U successfully authenticates with S and U sends M3 = {HRS} to S, where HRS = H2 (R || S). Otherwise, U terminates the session.(v)
On receivingM3 = {HRS}, S computes HRS′ = H2 (R || S) and checks if HRS′ = HRS. If this holds, S and U successfully authenticate each other. Otherwise, S terminates the session.(vi)
U and S compute common SK = H3 (IDU || TIDU || rU × S) = H3 (IDU || TIDU′ || rS × R).


#### 3.2.5. Password-Update Phase

When receiving the login message fromU, S performs as follows:(i)
U provides IDU, PWU, and the smart card at the terminal. Then, it computes BIDU′ = H2 (H1 (IDU) || (H1 (PWU || bU) × P)) and checks if BIDU′ = BIDU. If this holds, U can choose PWUnew. Otherwise, the session is terminated.(ii)
The smart card computesAIDUnew = H1 (PWU || bU)−1 × AIDU × H1 (PWUnew || bU) and BIDUnew = H2 (H1 (IDU) || H1 (PWUnew || bU) × P).(iii)
The smart card replacesAIDU and BIDU with AIDUnew and BIDUnew.


#### 3.2.6. The Scheme’s Cryptanalysis

If the user’s identity is leaked, that user will be impersonated. Assuming another adversary is also a member. We call him/herUa with corresponding {AIDA, BIDA} in his/her smart card. If Ua knows victim’s IDU, Ua performs the following steps to launch an impersonation attack:(i)
Ua randomly chooses rA ∈ [1, n − 1] and computes R = rA × P.(ii)
Next,Ua extracts TIDA = AIDA − H1 (PWA || bA) × P, where AIDA, PWA, bA, and TIDA are information in Ua’s smart card.(iii)
Ua computes M = rA × QS, CIDA = IDU ⊕ H2 (M || TIDA), DIDA = M + H1 (PWA || bA) × P, and EIDA = H3 (IDU || M || R). Then, Ua sends M1 = {CIDA, DIDA, EIDA, R} to S.(iv)
When receivingM1, S computes M′ = qS × R = qS × rA × P = rA × QS, H1 (PWU || bU) × P = DIDA − M′, TIDA′ = qS × H1 (PWA || bA) × P, and IDU = CIDA ⊕ H2 (M′ || TIDA′).(v)
S checks if H3 (IDU || M′ || R) = EIDA, and we see this condition holds.(vi)
S randomly chooses rS ∈ [1, n − 1], computes S = rS × P, T = S + M′, and HS = H2 (S || TIDA′), and sends M2 = {T, HS} to Ua.(vii)
On receivingM2, Ua computes S = T − M and HRS = H2 (R || S). Finally, Ua sends M3 = {HRS} to S.(viii)
When receivingM3, S computes HRS′ = H2 (R || S) and see that HRS′ = HRS.If the user’s identity is leaked, he/she will be impersonated. The reason is that the user’s identity is not attached with their secret information, for example, the authentication keyAIDU is not attached with identity, or BIDU is only used for verification of the smart-card owner and does not take part in the authentication phase.


### 3.3. Amin and Biswas’s Scheme

Amin and Biswas’s scheme [13] uses ECC and biohashing, a special hash function overcoming the problem of sensitive input which exists in traditional hash function. In 2004, Jin et al. [27] proposed a remarkable improved biohashing function. Amin and Biswas’s scheme includes four phases: registration, login, authentication, and password-update phases. Table 3 presents some notations used in this scheme.Table 3
Notations used in the scheme [13].
NotationsDescriptionUi, Sith user, medical centrePWi, IDi, BiPassword/identity/biometrics ofUip, q, FpTwo prime numbers, finite fieldEP (Fp)EC inFp: y2 = x3 + ax + b (a, b ∈ Fp) and δ = 4a3 + 27 b2 ≠ 0GGroup of points inEP (Fp)PBase point ofG with prime order qaPPoint multiplicationPxSecret key ofS (1024 bit)ℤp∗Multiplicative grouph (.)Hash function {0, 1}∗ ⟶ ℤp∗H (.)Biohashingh1 (.)Hash functionGp × Gp ⟶ ℤp∗⊕, ||,ENC/DECXOR, concatenation, encrypt/decrypt


#### 3.3.1. Registration Phase

In this phase,Ui chooses IDi, PWi, and biometrics Ti. Next, Ui computes Ai = h (IDi || PWi) and Fi = H (Ti) and sends {IDi, Ai, Fi} to S through a secure channel. When receiving {IDi, Ai, Fi} from Ui, S computes W = h (IDS ||x || IDi), Bi = h (IDi || Ai) ⊕ W, and CIDi = ENCx (IDi || Rran) and sends a smart card including {Fi, Ai, Bi, CIDi, h (.), H (.)} back to Ui through a secure channel, where IDS is S’s identity and Rran is the random number chosen by S. In this phase, Ui can choose IDi and PWi easily guessed by password-guessing attack or identity-guessing attack. Figure 5 describes all steps in this phase.Figure 5
User registration phase of Amin et al.’s scheme.


#### 3.3.2. Login Phase

WhenUi successfully registers, Ui performs as follows:(i)
Ui provides the smart card with Ti, and then the smart card computes Fi∗ = H (Ti) and checks if Fi∗ = Fi (Fi is stored in the smart card). If this condition holds, Ui continues providing IDi and PWi; otherwise, the scheme is terminated.(ii)
The smart card computesAi∗ = h (IDi || PWi) and checks if Ai∗ = Ai (Ai is stored in the smart card). If this condition holds, the phase continues; otherwise, it is terminated.(iii)
Ui randomly chooses ri, computes C1 = ri × P, W = Bi ⊕ h (IDi || Ai∗), C2 = ri ⊕ W, and C4 = h (IDi || ri || W), and sends {C2, C4, CIDi} to S through a public channel.In this phase,Ui needs to use biometrics + password + identity to prove the smart-card owner. This method protects the user from impersonation attacks. Figure 6 describes all steps in this phase and the authentication phase.Figure 6
User authentication phase of Amin et al.’s scheme.


#### 3.3.3. Authentication Phase

WhenS receives {C2, C4, CIDi} from Ui, S and Ui perform as follows:(i)
When receiving {C2, C4, CIDi} from Ui, S decrypts CIDi by using x and S obtains (IDi∗ || Rran) = DECx (CIDi). Then, S computes W = h (IDS ||x || IDi∗), ri∗ = C2 ⊕ W, C1∗ = ri∗ × P, and C4∗ = h (IDi || ri∗ || W) and checks if C4∗ = C4 (C4 is stored in the smart card). If this condition holds, S believes Ui is the valid user.(ii)
S randomly chooses rj, computes D1 = rj × P, SK = rj × C1∗ = rj × ri∗ × P, G1 = D1 + C1∗, Li = h (IDi∗ || h1 (D1) || W), and CIDi′ = ENCx (IDi∗ || Rran′), and sends {Li, G1, CIDi′} to Ui through a public channel.(iii)
When receiving {Li, G1, CIDi′} from S, Ui computes D1∗ = G1 − C1∗, Li∗ = h (IDi || h1 (D1∗) || W), and SK = ri × D1∗ = ri × rj × P and checks if Li∗ = Li. If this condition holds, Ui believe S is valid and SK is a common session key of Ui and S. After the successful authentication phase, Ui replaces CIDi with CIDi′. Finally, Ui computes Zi = h (IDi || SK) and sends to S through a public channel.(iv)
When receiving {Zi} from Ui, S computes Zi∗ = h (IDi∗ || SK) and checks if Zi∗ = Zi. If this condition holds, the authentication phase successfully completes.In this phase, replacingCIDi after successfully authentication will enhance the user’s privacy. Because each transaction has a different value, there is no way to know who is online, as well we cannot identify whether two transactions belong to one user.


#### 3.3.4. Password-Update Phase

Ui needs to successfully login if he/she wants to change the password. Ui needs to provide PWinew, and then his/her smart card computes Ainew = h (IDi || PWinew) and Binew = h (IDi || Ainew) ⊕ W, where W is the old value and replaces (Ai, Bi) with (Ainew, Binew).


#### 3.3.5. The Scheme’s Cryptanalysis

If the master key is leaked, all previous exchanged messages between the user and server are also leaked. For example, if the keyx is leaked, the adversary stores previous message packages of the user and server, such as {C2, CIDi, C4} or {Li, G1, CIDi′}. The adversary will extract IDi by using x to decrypt CIDi, computes W = h (IDS ||x || IDi) and ri = C2 ⊕ W. With ri, the adversary computes C1 = ri × P and D1 = G1 − C1. From ri and Di, the adversary finally computes SK = ri × D1.


### 3.4. Jangirala et al.’s Scheme

This scheme [18] uses hash function combined with random values, including four phases: registration, login, authentication, and password-update phases. Because designed for multiserver environment, the registration centre constructs the master key h (x || y) for itself and the submaster key h (SIDj || h (y)) for each service provider. Notations used in this scheme are in Table 1.


#### 3.4.1. Registration Phase

Ui registers with RC as follows:(i)
Ui chooses IDi, PWi, and random value b and computes Ai = h (IDi ⊕ b ⊕ PWi). Then, Ui sends IDi and Ai to RC through a secure channel.(ii)
On receiving {IDi, Ai} from Ui, RC computes Bi = h (Ai || x), Ci = h (IDi || h (y) || Ai), Di = h (Bi || h (x || y)), and Ei = Bi ⊕ h (x || y).(iii)
RC saves {Ci, Di, Ei, h (.), h (y)} into a smart card and sends to Ui via a secure channel.(iv)
Ui computes Li = b ⊕ h (IDi || PWi). Then, Ui inserts Li into the smart card, and finally, Ui has {Ci, Di, Ei, Li, h (.), h (y)}.In the registration phase, we see that their scheme encryptsb with h (IDi || PWi). This prevents some kinds of privileged insider attacks. Figure 7 describes all steps in this phase.Figure 7
User authentication phase of Jangirala et al.’s scheme.


#### 3.4.2. Login Phase

This phase sendsUi’s login request to Sj as follows:(i)
Ui inserts his/her smart card and inputs IDi and PWi. Then, the smart card computes b = Li ⊕ h (IDi || PWi), Ai = h (IDi ⊕ b ⊕ PWi), and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. If this holds, Ui continues. Otherwise, the smart card terminates the session.(ii)
The smart card randomly chooses valuesNi and computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Ni), CIDi = Ai ⊕ h (Di || SIDj || Ni), M1 = h (Pij || CIDi || Ai || Ni), and M2 = h (SIDj || h (y)) ⊕ Ni.(iii)
Ui sends {Pij, CIDi, M1, M2} to Sj through a public channel.At this phase, random valueNi can be easily known by the adversary because it is only protected by h (y). Furthermore, if the user’s smart card is leaked, the adversary can compute his/her Di and discover what the user did in previous session corresponding to Ni.


#### 3.4.3. Authentication Phase

WhenSj receives {Pij, CIDi, M1, M2} from Ui, Sj verifies Ui’s login message as follows:(i)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(ii)
Sj computes h (Pij || CIDi || Ai || Ni) and compares it with M1. If two values are not matched, Sj rejects the login message and terminates the session. Otherwise, Sj accepts the login message. Then, Sj randomly chooses Nj and computes SKij = h (h (Bi || h (x || y)) || Ai), M3 = h (SKij || Ai || SIDj || Nj), and M4 = SKij ⊕ Nj ⊕ Nj. Finally, Sj sends {M3, M4} to Ui through a public channel.(iii)
When receiving {M3, M4} from Sj, Ui computes SKij = h (Di || Ai), Nj = SKij ⊕ M4, and h (SKij || Ai || SIDj || SIDj) and then compares it with M3. If two values are not matched, Ui rejects the message and terminates the session. Otherwise, Ui successfully authenticates with Sj. Then, Ui computes M5 = h (SKij || Ai || SIDj || Ni || Nj) and sends {M5} to Sj through a public channel.(iv)
When receiving {M5} from Ui, Sj computes h (SKij || Ai || SIDj || Ni || Nj) and compares it with M5. If two values are equal, Sj successfully authenticates with Ui.(v)
Next,Ui and Sj compute a common session key SKeyij = h (SKij || Ai || SIDj || Ni || Di || Nj) used to encrypt later transactions. Also, Sj chooses the random value Nj and only the valid user (who has Di and Ai) can extract this Nj and send correct response. Figure 8 describes all steps in this phase.Figure 8
User authentication phase of Jangirala et al.’s scheme.


#### 3.4.4. Password-Update Phase

This phase is performed whenUi changes PWi into PWinew without interacting with RC:(i)
Ui provides his/her smart card at the terminal and inputs IDi and PWi.(ii)
The smart card computesb∗ = Li ⊕ h (IDi || PWi), Ai∗ = h (IDi ⊕ b∗ ⊕ PWi), and Ci∗ = h (IDi || h (y) || Ai∗) and checks if Ci∗ = Ci. Is this does not hold, the smart card rejects and terminates the password-update-request session. Otherwise, Ui inputs PWinew.(iii)
The smart card computesAinew = h (IDi ⊕ b∗ ⊕ PWinew) and Cinew = h (IDi || Ainew || h (y)).(iv)
Finally, the smart card replacesCi with Cinew and Li with Linew, where Linew = b∗ ⊕ h (IDi || PWinew).


#### 3.4.5. The Scheme’s Cryptanalysis

If anotherUi’s smart card leaks information {Ci, Di, Ei, h (y), h (.)} and the adversary Ua is another valid user, Ua can launch an impersonation attack as follows:(i)
Ua computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Na), where Na is random value chosen by Ua(ii)
Then,Ua computes CIDi = Aa ⊕ h (Di || SIDj || Na), M1 = h (Pij || CIDi || Aa || Na), and M2 = h (SIDj || h (y)) ⊕ Na, where Aa belongs to Ua(iii)
Next,Ua sends {Pij, CIDi, M1, M2} to Sj(iv)
Once receiving these messages,Sj computes Na = h (SIDj ||h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Na), Bi = Ei ⊕ h (x || y), and Di = h (Bi || h (x || y))(v)
NextSj computes Aa = CIDi ⊕ h (Di || SIDj || Na) and sees that M1 = h (Pij || CIDi || Aa || Na)(vi)
Sj chooses Nj and computes SKij = h (h (Bi || h (x || y)) || Aa), M3 = h (SKij || Aa || SIDj || Nj), and M4 = SKij ⊕ Nj(vii)
Then,Sj sends {M3, M4} to Ua(viii)
Once receiving these messages fromSj, Ua computes SKij = h (Di || Aa) and Nj = SKij ⊕ M4 and sends M5 to Sj, where M5 = h (SKij || Aa || SIDj || Na || Nj).(ix)
Once receivingM5 from Ua, Sj sees that M5 = h (SKij || Aa || SIDj || Na || Nj) and computes the session key SKeyij = h (SKij || Aa || SIDj || Na || Di || Nj)Clearly,Ua successfully authenticates with Sj without knowing the user’s identity and password.


### 3.5. Han et al.’s Scheme

This scheme [19] uses the fuzzy extractor to process the user’s biometrics, including four phases: registration, login, authentication, and password-update phases. With symmetric encryption, this scheme truly has strong user anonymity because the adversary cannot know if two login sessions are belonged to the same user. Some notations used in this scheme are in Table 4.Table 4
Notations used in the scheme [19].
NotationsDescriptionU, SUser/patient, telecare serverPW, ID, BPassword/identity/biometrics ofUsPrivate key of serverSKSession key betweenU and Sh (.)Cryptographic one-way hash functionEncx (.)/Decx (.)Symmetric encryption schemeGenProbabilistic generation algorithmRepProbabilistic reproduction algorithm⊕, ||,TnXOR, concatenation, Chebyshev operation


#### 3.5.1. Registration Phase

In the registration phase, we see that their scheme generates <R, P> from the user’s biometrics with the fuzzy extractor. Furthermore, the user’s dynamic identity is made by the server by using the encryption scheme. Figure 9 describes all steps in this phase.Figure 9
User registration phase of Han et al.’s scheme.Firstly, the user choosesID, PW, biometrics B, and random value r. Then, the fuzzy extractor generates <R, P> from B and the user computes A = h (PW || R) ⊕ r. Next, the user sends {ID, A}. Once receiving the user’s messages, the server computes AID = h (ID || s), K = h (AID), V′ = AID ⊕ A, and CID = Encs (ID || a), where a is chosen randomly by and s is private key of the server. Then, the server sends SC = {K, V′, CID, h (.)} to the user. Once receiving the server’s message, the user computes V = V′ ⊕ A ⊕ h (ID || PW || R) and replaces V′ by V. The user inserts P in SC and keeps it secret.


#### 3.5.2. Login Phase

The user sends insertsSC into the terminal and enters ID, PW, and B′ similar to B. Then, SC performs as follows:(i)
SC performs Rep (B′, P) to generate R and computes AID = V ⊕ h (ID || PW || R)(ii)
SC checks if K = h (AID). If this holds, go to next step(iii)
SC generates a nonce u and computes X = Tu (AID) and V1 = h (ID || X || CID || T1)(iv)
SC transmits {CID, X, V1, T1} to the serverAt this phase, the user needs to recreate theR value by providing correct his/her biometrics.


#### 3.5.3. Authentication Phase

When receiving the login message from the user,S verifies the login message as follows:(i)
S checks if |Tc − T1| ≤ δT, where Tc is receiving time. If this holds, S retrieves ID by computing Decs (CID) with the private key s.(ii)
Then,S computes AID = h (ID || s) and checks if V1 = h (ID || X || CID || T1). If this holds, S generates random values a′ and v.(iii)
Then,S computes CID′ = Encs (ID || a′), SK = h (Tv (X)), Y = Tv (AID), and V2 = h (CID′ || Y || SK || T2), where T2 is current time.(iv)
Then,S sends {CID′, Y, V2, T2} to the user.(v)
Once receiving messages from the server,SC checks T2 and calculates SK = h (Tu (Y)).(vi)
Then,SC checks if V2 = h (CID′ || Y || SK || T2). If this holds, SC replaces CID with CID′, computes V3 = h (SK || T3), and sends {V3, T3} to S.(vii)
Once receiving messages, the server checksT3 and verifies if V3 = h (SK || T3). If this holds, the user and server successfully authenticate to each other and accept SK as a session key.This scheme is completely dependent on random valuesu and v, and this is vulnerable to known session-specific temporary information attack. Figure 10 describes all steps in this phase.Figure 10
User authentication phase of Han et al.’s scheme.


#### 3.5.4. Password-Update Phase

This phase is performed whenU changes PW into PWnew without interacting with S:(i)
U inserts his/her smart card into the terminal and inputs ID, PW, and B′. SC executes Rep (B′, P) = R and computes AID = V ⊕ h (ID || PW || R).(ii)
SC checks if h (AID) = K. If this holds, SC allows the change request.(iii)
U inputs PWnew and Bnew, and then SC computes <Rnew, Pnew> = Gen (Bnew) and Vnew = V ⊕ h (ID || PW || R) ⊕ h (ID || PWnew || Rnew).(iv)
Finally,SC replaces V by Vnew.


#### 3.5.5. The Scheme’s Cryptanalysis

If another session leaks the random valuev, the adversary can exploit to reattack the user and know previous messages transmitted between the user and server. For example, the adversary Ua obtains {CID, X, V1, T1}, {CID′, Y, V2, T2}, and {V3, T3} with the random value v leaked, and Ua can launch an impersonation attack as follows:(i)
IfU sends the new login message {CID′, X′, V1′, T1′} to S, Ua can block this message.(ii)
Ua generates random CIDʺ.(iii)
Then,Ua computes SK′ = h (Tv (X′)) and V2′ = h (CIDʺ || Y || SK′ || T2′), where T2′ is current time and Y is previous value of U and S.(iv)
Then,Ua sends {CIDʺ, Y, V2′, T2′} to U.(v)
Once receiving the message fromUa, U checks T2′. If this holds, U computes SK′ = h (Tu′ (Y)), where u′ is a random value chosen by U.(vi)
U checks if V2′ = h (CIDʺ || Y || SK′ ||T2′). We see this holds and U sends V3′ = h (SK′ || T3′) to Ua.Clearly, the adversary can reuse this random valuev to reattack the user many times. The main reason is that CID is what the user does not know.


### 3.6. Proposed Scheme

InSection 3, we review some typical schemes using many approaches such as Chebyshev polynomial or elliptic curve cryptosystem in various environments. Although these schemes are well designed with some interesting primitives, such as fuzzy extractor or symmetric encryption scheme, they are still vulnerable to some typical kinds of attacks, such as password-guessing or impersonation. Indeed, there are still interesting schemes [17, 20], but they are designed with three-party participation different with two-party participation of the proposed scheme. Therefore, we temporarily do not consider in this paper. Figure 11 shows our architecture of participation between registration centre (RC), servers (Sj), and users (UX), where the keys of servers and users are created by RC.Figure 11
Architecture of our proposed scheme.With this architecture in Figure11, we can deploy a RC to centralize all medical servers. Also, the users easily find the medical services suitable for them. This section presents the phases in our proposed scheme. Our scheme uses Chebyshev polynomial in multiserver environment with two-party participation, including five phases: initialization, registration (server + user), authentication, and password-update phases. Some notations used in our scheme are in Table 5.Table 5
Notations used in our scheme.
NotationsDescriptionUX, Sj, RCXth user/jth server, registration centreBXBiometrics ofUXqRCMaster key ofRCASIDjSj’s master keysjXUX’s authentication key with SjSKSession key betweenUX and SjH0 (.)Cryptographic one-way hash functionGen/RepGeneration/reproduction algorithm⊕, ||,TnXOR, concatenation, Chebyshev operation


#### 3.6.1. System Initialization

RC chooses the big prime number p ∈ ℙ k-bit and a qRC. Then, RC chooses H0: {0, 1}∗ ⟶ {0, 1}k. RC publishes {T (.), H0 (.), p} and keeps qRC secret.


#### 3.6.2. Server Registration Phase

In this phase,Sj provides SIDj to RC through a secure channel. RC chooses rj and computes ASIDj =  TqRC (H0 (SIDj || rj)) mod p and then returns {rj, SIDj, ASIDj, H0 (.)} to Sj. Figure 12 shows the steps in this phase.Figure 12
Proposed scheme’s server registration phase.In this phase, each serverSj has unique master key ASIDj produced by RC. RC must keep the pair <rj, SIDj> for subsequent retrieval and the user’s registration.


#### 3.6.3. User Registration Phase

UX provides biometrics BX and UIDX, using Gen (BX) to generate <RX, PX>. Then, UX sends {UIDX, H0 (RX || UIDX)} to RC through a secure channel. Once receiving the messages, RC computes all submaster keys for all service providers. RC chooses rX and then computes sjX = TrX (UIDX || H0 (RX || UIDX)) mod p + TASIDj (H0 (rj + rX + UIDX)) mod p and RPWX = H0 (H0 (RX || UIDX) || rX). RC returns {s1X, s2X, …, smX, RPWX, and H0 (.), rX} to UX through a secure channel. Figure 13 shows the steps in this phase.Figure 13
Proposed scheme’s user registration phase.In this phase,RC computes sjX, which is an authentication key between UX and Sj (1 ≤ j ≤ m, where m is a number of Sj). Similar to [19], our scheme uses the fuzzy extractor to deal with the problem of output-sensitive due to inputs’ perturbations. Additionally, RC must notify Sj about UX by sending pair <rX, UIDX> for the subsequent user’s authentication.


#### 3.6.4. Authentication Phase

WhenUX logins to Sj, UX provides the smart card with UIDX and BX′ at the terminal. Then, the smart card reproduces RX = Rep (PX, BX′) and checks if RPWX = H0 (H0 (RX || UIDX) || rX); if this does not hold, the session is terminated; otherwise, the smart card chooses rU and computes TASIDj (H0 (rj + rX + UIDX)) mod p =  sjX − TrX (UIDX || H0 (RX || UIDX)) mod p, RU =  TrU (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p, R′ = RU + TASIDj (H0 (rj + rX + UIDX)) mod p, CID = UIDX ⊕ H0 (RU), and MU = H0 (RU, TASIDj (H0 (rj + rX + UIDX)) mod p). Then, the smart card sends {CID, R′, MU, rX} to Sj. On receiving the message, Sj computes TASIDj (H0 (rj + rX + UIDX)) mod p, RU′ = R′ − TASIDj (H0 (rj + rX + UIDX)) mod p, and UIDX = CID ⊕ H0 (RU′) and checks UIDX; then, Sj checks if MU = H0 (RU′, TASIDj (H0 (rj + rX + UIDX)) mod p), and if this does not hold, Sj terminates the session; otherwise, Sj chooses rS and computes RS =  TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p, S′ = RS + RU′, SK = H0 (TrS (RU′) mod p), and MS = H0 (RS, TASIDj (H0 (rj + rX + UIDX)) mod p). Sj sends {MS, S′} to UX. On receiving the message, UX computes RS′ = S′ − RU and SK = H0 (TrU (RS′) mod p) and checks if MS = H0 (RS′, TASIDj (H0 (rj + rX + UIDX)) mod p); if this does not hold, UX terminates the session; otherwise, UX believes Sj is valid and sends MUS = H0 (RS′, TrU (RS′) mod p) to Sj. On receiving the message, Sj checks if MUS = H0 (RS, TrS (RU′) mod p); if this does not hold, Sj terminates the session; otherwise, Sj believes UX is valid. Figure 14 shows the steps in this phase.Figure 14
Proposed scheme’s authentication phase.


#### 3.6.5. Password-Update Phase

WhenUX changes BX, UX provides his/her smart card with UIDX and similar BX′ at the terminal. Then, the smart card checks if RPWX = H0 (H0 (RX || UIDX) || rX), where RX = Rep (PX, BX′). If this does not hold, the smart card terminates the session; otherwise, UX inputs Bnew and computes RPWnew = H0 (H0 (Rnew || UIDX) || rX), where <Rnew, Pnew> = Gen (Bnew), Then, the smart card updates RPWX = RPWnew and PX = Pnew. Finally, the smart card updates all authentication keys sjX = sjX − TrX (UIDX || H0 (RX || UIDX)) + TrX (UIDX || H0 (Rnew || UIDX)), ∀j.


## 3.1. Li et al.’s Scheme

This scheme [11] uses hash function combined with random values, including four phases: registration, login, authentication, and password-update phases. Because designed for multiserver environment, the registration centre constructs the master key h (x || y) for itself and the submaster key h (SIDj || h (y)) for each service provider. Table 1 presents some notations used in this scheme.Table 1
Notations used in the scheme [11].
NotationsDescriptionUi, Sj, RCith user, jth server, registration centreIDi, PWiIdentity and password ofUiSIDj, CIDiSj’s identity, Ui’s dynamic identityx, yMaster key and secret value ofRCh (.), ⊕, ||Hash function, XOR, and concatenation⇒/⟶Secure/public channels


### 3.1.1. Registration Phase

Ui registers with RC as follows:(i)
Ui chooses IDi, PWi, and random value b and computes Ai = h (b ⊕ PWi). Then, Ui sends IDi and Ai to RC through a secure channel.(ii)
On receiving {IDi, Ai} from Ui, RC computes Bi = h (IDi || x), Ci = h (IDi || h (y) || Ai), Di = h (Bi || h (x || y)), and Ei = Bi ⊕ h (x || y).(iii)
RC saves {Ci, Di, Ei, h (.), h (y)} into a smart card and sends to Ui via a secure channel.(iv)
Ui inputs b into the smart card, and finally, Ui has {Ci, Di, Ei, b, h (.), h (y)}.In the registration phase, we see that the author used common keyh (y), and this is dangerous because the adversary can exploit this to launch an impersonation attack if the smart card’s information is leaked or stolen. Figure 1 describes all steps in this phase.Figure 1
User registration phase of Li et al.’s scheme.


### 3.1.2. Login Phase

When logging into service,Ui performs as follows:(i)
Ui provides his/her smart card and inputs IDi and PWi. Then, the smart card computes Ai = h (b ⊕ PWi) and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. If this holds, Ui continues. Otherwise, the smart card terminates the session.(ii)
The smart card randomly chooses valuesNi and computes Pij = Ei ⊕ (h (h) (SIDj || h (y)) || Ni), CIDi = Ai ⊕ (h (D)i || SIDj || Ni), M1 = h (P)ij || CIDi || Di || Ni), and M2 = h (SIDj ||h (y)) ⊕ Ni.(iii)
Ui sends {Pij, CIDi, M1, M2} to Sj through a public channel.At this phase, the random valueNi can be easily computed because it is only protected by h (y). This decreases the challenge from the user and makes the scheme unbalanced.


### 3.1.3. Authentication Phase

In this phase, the server also chooses the random valueNj and only the valid user (who has Ai) can recompute this Nj and send a correct response. Figure 2 describes all steps in this phase.Figure 2
User authentication phase of Li et al.’s scheme.WhenSj receives {Pij, CIDi, M1, M2} from Ui, Sj, and Ui, it performs the following steps:(i)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(ii)
Sj computes h (Pij || CIDi || Di || Ni) and compares it with M1. If two values are unequal, Sj rejects the login message and terminates the session. Otherwise, Sj accepts login message. Then, Sj randomly chooses Nj and computes M3 = h (Di || Ai || Nj || SIDj) and M4 = Ai ⊕ Ni ⊕ Nj. Finally, Sj sends {M3, M4} to Ui through a public channel.(iii)
When receiving {M3, M4} from Sj, Ui computes Nj = Ai ⊕ Ni ⊕ M4 and h (Di || Ai || Nj || SIDj) and then compares it with M3. If two values are unequal, Ui rejects the message and terminates the session. Otherwise, Ui successfully authenticates with Sj. Then, Ui computes M5 = h (Di || Ai || Ni || SIDj) and sends {M5} to Sj through a public channel.(iv)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj  || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(v)
When receiving {M5} from Ui, Sj computes h (Di || Ai || Ni || SIDj) and compares it with M5. If two values are equal, Sj successfully authenticates with Ui and authentication phase completes.(vi)
Next,Ui and Sj compute a common session key SK = h (Di || Ai || Ni || Nj || SIDj) used to encrypt later transactions.


### 3.1.4. Password-Update Phase

This phase is performed whenUi changes PWi into PWinew without interacting with RC:(i)
Ui inputs IDi and PWi and provides his/her smart card at the terminal.(ii)
The smart card computesAi = h (b ⊕ PWi) and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. Is this does not hold, the smart card rejects password-update request. Otherwise, Ui inputs PWinew and random number bnew.(iii)
The smart card computesAinew = h (bnew ⊕ PWinew) and Cinew = h (IDi || h (y) || Ainew).(iv)
Finally, the smart card replacesCi with Cinew and terminates the session.


### 3.1.5. The Scheme’s Cryptanalysis

IfUi loses his/her smart card, it can result in impersonation attack. Furthermore, another attacker Ua can exploit Sj to guess the password through session key. Therefore, Li’s scheme is also vulnerable to two-factor attack. Below are some steps to launch an impersonation and password-guessing attacks:(i)
Ua computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Ni), where Ei is extracted from the smart card. SIDj, h (y), and Ni are easily computed by Ua because they are public information.(ii)
NextUa computes CIDi = Ai ⊕ h (Di || SIDj || Ni), M1 = h (Pij || CIDi || Di || Ni), and M2 = h (SIDj || h (y)) ⊕ Ni, where Ai = h (b ⊕ PWi) is Ua’s value and Di is extracted from Ui’s smart card.(iii)
Ua sends {Pij, CIDi, M1, M2} to Sj. When receiving, Sj will perform the following steps to verify.(iv)
Sj extracts Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(v)
Sj sees M1 = h (Pij || CIDi || Di || Ni), so Sj randomly chooses Nj and computes M3 = h (Di || Ai || Nj || SIDj) and M4 = Ai ⊕ Ni ⊕ Nj. Sj sends {M3, M4} to Ua.(vi)
When receiving {M3, M4}, Ua computes M5 = h (Di || Ai || Ni || SIDj) and sends to Sj.(vii)
Sj sees M5 = h (Di || Ai || Ni || SIDj) and accepts Ua.(viii
)Finally,Ua and Sj compute a common session key SK = h (Di || Ai || Ni || Nj || SIDj).BecauseEi is extracted from Ui’s smart card, the values Bi and Di also belong to Ui. However, in Li’s scheme, Ai is separated from other values, so Ua can exploit this limitation to insert his/her information. Furthermore, if Ua captures previous transactions between Ui and Sj, he/she will launch Ui’s password-guessing attack. Assuming Ua has Ui’s M5 = h (Di || Ai || Ni || SIDj), so Ua can construct h (Di || h (b ⊕ guess) || Ni || SIDj) = M5 and use the password dictionary to search “guess” until success. Note that Ui’s Ni is easily found by computing Ni = M2 ⊕ h (SIDj || h (y)), in which SIDj and h (y) are those Ua easily computes.


## 3.1.1. Registration Phase

Ui registers with RC as follows:(i)
Ui chooses IDi, PWi, and random value b and computes Ai = h (b ⊕ PWi). Then, Ui sends IDi and Ai to RC through a secure channel.(ii)
On receiving {IDi, Ai} from Ui, RC computes Bi = h (IDi || x), Ci = h (IDi || h (y) || Ai), Di = h (Bi || h (x || y)), and Ei = Bi ⊕ h (x || y).(iii)
RC saves {Ci, Di, Ei, h (.), h (y)} into a smart card and sends to Ui via a secure channel.(iv)
Ui inputs b into the smart card, and finally, Ui has {Ci, Di, Ei, b, h (.), h (y)}.In the registration phase, we see that the author used common keyh (y), and this is dangerous because the adversary can exploit this to launch an impersonation attack if the smart card’s information is leaked or stolen. Figure 1 describes all steps in this phase.Figure 1
User registration phase of Li et al.’s scheme.


## 3.1.2. Login Phase

When logging into service,Ui performs as follows:(i)
Ui provides his/her smart card and inputs IDi and PWi. Then, the smart card computes Ai = h (b ⊕ PWi) and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. If this holds, Ui continues. Otherwise, the smart card terminates the session.(ii)
The smart card randomly chooses valuesNi and computes Pij = Ei ⊕ (h (h) (SIDj || h (y)) || Ni), CIDi = Ai ⊕ (h (D)i || SIDj || Ni), M1 = h (P)ij || CIDi || Di || Ni), and M2 = h (SIDj ||h (y)) ⊕ Ni.(iii)
Ui sends {Pij, CIDi, M1, M2} to Sj through a public channel.At this phase, the random valueNi can be easily computed because it is only protected by h (y). This decreases the challenge from the user and makes the scheme unbalanced.


## 3.1.3. Authentication Phase

In this phase, the server also chooses the random valueNj and only the valid user (who has Ai) can recompute this Nj and send a correct response. Figure 2 describes all steps in this phase.Figure 2
User authentication phase of Li et al.’s scheme.WhenSj receives {Pij, CIDi, M1, M2} from Ui, Sj, and Ui, it performs the following steps:(i)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(ii)
Sj computes h (Pij || CIDi || Di || Ni) and compares it with M1. If two values are unequal, Sj rejects the login message and terminates the session. Otherwise, Sj accepts login message. Then, Sj randomly chooses Nj and computes M3 = h (Di || Ai || Nj || SIDj) and M4 = Ai ⊕ Ni ⊕ Nj. Finally, Sj sends {M3, M4} to Ui through a public channel.(iii)
When receiving {M3, M4} from Sj, Ui computes Nj = Ai ⊕ Ni ⊕ M4 and h (Di || Ai || Nj || SIDj) and then compares it with M3. If two values are unequal, Ui rejects the message and terminates the session. Otherwise, Ui successfully authenticates with Sj. Then, Ui computes M5 = h (Di || Ai || Ni || SIDj) and sends {M5} to Sj through a public channel.(iv)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj  || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(v)
When receiving {M5} from Ui, Sj computes h (Di || Ai || Ni || SIDj) and compares it with M5. If two values are equal, Sj successfully authenticates with Ui and authentication phase completes.(vi)
Next,Ui and Sj compute a common session key SK = h (Di || Ai || Ni || Nj || SIDj) used to encrypt later transactions.


## 3.1.4. Password-Update Phase

This phase is performed whenUi changes PWi into PWinew without interacting with RC:(i)
Ui inputs IDi and PWi and provides his/her smart card at the terminal.(ii)
The smart card computesAi = h (b ⊕ PWi) and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. Is this does not hold, the smart card rejects password-update request. Otherwise, Ui inputs PWinew and random number bnew.(iii)
The smart card computesAinew = h (bnew ⊕ PWinew) and Cinew = h (IDi || h (y) || Ainew).(iv)
Finally, the smart card replacesCi with Cinew and terminates the session.


## 3.1.5. The Scheme’s Cryptanalysis

IfUi loses his/her smart card, it can result in impersonation attack. Furthermore, another attacker Ua can exploit Sj to guess the password through session key. Therefore, Li’s scheme is also vulnerable to two-factor attack. Below are some steps to launch an impersonation and password-guessing attacks:(i)
Ua computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Ni), where Ei is extracted from the smart card. SIDj, h (y), and Ni are easily computed by Ua because they are public information.(ii)
NextUa computes CIDi = Ai ⊕ h (Di || SIDj || Ni), M1 = h (Pij || CIDi || Di || Ni), and M2 = h (SIDj || h (y)) ⊕ Ni, where Ai = h (b ⊕ PWi) is Ua’s value and Di is extracted from Ui’s smart card.(iii)
Ua sends {Pij, CIDi, M1, M2} to Sj. When receiving, Sj will perform the following steps to verify.(iv)
Sj extracts Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(v)
Sj sees M1 = h (Pij || CIDi || Di || Ni), so Sj randomly chooses Nj and computes M3 = h (Di || Ai || Nj || SIDj) and M4 = Ai ⊕ Ni ⊕ Nj. Sj sends {M3, M4} to Ua.(vi)
When receiving {M3, M4}, Ua computes M5 = h (Di || Ai || Ni || SIDj) and sends to Sj.(vii)
Sj sees M5 = h (Di || Ai || Ni || SIDj) and accepts Ua.(viii
)Finally,Ua and Sj compute a common session key SK = h (Di || Ai || Ni || Nj || SIDj).BecauseEi is extracted from Ui’s smart card, the values Bi and Di also belong to Ui. However, in Li’s scheme, Ai is separated from other values, so Ua can exploit this limitation to insert his/her information. Furthermore, if Ua captures previous transactions between Ui and Sj, he/she will launch Ui’s password-guessing attack. Assuming Ua has Ui’s M5 = h (Di || Ai || Ni || SIDj), so Ua can construct h (Di || h (b ⊕ guess) || Ni || SIDj) = M5 and use the password dictionary to search “guess” until success. Note that Ui’s Ni is easily found by computing Ni = M2 ⊕ h (SIDj || h (y)), in which SIDj and h (y) are those Ua easily computes.


## 3.2. Qu and Tan’s Scheme

Qu and Tan’s scheme [12] uses ECC, and it is secure against some popular kinds of attacks as they claimed. However, we will prove their scheme is vulnerable to impersonation attack. This scheme includes five phases: initialization, registration, login, authentication, and password-update phases. Table 2 presents some notations used in this scheme.Table 2
Notations used in the scheme [12].
NotationsDescriptionS, U, (qS, QS)Server/user, key-pair ofSIDU, PWUIdentity and password ofUH1Hash function {0, 1}∗ ⟶ GpH2Hash functionGp × Gp ⟶ ℤp∗H3|Hash function {0, 1}∗ × Gp × Gp ⟶ {0, 1}krU, rSSecret values ofU and SFp, EP (Fp)Finite field, elliptic curve defined overFpGGroup of points inEP (Fp), G = n ∈ ℙPBase pointP is a generator of G


### 3.2.1. System Initialization

In this phase, the system initializes some parameters:(i)
S chooses the elliptic curve EP (a, b) and base point P with big prime order n(ii)
S chooses qS ∈ [1, n − 1] and computes the public key QS = qS × P(iii)
S chooses three hash functions, H1 (.), H2 (.), and H3 (.), described in Table 2(iv)
S published {EP (a, b), P, QS, H1 (.), H2 (.), H3 (.)}In this phase, we see thatH1 (.) is special because it receives any string and outputs a point belonging to the elliptic curve.


### 3.2.2. Registration Phase

When registering,U must follow following steps:(i)
U chooses IDU, PWU, and random numbers bU ∈ [1, n − 1] and then U provides IDU and H1 (PWU || bU) × P to S through a secure channel(ii)
When receiving {IDU, H1 (PWU || bU) × P} from U, S computes AIDU = (qS + 1) × H1 (PWU || bU) × P and BIDU = H2 (H1 (IDU) || H1 (PWU || bU) × P)(iii)
S saves {AIDU, BIDU} into the smart card and then sends to U via a secure channel(iv)
When receiving,U inputs bU into the smart card. Finally, U has {AIDU, BIDU, bU}At this phase,S attaches U’s personal information with S’s master key qS to create the user’s authentication key by using H1 (.). Figure 3 describes all steps in this phase.Figure 3
User registration phase of Qu et al.’s scheme.


### 3.2.3. Login Phase

WhenU logins into S, U provides IDU, PWU, and his/her smart card into the terminal. Then, the smart card performs the following steps:(i)
The smart card computesBIDU′ = H2 (H1 (IDU) || (H1 (PWU || bU) × P)) and checks if BIDU′ = BIDU (BIDU is stored in the smart card). If this holds, U provides correct information. Otherwise, the smart card will terminate the session.(ii)
U randomly chooses rU ∈ [1, n − 1] and computes TIDU = AIDU − H1 (PWU || bU) × P, M = rU × QS, CIDU = IDU × H2 (M || TIDU), DIDU = M + H1 (PWU || bU) × P, and EIDU = H3 (IDU || M || R), where R = rU × P.(iii)
The smart card sendsM1 = {CIDU, DIDU, EIDU, R} to S through a public channel.In this phase, identity is not attached withU’s authentication key, so this is a weak point that another adversary can exploit to launch an impersonation attack. Figure 4 describes all steps in this phase and authentication phase.Figure 4
User authentication phase of Qu et al.’s scheme.


### 3.2.4. Authentication Phase

When receiving the login message fromU, S performs as follows:(i)
S computes M′ = qS × R, H1 (PWU || bU) × P = DIDU − M′, TIDU′ = qS × H1 (PWU || bU) × P, and IDU = CIDU ⊕ H2 (M′ || TIDU′). Then, S checks if H3 (IDU ||M′ || R) = EIDU. If this holds, S successfully authenticates with U. Otherwise, the session is terminated.(ii)
S chooses rS ∈ [1, n − 1] and then computes S = rS × P, T = S + M′, and HS = H2 (S || TIDU′).(iii)
S sends M2 = {T, HS} to U through a public channel.(iv)
When receivingM2 = {T, HS} from S, U computes S = T – M and HS′ = H2 (S || H1 (PWU || bU) × QS) and checks if HS′ = HS. If this holds, U successfully authenticates with S and U sends M3 = {HRS} to S, where HRS = H2 (R || S). Otherwise, U terminates the session.(v)
On receivingM3 = {HRS}, S computes HRS′ = H2 (R || S) and checks if HRS′ = HRS. If this holds, S and U successfully authenticate each other. Otherwise, S terminates the session.(vi)
U and S compute common SK = H3 (IDU || TIDU || rU × S) = H3 (IDU || TIDU′ || rS × R).


### 3.2.5. Password-Update Phase

When receiving the login message fromU, S performs as follows:(i)
U provides IDU, PWU, and the smart card at the terminal. Then, it computes BIDU′ = H2 (H1 (IDU) || (H1 (PWU || bU) × P)) and checks if BIDU′ = BIDU. If this holds, U can choose PWUnew. Otherwise, the session is terminated.(ii)
The smart card computesAIDUnew = H1 (PWU || bU)−1 × AIDU × H1 (PWUnew || bU) and BIDUnew = H2 (H1 (IDU) || H1 (PWUnew || bU) × P).(iii)
The smart card replacesAIDU and BIDU with AIDUnew and BIDUnew.


### 3.2.6. The Scheme’s Cryptanalysis

If the user’s identity is leaked, that user will be impersonated. Assuming another adversary is also a member. We call him/herUa with corresponding {AIDA, BIDA} in his/her smart card. If Ua knows victim’s IDU, Ua performs the following steps to launch an impersonation attack:(i)
Ua randomly chooses rA ∈ [1, n − 1] and computes R = rA × P.(ii)
Next,Ua extracts TIDA = AIDA − H1 (PWA || bA) × P, where AIDA, PWA, bA, and TIDA are information in Ua’s smart card.(iii)
Ua computes M = rA × QS, CIDA = IDU ⊕ H2 (M || TIDA), DIDA = M + H1 (PWA || bA) × P, and EIDA = H3 (IDU || M || R). Then, Ua sends M1 = {CIDA, DIDA, EIDA, R} to S.(iv)
When receivingM1, S computes M′ = qS × R = qS × rA × P = rA × QS, H1 (PWU || bU) × P = DIDA − M′, TIDA′ = qS × H1 (PWA || bA) × P, and IDU = CIDA ⊕ H2 (M′ || TIDA′).(v)
S checks if H3 (IDU || M′ || R) = EIDA, and we see this condition holds.(vi)
S randomly chooses rS ∈ [1, n − 1], computes S = rS × P, T = S + M′, and HS = H2 (S || TIDA′), and sends M2 = {T, HS} to Ua.(vii)
On receivingM2, Ua computes S = T − M and HRS = H2 (R || S). Finally, Ua sends M3 = {HRS} to S.(viii)
When receivingM3, S computes HRS′ = H2 (R || S) and see that HRS′ = HRS.If the user’s identity is leaked, he/she will be impersonated. The reason is that the user’s identity is not attached with their secret information, for example, the authentication keyAIDU is not attached with identity, or BIDU is only used for verification of the smart-card owner and does not take part in the authentication phase.


## 3.2.1. System Initialization

In this phase, the system initializes some parameters:(i)
S chooses the elliptic curve EP (a, b) and base point P with big prime order n(ii)
S chooses qS ∈ [1, n − 1] and computes the public key QS = qS × P(iii)
S chooses three hash functions, H1 (.), H2 (.), and H3 (.), described in Table 2(iv)
S published {EP (a, b), P, QS, H1 (.), H2 (.), H3 (.)}In this phase, we see thatH1 (.) is special because it receives any string and outputs a point belonging to the elliptic curve.


## 3.2.2. Registration Phase

When registering,U must follow following steps:(i)
U chooses IDU, PWU, and random numbers bU ∈ [1, n − 1] and then U provides IDU and H1 (PWU || bU) × P to S through a secure channel(ii)
When receiving {IDU, H1 (PWU || bU) × P} from U, S computes AIDU = (qS + 1) × H1 (PWU || bU) × P and BIDU = H2 (H1 (IDU) || H1 (PWU || bU) × P)(iii)
S saves {AIDU, BIDU} into the smart card and then sends to U via a secure channel(iv)
When receiving,U inputs bU into the smart card. Finally, U has {AIDU, BIDU, bU}At this phase,S attaches U’s personal information with S’s master key qS to create the user’s authentication key by using H1 (.). Figure 3 describes all steps in this phase.Figure 3
User registration phase of Qu et al.’s scheme.


## 3.2.3. Login Phase

WhenU logins into S, U provides IDU, PWU, and his/her smart card into the terminal. Then, the smart card performs the following steps:(i)
The smart card computesBIDU′ = H2 (H1 (IDU) || (H1 (PWU || bU) × P)) and checks if BIDU′ = BIDU (BIDU is stored in the smart card). If this holds, U provides correct information. Otherwise, the smart card will terminate the session.(ii)
U randomly chooses rU ∈ [1, n − 1] and computes TIDU = AIDU − H1 (PWU || bU) × P, M = rU × QS, CIDU = IDU × H2 (M || TIDU), DIDU = M + H1 (PWU || bU) × P, and EIDU = H3 (IDU || M || R), where R = rU × P.(iii)
The smart card sendsM1 = {CIDU, DIDU, EIDU, R} to S through a public channel.In this phase, identity is not attached withU’s authentication key, so this is a weak point that another adversary can exploit to launch an impersonation attack. Figure 4 describes all steps in this phase and authentication phase.Figure 4
User authentication phase of Qu et al.’s scheme.


## 3.2.4. Authentication Phase

When receiving the login message fromU, S performs as follows:(i)
S computes M′ = qS × R, H1 (PWU || bU) × P = DIDU − M′, TIDU′ = qS × H1 (PWU || bU) × P, and IDU = CIDU ⊕ H2 (M′ || TIDU′). Then, S checks if H3 (IDU ||M′ || R) = EIDU. If this holds, S successfully authenticates with U. Otherwise, the session is terminated.(ii)
S chooses rS ∈ [1, n − 1] and then computes S = rS × P, T = S + M′, and HS = H2 (S || TIDU′).(iii)
S sends M2 = {T, HS} to U through a public channel.(iv)
When receivingM2 = {T, HS} from S, U computes S = T – M and HS′ = H2 (S || H1 (PWU || bU) × QS) and checks if HS′ = HS. If this holds, U successfully authenticates with S and U sends M3 = {HRS} to S, where HRS = H2 (R || S). Otherwise, U terminates the session.(v)
On receivingM3 = {HRS}, S computes HRS′ = H2 (R || S) and checks if HRS′ = HRS. If this holds, S and U successfully authenticate each other. Otherwise, S terminates the session.(vi)
U and S compute common SK = H3 (IDU || TIDU || rU × S) = H3 (IDU || TIDU′ || rS × R).


## 3.2.5. Password-Update Phase

When receiving the login message fromU, S performs as follows:(i)
U provides IDU, PWU, and the smart card at the terminal. Then, it computes BIDU′ = H2 (H1 (IDU) || (H1 (PWU || bU) × P)) and checks if BIDU′ = BIDU. If this holds, U can choose PWUnew. Otherwise, the session is terminated.(ii)
The smart card computesAIDUnew = H1 (PWU || bU)−1 × AIDU × H1 (PWUnew || bU) and BIDUnew = H2 (H1 (IDU) || H1 (PWUnew || bU) × P).(iii)
The smart card replacesAIDU and BIDU with AIDUnew and BIDUnew.


## 3.2.6. The Scheme’s Cryptanalysis

If the user’s identity is leaked, that user will be impersonated. Assuming another adversary is also a member. We call him/herUa with corresponding {AIDA, BIDA} in his/her smart card. If Ua knows victim’s IDU, Ua performs the following steps to launch an impersonation attack:(i)
Ua randomly chooses rA ∈ [1, n − 1] and computes R = rA × P.(ii)
Next,Ua extracts TIDA = AIDA − H1 (PWA || bA) × P, where AIDA, PWA, bA, and TIDA are information in Ua’s smart card.(iii)
Ua computes M = rA × QS, CIDA = IDU ⊕ H2 (M || TIDA), DIDA = M + H1 (PWA || bA) × P, and EIDA = H3 (IDU || M || R). Then, Ua sends M1 = {CIDA, DIDA, EIDA, R} to S.(iv)
When receivingM1, S computes M′ = qS × R = qS × rA × P = rA × QS, H1 (PWU || bU) × P = DIDA − M′, TIDA′ = qS × H1 (PWA || bA) × P, and IDU = CIDA ⊕ H2 (M′ || TIDA′).(v)
S checks if H3 (IDU || M′ || R) = EIDA, and we see this condition holds.(vi)
S randomly chooses rS ∈ [1, n − 1], computes S = rS × P, T = S + M′, and HS = H2 (S || TIDA′), and sends M2 = {T, HS} to Ua.(vii)
On receivingM2, Ua computes S = T − M and HRS = H2 (R || S). Finally, Ua sends M3 = {HRS} to S.(viii)
When receivingM3, S computes HRS′ = H2 (R || S) and see that HRS′ = HRS.If the user’s identity is leaked, he/she will be impersonated. The reason is that the user’s identity is not attached with their secret information, for example, the authentication keyAIDU is not attached with identity, or BIDU is only used for verification of the smart-card owner and does not take part in the authentication phase.


## 3.3. Amin and Biswas’s Scheme

Amin and Biswas’s scheme [13] uses ECC and biohashing, a special hash function overcoming the problem of sensitive input which exists in traditional hash function. In 2004, Jin et al. [27] proposed a remarkable improved biohashing function. Amin and Biswas’s scheme includes four phases: registration, login, authentication, and password-update phases. Table 3 presents some notations used in this scheme.Table 3
Notations used in the scheme [13].
NotationsDescriptionUi, Sith user, medical centrePWi, IDi, BiPassword/identity/biometrics ofUip, q, FpTwo prime numbers, finite fieldEP (Fp)EC inFp: y2 = x3 + ax + b (a, b ∈ Fp) and δ = 4a3 + 27 b2 ≠ 0GGroup of points inEP (Fp)PBase point ofG with prime order qaPPoint multiplicationPxSecret key ofS (1024 bit)ℤp∗Multiplicative grouph (.)Hash function {0, 1}∗ ⟶ ℤp∗H (.)Biohashingh1 (.)Hash functionGp × Gp ⟶ ℤp∗⊕, ||,ENC/DECXOR, concatenation, encrypt/decrypt


### 3.3.1. Registration Phase

In this phase,Ui chooses IDi, PWi, and biometrics Ti. Next, Ui computes Ai = h (IDi || PWi) and Fi = H (Ti) and sends {IDi, Ai, Fi} to S through a secure channel. When receiving {IDi, Ai, Fi} from Ui, S computes W = h (IDS ||x || IDi), Bi = h (IDi || Ai) ⊕ W, and CIDi = ENCx (IDi || Rran) and sends a smart card including {Fi, Ai, Bi, CIDi, h (.), H (.)} back to Ui through a secure channel, where IDS is S’s identity and Rran is the random number chosen by S. In this phase, Ui can choose IDi and PWi easily guessed by password-guessing attack or identity-guessing attack. Figure 5 describes all steps in this phase.Figure 5
User registration phase of Amin et al.’s scheme.


### 3.3.2. Login Phase

WhenUi successfully registers, Ui performs as follows:(i)
Ui provides the smart card with Ti, and then the smart card computes Fi∗ = H (Ti) and checks if Fi∗ = Fi (Fi is stored in the smart card). If this condition holds, Ui continues providing IDi and PWi; otherwise, the scheme is terminated.(ii)
The smart card computesAi∗ = h (IDi || PWi) and checks if Ai∗ = Ai (Ai is stored in the smart card). If this condition holds, the phase continues; otherwise, it is terminated.(iii)
Ui randomly chooses ri, computes C1 = ri × P, W = Bi ⊕ h (IDi || Ai∗), C2 = ri ⊕ W, and C4 = h (IDi || ri || W), and sends {C2, C4, CIDi} to S through a public channel.In this phase,Ui needs to use biometrics + password + identity to prove the smart-card owner. This method protects the user from impersonation attacks. Figure 6 describes all steps in this phase and the authentication phase.Figure 6
User authentication phase of Amin et al.’s scheme.


### 3.3.3. Authentication Phase

WhenS receives {C2, C4, CIDi} from Ui, S and Ui perform as follows:(i)
When receiving {C2, C4, CIDi} from Ui, S decrypts CIDi by using x and S obtains (IDi∗ || Rran) = DECx (CIDi). Then, S computes W = h (IDS ||x || IDi∗), ri∗ = C2 ⊕ W, C1∗ = ri∗ × P, and C4∗ = h (IDi || ri∗ || W) and checks if C4∗ = C4 (C4 is stored in the smart card). If this condition holds, S believes Ui is the valid user.(ii)
S randomly chooses rj, computes D1 = rj × P, SK = rj × C1∗ = rj × ri∗ × P, G1 = D1 + C1∗, Li = h (IDi∗ || h1 (D1) || W), and CIDi′ = ENCx (IDi∗ || Rran′), and sends {Li, G1, CIDi′} to Ui through a public channel.(iii)
When receiving {Li, G1, CIDi′} from S, Ui computes D1∗ = G1 − C1∗, Li∗ = h (IDi || h1 (D1∗) || W), and SK = ri × D1∗ = ri × rj × P and checks if Li∗ = Li. If this condition holds, Ui believe S is valid and SK is a common session key of Ui and S. After the successful authentication phase, Ui replaces CIDi with CIDi′. Finally, Ui computes Zi = h (IDi || SK) and sends to S through a public channel.(iv)
When receiving {Zi} from Ui, S computes Zi∗ = h (IDi∗ || SK) and checks if Zi∗ = Zi. If this condition holds, the authentication phase successfully completes.In this phase, replacingCIDi after successfully authentication will enhance the user’s privacy. Because each transaction has a different value, there is no way to know who is online, as well we cannot identify whether two transactions belong to one user.


### 3.3.4. Password-Update Phase

Ui needs to successfully login if he/she wants to change the password. Ui needs to provide PWinew, and then his/her smart card computes Ainew = h (IDi || PWinew) and Binew = h (IDi || Ainew) ⊕ W, where W is the old value and replaces (Ai, Bi) with (Ainew, Binew).


### 3.3.5. The Scheme’s Cryptanalysis

If the master key is leaked, all previous exchanged messages between the user and server are also leaked. For example, if the keyx is leaked, the adversary stores previous message packages of the user and server, such as {C2, CIDi, C4} or {Li, G1, CIDi′}. The adversary will extract IDi by using x to decrypt CIDi, computes W = h (IDS ||x || IDi) and ri = C2 ⊕ W. With ri, the adversary computes C1 = ri × P and D1 = G1 − C1. From ri and Di, the adversary finally computes SK = ri × D1.


## 3.3.1. Registration Phase

In this phase,Ui chooses IDi, PWi, and biometrics Ti. Next, Ui computes Ai = h (IDi || PWi) and Fi = H (Ti) and sends {IDi, Ai, Fi} to S through a secure channel. When receiving {IDi, Ai, Fi} from Ui, S computes W = h (IDS ||x || IDi), Bi = h (IDi || Ai) ⊕ W, and CIDi = ENCx (IDi || Rran) and sends a smart card including {Fi, Ai, Bi, CIDi, h (.), H (.)} back to Ui through a secure channel, where IDS is S’s identity and Rran is the random number chosen by S. In this phase, Ui can choose IDi and PWi easily guessed by password-guessing attack or identity-guessing attack. Figure 5 describes all steps in this phase.Figure 5
User registration phase of Amin et al.’s scheme.


## 3.3.2. Login Phase

WhenUi successfully registers, Ui performs as follows:(i)
Ui provides the smart card with Ti, and then the smart card computes Fi∗ = H (Ti) and checks if Fi∗ = Fi (Fi is stored in the smart card). If this condition holds, Ui continues providing IDi and PWi; otherwise, the scheme is terminated.(ii)
The smart card computesAi∗ = h (IDi || PWi) and checks if Ai∗ = Ai (Ai is stored in the smart card). If this condition holds, the phase continues; otherwise, it is terminated.(iii)
Ui randomly chooses ri, computes C1 = ri × P, W = Bi ⊕ h (IDi || Ai∗), C2 = ri ⊕ W, and C4 = h (IDi || ri || W), and sends {C2, C4, CIDi} to S through a public channel.In this phase,Ui needs to use biometrics + password + identity to prove the smart-card owner. This method protects the user from impersonation attacks. Figure 6 describes all steps in this phase and the authentication phase.Figure 6
User authentication phase of Amin et al.’s scheme.


## 3.3.3. Authentication Phase

WhenS receives {C2, C4, CIDi} from Ui, S and Ui perform as follows:(i)
When receiving {C2, C4, CIDi} from Ui, S decrypts CIDi by using x and S obtains (IDi∗ || Rran) = DECx (CIDi). Then, S computes W = h (IDS ||x || IDi∗), ri∗ = C2 ⊕ W, C1∗ = ri∗ × P, and C4∗ = h (IDi || ri∗ || W) and checks if C4∗ = C4 (C4 is stored in the smart card). If this condition holds, S believes Ui is the valid user.(ii)
S randomly chooses rj, computes D1 = rj × P, SK = rj × C1∗ = rj × ri∗ × P, G1 = D1 + C1∗, Li = h (IDi∗ || h1 (D1) || W), and CIDi′ = ENCx (IDi∗ || Rran′), and sends {Li, G1, CIDi′} to Ui through a public channel.(iii)
When receiving {Li, G1, CIDi′} from S, Ui computes D1∗ = G1 − C1∗, Li∗ = h (IDi || h1 (D1∗) || W), and SK = ri × D1∗ = ri × rj × P and checks if Li∗ = Li. If this condition holds, Ui believe S is valid and SK is a common session key of Ui and S. After the successful authentication phase, Ui replaces CIDi with CIDi′. Finally, Ui computes Zi = h (IDi || SK) and sends to S through a public channel.(iv)
When receiving {Zi} from Ui, S computes Zi∗ = h (IDi∗ || SK) and checks if Zi∗ = Zi. If this condition holds, the authentication phase successfully completes.In this phase, replacingCIDi after successfully authentication will enhance the user’s privacy. Because each transaction has a different value, there is no way to know who is online, as well we cannot identify whether two transactions belong to one user.


## 3.3.4. Password-Update Phase

Ui needs to successfully login if he/she wants to change the password. Ui needs to provide PWinew, and then his/her smart card computes Ainew = h (IDi || PWinew) and Binew = h (IDi || Ainew) ⊕ W, where W is the old value and replaces (Ai, Bi) with (Ainew, Binew).


## 3.3.5. The Scheme’s Cryptanalysis

If the master key is leaked, all previous exchanged messages between the user and server are also leaked. For example, if the keyx is leaked, the adversary stores previous message packages of the user and server, such as {C2, CIDi, C4} or {Li, G1, CIDi′}. The adversary will extract IDi by using x to decrypt CIDi, computes W = h (IDS ||x || IDi) and ri = C2 ⊕ W. With ri, the adversary computes C1 = ri × P and D1 = G1 − C1. From ri and Di, the adversary finally computes SK = ri × D1.


## 3.4. Jangirala et al.’s Scheme

This scheme [18] uses hash function combined with random values, including four phases: registration, login, authentication, and password-update phases. Because designed for multiserver environment, the registration centre constructs the master key h (x || y) for itself and the submaster key h (SIDj || h (y)) for each service provider. Notations used in this scheme are in Table 1.


### 3.4.1. Registration Phase

Ui registers with RC as follows:(i)
Ui chooses IDi, PWi, and random value b and computes Ai = h (IDi ⊕ b ⊕ PWi). Then, Ui sends IDi and Ai to RC through a secure channel.(ii)
On receiving {IDi, Ai} from Ui, RC computes Bi = h (Ai || x), Ci = h (IDi || h (y) || Ai), Di = h (Bi || h (x || y)), and Ei = Bi ⊕ h (x || y).(iii)
RC saves {Ci, Di, Ei, h (.), h (y)} into a smart card and sends to Ui via a secure channel.(iv)
Ui computes Li = b ⊕ h (IDi || PWi). Then, Ui inserts Li into the smart card, and finally, Ui has {Ci, Di, Ei, Li, h (.), h (y)}.In the registration phase, we see that their scheme encryptsb with h (IDi || PWi). This prevents some kinds of privileged insider attacks. Figure 7 describes all steps in this phase.Figure 7
User authentication phase of Jangirala et al.’s scheme.


### 3.4.2. Login Phase

This phase sendsUi’s login request to Sj as follows:(i)
Ui inserts his/her smart card and inputs IDi and PWi. Then, the smart card computes b = Li ⊕ h (IDi || PWi), Ai = h (IDi ⊕ b ⊕ PWi), and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. If this holds, Ui continues. Otherwise, the smart card terminates the session.(ii)
The smart card randomly chooses valuesNi and computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Ni), CIDi = Ai ⊕ h (Di || SIDj || Ni), M1 = h (Pij || CIDi || Ai || Ni), and M2 = h (SIDj || h (y)) ⊕ Ni.(iii)
Ui sends {Pij, CIDi, M1, M2} to Sj through a public channel.At this phase, random valueNi can be easily known by the adversary because it is only protected by h (y). Furthermore, if the user’s smart card is leaked, the adversary can compute his/her Di and discover what the user did in previous session corresponding to Ni.


### 3.4.3. Authentication Phase

WhenSj receives {Pij, CIDi, M1, M2} from Ui, Sj verifies Ui’s login message as follows:(i)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(ii)
Sj computes h (Pij || CIDi || Ai || Ni) and compares it with M1. If two values are not matched, Sj rejects the login message and terminates the session. Otherwise, Sj accepts the login message. Then, Sj randomly chooses Nj and computes SKij = h (h (Bi || h (x || y)) || Ai), M3 = h (SKij || Ai || SIDj || Nj), and M4 = SKij ⊕ Nj ⊕ Nj. Finally, Sj sends {M3, M4} to Ui through a public channel.(iii)
When receiving {M3, M4} from Sj, Ui computes SKij = h (Di || Ai), Nj = SKij ⊕ M4, and h (SKij || Ai || SIDj || SIDj) and then compares it with M3. If two values are not matched, Ui rejects the message and terminates the session. Otherwise, Ui successfully authenticates with Sj. Then, Ui computes M5 = h (SKij || Ai || SIDj || Ni || Nj) and sends {M5} to Sj through a public channel.(iv)
When receiving {M5} from Ui, Sj computes h (SKij || Ai || SIDj || Ni || Nj) and compares it with M5. If two values are equal, Sj successfully authenticates with Ui.(v)
Next,Ui and Sj compute a common session key SKeyij = h (SKij || Ai || SIDj || Ni || Di || Nj) used to encrypt later transactions. Also, Sj chooses the random value Nj and only the valid user (who has Di and Ai) can extract this Nj and send correct response. Figure 8 describes all steps in this phase.Figure 8
User authentication phase of Jangirala et al.’s scheme.


### 3.4.4. Password-Update Phase

This phase is performed whenUi changes PWi into PWinew without interacting with RC:(i)
Ui provides his/her smart card at the terminal and inputs IDi and PWi.(ii)
The smart card computesb∗ = Li ⊕ h (IDi || PWi), Ai∗ = h (IDi ⊕ b∗ ⊕ PWi), and Ci∗ = h (IDi || h (y) || Ai∗) and checks if Ci∗ = Ci. Is this does not hold, the smart card rejects and terminates the password-update-request session. Otherwise, Ui inputs PWinew.(iii)
The smart card computesAinew = h (IDi ⊕ b∗ ⊕ PWinew) and Cinew = h (IDi || Ainew || h (y)).(iv)
Finally, the smart card replacesCi with Cinew and Li with Linew, where Linew = b∗ ⊕ h (IDi || PWinew).


### 3.4.5. The Scheme’s Cryptanalysis

If anotherUi’s smart card leaks information {Ci, Di, Ei, h (y), h (.)} and the adversary Ua is another valid user, Ua can launch an impersonation attack as follows:(i)
Ua computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Na), where Na is random value chosen by Ua(ii)
Then,Ua computes CIDi = Aa ⊕ h (Di || SIDj || Na), M1 = h (Pij || CIDi || Aa || Na), and M2 = h (SIDj || h (y)) ⊕ Na, where Aa belongs to Ua(iii)
Next,Ua sends {Pij, CIDi, M1, M2} to Sj(iv)
Once receiving these messages,Sj computes Na = h (SIDj ||h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Na), Bi = Ei ⊕ h (x || y), and Di = h (Bi || h (x || y))(v)
NextSj computes Aa = CIDi ⊕ h (Di || SIDj || Na) and sees that M1 = h (Pij || CIDi || Aa || Na)(vi)
Sj chooses Nj and computes SKij = h (h (Bi || h (x || y)) || Aa), M3 = h (SKij || Aa || SIDj || Nj), and M4 = SKij ⊕ Nj(vii)
Then,Sj sends {M3, M4} to Ua(viii)
Once receiving these messages fromSj, Ua computes SKij = h (Di || Aa) and Nj = SKij ⊕ M4 and sends M5 to Sj, where M5 = h (SKij || Aa || SIDj || Na || Nj).(ix)
Once receivingM5 from Ua, Sj sees that M5 = h (SKij || Aa || SIDj || Na || Nj) and computes the session key SKeyij = h (SKij || Aa || SIDj || Na || Di || Nj)Clearly,Ua successfully authenticates with Sj without knowing the user’s identity and password.


## 3.4.1. Registration Phase

Ui registers with RC as follows:(i)
Ui chooses IDi, PWi, and random value b and computes Ai = h (IDi ⊕ b ⊕ PWi). Then, Ui sends IDi and Ai to RC through a secure channel.(ii)
On receiving {IDi, Ai} from Ui, RC computes Bi = h (Ai || x), Ci = h (IDi || h (y) || Ai), Di = h (Bi || h (x || y)), and Ei = Bi ⊕ h (x || y).(iii)
RC saves {Ci, Di, Ei, h (.), h (y)} into a smart card and sends to Ui via a secure channel.(iv)
Ui computes Li = b ⊕ h (IDi || PWi). Then, Ui inserts Li into the smart card, and finally, Ui has {Ci, Di, Ei, Li, h (.), h (y)}.In the registration phase, we see that their scheme encryptsb with h (IDi || PWi). This prevents some kinds of privileged insider attacks. Figure 7 describes all steps in this phase.Figure 7
User authentication phase of Jangirala et al.’s scheme.


## 3.4.2. Login Phase

This phase sendsUi’s login request to Sj as follows:(i)
Ui inserts his/her smart card and inputs IDi and PWi. Then, the smart card computes b = Li ⊕ h (IDi || PWi), Ai = h (IDi ⊕ b ⊕ PWi), and Ci∗ = h (IDi || h (y) || Ai) and checks if Ci∗ = Ci. If this holds, Ui continues. Otherwise, the smart card terminates the session.(ii)
The smart card randomly chooses valuesNi and computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Ni), CIDi = Ai ⊕ h (Di || SIDj || Ni), M1 = h (Pij || CIDi || Ai || Ni), and M2 = h (SIDj || h (y)) ⊕ Ni.(iii)
Ui sends {Pij, CIDi, M1, M2} to Sj through a public channel.At this phase, random valueNi can be easily known by the adversary because it is only protected by h (y). Furthermore, if the user’s smart card is leaked, the adversary can compute his/her Di and discover what the user did in previous session corresponding to Ni.


## 3.4.3. Authentication Phase

WhenSj receives {Pij, CIDi, M1, M2} from Ui, Sj verifies Ui’s login message as follows:(i)
Sj computes Ni = h (SIDj || h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Ni), Bi = Ei ⊕ h (x || y), Di = h (Bi || h (x || y)), and Ai = CIDi ⊕ h (Di || SIDj || Ni).(ii)
Sj computes h (Pij || CIDi || Ai || Ni) and compares it with M1. If two values are not matched, Sj rejects the login message and terminates the session. Otherwise, Sj accepts the login message. Then, Sj randomly chooses Nj and computes SKij = h (h (Bi || h (x || y)) || Ai), M3 = h (SKij || Ai || SIDj || Nj), and M4 = SKij ⊕ Nj ⊕ Nj. Finally, Sj sends {M3, M4} to Ui through a public channel.(iii)
When receiving {M3, M4} from Sj, Ui computes SKij = h (Di || Ai), Nj = SKij ⊕ M4, and h (SKij || Ai || SIDj || SIDj) and then compares it with M3. If two values are not matched, Ui rejects the message and terminates the session. Otherwise, Ui successfully authenticates with Sj. Then, Ui computes M5 = h (SKij || Ai || SIDj || Ni || Nj) and sends {M5} to Sj through a public channel.(iv)
When receiving {M5} from Ui, Sj computes h (SKij || Ai || SIDj || Ni || Nj) and compares it with M5. If two values are equal, Sj successfully authenticates with Ui.(v)
Next,Ui and Sj compute a common session key SKeyij = h (SKij || Ai || SIDj || Ni || Di || Nj) used to encrypt later transactions. Also, Sj chooses the random value Nj and only the valid user (who has Di and Ai) can extract this Nj and send correct response. Figure 8 describes all steps in this phase.Figure 8
User authentication phase of Jangirala et al.’s scheme.


## 3.4.4. Password-Update Phase

This phase is performed whenUi changes PWi into PWinew without interacting with RC:(i)
Ui provides his/her smart card at the terminal and inputs IDi and PWi.(ii)
The smart card computesb∗ = Li ⊕ h (IDi || PWi), Ai∗ = h (IDi ⊕ b∗ ⊕ PWi), and Ci∗ = h (IDi || h (y) || Ai∗) and checks if Ci∗ = Ci. Is this does not hold, the smart card rejects and terminates the password-update-request session. Otherwise, Ui inputs PWinew.(iii)
The smart card computesAinew = h (IDi ⊕ b∗ ⊕ PWinew) and Cinew = h (IDi || Ainew || h (y)).(iv)
Finally, the smart card replacesCi with Cinew and Li with Linew, where Linew = b∗ ⊕ h (IDi || PWinew).


## 3.4.5. The Scheme’s Cryptanalysis

If anotherUi’s smart card leaks information {Ci, Di, Ei, h (y), h (.)} and the adversary Ua is another valid user, Ua can launch an impersonation attack as follows:(i)
Ua computes Pij = Ei ⊕ h (h (SIDj || h (y)) || Na), where Na is random value chosen by Ua(ii)
Then,Ua computes CIDi = Aa ⊕ h (Di || SIDj || Na), M1 = h (Pij || CIDi || Aa || Na), and M2 = h (SIDj || h (y)) ⊕ Na, where Aa belongs to Ua(iii)
Next,Ua sends {Pij, CIDi, M1, M2} to Sj(iv)
Once receiving these messages,Sj computes Na = h (SIDj ||h (y)) ⊕ M2, Ei = Pij ⊕ h (h (SIDj || h (y)) || Na), Bi = Ei ⊕ h (x || y), and Di = h (Bi || h (x || y))(v)
NextSj computes Aa = CIDi ⊕ h (Di || SIDj || Na) and sees that M1 = h (Pij || CIDi || Aa || Na)(vi)
Sj chooses Nj and computes SKij = h (h (Bi || h (x || y)) || Aa), M3 = h (SKij || Aa || SIDj || Nj), and M4 = SKij ⊕ Nj(vii)
Then,Sj sends {M3, M4} to Ua(viii)
Once receiving these messages fromSj, Ua computes SKij = h (Di || Aa) and Nj = SKij ⊕ M4 and sends M5 to Sj, where M5 = h (SKij || Aa || SIDj || Na || Nj).(ix)
Once receivingM5 from Ua, Sj sees that M5 = h (SKij || Aa || SIDj || Na || Nj) and computes the session key SKeyij = h (SKij || Aa || SIDj || Na || Di || Nj)Clearly,Ua successfully authenticates with Sj without knowing the user’s identity and password.


## 3.5. Han et al.’s Scheme

This scheme [19] uses the fuzzy extractor to process the user’s biometrics, including four phases: registration, login, authentication, and password-update phases. With symmetric encryption, this scheme truly has strong user anonymity because the adversary cannot know if two login sessions are belonged to the same user. Some notations used in this scheme are in Table 4.Table 4
Notations used in the scheme [19].
NotationsDescriptionU, SUser/patient, telecare serverPW, ID, BPassword/identity/biometrics ofUsPrivate key of serverSKSession key betweenU and Sh (.)Cryptographic one-way hash functionEncx (.)/Decx (.)Symmetric encryption schemeGenProbabilistic generation algorithmRepProbabilistic reproduction algorithm⊕, ||,TnXOR, concatenation, Chebyshev operation


### 3.5.1. Registration Phase

In the registration phase, we see that their scheme generates <R, P> from the user’s biometrics with the fuzzy extractor. Furthermore, the user’s dynamic identity is made by the server by using the encryption scheme. Figure 9 describes all steps in this phase.Figure 9
User registration phase of Han et al.’s scheme.Firstly, the user choosesID, PW, biometrics B, and random value r. Then, the fuzzy extractor generates <R, P> from B and the user computes A = h (PW || R) ⊕ r. Next, the user sends {ID, A}. Once receiving the user’s messages, the server computes AID = h (ID || s), K = h (AID), V′ = AID ⊕ A, and CID = Encs (ID || a), where a is chosen randomly by and s is private key of the server. Then, the server sends SC = {K, V′, CID, h (.)} to the user. Once receiving the server’s message, the user computes V = V′ ⊕ A ⊕ h (ID || PW || R) and replaces V′ by V. The user inserts P in SC and keeps it secret.


### 3.5.2. Login Phase

The user sends insertsSC into the terminal and enters ID, PW, and B′ similar to B. Then, SC performs as follows:(i)
SC performs Rep (B′, P) to generate R and computes AID = V ⊕ h (ID || PW || R)(ii)
SC checks if K = h (AID). If this holds, go to next step(iii)
SC generates a nonce u and computes X = Tu (AID) and V1 = h (ID || X || CID || T1)(iv)
SC transmits {CID, X, V1, T1} to the serverAt this phase, the user needs to recreate theR value by providing correct his/her biometrics.


### 3.5.3. Authentication Phase

When receiving the login message from the user,S verifies the login message as follows:(i)
S checks if |Tc − T1| ≤ δT, where Tc is receiving time. If this holds, S retrieves ID by computing Decs (CID) with the private key s.(ii)
Then,S computes AID = h (ID || s) and checks if V1 = h (ID || X || CID || T1). If this holds, S generates random values a′ and v.(iii)
Then,S computes CID′ = Encs (ID || a′), SK = h (Tv (X)), Y = Tv (AID), and V2 = h (CID′ || Y || SK || T2), where T2 is current time.(iv)
Then,S sends {CID′, Y, V2, T2} to the user.(v)
Once receiving messages from the server,SC checks T2 and calculates SK = h (Tu (Y)).(vi)
Then,SC checks if V2 = h (CID′ || Y || SK || T2). If this holds, SC replaces CID with CID′, computes V3 = h (SK || T3), and sends {V3, T3} to S.(vii)
Once receiving messages, the server checksT3 and verifies if V3 = h (SK || T3). If this holds, the user and server successfully authenticate to each other and accept SK as a session key.This scheme is completely dependent on random valuesu and v, and this is vulnerable to known session-specific temporary information attack. Figure 10 describes all steps in this phase.Figure 10
User authentication phase of Han et al.’s scheme.


### 3.5.4. Password-Update Phase

This phase is performed whenU changes PW into PWnew without interacting with S:(i)
U inserts his/her smart card into the terminal and inputs ID, PW, and B′. SC executes Rep (B′, P) = R and computes AID = V ⊕ h (ID || PW || R).(ii)
SC checks if h (AID) = K. If this holds, SC allows the change request.(iii)
U inputs PWnew and Bnew, and then SC computes <Rnew, Pnew> = Gen (Bnew) and Vnew = V ⊕ h (ID || PW || R) ⊕ h (ID || PWnew || Rnew).(iv)
Finally,SC replaces V by Vnew.


### 3.5.5. The Scheme’s Cryptanalysis

If another session leaks the random valuev, the adversary can exploit to reattack the user and know previous messages transmitted between the user and server. For example, the adversary Ua obtains {CID, X, V1, T1}, {CID′, Y, V2, T2}, and {V3, T3} with the random value v leaked, and Ua can launch an impersonation attack as follows:(i)
IfU sends the new login message {CID′, X′, V1′, T1′} to S, Ua can block this message.(ii)
Ua generates random CIDʺ.(iii)
Then,Ua computes SK′ = h (Tv (X′)) and V2′ = h (CIDʺ || Y || SK′ || T2′), where T2′ is current time and Y is previous value of U and S.(iv)
Then,Ua sends {CIDʺ, Y, V2′, T2′} to U.(v)
Once receiving the message fromUa, U checks T2′. If this holds, U computes SK′ = h (Tu′ (Y)), where u′ is a random value chosen by U.(vi)
U checks if V2′ = h (CIDʺ || Y || SK′ ||T2′). We see this holds and U sends V3′ = h (SK′ || T3′) to Ua.Clearly, the adversary can reuse this random valuev to reattack the user many times. The main reason is that CID is what the user does not know.


## 3.5.1. Registration Phase

In the registration phase, we see that their scheme generates <R, P> from the user’s biometrics with the fuzzy extractor. Furthermore, the user’s dynamic identity is made by the server by using the encryption scheme. Figure 9 describes all steps in this phase.Figure 9
User registration phase of Han et al.’s scheme.Firstly, the user choosesID, PW, biometrics B, and random value r. Then, the fuzzy extractor generates <R, P> from B and the user computes A = h (PW || R) ⊕ r. Next, the user sends {ID, A}. Once receiving the user’s messages, the server computes AID = h (ID || s), K = h (AID), V′ = AID ⊕ A, and CID = Encs (ID || a), where a is chosen randomly by and s is private key of the server. Then, the server sends SC = {K, V′, CID, h (.)} to the user. Once receiving the server’s message, the user computes V = V′ ⊕ A ⊕ h (ID || PW || R) and replaces V′ by V. The user inserts P in SC and keeps it secret.


## 3.5.2. Login Phase

The user sends insertsSC into the terminal and enters ID, PW, and B′ similar to B. Then, SC performs as follows:(i)
SC performs Rep (B′, P) to generate R and computes AID = V ⊕ h (ID || PW || R)(ii)
SC checks if K = h (AID). If this holds, go to next step(iii)
SC generates a nonce u and computes X = Tu (AID) and V1 = h (ID || X || CID || T1)(iv)
SC transmits {CID, X, V1, T1} to the serverAt this phase, the user needs to recreate theR value by providing correct his/her biometrics.


## 3.5.3. Authentication Phase

When receiving the login message from the user,S verifies the login message as follows:(i)
S checks if |Tc − T1| ≤ δT, where Tc is receiving time. If this holds, S retrieves ID by computing Decs (CID) with the private key s.(ii)
Then,S computes AID = h (ID || s) and checks if V1 = h (ID || X || CID || T1). If this holds, S generates random values a′ and v.(iii)
Then,S computes CID′ = Encs (ID || a′), SK = h (Tv (X)), Y = Tv (AID), and V2 = h (CID′ || Y || SK || T2), where T2 is current time.(iv)
Then,S sends {CID′, Y, V2, T2} to the user.(v)
Once receiving messages from the server,SC checks T2 and calculates SK = h (Tu (Y)).(vi)
Then,SC checks if V2 = h (CID′ || Y || SK || T2). If this holds, SC replaces CID with CID′, computes V3 = h (SK || T3), and sends {V3, T3} to S.(vii)
Once receiving messages, the server checksT3 and verifies if V3 = h (SK || T3). If this holds, the user and server successfully authenticate to each other and accept SK as a session key.This scheme is completely dependent on random valuesu and v, and this is vulnerable to known session-specific temporary information attack. Figure 10 describes all steps in this phase.Figure 10
User authentication phase of Han et al.’s scheme.


## 3.5.4. Password-Update Phase

This phase is performed whenU changes PW into PWnew without interacting with S:(i)
U inserts his/her smart card into the terminal and inputs ID, PW, and B′. SC executes Rep (B′, P) = R and computes AID = V ⊕ h (ID || PW || R).(ii)
SC checks if h (AID) = K. If this holds, SC allows the change request.(iii)
U inputs PWnew and Bnew, and then SC computes <Rnew, Pnew> = Gen (Bnew) and Vnew = V ⊕ h (ID || PW || R) ⊕ h (ID || PWnew || Rnew).(iv)
Finally,SC replaces V by Vnew.


## 3.5.5. The Scheme’s Cryptanalysis

If another session leaks the random valuev, the adversary can exploit to reattack the user and know previous messages transmitted between the user and server. For example, the adversary Ua obtains {CID, X, V1, T1}, {CID′, Y, V2, T2}, and {V3, T3} with the random value v leaked, and Ua can launch an impersonation attack as follows:(i)
IfU sends the new login message {CID′, X′, V1′, T1′} to S, Ua can block this message.(ii)
Ua generates random CIDʺ.(iii)
Then,Ua computes SK′ = h (Tv (X′)) and V2′ = h (CIDʺ || Y || SK′ || T2′), where T2′ is current time and Y is previous value of U and S.(iv)
Then,Ua sends {CIDʺ, Y, V2′, T2′} to U.(v)
Once receiving the message fromUa, U checks T2′. If this holds, U computes SK′ = h (Tu′ (Y)), where u′ is a random value chosen by U.(vi)
U checks if V2′ = h (CIDʺ || Y || SK′ ||T2′). We see this holds and U sends V3′ = h (SK′ || T3′) to Ua.Clearly, the adversary can reuse this random valuev to reattack the user many times. The main reason is that CID is what the user does not know.


## 3.6. Proposed Scheme

InSection 3, we review some typical schemes using many approaches such as Chebyshev polynomial or elliptic curve cryptosystem in various environments. Although these schemes are well designed with some interesting primitives, such as fuzzy extractor or symmetric encryption scheme, they are still vulnerable to some typical kinds of attacks, such as password-guessing or impersonation. Indeed, there are still interesting schemes [17, 20], but they are designed with three-party participation different with two-party participation of the proposed scheme. Therefore, we temporarily do not consider in this paper. Figure 11 shows our architecture of participation between registration centre (RC), servers (Sj), and users (UX), where the keys of servers and users are created by RC.Figure 11
Architecture of our proposed scheme.With this architecture in Figure11, we can deploy a RC to centralize all medical servers. Also, the users easily find the medical services suitable for them. This section presents the phases in our proposed scheme. Our scheme uses Chebyshev polynomial in multiserver environment with two-party participation, including five phases: initialization, registration (server + user), authentication, and password-update phases. Some notations used in our scheme are in Table 5.Table 5
Notations used in our scheme.
NotationsDescriptionUX, Sj, RCXth user/jth server, registration centreBXBiometrics ofUXqRCMaster key ofRCASIDjSj’s master keysjXUX’s authentication key with SjSKSession key betweenUX and SjH0 (.)Cryptographic one-way hash functionGen/RepGeneration/reproduction algorithm⊕, ||,TnXOR, concatenation, Chebyshev operation


### 3.6.1. System Initialization

RC chooses the big prime number p ∈ ℙ k-bit and a qRC. Then, RC chooses H0: {0, 1}∗ ⟶ {0, 1}k. RC publishes {T (.), H0 (.), p} and keeps qRC secret.


### 3.6.2. Server Registration Phase

In this phase,Sj provides SIDj to RC through a secure channel. RC chooses rj and computes ASIDj =  TqRC (H0 (SIDj || rj)) mod p and then returns {rj, SIDj, ASIDj, H0 (.)} to Sj. Figure 12 shows the steps in this phase.Figure 12
Proposed scheme’s server registration phase.In this phase, each serverSj has unique master key ASIDj produced by RC. RC must keep the pair <rj, SIDj> for subsequent retrieval and the user’s registration.


### 3.6.3. User Registration Phase

UX provides biometrics BX and UIDX, using Gen (BX) to generate <RX, PX>. Then, UX sends {UIDX, H0 (RX || UIDX)} to RC through a secure channel. Once receiving the messages, RC computes all submaster keys for all service providers. RC chooses rX and then computes sjX = TrX (UIDX || H0 (RX || UIDX)) mod p + TASIDj (H0 (rj + rX + UIDX)) mod p and RPWX = H0 (H0 (RX || UIDX) || rX). RC returns {s1X, s2X, …, smX, RPWX, and H0 (.), rX} to UX through a secure channel. Figure 13 shows the steps in this phase.Figure 13
Proposed scheme’s user registration phase.In this phase,RC computes sjX, which is an authentication key between UX and Sj (1 ≤ j ≤ m, where m is a number of Sj). Similar to [19], our scheme uses the fuzzy extractor to deal with the problem of output-sensitive due to inputs’ perturbations. Additionally, RC must notify Sj about UX by sending pair <rX, UIDX> for the subsequent user’s authentication.


### 3.6.4. Authentication Phase

WhenUX logins to Sj, UX provides the smart card with UIDX and BX′ at the terminal. Then, the smart card reproduces RX = Rep (PX, BX′) and checks if RPWX = H0 (H0 (RX || UIDX) || rX); if this does not hold, the session is terminated; otherwise, the smart card chooses rU and computes TASIDj (H0 (rj + rX + UIDX)) mod p =  sjX − TrX (UIDX || H0 (RX || UIDX)) mod p, RU =  TrU (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p, R′ = RU + TASIDj (H0 (rj + rX + UIDX)) mod p, CID = UIDX ⊕ H0 (RU), and MU = H0 (RU, TASIDj (H0 (rj + rX + UIDX)) mod p). Then, the smart card sends {CID, R′, MU, rX} to Sj. On receiving the message, Sj computes TASIDj (H0 (rj + rX + UIDX)) mod p, RU′ = R′ − TASIDj (H0 (rj + rX + UIDX)) mod p, and UIDX = CID ⊕ H0 (RU′) and checks UIDX; then, Sj checks if MU = H0 (RU′, TASIDj (H0 (rj + rX + UIDX)) mod p), and if this does not hold, Sj terminates the session; otherwise, Sj chooses rS and computes RS =  TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p, S′ = RS + RU′, SK = H0 (TrS (RU′) mod p), and MS = H0 (RS, TASIDj (H0 (rj + rX + UIDX)) mod p). Sj sends {MS, S′} to UX. On receiving the message, UX computes RS′ = S′ − RU and SK = H0 (TrU (RS′) mod p) and checks if MS = H0 (RS′, TASIDj (H0 (rj + rX + UIDX)) mod p); if this does not hold, UX terminates the session; otherwise, UX believes Sj is valid and sends MUS = H0 (RS′, TrU (RS′) mod p) to Sj. On receiving the message, Sj checks if MUS = H0 (RS, TrS (RU′) mod p); if this does not hold, Sj terminates the session; otherwise, Sj believes UX is valid. Figure 14 shows the steps in this phase.Figure 14
Proposed scheme’s authentication phase.


### 3.6.5. Password-Update Phase

WhenUX changes BX, UX provides his/her smart card with UIDX and similar BX′ at the terminal. Then, the smart card checks if RPWX = H0 (H0 (RX || UIDX) || rX), where RX = Rep (PX, BX′). If this does not hold, the smart card terminates the session; otherwise, UX inputs Bnew and computes RPWnew = H0 (H0 (Rnew || UIDX) || rX), where <Rnew, Pnew> = Gen (Bnew), Then, the smart card updates RPWX = RPWnew and PX = Pnew. Finally, the smart card updates all authentication keys sjX = sjX − TrX (UIDX || H0 (RX || UIDX)) + TrX (UIDX || H0 (Rnew || UIDX)), ∀j.


## 3.6.1. System Initialization

RC chooses the big prime number p ∈ ℙ k-bit and a qRC. Then, RC chooses H0: {0, 1}∗ ⟶ {0, 1}k. RC publishes {T (.), H0 (.), p} and keeps qRC secret.


## 3.6.2. Server Registration Phase

In this phase,Sj provides SIDj to RC through a secure channel. RC chooses rj and computes ASIDj =  TqRC (H0 (SIDj || rj)) mod p and then returns {rj, SIDj, ASIDj, H0 (.)} to Sj. Figure 12 shows the steps in this phase.Figure 12
Proposed scheme’s server registration phase.In this phase, each serverSj has unique master key ASIDj produced by RC. RC must keep the pair <rj, SIDj> for subsequent retrieval and the user’s registration.


## 3.6.3. User Registration Phase

UX provides biometrics BX and UIDX, using Gen (BX) to generate <RX, PX>. Then, UX sends {UIDX, H0 (RX || UIDX)} to RC through a secure channel. Once receiving the messages, RC computes all submaster keys for all service providers. RC chooses rX and then computes sjX = TrX (UIDX || H0 (RX || UIDX)) mod p + TASIDj (H0 (rj + rX + UIDX)) mod p and RPWX = H0 (H0 (RX || UIDX) || rX). RC returns {s1X, s2X, …, smX, RPWX, and H0 (.), rX} to UX through a secure channel. Figure 13 shows the steps in this phase.Figure 13
Proposed scheme’s user registration phase.In this phase,RC computes sjX, which is an authentication key between UX and Sj (1 ≤ j ≤ m, where m is a number of Sj). Similar to [19], our scheme uses the fuzzy extractor to deal with the problem of output-sensitive due to inputs’ perturbations. Additionally, RC must notify Sj about UX by sending pair <rX, UIDX> for the subsequent user’s authentication.


## 3.6.4. Authentication Phase

WhenUX logins to Sj, UX provides the smart card with UIDX and BX′ at the terminal. Then, the smart card reproduces RX = Rep (PX, BX′) and checks if RPWX = H0 (H0 (RX || UIDX) || rX); if this does not hold, the session is terminated; otherwise, the smart card chooses rU and computes TASIDj (H0 (rj + rX + UIDX)) mod p =  sjX − TrX (UIDX || H0 (RX || UIDX)) mod p, RU =  TrU (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p, R′ = RU + TASIDj (H0 (rj + rX + UIDX)) mod p, CID = UIDX ⊕ H0 (RU), and MU = H0 (RU, TASIDj (H0 (rj + rX + UIDX)) mod p). Then, the smart card sends {CID, R′, MU, rX} to Sj. On receiving the message, Sj computes TASIDj (H0 (rj + rX + UIDX)) mod p, RU′ = R′ − TASIDj (H0 (rj + rX + UIDX)) mod p, and UIDX = CID ⊕ H0 (RU′) and checks UIDX; then, Sj checks if MU = H0 (RU′, TASIDj (H0 (rj + rX + UIDX)) mod p), and if this does not hold, Sj terminates the session; otherwise, Sj chooses rS and computes RS =  TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p, S′ = RS + RU′, SK = H0 (TrS (RU′) mod p), and MS = H0 (RS, TASIDj (H0 (rj + rX + UIDX)) mod p). Sj sends {MS, S′} to UX. On receiving the message, UX computes RS′ = S′ − RU and SK = H0 (TrU (RS′) mod p) and checks if MS = H0 (RS′, TASIDj (H0 (rj + rX + UIDX)) mod p); if this does not hold, UX terminates the session; otherwise, UX believes Sj is valid and sends MUS = H0 (RS′, TrU (RS′) mod p) to Sj. On receiving the message, Sj checks if MUS = H0 (RS, TrS (RU′) mod p); if this does not hold, Sj terminates the session; otherwise, Sj believes UX is valid. Figure 14 shows the steps in this phase.Figure 14
Proposed scheme’s authentication phase.


## 3.6.5. Password-Update Phase

WhenUX changes BX, UX provides his/her smart card with UIDX and similar BX′ at the terminal. Then, the smart card checks if RPWX = H0 (H0 (RX || UIDX) || rX), where RX = Rep (PX, BX′). If this does not hold, the smart card terminates the session; otherwise, UX inputs Bnew and computes RPWnew = H0 (H0 (Rnew || UIDX) || rX), where <Rnew, Pnew> = Gen (Bnew), Then, the smart card updates RPWX = RPWnew and PX = Pnew. Finally, the smart card updates all authentication keys sjX = sjX − TrX (UIDX || H0 (RX || UIDX)) + TrX (UIDX || H0 (Rnew || UIDX)), ∀j.


## 4. Security and Efficiency Analyses

In this section, we analyse our scheme on security and efficiency aspects.


### 4.1. Correctness Analysis

Similar to previous schemes, we also prove our scheme’s correctness using BAN-logic rules [28] and goals proposed in [29]. For simplicity, we let ⊗ denote the combination using Chebyshev operation. Table 6 shows some assumptions our scheme must satisfy.Table 6
The assumptions in BAN-logic.
AssumptionA1: UX | ≡ (UX ⟷UIDX Sj) − UX believes UX can share UIDX with SjA2: UX | ≡ (UX ⟷sjX Sj) − UX believes UX can share sjX with SjA3: UX | ≡ (Sj ⇒ (UX ⟷SK Sj)) − UX believes Sj controls the sharing of the session key between UX and SjA4: Sj | ≡ (UX ⇒ (UX ⟷UIDX Sj)) − Sj believes UX controls the sharing of UIDX between UX and SjA5: Sj | ≡ (UX ⇒ (UX ⟷SK Sj)) − Sj believes UX controls the sharing of the session key between UX and SjA6: Sj | ≡ (Sj ⟷sjX UX) − Sj believes Sj can share sjX with UXA7: UX | ≡ # (rS ⊗ sjX) − UX believes challenge messages from Sj are freshA8: Sj | ≡ # (rU ⊗ sjX) − Sj believes challenge messages from UX are freshThese assumptions stand for initial beliefs of the user and server, for example,A1 implies that users can share their identities with the server with the registration phase. Next, we will normalize all messages exchanged between the user and server.(i)
From the message {CID}, we have < UX ⟷UIDX Sj, UX ⟷sjX Sj, rU ⊗ sjX>(ii)
From the message {MU}, we have < rU ⊗ sjX, UX ⟷sjX Sj>(iii)
From the third messages {MS}, we have < rS ⊗ sjX, UX ⟷sjX Sj>(iv)
From the fourth message {MUS}, we have < UX ⟷sjX Sj, UX ⟷SK Sj>The normalization helps to clearly show information exchanged betweenUX and Sj, for example, CID containing identity, challenge information rU ⊗ sjX, and long-term key sjX. Next, we demonstrate how our scheme satisfies seven lemmas reorganized from [29].Lemma 1.
IfSj believes the authentication key (the long-term key) is successfully shared with UX and UX’s messages encrypted with this key are fresh, Sj will believe that UX believes UX’s UIDX is successfully shared with Sj:(3)Sj|≡Sj⟷sjXUX,Sj|≡#rU⊗sjXSj≡UX≡UX⟷UIDXSj.Proof.
WithA6 and CID, we apply the message-meaning rule to have Sj|≡Sj⟷sjXUX,Sj⊲CID/Sj≡UX∼CID. With A8, we apply the freshness rule to have Sj|≡#rU⊗sjX/Sj|≡#CID. Next, we apply the nonce-verification rule to have Sj≡UX∼CID,Sj|≡#CID/Sj≡UX≡CID. Finally, we apply the believe rule to have Sj≡UX≡CID/Sj≡UX≡UX⟷UIDXSj. So, with A6 and A8, we successfully demonstrate how our scheme satisfies Lemma 1.Lemma 2.
IfSj believes UX also believes UX’s UIDX is successfully shared with each other and UX totally controls this UIDX’s sharing, Sj also believes UX’s UIDX is successfully shared with each other:(4)Sj|≡UX|≡UX⟷UIDXSj,Sj|≡UX⟹UX⟷UIDXSjSj|≡UX⟷UIDXSj.Proof.
With Lemma1 and A4, we apply the jurisdiction rule to have Sj|≡UX|≡UX⟷UIDXSj,Sj|≡UX⇒UX⟷UIDXSj/Sj|≡UX⟷UIDXSj. So, with Lemma 1 and A4, we prove how our scheme satisfies Lemma 2.Lemma 3.
IfUX believes sjX is successfully shared with Sj and Sj’s messages encrypted with sjX are fresh, UX will believe Sj also believes UX’s UIDX is successfully shared with each other.Proof.
WithA2 and MS, we apply the jurisdiction rule to have UX|≡UX⟷sjXSj,UX⊲MS/UX≡Sj∼MS. Then, with A7, we apply the freshness rule to have UX|≡#rS⊗sjX,UX|≡Sj|∼MS/UX|≡#MS. So, combining two results with the nonce-verification rule, we have UX|≡Sj∼MS,UX≡#MS/UX|≡Sj|≡MS. Finally, we apply the believe rule to have UX|≡Sj|≡MS/UX|≡Sj|≡UX⟷UIDXSj. So, with A2 and A7, we successfully prove how our scheme satisfies Lemma 3. In short, with three lemmas, we can say that both Sj and UX believe and successfully share their identities with each other. Next, we need to prove the similar thing for the session key.Lemma 4.
IfUX believes that sjX is successfully shared with Sj and Sj’s messages encrypted with sjX are fresh, UX will believe Sj also believes the session key SK is successfully shared with each other:(5)UX|≡UX⟷sjXSj,UX|≡#rS⊗sjXUX|≡Sj|≡Sj⟷SKUX.Proof.
WithMUS and A2, we apply the message-meaning rule to have UX|≡UX⟷sjXSj,UX⊲MUS/UX|≡Sj|∼MUS. With A7 and MUS, we apply the freshness rule to have UX|≡#rS⊗sjX,UX⊲MUS/UX|≡#MUS. Next, we use the believe rule to have UX|≡Sj|∼MUS,UX|≡#MUS/UX|≡Sj|≡MUS. Again, we apply the believe rule to have UX|≡Sj|≡MUS/UX|≡Sj|≡Sj⟷SKUX. So, with A2 and A7, we successfully prove how our scheme satisfies Lemma 4.Lemma 5.
IfUX believes Sj totally controls SK’s sharing and Sj also believes SK is successfully shared with UX, UX will believe SK’s sharing:(6)UX|≡SjUX⟷SKSj,UX|≡Sj|≡Sj⟷SKUXUX|≡UX⟷SKSj.Proof.
WithA3 and Lemma 4, we apply the jurisdiction rule to have UX|≡SjUX⟷SKSj,UX|≡Sj|≡Sj⟷SKUX/UX|≡UX⟷SKSj. So, with A3 and Lemma 4, we successfully prove how our scheme satisfies Lemma 5.Lemma 6.
IfSj believes sjX is successfully shared with UX and the UX’s messages encrypted with sjX are fresh, Sj will believe UX also believes SK’s sharing:(7)UX|≡Sj⟷sjXUX,Sj|≡#rU⊗sjXSj|≡UX|≡UX⟷SKSj.Proof.
WithA6 and MUS, we apply the message-meaning rule to have Sj|≡Sj⟷sjXUX,Sj⊲MUS/Sj|≡UX|∼MUS. With A8 and MUS, we apply the freshness rule to have Sj|≡#rU⊗sjX,Sj⊲MUS/Sj|≡#MUS. With two results and the nonce-verification rule, we have Sj|≡UX|∼MUS,Sj|≡#MUS/Sj|≡UX|≡MUS. Finally, with A6 and the believe rule, we have Sj|≡Sj⟷sjXUX,Sj|≡UX|≡MUS/Sj|≡UX|≡UX⟷SKSj. So, with A6 and A8, we successfully prove how our scheme satisfies Lemma 6.Lemma 7.
IfSj believes UX totally controls SK’s sharing, Sj believes SK is successfully shared with UX:(8)UX|≡SjUX⟷SKSj,UX|≡Sj|≡Sj⟷SKUXUX|≡UX⟷SKSj.Proof.
WithSj |≡ UX|≡ MUS and A5, we apply the message-meaning rule to have Sj|≡UXUX⟷SKSj,Sj|≡UX|≡MUS/Sj|≡MUS. Finally, we apply the believe rule to have Sj|≡MUS/Sj|≡Sj⟷SKUX. So, with A5, we completely prove how our scheme satisfies Lemma 7. Finally, we can say that both Sj and UX believe the common SK in our scheme.


### 4.2. Authenticated Key Exchange Security Analysis (AKE-Security)

The adversarial model is presented in this section, and some definitions can be found in [17, 30]. At first, we use some notations standing for the instances of our scheme’s participants:(i)
RCk: the kth registration centre holding secret qRC(ii)
Sji: the ith server holding {rj, ASIDj}(iii)
UXi: the ith user holding the smart card and {UIDX, BX}(iv)
OHash: the hash oracle can be viewed as random functions(v)
sidUXiSji and sidSjiUXi: the all messages exchanged between UXi and Sji(vi)
pidUXi = Sji and pidSji = UXi: the partner identity of UXi is Sji and vice versaNext, there are some security properties:(i)
Sji and UXi are accepted if they can compute the valid session key and receive expected messages(ii)
Sji and UXi are partnered if (1) both of them are accepted, (2) pidUXi = Sji (pidSji = UXi), and (3) sidUXiSji = sidSjiUXi(iii)
UXi are fresh if (1) they are partnered, (2) no secret information of UXi is leaked before it is accepted, (3) no UXi’s session key is leaked before it is acceptedNext, there are some adversary’s capabilities. LetA be probabilistic polynomial time adversary attacking authentication scheme in AKE-security:(i)
Execution query helpsA to execute passive attacks against our scheme. We let qE be the sum of the number of execute queries and sidUXiSji ← Execute (UXi, Sji) be the symbol standing for the output of this query.(ii)
Send query helpsA to actively interact with UXi or Sji. We let qS be the sum of the number of send queries and mout ← Send (Oi, min) be the symbol standing for the output and input of this query, where Oi is UXi or Sji.(iii)
Reveal query helpsA to know the session key (sk) of UXi and Sji in another session. We let qR be the sum of the number of reveal queries and ski ← Reveal (Oi) be the symbol standing for the output of this query, where Oi is UXi or Sji. Note that to perform this query, Oi must be fresh.(iv)
Corrupt query helpsA to know secret information of UXi. We let qC be the sum of the number of corrupt queries and {UIDX, BX} ← Corrupt (UXi, 1) and {smart card} ← Corrupt (UXi, 0) be the symbol standing for the output of this query. Note that A only knows the smart card or {UIDX, BX}.(v)
Hash query helpsA to query a value m and receive corresponding r. If m is not queried before, OHash returns the random number r to the adversary. Otherwise, it returns the previously generated result. We let qH be the sum of the number of hash queries and r ← Hash (OHash, m) be the symbol standing for the output of this query.Theorem 1.
Our schemeP is AKE-security against A within a time tA if A cannot guess the correct session key of another fresh Oi. Formally, let AdvPAKE (A, tA) be the A’s chance of breaking P in AKE-security within in reasonable time tA, and we need AdvPAKE (A, tA) is negligible. In summary, we need AdvPAKE (A, tA) ≤ ε (∗).


### 4.3. The Definition of Experiments

We setExpTCMDHP (B) be experiment, where the adversary B wins if it successfully breaks CMDHP-security of the Chebyshev polynomial T’s problem within a time tB, and let AdvTCMDHP (B) = Pr[ExpTCMDHP (B) = 1] be the B’s winning chance. Note that we give OHash to B.Experiment 1.
ExpTCMDHP (B).{s, r} ⟵$ {0, 1}∗, X ⟵$ [0, p − 1]M ⟵ Tr (X) mod pN ⟵ Ts (X) mod pK ⟵ Tr (Ts (X)) mod pZ ⟵ BOHash (M, N, Hash (OHash, K))ifHash (OHash, Z) = Hash (OHash, K) then return 1else return 0
Also, we setExpPAKE (A) be experiment, where the adversary A wins if it successfully breaks AKE-security of our P within a time tA, and let AdvPAKE (A) = Pr [ExpPAKE (A) = 1] be the A’s winning chance. Note that we also give OHash to A.Experiment 2.
ExpPAKE (A).b ⟵$ {0, 1}, LU ⟵ {U1, …, Un}, LS ⟵ {S1, …, Sn}Ui ⟵$ LU, Sj ⟵$ LSsidUiSj ⟵ Execute (Ui, Sj)ifb = 0 thensk ⟵$ {0, 1}∗elsesk ⟵ Reveal (Ui){b′, Z} ⟵ AOHash (LU, LS, sk)ifb′ = bthen return 1else return 0
Note that ifb = b′ = 1, then we must have Hash (OHash, Z) = sk.
The proof of Theorem1.
Now we assume thatB wants to win in B’s experiment, and it runs A as the procedure. Also, A wants to win in A’s experiment and B must simulate the A’s environment as the following algorithm Let l be the security length, for example, the size of the prime p and hash function’s output. If A correctly guesses b′, then we must consider some following cases (Algorithm 1):(i)
A issues qH queries to OHash, and A has successful probability ≈ qH2/2l due to the birthday paradox.(ii)
A chooses qE pairs to execute and have all messages exchanged between them. Furthermore, A issues qC queries to some users to get the smart card or {UID, B}. So, A’s successful probability of correctly guessing random values r or s is ≈ qE×qC/p.(iii)
If A issuesqS′ queries to oracles simulated by B, there will be at least one Send query that helps A compute the session key. So, we have AdvTCMDHP (B) ≥ AdvPAKEA/qS′. When A issues the remaining qS−qS′ queries to normal Oi, A’s successful probability of correctly guessing is ≈ qS−qS′/p.
Finally, we haveAdvPAKE (A) ≤ qH2/2l + qE×qC/p + AdvTCMDHP (B) × qS′ + qS−qS′/p. Clearly, the right-hand side of this inequality is negligible, so we complete the proof.Algorithm 1:BTCMDHP (M, N, sk ⟵ Hash (OHash, K)).
SetLU ⟵ {U1, …, Un}, LS ⟵ {S1, …, Sn}RunAOHash (LU, LS, sk)ifA chooses qE pairs to execute thenB does & returns all sid to Aend ififA asks qR queries to fresh Oi in LU and LSthenifOi is normal in LU and LSthenB lets Oi return session-key to A as usualelseB returns random string to Aend ifend ififA asks qS queries to Oi in LU and LSthenifOi is normal in LU and LSthenB lets Oi & A exchange mout as usualelseB simulates & gives to A mout including M and Nend ifend ififA asks qC queries to some UXi in LUthenB returns smart-card or {UID, B} of UXi to AelseB returns random smart-card or {UID′, B′} to Aend ififA asks qH queries to OHashthenB lets OHash do with Aend ifUntilA stops and outputs {b′, Z}B returns (Hash (OHash, Z) = sk)


### 4.4. Security Analysis

In this section, we will analyse our scheme in some popular kinds of attacks. The comparison of the security feature with previous works is shown in Table7. Before coming into this section, we want to discuss the privileged insider attacks. In our scheme, we use biometrics rather than the password. Therefore, the privileged insider attacker cannot find it and exploit into different servers. Furthermore, all servers in our scheme use different long-term keys provided from RC, so the attacker cannot use the users’ information in another server to exploit in others. It can be said that it is hard to launch a privileged insider attack in our scheme.Table 7
The security feature comparison among the schemes.
SchemesLi [11]Qu [12]Amin [13]Jangirala [18]Han [19]OursPassword-guessing✗✓✓✓✓✓User’s anonymity✓✓✓✓✓✓Two-factor✗✓✓✗✓✓Known session-specific temporary information✗✓✓✗✗✓Session-key perfect forward✗✓✗✗✓✓User impersonation✗✗✓✗✗✓Server impersonation✓✓✓✓✓✓Man-in-the-middle✓✞1✞1✞1✞1✓Replay✓✓✓✓✓✓Parallel session✞1✞1✞1✞1✞1✓1Untouched.


### 4.5. Password-Guessing Attack

In this kind of attack, the adversary can guess the user’s password by exploiting leaking information from the smart card. The adversary will haveRPWX = H0 (H0 (RX || UIDX) || rX). Because RU is produced by the user’s biometrics, it is hard to guess. Clearly, the adversary cannot use the dictionary method to find biometrics and our scheme can resist this kind of attack.


### 4.6. User’s Anonymity

In this kind of attack, the adversary eavesdrops {rX, CID, MU, R′}, {S′, MS}, and {MUS} from UX. All messages are different at each login session because we use random values. So, the adversary cannot trace who is online. In other words, our scheme resists this attack.


### 4.7. Two-Factor Attack

AlthoughUX loses his/her smart card, the adversary cannot exploit because of needing BX to pass RPWX = H0 (H0 (RX || UIDX) || rX). Even if UX’s biometrics is fake, the adversary cannot exploit all information in the login message because he/she does not other supporting values. Clearly, our scheme resists this attack.


### 4.8. Known Session-Specific Information Attack

WhenrU and rS are leaked, the adversary cannot compute the session key (SK). He needs TrU (TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p) mod p to compute the SK. If he does not have the smart card’s information, all important keys cannot be successfully computed. Clearly, our scheme can resist this kind of attack.


### 4.9. Session-Key Perfect Forward Secrecy

If all important keys are leaked, the adversary cannot compute previous transactions betweenUX and Sj. With ASIDj and all messages UX sent to Sj, the adversary extracts RU = R′ − TASIDj (H0 (rj + rX + UIDX)) mod p and RS = S′ − RU. Finally, the adversary cannot compute TrU (TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p) mod p because of facing CMDHP. Clearly, our scheme can resist this kind of attack.


### 4.10. User Impersonation Attack

To impersonate as a valid user, the adversary needsRS = TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p. To have RS, he/she needs UX’s RU = TrU (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p. Furthermore, the adversary must resend the session key to Sj. Therefore, he/she not only finds RU but also knows rU to impersonate as a valid user. Clearly, our scheme can resist this kind of attack.


### 4.11. Server Impersonation Attack

To impersonate as a valid server, the adversary needsRU = TrU (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p. So, he/she also needs ASIDj to compute RU. We see this is impossible because Sj keeps ASIDj secret. Clearly, our scheme can resist this kind of attack.


### 4.12. Man-in-the-Middle Attack

In this kind of attack, the adversary can eavesdrop all messages exchanged betweenUX and Sj and then edits the parameters in these packages. For example, the adversary can insert his/her own session key with randomly chosen rU and rS. However, this is impossible because UX’s random value combined with ASIDj. Therefore, the adversary needs to compute this key to achieve the goal, but this is impossible because this is UX’s secret key. Clearly, our scheme resists this attack.


### 4.13. Replay Attack

In this kind of attack, the adversary can eavesdrop all messages exchanged betweenUX and Sj. At any time, he/she can replay to cheat UX or Sj. We consider if the adversary resends {CID, R′, MU, rX} to Sj, and this is the valid message. However, Sj requests UX respond {MUS} for confirmation, and the adversary cannot compute MUS. Furthermore, the adversary can resend Sj’s {MS, S′} to cheat UX, but this is impossible because UX and Sj use random values. So {MS, S′} is only valid if UX rechooses random values. Clearly, our scheme can resist this kind of attack.


### 4.14. Parallel Session Attack

In this kind of attack, the adversary will use {MS, S′} to create {CID, R′, MU, rX}, and cheat Sj. As aforementioned in replay and impersonation attacks, the adversary cannot achieve the goal because he/she needs key UX’s TASIDj (H0 (rj + rX + UIDX)) mod p and Sj’s ASIDj. Clearly, our scheme resists this attack.


### 4.15. Efficiency Analysis

Now, this section presents the cost of our scheme compared with previous schemes. Before coming to detail comparison, we will unify some notations and the bit size of some cryptographic primitives. If the scheme does not mention, we assume as follows: the sizes of identity, password, biometrics, timestamp, and random values are 128 bits. The size of hash function’s output and encryption scheme is 128 bits. The prime number in modular is 1024 bits (≈309 decimal digits) and 233 bits (≈70 decimal digits) in ECC. We let the notations denote the time to compute some cryptographic operations:(i)
tH: time to compute hash function (≈0.0004 ms)(ii)
tPA: time to compute point addition (≈0.36 ms)(iii)
tPM: time to compute point multiplication (≈12.4 ms)(iv)
tE/D: time to encrypt/decrypt (≈0.09 ms)(v)
tT: time to compute Chebyshev polynomial (≈127 ms)All the amount of time is results we measure on the real Android device with the Bouncy Castle library. Next, we evaluate the computation quantity of previous schemes and ours in Table8. In Li et al.’s scheme [11], registration needs 4 × tH and authentication needs 15 × tH. In Qu and Tan’s scheme [12], registration needs 4 × tH, 2 × tPM and authentication needs 11 × tH, 5 × tPM and 5 × tPA. In Amin and Biswas’s scheme [13], registration needs 5 × tH, 1 × tE/D and authentication needs 10 × tH, 5 × tPM, 2 × tPA and 1 × tE/D. In Jangirala et al.’s scheme [18], registration needs 5 × tH, 1 × tE/D and authentication needs 10 × tH, 5 × tPM, 2 × tPA and 1 × tE/D. In Han et al.’s scheme [19], registration needs 5 × tH, 1 × tE/D and authentication needs 10 × tH, 5 × tPM, 2 × tPA and 1 × tE/D. In the proposed scheme, registration needs 2 × tT, 4 × tH and authentication needs 11 × tH, 6 × tT.Table 8
The comparison of computation cost.
SchemesAuthentication/Registration phasesLi [11]15 ×tH4 ×tHQu [12]11 ×tH, 5 × tPM, 5 × tPA4 ×tH + 2 × tPMAmin [13]10 ×tH, 5 × tPM, 2 × tPA, 1 × tE/D5 ×tH, 1 × tE/DJangirala [18]21 ×tH6 ×tHHan [19]11 ×tH, 2 × tE/D, 4 × tT4 ×tH, 1 × tE/DOurs11 ×tH, 6 × tT4 ×tH, 2 × tTNext, we evaluate the store and authentication costs of previous schemes and ours in Table9. In Li et al.’s scheme [11], the user stores {Ci, Di, Ei, h (.), h (y), b} with 640 bits. And the authentication in this scheme needs {Pij, CIDi, M1, M2}, {M3, M4}, and {M5} with 896 bits. In Qu and Tan’s scheme [12], the user stores {AIDU, BIDU, bU} with 1618 bits. And the authentication in this scheme needs {CIDU, DIDU, EIDU, R}, {T, HS}, and {HRS} with 3702 bits. In Amin and Biswas’s scheme [13], the user needs {Fi, Ai, Bi, CIDi, h (.), H (.)} with 2304 bits. And authentication in this scheme needs {C2, C4, CIDi}, {Li, G1, CIDi′}, and {Zi} with 4818 bits. In Jangirala et al.’s scheme [18], the user needs {Ci, Di, Ei, h (y), h (.)} with 768 bits. And authentication in this scheme needs {Pij, CIDi, M1, M2}, {M3, M4}, and {M5} with 896 bits. In Han et al.’s scheme [19], the user needs {P, K, V, CID, h (.)} with 640 bits. And authentication in this scheme needs {CID, X, V1, T1}, {CID′, Y, T2, V2}, and {V3, T3} with 3072 bits. In our proposed scheme, the user stores {s1X, s2X, …, smX, RPWX, H0 (.), rX}, but we assume that the smart card stores only one siX for convenient comparison with other schemes in single-server environment, so the cost is 722 bits. And authentication in our scheme needs {CID, R′, MU, rX}, {MS, S′}, and {MUS} with 2688 bits.Table 9
The comparison of storage authentication cost.
SchemesStorage cost (bits)Authentication cost (bits)Li [11]640896Qu [12]16183702Amin [13]23044818Jangirala [18]768896Han [19]6403072Ours7222688


## 4.1. Correctness Analysis

Similar to previous schemes, we also prove our scheme’s correctness using BAN-logic rules [28] and goals proposed in [29]. For simplicity, we let ⊗ denote the combination using Chebyshev operation. Table 6 shows some assumptions our scheme must satisfy.Table 6
The assumptions in BAN-logic.
AssumptionA1: UX | ≡ (UX ⟷UIDX Sj) − UX believes UX can share UIDX with SjA2: UX | ≡ (UX ⟷sjX Sj) − UX believes UX can share sjX with SjA3: UX | ≡ (Sj ⇒ (UX ⟷SK Sj)) − UX believes Sj controls the sharing of the session key between UX and SjA4: Sj | ≡ (UX ⇒ (UX ⟷UIDX Sj)) − Sj believes UX controls the sharing of UIDX between UX and SjA5: Sj | ≡ (UX ⇒ (UX ⟷SK Sj)) − Sj believes UX controls the sharing of the session key between UX and SjA6: Sj | ≡ (Sj ⟷sjX UX) − Sj believes Sj can share sjX with UXA7: UX | ≡ # (rS ⊗ sjX) − UX believes challenge messages from Sj are freshA8: Sj | ≡ # (rU ⊗ sjX) − Sj believes challenge messages from UX are freshThese assumptions stand for initial beliefs of the user and server, for example,A1 implies that users can share their identities with the server with the registration phase. Next, we will normalize all messages exchanged between the user and server.(i)
From the message {CID}, we have < UX ⟷UIDX Sj, UX ⟷sjX Sj, rU ⊗ sjX>(ii)
From the message {MU}, we have < rU ⊗ sjX, UX ⟷sjX Sj>(iii)
From the third messages {MS}, we have < rS ⊗ sjX, UX ⟷sjX Sj>(iv)
From the fourth message {MUS}, we have < UX ⟷sjX Sj, UX ⟷SK Sj>The normalization helps to clearly show information exchanged betweenUX and Sj, for example, CID containing identity, challenge information rU ⊗ sjX, and long-term key sjX. Next, we demonstrate how our scheme satisfies seven lemmas reorganized from [29].Lemma 1.
IfSj believes the authentication key (the long-term key) is successfully shared with UX and UX’s messages encrypted with this key are fresh, Sj will believe that UX believes UX’s UIDX is successfully shared with Sj:(3)Sj|≡Sj⟷sjXUX,Sj|≡#rU⊗sjXSj≡UX≡UX⟷UIDXSj.Proof.
WithA6 and CID, we apply the message-meaning rule to have Sj|≡Sj⟷sjXUX,Sj⊲CID/Sj≡UX∼CID. With A8, we apply the freshness rule to have Sj|≡#rU⊗sjX/Sj|≡#CID. Next, we apply the nonce-verification rule to have Sj≡UX∼CID,Sj|≡#CID/Sj≡UX≡CID. Finally, we apply the believe rule to have Sj≡UX≡CID/Sj≡UX≡UX⟷UIDXSj. So, with A6 and A8, we successfully demonstrate how our scheme satisfies Lemma 1.Lemma 2.
IfSj believes UX also believes UX’s UIDX is successfully shared with each other and UX totally controls this UIDX’s sharing, Sj also believes UX’s UIDX is successfully shared with each other:(4)Sj|≡UX|≡UX⟷UIDXSj,Sj|≡UX⟹UX⟷UIDXSjSj|≡UX⟷UIDXSj.Proof.
With Lemma1 and A4, we apply the jurisdiction rule to have Sj|≡UX|≡UX⟷UIDXSj,Sj|≡UX⇒UX⟷UIDXSj/Sj|≡UX⟷UIDXSj. So, with Lemma 1 and A4, we prove how our scheme satisfies Lemma 2.Lemma 3.
IfUX believes sjX is successfully shared with Sj and Sj’s messages encrypted with sjX are fresh, UX will believe Sj also believes UX’s UIDX is successfully shared with each other.Proof.
WithA2 and MS, we apply the jurisdiction rule to have UX|≡UX⟷sjXSj,UX⊲MS/UX≡Sj∼MS. Then, with A7, we apply the freshness rule to have UX|≡#rS⊗sjX,UX|≡Sj|∼MS/UX|≡#MS. So, combining two results with the nonce-verification rule, we have UX|≡Sj∼MS,UX≡#MS/UX|≡Sj|≡MS. Finally, we apply the believe rule to have UX|≡Sj|≡MS/UX|≡Sj|≡UX⟷UIDXSj. So, with A2 and A7, we successfully prove how our scheme satisfies Lemma 3. In short, with three lemmas, we can say that both Sj and UX believe and successfully share their identities with each other. Next, we need to prove the similar thing for the session key.Lemma 4.
IfUX believes that sjX is successfully shared with Sj and Sj’s messages encrypted with sjX are fresh, UX will believe Sj also believes the session key SK is successfully shared with each other:(5)UX|≡UX⟷sjXSj,UX|≡#rS⊗sjXUX|≡Sj|≡Sj⟷SKUX.Proof.
WithMUS and A2, we apply the message-meaning rule to have UX|≡UX⟷sjXSj,UX⊲MUS/UX|≡Sj|∼MUS. With A7 and MUS, we apply the freshness rule to have UX|≡#rS⊗sjX,UX⊲MUS/UX|≡#MUS. Next, we use the believe rule to have UX|≡Sj|∼MUS,UX|≡#MUS/UX|≡Sj|≡MUS. Again, we apply the believe rule to have UX|≡Sj|≡MUS/UX|≡Sj|≡Sj⟷SKUX. So, with A2 and A7, we successfully prove how our scheme satisfies Lemma 4.Lemma 5.
IfUX believes Sj totally controls SK’s sharing and Sj also believes SK is successfully shared with UX, UX will believe SK’s sharing:(6)UX|≡SjUX⟷SKSj,UX|≡Sj|≡Sj⟷SKUXUX|≡UX⟷SKSj.Proof.
WithA3 and Lemma 4, we apply the jurisdiction rule to have UX|≡SjUX⟷SKSj,UX|≡Sj|≡Sj⟷SKUX/UX|≡UX⟷SKSj. So, with A3 and Lemma 4, we successfully prove how our scheme satisfies Lemma 5.Lemma 6.
IfSj believes sjX is successfully shared with UX and the UX’s messages encrypted with sjX are fresh, Sj will believe UX also believes SK’s sharing:(7)UX|≡Sj⟷sjXUX,Sj|≡#rU⊗sjXSj|≡UX|≡UX⟷SKSj.Proof.
WithA6 and MUS, we apply the message-meaning rule to have Sj|≡Sj⟷sjXUX,Sj⊲MUS/Sj|≡UX|∼MUS. With A8 and MUS, we apply the freshness rule to have Sj|≡#rU⊗sjX,Sj⊲MUS/Sj|≡#MUS. With two results and the nonce-verification rule, we have Sj|≡UX|∼MUS,Sj|≡#MUS/Sj|≡UX|≡MUS. Finally, with A6 and the believe rule, we have Sj|≡Sj⟷sjXUX,Sj|≡UX|≡MUS/Sj|≡UX|≡UX⟷SKSj. So, with A6 and A8, we successfully prove how our scheme satisfies Lemma 6.Lemma 7.
IfSj believes UX totally controls SK’s sharing, Sj believes SK is successfully shared with UX:(8)UX|≡SjUX⟷SKSj,UX|≡Sj|≡Sj⟷SKUXUX|≡UX⟷SKSj.Proof.
WithSj |≡ UX|≡ MUS and A5, we apply the message-meaning rule to have Sj|≡UXUX⟷SKSj,Sj|≡UX|≡MUS/Sj|≡MUS. Finally, we apply the believe rule to have Sj|≡MUS/Sj|≡Sj⟷SKUX. So, with A5, we completely prove how our scheme satisfies Lemma 7. Finally, we can say that both Sj and UX believe the common SK in our scheme.


## 4.2. Authenticated Key Exchange Security Analysis (AKE-Security)

The adversarial model is presented in this section, and some definitions can be found in [17, 30]. At first, we use some notations standing for the instances of our scheme’s participants:(i)
RCk: the kth registration centre holding secret qRC(ii)
Sji: the ith server holding {rj, ASIDj}(iii)
UXi: the ith user holding the smart card and {UIDX, BX}(iv)
OHash: the hash oracle can be viewed as random functions(v)
sidUXiSji and sidSjiUXi: the all messages exchanged between UXi and Sji(vi)
pidUXi = Sji and pidSji = UXi: the partner identity of UXi is Sji and vice versaNext, there are some security properties:(i)
Sji and UXi are accepted if they can compute the valid session key and receive expected messages(ii)
Sji and UXi are partnered if (1) both of them are accepted, (2) pidUXi = Sji (pidSji = UXi), and (3) sidUXiSji = sidSjiUXi(iii)
UXi are fresh if (1) they are partnered, (2) no secret information of UXi is leaked before it is accepted, (3) no UXi’s session key is leaked before it is acceptedNext, there are some adversary’s capabilities. LetA be probabilistic polynomial time adversary attacking authentication scheme in AKE-security:(i)
Execution query helpsA to execute passive attacks against our scheme. We let qE be the sum of the number of execute queries and sidUXiSji ← Execute (UXi, Sji) be the symbol standing for the output of this query.(ii)
Send query helpsA to actively interact with UXi or Sji. We let qS be the sum of the number of send queries and mout ← Send (Oi, min) be the symbol standing for the output and input of this query, where Oi is UXi or Sji.(iii)
Reveal query helpsA to know the session key (sk) of UXi and Sji in another session. We let qR be the sum of the number of reveal queries and ski ← Reveal (Oi) be the symbol standing for the output of this query, where Oi is UXi or Sji. Note that to perform this query, Oi must be fresh.(iv)
Corrupt query helpsA to know secret information of UXi. We let qC be the sum of the number of corrupt queries and {UIDX, BX} ← Corrupt (UXi, 1) and {smart card} ← Corrupt (UXi, 0) be the symbol standing for the output of this query. Note that A only knows the smart card or {UIDX, BX}.(v)
Hash query helpsA to query a value m and receive corresponding r. If m is not queried before, OHash returns the random number r to the adversary. Otherwise, it returns the previously generated result. We let qH be the sum of the number of hash queries and r ← Hash (OHash, m) be the symbol standing for the output of this query.Theorem 1.
Our schemeP is AKE-security against A within a time tA if A cannot guess the correct session key of another fresh Oi. Formally, let AdvPAKE (A, tA) be the A’s chance of breaking P in AKE-security within in reasonable time tA, and we need AdvPAKE (A, tA) is negligible. In summary, we need AdvPAKE (A, tA) ≤ ε (∗).


## 4.3. The Definition of Experiments

We setExpTCMDHP (B) be experiment, where the adversary B wins if it successfully breaks CMDHP-security of the Chebyshev polynomial T’s problem within a time tB, and let AdvTCMDHP (B) = Pr[ExpTCMDHP (B) = 1] be the B’s winning chance. Note that we give OHash to B.Experiment 1.
ExpTCMDHP (B).{s, r} ⟵$ {0, 1}∗, X ⟵$ [0, p − 1]M ⟵ Tr (X) mod pN ⟵ Ts (X) mod pK ⟵ Tr (Ts (X)) mod pZ ⟵ BOHash (M, N, Hash (OHash, K))ifHash (OHash, Z) = Hash (OHash, K) then return 1else return 0
Also, we setExpPAKE (A) be experiment, where the adversary A wins if it successfully breaks AKE-security of our P within a time tA, and let AdvPAKE (A) = Pr [ExpPAKE (A) = 1] be the A’s winning chance. Note that we also give OHash to A.Experiment 2.
ExpPAKE (A).b ⟵$ {0, 1}, LU ⟵ {U1, …, Un}, LS ⟵ {S1, …, Sn}Ui ⟵$ LU, Sj ⟵$ LSsidUiSj ⟵ Execute (Ui, Sj)ifb = 0 thensk ⟵$ {0, 1}∗elsesk ⟵ Reveal (Ui){b′, Z} ⟵ AOHash (LU, LS, sk)ifb′ = bthen return 1else return 0
Note that ifb = b′ = 1, then we must have Hash (OHash, Z) = sk.
The proof of Theorem1.
Now we assume thatB wants to win in B’s experiment, and it runs A as the procedure. Also, A wants to win in A’s experiment and B must simulate the A’s environment as the following algorithm Let l be the security length, for example, the size of the prime p and hash function’s output. If A correctly guesses b′, then we must consider some following cases (Algorithm 1):(i)
A issues qH queries to OHash, and A has successful probability ≈ qH2/2l due to the birthday paradox.(ii)
A chooses qE pairs to execute and have all messages exchanged between them. Furthermore, A issues qC queries to some users to get the smart card or {UID, B}. So, A’s successful probability of correctly guessing random values r or s is ≈ qE×qC/p.(iii)
If A issuesqS′ queries to oracles simulated by B, there will be at least one Send query that helps A compute the session key. So, we have AdvTCMDHP (B) ≥ AdvPAKEA/qS′. When A issues the remaining qS−qS′ queries to normal Oi, A’s successful probability of correctly guessing is ≈ qS−qS′/p.
Finally, we haveAdvPAKE (A) ≤ qH2/2l + qE×qC/p + AdvTCMDHP (B) × qS′ + qS−qS′/p. Clearly, the right-hand side of this inequality is negligible, so we complete the proof.Algorithm 1:BTCMDHP (M, N, sk ⟵ Hash (OHash, K)).
SetLU ⟵ {U1, …, Un}, LS ⟵ {S1, …, Sn}RunAOHash (LU, LS, sk)ifA chooses qE pairs to execute thenB does & returns all sid to Aend ififA asks qR queries to fresh Oi in LU and LSthenifOi is normal in LU and LSthenB lets Oi return session-key to A as usualelseB returns random string to Aend ifend ififA asks qS queries to Oi in LU and LSthenifOi is normal in LU and LSthenB lets Oi & A exchange mout as usualelseB simulates & gives to A mout including M and Nend ifend ififA asks qC queries to some UXi in LUthenB returns smart-card or {UID, B} of UXi to AelseB returns random smart-card or {UID′, B′} to Aend ififA asks qH queries to OHashthenB lets OHash do with Aend ifUntilA stops and outputs {b′, Z}B returns (Hash (OHash, Z) = sk)


## 4.4. Security Analysis

In this section, we will analyse our scheme in some popular kinds of attacks. The comparison of the security feature with previous works is shown in Table7. Before coming into this section, we want to discuss the privileged insider attacks. In our scheme, we use biometrics rather than the password. Therefore, the privileged insider attacker cannot find it and exploit into different servers. Furthermore, all servers in our scheme use different long-term keys provided from RC, so the attacker cannot use the users’ information in another server to exploit in others. It can be said that it is hard to launch a privileged insider attack in our scheme.Table 7
The security feature comparison among the schemes.
SchemesLi [11]Qu [12]Amin [13]Jangirala [18]Han [19]OursPassword-guessing✗✓✓✓✓✓User’s anonymity✓✓✓✓✓✓Two-factor✗✓✓✗✓✓Known session-specific temporary information✗✓✓✗✗✓Session-key perfect forward✗✓✗✗✓✓User impersonation✗✗✓✗✗✓Server impersonation✓✓✓✓✓✓Man-in-the-middle✓✞1✞1✞1✞1✓Replay✓✓✓✓✓✓Parallel session✞1✞1✞1✞1✞1✓1Untouched.


## 4.5. Password-Guessing Attack

In this kind of attack, the adversary can guess the user’s password by exploiting leaking information from the smart card. The adversary will haveRPWX = H0 (H0 (RX || UIDX) || rX). Because RU is produced by the user’s biometrics, it is hard to guess. Clearly, the adversary cannot use the dictionary method to find biometrics and our scheme can resist this kind of attack.


## 4.6. User’s Anonymity

In this kind of attack, the adversary eavesdrops {rX, CID, MU, R′}, {S′, MS}, and {MUS} from UX. All messages are different at each login session because we use random values. So, the adversary cannot trace who is online. In other words, our scheme resists this attack.


## 4.7. Two-Factor Attack

AlthoughUX loses his/her smart card, the adversary cannot exploit because of needing BX to pass RPWX = H0 (H0 (RX || UIDX) || rX). Even if UX’s biometrics is fake, the adversary cannot exploit all information in the login message because he/she does not other supporting values. Clearly, our scheme resists this attack.


## 4.8. Known Session-Specific Information Attack

WhenrU and rS are leaked, the adversary cannot compute the session key (SK). He needs TrU (TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p) mod p to compute the SK. If he does not have the smart card’s information, all important keys cannot be successfully computed. Clearly, our scheme can resist this kind of attack.


## 4.9. Session-Key Perfect Forward Secrecy

If all important keys are leaked, the adversary cannot compute previous transactions betweenUX and Sj. With ASIDj and all messages UX sent to Sj, the adversary extracts RU = R′ − TASIDj (H0 (rj + rX + UIDX)) mod p and RS = S′ − RU. Finally, the adversary cannot compute TrU (TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p) mod p because of facing CMDHP. Clearly, our scheme can resist this kind of attack.


## 4.10. User Impersonation Attack

To impersonate as a valid user, the adversary needsRS = TrS (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p. To have RS, he/she needs UX’s RU = TrU (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p. Furthermore, the adversary must resend the session key to Sj. Therefore, he/she not only finds RU but also knows rU to impersonate as a valid user. Clearly, our scheme can resist this kind of attack.


## 4.11. Server Impersonation Attack

To impersonate as a valid server, the adversary needsRU = TrU (TASIDj (H0 (rj + rX + UIDX)) mod p) mod p. So, he/she also needs ASIDj to compute RU. We see this is impossible because Sj keeps ASIDj secret. Clearly, our scheme can resist this kind of attack.


## 4.12. Man-in-the-Middle Attack

In this kind of attack, the adversary can eavesdrop all messages exchanged betweenUX and Sj and then edits the parameters in these packages. For example, the adversary can insert his/her own session key with randomly chosen rU and rS. However, this is impossible because UX’s random value combined with ASIDj. Therefore, the adversary needs to compute this key to achieve the goal, but this is impossible because this is UX’s secret key. Clearly, our scheme resists this attack.


## 4.13. Replay Attack

In this kind of attack, the adversary can eavesdrop all messages exchanged betweenUX and Sj. At any time, he/she can replay to cheat UX or Sj. We consider if the adversary resends {CID, R′, MU, rX} to Sj, and this is the valid message. However, Sj requests UX respond {MUS} for confirmation, and the adversary cannot compute MUS. Furthermore, the adversary can resend Sj’s {MS, S′} to cheat UX, but this is impossible because UX and Sj use random values. So {MS, S′} is only valid if UX rechooses random values. Clearly, our scheme can resist this kind of attack.


## 4.14. Parallel Session Attack

In this kind of attack, the adversary will use {MS, S′} to create {CID, R′, MU, rX}, and cheat Sj. As aforementioned in replay and impersonation attacks, the adversary cannot achieve the goal because he/she needs key UX’s TASIDj (H0 (rj + rX + UIDX)) mod p and Sj’s ASIDj. Clearly, our scheme resists this attack.


## 4.15. Efficiency Analysis

Now, this section presents the cost of our scheme compared with previous schemes. Before coming to detail comparison, we will unify some notations and the bit size of some cryptographic primitives. If the scheme does not mention, we assume as follows: the sizes of identity, password, biometrics, timestamp, and random values are 128 bits. The size of hash function’s output and encryption scheme is 128 bits. The prime number in modular is 1024 bits (≈309 decimal digits) and 233 bits (≈70 decimal digits) in ECC. We let the notations denote the time to compute some cryptographic operations:(i)
tH: time to compute hash function (≈0.0004 ms)(ii)
tPA: time to compute point addition (≈0.36 ms)(iii)
tPM: time to compute point multiplication (≈12.4 ms)(iv)
tE/D: time to encrypt/decrypt (≈0.09 ms)(v)
tT: time to compute Chebyshev polynomial (≈127 ms)All the amount of time is results we measure on the real Android device with the Bouncy Castle library. Next, we evaluate the computation quantity of previous schemes and ours in Table8. In Li et al.’s scheme [11], registration needs 4 × tH and authentication needs 15 × tH. In Qu and Tan’s scheme [12], registration needs 4 × tH, 2 × tPM and authentication needs 11 × tH, 5 × tPM and 5 × tPA. In Amin and Biswas’s scheme [13], registration needs 5 × tH, 1 × tE/D and authentication needs 10 × tH, 5 × tPM, 2 × tPA and 1 × tE/D. In Jangirala et al.’s scheme [18], registration needs 5 × tH, 1 × tE/D and authentication needs 10 × tH, 5 × tPM, 2 × tPA and 1 × tE/D. In Han et al.’s scheme [19], registration needs 5 × tH, 1 × tE/D and authentication needs 10 × tH, 5 × tPM, 2 × tPA and 1 × tE/D. In the proposed scheme, registration needs 2 × tT, 4 × tH and authentication needs 11 × tH, 6 × tT.Table 8
The comparison of computation cost.
SchemesAuthentication/Registration phasesLi [11]15 ×tH4 ×tHQu [12]11 ×tH, 5 × tPM, 5 × tPA4 ×tH + 2 × tPMAmin [13]10 ×tH, 5 × tPM, 2 × tPA, 1 × tE/D5 ×tH, 1 × tE/DJangirala [18]21 ×tH6 ×tHHan [19]11 ×tH, 2 × tE/D, 4 × tT4 ×tH, 1 × tE/DOurs11 ×tH, 6 × tT4 ×tH, 2 × tTNext, we evaluate the store and authentication costs of previous schemes and ours in Table9. In Li et al.’s scheme [11], the user stores {Ci, Di, Ei, h (.), h (y), b} with 640 bits. And the authentication in this scheme needs {Pij, CIDi, M1, M2}, {M3, M4}, and {M5} with 896 bits. In Qu and Tan’s scheme [12], the user stores {AIDU, BIDU, bU} with 1618 bits. And the authentication in this scheme needs {CIDU, DIDU, EIDU, R}, {T, HS}, and {HRS} with 3702 bits. In Amin and Biswas’s scheme [13], the user needs {Fi, Ai, Bi, CIDi, h (.), H (.)} with 2304 bits. And authentication in this scheme needs {C2, C4, CIDi}, {Li, G1, CIDi′}, and {Zi} with 4818 bits. In Jangirala et al.’s scheme [18], the user needs {Ci, Di, Ei, h (y), h (.)} with 768 bits. And authentication in this scheme needs {Pij, CIDi, M1, M2}, {M3, M4}, and {M5} with 896 bits. In Han et al.’s scheme [19], the user needs {P, K, V, CID, h (.)} with 640 bits. And authentication in this scheme needs {CID, X, V1, T1}, {CID′, Y, T2, V2}, and {V3, T3} with 3072 bits. In our proposed scheme, the user stores {s1X, s2X, …, smX, RPWX, H0 (.), rX}, but we assume that the smart card stores only one siX for convenient comparison with other schemes in single-server environment, so the cost is 722 bits. And authentication in our scheme needs {CID, R′, MU, rX}, {MS, S′}, and {MUS} with 2688 bits.Table 9
The comparison of storage authentication cost.
SchemesStorage cost (bits)Authentication cost (bits)Li [11]640896Qu [12]16183702Amin [13]23044818Jangirala [18]768896Han [19]6403072Ours7222688


## 5. Conclusions

This paper proposed a scheme using Chebyshev polynomial in multiserver environment. We survey and analysis current schemes to propose the solution overcoming the limitations in each approach. In the future, we will analyse many different approaches to apply with our scheme. Also, we design some new architectures which have average overall cost even if using high-cost computational operation. Finally, we try to minimize the size of message package exchanged between the user and server to enhance time-efficiency.



---

*Source: 3579705-2020-08-25.xml*