# Secure and Efficient User Authentication Scheme Based on Password and Smart Card for Multiserver Environment

Authors: Yan Zhao; Shiming Li; Liehui Jiang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The rapid development of information and network technologies motivates the emergence of various new computing paradigms, such as distributed computing, cloud computing, and edge computing. This also enables more and more network enterprises to provide multiple different services simultaneously. To ensure these services can only be accessed conveniently by authorized users, many password and smart card based authentication schemes for multiserver architecture have been proposed. Recently, Truong et al. introduced an identity based user authentication scheme on elliptic curve cryptography in multiserver environment and claimed that their scheme is secure against popular attacks. However, in this paper, we point out that their scheme suffers from offline password guessing and impersonation attack and fails to achieve security requirements of this kind of authentication scheme. Moreover, we put forward a new scheme to conquer security pitfalls in the above scheme. Security analysis indicates that the proposed scheme can be free from well-known attacks. Performance discussion demonstrates that our scheme has advantages in terms of both security property and computation efficiency and thus is more desirable for practical applications in multiserver environment.


---

## Body

## 1. Introduction

The authentication and key agreement protocol is one of fundamental building blocks for securing communications over the Internet. It enables protocol participants to authenticate each other’s identities and establish shared session keys subsequently used by encryption algorithms and is widely implemented in many areas, such as online-shopping, Internet banking, electronic governance, and electronic medical record system.Roughly speaking, the above application scenarios can be abstracted to a user-server model. That is, when a user wants to remotely access the service provided by a server, he/she first registers with the service provider. Then, the service provider can ensure that the service can only be accessed by legitimate users; meanwhile, the user can believe that the service provider is legal. So far, there are many kinds of authentication scheme that are applicable to the user-server setting, such as certificate-based authentication scheme [1, 2], identity-based authentication scheme [3–5], and password-based authentication scheme [6, 7].Among these variants of authentication scheme, password-based authentication scheme is particularly attractive due to its unique features, i.e., the password is easy to remember and the scheme is conveniently to be deployed. Specifically, in the context of this kind of authentication scheme, each user possesses a personal password, as the credential of accessing the service provider by a server. At the same time, the service provider maintains a table to verify the validity of all user’s passwords such that invalid users’ access request would be rejected. However, this also makes the scheme vulnerable to offline password guessing attack, especially when the verification table is disclosed. To conquer this issue, smart card is introduced into the design of password-based authentication scheme, which results in password and smart card based two-factor authentication scheme. Such an authentication provides stronger security guarantee; namely, even if the password or the smart card (not the both) gets exposed, the scheme can remain secure. Since the introduction of this kind of two-factor authentication scheme, a lot of schemes [8–14] based on different cryptography primitives have been proposed. Particularly, these schemes are designed for the single server environment.On the other hand, the rapid development of information and network technologies brings a number of new information systems, e.g., social networks, wireless sensor networks, and cloud computing, which can provide multiple services simultaneously. To solve the access control problem in the setting of multiple service providers, we can concurrently implement multiple instances of a password and smart card based authentication scheme designed in the single server environment. However, for a system user, this will bring tremendous workload of managing passwords and smart cards issued by different service providers. In addition, it also increases the damage of password disclosure.To improve the usability of password and smart card based authentication scheme, researchers propose to design this kind of authentication scheme for multiserver architecture. Informally, in the improved scheme, each user just needs to register with a registration center and then can access any service provided by those servers managed by the registration center. Specifically, Yeh [15] recently proposed such authentication scheme based on RSA cryptosystem and proved its security in the random oracle model. However, Truong et al. [16] found that Yeh’s scheme fails to provide mutual authentication and key agreement, which are basic security requirements of an authentication scheme. Furthermore, they proposed a new scheme to conquer these security pitfalls. Their scheme is built upon elliptic curve cryptography and is claimed to be secure against various attacks. Unfortunately, in this paper, we will demonstrate that Truong et al.’s [16] scheme cannot resist impersonation attack and offline password guessing attack, which is the most realistic and serious threat against this kind of authentication scheme. In addition, we also put forward a security enhanced password and smart card based authentication scheme in multiserver environment. The security analysis and performance discussion indicate that our scheme has advantages in terms of both security property and computation efficiency and thus are more desirable for practical applications.


### 1.1. Related Work

In 1981 Lamport [17] proposed the first password authentication scheme. This scheme is built upon cryptographically secure one-way hash function and has advantages of simplicity and convenience. However, it inevitably suffers from password guessing attack and the threat of the disclosure of the verification table. To enhance the security of password-based authentication scheme, Chang and Wu [18] introduced password and smart card based two-factor remote user authentication scheme. Since then, a number of such schemes [19–27] have been proposed to improve the security and efficiency of this kind of authentication scheme. In general, these schemes fall into two types, i.e., using static identity or dynamic identity. The main drawback of using static identity is that publicly transmitted identity will reveal user privacy. To conquer this issue, Das et al. [19] introduced the notion of password and smart card authentication scheme using dynamic identity and proposed a concrete protocol. However, Liao et al. [28] pointed out that this scheme cannot resist user impersonation attack and also proposed an improved scheme with mutual authentication. Subsequently, although there are various similar schemes designed to fix security pitfalls in previous schemes, most of them [20–22] are still vulnerable to offline password guessing attack when the smart card is lost.Today, with the rapid development of information and network technologies, more and more network enterprises can simultaneously provide multiple different kinds of services. If we directly use those authentication schemes designed for the single server environment, then a user has to register with all of service providers, which will bring heavy workload for the user to manage all passwords and identities. To solve this problem, Li et al. [29] proposed a password authentication scheme based on neural network in multiserver environment and claimed that one registration enables a user to access all of services. Subsequently, Lin et al. [30] gave a new scheme based on ElGamal signature to improve the efficiency of Li et al.’s scheme. Moreover, Juang [31] further used hash function and symmetric encryption algorithm to decrease the computation cost of this kind of authentication. However, Ku et al. [32] found that Juang’s scheme cannot resist insider attack and also cannot support perfect forward secrecy.To enhance the security of the above password-based authentication schemes for multiserver environment, in 2009 Liao and Wang [33] proposed the first password and smart card based authentication scheme in the multiserver environment using dynamic identity. But Hsiang and Shih [34] immediately noted that Liao et al.’s scheme is vulnerable to inside attack, impersonation attack, and forgery attack. Although Hsiang and Shih gave an improved scheme, Sood et al. [35] found that Hsiang and Shih’s scheme is susceptible to replay attack, impersonation attack, and stolen smart card attack. Recently, motivated by security requirements from different areas, a few of new two-factor authentication schemes [15, 16, 36–40] for multiserver environment have been put forward. These schemes are mainly built upon elliptic curve cryptosystem. In addition, there are several works that introduce biometrics into the design of authentication scheme for multiserver environment. For example, Odelu et al. [41] proposed a secure multiserver authentication protocol using biometric-based smart card. He and Wang [42] presented a biometrics-based three-factor authentication scheme for multiserver environment using elliptic curve cryptography. Moreover, there are a few similarly schemes [43–46] that are put forward recently. Although there have been various multifactor authentication schemes for multiserver environment, how to design a secure and efficient authentication scheme remains challenging.


### 1.2. Outline

The remainder of this paper is organized as follows. Section2 briefly reviews Truong et al.’s [16] authentication scheme. Two kinds of practical attack against their scheme are provided in Section 3. We propose a security enhanced password and smart card based authentication scheme in multiserver environment in Section 4 and present the corresponding security analysis in Section 5. Section 6 discusses the performance of the proposed scheme. Finally, we give the conclusion in Section 7.


## 1.1. Related Work

