# Applying LU Decomposition of Matrices to Design Anonymity Bilateral Remote User Authentication Scheme

Authors: Xiong Li; Jianwei Niu; Muhammad Khurram Khan; Zhibo Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We apply LU decomposition of matrices to present an anonymous bilateral authentication scheme. This paper aims at improving security and providing more excellent performances for remote user authentication scheme. The proposed scheme can provide bilateral authentication and session key agreement, can quickly check the validity of the input password, and can really protect the user anonymity. The security of the proposed scheme is based on the discrete logarithm problem (DLP), Diffie-Hellman problem (DHP), and the one-way hash function. It can resist various attacks such as insider attack, impersonation attack, server spoofing attack, and stolen smart card attack. Moreover, the presented scheme is computationally efficient for real-life implementation.


---

## Body

## 1. Introduction

The remote user authentication scheme allows the user and the remote server to mutually authenticate each other over public network environments, and then the authorized user can access the services and resources which are provided by the remote server. Generally, the password-based authentication scheme provides an efficient and secure way for mutual authentication and allows the user and the server to establish a shared session key for future secret communication after the mutual authentication process. In 1981, Lamport [1] first proposed a password-based remote user authentication scheme for the insecure communication. Since then, the researchers have proposed many password-based remote user authentication schemes [2–7] to ensure the secure communication through the public network, and also many studies [8–18] have been presented to enhance the security or improve the computation and communication costs of the remote user authentication scheme.In the public network environments, it is important to ensure user anonymity such that the user’s real identity can only be revealed by authorized entities. In 2000, Lee and Chang [19] proposed a user identification scheme with key distribution preserving user anonymity for the distributed computer network. However, Wu and Hsu [20] pointed out that Lee and Chang’s scheme cannot protect user anonymity as they claimed, and they proposed an enhanced scheme. Later, Yang et al. [21] showed that Wu and Hsu’s scheme cannot resist impersonation attack and proposed an improved scheme which is more secure and efficient. Unfortunately, Mangipudi and Katti [22] presented that Yang et al.’s protocol is vulnerable to a Denial-of-Service (DoS) attack and proposed a secure identification and key agreement protocol with user anonymity. Recently, Wang et al. [23] presented a secure and efficient identification and key agreement protocol with user anonymity based on the difficulty of computing the elliptic curve Diffie-Hellman. Their scheme’s computation cost is lower and is suitable for applications in low power computing environments.In 2004, Choi and Youn [24] proposed a novel data encryption and distribution approach using LU decomposition of matrices. Then, Pathan et al. [25, 26] proposed two efficient bilateral remote user authentication schemes based on LU decomposition of matrices. Nevertheless, these schemes have several weaknesses, such as they cannot resist replay attacks, they cannot preserve the user anonymity, the server and users cannot agree on a session key, and so forth. To address these issues, Tseng et al. [27] proposed a user authentication scheme based on LU decomposition of matrices. They claimed that their scheme can resist replay attack, forgery attack, and insider attack and provide user anonymity. Whereas, after careful analysis, we find that Tseng et al.’s scheme is still vulnerable to insider attack, stolen smart card attack and inefficient for wrong password login and does not provide user anonymity. To overcome these existed weaknesses of Tseng et al.’s scheme, we propose a novel bilateral authentication scheme with user anonymity using LU decomposition of matrices. Analysis shows that our scheme not only can provide better security properties but also is more efficient than the other authentication schemes.The rest of this paper is organized as follows: Section2 introduces the necessary preliminaries of this paper. The brief review of Tseng et al.’s scheme is provided in Section 3. Section 4 describes a cryptanalysis of Tseng et al.’s scheme. The proposed scheme and the corresponding analysis are presented in Sections 5 and 6, respectively. Finally, we conclude this paper in Section 7.


## 2. Preliminaries

In this section, we introduce some basic information about the LU decomposition of matrices and Discrete logarithm problem, and they are the mathematical basis of our proposed bilateral remote user authentication protocol with user anonymity.


### 2.1. LU Decomposition of Matrices

From the matrix theory, LU decomposition factorizes a matrix as the product of a lower triangular matrix and an upper triangular matrix. LetA be a square matrix; an LU decomposition of matrix A is the form A=LU, where L is a lower triangular matrix and U is an upper triangular matrix. This means that L has only zeros above the diagonal and U has only zeros below the diagonal. For example, for a 4×4 matrix A, its LU decomposition looks like
(1)A=(a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44)=(l11000l21l2200l31l32l330l41l42l43l44)(u11u12u13u140u22u23u2400u33u34000u44).IfA is a singular matrix of rank k, it admits an LU decomposition if all the k-leading principal minors are nonzero.In the identity authentication system, we assume thatn is the number of users the system can support. We can introduce the LU decomposition into the user authentication system to ensure the security of the system. In the system initialization phase, the remote server generates a symmetric matrix An×n as his/her master secret key. With the LU decomposition, the server can separate the symmetric key matrix An×n to the product of a lower triangular matrix Ln×n and an upper triangular matrix Un×n, that is, An×n=Ln×nUn×n, and stores these matrices in other servers.SinceA is a symmetric matrix, we have that aij=aji, for 1≤i≤n and 1≤j≤n, and the product of the xth row of matrix Ln×n and the yth column of matrix Un×n is equal to the product of the yth row of matrix Ln×n and the xth column of matrix Un×n. For example, suppose A is a 4×4 symmetric matrix with LU decomposition as follows:
(2)A=(12342587381194796).
We can perform elementary row operations to get the lower matrix L and upper matrix U as follows:
(3)L=(1000210032104-1121),U=(1234012-100-2-1000-212).
Given i=3 and j=4, we can compute a34 and a43 as follows:
(4)a34=LR(3)×UC(4)=(3210)×(4-1-1-212)T=9,a43=LR(4)×UC(3)=(4-1121)×(32-20)T=9,
where LR(3) denotes the 3rd row of the matrix L and UC(4) denotes the 4th column of the matrix U, and we have that a34=a43.


### 2.2. Discrete Logarithm Problem

The detailed information about discrete logarithm problem can be found in the literature [28], and we briefly introduce the discrete logarithm problem as follow. In a multiplicative group 〈g〉 of order q, where p=2q+1 is the modulus for the group, both p and q are public large prime numbers. This implies(1)
〈g〉={X∣X=gxmodp, for x=1,2,3} is a finite set of size q, where 2≤g≤p-1 and gqmodp=1.(2)
Givenx and g, computing the modular exponentiation X=gxmodp is relatively easy. However, given X and g, it is computationally infeasible to find x such that X=gxmodp; namely, in 〈g〉, the discrete logarithm problem is intractable [28].(3)
Moreover, giveng, p, X=gxmodp  and Y=gymodp, computing K=gxy mod p, which is known as the Diffie-Hellman problem, is also intractable [28].


## 2.1. LU Decomposition of Matrices

