FIT2011（第 10 回情報科学技術フォーラム）L-022

One-Time Password Authentication Scheme to Solve Stolen Verifier Problem
Ryoichi Isawa †1

Introduction

Secure authentication schemes between an authentication server and users are required to avoid many risks
on the Internet. There are three authentication schemes:static password authentications like Basic and Digest Access Authentication[1], public-key certificate schemes, andone-time password schemes. In spite of using SSL/TLS, thestatic password authentications are known as being insecure
because majority of people use short and simple passwords.
An adversary can easily guess their passwords, for example
by Library attack. Public-key certificate schemes provide
the necessary security. However, it requires heavy computational costs and is not suitable for low spec mobile devices. In contrast, the computational costs of one-time password schemes are lower than that of public-key certificate
schemes. They are generally based on a symmetric encryption function or a one-way hash function. In addition, since
one-time password schemes generate a diﬀerent password at
every authentication session, they are more secure than thestatic password authentications. Thus, one-time password
schemes is an important area of research.
There are three types of one-time password scheme:
1) based on time-synchronization between the authentication server and the user[2], 2) using a mathematical algorithm where the new one-time password is based on achallenge[3, 4, 5] and 3) using a mathematical algorithm togenerate a new one-time password based on the previous
one-time password. We focus on the type 3 in this study,
because it changes not only the one-time password but also
the secret data stored by the server and the user at every authentication session. We can use our biometric information
as the user’s first secret data without care.
Most schemes[6, 7, 8, 9] are vulnerable to Hybrid Theft
attack. An adversary can steal the secret data from an authentication server or can obtain the communication data in
Hybrid Theft attack. The adversary tries to impersonate alegal user using the stolen data. Since the adversary can obtain the server’s secret data, the Hybrid Theft attack is very
diﬃcult to immunize. 2GR[10] is designed to immunize
the Hybrid Theft attack, but it suﬀers from the Impersonation attack[11]. SAS-X(2)[12] is secure against the Hybrid
Theft attack, but suﬀers from DoS attack.
We classify one-time password schemes into two designs:
1) based on only a one-way hash function and 2) combining
a symmetric encryption function and a one-way hash function. The former is superior in computational cost to thelatter, because one-way hash functions can compute faster

Masakatu Morii ‡than symmetric encryption functions. In addition, the latter uses two functions. If we make the circuit board of a
one-time password scheme, the area resources of the former
become smaller than that of the latter. On the other hand,
we could easily make a secure scheme of the latter. The
schemes[6, 7, 8, 9, 10] are the former, and SAS-X(2)[12] isthe latter.
In this paper, we propose a new one-time password
scheme against the Hybrid Theft attack*1 . The proposed
scheme has three advantages: 1) secure against all the existing attacks, 2) based on only one-way hash function, and 3)
a mutual authentication scheme. Compared with SAS-X(2),the proposed scheme is more secure because of the advantage 1, and can compute faster because of the advantage 2.
SAS-X(2) is a one-way authentication scheme. In contrast,
the proposed scheme is a mutual authentication scheme.

2 Attacks on One-Time Password Scheme
There are ten attacks on one-time password scheme. The
Replay attack, the Forgery attack, the Impersonation attack,and the DoS attack are defined in [7]. The SV attack isdefined in [15]. The Theft attack and the Server Modification attack are defined in [10]. The SV DoS attack isdefined in [14]. In this paper, we call the SV DoS attack
Theft DoS attack because of the same assumption of the SV
DoS attack[14]. We define the Hybrid Theft attack and theServer Impersonation attack in this section.
Replay attack: An adversary obtains the communication

data between the server and the user in the past authentication sessions. In the current authentication session,
she/he replaces all or a specific part of the communication data with the obtained data. If it succeeds, she/heimpersonates a legal user from the next authentication
session.
Forgery attack: An adversary modifies the communication data in the current authentication session. If it succeeds, she/he impersonates a legal user from the next
authentication session.
Impersonation attack: An adversary uses both the Replay
attack and the Forgery attack in order to impersonate alegal user.
Server Impersonation attack: An adversary uses the Impersonation attack in order to impersonate the legal
server of a specific user. One-way authentication
schemes are vulnerable to this attack.
adversary
Denial of Service attack (DoS attack): An*1† Graduate School of Science and Technology, Kobe Uni-