In 1981 Lamport [17] proposed the first password authentication scheme. This scheme is built upon cryptographically secure one-way hash function and has advantages of simplicity and convenience. However, it inevitably suffers from password guessing attack and the threat of the disclosure of the verification table. To enhance the security of password-based authentication scheme, Chang and Wu [18] introduced password and smart card based two-factor remote user authentication scheme. Since then, a number of such schemes [19–27] have been proposed to improve the security and efficiency of this kind of authentication scheme. In general, these schemes fall into two types, i.e., using static identity or dynamic identity. The main drawback of using static identity is that publicly transmitted identity will reveal user privacy. To conquer this issue, Das et al. [19] introduced the notion of password and smart card authentication scheme using dynamic identity and proposed a concrete protocol. However, Liao et al. [28] pointed out that this scheme cannot resist user impersonation attack and also proposed an improved scheme with mutual authentication. Subsequently, although there are various similar schemes designed to fix security pitfalls in previous schemes, most of them [20–22] are still vulnerable to offline password guessing attack when the smart card is lost.Today, with the rapid development of information and network technologies, more and more network enterprises can simultaneously provide multiple different kinds of services. If we directly use those authentication schemes designed for the single server environment, then a user has to register with all of service providers, which will bring heavy workload for the user to manage all passwords and identities. To solve this problem, Li et al. [29] proposed a password authentication scheme based on neural network in multiserver environment and claimed that one registration enables a user to access all of services. Subsequently, Lin et al. [30] gave a new scheme based on ElGamal signature to improve the efficiency of Li et al.’s scheme. Moreover, Juang [31] further used hash function and symmetric encryption algorithm to decrease the computation cost of this kind of authentication. However, Ku et al. [32] found that Juang’s scheme cannot resist insider attack and also cannot support perfect forward secrecy.To enhance the security of the above password-based authentication schemes for multiserver environment, in 2009 Liao and Wang [33] proposed the first password and smart card based authentication scheme in the multiserver environment using dynamic identity. But Hsiang and Shih [34] immediately noted that Liao et al.’s scheme is vulnerable to inside attack, impersonation attack, and forgery attack. Although Hsiang and Shih gave an improved scheme, Sood et al. [35] found that Hsiang and Shih’s scheme is susceptible to replay attack, impersonation attack, and stolen smart card attack. Recently, motivated by security requirements from different areas, a few of new two-factor authentication schemes [15, 16, 36–40] for multiserver environment have been put forward. These schemes are mainly built upon elliptic curve cryptosystem. In addition, there are several works that introduce biometrics into the design of authentication scheme for multiserver environment. For example, Odelu et al. [41] proposed a secure multiserver authentication protocol using biometric-based smart card. He and Wang [42] presented a biometrics-based three-factor authentication scheme for multiserver environment using elliptic curve cryptography. Moreover, there are a few similarly schemes [43–46] that are put forward recently. Although there have been various multifactor authentication schemes for multiserver environment, how to design a secure and efficient authentication scheme remains challenging.


## 1.2. Outline

The remainder of this paper is organized as follows. Section2 briefly reviews Truong et al.’s [16] authentication scheme. Two kinds of practical attack against their scheme are provided in Section 3. We propose a security enhanced password and smart card based authentication scheme in multiserver environment in Section 4 and present the corresponding security analysis in Section 5. Section 6 discusses the performance of the proposed scheme. Finally, we give the conclusion in Section 7.


## 2. Review of Truong et al.’s Scheme

In this section, we briefly review Truong et al.’s [16] scheme. We summarize the notations used throughout this paper in Table 1. Specifically, Truong et al.’s authentication scheme is comprised of the following four phases.Table 1
The notations used throughout this paper.
Symbol
Description
R
C
The registration center
U
i
Theith system user
S
j
Thejth service provider
P
W
i
The userU
i’s personal password
H
1
(
⋅
)
,
H
2
(
⋅
)
Secure one-way hash functions
⊕
The exclusive or operation
x
i, y
j
Random integers picked byU
i and S
j
T
i, T
j
The timestamps on sides ofU
i and S
j
α
The master secret key ofR
C
U
I
D
i
The userU
i’s identity
S
I
D
j
The serverS
j’s identity
A
S
I
D
j
The serverS
j’s secret key
[
m
]
The integer set{
1,2
,
…
,
m
}
∥
The concatenation operation
S
K
i
,
j, S
K
j
,
i
Shared session key
Δ
T
The maximum delay allowed


### 2.1. Initialization Phase

In this phase, the registration centerR
C is given a security parameter κ and initializes the system as follows:(1)
Select an elliptic curveE
p
(
a
,
b
) defined over Z
p
∗, where p is a prime number of size κ and a
,
b
∈
Z
p. Let G be a cyclic group derived from E
p
(
a
,
b
) with prime order q and let g
∈
G be a random generator.
(2)
Randomly chooseα
∈
Z
q
∗ and select two hash functions h
1
:
{
0,1
}
∗
→
{
0,1
}
n, h
2
:
{
0,1
}
∗
→
G.
(3)
Publish the system public parameter asp
p
=
{
E
p
(
a
,
b
)
,
g
,
h
1
(
·
)
,
h
2
(
·
)
}, and keep m
s
k
=
α as the secret key.


### 2.2. Registration Phase

This phase consists of two parts, i.e., server registration and user registration. First, when a service providerS
j intends to register with the registration center R
C, as indicated in Figure 1, they interactively perform as follows:(1)
The service providerS
j chooses an identity S
I
D
j and submits it to the registration center R
C through a secure channel.
(2)
After receivingS
j’s registration request, the registration center R
C picks a random integer z
j
∈
Z
q and computes A
S
I
D
j
=
α
·
h
2
(
S
I
D
j
∥
z
j
) and then sends {
z
j
,
S
I
D
j
,
A
S
I
D
j
,
h
1
(
·
)
,
h
2
(
·
)
} to the service provider S
j via a secure channel.
(3)
Upon getting the registration centerR
C’s response message, the service provider S
j keeps A
S
I
D
j as its master secret key.Figure 1
Server registration of Truong et al.’s scheme.Second, as shown in Figure2, a user U
i intending to register with the registration center R
C carries out the following steps:(1)
The userU
i chooses an identity U
I
D
i and submits it to the registration R
C via a secure channel.
(2)
After receiving the registration request fromU
i, the registration center R
C randomly selects P
W
i and r
i
∈
Z
q
∗. Then, for each j
∈
[
m
], the registration center R
C computes s
i
,
j
=
h
2
(
U
I
D
i
∥
r
i
)
+
A
S
I
D
j and R
P
W
i
=
h
1
(
P
W
i
∥
U
I
D
i
∥
r
i
).
(3)
The registration centerR
C returns a smart card including the secret information {
R
P
W
i
,
h
1
(
·
)
,
r
i
,
{
s
i
,
j
}
j
=
1
m
} and P
W
i to the user U
i.
(4)
Upon gettingR
C’s response information, the user U
i immediately updates the initial password chosen by R
C.Figure 2
User registration of Truong et al.’s scheme.


### 2.3. Login-In and Authentication Phase

When a userU
i wants to access the service from a provider S
j, they need to interactively perform an authentication procedure to ensure the provided service is legally accessed. As shown in Figure 3, the details of the authentication procedure are as follows:(1)
The userU
i inserts his/her smart card into a card-reader device and inputs the identity U
I
D
i and the password P
W
i.
(2)
The smart card verifies the validity of the userU
i by recomputing the secret value R
P
W
i
′
=
h
1
(
P
W
i
∥
U
I
D
i
∥
r
i
) and checking if R
P
W
i
′
=
R
P
W
i. If not, the smart card terminates the authentication procedure; otherwise, it randomly selects an integer x
i
∈
Z
q
∗ and computes (1)
X
i
=
x
i
·
g
,
X
i
′
=
X
i
+
s
i
,
j
,
M
1
=
h
1
r
i
∥
U
I
D
i
∥
X
i
∥
s
i
,
j
∥
X
i
′
.
After that, the smart card sends the message{
U
I
D
i
,
X
i
′
,
M
1
,
r
i
} to the service provider S
j.
(3)
Upon receiving the message from the userU
i, the service provider S
j verifies U
I
D
i and successively computes (2)
s
i
,
j
′
=
h
2
U
I
D
i
∥
r
i
+
A
S
I
D
j
,
X
i
∗
=
X
i
′
-
s
i
,
j
′
,
M
1
′
=
h
1
r
i
∥
U
I
D
i
∥
X
i
∗
∥
s
i
,
j
′
∥
X
i
′
.
Then, it checks whether it holds thatM
1
′
=
M
1. If not, the service provider S
j also terminates the authentication procedure; otherwise, it chooses a random integer y
j
∈
Z
q
∗ and computes (3)
Y
j
=
y
j
·
g
,
Y
j
′
=
X
i
∗
+
Y
j
,
K
j
,
i
=
y
j
·
X
i
∗
,
M
2
=
h
1
X
i
′
∥
r
i
∥
U
I
D
i
∥
X
i
∗
∥
s
i
,
j
′
∥
Y
j
∥
K
j
,
i
.
Subsequently,S
j sends the message {
M
2
,
Y
j
′
} to the user U
i.
(4)
After receiving the message from the service providerS
j, the user U
i’s smart card computes (4)
Y
j
∗
=
Y
j
′
-
X
i
,
K
i
,
j
=
x
i
·
Y
j
∗
,
M
2
′
=
h
1
X
i
′
∥
r
i
∥
U
I
D
i
∥
X
i
∥
s
i
,
j
∥
Y
j
∗
∥
K
i
,
j
.
Then, the smart card checks ifM
2
′
=
M
2. If not, the authentication procedure is terminated; otherwise, the smart card successfully authenticates the service provider S
j and sends M
3
=
h
1
(
X
i
∥
Y
j
∗
∥
K
i
,
j
) to S
j.
(5)
When receiving the messageM
3 from the user U
i, the service provider recomputes M
3
′
=
h
1
(
X
i
∗
∥
Y
j
∥
K
j
,
i
) and checks if M
3
′
=
M
3. If not, S
j terminates the authentication procedure; otherwise, the user U
i is successfully authenticated by the service provider S
j.
(6)
The userU
i and the service provider S
j derive a shared session key: (5)
S
K
=
h
1
K
i
,
j
∥
U
I
D
i
∥
S
I
D
j
=
h
1
K
j
,
i
∥
U
I
D
i
∥
S
I
D
j
.
This completes the authentication procedure.Figure 3
Authentication phase of Truong et al.’s scheme.