From the matrix theory, LU decomposition factorizes a matrix as the product of a lower triangular matrix and an upper triangular matrix. LetA be a square matrix; an LU decomposition of matrix A is the form A=LU, where L is a lower triangular matrix and U is an upper triangular matrix. This means that L has only zeros above the diagonal and U has only zeros below the diagonal. For example, for a 4×4 matrix A, its LU decomposition looks like
(1)A=(a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44)=(l11000l21l2200l31l32l330l41l42l43l44)(u11u12u13u140u22u23u2400u33u34000u44).IfA is a singular matrix of rank k, it admits an LU decomposition if all the k-leading principal minors are nonzero.In the identity authentication system, we assume thatn is the number of users the system can support. We can introduce the LU decomposition into the user authentication system to ensure the security of the system. In the system initialization phase, the remote server generates a symmetric matrix An×n as his/her master secret key. With the LU decomposition, the server can separate the symmetric key matrix An×n to the product of a lower triangular matrix Ln×n and an upper triangular matrix Un×n, that is, An×n=Ln×nUn×n, and stores these matrices in other servers.SinceA is a symmetric matrix, we have that aij=aji, for 1≤i≤n and 1≤j≤n, and the product of the xth row of matrix Ln×n and the yth column of matrix Un×n is equal to the product of the yth row of matrix Ln×n and the xth column of matrix Un×n. For example, suppose A is a 4×4 symmetric matrix with LU decomposition as follows:
(2)A=(12342587381194796).
We can perform elementary row operations to get the lower matrix L and upper matrix U as follows:
(3)L=(1000210032104-1121),U=(1234012-100-2-1000-212).
Given i=3 and j=4, we can compute a34 and a43 as follows:
(4)a34=LR(3)×UC(4)=(3210)×(4-1-1-212)T=9,a43=LR(4)×UC(3)=(4-1121)×(32-20)T=9,
where LR(3) denotes the 3rd row of the matrix L and UC(4) denotes the 4th column of the matrix U, and we have that a34=a43.


## 2.2. Discrete Logarithm Problem

The detailed information about discrete logarithm problem can be found in the literature [28], and we briefly introduce the discrete logarithm problem as follow. In a multiplicative group 〈g〉 of order q, where p=2q+1 is the modulus for the group, both p and q are public large prime numbers. This implies(1)
〈g〉={X∣X=gxmodp, for x=1,2,3} is a finite set of size q, where 2≤g≤p-1 and gqmodp=1.(2)
Givenx and g, computing the modular exponentiation X=gxmodp is relatively easy. However, given X and g, it is computationally infeasible to find x such that X=gxmodp; namely, in 〈g〉, the discrete logarithm problem is intractable [28].(3)
Moreover, giveng, p, X=gxmodp  and Y=gymodp, computing K=gxy mod p, which is known as the Diffie-Hellman problem, is also intractable [28].


## 3. Review of Tseng et al.’s Scheme

In this section, we briefly review Tseng et al.’s scheme, and more details can be found in [27]. Tseng et al.’s scheme contains four phases, that is, the registration phase, the login phase, the authentication phase, and the password change phase. The notations used throughout this paper are listed in Table 1.Table 1
Notations used in this paper.
S
The server
U
i
Useri
I
D
i
The identity of userUi
P
W
i
The password of userUi
K
S
The server's secret key
A
K
i
The authenticated session key shared between the server andUi
n
The number of users that could be supported by the system
A
A secretn×n symmetric matrix with LU decomposition generated by the server
L
,
U
MatrixA's LU decomposition such that A=LU
T
The timestamp
Δ
T
The expected time interval for transmission delay
h
(
·
)
One-way hash function
p
,
q
Two big prime numbers generated according to the requirement as in Section2.2
g
A generator of orderq


### 3.1. Registration Phase

Suppose a new userUi with the identity IDi wants to register himself/herself with the server for access the remote services. Ui randomly chooses his/her password PWi and sends IDi,h(PWi) to the server through a secure channel. Upon receiving the registration request message, the server takes the following steps:(1)
generates two random numbersxi,yi between 1 and n. Then selects the xith row from the matrix L (denoted as LR(xi)), the xith column from matrix U (denoted as UC(xi)), and the yith column from the matrix U (denoted as UC(yi));(2)
computes(Kxiyi,θi,vi) as follows:
Kxiyi=LR(xi)×UC(yi),θi=h(IDi⊕Kxiyi)⊕h(PWi)⊕h(KS),andvi=h(KS)⊕yi;(3)
stores(Kxiyi,θi,UC(xi),vi,h(·),g,p) into a smart card and submits the smart card to Ui via a secure channel.


### 3.2. Login Phase

WhenUi wants to login into the system, Ui first inserts the smart card to the card reader and inputs his/her password PWi*. The smart card performs the following steps to generate the login request message:(1)
Generates a random numberr;(2)
computesHi=Kxiyi⊕h(r⊕T) and Si=θi⊕h(PWi*)⊕r, where T is the current timestamp;(3)
generates a random numbera and then computes ri=gamodp and Ri=h(θi⊕ri);(4)
encrypts(IDi,ri,UC(xi),vi,T) with Ri and computes Ci=θi⊕h(IDi⊕Kxiyi)⊕h(PWi*)⊕Ri=h(KS)⊕Ri;(5)
sends the login request messageMi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) to the server.


### 3.3. Authentication Phase

Upon receiving the login request messageMi, the server and the user Ui perform the following operations for mutual authentication.(1)
The server computesRi=Ci⊕h(KS) and decrypts ERi(IDi,ri,UC(xi),vi,T) with Ri.(2)
The server checks the validity ofIDi. If IDi is invalid, the server rejects the login request.(3)
The server verifies whether the time interval(T′-T)≤ΔT, where T′ is the current timestamp when the server received the message. If (T′-T)≥ΔT, the login request is considered out of date and is rejected.(4)
The server computesyi=vi⊕h(KS).(5)
The server computesKyixi=LR(yi)×UC(xi), t=h(IDi⊕Kyixi), and   r′=Si⊕T⊕h(KS)⊕t.(6)
The server verifies whetherKxiyi equals Hi⊕h(r′). If not, the server rejects the login request. Otherwise, it proceeds to the next steps.(7)
The server generates a random numberb and computes rs=gbmodp.(8)
The server computes the authenticated session keyAKi=rib=gabmodp.(9)
At last, the server sendsERi(Kyixi⊕rs,ri+1,T′′) to Ui, where T′′ is the current timestamp.(10)
When receiving the messageERi(Kyixi⊕rs,ri+1,T′′), Ui decrypts the message, gets Kyixi⊕rs, and verifies whether (T′′′-T′′)≤ΔT, where T′′′ is the current timestamp. If so, Ui proceeds to the next steps.(11)
Ui checks whether decrypted data contain the value ri+1. If so, Ui uses Kyixi to compute rs=(Kyixi⊕rs)⊕Kyixi.(12)
Ui generates the authenticated session key AKi as AKi=rsa=(gb)a=gabmodp. Then Ui can communicate with the server secretly by using AKi.


### 3.4. Password Change Phase

WhenUi wants to change his password PWi to PWi′, he sends (IDi,h(PWi),h(PWi′)) to the server. Upon receiving the password-changing message, the server takes the following steps:(1)
computesθi′=θi⊕h(PWi)⊕h(PWi′)=h(IDi⊕Kxiyi)⊕h(PWi′)⊕h(KS);(2)
replacesθi with θi′ in the smart card.


## 3.1. Registration Phase

Suppose a new userUi with the identity IDi wants to register himself/herself with the server for access the remote services. Ui randomly chooses his/her password PWi and sends IDi,h(PWi) to the server through a secure channel. Upon receiving the registration request message, the server takes the following steps:(1)
generates two random numbersxi,yi between 1 and n. Then selects the xith row from the matrix L (denoted as LR(xi)), the xith column from matrix U (denoted as UC(xi)), and the yith column from the matrix U (denoted as UC(yi));(2)
computes(Kxiyi,θi,vi) as follows:
Kxiyi=LR(xi)×UC(yi),θi=h(IDi⊕Kxiyi)⊕h(PWi)⊕h(KS),andvi=h(KS)⊕yi;(3)
stores(Kxiyi,θi,UC(xi),vi,h(·),g,p) into a smart card and submits the smart card to Ui via a secure channel.