versity‡ Graduate School of Engineering, Kobe University

225( 第 4 分冊 )In 2007, we proposed the scheme against the Hybrid Theft
attack[13]. In this paper, we improve the scheme[13] for the server
and the user to update all secret data at every authentication session.
In [14], Nakayama et al. claimed the scheme[13] suﬀers from the
Theft DoS attack. But it is not true. We omit that proof in this paper.

Copyright © 2011 by Information Processing Society of Japan and
The Instiute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2011（第 10 回情報科学技術フォーラム）uses the Replay attack or the Forgery attack in order
to alter the server’s secret data or the user’s one. If it
succeeds, the server and the user cannot authenticate
each other from the next authentication session.
Stolen Verifier attack (SV attack): An adversary steals
verification data from the server in the current or pastauthentication sessions. Here, the verification data does
not include secret keys used with XOR operation or an
encryption function. She/he generates communication
data using the stolen data and sends them to the server.
If it succeeds, she/he impersonates a legal user from thenext authentication session.
Theft attack: An adversary steals the secret data from theserver in the current or past authentication sessions.
Here, the secret data mean both the verification data
and the secret keys. She/he generates communication
data using the stolen data and sends them to the server.
If it succeeds, she/he impersonates a legal user from thenext authentication session.
Hybrid Theft attack: An adversary uses both the Theft attack and the Impersonation attack in order to impersonate a legal user.
Theft DoS attack: An adversary uses both the Hybrid
Theft attack in order to alter the server’s secret data or
the user’s one. If it succeeds, the server and the user
cannot authenticate each other from the next authentication session.
Server Modification attack: An adversary directly modifies the server’s secret data. Tsuji et al. says that this
attack is more unrealistic than the Theft attack, becausethe ‘writing’ is under high restriction than the ‘reading’in most of systems[10]. We also do not consider this attack.

Table 1 List of symbols used in this paper

U
S
A
ID
PW
h(x)
x̌
x0

X⇒Y: ZX→Y: Z||⊕a user who requests the server to authenticate her/himself
the authentication serveran adversary
a user’s identificationa user’s password
the hash value of the input data x
used when U or S compares certain datawith x̌used when A chooses x0 at random insteadof a valid x, or used when A calculates certain data y0 from x0
X sends Z to Y through a secure channel
X sends Z to Y through an insecure channel
a concatenation
XOR operation

dates the new verifier without any integrity check. Kuo et
al. also indicated that 2GR was vulnerable to the Impersonation attack and proposed an improved scheme immunizing the Hybrid Theft attack[9]. Unfortunately, Kim et al.
pointed out that Kuo et al.’s scheme was still vulnerable tothe attack[17]. Although Kim et al. proposed a new scheme,
they did not prove that their scheme was secure against theTheft attack. In order to immunize the Hybrid Theft attack,Tsuji et al. proposed SAS-X(2)[12]. However, it suﬀers
from the Denial of Service attack (DoS attack)[18]. Thus
all the existing schemes have certain vulnerabilities.

4 Proposed Scheme
3

Weaknesses of Existing Schemes

In 2002, Tsuji et al. proposed SAS-2 (Simple And Secure
password authentication protocol, ver.2), which reduced thetimes of a one-way hash function operated at the server andthe user[6, 7]. SAS-2 was superior in computational costto the revised SAS[16] with the equivalent security level.
In this scheme, Tsuji et al. assumed any adversaries cannot
steal the server’s secret data. Naturally, SAS-2 is vulnerable
to the Hybrid Theft attack.
Chien et al. proposed the ROSI (RObust and SImple authentication protocol), which immunizes the SV attack[8].
Chien et al. assumed the server had the secret key which
an adversary could not steal. Tsuji et al. pointed out thatROSI was vulnerable to the Hybrid Theft attack and proposed 2GR (Two-Gene-Relation password authentication
protocol)[10] in order to immunize the Hybrid Theft attack.
However, Lin et al. found that 2GR was vulnerable to theImpersonation attack[11]. In the Impersonation attack, anadversary tries to impersonate a legal user using the intercepted communication data. There are two reasons why
2GR was vulnerable to the attack: 1) 2GR is a one-way
authentication scheme (user to server) and 2) the server up-

