SECURITY ENHANCEMENT FOR A LOW COMPUTATION COST
USER AUTHENTICATION SCHEME
Behnam Sattarzadeh, Mahdi Asadpour and Rasool Jalili
Computer Engineering Department, Sharif University of Technology, Azadi ave, Tehran, Iran.
Keywords:
Forgery attack, Authentication, Smart card.
Abstract:
In 2003, Wu and Chieu proposed a user friendly remote authentication scheme using smart cards. Later, Yang
and Wang pointed out that Wu and Chieu’s scheme is vulnerable to the password guessing and forgery attacks.
Recently, Lee et al. proposed an improved authentication scheme and claimed that their scheme is secure
against forgery attack. However, in this paper, we illustrate that Lee et al.’s scheme is still vulnerable to the
forgery attack. We also propose an enhancement of the scheme to resist such that attack.
1 INTRODUCTION
User authentication is an important security topic for
remote login systems and there are many schemes ex-
isted for this purpose. Among them, the password
scheme is the most convenient and widely adopted
one (Lin and Hwang, 2003).
In 1981, Lamport proposed a remote authentica-
tion scheme for insecure communication (Lamport,
1981). The scheme could resist against replay attack,
however it needed a password table for the user’s au-
thentication and that may cause problem if intruders
can modify the passwords stored in the password ta-
ble (Hwang and Li, 2000).
Sun, 2000, proposed an efficient remote user au-
thentication scheme using smart card (Sun, 2000). In
his scheme, no password table is required to keep in,
but the password of the user is generated by the sys-
tem and the lengthy assigned password does not pro-
vide adequate satisfaction for the user.
Next in 2003, Wu and Chieu proposed a user
friendly remote authentication scheme to improve the
disadvantage of Sun’s scheme (Wu and Chieu, 2003).
Their scheme allows the user to choose or change
his password freely but it requires costly exponen-
tial computation. Since the computation capabilities
of smart cards are limited, time-consuming opera-
tions are not suitable in such environments (Fan et al.,
2005).
Later Yang and Wang in (Yang and Wang, 2004),
independently Min–Shiang Hwang et al. in (Hwang
et al., 2005) and Kuo–Feng Hwang et al. in (Hwang
and Liao, 2005), have pointed out the scheme suffers
from the password guessing and forgery attacks.
Recently Lee et al. proposed an improved low com-
putation cost user authentication scheme, which uses
one-way hash functions instead of exponential oper-
ations to be suitable for smart card applications and
mobile devices (Lee et al., 2005). By the way, they
claimed that their scheme not only is secure against
forgery attack, but also can be used for mobile com-
munications.
In this paper, we show that Lee et al.’s authentica-
tion scheme still suffers from the forgery attack. Then
we present an enhancement of the scheme to resolve
that problem.
The rest of this paper is organized as follows. In the
following section, we review the Lee et al.’s scheme.
In section 3, we illustrate that their scheme is inse-
cure against forgery attack. In section 4, an improved
scheme is proposed to overcome this attack, followed
by its security and computation cost analyses. Finally,
a concluding remark is given in section 6.
2 REVIEW OF LEE ET AL.’S
SCHEME
There are three phases in the scheme: registration,
login and authentication phases. We recall the three
phases in the following (Figure 1).
5
Sattarzadeh B., Asadpour M. and Jalili R. (2006).
SECURITY ENHANCEMENT FOR A LOW COMPUTATION COST USER AUTHENTICATION SCHEME.
In Proceedings of the International Conference on Security and Cryptography, pages 5-8
DOI: 10.5220/0002099900050008
Copyright
c
SciTePress
Figure 1: Login and authentication phases in Lee et al.’s
scheme.
2.1 Registration Phase
The user submits her/his identity ID
i
and a chosen
password P W
i
to the server. Upon receiving the reg-
istration request, the server performs the following
steps:
1. Compute A
i
= h(ID
i
k x), where x is the server’s
private key and h(.) is a one-way hash function.
2. Compute B
i
= h(A
i
k h(P W
i
)).
3. The server issues a smart card with the secure in-
formation {ID
i
, A
i
, B
i
, h(.)}, and delivers it to the
user through a secure channel.
2.2 Login Phase
When the user wants to login, she/he inserts her/his
smart card into the card reader and keys in the iden-
tity ID
i
and password P W
∗
i
, then the smart card per-
forms the following operations:
1. Compute
B
∗
i
= h(A
i
k h(P W
∗
i
)),
C
1
= h(T ⊕ B
i
) and
C
2
= B
∗
i
⊕ A
i
,
where A
i
and B
i
are stored in the smart card and T
is the current date and time.
2. Send the login message m = {ID
i
, C
2
, C
1
, T } to
the server.
2.3 Authentication Phase
After receiving the message m at the time T
0
, the
server first checks the format of ID
i
to make sure
whether it is valid. Then, the server authenticates the
user with the following steps:
1. Verify whether the (T
0
− T ) is in the valid time
interval 4T . If it is not, the system rejects the login
request.
2. Compute A
i
= h(ID
i
k x), and obtain B
∗
i
by
computing B
∗
i
= C
2
⊕ A
i
.
Figure 2: A forgery attack on Lee et al.’s scheme.
3. Compute C
∗
1
= h(T ⊕B
∗
i
). If C
∗
1
matches with C
1
,
the system will accept the login request. Otherwise,
it rejects the login request.
3 FORGERY ATTACK ON LEE
ET AL.’S SCHEME
In this section, we present a forgery attack against Lee
et al.’s scheme, as summarized in Figure 2. Forgery
attack occurs when an attacker pretends to be a legal
user and is successfully authenticated by the server.
Suppose the user identifier is ID
i
. An adversary
can forge a valid login request for ID
i
using the fol-
lowing steps:
1. Intercept one of user’s login messages, say
{ID
i
, C
2
, C
1
, T }.
2. Compute
4T = T ⊕ T
a
and
C
2a
= C
2
⊕ 4T,
where T
a
denotes the login date and time of the
attacker.
3. Send m
a
= {ID
i
, C
2a
, C
1
, T
a
} to the server.
After receiving the message m
a
at time T
0
, the
server verifies ID
i
and T
a
. If they are valid, the server
performs the following steps:
1. Compute A
i
= h(ID
i
k x), and B
∗
ia
as:
B
∗
ia
= C
2a
⊕ A
i
= (C
2
⊕ 4T ) ⊕ A
i
= ((B
∗
i
⊕ A
i
) ⊕ 4T ) ⊕ A
i
= B
∗
i
⊕ 4T ⊕ A
i
⊕ A
i
= B
∗
i
⊕ 4T
SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY
6
Figure 3: Login and authentication phases of improved
scheme.
2. Compute C
∗
1a
as:
C
∗
1a
= h(T
a
⊕ B
∗
ia
)
= h(T
a
⊕ (B
∗
i
⊕ 4T ))
= h(T
a
⊕ (B
∗
i
⊕ (T ⊕ T
a
)))
= h(T ⊕ B
∗
i
⊕ T
a
⊕ T
a
)
= h(T ⊕ B
∗
i
)
As you find, the server can verify the equation
C
∗
1a
= C
1
, then it will accept this forged login re-
quest. By generalizing the above attack, an adversary
can easily pretend to be any legal user and login to
server at any time.
4 THE IMPROVED SCHEME
In this section, we propose an improvement on Lee
et al.’s scheme to resist the attack, stated in previous
section. As a summary, we only change the structure
of message C
2
from B
∗
i
⊕ A
i
to B
∗
i
⊕ h(A
i
k T ).
Now, C
2
depends on the time of the login message T
through one additional one-way hash function. The
proposed scheme is described as follows (Figure 3).
4.1 Registration Phase
The registration phase is the same as that of Lee
et al.’s scheme.
4.2 Login Phase
The user inserts the smart card into the card reader
and keys in identity ID
i
and password P W
∗
i
, then
the smart card performs the following operations:
1. Compute
B
∗
i
= h(A
i
k h(P W
∗
i
)),
C
1
= h(T ⊕ B
i
) and
C
2
= B
∗
i
⊕ h(A
i
k T ),
2. Send the login message m = {ID
i
, C
2
, C
1
, T } to
the server.
4.3 Authentication Phase
Upon receiving the message m at the time T
0
, first,
server checks the format of ID
i
. Then, the server
authenticates the user with the following steps:
1. Verify whether the (T
0
− T ) is in the valid time
interval 4T . If it is not, the system rejects the login
request.
2. Compute
A
i
= h(ID
i
k x), and
B
∗
i
= C
2
⊕ h(A
i
k T ).
3. Compute C
∗
1
= h(T ⊕B
∗
i
). If C
∗
1
matches with C
1
,
the system will accept the login request. Otherwise,
it rejects the login request.
5 ANALYSIS
Since our scheme is a slight modification of the Lee
et al.’s scheme and the security of their scheme have
already been demonstrated in (Lee et al., 2005), so in
the following subsection, we only discuss the differ-
ence between their scheme and ours in terms of secu-
rity. Subsequently the computation cost analysis will
be presented.
5.1 Security Analysis
We here demonstrate that the proposed scheme can
withstand the forgery attack rather than other attacks
described in Lee et al.’s scheme.
Assume that an attacker may impersonate ID
i
by
forging a login request {ID
i
, C
2
, C
1
, T } and sending
it to the server with some modifications. But due to
the below facts that:
1. It is extremely difficult to derive the server’s secret
key x from A
i
= h(ID
i
k x), because the one-way
hash function is computationally difficult to invert.
2. No one can forge a valid parameter C
1
= h(T ⊕B
i
)
or C
2
= B
∗
i
⊕ h(A
i
k T ), because these values are
derived from B
i
, B
∗
i
or A
i
, which are unknown to
everyone except legal user. By the way, the attacker
can only generate them by acquiring the server’s
secret key x, which is infeasible.
3. On the other hand, since timestamp T in C
1
and
C
2
is expired, the attacker must choose another
valid timestamp, say T
a
, and uses it in her/his lo-
gin request. But she/he cannot generate C
1a
=
h(T
a
⊕ B
i
) or C
2a
= B
∗
i
⊕ h(A
i
k T
a
) with
this new timestamp. The reason is the same as the
above statement 2.
SECURITY ENHANCEMENT FOR A LOW COMPUTATION COST USER AUTHENTICATION SCHEME
7
Table 1: Comparison of computational cost.
Phase Lee et al.’s scheme Our scheme
Reg. 3T
H
3T
H
Login 3T
H
+ 2T
XOR
4T
H
+ 2T
XOR
Auth. 2T
H
+ 2T
XOR
3T
H
+ 2T
XOR
Hence, any forged login request will be rejected in
steps 2 and 3 of authentication phase, where server
tries to compute B
∗
i
= C
2
⊕ h(A
i
k T
a
) and C
∗
1
=
h(T
a
⊕ B
∗
i
) and compare C
∗
1
with received C
1
.
5.2 Computation Cost Analysis
We here evaluate the computation cost of the im-
proved scheme and make comparison with the Lee
et al.’s scheme.
All phases of proposed protocol only require lim-
ited number of hash computations, exclusive-or op-
erations, and some other low-cost operations such as
string concatenations. The hash operations can be
performed efficiently and computation cost of other
operations is extremely low, so the efficiency of user
and server are guaranteed in the proposed protocol.
You can compare the computational cost of three
phases of our scheme with Lee et al.’s scheme in Ta-
ble 1, where T
H
means execution time of one-way
hash function h(.), and T
XOR
means execution time
of exclusive-or operation ⊕. You can see that in both
login and authentication phases, our scheme adds just
one more T
H
to their scheme, so it does not incur
much more computational cost to provide protection
against forgery attack. In other words, an additional
hash computation may be the simplest way to prevent
from forgery attack, as our scheme does.
6 CONCLUSION
In this paper, we showed that Lee et al.’s authentica-
tion scheme, which was proposed to solve the forgery
attack of the Wu and Chieu’s scheme, is still vulnera-
ble to the forgery attack. So Lee et al.’s authentication
scheme is insecure.
Finally, we proposed an improved scheme with
very low additional computational cost that not only
can achieve all the advantages of Lee et al.’s scheme
but also can withstand against the forgery attack.
REFERENCES
Lin, C-L. and Hwang, T. (2003). A password authentication
scheme with secure password updating. Computers
and Security, Vol. 22, Issue 1, pp. 68–72.
Lamport, L. (1981). Password authentication with insecure
communication. Communications of ACM, Vol. 24,
pp. 770–772.
Hwang, M-S. and Li, L-H. (2000). A new remote user au-
thentication scheme using smart cards. IEEE Trans-
actions on Consumer Electronics, Vol. 46, Issue 1,
pp. 28–30.
Sun, H-M. (2000). An efficient remote use authentication
scheme using smart cards. IEEE Transactions on Con-
sumer Electronics, Vol. 46, Issue 4, pp. 958–961.
Wu, S-T. and Chieu, B-C. (2003). A user friendly remote
authentication scheme with smart cards. Computers
and Security, Vol. 22, Issue 6, pp. 547–550.
Fan, C-I. and Chan, Y-C. and Zhang, Z-K. (2005). Robust
remote authentication scheme with smart cards. Com-
puters and Security, Vol. 24, Issue 8, pp. 619–628.
Yang, C-C. and Wang, R-C. (2004). Cryptanalysis of a
user friendly remote authentication scheme with smart
cards. Computers and Secu rity, Vol. 23, Issue 5,
pp. 425–427.
Hwang, M-S. and Lo, J-W. and Liu, C-Y. and Lin, S-C.
(2005). Cryptanalysis of a user friendly remote au-
thentication scheme with smart card. Journal of Ap-
plied Sciences, Vol. 5, Issue 1, pp. 99–100.
Hwang, K-F. and Liao, I-E. (2005). Two attacks on a
user friendly remote authentication scheme with smart
cards. ACM SIGOPS Operating Systems Review,
Vol. 39, Issue 2, pp. 94–96.
Lee, C-Y. and Lin, C-H. and Chang, C-C. (2005). An
improved low computation cost user authentication
scheme for mobile communication. Proceedings of
19th International Conference on Advanced Informa-
tion Networking and Applications (AINA’05), IEEE
Computer Society, Vol. 2, pp. 249–252.
SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY
8