## 3.2. Login Phase

WhenUi wants to login into the system, Ui first inserts the smart card to the card reader and inputs his/her password PWi*. The smart card performs the following steps to generate the login request message:(1)
Generates a random numberr;(2)
computesHi=Kxiyi⊕h(r⊕T) and Si=θi⊕h(PWi*)⊕r, where T is the current timestamp;(3)
generates a random numbera and then computes ri=gamodp and Ri=h(θi⊕ri);(4)
encrypts(IDi,ri,UC(xi),vi,T) with Ri and computes Ci=θi⊕h(IDi⊕Kxiyi)⊕h(PWi*)⊕Ri=h(KS)⊕Ri;(5)
sends the login request messageMi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) to the server.


## 3.3. Authentication Phase

Upon receiving the login request messageMi, the server and the user Ui perform the following operations for mutual authentication.(1)
The server computesRi=Ci⊕h(KS) and decrypts ERi(IDi,ri,UC(xi),vi,T) with Ri.(2)
The server checks the validity ofIDi. If IDi is invalid, the server rejects the login request.(3)
The server verifies whether the time interval(T′-T)≤ΔT, where T′ is the current timestamp when the server received the message. If (T′-T)≥ΔT, the login request is considered out of date and is rejected.(4)
The server computesyi=vi⊕h(KS).(5)
The server computesKyixi=LR(yi)×UC(xi), t=h(IDi⊕Kyixi), and   r′=Si⊕T⊕h(KS)⊕t.(6)
The server verifies whetherKxiyi equals Hi⊕h(r′). If not, the server rejects the login request. Otherwise, it proceeds to the next steps.(7)
The server generates a random numberb and computes rs=gbmodp.(8)
The server computes the authenticated session keyAKi=rib=gabmodp.(9)
At last, the server sendsERi(Kyixi⊕rs,ri+1,T′′) to Ui, where T′′ is the current timestamp.(10)
When receiving the messageERi(Kyixi⊕rs,ri+1,T′′), Ui decrypts the message, gets Kyixi⊕rs, and verifies whether (T′′′-T′′)≤ΔT, where T′′′ is the current timestamp. If so, Ui proceeds to the next steps.(11)
Ui checks whether decrypted data contain the value ri+1. If so, Ui uses Kyixi to compute rs=(Kyixi⊕rs)⊕Kyixi.(12)
Ui generates the authenticated session key AKi as AKi=rsa=(gb)a=gabmodp. Then Ui can communicate with the server secretly by using AKi.


## 3.4. Password Change Phase

WhenUi wants to change his password PWi to PWi′, he sends (IDi,h(PWi),h(PWi′)) to the server. Upon receiving the password-changing message, the server takes the following steps:(1)
computesθi′=θi⊕h(PWi)⊕h(PWi′)=h(IDi⊕Kxiyi)⊕h(PWi′)⊕h(KS);(2)
replacesθi with θi′ in the smart card.


## 4. Cryptanalysis of Tseng et al.’s Scheme

Tseng et al. claimed that their scheme can protect user anonymity and can resist various known attacks. However, after careful analysis, we find that their scheme cannot really protect the user anonymity and is vulnerable to insider attack, server spoofing attack. Besides, their scheme is inefficient for wrong password login. We analyze the security weaknesses of Tseng et al.’s scheme as below.


### 4.1. Attacks against the User Anonymity

In order to prevent the attacker from tracking the user’s movements, it is important to ensure user anonymity such that the user’s real identity can only be recognized by the server.Kocher et al. [29] and Messerges et al. [30] have pointed out that the confidential information stored on the smart card can be extracted by physically monitoring its power consumption. So, in Tseng et al.’s scheme, a legal but malicious user UA can extract information (KxAyA,θA,UC(xA),vA,h(·),p,g) from his/her own smart card, and with his/her own identity IDA and password PWA, he/she can compute the value of h(KS)=θA⊕h(IDA⊕KxAyA)⊕h(PWA). When the valid login request message Mi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) of a legal user Ui was to be intercepted by this malicious user UA from the public communication channel, the malicious user UA can compute Ri=Ci⊕h(KS), and then he/she can decrypts ERi(IDi,ri,UC(xi),vi,T) using Ri to obtain (IDi,ri,UC(xi),vi,T) of the user Ui. Obviously, the malicious user UA can obtain the real identity IDi of the user Ui. From the above discussion, we can see that Tseng et al.’s scheme cannot really protect user anonymity.


### 4.2. Insider Attack

In the registration phase of Tseng et al.’s scheme, the userUi sends IDi,h(PWi) to the server for registration, and these information can be acquired by the privileged insider. However, in password change phase, the server simply not checks the validity of user Ui’s IDi and PWi. So, this privileged insider of the remote system can masquerade as the user Ui to send the triple (IDi,h(PWi),h(PWi′)) to the server to perform the password-changing phase. Upon receiving the password-changing message, the server takes the following steps:(1)
computesθi′=θi⊕h(PWi)⊕h(PWi′)=h(IDi⊕Kxiyi)⊕h(PWi′)⊕h(KS);(2)
replacesθi with θi′ in the smart card.Therefore, since the server does not check the validity of the user’s identity and password when the user wants to change his/her password, Tseng et al.’s scheme is vulnerable to insider attack, and the privileged insider can easily change the legal user’s password.


### 4.3. Stolen Smart Card Attack

Stolen smart card attack is that if the user’s smart card is lost or stolen, the attacker can extract the information stored in the smart card and can easily change the password of the smart card, can guess the password of the user by using password guessing attacks, or can impersonate the user to login to the system.In Tseng et al.’s scheme, a legal but malicious userUA having his own smart card can gather information (KxAyA,θA,UC(xA),vA,h(·),p,g) from his own smart card, and he/she can get the value of h(KS) as shown in Section 4.1. Now the malicious user UA can intercept a valid login request message Mi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) of the legal user Ui from the public communication channel. Then the malicious user UA can compute Ri=Ci⊕h(KS) and can get the identity IDi of user Ui by decrypt ERi(IDi,ri,UC(xi),vi,T) using Ri. In case the user Ui’s smart card is stolen by this malicious user UA, he/she can extract the information (Kxiyi,θi,UC(xi),vi,h(·),g,p) from the memory of the smart card. With the information IDi, h(KS), Kxiyi, and θi, the malicious user UA can guess Ui’s password by the following processes.(1)
The attacker computesh(PWi)=θi⊕h(IDi⊕Kxiyi)⊕h(KS).(2)
The attacker chooses a passwordPWi′ from a uniformly scattered dictionary.(3)
The attacker computesh(PWi′) and verifies the correctness of password PWi′ by checking whether h(PWi′) equals h(PWi) or not.(4)
The attacker repeats steps (2) and (3) untilh(PWi′) equals h(PWi) to guess a correct password.After getting the correctIDi, and PWi, the malicious user UA can easily change the password of user Ui and can impersonate Ui to login to the system.


### 4.4. Inefficient for Wrong Password Login

