# Applying Semigroup Property of Enhanced Chebyshev Polynomials to Anonymous Authentication Protocol

Authors: Hong Lai; Jinghua Xiao; Lixiang Li; Yixian Yang
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

We apply semigroup property of enhanced Chebyshev polynomials to present an anonymous authentication protocol. This paper aims at improving security and reducing computational and storage overhead. The proposed scheme not only has much lower computational complexity and cost in the initialization phase but also allows the users to choose their passwords freely. Moreover, it can provide revocation of lost or stolen smart card, which can resist man-in-the-middle attack and off-line dictionary attack together with various known attacks.


---

## Body

## 1. Introduction

With rapid developments in limits and possibilities of communications and information transmissions, there is a growing demand of authentication protocol, which has greatly spurred research activities in authentication protocols' study. In general, the server authenticates the users by matching the user's identity and password after establishing a secure channel [1]. Since the server establishes a secure channel before asking identity/password information, an attacker can open a connection to a server thatdoes not respond when identity/password information is inquired by the server, which results in the consumption of the resources of the server. Moreover, the attacker can set up many connections and consume all the resources of the server. However, this method is vulnerable to denial of service (DoS) attack and cannot discriminate an impostor who fraudulently obtains access privileges (e.g., user's identity and password) from the real user. Later, Li and Hwang [2] proposed a biometrics-based remote user authentication scheme using smart cards. Soon, Li et al. [3, 4] improved Li and Hwang's scheme. There is no doubt that most existing authentication protocols only achieve “heuristic” security, that is, the underlying hardness assumptions of these protocols are not perfect. However, we discover the references [5–9], which contain the detection of the DDOS attacks by consuming all, or mostly, the resources of the server can be assured, providing a more hopeful line of investigation for us to future study.Later, Bellovin and Merritt [10] firstly presented a two-party password authenticated key exchange (2PAKE) protocol which permits a user and a server to establish a session key over an insecure channel to address the problem mentioned above. In their protocol, each user just shares an easy-to-remember password with the trusted server. Regretfully, Patel [11] pointed out that it was easy for an adversary to guess the passwords used for authentication in Bellovin and Merritt's protocol. In order to avoid these attacks, many 2PAKE protocols with weak passwords for authentication have been presented by the researchers [12–18]. However, in these 2PAKE protocols, every user has to share a different password with his/her peer. It is usually rather inconvenient for applications in large-scale communication environments. To surmount this weakness, three-party PAKE (3PAKE) protocols have been proposed in [19–22]. Unlike 2PAKE protocols, 3PAKE protocol is a very practical mechanism to establish secure session key through authenticating each other with a trusted server's help. There are two common weaknesses in these schemes as follows. (1) They needs more communications rounds to reduce computational load. However, as early as in 1995, Gong pointed out that the number of rounds is a key standard for weighing against the performance of a protocol. (2) The sensitive table that stores the shared secret between the server and the designed users will be an attractive target leading to potential server compromise. In 2008, Chen et al. [23] proposed a round and computation-efficient three-party authenticated key exchange protocol, which addressed the above mentioned problems. However, we find that their scheme still exist following four drawbacks. (1) It has computational efficiency problems in initialization phase. (2) User has no choice in choosing his password. (3) It cannot protect user anonymity. (4) There is no provision for revocation of lost or stolen smart card, which is susceptible to man-in-the-middle attack.Therefore, in this paper, password-based anonymous authentication protocol defined over enhanced Chebyshev polynomials is proposed. A number of outstanding mathematicians and numerical analysts have said that Chebyshev polynomials are everywhere dense in numerical analysis. There is scarcely any area of numerical analysis where Chebyshev polynomials do not drop in like surprise visitors, and indeed there are now a number of subjects in which these polynomials take a significant position in modern developments [24]. One is taken on a journey which leads into all areas of numerical analysis by studying Chebyshev polynomials. Moreover, due to the semigroup property of enhanced Chebyshev polynomials, the well-known discrete logarithm problem and the Diffie-Hellman problem are proved to hold in enhanced Chebyshev polynomials [25]. Thus, we apply semigroup property of enhanced Chebyshev polynomials to present an anonymous authentication protocol. Moreover, our proposed protocol has the following features.(1)
It has much lower computational complexity and cost in the initialization phase.(2)
It allows the users to choose their passwords freely.(3)
It can provide revocation of lost or stolen smart card, which can resist man-in-the-middle attack.(4)
There is no need to find primitive elements, large prime, and even large number.The rest of this paper is organized as follows. Section2 gives description of enhanced Chebyshev polynomials and some hard problems based on them. Section 3 briefly reviews Chen et al.'s protocol and describes its disadvantages. In Section 4, we apply semigroup property of enhanced Chebyshev polynomials to design an anonymous authentication protocol. We analyze the security of proposed scheme in Section 5, and computational efficiency analysis is made in Section 6. Finally, we conclude this paper in Section 7.


## 2. Preliminaries

In this section, we review some basic definitions concerning enhanced Chebyshev polynomials and some hard problems based on the enhanced Chebyshev polynomials [26].Definition 2.1 (Chebyshev polynomials).
The Chebyshev polynomials of degreen are defined as
(2.1)Tn(x)=cos(n×arccos(x)),{x∣-1≤x≤1},
The recurrent formulas are(2.2)Tn(x)=2xTn-1(x)-Tn-2(x),
where n≥2,T0(x)=1, and T1(x)=x.
The first few Chebyshev polynomials are(2.3)T2(x)=2x2-1,T3(x)=4x3-3x,T4(x)=8x4-8x2+1.
It can be identified that Chebyshev polynomial has the following properties:(1)
semigroup property as(2.4)Tr(Ts(x))=cosr*arccos(cos(s*arccos(x)))=cosrs*arccos(x)=Ts(Tr(x))=Trs(x),(2)
chaotic property,Whenn>1, Chebyshev polynomials map Tn(x):[-1,1]→[-1,1] of degree n is a chaotic map with its invariant density as
(2.5)f*(x)=1π1-x2,
for Lyapunov exponent λ=lnn>0.Definition 2.2 (enhanced Chebyshev polynomials).
In order to enhance the property of the Chebyshev chaotic map, Zhang [27] proved that the semigroup property holds for Chebyshev polynomials defined on interval (-∞,+∞). This paper uses the following enhanced Chebyshev polynomials:
(2.6)Tn(x)=2xTn-1(x)-Tn-2(x)(modN),
where n≥2,x∈(-∞,+∞), and N is a large prime number. Obviously,
(2.7)Tr(Ts(x))=Ts(Tr(x))=Trs(x).
So the semigroup property still holds and the enhanced Chebyshev polynomials also commute under composition.Definition 2.3 (the discrete logarithm problem (DLP)).
DLP is explained by the following. Given an elementα, find the integer r, such that Tr(x)=α.Definition 2.4 (the Diffie-Hellman problem (DHP)).
DHP is explained by the following. Given an elementx, and the values of Tr(x), Ts(x), what is the value of Trs(x)?


## 3.   Review of Chen et al.'s Protocol

This section reviews Chen et al.'s protocol (showed in Figure1). Some of the notations used in this protocol are defined in Table 1.Table 1
Some of the notations used in Chen et al.'s protocol.
Symbol
Definition
I
D
A
,
I
D
B
Identities of usersA and B, respectively
I
D
S
Identity of the authentication serverS
p
,
q
,
g
The large primesp and q, a generator g of group G with the order q
x
,
y
The long-term key ofS, and y=gxmodp
δ
A
,
δ
B
Components of authentication informationVA and VB
a
,
b
Random number privately chosen byA and B, respectively
R
A
,
R
B
Components of session key, whereRA=gamodp and RB=gbmodp
h
(
·
)
Collision-free one-way hash function
C
X
Y
Evidence generated by userX for user YFigure 1
Authenticated key exchange phase in Chen et al.'s protocol.


### 3.1. Initialization Phase

In this phase,A and B ought to register with S to be legal participants, and S should choose issue secret keys, which will be used in the subsequent phase. Through taking A for an example, S executes the following steps to authorize A.(1)
Randomly choose1≤δA<q and calculate VA=h(IDA,δA).(2)
Generate signature(eA,sA) as A's self-verified token, where  rA=gδAmodp, eA=h(rA,IDA), and sA=(δA-xeA)modq.(3)
Store the authentication information(VA,(eA,sA)) into a smart card and then deliver it to A in a secure way.To test whether(eA,sA) is authorized by S, A retrieves rA′ as rA′=gsA·yeAmodp, and then verifies h(rA′,IDA)=?eA.Similarly, afterB obtains the authorization information (VB,(eB,sB)) stored in the smart card from S, he can ensure that whether (eB,sB) is valid by using the method mentioned above.


### 3.2. Authentication key Exchange Phase

This phase aims to establish the session keySK with S's help. It just needs three rounds to achieve this goal.Round 1:
(3.1)
A
→
S
:
(
I
D
A
,
I
D
B
,
W
A
)
,
A
→
B
:
(
I
D
A
,
T
A
,
R
A
)
.
(1)
Randomly choose an integera and compute RA=gamod   p, CAS=h(IDA,IDB,TA,RA,VA), then transmits IDA,IDB and WA=(CAS,TA,RA,(eA,sA)) to S; where TA is the time stamp obtained by A from the local clock to ensure the freshness of the message.
(2)
A transmits IDA,TA and RA to B.Round 2:
(3.2)
B
→
S
:
(
I
D
B
,
I
D
A
,
W
B
)
,
B
→
A
:
(
I
D
B
,
T
B
,
R
B
,
C
B
A
)
.
After receiving the message from A, B does the following steps.(1)
Randomly choose an integerb and compute RB=gbmodp, CBS=h(IDB,IDA,TB,RB,VB), and send WB=(CBS,TB,RB,(eB,sB)) to S, where TB is the time stamp obtained by B from the local clock to ensure the freshness of the message.(2)
Calculate the session keySK=(RA)bmodp and then transmit CBA=h(TA,RA,RB,SK) to A.Round 3:
(3.3)
S
→
A
:
C
S
A
,
S
→
B
:
C
S
B
,
A
→
B
:
C
A
B
.
In this round, S does the following steps.(1)
Verify whetherTA is fresher than the one received in the last request. If so, apply x to computing δA′=(sA+xeA)modq and VA′=h(IDA,δA′), and then compute CSA′=h(IDA,IDB,TA,RA,VA′). In the following, test CAS′=?CAS to authenticate the identity of A; if it holds, S calculates CSA=h(CAS,TB,RB,VA′) and transmits it to A.(2)
Test whetherTB is fresher than the one received in the last request. If so, S calculates VB′=h(IDB,δB′) and computes CBS′=H(IDA,IDB,TB,RB,VB′). Then, check CBS′=?CBS to authenticate the identity of B; if it holds, S calculates CSB=h(CBS,TA,RA,VB′) and transmits it to B.(3)
Independently,A tests whether (T-TA) is in a valid period, where T is the time when the message transmitted from B after Round 2 was received. If so, A uses the received RB to compute the session key SK′=(RB)amodp. Then, it computes CBA′=h(TA,RA,RB,SK′) and checks CBA′=?CBA to authenticate B; if it holds, A computes CAB=h(CBA,TB,SK′) and sends it to B.After this round,A tests whether (T′-TA) is in a valid period, where T′ is the time when CSA was received. If so, A calculates CSA′=h(CAS,TB,RB,VA) and tests CSA′=?CSA to verify the correctness of CSA. If it holds, A finishes this protocol.Similarly,B tests if (T′′-TB) is in a valid period, where T′′ is the time when CSB was received. If so, B calculates CSB′=h(CBS,TA,RA,VB) and tests CSB′=?CSB to verify the correctness of CSB. If it holds, B completes this protocol.


### 3.3. Disadvantages of Chen et al.'s Protocol

In this section, we argue that Chen et al.'s scheme still has four disadvantages. The detailed description of the weaknesses is as follows.


#### 3.3.1. Computational Efficiency Problem

In the initialization phase of Chen et al.'s protocol,S has to compute all the authenticated information (δA,rA,eA,sA) for A and (δB,rB,eB,sB) for B. Server has to perform two modular exponentiation operations, which are more expensive than other operations in Chen et al.'s protocol. Hence, it has low efficiency in this phase.


#### 3.3.2. Lack of User Friendliness

In Chen et al.'s scheme, the password is chosen by the serverS without the consent of A/B, thus, A/B can only passively accept the password from S. It is not practical for real life applications, such as on-line banking and e-mail subscription. Moreover, δA/δB∈[1,q] chosen by the server could be long and random (e.g., 160 bits), which might be difficult for a registered user A/B to remember easily, and it is most likely that A/B may forget this long and random password if he is not frequently using the system. Hence, Chen et al.'s scheme has lack of user friendliness.


#### 3.3.3. No Protecting User Anonymity

In authenticated key exchange phase of Chen et al.'s scheme,IDA,IDB are sent to S over insecure channel in the authentication message: (IDA,IDB,WA), (IDB,IDA,WB). In certain authentication scenarios, such as e-voting and secret online-order placement, it is fairly crucial to protect the privacy of a user. Once an attacker sniffs the communication parties involved in the authentication process, he can easily analyze the transaction being performed by users. Hence, Chen et al.'s scheme fails to provide the user anonymity in the authentication phase.


#### 3.3.4. No Provision for Revocation of Lost or Stolen Smart Card

In case the smart card is lost or stolen, the attacker may impersonate the legal user using the lost or stolen smart card, so there should be a mechanism to ensure that the system can revoke the lost or stolen smart card to avoid the possible attacks. Providing for revocation is also one of the requirements of smart card-based authentication protocols. By keeping record of valid card identifier of every registered user, the authentication system can tell the valid card from the invalid one. Regretfully, Chen et al.'s scheme ignored this feature and there is no mechanism to revoke the lost smart card. Moreover, the drawback would become catastrophic if an attacker has got the lost smart card by accident and has revealed the authentication message of a legal user by any means to login into the system for performing secure transaction, such as on-line banking and e-commerce. Thus, Chen et al.'s scheme failed to provide the important feature of smart card-based authentication for revoking the lost smart cards without changing the user's identities.


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

Due to Section3.3.4, unqualified users can easily launch a man-in-the-middle attack when the smart card is stolen. The steps of the attack is outlined in Figure 2 and explained as follows.Figure 2
Man-in-the-middle attack in Chen et al.'s protocol.Suppose an adversaryM had stolen the smart card from the legal user, then he can obtain the authenticated values VA and VB. Let RM=gmmodp be M's ephemeral public key, and m∈zp* is chosen by M. Then, he replaces CSA and CSB with CSA′ and CSB′ in Round 3. The notation “⇢” denotes the transmitted message that is manipulated by M. The purpose of M is to share a session key with A by posing as B and to share a session key with B by posing as A. The specific process is as follows.Round 1:
(3.4)
A
→
S
:
(
I
D
A
,
I
D
B
,
W
A
)
,
A
⇢
M
(
B
)
:
(
I
D
A
,
T
A
,
R
A
)
,
M
(
A
)
⇢
B
:
(
I
D
A
,
T
A
,
R
M
)
.Round 2:
(3.5)
B
→
S
:
(
I
D
B
,
I
D
A
,
W
B
)
,
B
⇢
M
(
A
)
:
(
I
D
B
,
T
B
,
R
B
,
C
B
M
)
.
M
(
B
)
⇢
A
:
(
I
D
B
,
T
B
,
R
M
,
C
M
A
)
.
When receiving the message from M(A), B calculates the session key with M(A), as SKMB=gbmmodp, CBM=h(TA,RM,RB,SKMB), then M calculates the session key with A as SKAM=gammodp, CAM=h(TA,RM,RB,SKAM).Round 3:
(3.6)
S
⇢
M
(
A
)
:
C
S
A
,
M
(
S
)
⇢
A
:
C
S
A
′
,
S
⇢
M
(
B
)
:
C
S
B
,
M
(
S
)
⇢
B
:
C
S
B
′
,
A
⇢
M
(
B
)
:
C
A
M
,
M
(
A
)
⇢
B
:
C
M
B
.
In this round, becauseM obtains the value VA, he can compute CSA′=h(CAS,TB,RM,VA) for mutual authentication with A; similarly, M can also use VB to calculate CSB′=h(CBS,TA,RM,VB) for mutual authentication with B.
When receiving the valuesCSA′ and CSB′, A and B authenticate the server using their own parameters. Then A computes CMB=h(CBM,TB,SKAM) for M(B), it confirms if CMB is valid from its own knowledge. M calculates CMB=h(CMA,TB,SKMB) and sends it to B to achieve session key agreement.
Finally,M has shared the session key SKAM=gammodp with A and SKBM=gbmmodp with B. In this case, the authenticate mechanism of the Chen et al.'s protocol does not help.


## 3.1. Initialization Phase

In this phase,A and B ought to register with S to be legal participants, and S should choose issue secret keys, which will be used in the subsequent phase. Through taking A for an example, S executes the following steps to authorize A.(1)
Randomly choose1≤δA<q and calculate VA=h(IDA,δA).(2)
Generate signature(eA,sA) as A's self-verified token, where  rA=gδAmodp, eA=h(rA,IDA), and sA=(δA-xeA)modq.(3)
Store the authentication information(VA,(eA,sA)) into a smart card and then deliver it to A in a secure way.To test whether(eA,sA) is authorized by S, A retrieves rA′ as rA′=gsA·yeAmodp, and then verifies h(rA′,IDA)=?eA.Similarly, afterB obtains the authorization information (VB,(eB,sB)) stored in the smart card from S, he can ensure that whether (eB,sB) is valid by using the method mentioned above.


## 3.2. Authentication key Exchange Phase

This phase aims to establish the session keySK with S's help. It just needs three rounds to achieve this goal.Round 1:
(3.1)
A
→
S
:
(
I
D
A
,
I
D
B
,
W
A
)
,
A
→
B
:
(
I
D
A
,
T
A
,
R
A
)
.
(1)
Randomly choose an integera and compute RA=gamod   p, CAS=h(IDA,IDB,TA,RA,VA), then transmits IDA,IDB and WA=(CAS,TA,RA,(eA,sA)) to S; where TA is the time stamp obtained by A from the local clock to ensure the freshness of the message.
(2)
A transmits IDA,TA and RA to B.Round 2:
(3.2)
B
→
S
:
(
I
D
B
,
I
D
A
,
W
B
)
,
B
→
A
:
(
I
D
B
,
T
B
,
R
B
,
C
B
A
)
.
After receiving the message from A, B does the following steps.(1)
Randomly choose an integerb and compute RB=gbmodp, CBS=h(IDB,IDA,TB,RB,VB), and send WB=(CBS,TB,RB,(eB,sB)) to S, where TB is the time stamp obtained by B from the local clock to ensure the freshness of the message.(2)
Calculate the session keySK=(RA)bmodp and then transmit CBA=h(TA,RA,RB,SK) to A.Round 3:
(3.3)
S
→
A
:
C
S
A
,
S
→
B
:
C
S
B
,
A
→
B
:
C
A
B
.
In this round, S does the following steps.(1)
Verify whetherTA is fresher than the one received in the last request. If so, apply x to computing δA′=(sA+xeA)modq and VA′=h(IDA,δA′), and then compute CSA′=h(IDA,IDB,TA,RA,VA′). In the following, test CAS′=?CAS to authenticate the identity of A; if it holds, S calculates CSA=h(CAS,TB,RB,VA′) and transmits it to A.(2)
Test whetherTB is fresher than the one received in the last request. If so, S calculates VB′=h(IDB,δB′) and computes CBS′=H(IDA,IDB,TB,RB,VB′). Then, check CBS′=?CBS to authenticate the identity of B; if it holds, S calculates CSB=h(CBS,TA,RA,VB′) and transmits it to B.(3)
Independently,A tests whether (T-TA) is in a valid period, where T is the time when the message transmitted from B after Round 2 was received. If so, A uses the received RB to compute the session key SK′=(RB)amodp. Then, it computes CBA′=h(TA,RA,RB,SK′) and checks CBA′=?CBA to authenticate B; if it holds, A computes CAB=h(CBA,TB,SK′) and sends it to B.After this round,A tests whether (T′-TA) is in a valid period, where T′ is the time when CSA was received. If so, A calculates CSA′=h(CAS,TB,RB,VA) and tests CSA′=?CSA to verify the correctness of CSA. If it holds, A finishes this protocol.Similarly,B tests if (T′′-TB) is in a valid period, where T′′ is the time when CSB was received. If so, B calculates CSB′=h(CBS,TA,RA,VB) and tests CSB′=?CSB to verify the correctness of CSB. If it holds, B completes this protocol.


## 3.3. Disadvantages of Chen et al.'s Protocol

In this section, we argue that Chen et al.'s scheme still has four disadvantages. The detailed description of the weaknesses is as follows.


### 3.3.1. Computational Efficiency Problem

In the initialization phase of Chen et al.'s protocol,S has to compute all the authenticated information (δA,rA,eA,sA) for A and (δB,rB,eB,sB) for B. Server has to perform two modular exponentiation operations, which are more expensive than other operations in Chen et al.'s protocol. Hence, it has low efficiency in this phase.


### 3.3.2. Lack of User Friendliness

In Chen et al.'s scheme, the password is chosen by the serverS without the consent of A/B, thus, A/B can only passively accept the password from S. It is not practical for real life applications, such as on-line banking and e-mail subscription. Moreover, δA/δB∈[1,q] chosen by the server could be long and random (e.g., 160 bits), which might be difficult for a registered user A/B to remember easily, and it is most likely that A/B may forget this long and random password if he is not frequently using the system. Hence, Chen et al.'s scheme has lack of user friendliness.


### 3.3.3. No Protecting User Anonymity

In authenticated key exchange phase of Chen et al.'s scheme,IDA,IDB are sent to S over insecure channel in the authentication message: (IDA,IDB,WA), (IDB,IDA,WB). In certain authentication scenarios, such as e-voting and secret online-order placement, it is fairly crucial to protect the privacy of a user. Once an attacker sniffs the communication parties involved in the authentication process, he can easily analyze the transaction being performed by users. Hence, Chen et al.'s scheme fails to provide the user anonymity in the authentication phase.


### 3.3.4. No Provision for Revocation of Lost or Stolen Smart Card

In case the smart card is lost or stolen, the attacker may impersonate the legal user using the lost or stolen smart card, so there should be a mechanism to ensure that the system can revoke the lost or stolen smart card to avoid the possible attacks. Providing for revocation is also one of the requirements of smart card-based authentication protocols. By keeping record of valid card identifier of every registered user, the authentication system can tell the valid card from the invalid one. Regretfully, Chen et al.'s scheme ignored this feature and there is no mechanism to revoke the lost smart card. Moreover, the drawback would become catastrophic if an attacker has got the lost smart card by accident and has revealed the authentication message of a legal user by any means to login into the system for performing secure transaction, such as on-line banking and e-commerce. Thus, Chen et al.'s scheme failed to provide the important feature of smart card-based authentication for revoking the lost smart cards without changing the user's identities.


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

Due to Section3.3.4, unqualified users can easily launch a man-in-the-middle attack when the smart card is stolen. The steps of the attack is outlined in Figure 2 and explained as follows.Figure 2
Man-in-the-middle attack in Chen et al.'s protocol.Suppose an adversaryM had stolen the smart card from the legal user, then he can obtain the authenticated values VA and VB. Let RM=gmmodp be M's ephemeral public key, and m∈zp* is chosen by M. Then, he replaces CSA and CSB with CSA′ and CSB′ in Round 3. The notation “⇢” denotes the transmitted message that is manipulated by M. The purpose of M is to share a session key with A by posing as B and to share a session key with B by posing as A. The specific process is as follows.Round 1:
(3.4)
A
→
S
:
(
I
D
A
,
I
D
B
,
W
A
)
,
A
⇢
M
(
B
)
:
(
I
D
A
,
T
A
,
R
A
)
,
M
(
A
)
⇢
B
:
(
I
D
A
,
T
A
,
R
M
)
.Round 2:
(3.5)
B
→
S
:
(
I
D
B
,
I
D
A
,
W
B
)
,
B
⇢
M
(
A
)
:
(
I
D
B
,
T
B
,
R
B
,
C
B
M
)
.
M
(
B
)
⇢
A
:
(
I
D
B
,
T
B
,
R
M
,
C
M
A
)
.
When receiving the message from M(A), B calculates the session key with M(A), as SKMB=gbmmodp, CBM=h(TA,RM,RB,SKMB), then M calculates the session key with A as SKAM=gammodp, CAM=h(TA,RM,RB,SKAM).Round 3:
(3.6)
S
⇢
M
(
A
)
:
C
S
A
,
M
(
S
)
⇢
A
:
C
S
A
′
,
S
⇢
M
(
B
)
:
C
S
B
,
M
(
S
)
⇢
B
:
C
S
B
′
,
A
⇢
M
(
B
)
:
C
A
M
,
M
(
A
)
⇢
B
:
C
M
B
.
In this round, becauseM obtains the value VA, he can compute CSA′=h(CAS,TB,RM,VA) for mutual authentication with A; similarly, M can also use VB to calculate CSB′=h(CBS,TA,RM,VB) for mutual authentication with B.
When receiving the valuesCSA′ and CSB′, A and B authenticate the server using their own parameters. Then A computes CMB=h(CBM,TB,SKAM) for M(B), it confirms if CMB is valid from its own knowledge. M calculates CMB=h(CMA,TB,SKMB) and sends it to B to achieve session key agreement.
Finally,M has shared the session key SKAM=gammodp with A and SKBM=gbmmodp with B. In this case, the authenticate mechanism of the Chen et al.'s protocol does not help.


## 3.3.1. Computational Efficiency Problem

In the initialization phase of Chen et al.'s protocol,S has to compute all the authenticated information (δA,rA,eA,sA) for A and (δB,rB,eB,sB) for B. Server has to perform two modular exponentiation operations, which are more expensive than other operations in Chen et al.'s protocol. Hence, it has low efficiency in this phase.


## 3.3.2. Lack of User Friendliness

In Chen et al.'s scheme, the password is chosen by the serverS without the consent of A/B, thus, A/B can only passively accept the password from S. It is not practical for real life applications, such as on-line banking and e-mail subscription. Moreover, δA/δB∈[1,q] chosen by the server could be long and random (e.g., 160 bits), which might be difficult for a registered user A/B to remember easily, and it is most likely that A/B may forget this long and random password if he is not frequently using the system. Hence, Chen et al.'s scheme has lack of user friendliness.


## 3.3.3. No Protecting User Anonymity

In authenticated key exchange phase of Chen et al.'s scheme,IDA,IDB are sent to S over insecure channel in the authentication message: (IDA,IDB,WA), (IDB,IDA,WB). In certain authentication scenarios, such as e-voting and secret online-order placement, it is fairly crucial to protect the privacy of a user. Once an attacker sniffs the communication parties involved in the authentication process, he can easily analyze the transaction being performed by users. Hence, Chen et al.'s scheme fails to provide the user anonymity in the authentication phase.


## 3.3.4. No Provision for Revocation of Lost or Stolen Smart Card

In case the smart card is lost or stolen, the attacker may impersonate the legal user using the lost or stolen smart card, so there should be a mechanism to ensure that the system can revoke the lost or stolen smart card to avoid the possible attacks. Providing for revocation is also one of the requirements of smart card-based authentication protocols. By keeping record of valid card identifier of every registered user, the authentication system can tell the valid card from the invalid one. Regretfully, Chen et al.'s scheme ignored this feature and there is no mechanism to revoke the lost smart card. Moreover, the drawback would become catastrophic if an attacker has got the lost smart card by accident and has revealed the authentication message of a legal user by any means to login into the system for performing secure transaction, such as on-line banking and e-commerce. Thus, Chen et al.'s scheme failed to provide the important feature of smart card-based authentication for revoking the lost smart cards without changing the user's identities.


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

Due to Section3.3.4, unqualified users can easily launch a man-in-the-middle attack when the smart card is stolen. The steps of the attack is outlined in Figure 2 and explained as follows.Figure 2
Man-in-the-middle attack in Chen et al.'s protocol.Suppose an adversaryM had stolen the smart card from the legal user, then he can obtain the authenticated values VA and VB. Let RM=gmmodp be M's ephemeral public key, and m∈zp* is chosen by M. Then, he replaces CSA and CSB with CSA′ and CSB′ in Round 3. The notation “⇢” denotes the transmitted message that is manipulated by M. The purpose of M is to share a session key with A by posing as B and to share a session key with B by posing as A. The specific process is as follows.Round 1:
(3.4)
A
→
S
:
(
I
D
A
,
I
D
B
,
W
A
)
,
A
⇢
M
(
B
)
:
(
I
D
A
,
T
A
,
R
A
)
,
M
(
A
)
⇢
B
:
(
I
D
A
,
T
A
,
R
M
)
.Round 2:
(3.5)
B
→
S
:
(
I
D
B
,
I
D
A
,
W
B
)
,
B
⇢
M
(
A
)
:
(
I
D
B
,
T
B
,
R
B
,
C
B
M
)
.
M
(
B
)
⇢
A
:
(
I
D
B
,
T
B
,
R
M
,
C
M
A
)
.
When receiving the message from M(A), B calculates the session key with M(A), as SKMB=gbmmodp, CBM=h(TA,RM,RB,SKMB), then M calculates the session key with A as SKAM=gammodp, CAM=h(TA,RM,RB,SKAM).Round 3:
(3.6)
S
⇢
M
(
A
)
:
C
S
A
,
M
(
S
)
⇢
A
:
C
S
A
′
,
S
⇢
M
(
B
)
:
C
S
B
,
M
(
S
)
⇢
B
:
C
S
B
′
,
A
⇢
M
(
B
)
:
C
A
M
,
M
(
A
)
⇢
B
:
C
M
B
.
In this round, becauseM obtains the value VA, he can compute CSA′=h(CAS,TB,RM,VA) for mutual authentication with A; similarly, M can also use VB to calculate CSB′=h(CBS,TA,RM,VB) for mutual authentication with B.
When receiving the valuesCSA′ and CSB′, A and B authenticate the server using their own parameters. Then A computes CMB=h(CBM,TB,SKAM) for M(B), it confirms if CMB is valid from its own knowledge. M calculates CMB=h(CMA,TB,SKMB) and sends it to B to achieve session key agreement.
Finally,M has shared the session key SKAM=gammodp with A and SKBM=gbmmodp with B. In this case, the authenticate mechanism of the Chen et al.'s protocol does not help.


## 4. An Anonymous Authentication Protocol Using Semiproperty of Enhanced Chebyshev Polynomials

To surmount serious latency security problems in the Chen et al.'s protocol, we apply semigroup property of enhanced Chebyshev polynomials to designing a new anonymous authentication protocol.


### 4.1. Notations

In the section, we describe some of the notations used in our protocol (Table2).Table 2
Some of the notations used in our paper.
Symbol
Definition
I
D
A
,
I
D
B
Identities of usersA and B, respectively
I
D
S
Identity of the authentication serverS
N
The large primeN
x
1
,
y
,
n
The long-term key ofS, and y=Tx1(x)
x
x is the seed of the enhanced Chebyshev polynomial
P
A
,
P
B
Passwords ofA and B, respectively
a
,
b
Random large integer number chosen byA and B, respectively
R
A
,
R
B
Components of session key, whereRA=Ta(x) and RB=Tb(x)
H
(
·
)
Collision resistant secure one-way chaotic hash function
C
X
Y
Evidence generated by userX for user Y


### 4.2. Initialization Phase

In this phase, the users and the server need some intercommunication for user's registration.We takeA for an example. To register with S to become a valid user A, A and S will do the following steps.(1)
A→S: (DA,IDA)A freely chooses an easy-to-remember password PA and identity IDA, then computes DA=TPA(x) and sends (DA,IDA) to S.(2)
When receivingDA from A, S first tests if DA=?DI. If DA=DI, S should ask A to submit a different password.(3)
S→A: (ΔA,H(·))Then,S computes ΔA=En(TPA(x)∥IDA), for convenience, S stores (ΔA,H(·)) into a smart card and then delivers it to A face to face.Of course,B registers with S in the same way.


### 4.3. Authentication Key Exchange Phase

This phase aims to establish a session keySK. To achieve this goal, A and B first compute VA=H(TPA(y)) and VB=H(TPB(y)) using their own passwords and the public key of S as their authentication information respectively. Note that VA,VB can be precomputed. This phase also includes three rounds (shown phase in Figure 3) and the detailed descriptions are as follows.Figure 3
Authenticated key exchange phase in our proposed protocol.Round 1:
(4.1)
A
→
S
:
(
I
D
A
,
Δ
A
,
W
A
)
A
→
B
:
(
Δ
A
,
T
A
,
R
A
)
.
(1)
CalculatesCAS=H(ΔA,TA,RA,VA) and WA=(CAS,TA,RA,ΔA), then transmits ΔA and WA to S; where the meaning of TA is the same as that in the Chen et al.'s protocol.
(2)
A transmitsΔA,TA and RA to B.Round 2:
(4.2)
B
→
S
:
(
I
D
B
,
Δ
A
,
Δ
B
,
W
B
)
B
→
A
:
(
Δ
B
,
T
B
,
R
B
,
C
B
A
)
.
On receiving the request transmitted from A, B does the following steps.(1)
Bcalculates CBS=H(ΔB,TB,RB,VB) and sends WB=(CBS,TB,RB,ΔB) to S; the meaning of TB is the same as that in the Chen et al.'s protocol.(2)
B calculates the session key SK=Tb(RA) and transmits CBA=H(TA,RA,RB,SK) to A.Round 3:
(4.3)
S
→
A
:
C
S
A
,
S
→
B
:
C
S
B
,
A
→
B
:
C
A
B
.
In this round, S does the following steps.(1)
Verify ifTA is in a valid time interval. If so, S decrypts ΔA,ΔB with his private key n to reveal TPA(x)∥IDA and TPB(x)∥IDB. Then, S calculates VA′=H(Tx1(DA)) and computes CSA′=H(ΔA,TA,RA,VA′). Finally, test CAS′=?CAS, if it holds, S calculates CSA=H(CAS,TB,RB,VA′) and transmits it to A.(2)
Test whetherTB is in a valid time interval. If so, S calculates VB′=H(Tx1(DB)) and computes CBS′=H(ΔB,TB,RB,VB′). Then, he tests CBS′=?CBS, if it holds, S calculates CSB=H(CBS,TA,RA,VB′), and transmits it to B.(3)
Independently,A tests if (T-TA) is in a valid period, where T is the time when B received the message from S. If so, A calculates SK′=Ta(RB) and CBA′=H(TA,RA,RB,SK′); then, tests CBA′=?CBA; if it holds, A calculates CAB=H(CBA,TB,SK′) and sends it to B.
After this round,A tests if (T′-TA) is in a valid period, where T′ is the time when CSA was received. If so, A calculates CSA′=H(CAS,TB,RB,VA) and tests CSA′=?CSA to verify the correctness of CSA. If it holds, A finishes this protocol.
Similarly,B tests if (T′′-TB) is in a valid period, where T′′ is the time when CSB was received. If so, B calculates CSB′=H(CBS,TA,RA,VB) and tests CSB′=?CSB to verify the correctness of CSB. If it holds, B finishes this protocol.


## 4.1. Notations

In the section, we describe some of the notations used in our protocol (Table2).Table 2
Some of the notations used in our paper.
Symbol
Definition
I
D
A
,
I
D
B
Identities of usersA and B, respectively
I
D
S
Identity of the authentication serverS
N
The large primeN
x
1
,
y
,
n
The long-term key ofS, and y=Tx1(x)
x
x is the seed of the enhanced Chebyshev polynomial
P
A
,
P
B
Passwords ofA and B, respectively
a
,
b
Random large integer number chosen byA and B, respectively
R
A
,
R
B
Components of session key, whereRA=Ta(x) and RB=Tb(x)
H
(
·
)
Collision resistant secure one-way chaotic hash function
C
X
Y
Evidence generated by userX for user Y


## 4.2. Initialization Phase

In this phase, the users and the server need some intercommunication for user's registration.We takeA for an example. To register with S to become a valid user A, A and S will do the following steps.(1)
A→S: (DA,IDA)A freely chooses an easy-to-remember password PA and identity IDA, then computes DA=TPA(x) and sends (DA,IDA) to S.(2)
When receivingDA from A, S first tests if DA=?DI. If DA=DI, S should ask A to submit a different password.(3)
S→A: (ΔA,H(·))Then,S computes ΔA=En(TPA(x)∥IDA), for convenience, S stores (ΔA,H(·)) into a smart card and then delivers it to A face to face.Of course,B registers with S in the same way.


## 4.3. Authentication Key Exchange Phase

This phase aims to establish a session keySK. To achieve this goal, A and B first compute VA=H(TPA(y)) and VB=H(TPB(y)) using their own passwords and the public key of S as their authentication information respectively. Note that VA,VB can be precomputed. This phase also includes three rounds (shown phase in Figure 3) and the detailed descriptions are as follows.Figure 3
Authenticated key exchange phase in our proposed protocol.Round 1:
(4.1)
A
→
S
:
(
I
D
A
,
Δ
A
,
W
A
)
A
→
B
:
(
Δ
A
,
T
A
,
R
A
)
.
(1)
CalculatesCAS=H(ΔA,TA,RA,VA) and WA=(CAS,TA,RA,ΔA), then transmits ΔA and WA to S; where the meaning of TA is the same as that in the Chen et al.'s protocol.
(2)
A transmitsΔA,TA and RA to B.Round 2:
(4.2)
B
→
S
:
(
I
D
B
,
Δ
A
,
Δ
B
,
W
B
)
B
→
A
:
(
Δ
B
,
T
B
,
R
B
,
C
B
A
)
.
On receiving the request transmitted from A, B does the following steps.(1)
Bcalculates CBS=H(ΔB,TB,RB,VB) and sends WB=(CBS,TB,RB,ΔB) to S; the meaning of TB is the same as that in the Chen et al.'s protocol.(2)
B calculates the session key SK=Tb(RA) and transmits CBA=H(TA,RA,RB,SK) to A.Round 3:
(4.3)
S
→
A
:
C
S
A
,
S
→
B
:
C
S
B
,
A
→
B
:
C
A
B
.
In this round, S does the following steps.(1)
Verify ifTA is in a valid time interval. If so, S decrypts ΔA,ΔB with his private key n to reveal TPA(x)∥IDA and TPB(x)∥IDB. Then, S calculates VA′=H(Tx1(DA)) and computes CSA′=H(ΔA,TA,RA,VA′). Finally, test CAS′=?CAS, if it holds, S calculates CSA=H(CAS,TB,RB,VA′) and transmits it to A.(2)
Test whetherTB is in a valid time interval. If so, S calculates VB′=H(Tx1(DB)) and computes CBS′=H(ΔB,TB,RB,VB′). Then, he tests CBS′=?CBS, if it holds, S calculates CSB=H(CBS,TA,RA,VB′), and transmits it to B.(3)
Independently,A tests if (T-TA) is in a valid period, where T is the time when B received the message from S. If so, A calculates SK′=Ta(RB) and CBA′=H(TA,RA,RB,SK′); then, tests CBA′=?CBA; if it holds, A calculates CAB=H(CBA,TB,SK′) and sends it to B.
After this round,A tests if (T′-TA) is in a valid period, where T′ is the time when CSA was received. If so, A calculates CSA′=H(CAS,TB,RB,VA) and tests CSA′=?CSA to verify the correctness of CSA. If it holds, A finishes this protocol.
Similarly,B tests if (T′′-TB) is in a valid period, where T′′ is the time when CSB was received. If so, B calculates CSB′=H(CBS,TA,RA,VB) and tests CSB′=?CSB to verify the correctness of CSB. If it holds, B finishes this protocol.


## 5. Security Analysis

The enhanced scheme is a modified form of the Chen et al.'s scheme. Hence, we just discuss the enhanced and some important security features of the proposed scheme instead of discussing the security analysis that has been already shown in [23]. Before analyzing the security properties, we stress the following two facts to prove security that authenticated key agreement protocol should meet. (1) It is widely believed that there is no polynomial-time algorithm to solve DLP and DHP based on enhanced Chebyshev polynomials with nonnegligible probability. (2) The chaotic hash function has collision-free and irreversible properties.


### 5.1. Securely Chosen and Update Password

In our proposed scheme,A/B is able to freely choose and change his password without any hassle of contacting the server S. Any users except A/B cannot change or update the password without knowing the corresponding valid IDA/IDB and PA/PB of the smart card holder.


### 5.2. Revocation of Smart Card

In our proposed scheme, if(A/B)'s smart card is stolen or lost, he can request the server S to revoke his smart card for future use. S can revoke the smart card directly. If an adversary who steals (A/B)'s smart card wants to derive PA from ΔA=En(TPA(x)∥IDA),  this will be impossible, because just S knows the secret key n, and he is faced with the discrete logarithm problem (DLP) too. Hence, the old smart card becomes useless for future use.


### 5.3. The Proposed Protocol Can Resist Man-in-the-Middle Attack

Due toVA=H(TPA(y))=H(Tx1(DA)), if the adversary attempts to login to S, it needs to derive x1/PA from y/ΔA. However, it is widely believed that there is no polynomial-time algorithm to solve DLP based on enhanced Chebyshev polynomials with nonnegligible probability. Moreover, because just S knows the secret key n, he even cannot obtain DA. So the adversary cannot compute VA. Due to the same reason, the adversary cannot calculate VB either, that is, our protocol can resist man-in-the-middle attack.


### 5.4. Protection of User Anonymity

The anonymity feature of users is that the real identity of user should be protected from being revealed by any other entity exceptS. Our protocol can preserve the identity anonymity for any user which can be explained as follows.I
D
A is hidden in ΔA=En(TPA(x)∥IDA). Because just S knows the secret key n, even if adversary can obtain ΔA from the stolen smart card, he still cannot decrypt ΔA.


### 5.5. The Proposed Protocol Can Provide Mutual Authentication

Similarly to Chen et al.'s scheme, we analyze this property from three aspects: authentications amongA, B, and S.Case 1.
A and B To authenticate A, S needs to suppose that they own the same session key. In this protocol, S is responsible for confirming both the origin and integrity of the received message in step (2) to help them authenticate each other. S ensures that the received messages TA,RA,VA and TB,RB,VB are truly sent from A and B, respectively, and that no modification has occurred. Meanwhile, S sends the respective evidence CSA and CSB for the origin and the integrity of (TA,RA) and (TB,RB). Based on the premise that S is trustworthy, A/B is convinced that the origin of (TB,RB)/(TA,RA) is B/A when the validity of CSA/CSB is verified. As only A/B knows the secret a/b of RA/RB, the common session key is generated by A/B as Ta(RB)/Tb(RA). Because the session key is only known by A/B, no one can forge a valid CBA=H(TA,RA,RB,SK) or CAB=H(CBA,TB,SK′). Therefore, mutual authentication between A and B is achieved while the session key confirmation is guaranteed.Case 2.
A and S To achieve the mutual authentication between A and S, on the one hand, S has to verify the validity of the evidence CAS=H(ΔA,TA,RA,VA). On the other hand, A must test the validity of CSA=H(CAS,TB,RB,VA′) to authenticate S. These evidences are computed with the common secret key. Because only A and S know the common secret key VA, where VA equals VA′, no one can counterfeit the evidence. When validity of CAS and CSA is tested by S and A, respectively, the integrity of the transmitted message from S that contains TA,RA is confirmed by S and the integrity of evidence CSA from S is confirmed by A. Thus, mutual authentication between A and S is achieved.Case 3.
B and S The analysis of the mutual authentication between B and S is done likewise. Except B and S, no one knows the secret key VB. Therefore, mutual authentication between B and S is achieved by verifying the validity of CBS=H(ΔB,TB,RB,VB) and CSB=H(CBS,TA,RA,VB′), respectively.


### 5.6. The Proposed Protocol Can Resist Bergamo et al.'s Attack

In addition, because our protocol is based on semigroup property of enhanced Chebyshev polynomials, we should consider Bergamo et al.'s attack [20]. Bergamo et al.'s attack is based on the condition that an adversary can obtain the related elements x,N,Ta(x) and Tb(x). In the proposed protocol, an attacker could get x and N easily, but they cannot obtain Ta(x) and Tb(x), even though the attacker is a legal user. Besides, the proposed protocol utilizes the enhanced Chebyshev polynomials, in which the periodicity of the cosine function is avoided by extending the interval of x from (-1,+1) to (-∞,+∞). Therefore, the attacker have no way to perform a successful attack using Bergamo et al.'s method.


### 5.7. The Proposed Protocol Can Resist Off-Line Dictionary Attack

In the off-line dictionary attack, the adversary can recode all transmitted messages in the initialization phase and attempt to guess usingA's/B's identities IDA/IDB and passwords PA/PB from the recorded massages. An attacker tries to obtain identity and password verification information from ΔA, he must guess n,PA,IDA correctly at the same time. However, the probability of guessing the three numbers correctly in the same attempt is nearly zero. Furthermore, even if the attacker guesses one parameter correctly, he or she cannot verify it with any password verifier information. Hence, the proposed protocol is secure against off-line dictionary attack.According to the above analysis, we list the security properties' comparison of Chen et al.'s protocol and our protocol in Table3.Table 3
Comparison of security properties.
Security properties
Chen et al.’s protocol
Our protocol
Anonymity
No
Yes
Man-in-the-middle attack
No
Yes
DoS attack
Yes
Yes
Mutual authentication among three parties
Yes
Yes
Perfect forward secrecy
Yes
Yes
Provision for revocation of lost or stolen smart card
No
Yes
Insider attack
Yes
Yes
User friendliness
No
Yes
Replay attack
Yes
Yes


## 5.1. Securely Chosen and Update Password

In our proposed scheme,A/B is able to freely choose and change his password without any hassle of contacting the server S. Any users except A/B cannot change or update the password without knowing the corresponding valid IDA/IDB and PA/PB of the smart card holder.


## 5.2. Revocation of Smart Card

In our proposed scheme, if(A/B)'s smart card is stolen or lost, he can request the server S to revoke his smart card for future use. S can revoke the smart card directly. If an adversary who steals (A/B)'s smart card wants to derive PA from ΔA=En(TPA(x)∥IDA),  this will be impossible, because just S knows the secret key n, and he is faced with the discrete logarithm problem (DLP) too. Hence, the old smart card becomes useless for future use.


## 5.3. The Proposed Protocol Can Resist Man-in-the-Middle Attack

Due toVA=H(TPA(y))=H(Tx1(DA)), if the adversary attempts to login to S, it needs to derive x1/PA from y/ΔA. However, it is widely believed that there is no polynomial-time algorithm to solve DLP based on enhanced Chebyshev polynomials with nonnegligible probability. Moreover, because just S knows the secret key n, he even cannot obtain DA. So the adversary cannot compute VA. Due to the same reason, the adversary cannot calculate VB either, that is, our protocol can resist man-in-the-middle attack.


## 5.4. Protection of User Anonymity

The anonymity feature of users is that the real identity of user should be protected from being revealed by any other entity exceptS. Our protocol can preserve the identity anonymity for any user which can be explained as follows.I
D
A is hidden in ΔA=En(TPA(x)∥IDA). Because just S knows the secret key n, even if adversary can obtain ΔA from the stolen smart card, he still cannot decrypt ΔA.


## 5.5. The Proposed Protocol Can Provide Mutual Authentication

Similarly to Chen et al.'s scheme, we analyze this property from three aspects: authentications amongA, B, and S.Case 1.
A and B To authenticate A, S needs to suppose that they own the same session key. In this protocol, S is responsible for confirming both the origin and integrity of the received message in step (2) to help them authenticate each other. S ensures that the received messages TA,RA,VA and TB,RB,VB are truly sent from A and B, respectively, and that no modification has occurred. Meanwhile, S sends the respective evidence CSA and CSB for the origin and the integrity of (TA,RA) and (TB,RB). Based on the premise that S is trustworthy, A/B is convinced that the origin of (TB,RB)/(TA,RA) is B/A when the validity of CSA/CSB is verified. As only A/B knows the secret a/b of RA/RB, the common session key is generated by A/B as Ta(RB)/Tb(RA). Because the session key is only known by A/B, no one can forge a valid CBA=H(TA,RA,RB,SK) or CAB=H(CBA,TB,SK′). Therefore, mutual authentication between A and B is achieved while the session key confirmation is guaranteed.Case 2.
A and S To achieve the mutual authentication between A and S, on the one hand, S has to verify the validity of the evidence CAS=H(ΔA,TA,RA,VA). On the other hand, A must test the validity of CSA=H(CAS,TB,RB,VA′) to authenticate S. These evidences are computed with the common secret key. Because only A and S know the common secret key VA, where VA equals VA′, no one can counterfeit the evidence. When validity of CAS and CSA is tested by S and A, respectively, the integrity of the transmitted message from S that contains TA,RA is confirmed by S and the integrity of evidence CSA from S is confirmed by A. Thus, mutual authentication between A and S is achieved.Case 3.
B and S The analysis of the mutual authentication between B and S is done likewise. Except B and S, no one knows the secret key VB. Therefore, mutual authentication between B and S is achieved by verifying the validity of CBS=H(ΔB,TB,RB,VB) and CSB=H(CBS,TA,RA,VB′), respectively.


## 5.6. The Proposed Protocol Can Resist Bergamo et al.'s Attack

In addition, because our protocol is based on semigroup property of enhanced Chebyshev polynomials, we should consider Bergamo et al.'s attack [20]. Bergamo et al.'s attack is based on the condition that an adversary can obtain the related elements x,N,Ta(x) and Tb(x). In the proposed protocol, an attacker could get x and N easily, but they cannot obtain Ta(x) and Tb(x), even though the attacker is a legal user. Besides, the proposed protocol utilizes the enhanced Chebyshev polynomials, in which the periodicity of the cosine function is avoided by extending the interval of x from (-1,+1) to (-∞,+∞). Therefore, the attacker have no way to perform a successful attack using Bergamo et al.'s method.


## 5.7. The Proposed Protocol Can Resist Off-Line Dictionary Attack

In the off-line dictionary attack, the adversary can recode all transmitted messages in the initialization phase and attempt to guess usingA's/B's identities IDA/IDB and passwords PA/PB from the recorded massages. An attacker tries to obtain identity and password verification information from ΔA, he must guess n,PA,IDA correctly at the same time. However, the probability of guessing the three numbers correctly in the same attempt is nearly zero. Furthermore, even if the attacker guesses one parameter correctly, he or she cannot verify it with any password verifier information. Hence, the proposed protocol is secure against off-line dictionary attack.According to the above analysis, we list the security properties' comparison of Chen et al.'s protocol and our protocol in Table3.Table 3
Comparison of security properties.
Security properties
Chen et al.’s protocol
Our protocol
Anonymity
No
Yes
Man-in-the-middle attack
No
Yes
DoS attack
Yes
Yes
Mutual authentication among three parties
Yes
Yes
Perfect forward secrecy
Yes
Yes
Provision for revocation of lost or stolen smart card
No
Yes
Insider attack
Yes
Yes
User friendliness
No
Yes
Replay attack
Yes
Yes


## 6. Computational Efficiency Analysis

The proposed protocol is achieved through DLP and DHP problems based on enhanced Chebyshev polynomials. It enjoys the following advantages.(1) In the initial phase, we take A for example, S only needs to test DA=?DI, where DI denotes the users' component of authentication information and computes ΔA. However, in Chen et al.'s protocol, S has to compute (VA,rA,eA,sA). In a word, our protocol greatly reduces the computational complexity and computational cost. Hence, our scheme is more efficient and practical. (2)VA′,VB′ can be precomputed off-line in our protocol, which improves the computational efficiency and saves communication bandwidth. The detailed comparison is shown in Table 4.Table 4
Comparison of computation overhead in initialization phase.
Chen et al.'s protocol
Our protocol
Random number (A/B/S)
0/0/0
1/1/0
Symmetric encryption/decryption (A/B/S)
0/0/0
0/0/2
Modular exponentiation (A/B/S)
1/1/2
0/0/0
Hash operation (A/B/S)
1/1/4
1/1/2
Chebyshev polynomial computing (A/B/S)
0/0/0
1/1/0


## 7. Conclusion

In this paper, we have applied semigroup property of enhanced Chebyshev polynomials to present a novel authenticated key exchange protocol. To the best of our knowledge, it is the first time to realize three-party authenticated key exchange protocol preserving user anonymity with semigroup property of enhanced Chebyshev polynomials. First, we argued that Chen et al.'s protocol has computational efficiency problem in initialization phase and cannot protect user anonymity, user has no choice in choosing his password, and there is no provision for revocation of lost or stolen smart card leading to man-in-the-middle attack. To surmount these identified drawbacks, we have proposed an enhanced protocol to reduce computational complexity and computational cost in initialization phase and improve security. Hence, our proposed protocol is more efficient and practical. Furthermore, analysis shows that our protocol can resist various kinds of attacks.



---

*Source: 454823-2012-09-23.xml*