### 2.4. Password Update Phase

When a userU
i wants to update his/her password, he/she can conveniently achieve this goal by performing the following procedure:(1)
The userU
i inserts the smart card into a card-reader device and provides the corresponding identity U
I
D
i and password P
W
i.
(2)
The smart card recomputesR
P
W
i
′
=
h
1
(
P
W
i
∥
U
I
D
i
∥
r
i
) and checks if it holds that R
P
W
i
′
=
R
P
W
i. If not, the update procedure is terminated; otherwise, the smart card requires the user U
i to input a new password P
W
i
n
e
w and computes R
P
W
i
n
e
w
=
h
1
(
P
W
i
n
e
w
∥
U
I
D
i
∥
r
i
).
(3)
Finally, the smart card replacesR
P
W
i with R
P
W
i
n
e
w. This completes the update procedure.


## 2.1. Initialization Phase

In this phase, the registration centerR
C is given a security parameter κ and initializes the system as follows:(1)
Select an elliptic curveE
p
(
a
,
b
) defined over Z
p
∗, where p is a prime number of size κ and a
,
b
∈
Z
p. Let G be a cyclic group derived from E
p
(
a
,
b
) with prime order q and let g
∈
G be a random generator.
(2)
Randomly chooseα
∈
Z
q
∗ and select two hash functions h
1
:
{
0,1
}
∗
→
{
0,1
}
n, h
2
:
{
0,1
}
∗
→
G.
(3)
Publish the system public parameter asp
p
=
{
E
p
(
a
,
b
)
,
g
,
h
1
(
·
)
,
h
2
(
·
)
}, and keep m
s
k
=
α as the secret key.


## 2.2. Registration Phase

This phase consists of two parts, i.e., server registration and user registration. First, when a service providerS
j intends to register with the registration center R
C, as indicated in Figure 1, they interactively perform as follows:(1)
The service providerS
j chooses an identity S
I
D
j and submits it to the registration center R
C through a secure channel.
(2)
After receivingS
j’s registration request, the registration center R
C picks a random integer z
j
∈
Z
q and computes A
S
I
D
j
=
α
·
h
2
(
S
I
D
j
∥
z
j
) and then sends {
z
j
,
S
I
D
j
,
A
S
I
D
j
,
h
1
(
·
)
,
h
2
(
·
)
} to the service provider S
j via a secure channel.
(3)
Upon getting the registration centerR
C’s response message, the service provider S
j keeps A
S
I
D
j as its master secret key.Figure 1
Server registration of Truong et al.’s scheme.Second, as shown in Figure2, a user U
i intending to register with the registration center R
C carries out the following steps:(1)
The userU
i chooses an identity U
I
D
i and submits it to the registration R
C via a secure channel.
(2)
After receiving the registration request fromU
i, the registration center R
C randomly selects P
W
i and r
i
∈
Z
q
∗. Then, for each j
∈
[
m
], the registration center R
C computes s
i
,
j
=
h
2
(
U
I
D
i
∥
r
i
)
+
A
S
I
D
j and R
P
W
i
=
h
1
(
P
W
i
∥
U
I
D
i
∥
r
i
).
(3)
The registration centerR
C returns a smart card including the secret information {
R
P
W
i
,
h
1
(
·
)
,
r
i
,
{
s
i
,
j
}
j
=
1
m
} and P
W
i to the user U
i.
(4)
Upon gettingR
C’s response information, the user U
i immediately updates the initial password chosen by R
C.Figure 2
User registration of Truong et al.’s scheme.


## 2.3. Login-In and Authentication Phase

When a userU
i wants to access the service from a provider S
j, they need to interactively perform an authentication procedure to ensure the provided service is legally accessed. As shown in Figure 3, the details of the authentication procedure are as follows:(1)
The userU
i inserts his/her smart card into a card-reader device and inputs the identity U
I
D
i and the password P
W
i.
(2)
The smart card verifies the validity of the userU
i by recomputing the secret value R
P
W
i
′
=
h
1
(
P
W
i
∥
U
I
D
i
∥
r
i
) and checking if R
P
W
i
′
=
R
P
W
i. If not, the smart card terminates the authentication procedure; otherwise, it randomly selects an integer x
i
∈
Z
q
∗ and computes (1)
X
i
=
x
i
·
g
,
X
i
′
=
X
i
+
s
i
,
j
,
M
1
=
h
1
r
i
∥
U
I
D
i
∥
X
i
∥
s
i
,
j
∥
X
i
′
.
After that, the smart card sends the message{
U
I
D
i
,
X
i
′
,
M
1
,
r
i
} to the service provider S
j.
(3)
Upon receiving the message from the userU
i, the service provider S
j verifies U
I
D
i and successively computes (2)
s
i
,
j
′
=
h
2
U
I
D
i
∥
r
i
+
A
S
I
D
j
,
X
i
∗
=
X
i
′
-
s
i
,
j
′
,
M
1
′
=
h
1
r
i
∥
U
I
D
i
∥
X
i
∗
∥
s
i
,
j
′
∥
X
i
′
.
Then, it checks whether it holds thatM
1
′
=
M
1. If not, the service provider S
j also terminates the authentication procedure; otherwise, it chooses a random integer y
j
∈
Z
q
∗ and computes (3)
Y
j
=
y
j
·
g
,
Y
j
′
=
X
i
∗
+
Y
j
,
K
j
,
i
=
y
j
·
X
i
∗
,
M
2
=
h
1
X
i
′
∥
r
i
∥
U
I
D
i
∥
X
i
∗
∥
s
i
,
j
′
∥
Y
j
∥
K
j
,
i
.
Subsequently,S
j sends the message {
M
2
,
Y
j
′
} to the user U
i.
(4)
After receiving the message from the service providerS
j, the user U
i’s smart card computes (4)
Y
j
∗
=
Y
j
′
-
X
i
,
K
i
,
j
=
x
i
·
Y
j
∗
,
M
2
′
=
h
1
X
i
′
∥
r
i
∥
U
I
D
i
∥
X
i
∥
s
i
,
j
∥
Y
j
∗
∥
K
i
,
j
.
Then, the smart card checks ifM
2
′
=
M
2. If not, the authentication procedure is terminated; otherwise, the smart card successfully authenticates the service provider S
j and sends M
3
=
h
1
(
X
i
∥
Y
j
∗
∥
K
i
,
j
) to S
j.
(5)
When receiving the messageM
3 from the user U
i, the service provider recomputes M
3
′
=
h
1
(
X
i
∗
∥
Y
j
∥
K
j
,
i
) and checks if M
3
′
=
M
3. If not, S
j terminates the authentication procedure; otherwise, the user U
i is successfully authenticated by the service provider S
j.
(6)
The userU
i and the service provider S
j derive a shared session key: (5)
S
K
=
h
1
K
i
,
j
∥
U
I
D
i
∥
S
I
D
j
=
h
1
K
j
,
i
∥
U
I
D
i
∥
S
I
D
j
.
This completes the authentication procedure.Figure 3
Authentication phase of Truong et al.’s scheme.


## 2.4. Password Update Phase

When a userU
i wants to update his/her password, he/she can conveniently achieve this goal by performing the following procedure:(1)
The userU
i inserts the smart card into a card-reader device and provides the corresponding identity U
I
D
i and password P
W
i.
(2)
The smart card recomputesR
P
W
i
′
=
h
1
(
P
W
i
∥
U
I
D
i
∥
r
i
) and checks if it holds that R
P
W
i
′
=
R
P
W
i. If not, the update procedure is terminated; otherwise, the smart card requires the user U
i to input a new password P
W
i
n
e
w and computes R
P
W
i
n
e
w
=
h
1
(
P
W
i
n
e
w
∥
U
I
D
i
∥
r
i
).
(3)
Finally, the smart card replacesR
P
W
i with R
P
W
i
n
e
w. This completes the update procedure.


## 3. Cryptanalysis of Truong et al.’s Authentication Scheme

In this section, we show that Truong et al.’s [16] protocol suffers from offline password guessing attack and server impersonation attack. To this end, we first formalize the adversary’s capacity. Roughly, in the literature of two-factor authentication scheme based on password and smart card, an adversary is allowed to(i)
overhear, modify, synthesize, and intercept any messages transmitted over the public channel,
(ii)
obtain the user’s password or the private information stored in the smart card by using the technologies introduced in [48, 49], but not both.The above two assumptions about the adversary’s capacity are widely recognised and adopted in the security analysis of password and smart card based two-factor authentication protocols, including [16]’s protocol and our scheme. Below we give the attack details.


### 3.1. Offline Password Guessing Attack