Generally speaking, in practical applications, the userUi may keep different passwords for different applications to ensure security. Users are easy to confuse the password such that the user cannot match the application with the correct password; in other words, it is possible that the user enters a wrong password in the login phase.In the login phase, the smart card does not verify the correctness of the entered password by the user. If the userUi inputs a wrong password PWi′(≠PWi) by mistake, the smart card and the server will perform the following steps:(1)
generates a random numberr, gets the current timestamp T, and computes Hi=Kxiyi⊕h(r⊕T) and Si=θi⊕h(PWi′)⊕r;(2)
generates a random numbera and computes ri=gamodp and Ri=h(θi⊕ri);(3)
encrypts(IDi,ri,UC(xi),vi,T) with Ri and computes Ci=θi⊕h(IDi⊕Kxiyi)⊕h(PWi′)⊕Ri(=h(KS)⊕h(PWi)⊕h(PWi′)⊕Ri);(4)
sends the login request messageMi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) to the server;(5)
when the server receives the login request messageMi, the server computes Ri′=Ci⊕h(KS)=h(KS)⊕h(PWi)⊕h(PWi′)⊕Ri⊕h(KS)=h(PWi)⊕h(PWi′)⊕Ri. It is obvious that Ri′≠Ri, since PWi′≠PWi;(6)
when the server decryptsERi(IDi,ri,UC(xi),vi,T) using Ri′, the server will find that the user Ui’s identity is invalid. Thus, the server rejects the user Ui’s login request.In this case, the userUi is unaware of the fact that he/she has entered his/her password incorrectly in the login phase, which results in unnecessary extra communication and computation costs.


## 4.1. Attacks against the User Anonymity

In order to prevent the attacker from tracking the user’s movements, it is important to ensure user anonymity such that the user’s real identity can only be recognized by the server.Kocher et al. [29] and Messerges et al. [30] have pointed out that the confidential information stored on the smart card can be extracted by physically monitoring its power consumption. So, in Tseng et al.’s scheme, a legal but malicious user UA can extract information (KxAyA,θA,UC(xA),vA,h(·),p,g) from his/her own smart card, and with his/her own identity IDA and password PWA, he/she can compute the value of h(KS)=θA⊕h(IDA⊕KxAyA)⊕h(PWA). When the valid login request message Mi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) of a legal user Ui was to be intercepted by this malicious user UA from the public communication channel, the malicious user UA can compute Ri=Ci⊕h(KS), and then he/she can decrypts ERi(IDi,ri,UC(xi),vi,T) using Ri to obtain (IDi,ri,UC(xi),vi,T) of the user Ui. Obviously, the malicious user UA can obtain the real identity IDi of the user Ui. From the above discussion, we can see that Tseng et al.’s scheme cannot really protect user anonymity.


## 4.2. Insider Attack

In the registration phase of Tseng et al.’s scheme, the userUi sends IDi,h(PWi) to the server for registration, and these information can be acquired by the privileged insider. However, in password change phase, the server simply not checks the validity of user Ui’s IDi and PWi. So, this privileged insider of the remote system can masquerade as the user Ui to send the triple (IDi,h(PWi),h(PWi′)) to the server to perform the password-changing phase. Upon receiving the password-changing message, the server takes the following steps:(1)
computesθi′=θi⊕h(PWi)⊕h(PWi′)=h(IDi⊕Kxiyi)⊕h(PWi′)⊕h(KS);(2)
replacesθi with θi′ in the smart card.Therefore, since the server does not check the validity of the user’s identity and password when the user wants to change his/her password, Tseng et al.’s scheme is vulnerable to insider attack, and the privileged insider can easily change the legal user’s password.


## 4.3. Stolen Smart Card Attack

Stolen smart card attack is that if the user’s smart card is lost or stolen, the attacker can extract the information stored in the smart card and can easily change the password of the smart card, can guess the password of the user by using password guessing attacks, or can impersonate the user to login to the system.In Tseng et al.’s scheme, a legal but malicious userUA having his own smart card can gather information (KxAyA,θA,UC(xA),vA,h(·),p,g) from his own smart card, and he/she can get the value of h(KS) as shown in Section 4.1. Now the malicious user UA can intercept a valid login request message Mi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) of the legal user Ui from the public communication channel. Then the malicious user UA can compute Ri=Ci⊕h(KS) and can get the identity IDi of user Ui by decrypt ERi(IDi,ri,UC(xi),vi,T) using Ri. In case the user Ui’s smart card is stolen by this malicious user UA, he/she can extract the information (Kxiyi,θi,UC(xi),vi,h(·),g,p) from the memory of the smart card. With the information IDi, h(KS), Kxiyi, and θi, the malicious user UA can guess Ui’s password by the following processes.(1)
The attacker computesh(PWi)=θi⊕h(IDi⊕Kxiyi)⊕h(KS).(2)
The attacker chooses a passwordPWi′ from a uniformly scattered dictionary.(3)
The attacker computesh(PWi′) and verifies the correctness of password PWi′ by checking whether h(PWi′) equals h(PWi) or not.(4)
The attacker repeats steps (2) and (3) untilh(PWi′) equals h(PWi) to guess a correct password.After getting the correctIDi, and PWi, the malicious user UA can easily change the password of user Ui and can impersonate Ui to login to the system.


## 4.4. Inefficient for Wrong Password Login

Generally speaking, in practical applications, the userUi may keep different passwords for different applications to ensure security. Users are easy to confuse the password such that the user cannot match the application with the correct password; in other words, it is possible that the user enters a wrong password in the login phase.In the login phase, the smart card does not verify the correctness of the entered password by the user. If the userUi inputs a wrong password PWi′(≠PWi) by mistake, the smart card and the server will perform the following steps:(1)
generates a random numberr, gets the current timestamp T, and computes Hi=Kxiyi⊕h(r⊕T) and Si=θi⊕h(PWi′)⊕r;(2)
generates a random numbera and computes ri=gamodp and Ri=h(θi⊕ri);(3)
encrypts(IDi,ri,UC(xi),vi,T) with Ri and computes Ci=θi⊕h(IDi⊕Kxiyi)⊕h(PWi′)⊕Ri(=h(KS)⊕h(PWi)⊕h(PWi′)⊕Ri);(4)
sends the login request messageMi=(Ci,ERi(IDi,ri,UC(xi),vi,T),Hi,Si,T) to the server;(5)
when the server receives the login request messageMi, the server computes Ri′=Ci⊕h(KS)=h(KS)⊕h(PWi)⊕h(PWi′)⊕Ri⊕h(KS)=h(PWi)⊕h(PWi′)⊕Ri. It is obvious that Ri′≠Ri, since PWi′≠PWi;(6)
when the server decryptsERi(IDi,ri,UC(xi),vi,T) using Ri′, the server will find that the user Ui’s identity is invalid. Thus, the server rejects the user Ui’s login request.In this case, the userUi is unaware of the fact that he/she has entered his/her password incorrectly in the login phase, which results in unnecessary extra communication and computation costs.


## 5. The Proposed Scheme

In this section, we apply the LU decomposition of matrices to design a novel bilateral remote user authentication scheme with user anonymity, where LU decomposition of matrices ensures secretly information exchange between the user and the server, and enhances the security of the authentication scheme. To initiate the scheme, the server chooses an×n symmetric matrix A with LU decomposition as A=LU and secretly stores these matrices as his/her secret key in other servers, where n is the number of users the system can support. The server chooses a secret key KS with 256 bits, which makes the KS have a high entropy and can resist brutal force attack. The proposed scheme also contains four phases, that is, the registration phase, the login phase, the authentication and key agreement phase, and the password change phase. The proposed scheme contains the timestamps, so the authentication system needs to deploy a mechanism such as NTP (Network Time Protocol) to ensure clock synchronization between the user and the remote server. The detailed information about these phases are described as follows and also shown in Figure 1.Figure 1
The proposed scheme.


