# Improved Chebyshev Polynomials-Based Authentication Scheme in Client-Server Environment

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

---

## Abstract

With nonstop development of communication technologies, all aspects of social life continuously change and so do network systems. When establishing connection is easy, the convenience of online-service receives many users’ attentions, for example, the patients directly access medical system to be advised by doctors at any time. Therefore, user authentication scheme is necessary when we want to provide privacy and security for working sessions. Storing a password list for verification is an old method and not secure. This list can be easily leaked, and adversary can launch an offline password-guessing attack. In addition, information exchanged between user and server needs being prevented from attacker’s decryption. It can be said that current authentication schemes are unsuitable for new security standard. We need a strong user authentication scheme using new approach to overcome existing limitations and guarantee time efficiency. In this paper, we make a design withChebyshev polynomial to achieve our goals and resist some kinds of attacks.


---

## Body

## 1. Introduction

User authentication is one of the first important parts in all remote services. Furthermore, after successful authentication, partners secretly exchange the messages to each other and we need a session key to encrypt all these messages. Therefore, authentication scheme also needs a session key agreement phase. Especially, when the wearable devices become popular, such as smart-glasses or smart-watch, a user wants to connect to remote service through these low-power computing devices. Therefore, in addition to security, also we consider the time efficiency which is one of the important factors. There are many proposed results using cryptography primitives to make a reasonable user authentication scheme. Lamport [1] is the pioneer using hash function with password. His method is a usage of password-table for user verification in login phase. This is a simple way and easily implemented, but his scheme is vulnerable to verification stolen attack, and inappropriately using password can result in offline password-guessing attack. Then, there are many proposed schemes to enhance security. Typically, in 2004 Das et al. [2] proposed dynamic identity to provide user anonymity in his scheme. This is a positive idea, but in his scheme, he uses password instead of real user’s identity to create a dynamic login message. This causes their scheme cannot resist password-related attacks, and even the server may launch a password-guessing attack to find real user’s password.In 2006, Yoon et al. [3] proposed dynamic identity scheme using time-stamp. This scheme overcomes the reflection attack existing in Liao et al.’s scheme [4]. Clearly, Yoon’s scheme has important improved ideas to isolate such problems. However, they also use password to authenticate with online server, so their scheme is still vulnerable to password-related attacks. Until now, password is still one of the most convenient factors in many authentication schemes, if only using this factor can be insecure. Using reasonable encryption scheme with block-cipher, such asAdvance Encryption Standard (AES) orTriple Data Encryption Standard (T-DES), can enhance security for authentication scheme. Furthermore, if we only use hash function in scheme, this can increase authentication speed because time-cost of hash function is lower than the encryption scheme.In addition to applying cryptography primitives, there is an approach using hard problems as security foundation, such as RSA orElliptic curve crypto-systems(ECC). In 2009, Yang et al. [5] proposed a scheme in ECC. This is an efficient scheme because it usesdiscrete logarithm andDiffie-Hellman problems inelliptic curve. However, instead of using random values, they use point’s coordinates to create a session key which does not satisfyperfect forward session key secrecy (PFS), one of the most standards to evaluate a strong authentication scheme. Therefore, some improved schemes were proposed, for instance, Islam et al. [6]. Their scheme used random values in creation of session key. However, his scheme is still vulnerable to known session-specific temporary information and denial of service attacks. In 2015 and 2016, Huang et al. [7] and Chaudhry et al. [8] proposed ECC-based authentication schemes, but these schemes cannot resist malicious user attack and does not provide PFS. Also, in 2015 Chaudhry et al. [9] proposed an authentication scheme in multiserver environment with general public key cryptography (RSA or ECC). However, their scheme needs a certificate agency (CA) to check the validity for the server’s key pairs. Furthermore, all previous session keys will be recomputed if PFS appears. Compared with RSA, ECC can achieve the same security with a smaller key size. It can be said that ECC is one of the popular approaches many authors apply in authentication scheme because it offers better performance [10].Recently,Chebyshev polynomial is an approach many authors pay attention to. Although this method’s computational cost is more than ECC’s and it is being researched to be a standard such as RSA or ECC. However, this is a new method, so there are so many papers applying it into their schemes. At first, authentication schemes use polynomial on real field to make a security foundation, but Bergamo [11] proposed a solution to break its security. In 2013, Hao et al. [12] proposed a scheme in telecare medicine information system using polynomial in real field, but Lee et al. [13] discovered that this scheme is vulnerable to violation of the contributory of key agreements. And Lee proposed a different improved scheme. However, we see that his scheme is still vulnerable to what Hao’s scheme did. Also, there are some papers [14, 15] facing the same problem which Lee and Hao did. To enhance security forChebyshev polynomial, Zhang [16] extended the polynomial’s semigroup property to the interval (-∞, +∞). Since then,Chebyshev polynomial can be placed in modular prime number field and receives more consideration of security analysis [17]. In 2016, Irshad et al. [18] proposed an authentication scheme in multiserver withChebyshev. This scheme is designed with three actors suitable for global mobility network (Glomonet). However, a partial of information about registration centre’s master key (Ky) can be leaked. In their scheme, they havePIDi  ⊕Ky = (qi ∥ID ∥PW). Clearly, the value and length ofID andPW is known, and any users easily guess by inspectingPIDi = (x ∥easily_guess) ⊕ (qi ∥ID ∥PW). Although all information ofKy is not leaked, this is dangerous because user can collect manyPID to find the “x” value. In 2017, Wang and Xu [19] proposed a reference model to solve the offline dictionary attacks. Their model is truly useful for designing many schemes with different approaches, such as RSA, ECC, orChebyshev. It can be said thatChebyshev polynomial is a new approach which is being developed by many researchers and can be replaced for ECC or RSA in the future.The rest of our paper is organized as follows. In Section2, we present some background aboutChebyshev polynomial. In Section 3, we review some previous typical schemes and analyse them on security aspect. Then in Section 4 we propose improved scheme in client-server environment usingChebyshev polynomial in modular prime number field. In Section 5, we analyse our proposed scheme on two aspects, namely, security and efficiency. Finally, the conclusion is presented in Section 6.


## 2. Preliminaries

This section describes some features ofChebyshev polynomial in real and modular prime number fields [20]. Also, we give some different proofs compared with [21, 22]. Following arechaotic maps and two hard problems.


### 2.1. Chebyshev Chaotic Maps

Letn∈N andx∈[-1,1]; we defineChebyshev polynomial Tn(x): [-1,1] → [-1,1] asTn(x) = cos⁡n×arcos(x). Its semigroup property is as follows:(1)TaTbx=cos⁡a×arcoscos⁡b×arcosx=cos⁡a×b×arcosx=cos⁡b×a×arcosx=cos⁡b×arcoscos⁡a×arcos⁡x=TbTaxIn 2008, Zhang [16] extended (1) to the interval (-∞, +∞). Therefore, we have a different formula ofChebyshev polynomial as follows:(2)T0x=1modpT1x=xmodpTnx=2×x×Tn-1x-Tn-2xmodpwherep∈P,x∈[0,p–1] andn∈ℕ. We see that (2) can be changed to(3)Tnxmodp=λ1n+λ2n2modp


### 2.2. The Hard Problems

In addition to four important properties, we have two computational problems onchaotic maps we apply in proposed user authentication scheme.(i)
The first problem ischaotic maps baseddiscrete logarithm (CMDLP): Given y∈[0,p-1],p∈P, andx, it is hard to findr value such thatTr(x) =ymodp. We call thisdiscrete logarithm problem onchaotic maps.(ii)
The second problem ischaotic maps baseddiscrete logarithm (CMDHP): Givenx∈[0,p-1],p∈ ℙ,Ta(x)modp, andTb(x)modp, it is hard to findTab(x)modp. We call thisDiffie-Hellman problemchaotic maps.


## 2.1. Chebyshev Chaotic Maps

Letn∈N andx∈[-1,1]; we defineChebyshev polynomial Tn(x): [-1,1] → [-1,1] asTn(x) = cos⁡n×arcos(x). Its semigroup property is as follows:(1)TaTbx=cos⁡a×arcoscos⁡b×arcosx=cos⁡a×b×arcosx=cos⁡b×a×arcosx=cos⁡b×arcoscos⁡a×arcos⁡x=TbTaxIn 2008, Zhang [16] extended (1) to the interval (-∞, +∞). Therefore, we have a different formula ofChebyshev polynomial as follows:(2)T0x=1modpT1x=xmodpTnx=2×x×Tn-1x-Tn-2xmodpwherep∈P,x∈[0,p–1] andn∈ℕ. We see that (2) can be changed to(3)Tnxmodp=λ1n+λ2n2modp


## 2.2. The Hard Problems