To launch this kind of attack against a userU
i, an adversary A records the message {
U
I
D
i
,
X
i
′
,
M
1
,
r
i
} appearing in some instance of the authentication procedure executed between U
i and a server S
j and then steals U
i’s smart card and extracts secret values {
R
P
W
i
,
h
1
(
·
)
,
r
i
,
{
s
i
,
j
}
j
=
1
m
}. After that, the adversary A performs as follows:(1)
Construct a personal password dictionaryD, and select a candidate password P
W
i
∗
∈
D.
(2)
ComputeR
P
W
i
∗
=
h
1
(
P
W
i
∗
∥
U
I
D
i
∥
r
i
), and check if it holds that R
P
W
i
∗
=
P
R
W
i. If yes, it implies that A’s guess is correct; otherwise, go to the next step.
(3)
Choose a new candidate password, and repeat the previous step until the correct password is recovered.After the adversaryA gets the correct password, it can further completely impersonate the user U
i since it simultaneously holds U
i’s password and smart card. On the other hand, the computation cost of verifying a candidate password is only one hash operation, which is nearly negligible when running it on a personal computer. Thus, the entire complexity of completing the password guessing attack is linear in the size of the password dictionary D, which is rather small in practice. This implies that the adversary A can recover a user’s password in just a few minutes and this kind of attack is practical.


### 3.2. Impersonation Attack

In this kind of attack, a malicious user (adversary) tries to impersonate a legal user or a server. We demonstrate that a malicious userU
x can impersonate any legal server and user.First, the malicious userU
x extracts secret values {
R
P
W
x
,
h
1
(
·
)
,
r
x
,
{
s
x
,
j
}
j
=
1
m
} stored in his/her smart card, where s
x
,
j
=
h
2
(
U
I
D
x
∥
r
x
)
+
A
S
I
D
j for any j
∈
[
m
]. Intuitively, U
x can directly get A
S
I
D
j
=
s
x
,
j
-
h
2
(
U
I
D
x
∥
r
x
) (the values s
x
,
j
,
U
I
D
x
,
r
x are all available for U
x. In Truong et al.’s protocol, although the hash function h
2
(
·
) is not stored in the user’s smart card, we think it is public and is available for any one. In fact, the user can also get h
2
(
·
) from a malicious server), which is the only secret value of the server S
j. Consequently, U
x can utilize it to impersonate the server S
j at any time.Second, for any userU
i, since his/her identity U
I
D
i and the random value r
i are transmitted over the public channel, then the malicious user U
x can directly compute the secret value s
i
,
j
=
h
2
(
U
I
D
i
∥
r
i
)
+
A
S
I
D
j with the corrupted secret value A
S
I
D
j. Furthermore, by using s
i
,
j, the malicious user U
x can impersonate the user U
i to access the service provided by the server S
j, even if he/she does not know U
i’s password. Essentially speaking, this is mainly because that the correctness of the password is locally checked by the smart card, rather than by the corresponding server.In short, by either launching offline password guessing attack or using the above two variants of impersonation attack in a combinational way, a malicious user (adversary) can totally break the security of Turong et al.’s [16] scheme. Thus, it does not achieve the intended security requirements and is not adaptable for practical applications.


## 3.1. Offline Password Guessing Attack

To launch this kind of attack against a userU
i, an adversary A records the message {
U
I
D
i
,
X
i
′
,
M
1
,
r
i
} appearing in some instance of the authentication procedure executed between U
i and a server S
j and then steals U
i’s smart card and extracts secret values {
R
P
W
i
,
h
1
(
·
)
,
r
i
,
{
s
i
,
j
}
j
=
1
m
}. After that, the adversary A performs as follows:(1)
Construct a personal password dictionaryD, and select a candidate password P
W
i
∗
∈
D.
(2)
ComputeR
P
W
i
∗
=
h
1
(
P
W
i
∗
∥
U
I
D
i
∥
r
i
), and check if it holds that R
P
W
i
∗
=
P
R
W
i. If yes, it implies that A’s guess is correct; otherwise, go to the next step.
(3)
Choose a new candidate password, and repeat the previous step until the correct password is recovered.After the adversaryA gets the correct password, it can further completely impersonate the user U
i since it simultaneously holds U
i’s password and smart card. On the other hand, the computation cost of verifying a candidate password is only one hash operation, which is nearly negligible when running it on a personal computer. Thus, the entire complexity of completing the password guessing attack is linear in the size of the password dictionary D, which is rather small in practice. This implies that the adversary A can recover a user’s password in just a few minutes and this kind of attack is practical.


## 3.2. Impersonation Attack

In this kind of attack, a malicious user (adversary) tries to impersonate a legal user or a server. We demonstrate that a malicious userU
x can impersonate any legal server and user.First, the malicious userU
x extracts secret values {
R
P
W
x
,
h
1
(
·
)
,
r
x
,
{
s
x
,
j
}
j
=
1
m
} stored in his/her smart card, where s
x
,
j
=
h
2
(
U
I
D
x
∥
r
x
)
+
A
S
I
D
j for any j
∈
[
m
]. Intuitively, U
x can directly get A
S
I
D
j
=
s
x
,
j
-
h
2
(
U
I
D
x
∥
r
x
) (the values s
x
,
j
,
U
I
D
x
,
r
x are all available for U
x. In Truong et al.’s protocol, although the hash function h
2
(
·
) is not stored in the user’s smart card, we think it is public and is available for any one. In fact, the user can also get h
2
(
·
) from a malicious server), which is the only secret value of the server S
j. Consequently, U
x can utilize it to impersonate the server S
j at any time.Second, for any userU
i, since his/her identity U
I
D
i and the random value r
i are transmitted over the public channel, then the malicious user U
x can directly compute the secret value s
i
,
j
=
h
2
(
U
I
D
i
∥
r
i
)
+
A
S
I
D
j with the corrupted secret value A
S
I
D
j. Furthermore, by using s
i
,
j, the malicious user U
x can impersonate the user U
i to access the service provided by the server S
j, even if he/she does not know U
i’s password. Essentially speaking, this is mainly because that the correctness of the password is locally checked by the smart card, rather than by the corresponding server.In short, by either launching offline password guessing attack or using the above two variants of impersonation attack in a combinational way, a malicious user (adversary) can totally break the security of Turong et al.’s [16] scheme. Thus, it does not achieve the intended security requirements and is not adaptable for practical applications.


## 4. The Proposed Scheme

In this section, to conquer those security pitfalls in Turong et al.’s [16] protocol, we propose a security enhanced password and smart card based authentication scheme in multiserver environment. Before describing the concrete scheme, we give an overview to demonstrate our design criteria.Note that the reason of Turong et al.’s [16] protocol suffering from offline password guessing attack mainly lies in the fact that the password correctness islocally verified by the smart card. As a result, when the smart card is lost, an adversary can utilize the secret value stored in the smart card to launch offline password guessing attack. In our scheme, we let the service provider check the password validity. Specifically, after a user inputs his/her password, the smart card uses it to recover a secret value, which is computable for the service provider. Then, by verifying the correctness of the secret value, the service provider can ensure whether the user holds the correct password or not. In addition, these messages transmitted over the public channel should also avoid being used to check the validity of the password.On the other hand, to prevent a malicious user from directly recovering a server’s secret key (i.e.,A
S
I
D
j in Turong et al.’s [16] protocol), we let the registration center first perform hash operation on each server’s secret key and then use it to produce a private value for the user, rather than directly employing the server’s secret key to do that as in Turong et al.’s [16] protocol. As shown in the security analysis of our scheme, this enables our scheme to be free from user/server impersonation attack. Moreover, as in the design of most authentication schemes, we call Diffie-Hellman key exchange mechanism to achieve key agreement and forward security and exploit the freshness of random numbers and timestamps to prevent replay attack.The concrete authentication scheme is comprised of four phases: initialization phase, registration phase, authentication phase, and password update phase, which are separately specialized as follows.


### 4.1. Initialization Phase

In this phase, the registration center initializes the system according to a security parameterκ as follows:(1)
Choose a prime numberp with the size κ and then generate an elliptic curve E
p
(
a
,
b
) defined over Z
p
∗, where a
,
b
∈
Z
p. Furthermore, produce a cyclic group G with prime order q from E
p
(
a
,
b
), and randomly pick a generator g
∈
G.
(2)
Randomly sample an integerα from Z
q
∗, and choose two cryptographically secure hash functions H
1
:
{
0,1
}
∗
→
{
0,1
}
n, H
2
:
{
0,1
}
∗
→
G.
(3)
Publish the system public parameter asp
p
=
{
E
p
(
a
,
b
)
,
g
,
H
1
(
·
)
,
H
2
(
·
)
}, which are available to all system users, and set m
s
k
=
α as the master secret key.


### 4.2. Registration Phase