### 5.1. Registration Phase

When a userUi wants to become a legal user of the system, Ui generates his own identity IDi and easy-to-remember password PWi and selects and remembers a random number bi (the bit length of bi is assumed to be 128). Then, Ui computes RPWi=h(bi∥PWi) and submits IDi and RPWi to the server over a secure communication channel for registration. h(·) used throughout the proposed scheme is a collision-free one-way hash function such as SHA-1 [31], which maps any message with the length less than 264 bit to a 160-bit message digest. Upon receiving the registration request message, the server S and the user Ui take the following steps.(1)
The serverS computes Ai=h(IDi∥KS), Bi=Ai⊕h(IDi⊕RPWi), and Ci=h(Ai).(2)
The serverS chooses two random numbers xi,yi∈[1,n] and computes Kxiyi=LR(xi)×UC(yi), Di=h(Kxiyi⊕KS)⊕h(IDi∥RPWi), Ei=h(KS)⊕yi, where the meaning of symbols LR(xi) and UC(yi) are the same as in Section 3.1.(3)
The server stores{Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p} into a smart card and issues the smart card to Ui via a secure channel, where p is a big prime and p=2q+1, q is also a big prime, and g is a primitive element with gq=1modp.(4)
At last, in order to facilitate the subsequent verification, the userUi enters the remembered random number bi into the smart card, and the smart card contains {Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p,bi}.


### 5.2. Login Phase

When the userUi wants to login to the system, Ui inserts his/her smart card into the card reader and inputs his/her identity IDi, password PWi. Then the smart card performs the following operations:(1)
computesRPWi=h(bi∥PWi), Ai=Bi⊕h(IDi⊕RPWi), and Ci′=h(Ai) and compares Ci′=?Ci. If they are equal, it means the user inputs the right identity and password. Otherwise, the input identity or password is not valid, and the smart card terminates the session;(2)
generates a random numberr, gets current timestamp T, and computes Fi=Di⊕h(IDi∥RPWi), Gi=Fi⊕r, CIDi=r⊕IDi, and Hi=Ei⊕T;(3)
generates a random numberri∈(1,q) and computes Ri=grimodp, Ji=Ri⊕h(r⊕T), and Mi=h(h(IDi∥Kxiyi)∥Ri∥r∥T), where Mi is used to resist the forgery attack such that any change of the login request message is invalid login message;(4)
submits the login request message{Gi,CIDi,Hi,Ji,UC(xi),Mi,T} to the server.


### 5.3. Verification and Key Agreement Phase

Upon receiving the login request message{Gi,CIDi,Hi,Ji,UC(xi),Mi,T}, the server performs the following steps for mutual authentication and key agreement.(1)
The serverS verifies the validity of the time interval between T′ and T. If (T′-T)≥ΔT, S rejects the login request. Here T′ is the timestamp, when the login request message was received, and ΔT is the expected valid time interval for transmission delay.(2)
The serverS computes yi=Hi⊕h(KS)⊕T, Kyixi=LR(yi)×UC(xi).(3)
The serverS computes r′=h(Kyixi⊕KS)⊕Gi, Ri′=Ji⊕h(r′⊕T), and IDi=CIDi⊕r′ and checks whether IDi is the registered identity of a valid user. If so, the server S performs the following steps. Otherwise, the session is terminated.(4)
The serverS computes Mi′=h(h(IDi∥Kyixi)∥Ri′∥r′∥T) and checks Mi′=?Mi. If they are equal, the validity of the user Ui is authenticated by the server S. Otherwise, the session is terminated by the server S.(5)
For achieving mutual authentication, the server chooses a random numberrs∈(1,q), gets the current timestamp T′′, and computes Rs=grsmodp, Ki=Rs⊕Ri′, and Ms=h(h(IDi∥Kyixi)∥Ri′∥Rs∥r′∥T′′).(6)
The serverS submits the reply message {Ki,Ms,T′′} to the user Ui for mutual authentication.(7)
After receiving the mutual authentication message(Ki,Ms,T′′), the smart card verifies the validity of the time interval between T′′′ and T′′. If (T′′′-T′′)≥ΔT, the user Ui terminates the session. Here T′′′ is the timestamp, when the mutual authentication message was received.(8)
The smart card computesRs′=Ki⊕Ri, Ms′=h(h(IDi∥Kxiyi)∥Ri∥Rs′∥r∥T′′) and checks Ms′=?Ms. If they are equal, the server S is authenticated by the user Ui, and the server S and user achieve mutual authentication. Otherwise, the smart card terminates this session.(9)
At last, the userUi and the server S can compute AKi=Rs′rimodp=grirsmodp and AKi=Ri′rsmodp =grirsmodp, respectively, as their shared session key for future secret communication.


### 5.4. Password Change Phase

When the userUi wants to renew his/her password to PWinew, the user Ui can update his/her password by performing the following steps without communicating with the server S.(1)
The userUi inserts his smart card into a card reader and inputs his identity IDi and old password PWi and requests to change his/her password.(2)
The smart card computesRPWi=h(bi∥PWi), Ai=Bi⊕h(IDi⊕RPWi), Ci′=h(Ai′) and compares Ci′=?Ci. If they are not equal, the password change request is rejected. Otherwise the user Ui inputs a new password PWinew.(3)
The smart card computesRPWi*=h(bi∥PWinew), Bi*=Ai⊕h(IDi⊕RPWi*), and Di*=Di*⊕h(IDi∥RPWi)⊕h(IDi∥RPWi*).(4)
Finally, the smart card replacesBi and Di with Bi* and Di*, respectively, to update his/her password.


## 5.1. Registration Phase

When a userUi wants to become a legal user of the system, Ui generates his own identity IDi and easy-to-remember password PWi and selects and remembers a random number bi (the bit length of bi is assumed to be 128). Then, Ui computes RPWi=h(bi∥PWi) and submits IDi and RPWi to the server over a secure communication channel for registration. h(·) used throughout the proposed scheme is a collision-free one-way hash function such as SHA-1 [31], which maps any message with the length less than 264 bit to a 160-bit message digest. Upon receiving the registration request message, the server S and the user Ui take the following steps.(1)
The serverS computes Ai=h(IDi∥KS), Bi=Ai⊕h(IDi⊕RPWi), and Ci=h(Ai).(2)
The serverS chooses two random numbers xi,yi∈[1,n] and computes Kxiyi=LR(xi)×UC(yi), Di=h(Kxiyi⊕KS)⊕h(IDi∥RPWi), Ei=h(KS)⊕yi, where the meaning of symbols LR(xi) and UC(yi) are the same as in Section 3.1.(3)
The server stores{Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p} into a smart card and issues the smart card to Ui via a secure channel, where p is a big prime and p=2q+1, q is also a big prime, and g is a primitive element with gq=1modp.(4)
At last, in order to facilitate the subsequent verification, the userUi enters the remembered random number bi into the smart card, and the smart card contains {Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p,bi}.


## 5.2. Login Phase