In addition to four important properties, we have two computational problems onchaotic maps we apply in proposed user authentication scheme.(i)
The first problem ischaotic maps baseddiscrete logarithm (CMDLP): Given y∈[0,p-1],p∈P, andx, it is hard to findr value such thatTr(x) =ymodp. We call thisdiscrete logarithm problem onchaotic maps.(ii)
The second problem ischaotic maps baseddiscrete logarithm (CMDHP): Givenx∈[0,p-1],p∈ ℙ,Ta(x)modp, andTb(x)modp, it is hard to findTab(x)modp. We call thisDiffie-Hellman problemchaotic maps.


## 3. Cryptanalysis of Typical Related Works

In this section, we review some typical related works applyingChebyshev chaotic map in user authentication schemes. Also, we analyse on their security.


### 3.1. Han-Yu Lin’s Scheme

Lin’s scheme [23] includes four phases: system initialization, user registration, authentication and password change phases.(1)
Initialization phase. The serverS chooses all necessary parameters (r,x,Tr(x),h(.),Ek(.)). Especially (x, Tr(x)) is written into user’s smartcard.(2)
Registration phase. The userU chooses identityID, passwordPW, and random valuet, then computesH =h(PW,t), and sends ID,H toS through a secure channel. Once receivingU’s messages,S checksID’s validity and uses master keys to computeR =Es(ID,H),D =H ⊕ (x ∥Tr(x)). Finally,S sends R,h(.),Ek(.),D toU through a secure channel.U receivesS’s incoming smartcard and insertst into it.(3)
Authentication phase. WhenU authenticates withS,U provides (ID,PW) and smartcard into the terminal. Below are some steps for authentication (see Figure 1):
(a)
Smartcard choosesj and computes (x ∥Tr(x)) =h(PW,t) ⊕D,v =Tj(Tr(x)) andQ =h(ID,H).(b)
Next,U sends (Tj(x), Ev(Q,R,T1)) toS, whereT1 is receiving time-stamp.(c)
Once receivingU’s messages,S computesv =Tr(Tj(x)) and decrypts Ev(Q,R,T1) and then checksT1.(d)
Next,S decryptsR withs to recover (ID′,H′) and computesQ′ =h(ID′,H′). IfQ =Q′ thenS successfully authenticates withU. Otherwise,S terminates the session.(e)
Then,S choosesj′ and sends Ev(Tj′(x),h(ID,T2),T2) toU, whereT2 is time-stamp whenS sends the message toU.(f)
Once receivingS’s message,U decrypts and checksT2’s validity. At the same time,U computesh′(ID,T2).U checks the validity ofh′(ID,T2) ?=h(ID,T2). If this condition holds,U successfully authenticates withS; otherwiseU terminates the session.(g)
After successfully authentication phase, bothU andS compute session keyλ = Tj(Tj′(x)) for later usage.(4)
Password change phase.U provides smartcard, oldPW and newPW∗. Then, smartcard randomly choosesi and computesH′ =h′(PW,t), (x ∥Tr(x)) =H′  ⊕D,η = Ti(Tr(x)) andH∗ =h(PW∗,t) and then sends Ti(x),Eη(H′,H∗,R) toS. Once receivingU’s messages,S computesη =Ts(Ti(x)) and decryptsEη(H′,H∗,R) withη ands. Finally,S comparesH′ ?=H. If this holds,S returnsR∗ =Es(ID,H∗) to smartcard, then it updatesR =R∗.Figure 1
Han-Yu Lin’s authentication scheme.


### 3.2. Security Analysis on Han-Yu Lin’s Scheme

In this subsection, we also review some limitations existing in this scheme.(i)
In this phase, (x ∥ Tr(x)) is the same in all users’ smartcard. Therefore, malicious user can exploit this to launch an offline password-guessing attack if another user’s smartcard is lost. Suppose malicious user extracts R,h(.), Ek(.),D,t of another user. Then, malicious user computesH by performingH =D ⊕ (x ∥Tr(x)), where (x ∥Tr(x)) belongs to malicious user’s smartcard. WithH, malicious user buildsH ?=h(PW,t) and Han-Yu Lin’s scheme is vulnerable to this kind of attack.(ii)
Also, Han-Yu Lin’s scheme is vulnerable to contributory property of key agreement. In this scheme,S can determine common session key withoutU’s random value. Below are some stepsS can perform:
(1)
Findj′ such that Tj′(x) =Tj(x), wherej′ = cos-1⁡Tjx+k2π/cos-1(x)∣k∈Z.(2)
Then,S chooses session keyλ′ and computesv = cos-1⁡λ′+k2π/j′×cos-1⁡(x)∣k∈Z.(3)
S hasλ’ = Tv(Tj′(x)) and transmits Tv(x) toU. WhenU receives Tv(x),U computes Tj(Tv(x)) = Tv(Tj(x)) = Tv(Tj′(x)) =λ′. So, Lin’s scheme is vulnerable to this property.


### 3.3. Hongfeng Zhu’s Scheme

Zhu’s scheme [24] includes four phases: registration, login, authentication, and password change phases.(1)
Registration phase. In this phase, the userU chooses passwordPWa, then randomly chooses valuet, and computesWa =h(PWa ∥t). Next,U sends (IDa,Wa) to the serverS through a secure channel. After receivingU’s (IDa,Wa),S computesHa =h(s ∥IDa),na =h(Wa ∥IDa) ⊕Ha, and sends na,x,Ts(x) toU through a secure channel. Once receivingS’s messages,U computesNa =h(IDa ∥PWa) ⊕na  ⊕h(Wa ∥IDa) =h(IDa ∥PWa) ⊕Ha. Finally,U saves Na,x,Ts(x) intoU’s device.(2)
Login-authentication phases (see Figure 2). In this phase,U inputs (IDa,PWa) andU’s device randomly chooses two valuesk,R to computeHa =Na  ⊕h(IDa ∥PWa) =h(s ∥IDa), Tk(x),KAS =TkTs(x),HA =h(Ha ∥Tk(x) ∥IDa ∥IDb ∥R),C = EKAS(HA ∥IDa ∥IDb ∥R). Then,U sends C,Tk(x) toS. After receivingU’s messages,S computesKSA =TsTk(x) by usingTk(x) and master keys. Then,S decryptsC to recoverHA ∥IDa ∥IDb ∥R.S computesHa =h(s ∥IDa) and HA′=h(Ha ∥Tk(x) ∥IDa ∥IDb ∥R). Finally,S checks HA′ ?=HA. If this holds,S randomly choosesr and computesV1 =h(h(R ∥r)),V2 =Ha  ⊕h(R ∥r),SK =h(IDa ∥IDb ∥R ∥h(R ∥r)) and sends V1,V2 toU. Otherwise,S terminates the session. Once receivingS’s V1,V2,U’s device checksV1 ?=h(V2  ⊕Ha). If this does not hold,U’s device terminates the session, otherwise it computesSK =h(IDa ∥IDb ∥R ∥h(R ∥r)).(3)
Password change phase. In this phase,U provides oldPWa, new PWa′, andID. Then, the device chooses random valuek′ and computesHa =Na⊕h(IDa ∥PWa) =h(s ∥IDa), Na′ =Na⊕h (IDa ∥PWa) ⊕h(IDa ∥ PWa′),Tk(x)′, KAS′ = Tk′Ts(x), HA′ =h(Ha ∥ Tkx′ ∥IDa ∥IDb ∥h(Na′)) andC′ = EKAS′(HA′ ∥IDa ∥IDb ∥h(Na′)). The device sends C′,Tk(x)′ toS.S computes KSA′ = TsTk′(x) to decrypt DKAS′(C) = HA′ ∥IDa ∥IDb ∥h(Na′). Next,S computesHa =h(s ∥IDa) and HA′′ =h(Ha ∥Tk(x)′ ∥IDa ∥IDb ∥h(Na′)).S checks HA′′ ?= HA′. If this does not hold,S rejects. Otherwise, password-update is accepted and device computesV3 =h(KSA′ ∥response), whereresponse = “update” or “refuse”. Finally,S returnsV3 toU. OnceU’s device receives V3,response, it checksV3 ?=h(KAS′ ∥response). If this holds, it updates (Na with Na′) or rejects if response isrefused.Figure 2
Hongfeng Zhu’s authentication scheme.


### 3.4. Security Analysis on Hongfeng Zhu’s Scheme