In this phase, each system userU
i registers with the registration center R
C to get a smart card containing several secret values, as a credential of U
i to prove his/her authenticity to service providers. Each service provider S
j registers with R
C to obtain a secret key, as a credential of S
j to show its legality to system users.Specifically speaking, to register withR
C, as shown in Figure 4, service providers S
j and R
C perform as follows:(1)
The service providerS
j selects a unique identity S
I
D
j and sends it to the registration center R
C via a secure channel.
(2)
Upon receiving the registration request fromS
j, the registration center R
C directly computes A
S
I
D
j
=
H
2
(
S
I
D
j
∥
α
) and then sends the message {
A
S
I
D
j
} to S
j through a secure channel.
(3)
After obtaining the registration centerR
C’s response message, S
j keeps A
S
I
D
j as its secret key.Figure 4
Server registration in our scheme.For a system userU
i intending to register with the registration center R
C, as shown in Figure 5, they interactively conduct the following steps:(1)
The userU
i selects a unique identity U
I
D
i and a personal password P
W
i easy to remember. Moreover, he/she randomly samples an integer r
i
∈
Z
q
∗ and computes R
P
W
i
=
H
1
(
P
W
i
∥
r
i
). Then, U
i sends the registration request message {
U
I
D
i
,
P
R
W
i
} to R
C via a secure channel.
(2)
After receiving the registration request fromU
i, the registration center R
C computes s
i
,
j
=
H
1
(
A
S
I
D
j
∥
U
I
D
i
)
⊕
R
P
W
i for each j
∈
[
m
] and issues a smart card containing {
{
s
i
,
j
}
j
=
1
m
,
H
1
(
·
)
,
H
2
(
·
)
,
g
} to the user U
i.
(3)
Upon receipt of the smart card, the userU
i rewrites the random value r
i into the smart card and keeps properly.Figure 5
User registration in our scheme.


### 4.3. Authentication Phase

By running an authentication procedure between a system userU
i and a service provider S
j, they can check the validity of each other and establish a secure channel. That is, S
j ensures that U
i is a registered user, and U
i believes that the service provided by S
j is legal. As shown in Figure 6, such a procedure is performed as follows:(1)
The userU
i attaches his/her smart card to a card-reader device and inputs his/her identity U
I
D
i and the corresponding password P
W
i.
(2)
U
i’s smart card first computes R
P
W
i
′
=
H
1
(
P
W
i
∥
U
I
D
i
∥
r
i
) and s
i
,
j
′
=
s
i
,
j
⊕
R
P
W
i
′. Then, it randomly selects an integer x
i
∈
Z
q
∗ and further calculates (6)
X
i
=
x
i
·
g
,
X
i
′
=
X
i
+
H
2
s
i
,
j
′
,
M
1
=
H
1
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
T
i
,
whereT
i is the current timestamp. After that, the smart card sends the authentication request message {
U
I
D
i
,
X
i
′
,
T
i
,
M
1
} to the service provider S
j.
(3)
Upon the receipt of the message from the userU
i, the service provider S
j checks the validity of U
I
D
i and T
i by verifying if |
T
j
c
-
T
i
|
≤
Δ
T, where T
j
c is the current timestamp. If not, the user’s authentication request would be rejected. Moreover, S
j computes M
1
′
=
H
1
(
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
T
i
). Then, it checks whether it holds that M
1
′
=
M
1. If not, the service provider S
j terminates the authentication procedure; otherwise, it chooses a random integer y
j
∈
Z
q
∗ and computes (7)
s
i
,
j
′
=
H
1
A
S
I
D
j
∥
U
I
D
i
,
X
i
∗
=
X
i
′
-
H
2
s
i
,
j
′
,
Y
j
=
y
j
·
g
,
Y
j
′
=
X
i
∗
+
Y
j
,
K
j
,
i
=
y
j
·
X
i
∗
,
M
2
=
H
1
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
Y
j
′
∥
K
j
,
i
∥
T
j
,
whereT
j is the current timestamp. Subsequently, S
j sends the message {
M
2
,
Y
j
′
,
T
j
} to the user U
i.
(4)
After receiving the message from the service providerS
j, the user U
i’s smart card first checks the validity of T
j by verifying if |
T
i
c
-
T
j
|
≤
Δ
T, where T
i
c is the current timestamp. After that, it computes (8)
Y
j
∗
=
Y
j
′
-
X
i
,
K
i
,
j
=
x
i
·
Y
j
∗
,
M
2
′
=
H
1
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
Y
j
′
∥
K
i
,
j
∥
T
j
.
Then, the smart card checks ifM
2
′
=
M
2. If not, the authentication procedure is terminated; otherwise, the smart card successfully authenticates the service provider S
j and sends M
3
=
H
1
(
X
i
∥
Y
j
∗
∥
K
i
,
j
∥
T
i
′
) to S
j, where T
i
′ is the current timestamp.
(5)
When receiving the messageM
3 from the user U
i, the service provider S
j first checks the validity of T
i
′ by verifying if |
T
j
c
-
T
i
′
|
≤
Δ
T, where T
j
c is the current timestamp. Then, S
j recomputes M
3
′
=
H
1
(
X
i
∗
∥
Y
j
∥
K
j
,
i
∥
T
i
′
) and checks if M
3
′
=
M
3. If not, S
j terminates the authentication procedure; otherwise, the user U
i is successfully authenticated by the service provider S
j.
(6)
The userU
i and the service provider S
j derive a shared session key: (9)
S
K
=
H
1
K
i
,
j
∥
U
I
D
i
∥
S
I
D
j
=
H
1
K
j
,
i
∥
U
I
D
i
∥
S
I
D
j
.
This completes the authentication procedure.Figure 6
Authentication phase in our scheme.


### 4.4. Password Update Phase

When a userU
i wants to update his/her original password P
W
i, the following steps are conducted:(1)
U
i randomly selects a service provider S
k, with whom U
i performs the authentication procedure.
(2)
If bothU
i and S
k pass through the authentication, then U
i selects a new password P
W
i
n
e
w and lets the smart card compute (10)
R
P
W
i
n
e
w
=
H
1
P
W
i
n
e
w
∥
r
i
,
s
i
,
j
n
e
w
=
s
i
,
j
⊕
R
P
W
i
⊕
R
P
W
i
n
e
w
for
j
=
1
t
o
m
.
(3)
The smart card replacess
i
,
j with s
i
,
j
n
e
w (1
≤
j
≤
m).Remark 1.
Note that the password update phase in our scheme is significantly different from that in Truong et al.’s [16] scheme, in which the password update is completed in an offline way. This implies that the smart card has to check the validity of the password. As a result, when the smart card is lost, their scheme suffers from offline password guessing attack. However, in our scheme, the validity of the password is verified by a service provider, rather than the smart card. Although the password update phase in our scheme needs more computation and communication cost (compared with Truong et al.’s [16] scheme), it provides stronger security guarantee.


## 4.1. Initialization Phase

In this phase, the registration center initializes the system according to a security parameterκ as follows:(1)
Choose a prime numberp with the size κ and then generate an elliptic curve E
p
(
a
,
b
) defined over Z
p
∗, where a
,
b
∈
Z
p. Furthermore, produce a cyclic group G with prime order q from E
p
(
a
,
b
), and randomly pick a generator g
∈
G.
(2)
Randomly sample an integerα from Z
q
∗, and choose two cryptographically secure hash functions H
1
:
{
0,1
}
∗
→
{
0,1
}
n, H
2
:
{
0,1
}
∗
→
G.
(3)
Publish the system public parameter asp
p
=
{
E
p
(
a
,
b
)
,
g
,
H
1
(
·
)
,
H
2
(
·
)
}, which are available to all system users, and set m
s
k
=
α as the master secret key.


## 4.2. Registration Phase

In this phase, each system userU
i registers with the registration center R
C to get a smart card containing several secret values, as a credential of U
i to prove his/her authenticity to service providers. Each service provider S
j registers with R
C to obtain a secret key, as a credential of S
j to show its legality to system users.Specifically speaking, to register withR
C, as shown in Figure 4, service providers S
j and R
C perform as follows:(1)
The service providerS
j selects a unique identity S
I
D
j and sends it to the registration center R
C via a secure channel.
(2)
Upon receiving the registration request fromS
j, the registration center R
C directly computes A
S
I
D
j
=
H
2
(
S
I
D
j
∥
α
) and then sends the message {
A
S
I
D
j
} to S
j through a secure channel.
(3)
After obtaining the registration centerR
C’s response message, S
j keeps A
S
I
D
j as its secret key.Figure 4
Server registration in our scheme.For a system userU
i intending to register with the registration center R
C, as shown in Figure 5, they interactively conduct the following steps:(1)
The userU
i selects a unique identity U
I
D
i and a personal password P
W
i easy to remember. Moreover, he/she randomly samples an integer r
i
∈
Z
q
∗ and computes R
P
W
i
=
H
1
(
P
W
i
∥
r
i
). Then, U
i sends the registration request message {
U
I
D
i
,
P
R
W
i
} to R
C via a secure channel.
(2)
After receiving the registration request fromU
i, the registration center R
C computes s
i
,
j
=
H
1
(
A
S
I
D
j
∥
U
I
D
i
)
⊕
R
P
W
i for each j
∈
[
m
] and issues a smart card containing {
{
s
i
,
j
}
j
=
1
m
,
H
1
(
·
)
,
H
2
(
·
)
,
g
} to the user U
i.
(3)
Upon receipt of the smart card, the userU
i rewrites the random value r
i into the smart card and keeps properly.Figure 5
User registration in our scheme.


## 4.3. Authentication Phase