Table 1 shows a list of symbols used in this paper. The
proposed scheme consists of two phases: the registration
phase and the authentication phase. In order to immunize
the Hybrid Theft attack, U does not send a next verifier Ai+1
to S and S does not store it in the ith authentication session.
Since U creates Ai+1 using a random number Qi in the (i −1)th authentication session, U will never send Qi to S and S
does not store it.
4.1 Registration Phase

1. U inputs ID and PW.
2. U⇒S: ID.
3. S generates three random numbers R0 , R−1 , and F0 .
4. S⇒U: R0 , R−1 , F0 .
5. U calculates the following data.

226( 第 4 分冊 )A1 = h(ID||PW||F0 )F1 = h(A1 )Q1 = h(PW||R−1 )
A2 = h(ID||Q1 ||F1 )F2 = h(A2 )Q2 = h(Q1 ||R0 )Copyright © 2011 by Information Processing Society of Japan and
The Instiute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2011（第 10 回情報科学技術フォーラム）V1 = h(A1 ||F2 )6. U stores ID, Q2 , A1 , F1 , A2 , and F2 .
7. U⇒S: F1 , V1 .
8. S stores ID, F1 , and V1 .
4.2

Authentication Phase

Let us illustrate the protocol as follows. U has stored ID,
Qi+1 , Ai , Fi , Ai+1 , and Fi+1 . S has stored ID, Fi , and Vi .
1. U calculates the following data.
Ai+2 = h(ID||Qi+1 ||Fi+1 )Fi+2 = h(Ai+2 )Fi+1 ⊕ Fi
Ai ⊕ Fi+1
Vi+1 = h(Ai+1 ||Fi+2 )h(Fi ||Vi+1 )2. U→S: ID, Fi+1 ⊕ Fi , Ai ⊕ Fi+1 , Vi+1 , h(Fi ||Vi+1 ).
3. S obtains Fi+1 and Ai , and verifies their validity as
follows. S extracts Fi+1 from the received Fi+1 ⊕ Fi
using the stored Fi , and extracts Ai from the received
Ai ⊕ Fi+1 using the obtained Fi+1 . S calculates F̌i =h(Ai ) using the obtained Ai , and compares F̌i with thestored Fi . If they match, S is convinced that the received Fi+1 , Fi , and Ai have not been modified; otherwise S terminates this authentication session.
4. S tries to authenticate U using Vi as follows. S calculates V̌i = h(Ai ||Fi+1 ), and compares V̌i with the stored
Vi . If they match, S authenticates U; otherwise, S detects the Theft DoS attack and terminates this authentication session.
5. S verifies the validity of Vi+1 as follows. S calculatesh(Fi ||Vi+1 ) using the stored Fi and the received Vi+1 .
Then S compares it with the received h(Fi ||Vi+1 ). If they
match, S is convinced that Vi+1 have not been modified;otherwise S terminates this authentication session.
6. S calculates h(Ri ||Fi ) using a randomly selected number
Ri , and stores Fi+1 and Vi+1 .
7. S→U: Ri , h(Ri ||Fi ).
8. U tries to authenticate S as follows. U calculatesh(Ri ||Fi ) using the received Ri and the stored Fi . Then
U compares the calculated h(Ri ||Fi ) with the received
one. If they match, U authenticates S; otherwise, U terminates this authentication session.
9. U calculates Qi+2 = h(Qi+1 ||Ri ) and stores Qi+2 , Ai+2 ,and Fi+2 .
4.3

Security Analysis

This section discusses the security of the proposed
scheme against various attacks. The security analysis on
the Hybrid Theft attack shows in Sect.4.4.
Replay attack: A uses the past communication data in the

Replay attack. If U changes all the communication data
at random at every authentication session, we conclude
the one-time password scheme is secure against the Replay attack. In the proposed scheme, all the communi-