Next, we also review some limitations existing in this scheme.(i)
Hongfeng Zhu’s scheme does not provide PFS. If important information such as master keys is leaked,U’s session key will be easily computed with previous exchanged messages. Suppose an adversary captures C, Tk(x) and V1,V2 at another session betweenU andS. Withs, the adversary computesKSA =TsTk(x) and decrypts DKSA(C) =HA ∥IDa ∥IDb ∥R. Next, he/she computesHa =h(s ∥IDa) and extractsh(R ∥r) =V2  ⊕Ha. Finally, he/she computesSK =h(IDa ∥IDb ∥R ∥h(R ∥r)). Clearly, this scheme does not satisfy PFS.(ii)
This scheme does not store password-confirmation message atU’s device, so password-update phase must connect toS. However, adding a value inU’s device helps login phase be more secure if the device is stolen. For example, we addL =h(IDa ∥PWa ∥Ha) into the device. When logging,U inputsIDa andPWa.U’s device computesHa =Na  ⊕h(IDa ∥PWa) and then checksL ?=h(IDa ∥PWa ∥Ha). If this holds,U is real device’s owner. WithL, this scheme can resist offline password-guessing attack if device’s information is leaked becauseL contains authentication keyHa =h(s ∥IDa). In password change phase,U needs correcting oldPW to passL =h(IDa ∥PWa ∥Ha). If this holds,U’s device will accept newPW′ provided byU. Next,U’s device recomputes Na′ =Na  ⊕h(IDa ∥PWa) ⊕h(IDa ∥ PWa′) andL′ =h(IDa ∥ PWa′ ∥Ha). Clearly, password change phase is more efficient than previous old phase.


## 3.1. Han-Yu Lin’s Scheme

Lin’s scheme [23] includes four phases: system initialization, user registration, authentication and password change phases.(1)
Initialization phase. The serverS chooses all necessary parameters (r,x,Tr(x),h(.),Ek(.)). Especially (x, Tr(x)) is written into user’s smartcard.(2)
Registration phase. The userU chooses identityID, passwordPW, and random valuet, then computesH =h(PW,t), and sends ID,H toS through a secure channel. Once receivingU’s messages,S checksID’s validity and uses master keys to computeR =Es(ID,H),D =H ⊕ (x ∥Tr(x)). Finally,S sends R,h(.),Ek(.),D toU through a secure channel.U receivesS’s incoming smartcard and insertst into it.(3)
Authentication phase. WhenU authenticates withS,U provides (ID,PW) and smartcard into the terminal. Below are some steps for authentication (see Figure 1):
(a)
Smartcard choosesj and computes (x ∥Tr(x)) =h(PW,t) ⊕D,v =Tj(Tr(x)) andQ =h(ID,H).(b)
Next,U sends (Tj(x), Ev(Q,R,T1)) toS, whereT1 is receiving time-stamp.(c)
Once receivingU’s messages,S computesv =Tr(Tj(x)) and decrypts Ev(Q,R,T1) and then checksT1.(d)
Next,S decryptsR withs to recover (ID′,H′) and computesQ′ =h(ID′,H′). IfQ =Q′ thenS successfully authenticates withU. Otherwise,S terminates the session.(e)
Then,S choosesj′ and sends Ev(Tj′(x),h(ID,T2),T2) toU, whereT2 is time-stamp whenS sends the message toU.(f)
Once receivingS’s message,U decrypts and checksT2’s validity. At the same time,U computesh′(ID,T2).U checks the validity ofh′(ID,T2) ?=h(ID,T2). If this condition holds,U successfully authenticates withS; otherwiseU terminates the session.(g)
After successfully authentication phase, bothU andS compute session keyλ = Tj(Tj′(x)) for later usage.(4)
Password change phase.U provides smartcard, oldPW and newPW∗. Then, smartcard randomly choosesi and computesH′ =h′(PW,t), (x ∥Tr(x)) =H′  ⊕D,η = Ti(Tr(x)) andH∗ =h(PW∗,t) and then sends Ti(x),Eη(H′,H∗,R) toS. Once receivingU’s messages,S computesη =Ts(Ti(x)) and decryptsEη(H′,H∗,R) withη ands. Finally,S comparesH′ ?=H. If this holds,S returnsR∗ =Es(ID,H∗) to smartcard, then it updatesR =R∗.Figure 1
Han-Yu Lin’s authentication scheme.


## 3.2. Security Analysis on Han-Yu Lin’s Scheme

In this subsection, we also review some limitations existing in this scheme.(i)
In this phase, (x ∥ Tr(x)) is the same in all users’ smartcard. Therefore, malicious user can exploit this to launch an offline password-guessing attack if another user’s smartcard is lost. Suppose malicious user extracts R,h(.), Ek(.),D,t of another user. Then, malicious user computesH by performingH =D ⊕ (x ∥Tr(x)), where (x ∥Tr(x)) belongs to malicious user’s smartcard. WithH, malicious user buildsH ?=h(PW,t) and Han-Yu Lin’s scheme is vulnerable to this kind of attack.(ii)
Also, Han-Yu Lin’s scheme is vulnerable to contributory property of key agreement. In this scheme,S can determine common session key withoutU’s random value. Below are some stepsS can perform:
(1)
Findj′ such that Tj′(x) =Tj(x), wherej′ = cos-1⁡Tjx+k2π/cos-1(x)∣k∈Z.(2)
Then,S chooses session keyλ′ and computesv = cos-1⁡λ′+k2π/j′×cos-1⁡(x)∣k∈Z.(3)
S hasλ’ = Tv(Tj′(x)) and transmits Tv(x) toU. WhenU receives Tv(x),U computes Tj(Tv(x)) = Tv(Tj(x)) = Tv(Tj′(x)) =λ′. So, Lin’s scheme is vulnerable to this property.


## 3.3. Hongfeng Zhu’s Scheme

Zhu’s scheme [24] includes four phases: registration, login, authentication, and password change phases.(1)
Registration phase. In this phase, the userU chooses passwordPWa, then randomly chooses valuet, and computesWa =h(PWa ∥t). Next,U sends (IDa,Wa) to the serverS through a secure channel. After receivingU’s (IDa,Wa),S computesHa =h(s ∥IDa),na =h(Wa ∥IDa) ⊕Ha, and sends na,x,Ts(x) toU through a secure channel. Once receivingS’s messages,U computesNa =h(IDa ∥PWa) ⊕na  ⊕h(Wa ∥IDa) =h(IDa ∥PWa) ⊕Ha. Finally,U saves Na,x,Ts(x) intoU’s device.(2)
Login-authentication phases (see Figure 2). In this phase,U inputs (IDa,PWa) andU’s device randomly chooses two valuesk,R to computeHa =Na  ⊕h(IDa ∥PWa) =h(s ∥IDa), Tk(x),KAS =TkTs(x),HA =h(Ha ∥Tk(x) ∥IDa ∥IDb ∥R),C = EKAS(HA ∥IDa ∥IDb ∥R). Then,U sends C,Tk(x) toS. After receivingU’s messages,S computesKSA =TsTk(x) by usingTk(x) and master keys. Then,S decryptsC to recoverHA ∥IDa ∥IDb ∥R.S computesHa =h(s ∥IDa) and HA′=h(Ha ∥Tk(x) ∥IDa ∥IDb ∥R). Finally,S checks HA′ ?=HA. If this holds,S randomly choosesr and computesV1 =h(h(R ∥r)),V2 =Ha  ⊕h(R ∥r),SK =h(IDa ∥IDb ∥R ∥h(R ∥r)) and sends V1,V2 toU. Otherwise,S terminates the session. Once receivingS’s V1,V2,U’s device checksV1 ?=h(V2  ⊕Ha). If this does not hold,U’s device terminates the session, otherwise it computesSK =h(IDa ∥IDb ∥R ∥h(R ∥r)).(3)
Password change phase. In this phase,U provides oldPWa, new PWa′, andID. Then, the device chooses random valuek′ and computesHa =Na⊕h(IDa ∥PWa) =h(s ∥IDa), Na′ =Na⊕h (IDa ∥PWa) ⊕h(IDa ∥ PWa′),Tk(x)′, KAS′ = Tk′Ts(x), HA′ =h(Ha ∥ Tkx′ ∥IDa ∥IDb ∥h(Na′)) andC′ = EKAS′(HA′ ∥IDa ∥IDb ∥h(Na′)). The device sends C′,Tk(x)′ toS.S computes KSA′ = TsTk′(x) to decrypt DKAS′(C) = HA′ ∥IDa ∥IDb ∥h(Na′). Next,S computesHa =h(s ∥IDa) and HA′′ =h(Ha ∥Tk(x)′ ∥IDa ∥IDb ∥h(Na′)).S checks HA′′ ?= HA′. If this does not hold,S rejects. Otherwise, password-update is accepted and device computesV3 =h(KSA′ ∥response), whereresponse = “update” or “refuse”. Finally,S returnsV3 toU. OnceU’s device receives V3,response, it checksV3 ?=h(KAS′ ∥response). If this holds, it updates (Na with Na′) or rejects if response isrefused.Figure 2
Hongfeng Zhu’s authentication scheme.