By running an authentication procedure between a system userU
i and a service provider S
j, they can check the validity of each other and establish a secure channel. That is, S
j ensures that U
i is a registered user, and U
i believes that the service provided by S
j is legal. As shown in Figure 6, such a procedure is performed as follows:(1)
The userU
i attaches his/her smart card to a card-reader device and inputs his/her identity U
I
D
i and the corresponding password P
W
i.
(2)
U
i’s smart card first computes R
P
W
i
′
=
H
1
(
P
W
i
∥
U
I
D
i
∥
r
i
) and s
i
,
j
′
=
s
i
,
j
⊕
R
P
W
i
′. Then, it randomly selects an integer x
i
∈
Z
q
∗ and further calculates (6)
X
i
=
x
i
·
g
,
X
i
′
=
X
i
+
H
2
s
i
,
j
′
,
M
1
=
H
1
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
T
i
,
whereT
i is the current timestamp. After that, the smart card sends the authentication request message {
U
I
D
i
,
X
i
′
,
T
i
,
M
1
} to the service provider S
j.
(3)
Upon the receipt of the message from the userU
i, the service provider S
j checks the validity of U
I
D
i and T
i by verifying if |
T
j
c
-
T
i
|
≤
Δ
T, where T
j
c is the current timestamp. If not, the user’s authentication request would be rejected. Moreover, S
j computes M
1
′
=
H
1
(
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
T
i
). Then, it checks whether it holds that M
1
′
=
M
1. If not, the service provider S
j terminates the authentication procedure; otherwise, it chooses a random integer y
j
∈
Z
q
∗ and computes (7)
s
i
,
j
′
=
H
1
A
S
I
D
j
∥
U
I
D
i
,
X
i
∗
=
X
i
′
-
H
2
s
i
,
j
′
,
Y
j
=
y
j
·
g
,
Y
j
′
=
X
i
∗
+
Y
j
,
K
j
,
i
=
y
j
·
X
i
∗
,
M
2
=
H
1
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
Y
j
′
∥
K
j
,
i
∥
T
j
,
whereT
j is the current timestamp. Subsequently, S
j sends the message {
M
2
,
Y
j
′
,
T
j
} to the user U
i.
(4)
After receiving the message from the service providerS
j, the user U
i’s smart card first checks the validity of T
j by verifying if |
T
i
c
-
T
j
|
≤
Δ
T, where T
i
c is the current timestamp. After that, it computes (8)
Y
j
∗
=
Y
j
′
-
X
i
,
K
i
,
j
=
x
i
·
Y
j
∗
,
M
2
′
=
H
1
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
Y
j
′
∥
K
i
,
j
∥
T
j
.
Then, the smart card checks ifM
2
′
=
M
2. If not, the authentication procedure is terminated; otherwise, the smart card successfully authenticates the service provider S
j and sends M
3
=
H
1
(
X
i
∥
Y
j
∗
∥
K
i
,
j
∥
T
i
′
) to S
j, where T
i
′ is the current timestamp.
(5)
When receiving the messageM
3 from the user U
i, the service provider S
j first checks the validity of T
i
′ by verifying if |
T
j
c
-
T
i
′
|
≤
Δ
T, where T
j
c is the current timestamp. Then, S
j recomputes M
3
′
=
H
1
(
X
i
∗
∥
Y
j
∥
K
j
,
i
∥
T
i
′
) and checks if M
3
′
=
M
3. If not, S
j terminates the authentication procedure; otherwise, the user U
i is successfully authenticated by the service provider S
j.
(6)
The userU
i and the service provider S
j derive a shared session key: (9)
S
K
=
H
1
K
i
,
j
∥
U
I
D
i
∥
S
I
D
j
=
H
1
K
j
,
i
∥
U
I
D
i
∥
S
I
D
j
.
This completes the authentication procedure.Figure 6
Authentication phase in our scheme.


## 4.4. Password Update Phase

When a userU
i wants to update his/her original password P
W
i, the following steps are conducted:(1)
U
i randomly selects a service provider S
k, with whom U
i performs the authentication procedure.
(2)
If bothU
i and S
k pass through the authentication, then U
i selects a new password P
W
i
n
e
w and lets the smart card compute (10)
R
P
W
i
n
e
w
=
H
1
P
W
i
n
e
w
∥
r
i
,
s
i
,
j
n
e
w
=
s
i
,
j
⊕
R
P
W
i
⊕
R
P
W
i
n
e
w
for
j
=
1
t
o
m
.
(3)
The smart card replacess
i
,
j with s
i
,
j
n
e
w (1
≤
j
≤
m).Remark 1.
Note that the password update phase in our scheme is significantly different from that in Truong et al.’s [16] scheme, in which the password update is completed in an offline way. This implies that the smart card has to check the validity of the password. As a result, when the smart card is lost, their scheme suffers from offline password guessing attack. However, in our scheme, the validity of the password is verified by a service provider, rather than the smart card. Although the password update phase in our scheme needs more computation and communication cost (compared with Truong et al.’s [16] scheme), it provides stronger security guarantee.


## 5. Security Analysis

Although formal security analysis (or provable security) is more desirable, now it is difficult to achieve this requirement due to the complexity of the protocol design. In fact, there are already several similar authentication schemes that are claimed to be provably secure by defining the corresponding security model, or using the BAN logic [50]. However, subsequent works indicate that these schemes all fail to provide the required security properties. Therefore, we use informal and heuristic manner to analyze the security of the proposed scheme. We note that such a manner is widely accepted and used in the literature of multifactor authentication scheme [15, 20, 24, 33, 36, 38, 39, 51].Specifically, we show that our scheme can resist various well-known attacks, including replay attack, impersonation attack, offline password guessing attack, and known-key attack. We also demonstrate that the proposed scheme achieves intended security goals, such as mutual authentication, key agreement, and two-factor authentication.


### 5.1. Replay Attack

To launch the replay attack, an adversary first needs to eavesdrop these messages{
U
I
D
i
,
X
i
′
,
T
i
,
M
1
}, {
M
2
,
Y
j
′
,
T
j
}, and {
M
3
,
T
i
′
} transmitted between a user U
i and a service provider S
j and then resends one of them to U
i or S
j. Now we show how our scheme can be free from this kind of attack.If the adversary sends{
U
I
D
i
,
X
i
′
,
T
i
,
M
1
} (the adversary needs to choose the current timestamp on the user side and recomputes M
1) to the service provider S
j, then S
j would generate a new message {
M
2
n
e
w
,
Y
j
′
n
e
w
,
T
j
n
e
w
} according to the authentication procedure. Note that the computation of Y
j
′
n
e
w involves a new random integer. However, the adversary does not know the random integer x
i originally used in the computation of X
i
′. As a result, the adversary cannot produce correct response message M
3 and would be rejected by the service provider S
j. Similarly, if the adversary wants to send the message {
M
2
,
Y
j
′
,
T
j
} to the user U
i, it also cannot pass through the verification of the user U
i, since U
i would use a new random integer to check its validity, rather than the original x
i. Thus, the proposed scheme can be free from the replay attack. Essentially speaking, we use two kinds of mechanism in a combinatorial way to avoid the replay attack, namely, timestamp and nonce (in the case that the time period in the system cannot be synchronized, the timestamp would fail to prevent the replay attack).


### 5.2. Insider Attack

The insider attack mainly means that a malicious insider party (e.g., the registration center or a service provider) tries to get a user’s password. First, from the perspective of the registration center, it can get the registration informationR
P
W
i
=
H
1
(
P
W
i
∥
r
i
), where r
i is a random integer chosen by the user U
i. Thus, without the knowledge of r
i, the registration center cannot launch offline password guessing attack to recover U
i’s password P
W
i. Second, on the side of a service provider S
j, it also cannot get any information about the user U
i’s password, since those messages transmitted between them do not involve U
i’s password. Therefore, we conclude that our scheme can resist the insider attack.


### 5.3. Impersonation Attack

The impersonation attack against the proposed scheme falls into two classes, i.e., user personation and service provider personation. Below we show that the proposed scheme can withstand these two kinds of impersonation attack.If an adversaryA, which might be a malicious user or a malicious service provider, wants to impersonate user U
i, then it has to correctly compute the challenge value M
3
=
H
1
(
X
i
∥
Y
j
∗
∥
K
i
,
j
∥
T
i
′
). Obviously, for this to be computable, the adversary A has to know the values X
i, Y
j
∗, and K
i
,
j. Moreover, if the adversary itself produces the value X
i
=
x
i
·
g without (if the adversary holds U
i’s password and smart card, then it will not have to impersonate U
i) using U
i’s secret information (i.e., P
W
i and s
i
,
j), then the corresponding value X
i
∗ computed by the service provider is not equal to X
i. As a result, it holds that K
i
,
j
≠
K
j
,
i, which implies that the adversary A cannot pass through the service provider’s authentication since M
3
≠
M
3
′. Thus, the adversary A cannot impersonate the user U
i.On the other hand, if the adversaryA wants to impersonate a service provider S
j, then it also has to pass through a user U
i’s authentication. This requires the adversary A to compute the correct value K
j
,
i
=
y
j
·
X
i
∗. We note that the adversary A cannot get correct X
i
∗
=
X
i
′
-
s
i
,
j
′ without the secret value A
S
I
D
j (s
i
,
j
′
=
H
1
(
A
S
I
D
j
∥
U
I
D
i
)). Consequently, it cannot impersonate the service provider S
j since it cannot produce the correct value M
2.