When the userUi wants to login to the system, Ui inserts his/her smart card into the card reader and inputs his/her identity IDi, password PWi. Then the smart card performs the following operations:(1)
computesRPWi=h(bi∥PWi), Ai=Bi⊕h(IDi⊕RPWi), and Ci′=h(Ai) and compares Ci′=?Ci. If they are equal, it means the user inputs the right identity and password. Otherwise, the input identity or password is not valid, and the smart card terminates the session;(2)
generates a random numberr, gets current timestamp T, and computes Fi=Di⊕h(IDi∥RPWi), Gi=Fi⊕r, CIDi=r⊕IDi, and Hi=Ei⊕T;(3)
generates a random numberri∈(1,q) and computes Ri=grimodp, Ji=Ri⊕h(r⊕T), and Mi=h(h(IDi∥Kxiyi)∥Ri∥r∥T), where Mi is used to resist the forgery attack such that any change of the login request message is invalid login message;(4)
submits the login request message{Gi,CIDi,Hi,Ji,UC(xi),Mi,T} to the server.


## 5.3. Verification and Key Agreement Phase

Upon receiving the login request message{Gi,CIDi,Hi,Ji,UC(xi),Mi,T}, the server performs the following steps for mutual authentication and key agreement.(1)
The serverS verifies the validity of the time interval between T′ and T. If (T′-T)≥ΔT, S rejects the login request. Here T′ is the timestamp, when the login request message was received, and ΔT is the expected valid time interval for transmission delay.(2)
The serverS computes yi=Hi⊕h(KS)⊕T, Kyixi=LR(yi)×UC(xi).(3)
The serverS computes r′=h(Kyixi⊕KS)⊕Gi, Ri′=Ji⊕h(r′⊕T), and IDi=CIDi⊕r′ and checks whether IDi is the registered identity of a valid user. If so, the server S performs the following steps. Otherwise, the session is terminated.(4)
The serverS computes Mi′=h(h(IDi∥Kyixi)∥Ri′∥r′∥T) and checks Mi′=?Mi. If they are equal, the validity of the user Ui is authenticated by the server S. Otherwise, the session is terminated by the server S.(5)
For achieving mutual authentication, the server chooses a random numberrs∈(1,q), gets the current timestamp T′′, and computes Rs=grsmodp, Ki=Rs⊕Ri′, and Ms=h(h(IDi∥Kyixi)∥Ri′∥Rs∥r′∥T′′).(6)
The serverS submits the reply message {Ki,Ms,T′′} to the user Ui for mutual authentication.(7)
After receiving the mutual authentication message(Ki,Ms,T′′), the smart card verifies the validity of the time interval between T′′′ and T′′. If (T′′′-T′′)≥ΔT, the user Ui terminates the session. Here T′′′ is the timestamp, when the mutual authentication message was received.(8)
The smart card computesRs′=Ki⊕Ri, Ms′=h(h(IDi∥Kxiyi)∥Ri∥Rs′∥r∥T′′) and checks Ms′=?Ms. If they are equal, the server S is authenticated by the user Ui, and the server S and user achieve mutual authentication. Otherwise, the smart card terminates this session.(9)
At last, the userUi and the server S can compute AKi=Rs′rimodp=grirsmodp and AKi=Ri′rsmodp =grirsmodp, respectively, as their shared session key for future secret communication.


## 5.4. Password Change Phase

When the userUi wants to renew his/her password to PWinew, the user Ui can update his/her password by performing the following steps without communicating with the server S.(1)
The userUi inserts his smart card into a card reader and inputs his identity IDi and old password PWi and requests to change his/her password.(2)
The smart card computesRPWi=h(bi∥PWi), Ai=Bi⊕h(IDi⊕RPWi), Ci′=h(Ai′) and compares Ci′=?Ci. If they are not equal, the password change request is rejected. Otherwise the user Ui inputs a new password PWinew.(3)
The smart card computesRPWi*=h(bi∥PWinew), Bi*=Ai⊕h(IDi⊕RPWi*), and Di*=Di*⊕h(IDi∥RPWi)⊕h(IDi∥RPWi*).(4)
Finally, the smart card replacesBi and Di with Bi* and Di*, respectively, to update his/her password.


## 6. Analysis of the Proposed Scheme

In this section, we first discuss the security features of the proposed anonymity bilateral authentication scheme. Then we evaluate the performance and functionality of our proposed scheme and make comparisons with Tseng et al.’ scheme.


### 6.1. Security of Session Key

#### 6.1.1. Known-Key Secrecy

Known-key secrecy means that compromise of one session key should not compromise other session keys. In our scheme, the session keyAKi=grirsmodp is associated with ri,grimodp,rs, and grsmodp. According to discrete logarithm problem (DLP) and Diffie-Hellman problem (DHP), knowing a session key AKi=grirsmodp and the random number ri, rs is useless for computing the other session keys AKi′=gri′rs′modp without knowing ri′ and rs′. It is impossible for an attacker to compute the other session key AKi′, and the proposed scheme provides known-key security.


#### 6.1.2. Forward Secrecy

Forward secrecy means that if the long-term secret keys (e.g., the server’s secret keyKS and user’s password PWi) are compromised, the secrecy of previously established session keys should not be affected. In our scheme, we assume that the master secret key KS and the password PWi of user Ui are compromised for some reasons, and the attacker gets the previous communication message {Gi,CIDi,Hi,Ji,UC(xi),Mi,T} and {Ki,Ms,T′′} from the public channel; then the attacker can get yi=Hi⊕h(KS)⊕T. However, since the secret matrix L has been maintained only by the server S, the attacker cannot compute Kxiyi, r and has no way to know ri, Ri, rs, and Rs. Therefore, the attacker has no way to get the previous session key AKi=grirs mod p, and our scheme can ensure perfect forward secrecy.


### 6.2. Protect User Anonymity

In the login phase and authentication phase of the proposed scheme, the real identityIDi of user Ui is not transmit via plain text form. If the login request message {Gi,CIDi,Hi,Ji,UC(xi),Mi,T} and the mutual authentication message {Ki,Ms,T′′} are eavesdropped by an attacker from the public channel, the attacker has to get the random number r to compute the real identity IDi. However, the attacker has no way to know Kxiyi and KS, so he/she has no valid method to get the random number r and cannot reveal the real identity IDi of the user Ui. Therefore, our scheme can really protect user anonymity.


### 6.3. Resist Impersonation Attack

In this type of attack, in order to impersonate as a legitimate user, the attacker or a malicious user has to forge a valid login request message{Gi,CIDi,Hi,Ji,UC(xi),Mi,T} using the previously eavesdropped messages or the information obtained from the lost smart card. However, in the proposed scheme, the attacker and any malicious user UA cannot forge a valid login request message, since he/she has no knowledge of IDi, RPWi, Fi, and Kxiyi, so he/she cannot impersonate as the legitimate user Ui.In addition, even if the adversary or a malicious user has obtained the smart card of userUi and extracts the parameters {Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p,bi} which are stored in the smart card by some way, he/she still cannot forge a valid login request message, since he/she have no way to get the valid IDi, PWi, where they are all protected by the one-way hash function.Therefore, the proposed protocol is secure against impersonation attack. At the same time, the attacker cannot get the validIDi, PWi, so the proposed protocol can resist the denial of service attack.


### 6.4. Resist Insider Attack

In the registration phase of the proposed scheme, the userUi freely selects his/her password PWi and submits the masked password RPWi=h(bi⊕PWi) instead of h(PWi) to the server for registration. In the proposed scheme, the password must first be verified by the smart card in login and password change phase, only the adversary gets the valid password PWi of the user Ui, and he/she can impersonate the user Ui to access service. However, if the insider of the remote system gets the information IDi and RPWi=h(bi⊕PWi), he/she cannot obtain the password PWi since it is protected by the one-way hash function and cannot impersonate the user Ui to login to the system or change the user’s password. Therefore, the proposed scheme can resist insider attack properly.