## 3.4. Security Analysis on Hongfeng Zhu’s Scheme

Next, we also review some limitations existing in this scheme.(i)
Hongfeng Zhu’s scheme does not provide PFS. If important information such as master keys is leaked,U’s session key will be easily computed with previous exchanged messages. Suppose an adversary captures C, Tk(x) and V1,V2 at another session betweenU andS. Withs, the adversary computesKSA =TsTk(x) and decrypts DKSA(C) =HA ∥IDa ∥IDb ∥R. Next, he/she computesHa =h(s ∥IDa) and extractsh(R ∥r) =V2  ⊕Ha. Finally, he/she computesSK =h(IDa ∥IDb ∥R ∥h(R ∥r)). Clearly, this scheme does not satisfy PFS.(ii)
This scheme does not store password-confirmation message atU’s device, so password-update phase must connect toS. However, adding a value inU’s device helps login phase be more secure if the device is stolen. For example, we addL =h(IDa ∥PWa ∥Ha) into the device. When logging,U inputsIDa andPWa.U’s device computesHa =Na  ⊕h(IDa ∥PWa) and then checksL ?=h(IDa ∥PWa ∥Ha). If this holds,U is real device’s owner. WithL, this scheme can resist offline password-guessing attack if device’s information is leaked becauseL contains authentication keyHa =h(s ∥IDa). In password change phase,U needs correcting oldPW to passL =h(IDa ∥PWa ∥Ha). If this holds,U’s device will accept newPW′ provided byU. Next,U’s device recomputes Na′ =Na  ⊕h(IDa ∥PWa) ⊕h(IDa ∥ PWa′) andL′ =h(IDa ∥ PWa′ ∥Ha). Clearly, password change phase is more efficient than previous old phase.


## 4. Proposed Scheme

Our proposed scheme usingChebyshev polynomial includes five phases: initialization, registration, authentication, and biometrics update phases. Below are some notations used in our scheme:(i)
Ui: the ith user(ii)
IDi: the ith user’s identification(iii)
Bi: the ith user’s biometrics(iv)
S: the server(v)
qS: the server’s master key(vi)
h(.): hash function(vii)
sk: common session key(viii)
SC: the smartcard(ix)
⊕, ∥: the XOR and concatenation operations(x)
T(.):Chebyshev polynomial operation


### 4.1. Initialization Phase

In this phase, we choose a huge prime numberk-bit p. ThenS choosesqS∈[1,p-1] andh: 0, 1∗ → 0, 1k. Finally,S publishes p,T(.),h(.)


### 4.2. Registration Phase

U i providesBi andIDi. Also,Ui randomly choosesN. Then,Ui computeshBi =h(N ∥Bi) andVi =h(Bi ∥N). Finally,Ui sends hBi,IDi toS through a secure channel. On receiving the Ui’s information,S checks IDi’s validity. Then,S randomly choosesXi.S computeshAIDi = TqS(h(IDi ∥Xi)) modp + TXi(h(IDi ∥hBi)) modp, thenS sends hAIDi, Xi toUi through a secure channel.Ui stores the information sent fromS into aSC(see Figure 3).Figure 3
Proposed scheme’s registration phase.


### 4.3. Authentication Phase

U i providesBi andIDi at the terminal. ThenSC checks ifVi ?=h(Bi ∥N). If this holds,SC computeshBi =h(N ∥Bi),AIDi =hAIDi - TXi(h(IDi ∥hBi)) modp.SC choosesri∈[1,p-1] and computesR′ = Tri(h(IDi ∥Xi)) modp,Ri = Tri(AIDi) modp,Mi =h(Ri,AIDi), andCID =IDi  ⊕h(Ri).SC sends Xi,CID,Mi,R′ toS through a common channel (see Figure 4).Figure 4
Proposed scheme’s authentication phase.When receivingUi’s login message, S computes Ri′ and AIDi∗, where Ri′ = TqS(R′) modp,IDi =CID ⊕h(Ri′) and AIDi∗ = TqS(h(IDi ∥ Xi)) modp. ThenS checks if Mi ?=h(Ri′, AIDi∗). If this does not hold, S terminates the session. Otherwise,S chooses rS∈[1,p-1] and computes RS = TrS(AIDi∗) modp,S′ = RS + Ri′,sk =h(TrS(Ri′)) and MS =h(RS, AIDi∗).S sends S′, MS to Ui through a common channel.When receivingS′,MS, Ui’sSC computes RS′ =S′ –Ri and checks ifMS ?=h(RS′,AIDi). If this holds,SC computessk =h(Tri(RS′)),MUS =h(RS′, Tri(RS′)). Then,SC sends MUS toS through a common channel.S checks ifMUS ?=h(RS, TrS(Ri′)). If this holds,S acceptsUi.Ui andS usesk to encrypt the information after authentication phase.


### 4.4. Biometrics Update Phase

WhenUi changes his/her biometrics, Ui’sSC checks if Vi ?=h(Bi ∥N). If this holds,SC computes Vinew =h(Binew ∥N) and hAIDinew = TXi(h(IDi ∥ hBinew)) modp + hAIDi - TXi(h(IDi ∥ hBi)) modp. Finally,SC replaces Vi and hAIDi with Vinew and hAIDinew.


## 4.1. Initialization Phase

In this phase, we choose a huge prime numberk-bit p. ThenS choosesqS∈[1,p-1] andh: 0, 1∗ → 0, 1k. Finally,S publishes p,T(.),h(.)


## 4.2. Registration Phase

U i providesBi andIDi. Also,Ui randomly choosesN. Then,Ui computeshBi =h(N ∥Bi) andVi =h(Bi ∥N). Finally,Ui sends hBi,IDi toS through a secure channel. On receiving the Ui’s information,S checks IDi’s validity. Then,S randomly choosesXi.S computeshAIDi = TqS(h(IDi ∥Xi)) modp + TXi(h(IDi ∥hBi)) modp, thenS sends hAIDi, Xi toUi through a secure channel.Ui stores the information sent fromS into aSC(see Figure 3).Figure 3
Proposed scheme’s registration phase.


## 4.3. Authentication Phase

U i providesBi andIDi at the terminal. ThenSC checks ifVi ?=h(Bi ∥N). If this holds,SC computeshBi =h(N ∥Bi),AIDi =hAIDi - TXi(h(IDi ∥hBi)) modp.SC choosesri∈[1,p-1] and computesR′ = Tri(h(IDi ∥Xi)) modp,Ri = Tri(AIDi) modp,Mi =h(Ri,AIDi), andCID =IDi  ⊕h(Ri).SC sends Xi,CID,Mi,R′ toS through a common channel (see Figure 4).Figure 4
Proposed scheme’s authentication phase.When receivingUi’s login message, S computes Ri′ and AIDi∗, where Ri′ = TqS(R′) modp,IDi =CID ⊕h(Ri′) and AIDi∗ = TqS(h(IDi ∥ Xi)) modp. ThenS checks if Mi ?=h(Ri′, AIDi∗). If this does not hold, S terminates the session. Otherwise,S chooses rS∈[1,p-1] and computes RS = TrS(AIDi∗) modp,S′ = RS + Ri′,sk =h(TrS(Ri′)) and MS =h(RS, AIDi∗).S sends S′, MS to Ui through a common channel.When receivingS′,MS, Ui’sSC computes RS′ =S′ –Ri and checks ifMS ?=h(RS′,AIDi). If this holds,SC computessk =h(Tri(RS′)),MUS =h(RS′, Tri(RS′)). Then,SC sends MUS toS through a common channel.S checks ifMUS ?=h(RS, TrS(Ri′)). If this holds,S acceptsUi.Ui andS usesk to encrypt the information after authentication phase.


## 4.4. Biometrics Update Phase

WhenUi changes his/her biometrics, Ui’sSC checks if Vi ?=h(Bi ∥N). If this holds,SC computes Vinew =h(Binew ∥N) and hAIDinew = TXi(h(IDi ∥ hBinew)) modp + hAIDi - TXi(h(IDi ∥ hBi)) modp. Finally,SC replaces Vi and hAIDi with Vinew and hAIDinew.


## 5. Security and Efficiency Analyses

In this section, we analyse our scheme on security and efficiency aspects. Also, our scheme’s design is correctly proved with BAN-logic [25], while its security is presented in each concrete attack case.


### 5.1. Correctness Analysis