cation data except for ID are Fi+1 ⊕ Fi , Ai ⊕ Fi+1 , Vi+1 ,and h(Fi ||Vi+1 ) in the ith authentication session. U updates Ai to Ai+1 using a random number Qi at every
authentication session. Similarly, U updates Fi to Fi+1
using such Ai . Since Fi+1 ⊕ Fi , Ai ⊕ Fi+1 , and h(Fi ||Vi+1 )include Fi or Ai , they changes at every authentication
session. Likewise, U updates Ai+1 to Ai+2 using a random number Qi+1 so that Vi+1 (= h(Ai+1 ||Fi+2 )) changes
at every authentication session. Therefore the proposed
scheme is secure against from the Replay attack.
Forgery attack: A modifies the communication data in the
ith authentication session. If S verifies whether or not
all the communication data are modified, we conclude
the one-time password scheme is secure against theForgery attack. In the proposed scheme, S verifies
Fi+1 ⊕ Fi and Ai ⊕ Fi+1 at step 3 in the authentication
phase. At step 5, S verifies Vi+1 and h(Fi ||Vi+1 ). Therefore the proposed scheme is secure against the Forgery
attack.
Impersonation attack: In the proposed scheme, Uchanges all the communication data at random atevery authentication session. S also verifies them. We
conclude that the proposed scheme is secure against
the Impersonation attack.
Server Impersonation attack: This security analysis issimilar to that of the Impersonation attack. In the proposed scheme, S changes Ri and h(Ri ||Fi ) at random atevery authentication session. U also verifies them atstep 8 in the authentication phase. Therefore the proposed scheme is secure against the Server Impersonation attack.
DoS attack: A has to modify the communication data inorder to alter S’s secret data or U’s secret data. In the
proposed scheme, both S and U verify all the communication data. Therefore the proposed scheme is secureagainst the DoS attack.
Theft attack: In the proposed scheme, S authenticates U
using the received Ai and Fi+1 . S does not store themand the data from which Ai and Fi+1 are created. Since
A cannot obtain Ai and Fi+1 , the proposed scheme issecure against the Theft attack.
Theft DoS attack: Suppose that A has stolen Fi from S.
00
A modifies Vi+1 and h(Fi ||Vi+1 ) as Vi+1
and h(Fi ||Vi+1)
at random respectively. S updates Vi to the received
0
Vi+1. In the (i + 1)th authentication session, S can detect the Theft DoS attack at step 4 in the authentication
phase. Therefore the proposed scheme is secure against
the Theft DoS attack. However, since S cannot authenticate U, S terminates the authentication session. Here,let us give a variation for S to continue the authentication as follows. Suppose that S and U have the current
secret data and the previous one. When S detects the
Theft DoS attack, S and U use the previous secret data.
Having authenticated each other, they updates own previous secret data to the current secret data. The variation on the proposed scheme can immunize the Theft
DoS attack completely.

227( 第 4 分冊 )Copyright © 2011 by Information Processing Society of Japan and
The Instiute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2011（第 10 回情報科学技術フォーラム）4.4

Security Analysis on Hybrid Theft attack

In one-time password schemes, A can certainly impersonate a legal user only once in the ith authentication session as
follows. A intercepts the communication data and directlysends them to S. Since S receives the valid data, S is convinced that A is the legal user. Similarly, in the Hybrid Theft
attack, A can certainly impersonate a legal user only once.
The question we should consider is whether A can impersonate U in the (i + 1)th authentication session.
In the proposed scheme, S verifies Fi+1 = h(Ai+1 ) at step
3 in the (i + 1)th authentication session. In order to impersonate U, 1) A has to obtain a valid Ai+1 or 2) A has to make0
S store Fi+1
= h(A0i+1 ) in the ith authentication session. Suppose that A steals Fi from S. Then A intercepts the communication data, and extracts Ai and Fi+1 from the intercepted
data using the stolen Fi . Now A has U’s secret data except
for Ai+1 and Qi+1 in the ith authentication session. However,since A cannot obtain Ai+1 (= h(ID||Qi ||Fi )), Qi+1 , and also
Qi , A cannot take the method 1. On the other hand, even0
⊕ Fi andif A replaces Fi+1 ⊕ Fi and Ai ⊕ Fi+1 with Fi+10
Ai ⊕ Fi+1 respectively on the network, S rejects the requests
of A at step 4 in the ith authentication session. Thus, A cannot take the method 2. Therefore the proposed scheme issecure against the Hybrid Theft attack.

5

Conclusion

The existing schemes are vulnerable to some attacks. In
this paper, we proposed a new one-time password scheme
against the Hybrid Theft attack. Moreover, only the proposed scheme is secure against all the existing attacks. In
addition, the proposed scheme can compute faster because
it is based on only a one-way hash function. For the same
reason, when we make the circuit board of the proposed
scheme, the area resources become smaller. We can apply
the proposed scheme to low spec devices and design a secure authentication system.