### 6.5. Resist Stolen Smart Card Attack

Assume that the userUi’s smart card has been lost or stolen, the attacker can extract the stored information {Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p,bi} from the smart card using differential power analysis [29] and simple power analysis [30]. Even after gathering these information, in order to change the user’s password or login into the system by using the lost smart card, the attacker has to get real identity IDi and the password PWi correctly at the same time. However, because the attacker has not the knowledge of the master secret key KS and meanwhile the IDi and the PWi are protected by one-way hash function, it is not possible for an attacker to guess the IDi and the PWi correctly at the same time in real polynomial time. Therefore, the proposed scheme is secure against stolen smart card attack.


### 6.6. Resist Server Spoofing Attack

In the proposed scheme, in order to masquerade as the remote server to cheat the userUi, the attacker has to get the secret information L and KS to compute the valid reply mutual authentication message. However, the secret matrix L is only maintained by the server S such that the attacker has no way to recover the information Kyixi. On the other hand, even if the malicious user UA has got his own smart card information {BA,CA,KxAyA,DA,EA,UC(xA),g,p,bA} and other users’ communication messages {Gi,CIDi,Hi,Ji,UC(xi),Mi,T} and {Ki,Ms,T′′}, he/she still has no way to get KS since it is protected by the one-way hash function. So the attacker cannot get the required information L and KS, and the proposed scheme can resist the server spoofing attack.


### 6.7. Efficient for Wrong Password Verification