Before getting into details about security, we will prove our scheme’s correctness with BAN-logic. We inherit some objectives from [26] because we see that they are reasonable ones, which authentication scheme must achieve to successfully share partner’s identities and session keys. For simplicity, we letK denote user’s long-term key shared by server at registration phase,sk denote session key, and ⊗ denoteChebyshev operation. Firstly, our scheme must satisfy some assumptions as shown in Table 1 (this is a must in this model)Table 1
The assumptions in BAN-logic.
Assumptions A 1: U ∣≡(U↔IDS) – U believes U can share ID with S A 2: U ∣≡(U↔KS)– U believes U can share K with S A 3: U ∣≡(S⇒(U↔SKS))– U believes S controls the sharing of sk between U and S A 4: S ∣≡(U⇒(U↔IDS))– SbelievesUcontrolsthe sharing ofIDbetweenUandS A 5: S ∣≡(U⇒(U↔SKS))–S believesUcontrols the sharing ofskbetweenUandS A 6: S ∣≡(S↔KU)– Sbelieves S can share KwithU A 7: U ∣≡ #(rS⊗ K) – U believes the challenge messages from S is fresh A 8: S ∣≡ #(rU⊗ K) – S believes the challenge messages from U is freshThese assumptions represent the first necessary believes of user and server. For example, when the users register with server, it is mean that they believe they can share identity with server (A1). Next, we will normalize all messages exchanged between user and server.(i)
From the messageCID we have <U↔IDS,U↔KS, rU  ⊗K>(ii)
From the messageMi we have <rU  ⊗K,U↔KS>(iii)
From the third messagesMUS we have <rS  ⊗K,U↔KS>(iv)
From the fourth messageMUS we have <U↔KS, U↔skS>The normalization is an arrangement of information exchanged between user and server. For example,CID contains identity, challenge informationrU  ⊗K, and long-term keyK. Normalization helps to highlight the important data in the messages. Next, we will demonstrate how our scheme satisfies seven lemmas that we reorganized from [32].Lemma 1.
If the server believes authentication key (long-term key) is successfully shared with user and the user’s messages encrypted with this key are fresh, the server will believe that the user believes his/her identity is successfully shared with server.(4)S∣≡S↔KU,S∣≡#rU⊗KS∣≡U∣≡U↔IDSProof.
WithA6 andCID, we applymessage-meaning rule to have(5)S∣≡S↔KU,S⊲<U↔IDS,U↔KS,rU⊗K>S∣≡U∣~<U↔IDS,U↔KS,rU⊗K>
WithA8, we applyfreshness rule to have(6)S∣≡#rU⊗KS∣≡#<U↔IDS,U↔KS,rU⊗K>
With (5) and (6), we applynonce-verification rule to have(7)S∣≡U∣~<U↔IDS,U↔KS,rU⊗K>,S∣≡#<U↔IDS,U↔KS,rU⊗K>S∣≡U∣≡<U↔IDS,U↔KS,rU⊗K>
With (7), we applybelieve rule:(8)S∣≡U∣≡<U↔IDS,U↔KS,rU⊗K>S∣≡U∣≡U↔IDS
So, withA6 andA8 we successfully demonstrate how our scheme satisfiesLemma1.Lemma 2.
If the server believes the user also believes his/her identity is successfully shared with each other and user totally controls this identity’s sharing, the server also believes user’s identity is successfully shared with each other.(9)S∣≡U∣≡U↔IDS,S∣≡U⇒U↔IDSS∣≡U↔IDSProof.
WithLemma1 andA4, we applyjurisdiction rule to have(10)S∣≡U∣≡U↔IDS,S∣≡U⇒U↔IDSS∣≡U↔IDS
So, withLemma1 andA4, we successfully demonstrate how our scheme satisfiesLemma2.Lemma 3.
If the user believes authentication key is successfully shared with server and the server’s messages encrypted with this key are fresh, the user will believe the server also believes user’s identity is successfully shared with each other.(11)U∣≡U↔KS,U∣≡#rS⊗KU∣≡S∣≡U↔IDSProof.
WithA2 andMS, we applyjurisdiction rule to have(12)U∣≡U↔KS,U⊲<rS⊗K,U↔KS>U∣≡S∣~<rS⊗K,U↔KS>With (12) andA7, we applyfreshness rule to have(13)U∣≡#rS⊗K,U∣≡S∣~<rS⊗K,U↔KS>U∣≡#<rS⊗K,U↔KS>
With (12) and (13), we applynonce-verification rule to have(14)U∣≡S∣~<rS⊗K,U↔KS>,U∣≡#<rS⊗K,U↔KS>U∣≡S∣≡<rS⊗K,U↔KS>
With (14), we applybelieve rule to have(15)U∣≡S∣≡<rS⊗K,U↔KS>U∣≡S∣≡U↔IDSSo, withA2 andA7 we successfully demonstrate how our scheme satisfiesLemma3. In short, with three lemmas we can say that both server and user believe and successfully share their identities with each other. Next, we need to prove the similar thing for session key.Lemma 4.
If the user believes that authentication key is successfully shared with server and server’s messages encrypted with this key are fresh, the user will believe the server also believes session key is successfully shared with each other.(16)U∣≡U↔KS,U∣≡#rS⊗KU∣≡S∣≡S↔SKUProof.
WithA2 and MUS, we applymessage-meaning rule to have(17)U∣≡U↔KS,U⊲<U↔KS,U↔skS>U∣≡S∣~<U↔KS,U↔skS>
WithA7 and MUS, we applyfreshness rule to have(18)U∣≡#rS⊗K,U⊲<U↔KS,U↔skS>U∣≡#<U↔KS,U↔skS>
With (17) and (18), we applybelieve rule to have(19)U∣≡S∣~<U↔KS,U↔skS>,U∣≡#<U↔KS,U↔skS>U∣≡S∣≡<U↔KS,U↔skS>
With (19), we applybelieve rule to have(20)U∣≡S∣≡<U↔KS,U↔skS>U∣≡S∣≡S↔skU
So, withA2 andA7 we successfully demonstrate how our scheme satisfiesLemma4.Lemma 5.
If the user believes the server totally controls session key’s sharing and the server also believes session key is successfully shared with user, the user will believe this session key’s sharing.(21)U∣≡S⇒U↔SKS,U∣≡S∣≡S↔SKUU∣≡U↔SKSProof.
WithA3 andLemma4, we applyjurisdiction rule to have(22)U∣≡S⇒U↔skS,U∣≡S∣≡S↔skUU∣≡U↔skS
So, withA3 andLemma4, we successfully demonstrate how our scheme satisfiesLemma5.Lemma 6.
If the server believes authentication key is successfully shared with user and the user’s messages encrypted with this key are fresh, the server will believe the user also believes this session key’s sharing.(23)S∣≡S↔KU,S∣≡#rU⊗KS∣≡U∣≡U↔SKSProof.
WithA6 andMUS, we applymessage-meaning rule to have(24)S∣≡S↔KU,S⊲<U↔KS,U↔skS>S∣≡U∣~<U↔KS,U↔skS>
WithA8 andMUS, we applyfreshness rule to have(25)S∣≡#rU⊗AID,S⊲<U↔KS,U↔skS>S∣≡#<U↔KS,U↔skS>
With (24) and (25), we applynonce-verification to have(26)S∣≡U∣~<U↔KS,U↔skS>,S∣≡#<U↔KS,U↔skS>S∣≡U∣≡<U↔KS,U↔skS>
WithA6 and (26), we applybelieve rule to have(27)S∣≡S↔KU,S∣≡U∣≡<U↔KS,U↔skS>S∣≡U∣≡U↔skS
So, withA6 andA8, we successfully demonstrate how our scheme satisfiesLemma6.Lemma 7.
If the server believes the user totally controls the session key’s sharing, the server will believe the session key is successfully shared with user.(28)S∣≡U⇒U↔SKSS∣≡S↔skUProof.
With (26) andA5, we applymessage-meaning rule to have(29)S∣≡U⇒U↔skS,S∣≡U∣≡<U↔KS,U↔skS>S∣≡<U↔KS,U↔skS>
With (29), we applybelieve rule to have(30)S∣≡<U↔KS,U↔skS>S∣≡S↔skUSo, withA5 we completely demonstrate how our scheme satisfiesLemma7. Finally, we can say that both server and user believe the common session key in our scheme.


### 5.2. Security Analysis