Reference[1] J. Franks, P. Hallam-Baker, J. Hostetler, S. Lawrence,
P. Leach, A. Luotonen, and L. Stewart, “Http authentication: Basic and digest access authentication,” Internet Request For Comments 2617, June 1999.
[2] N. Sklavos and C. Efstathiou, “Securid authenticator:
On the hardware implementation eﬃciency,” proceedings of 14th IEEE International Conference on Electronics, pp.589–592, Dec. 2007.
[3] M. Peyravian and N. Zunic, “Methods for protecting password transmission,” Computers and Security,
vol.19, no.5, pp.466–469, July 2000.
[4] T.H. Chen and W.B. Lee, “A new method for usinghash functions to solve remote user authentication,”
Computers and Electrical Engineering, vol.34, pp.53–
62, Jan. 2008.
[5] J.Y. Kim, H.K. Choi, and J.A. Copeland, “Further
improved remote user authentication scheme,” IEICE

Trans. Fundamentals, vol.E94-A, no.6, pp.1426–1433,
June 2011.
[6] T. Tsuji and A. Shimizu, “Simple and secure password
authentication protocol, ver.2 (sas-2),” IEICE Technical Report, OIS2002-30, vol.46, no.2, pp.7–11, Sept.
2002.
[7] T. Tsuji and A. Shimizu, “A one-time password authentication method for low spec machines and on internet protocols,” IEICE Trans. Commun., vol.E87-B,
no.6, pp.1594–1600, June 2004.
[8] H.Y. Chien and J.K. Jan, “Robust and simple authentication protocol,” Comput. J., vol.46, no.2, pp.193–
201, Feb. 2003.
[9] W.C. Kuo and Y.C. Lee, “Attack and improvement on
the one-time password authentication protocol against
theft attacks,” Proceedings of the Sixth International
Conference on Machine Learning and Cybernetics,
pp.1918–1922, Aug. 2007.
[10] T. Tsuji and A. Shimizu, “One-time password authentication protocol against theft attacks,” IEICE Trans.
Commun., vol.E87-B, no.3, pp.523–529, March 2004.
[11] C.L. Lin and C.P. Hung, “Impersonation attack on
two-gene-relation password authentication protocol(2gr),” IEICE Trans. Commun., vol.E89-B, no.12,
pp.3425–3427, Dec. 2006.
[12] T. Tsuji, T. Nakahara, and A. Shimizu, “A one-time
password authentication method,” IEICE Technical
Report, OIS2005-83, vol.111, no.1, pp.23–28, Jan.
2006.
[13] S. Nakano, H. Kuwakado, and M. Morii, “Analysis of secure mutual authentication methods against
the stolen-verifier attack,” IEICE Technical Report,
OIS2007-37 (Japanese Edition), vol.107, no.230,
pp.61–64, Sept. 2007.
[14] Y. Nakayama, T. Tsuji, and A. Shimizu, “A one-time
password authentication scheme resistant to dos attacks,” IEICE Technical Report, OIS2008-87, vol.111,
no.1, pp.23–28, Jan. 2009.
[15] C.M. Chen and W.C. Ku, “Stolen-verifier attack on
two new strong-password authentication protocols,”
IEICE Trans. Commun., vol.E85-B, no.11, pp.2519–
1521, Nov. 2002.
[16] T. Kamioka and A. Shimizu, “The examination of the
security of sas one-time password authentication,” IEICE Technical Report, OFS2001-48, pp.53–58, Nov.
2001.
[17] M. Kim, B. Lee, S. Kim, and D. Won, “Weaknesses
and improvements of a one-time password authentication scheme,” International Journal of Future Generation Communication and Networking, vol.2, no.4,
pp.29–38, Dec. 2009.
[18] K. Uo, Y. Shiraishi, and M. Morii, “Evaluation of a
one-time password method to resist stolen-verifier attack,” Proceedings of Computer Security Symposium2006 (Japanese Edition), CD-ROM, pp. 8A-4, 6 pages,
Oct. 2006.

228( 第 4 分冊 )Copyright © 2011 by Information Processing Society of Japan and
The Instiute of Electronics, Information and Communication Engineers
All rights reserved.