### 5.4. Offline Password Guessing Attack

To launch the offline password guessing attack, an adversaryA has to hold a value that can be used to check the validity of a candidate password. Below we demonstrate that none of those transmitted messages in the proposed scheme can be used to do this.In the authentication phase of the proposed scheme, note that a userU
i’s password P
W
i is only used to recover the secret value s
i
,
j
′
=
s
i
,
j
⊕
R
P
W
i, and its validity is not verified on the user side. Thus, even if the smart card is lost, those secret values stored in the smart card cannot be used to launch offline password guessing attack. Furthermore, for the first message {
U
I
D
i
,
X
i
,
T
i
,
M
1
}, both the value X
i
′
=
X
i
+
H
2
(
s
i
,
j
′
) and the hash value M
1
=
H
1
(
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
T
i
) involve U
i’s password. However, the computation of M
1 does not need any secret value and thus cannot be used to check the validity of a candidate password. Moreover, without the knowledge of the value X
i, the public value X
i
′ also cannot be used to verify the validity of a candidate password. For the second message {
M
2
,
Y
j
′
} and third message {
M
3
}, observe that they do not involve any information about U
i’s password and thus naturally cannot be used to launch the offline password guessing attack. Therefore, the proposed scheme is secure against password guessing attack.


### 5.5. Known-Key Attack

The known-key attack means that the disclosure of a session key will affect the security of other session keys. In our scheme, a session keyS
K
=
H
1
(
K
i
,
j
∥
U
I
D
∥
S
I
D
j
) is derived from a fresh value K
i
,
j
=
(
x
i
y
j
)
·
g, where x
i and y
j are randomly sampled from Z
q
∗. This implies that all session keys are independent from each other. Thus, the disclosure of a session key has no influence on the security of other session keys, and the proposed scheme can withstand known-key attack.


### 5.6. Mutual Authentication and Key Agreement

In the authentication of the proposed scheme, observe that both the userU
i and the service provider S
j have to respond to the partner’s challenge. Specifically, the service provider S
j uses its secret value A
S
I
D
j to produce a correct response value M
2, whose validity would be checked by the user U
i. On the other hand, the user U
i also utilizes the consistent value X
i to generate a response value M
3, whose correctness would be verified by the service provider S
j. We can see that, to complete the authentication procedure, the user U
i and the service provider S
j are required to pass through each other’s authentication. Thus, the proposed scheme achieves mutual authentication.Focusing on the generation of the session key, we can see that both the userU
i and the service provider contribute to the computation of session key, namely, x
i and y
j. This implies that neither one can completely control the generation of the session key, and the session key can be sufficiently random if at least one of the participants is able to produce sufficiently random inputs. Therefore, the proposed scheme enjoys the functionality of key agreement.


### 5.7. Perfect Forward Secrecy

In the setting of the proposed scheme, the perfect forward secrecy requires that after a userU
i’s secret information (i.e., the password and those secret values stored in the smart card) and a service provider S
j’s secret key A
S
I
D
j get exposed, previous session keys established and used between U
i and S
j should remain secure. By basing our scheme on the Diffie-Hellman protocol, it achieves perfect forward secrecy. Concretely, with the knowledge of U
i and S
j’s secret information, an adversary can recover X
i
=
x
i
·
g and Y
j
=
y
j
·
g. However, from the intractability of the computational Diffie-Hellman problem, we know that it is impossible for A to compute K
i
,
j
=
(
x
i
y
j
)
·
g, and thus A cannot further recover the session key S
K
=
H
1
(
K
i
,
j
∥
U
I
D
i
∥
S
I
D
j
). This is why the perfect forward secrecy of the proposed scheme can be achieved.


### 5.8. Two-Factor Authentication

Two-factor authentication is a major security advantage of password and smart card based authentication scheme. That is, once the password or the smart card is revealed (not the both), the scheme should remain secure. Below we show that the proposed scheme is still secure in the above two cases.In the case that an adversaryA knows a user U
i’s password P
W
i but does not have U
i’s smart card, the adversary A cannot compute s
i
,
j
′
=
s
i
,
j
⊕
R
P
W
i, where s
i
,
j is stored in the smart card and R
P
W
i
=
H
1
(
P
W
i
∥
U
I
D
i
∥
r
i
). As a result, it cannot produce a correct value X
i that is consistent with the one computed by the service provider. Thus, the adversary cannot pass through the service provider’s authentication. Namely, the proposed scheme remains secure in this case.In the case that an adversaryA holds a user’s smart card but does not know the user’s password, as analyzed in the offline password guessing attack, no message can be used check the validity of a candidate password. On the other hand, without the knowledge of the correct password, due to the similar reason, the adversary A also cannot pass through the service provider’s authentication. Thus, the proposed scheme is still secure in this case.


## 5.1. Replay Attack

To launch the replay attack, an adversary first needs to eavesdrop these messages{
U
I
D
i
,
X
i
′
,
T
i
,
M
1
}, {
M
2
,
Y
j
′
,
T
j
}, and {
M
3
,
T
i
′
} transmitted between a user U
i and a service provider S
j and then resends one of them to U
i or S
j. Now we show how our scheme can be free from this kind of attack.If the adversary sends{
U
I
D
i
,
X
i
′
,
T
i
,
M
1
} (the adversary needs to choose the current timestamp on the user side and recomputes M
1) to the service provider S
j, then S
j would generate a new message {
M
2
n
e
w
,
Y
j
′
n
e
w
,
T
j
n
e
w
} according to the authentication procedure. Note that the computation of Y
j
′
n
e
w involves a new random integer. However, the adversary does not know the random integer x
i originally used in the computation of X
i
′. As a result, the adversary cannot produce correct response message M
3 and would be rejected by the service provider S
j. Similarly, if the adversary wants to send the message {
M
2
,
Y
j
′
,
T
j
} to the user U
i, it also cannot pass through the verification of the user U
i, since U
i would use a new random integer to check its validity, rather than the original x
i. Thus, the proposed scheme can be free from the replay attack. Essentially speaking, we use two kinds of mechanism in a combinatorial way to avoid the replay attack, namely, timestamp and nonce (in the case that the time period in the system cannot be synchronized, the timestamp would fail to prevent the replay attack).


## 5.2. Insider Attack

The insider attack mainly means that a malicious insider party (e.g., the registration center or a service provider) tries to get a user’s password. First, from the perspective of the registration center, it can get the registration informationR
P
W
i
=
H
1
(
P
W
i
∥
r
i
), where r
i is a random integer chosen by the user U
i. Thus, without the knowledge of r
i, the registration center cannot launch offline password guessing attack to recover U
i’s password P
W
i. Second, on the side of a service provider S
j, it also cannot get any information about the user U
i’s password, since those messages transmitted between them do not involve U
i’s password. Therefore, we conclude that our scheme can resist the insider attack.


## 5.3. Impersonation Attack

The impersonation attack against the proposed scheme falls into two classes, i.e., user personation and service provider personation. Below we show that the proposed scheme can withstand these two kinds of impersonation attack.If an adversaryA, which might be a malicious user or a malicious service provider, wants to impersonate user U
i, then it has to correctly compute the challenge value M
3
=
H
1
(
X
i
∥
Y
j
∗
∥
K
i
,
j
∥
T
i
′
). Obviously, for this to be computable, the adversary A has to know the values X
i, Y
j
∗, and K
i
,
j. Moreover, if the adversary itself produces the value X
i
=
x
i
·
g without (if the adversary holds U
i’s password and smart card, then it will not have to impersonate U
i) using U
i’s secret information (i.e., P
W
i and s
i
,
j), then the corresponding value X
i
∗ computed by the service provider is not equal to X
i. As a result, it holds that K
i
,
j
≠
K
j
,
i, which implies that the adversary A cannot pass through the service provider’s authentication since M
3
≠
M
3
′. Thus, the adversary A cannot impersonate the user U
i.On the other hand, if the adversaryA wants to impersonate a service provider S
j, then it also has to pass through a user U
i’s authentication. This requires the adversary A to compute the correct value K
j
,
i
=
y
j
·
X
i
∗. We note that the adversary A cannot get correct X
i
∗
=
X
i
′
-
s
i
,
j
′ without the secret value A
S
I
D
j (s
i
,
j
′
=
H
1
(
A
S
I
D
j
∥
U
I
D
i
)). Consequently, it cannot impersonate the service provider S
j since it cannot produce the correct value M
2.


## 5.4. Offline Password Guessing Attack