Before getting into details about some kinds of attacks, we will use random oracle model to prove the security for the session key inChebyshev polynomial case (see [27, 28] for more details). At first, we need to remind the model’s circumstance. Assuming another actorB has Ω = Tp(x),Tq(x)) andBneeds to computeTp×q(x),Bhas someoraclesClient andServer with all their instances at different times.Balso has an algorithmA being able to break our scheme to compute the session key with given probability ε.B will useA to find the session key and then computeTp×q(x) to solve CMDHP. To achieve this,B must “inject” Ω’s parameters into the messages whenA interacts with the oracles’ instances, andB also simulates an appropriate environment suitable forA to operate. Note that our scheme uses hash function and it is considered as an oracle. Next, we claim our theorem about the session key’s security.Theorem 8.
LetA be an adversary breaking our scheme in the meaning ofAKESecurity in timetA, usingqSendSend queries andqHashHash queries. We have(31)AdvPAKEA,tA,qSend,qHash≤qHash×qSend×AdvEFqECDHPCMDHPB,tB,qSend,qHash
whereB is an adversary breaking CMDHP in tB. The meaning of theorem is thatA’s successful probability breaking our scheme in the meaning ofAKESecurity is less thanB’s successful probability breaking CMDHP. According to CMDHP,B’s success probability is extremely low, and so isA’s successful probability breaking our scheme. Therefore, we can claim that our scheme has secure session key in the meaning ofAKESecurity.Proof.
Assume that we have actorB. This time,B needs to create some instances of oraclesClient andServer with Ω’s parameter.B also simulates an appropriate environment whereA can operate.
WhenA sendsSend(“Start”) to Uxi∈Client, Uxi repliesm1 toA (note thatm1 = identity encrypted,challenge information,confirmation depends on concrete scheme). Maybe,A sendsSend(“Start”) to some simulated oracle, for example, UBv. This time,B needs to inject Ω’s parameters intom1 with concrete scheme’s rules. Finally,B sendsm1 toA. WhenA sendsSend(m1) to Syj∈Server, Syj repliesm2 toA (note thatm2 = confirmation,challenge information depends on concrete scheme). Maybe,A sendsSend(m1) to simulated oracle SBv. This time,B also needs to inject Ω’s parameters intom2 and sendsm2 toA. WhenA sendsSend(m2) to Syj∈Server, Syj repliesm3 = final confirmation toA. Maybe,A sendsSend(m2) to simulated oracle SBv.B randomly choosessk←$0,1n, computesfinal confirmation message with this randomsk, and sendsm3 toA.
Sometimes,A sends wrongSend queries to the instances, so there are some oracles with“Accept” state and some oracles with “Reject” state. However, whenA finishes sending qSendSend queries, all instancesA interacts with must have“Terminated” state which istrue.
WhenA sendsCorrupt andReveal queries to these instances, their state will determine whatA obtains, such as long-term key or session key. WhenA sendsCorrupt andReveal queries to the oraclesB simulates,B will generate a random string representing session key for them. WhenA sendshash queries,B will let hash’soracle interact withA.
Finally,B activatesA to sends a uniqueTest query to simulated oracle or indicated oracle, andB expectsA to correctly guess bitb of this instance. In other words,B wantsA to correct guess this instance’s session key withA’s successful probability. We see that ifB is success, B needs three following consecutive factors:
(i)B needsA to correctly findsk of simulated oracle, andA’s successful probability is ε = AdvPAKE(A,tA).
(ii) Furthermore, whenA correctly findssk=h(Tp×q(x)…),A had found “Tp×q(x)” satisfying with thissk. Clearly, ifA sends qHash queries to hash’s oracle, there is at least one-timeA succeeds. So, γ ≥ 1/qHash. (Note that: the session keysk will be always computed with hash function.)
(iii) Next, whenA correctly finds Tp×q(x),A must correct guessq ors. Clearly, ifA sends qSend queries to the oracle, there is at least one-timeA succeeds. So, μ ≥ 1/qSend.
Finally, we haveAdvE(Fq)ECDHP(CMDHP)(B, tB, qSend, qHash) = ε × γ × μ ≥ ε × 1/qHash∗qSend ⇒ qSend × qHash × AdvE(Fq)ECDHP(CMDHP)(B, tB, qSend, qHash) ≥ ε = AdvPAKE(A, tA, qSend, qHash).In this subsection, we analyse our scheme on security aspect (see Table2).(1)
Password-guessing attack. If the smartcard’s information is leaked, and the adversary can exploit to perform password-guessing attack. Therefore, the adversary has Vi =h(Bi ∥N) in the smartcard. Differently from password,Bi is the user’s biometrics and it cannot be predicted. In short, our scheme easily resists this kind of attack.(2)
Replay attack. In this kind of attack, the adversary can replay the login message to impersonate the user. In our scheme, the adversary can replay Xi,CID,Mi,R′ to the server. Then, the server replies S′,MS to the adversary. At this time, the adversary cannot computeMUS becauseRi = Tri(AIDi) modp is impossible to know. Therefore, our scheme can resist this kind of attack.(3)
User anonymity. In this kind of attack, the adversary eavesdrops Xi,CID,Mi,R′, S′,MS and MUS of another user. The user’s identity is encrypted withRi, which includes the secretAIDi. Therefore, the adversary cannot trace who is authenticating and our scheme provides user anonymity.(4)
Impersonation attack. In this kind of attack, the adversary can impersonate either user or server. In our scheme, the adversary eavesdrops Xi,CID,Mi,R′ and S′, MS. However, he must sendMUS to cheat the server and this is impossible becauseri andAIDi are secret. Moreover, if he wants to impersonate the server, he needs to computeMS and this is impossible becauseAIDi is secret. Therefore, our scheme can resist this kind of attack(5)
Man-in-the-middle attack. In this kind of attack, the adversary can cheat both user and server simultaneously. However, he must compute random valuesri andAIDi. From this information, he can deriveRi to cheat the server and deriveMUS to cheat the user. Clearly, this information is secret, and the adversary cannot steal them.(6)
Parallel attack. In this kind of attack, the adversary uses another session’s messages to exploit the others. In our scheme, this is impossible because each session has different random values. For example, another session has the unique valuesri andrS, so all sessions have no relationship with each other.(7)
Two-factor attack. In this kind of attack, the adversary can steal the user’s biometrics, and then use this information to compute authentication key. We see that the smartcard includes N,Vi,hAIDi, Xi, so if there is no Bi, the adversary cannot computeAIDi. Of course, if the smartcard is well-protected, the adversary has no way to computeAIDi. Our scheme can resist this kind of attack.(8)
Perfect secrecy. In this kind of attack, the adversary has all secret keys of the users and the server. Of course, the service must be stopped at this time. However, we need to prevent the adversary from knowing past-transactions, and this means that all session keys must be secret. In our scheme, the session key is constructed fromri,rS, andAIDi. Clearly, if the adversary knows Tri(AIDi) and TrS(AIDi), he cannot compute Tri(TrS(AIDi)) because of facing with CMDHP.Table 2
The security feature comparison among the schemes.
Kinds of attack Lin[23] Zhu[24] Ours Password-guessing ✘ ✔ ✔ Replay ⌀1 ✔ ✔ User anonymity ✔ ⌀ ✔ Impersonation ✔ ✔ ✔ Man-in-the-middle ⌀ ⌀ ✔ Parallel ⌀ ⌀ ✔ Two-factor ✘ ✔ ✔ Perfect secrecy session key ⌀ ✘ ✔ 1The authors do not consider.


### 5.3. Efficiency Analysis

To compare efficiency between our scheme and previous ones, we let “h” be the hash operation, “e/d” be the encryption/decryption, and “T” be computational operation of polynomial. At registration phase, our scheme uses 4 ×h and 2 ×T. Lin’s scheme uses 1 ×h, 1 ×T, and 1×e/d. Zhu’s scheme uses 5 ×h. At authentication phase, our scheme uses 14 ×h and 8 ×T. Lin’s scheme uses 4 ×h, 5 ×T, and 5 ×e/d. Zhu’s scheme uses 9 ×h, 3 ×T, and 2 ×e/d. Our scheme’s computational cost is more than previous ones due to security enhancement (see Table 3).Table 3
The efficiency comparison among the schemes.
The phases Lin[23] Zhu[24] Ours Registration 1×h+1×T+1×e/d 5×h 4×h+2×T Authentication 4×h+5×T+5×e/d 9×h+3×T+2×e/d 14×h+8×TAlso, we letth,tT, andte/d denote running-time corresponding to each operation, for example,h,T, ande/d (th ≪te/d <tT). To relatively measure the running-time of three operations, we conduct an experiment usingJava Cryptography Architecture withBouncy Castle library inAndroid mobile device, core 4 CPU 1.2 GHz, and we haveth ≈ 0.00004ms,te/d ≈ 0.09385ms, andtT ≈ 80 ms (see Figure 5).Figure 5
The running-time of three schemes.


## 5.1. Correctness Analysis