In the login and password change phase of the proposed scheme, the validity of the passwordPWi can quickly be verified by the smart card, when the user Ui inputs his/her password. If the user Ui inputs a wrong password PWi′(≠PWi), the smart card computes RPWi′=h(bi∥PWi′)(≠h(bi∥PWi)=RPWi, Ai′=Bi⊕h(IDi∥RPWi′)=Ai⊕h(IDi⊕RPWi)⊕h(IDi∥RPWi′)(≠Ai) and gets Ci′=h(Ai′)≠h(Ai)=Ci. So, the wrong password can quickly be checked by the smart card, and the server does not need to waste unnecessary communication and computation cost to verify the validity of the password. Thus, the proposed scheme is efficient for wrong password verification.


### 6.8. Performance and Functionality Analysis

In this section, we evaluate the performance and functionality of our proposed scheme and make comparisons with Tseng et al.’s scheme. In order to facilitate the computational complexity analysis of the scheme, we define the following notations.Th
: the time for executing a one-way hash functionh(·),TM
: the time for performing a vector multiplication operation,TEXP
: the time for performing an exponentiation operation,TENC
: the time for performing a symmetric encryption operation, andTDEC
: the time for performing a symmetric decryption operation.Because exclusion-OR operation requires very few computations, we neglect considering its computational cost in this paper. We list the result of performance comparison in Table2, and we can see that the total computational cost of our scheme and Tesng et al.’s scheme are 2TM+18TH+4TEXP and 2TM+9TH+4TEXP+2TENC+2TDEC, respectively. Since the symmetric cryptosystem needs more computational costs than the one-way hash functions, our scheme is more efficient than Tseng et al.’s scheme.Table 2
Performance comparison of our scheme and Tseng et al.'s scheme.
Our scheme
Tseng et al.'s scheme [27]
Registration phase
1
T
M
+
6
T
H
1
T
M
+
3
T
H
Login phase
6
T
H
+
1
T
EXP
4
T
H
+
1
T
EXP
+
1
T
ENC
Verification and key agreement phase
1
T
M
+
6
T
H
+
3
T
EXP
1
T
M
+
2
T
H
+
3
T
EXP
+
1
T
ENC
+
2
T
DEC
Total
2
T
M
+
18
T
H
+
4
T
EXP
2
T
M
+
9
T
H
+
4
T
EXP
+
2
T
ENC
+
2
T
DECTable3 shows the functional comparison of our proposed scheme and Tseng et al.’s scheme. Compared with Tseng et al.’s scheme, our scheme can resist various attacks and can really protect user anonymity. Besides, our scheme can quickly check the validity of the password in the very beginning of login phase. Therefore, our scheme is more secure and efficient than Tseng et al.’s scheme.Table 3
Functionality comparison between our scheme and Tseng et al.'s scheme.
Our scheme
Tseng et al.'s scheme [27]
Protect user anonymity
Yes
No
Resist impersonation attack
Yes
Yes
Resist insider attack
Yes
No
Resist stolen smart card attack
Yes
No
Resist server spoofing attack
Yes
Yes
Efficient for password verification
Yes
No
Mutual authentication
Yes
Yes
Session key agreement
Yes
Yes


## 6.1. Security of Session Key

### 6.1.1. Known-Key Secrecy

Known-key secrecy means that compromise of one session key should not compromise other session keys. In our scheme, the session keyAKi=grirsmodp is associated with ri,grimodp,rs, and grsmodp. According to discrete logarithm problem (DLP) and Diffie-Hellman problem (DHP), knowing a session key AKi=grirsmodp and the random number ri, rs is useless for computing the other session keys AKi′=gri′rs′modp without knowing ri′ and rs′. It is impossible for an attacker to compute the other session key AKi′, and the proposed scheme provides known-key security.


### 6.1.2. Forward Secrecy

Forward secrecy means that if the long-term secret keys (e.g., the server’s secret keyKS and user’s password PWi) are compromised, the secrecy of previously established session keys should not be affected. In our scheme, we assume that the master secret key KS and the password PWi of user Ui are compromised for some reasons, and the attacker gets the previous communication message {Gi,CIDi,Hi,Ji,UC(xi),Mi,T} and {Ki,Ms,T′′} from the public channel; then the attacker can get yi=Hi⊕h(KS)⊕T. However, since the secret matrix L has been maintained only by the server S, the attacker cannot compute Kxiyi, r and has no way to know ri, Ri, rs, and Rs. Therefore, the attacker has no way to get the previous session key AKi=grirs mod p, and our scheme can ensure perfect forward secrecy.


## 6.1.1. Known-Key Secrecy

Known-key secrecy means that compromise of one session key should not compromise other session keys. In our scheme, the session keyAKi=grirsmodp is associated with ri,grimodp,rs, and grsmodp. According to discrete logarithm problem (DLP) and Diffie-Hellman problem (DHP), knowing a session key AKi=grirsmodp and the random number ri, rs is useless for computing the other session keys AKi′=gri′rs′modp without knowing ri′ and rs′. It is impossible for an attacker to compute the other session key AKi′, and the proposed scheme provides known-key security.


## 6.1.2. Forward Secrecy

Forward secrecy means that if the long-term secret keys (e.g., the server’s secret keyKS and user’s password PWi) are compromised, the secrecy of previously established session keys should not be affected. In our scheme, we assume that the master secret key KS and the password PWi of user Ui are compromised for some reasons, and the attacker gets the previous communication message {Gi,CIDi,Hi,Ji,UC(xi),Mi,T} and {Ki,Ms,T′′} from the public channel; then the attacker can get yi=Hi⊕h(KS)⊕T. However, since the secret matrix L has been maintained only by the server S, the attacker cannot compute Kxiyi, r and has no way to know ri, Ri, rs, and Rs. Therefore, the attacker has no way to get the previous session key AKi=grirs mod p, and our scheme can ensure perfect forward secrecy.


## 6.2. Protect User Anonymity

In the login phase and authentication phase of the proposed scheme, the real identityIDi of user Ui is not transmit via plain text form. If the login request message {Gi,CIDi,Hi,Ji,UC(xi),Mi,T} and the mutual authentication message {Ki,Ms,T′′} are eavesdropped by an attacker from the public channel, the attacker has to get the random number r to compute the real identity IDi. However, the attacker has no way to know Kxiyi and KS, so he/she has no valid method to get the random number r and cannot reveal the real identity IDi of the user Ui. Therefore, our scheme can really protect user anonymity.


## 6.3. Resist Impersonation Attack

In this type of attack, in order to impersonate as a legitimate user, the attacker or a malicious user has to forge a valid login request message{Gi,CIDi,Hi,Ji,UC(xi),Mi,T} using the previously eavesdropped messages or the information obtained from the lost smart card. However, in the proposed scheme, the attacker and any malicious user UA cannot forge a valid login request message, since he/she has no knowledge of IDi, RPWi, Fi, and Kxiyi, so he/she cannot impersonate as the legitimate user Ui.In addition, even if the adversary or a malicious user has obtained the smart card of userUi and extracts the parameters {Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p,bi} which are stored in the smart card by some way, he/she still cannot forge a valid login request message, since he/she have no way to get the valid IDi, PWi, where they are all protected by the one-way hash function.Therefore, the proposed protocol is secure against impersonation attack. At the same time, the attacker cannot get the validIDi, PWi, so the proposed protocol can resist the denial of service attack.


## 6.4. Resist Insider Attack

In the registration phase of the proposed scheme, the userUi freely selects his/her password PWi and submits the masked password RPWi=h(bi⊕PWi) instead of h(PWi) to the server for registration. In the proposed scheme, the password must first be verified by the smart card in login and password change phase, only the adversary gets the valid password PWi of the user Ui, and he/she can impersonate the user Ui to access service. However, if the insider of the remote system gets the information IDi and RPWi=h(bi⊕PWi), he/she cannot obtain the password PWi since it is protected by the one-way hash function and cannot impersonate the user Ui to login to the system or change the user’s password. Therefore, the proposed scheme can resist insider attack properly.


## 6.5. Resist Stolen Smart Card Attack

Assume that the userUi’s smart card has been lost or stolen, the attacker can extract the stored information {Bi,Ci,Kxiyi,Di,Ei,UC(xi),g,p,bi} from the smart card using differential power analysis [29] and simple power analysis [30]. Even after gathering these information, in order to change the user’s password or login into the system by using the lost smart card, the attacker has to get real identity IDi and the password PWi correctly at the same time. However, because the attacker has not the knowledge of the master secret key KS and meanwhile the IDi and the PWi are protected by one-way hash function, it is not possible for an attacker to guess the IDi and the PWi correctly at the same time in real polynomial time. Therefore, the proposed scheme is secure against stolen smart card attack.


## 6.6. Resist Server Spoofing Attack

In the proposed scheme, in order to masquerade as the remote server to cheat the userUi, the attacker has to get the secret information L and KS to compute the valid reply mutual authentication message. However, the secret matrix L is only maintained by the server S such that the attacker has no way to recover the information Kyixi. On the other hand, even if the malicious user UA has got his own smart card information {BA,CA,KxAyA,DA,EA,UC(xA),g,p,bA} and other users’ communication messages {Gi,CIDi,Hi,Ji,UC(xi),Mi,T} and {Ki,Ms,T′′}, he/she still has no way to get KS since it is protected by the one-way hash function. So the attacker cannot get the required information L and KS, and the proposed scheme can resist the server spoofing attack.


## 6.7. Efficient for Wrong Password Verification

In the login and password change phase of the proposed scheme, the validity of the passwordPWi can quickly be verified by the smart card, when the user Ui inputs his/her password. If the user Ui inputs a wrong password PWi′(≠PWi), the smart card computes RPWi′=h(bi∥PWi′)(≠h(bi∥PWi)=RPWi, Ai′=Bi⊕h(IDi∥RPWi′)=Ai⊕h(IDi⊕RPWi)⊕h(IDi∥RPWi′)(≠Ai) and gets Ci′=h(Ai′)≠h(Ai)=Ci. So, the wrong password can quickly be checked by the smart card, and the server does not need to waste unnecessary communication and computation cost to verify the validity of the password. Thus, the proposed scheme is efficient for wrong password verification.


## 6.8. Performance and Functionality Analysis

In this section, we evaluate the performance and functionality of our proposed scheme and make comparisons with Tseng et al.’s scheme. In order to facilitate the computational complexity analysis of the scheme, we define the following notations.Th
: the time for executing a one-way hash functionh(·),TM
: the time for performing a vector multiplication operation,TEXP
: the time for performing an exponentiation operation,TENC
: the time for performing a symmetric encryption operation, andTDEC
: the time for performing a symmetric decryption operation.Because exclusion-OR operation requires very few computations, we neglect considering its computational cost in this paper. We list the result of performance comparison in Table2, and we can see that the total computational cost of our scheme and Tesng et al.’s scheme are 2TM+18TH+4TEXP and 2TM+9TH+4TEXP+2TENC+2TDEC, respectively. Since the symmetric cryptosystem needs more computational costs than the one-way hash functions, our scheme is more efficient than Tseng et al.’s scheme.Table 2
Performance comparison of our scheme and Tseng et al.'s scheme.
Our scheme
Tseng et al.'s scheme [27]
Registration phase
1
T
M
+
6
T
H
1
T
M
+
3
T
H
Login phase
6
T
H
+
1
T
EXP
4
T
H
+
1
T
EXP
+
1
T
ENC
Verification and key agreement phase
1
T
M
+
6
T
H
+
3
T
EXP
1
T
M
+
2
T
H
+
3
T
EXP
+
1
T
ENC
+
2
T
DEC
Total
2
T
M
+
18
T
H
+
4
T
EXP
2
T
M
+
9
T
H
+
4
T
EXP
+
2
T
ENC
+
2
T
DECTable3 shows the functional comparison of our proposed scheme and Tseng et al.’s scheme. Compared with Tseng et al.’s scheme, our scheme can resist various attacks and can really protect user anonymity. Besides, our scheme can quickly check the validity of the password in the very beginning of login phase. Therefore, our scheme is more secure and efficient than Tseng et al.’s scheme.Table 3
Functionality comparison between our scheme and Tseng et al.'s scheme.
Our scheme
Tseng et al.'s scheme [27]
Protect user anonymity
Yes
No
Resist impersonation attack
Yes
Yes
Resist insider attack
Yes
No
Resist stolen smart card attack
Yes
No
Resist server spoofing attack
Yes
Yes
Efficient for password verification
Yes
No
Mutual authentication
Yes
Yes
Session key agreement
Yes
Yes


## 7. Conclusions

In this paper, we have applied the LU decomposition of matrices to present a novel anonymity bilateral authentication scheme. First, we pointed out the security weaknesses of Tseng et al.’s scheme, that is, their scheme is vulnerable to insider attack and stolen smart card attack, is inefficient for wrong password login, and does not really provide user anonymity. To surmount these identified weaknesses, we have proposed a novel scheme using the LU decomposition of matrices to reduce computational complexity and improve security, where LU decomposition of matrices ensures secretly information exchange between the user and the server, and enhances the security of the authentication scheme. Hence, our proposed protocol is more efficient and practical.



---

*Source: 910409-2013-03-11.xml*