To launch the offline password guessing attack, an adversaryA has to hold a value that can be used to check the validity of a candidate password. Below we demonstrate that none of those transmitted messages in the proposed scheme can be used to do this.In the authentication phase of the proposed scheme, note that a userU
i’s password P
W
i is only used to recover the secret value s
i
,
j
′
=
s
i
,
j
⊕
R
P
W
i, and its validity is not verified on the user side. Thus, even if the smart card is lost, those secret values stored in the smart card cannot be used to launch offline password guessing attack. Furthermore, for the first message {
U
I
D
i
,
X
i
,
T
i
,
M
1
}, both the value X
i
′
=
X
i
+
H
2
(
s
i
,
j
′
) and the hash value M
1
=
H
1
(
U
I
D
i
∥
S
I
D
j
∥
X
i
′
∥
T
i
) involve U
i’s password. However, the computation of M
1 does not need any secret value and thus cannot be used to check the validity of a candidate password. Moreover, without the knowledge of the value X
i, the public value X
i
′ also cannot be used to verify the validity of a candidate password. For the second message {
M
2
,
Y
j
′
} and third message {
M
3
}, observe that they do not involve any information about U
i’s password and thus naturally cannot be used to launch the offline password guessing attack. Therefore, the proposed scheme is secure against password guessing attack.


## 5.5. Known-Key Attack

The known-key attack means that the disclosure of a session key will affect the security of other session keys. In our scheme, a session keyS
K
=
H
1
(
K
i
,
j
∥
U
I
D
∥
S
I
D
j
) is derived from a fresh value K
i
,
j
=
(
x
i
y
j
)
·
g, where x
i and y
j are randomly sampled from Z
q
∗. This implies that all session keys are independent from each other. Thus, the disclosure of a session key has no influence on the security of other session keys, and the proposed scheme can withstand known-key attack.


## 5.6. Mutual Authentication and Key Agreement

In the authentication of the proposed scheme, observe that both the userU
i and the service provider S
j have to respond to the partner’s challenge. Specifically, the service provider S
j uses its secret value A
S
I
D
j to produce a correct response value M
2, whose validity would be checked by the user U
i. On the other hand, the user U
i also utilizes the consistent value X
i to generate a response value M
3, whose correctness would be verified by the service provider S
j. We can see that, to complete the authentication procedure, the user U
i and the service provider S
j are required to pass through each other’s authentication. Thus, the proposed scheme achieves mutual authentication.Focusing on the generation of the session key, we can see that both the userU
i and the service provider contribute to the computation of session key, namely, x
i and y
j. This implies that neither one can completely control the generation of the session key, and the session key can be sufficiently random if at least one of the participants is able to produce sufficiently random inputs. Therefore, the proposed scheme enjoys the functionality of key agreement.


## 5.7. Perfect Forward Secrecy

In the setting of the proposed scheme, the perfect forward secrecy requires that after a userU
i’s secret information (i.e., the password and those secret values stored in the smart card) and a service provider S
j’s secret key A
S
I
D
j get exposed, previous session keys established and used between U
i and S
j should remain secure. By basing our scheme on the Diffie-Hellman protocol, it achieves perfect forward secrecy. Concretely, with the knowledge of U
i and S
j’s secret information, an adversary can recover X
i
=
x
i
·
g and Y
j
=
y
j
·
g. However, from the intractability of the computational Diffie-Hellman problem, we know that it is impossible for A to compute K
i
,
j
=
(
x
i
y
j
)
·
g, and thus A cannot further recover the session key S
K
=
H
1
(
K
i
,
j
∥
U
I
D
i
∥
S
I
D
j
). This is why the perfect forward secrecy of the proposed scheme can be achieved.


## 5.8. Two-Factor Authentication

Two-factor authentication is a major security advantage of password and smart card based authentication scheme. That is, once the password or the smart card is revealed (not the both), the scheme should remain secure. Below we show that the proposed scheme is still secure in the above two cases.In the case that an adversaryA knows a user U
i’s password P
W
i but does not have U
i’s smart card, the adversary A cannot compute s
i
,
j
′
=
s
i
,
j
⊕
R
P
W
i, where s
i
,
j is stored in the smart card and R
P
W
i
=
H
1
(
P
W
i
∥
U
I
D
i
∥
r
i
). As a result, it cannot produce a correct value X
i that is consistent with the one computed by the service provider. Thus, the adversary cannot pass through the service provider’s authentication. Namely, the proposed scheme remains secure in this case.In the case that an adversaryA holds a user’s smart card but does not know the user’s password, as analyzed in the offline password guessing attack, no message can be used check the validity of a candidate password. On the other hand, without the knowledge of the correct password, due to the similar reason, the adversary A also cannot pass through the service provider’s authentication. Thus, the proposed scheme is still secure in this case.


## 6. Performance Discussions

In this section, we discuss the performance of the proposed scheme in terms of security property and computation efficiency via comparing it with other related works.In Table2, we present security properties of the listed authentication schemes. We can see that only Li et al.’s [47] scheme cannot resist insider attack since the registration center maintains a table to verify users’ passwords. As analyzed by Truong et al. [16], in Yeh’s [15] scheme, the secret values computed by the user and the service provider are not consistent with each other; thus, this scheme cannot provide the security properties of mutual authentication and session key agreement. In addition, Li et al.’s [47] scheme only uses hash and XOR operations. Thus, after an adversary gets a user/server’s secret keys, it can further recover any previous session keys. Consequently, it cannot provide perfect forward secrecy. Moreover, except for our scheme, other listed schemes [15, 16, 40, 47] all cannot resist offline password guessing attack, which is the most realistic threat aimed at password and smart card based authentication scheme. Even worse, after the user’s smart card is lost, an adversary can correctly recover the corresponding password. This is also why these schemes [15, 16, 40, 47] suffer from user impersonation attack and cannot achieve two-factor authentication. Particularly, in Truong et al.’s [16] scheme, a malicious user can directly obtain any service provider’s secret key. As a result, their scheme is vulnerable to server impersonation attack. In short, our scheme surpasses other listed schemes in terms of security property and provides stronger security guarantee for practical applications.Table 2
Comparisons of security properties with related works.
Security Properties
Li et al. [47]
Pippal et al. [40]
Yeh [15]
Truong et al. [16]
Ours
Insider attack
✘
✔
✔
✔
✔
Replay attack
✔
✔
✔
✔
✔
Known-key attack
✔
✔
✔
✔
✔
Mutual authentication
✔
✔
✘
✔
✔
Session key agreement
✔
✔
✘
✔
✔
Perfect forward secrecy
✘
✔
✔
✔
✔
Two-factor authentication
✘
✘
✘
✘
✔
User impersonation attack
✘
✘
✘
✘
✔
Server impersonation attack
✘
✘
✔
✘
✔
Offline password guessing attack
✘
✘
✘
✘
✔
Note.✔ means that the scheme can provide the corresponding security property, and ✘ indicates that it cannot achieve this.In Table3, we summarize the computation cost of the authentication procedure of these schemes. By running the main operations (i.e., hash operation, XOR operation, modular exponentiation, point multiplication, and point addition) involved in these schemes by calling the library MIRCAL (https://libraries.docs.miracl.com/), we have that T
e
≫
T
p
>
T
m
>
T
h
≫
T
x
o
r. Thus, we can see that Li et al.’s [47] scheme is the most efficient one since it only uses the hash operation and XOR operation, but it cannot provide the required security guarantee. On the other hand, our scheme is more efficient than other schemes [15, 16, 40]; meanwhile, it is also more secure than them. Therefore, from the perspective of both security and efficiency, the proposed authentication is more desirable for practical applications.Table 3
Comparisons of computation efficiency with related works.
Computation party
Li et al. [47]
Pippal et al. [40]
Yeh [15]
Truong et al. [16]
Ours
User side
10
T
h
+
6
T
x
o
r
4
T
h
+
3
T
e
4
T
h
+
2
T
e
5
T
h
+
2
T
p
+
2
T
m
6
T
h
+
2
T
p
+
2
T
m
Server side
18
T
h
+
15
T
x
o
r
3
T
h
+
4
T
e
4
T
h
+
4
T
e
6
T
h
+
2
T
p
+
3
T
m
6
T
h
+
2
T
p
+
2
T
m
Total
28
T
h
+
21
T
x
o
r
7
T
h
+
7
T
e
8
T
h
+
6
T
e
11
T
h
+
4
T
p
+
5
T
m
12
T
h
+
4
T
p
+
4
T
m
Note.  T
h = the running time of one hash operation. T
x
o
r = the running time of one XOR operation. T
p = the running time of one point multiplication over elliptic curves group. T
m = the running time of one point addition over elliptic curves group. T
e = the running time of one modular exponentiation.


## 7. Conclusion

In this paper, we study the design and analysis of password and smart card based authentication scheme for multiserver architecture. Specifically, we pointed out that Truong et al.’s [16] scheme is vulnerable to offline password guessing attack and user/server impersonation attack. We also analyzed why their scheme fails to achieve the intended security goal. Moreover, we proposed a security enhanced and cost-effective authentication scheme to secure communications in the setting of multiple service providers. Security analysis and performance discussion show that our scheme has advantages in terms of security and efficiency and thus is more desirable for practical applications.



---

*Source: 9178941-2018-05-20.xml*