Before getting into details about security, we will prove our scheme’s correctness with BAN-logic. We inherit some objectives from [26] because we see that they are reasonable ones, which authentication scheme must achieve to successfully share partner’s identities and session keys. For simplicity, we letK denote user’s long-term key shared by server at registration phase,sk denote session key, and ⊗ denoteChebyshev operation. Firstly, our scheme must satisfy some assumptions as shown in Table 1 (this is a must in this model)Table 1
The assumptions in BAN-logic.
Assumptions A 1: U ∣≡(U↔IDS) – U believes U can share ID with S A 2: U ∣≡(U↔KS)– U believes U can share K with S A 3: U ∣≡(S⇒(U↔SKS))– U believes S controls the sharing of sk between U and S A 4: S ∣≡(U⇒(U↔IDS))– SbelievesUcontrolsthe sharing ofIDbetweenUandS A 5: S ∣≡(U⇒(U↔SKS))–S believesUcontrols the sharing ofskbetweenUandS A 6: S ∣≡(S↔KU)– Sbelieves S can share KwithU A 7: U ∣≡ #(rS⊗ K) – U believes the challenge messages from S is fresh A 8: S ∣≡ #(rU⊗ K) – S believes the challenge messages from U is freshThese assumptions represent the first necessary believes of user and server. For example, when the users register with server, it is mean that they believe they can share identity with server (A1). Next, we will normalize all messages exchanged between user and server.(i)
From the messageCID we have <U↔IDS,U↔KS, rU  ⊗K>(ii)
From the messageMi we have <rU  ⊗K,U↔KS>(iii)
From the third messagesMUS we have <rS  ⊗K,U↔KS>(iv)
From the fourth messageMUS we have <U↔KS, U↔skS>The normalization is an arrangement of information exchanged between user and server. For example,CID contains identity, challenge informationrU  ⊗K, and long-term keyK. Normalization helps to highlight the important data in the messages. Next, we will demonstrate how our scheme satisfies seven lemmas that we reorganized from [32].Lemma 1.
If the server believes authentication key (long-term key) is successfully shared with user and the user’s messages encrypted with this key are fresh, the server will believe that the user believes his/her identity is successfully shared with server.(4)S∣≡S↔KU,S∣≡#rU⊗KS∣≡U∣≡U↔IDSProof.
WithA6 andCID, we applymessage-meaning rule to have(5)S∣≡S↔KU,S⊲<U↔IDS,U↔KS,rU⊗K>S∣≡U∣~<U↔IDS,U↔KS,rU⊗K>
WithA8, we applyfreshness rule to have(6)S∣≡#rU⊗KS∣≡#<U↔IDS,U↔KS,rU⊗K>
With (5) and (6), we applynonce-verification rule to have(7)S∣≡U∣~<U↔IDS,U↔KS,rU⊗K>,S∣≡#<U↔IDS,U↔KS,rU⊗K>S∣≡U∣≡<U↔IDS,U↔KS,rU⊗K>
With (7), we applybelieve rule:(8)S∣≡U∣≡<U↔IDS,U↔KS,rU⊗K>S∣≡U∣≡U↔IDS
So, withA6 andA8 we successfully demonstrate how our scheme satisfiesLemma1.Lemma 2.
If the server believes the user also believes his/her identity is successfully shared with each other and user totally controls this identity’s sharing, the server also believes user’s identity is successfully shared with each other.(9)S∣≡U∣≡U↔IDS,S∣≡U⇒U↔IDSS∣≡U↔IDSProof.
WithLemma1 andA4, we applyjurisdiction rule to have(10)S∣≡U∣≡U↔IDS,S∣≡U⇒U↔IDSS∣≡U↔IDS
So, withLemma1 andA4, we successfully demonstrate how our scheme satisfiesLemma2.Lemma 3.
If the user believes authentication key is successfully shared with server and the server’s messages encrypted with this key are fresh, the user will believe the server also believes user’s identity is successfully shared with each other.(11)U∣≡U↔KS,U∣≡#rS⊗KU∣≡S∣≡U↔IDSProof.
WithA2 andMS, we applyjurisdiction rule to have(12)U∣≡U↔KS,U⊲<rS⊗K,U↔KS>U∣≡S∣~<rS⊗K,U↔KS>With (12) andA7, we applyfreshness rule to have(13)U∣≡#rS⊗K,U∣≡S∣~<rS⊗K,U↔KS>U∣≡#<rS⊗K,U↔KS>
With (12) and (13), we applynonce-verification rule to have(14)U∣≡S∣~<rS⊗K,U↔KS>,U∣≡#<rS⊗K,U↔KS>U∣≡S∣≡<rS⊗K,U↔KS>
With (14), we applybelieve rule to have(15)U∣≡S∣≡<rS⊗K,U↔KS>U∣≡S∣≡U↔IDSSo, withA2 andA7 we successfully demonstrate how our scheme satisfiesLemma3. In short, with three lemmas we can say that both server and user believe and successfully share their identities with each other. Next, we need to prove the similar thing for session key.Lemma 4.
If the user believes that authentication key is successfully shared with server and server’s messages encrypted with this key are fresh, the user will believe the server also believes session key is successfully shared with each other.(16)U∣≡U↔KS,U∣≡#rS⊗KU∣≡S∣≡S↔SKUProof.
WithA2 and MUS, we applymessage-meaning rule to have(17)U∣≡U↔KS,U⊲<U↔KS,U↔skS>U∣≡S∣~<U↔KS,U↔skS>
WithA7 and MUS, we applyfreshness rule to have(18)U∣≡#rS⊗K,U⊲<U↔KS,U↔skS>U∣≡#<U↔KS,U↔skS>
With (17) and (18), we applybelieve rule to have(19)U∣≡S∣~<U↔KS,U↔skS>,U∣≡#<U↔KS,U↔skS>U∣≡S∣≡<U↔KS,U↔skS>
With (19), we applybelieve rule to have(20)U∣≡S∣≡<U↔KS,U↔skS>U∣≡S∣≡S↔skU
So, withA2 andA7 we successfully demonstrate how our scheme satisfiesLemma4.Lemma 5.
If the user believes the server totally controls session key’s sharing and the server also believes session key is successfully shared with user, the user will believe this session key’s sharing.(21)U∣≡S⇒U↔SKS,U∣≡S∣≡S↔SKUU∣≡U↔SKSProof.
WithA3 andLemma4, we applyjurisdiction rule to have(22)U∣≡S⇒U↔skS,U∣≡S∣≡S↔skUU∣≡U↔skS
So, withA3 andLemma4, we successfully demonstrate how our scheme satisfiesLemma5.Lemma 6.
If the server believes authentication key is successfully shared with user and the user’s messages encrypted with this key are fresh, the server will believe the user also believes this session key’s sharing.(23)S∣≡S↔KU,S∣≡#rU⊗KS∣≡U∣≡U↔SKSProof.
WithA6 andMUS, we applymessage-meaning rule to have(24)S∣≡S↔KU,S⊲<U↔KS,U↔skS>S∣≡U∣~<U↔KS,U↔skS>
WithA8 andMUS, we applyfreshness rule to have(25)S∣≡#rU⊗AID,S⊲<U↔KS,U↔skS>S∣≡#<U↔KS,U↔skS>
With (24) and (25), we applynonce-verification to have(26)S∣≡U∣~<U↔KS,U↔skS>,S∣≡#<U↔KS,U↔skS>S∣≡U∣≡<U↔KS,U↔skS>
WithA6 and (26), we applybelieve rule to have(27)S∣≡S↔KU,S∣≡U∣≡<U↔KS,U↔skS>S∣≡U∣≡U↔skS
So, withA6 andA8, we successfully demonstrate how our scheme satisfiesLemma6.Lemma 7.
If the server believes the user totally controls the session key’s sharing, the server will believe the session key is successfully shared with user.(28)S∣≡U⇒U↔SKSS∣≡S↔skUProof.
With (26) andA5, we applymessage-meaning rule to have(29)S∣≡U⇒U↔skS,S∣≡U∣≡<U↔KS,U↔skS>S∣≡<U↔KS,U↔skS>
With (29), we applybelieve rule to have(30)S∣≡<U↔KS,U↔skS>S∣≡S↔skUSo, withA5 we completely demonstrate how our scheme satisfiesLemma7. Finally, we can say that both server and user believe the common session key in our scheme.


## 5.2. Security Analysis

Before getting into details about some kinds of attacks, we will use random oracle model to prove the security for the session key inChebyshev polynomial case (see [27, 28] for more details). At first, we need to remind the model’s circumstance. Assuming another actorB has Ω = Tp(x),Tq(x)) andBneeds to computeTp×q(x),Bhas someoraclesClient andServer with all their instances at different times.Balso has an algorithmA being able to break our scheme to compute the session key with given probability ε.B will useA to find the session key and then computeTp×q(x) to solve CMDHP. To achieve this,B must “inject” Ω’s parameters into the messages whenA interacts with the oracles’ instances, andB also simulates an appropriate environment suitable forA to operate. Note that our scheme uses hash function and it is considered as an oracle. Next, we claim our theorem about the session key’s security.Theorem 8.
LetA be an adversary breaking our scheme in the meaning ofAKESecurity in timetA, usingqSendSend queries andqHashHash queries. We have(31)AdvPAKEA,tA,qSend,qHash≤qHash×qSend×AdvEFqECDHPCMDHPB,tB,qSend,qHash
whereB is an adversary breaking CMDHP in tB. The meaning of theorem is thatA’s successful probability breaking our scheme in the meaning ofAKESecurity is less thanB’s successful probability breaking CMDHP. According to CMDHP,B’s success probability is extremely low, and so isA’s successful probability breaking our scheme. Therefore, we can claim that our scheme has secure session key in the meaning ofAKESecurity.Proof.
Assume that we have actorB. This time,B needs to create some instances of oraclesClient andServer with Ω’s parameter.B also simulates an appropriate environment whereA can operate.
WhenA sendsSend(“Start”) to Uxi∈Client, Uxi repliesm1 toA (note thatm1 = identity encrypted,challenge information,confirmation depends on concrete scheme). Maybe,A sendsSend(“Start”) to some simulated oracle, for example, UBv. This time,B needs to inject Ω’s parameters intom1 with concrete scheme’s rules. Finally,B sendsm1 toA. WhenA sendsSend(m1) to Syj∈Server, Syj repliesm2 toA (note thatm2 = confirmation,challenge information depends on concrete scheme). Maybe,A sendsSend(m1) to simulated oracle SBv. This time,B also needs to inject Ω’s parameters intom2 and sendsm2 toA. WhenA sendsSend(m2) to Syj∈Server, Syj repliesm3 = final confirmation toA. Maybe,A sendsSend(m2) to simulated oracle SBv.B randomly choosessk←$0,1n, computesfinal confirmation message with this randomsk, and sendsm3 toA.
Sometimes,A sends wrongSend queries to the instances, so there are some oracles with“Accept” state and some oracles with “Reject” state. However, whenA finishes sending qSendSend queries, all instancesA interacts with must have“Terminated” state which istrue.
WhenA sendsCorrupt andReveal queries to these instances, their state will determine whatA obtains, such as long-term key or session key. WhenA sendsCorrupt andReveal queries to the oraclesB simulates,B will generate a random string representing session key for them. WhenA sendshash queries,B will let hash’soracle interact withA.
Finally,B activatesA to sends a uniqueTest query to simulated oracle or indicated oracle, andB expectsA to correctly guess bitb of this instance. In other words,B wantsA to correct guess this instance’s session key withA’s successful probability. We see that ifB is success, B needs three following consecutive factors:
(i)B needsA to correctly findsk of simulated oracle, andA’s successful probability is ε = AdvPAKE(A,tA).
(ii) Furthermore, whenA correctly findssk=h(Tp×q(x)…),A had found “Tp×q(x)” satisfying with thissk. Clearly, ifA sends qHash queries to hash’s oracle, there is at least one-timeA succeeds. So, γ ≥ 1/qHash. (Note that: the session keysk will be always computed with hash function.)
(iii) Next, whenA correctly finds Tp×q(x),A must correct guessq ors. Clearly, ifA sends qSend queries to the oracle, there is at least one-timeA succeeds. So, μ ≥ 1/qSend.
Finally, we haveAdvE(Fq)ECDHP(CMDHP)(B, tB, qSend, qHash) = ε × γ × μ ≥ ε × 1/qHash∗qSend ⇒ qSend × qHash × AdvE(Fq)ECDHP(CMDHP)(B, tB, qSend, qHash) ≥ ε = AdvPAKE(A, tA, qSend, qHash).In this subsection, we analyse our scheme on security aspect (see Table2).(1)
Password-guessing attack. If the smartcard’s information is leaked, and the adversary can exploit to perform password-guessing attack. Therefore, the adversary has Vi =h(Bi ∥N) in the smartcard. Differently from password,Bi is the user’s biometrics and it cannot be predicted. In short, our scheme easily resists this kind of attack.(2)
Replay attack. In this kind of attack, the adversary can replay the login message to impersonate the user. In our scheme, the adversary can replay Xi,CID,Mi,R′ to the server. Then, the server replies S′,MS to the adversary. At this time, the adversary cannot computeMUS becauseRi = Tri(AIDi) modp is impossible to know. Therefore, our scheme can resist this kind of attack.(3)
User anonymity. In this kind of attack, the adversary eavesdrops Xi,CID,Mi,R′, S′,MS and MUS of another user. The user’s identity is encrypted withRi, which includes the secretAIDi. Therefore, the adversary cannot trace who is authenticating and our scheme provides user anonymity.(4)
Impersonation attack. In this kind of attack, the adversary can impersonate either user or server. In our scheme, the adversary eavesdrops Xi,CID,Mi,R′ and S′, MS. However, he must sendMUS to cheat the server and this is impossible becauseri andAIDi are secret. Moreover, if he wants to impersonate the server, he needs to computeMS and this is impossible becauseAIDi is secret. Therefore, our scheme can resist this kind of attack(5)
Man-in-the-middle attack. In this kind of attack, the adversary can cheat both user and server simultaneously. However, he must compute random valuesri andAIDi. From this information, he can deriveRi to cheat the server and deriveMUS to cheat the user. Clearly, this information is secret, and the adversary cannot steal them.(6)
Parallel attack. In this kind of attack, the adversary uses another session’s messages to exploit the others. In our scheme, this is impossible because each session has different random values. For example, another session has the unique valuesri andrS, so all sessions have no relationship with each other.(7)
Two-factor attack. In this kind of attack, the adversary can steal the user’s biometrics, and then use this information to compute authentication key. We see that the smartcard includes N,Vi,hAIDi, Xi, so if there is no Bi, the adversary cannot computeAIDi. Of course, if the smartcard is well-protected, the adversary has no way to computeAIDi. Our scheme can resist this kind of attack.(8)
Perfect secrecy. In this kind of attack, the adversary has all secret keys of the users and the server. Of course, the service must be stopped at this time. However, we need to prevent the adversary from knowing past-transactions, and this means that all session keys must be secret. In our scheme, the session key is constructed fromri,rS, andAIDi. Clearly, if the adversary knows Tri(AIDi) and TrS(AIDi), he cannot compute Tri(TrS(AIDi)) because of facing with CMDHP.Table 2
The security feature comparison among the schemes.
Kinds of attack Lin[23] Zhu[24] Ours Password-guessing ✘ ✔ ✔ Replay ⌀1 ✔ ✔ User anonymity ✔ ⌀ ✔ Impersonation ✔ ✔ ✔ Man-in-the-middle ⌀ ⌀ ✔ Parallel ⌀ ⌀ ✔ Two-factor ✘ ✔ ✔ Perfect secrecy session key ⌀ ✘ ✔ 1The authors do not consider.


## 5.3. Efficiency Analysis

To compare efficiency between our scheme and previous ones, we let “h” be the hash operation, “e/d” be the encryption/decryption, and “T” be computational operation of polynomial. At registration phase, our scheme uses 4 ×h and 2 ×T. Lin’s scheme uses 1 ×h, 1 ×T, and 1×e/d. Zhu’s scheme uses 5 ×h. At authentication phase, our scheme uses 14 ×h and 8 ×T. Lin’s scheme uses 4 ×h, 5 ×T, and 5 ×e/d. Zhu’s scheme uses 9 ×h, 3 ×T, and 2 ×e/d. Our scheme’s computational cost is more than previous ones due to security enhancement (see Table 3).Table 3
The efficiency comparison among the schemes.
The phases Lin[23] Zhu[24] Ours Registration 1×h+1×T+1×e/d 5×h 4×h+2×T Authentication 4×h+5×T+5×e/d 9×h+3×T+2×e/d 14×h+8×TAlso, we letth,tT, andte/d denote running-time corresponding to each operation, for example,h,T, ande/d (th ≪te/d <tT). To relatively measure the running-time of three operations, we conduct an experiment usingJava Cryptography Architecture withBouncy Castle library inAndroid mobile device, core 4 CPU 1.2 GHz, and we haveth ≈ 0.00004ms,te/d ≈ 0.09385ms, andtT ≈ 80 ms (see Figure 5).Figure 5
The running-time of three schemes.


## 6. Conclusion

This paper proposes a Chebyshev polynomials-based scheme in client-server environment. Although, our scheme takes more time than previous ones, it is advanced and resists some popular kinds of attack. Soon, we improve some techniques to reduce time-cost for computing Chebyshev polynomials.



---

*Source: 4250743-2019-01-17.xml*