2002
Master’s thesis

A One-Time Password
Authentication Method

1055124

Takasuke TSUJI

AdvisorAkihiro SHIMIZU

January 31, 2003
Course of Information Systems Engineering,
Graduate School of Engineering,
Kochi University of Technology

Abstract
A One-Time Password Authentication Method
Takasuke TSUJI

Applications for transferring money or personal information are increasingly
common on the Internet and in mobile communications. These applications require
user authentication for conﬁrming legal users.

One-time password authentication

methods change the veriﬁer every time by sending the present veriﬁer along with thenext veriﬁer. However, such methods risk attacks because those protocols use two
veriﬁers every session. The SAS (Simple And Secure password authentication protocol)
is a one-time password authentication method that uses a hash function ﬁve times, but
it requires high overhead on low spec machines. In this paper, I propose a new method,SAS-2, which reduces hash function adaptation overhead by 40%. This method has amutual authentication phase which maintains synchronous data communications in its
authentication procedure. Moreover, SAS-2 can be applied to key-free systems.

key words

cryptography, hash function, one-way function, password authentica-

tion, one-time password–i–Contents
Chapter 1

Introduction

1

1.1

Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Existing Studies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Statememt Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5

Study Scope and Contents . . . . . . . . . . . . . . . . . . . . . . . . . .

4

Chapter 2

Secure One-Time Password Authentication Protocols

62.1

Deﬁnitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Lamport’s Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2.1

Registration Phase of Lamport’s Protocol . . . . . . . . . . . . .

7

2.2.2

Authentication Phase of Lamport’s Protocol . . . . . . . . . . .

8

2.2.3

Considerations of Lamport’s protocol. . . . . . . . . . . . . . .

9The Revised SAS Protocol . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.1

Registration Phase of the Revised SAS Protocol . . . . . . . . .

10

2.3.2

Authentication Phase of the Revised SAS Protocol . . . . . . . .

11

2.3.3

Considerations of the Revised SAS protocol . . . . . . . . . . . .

13

2.3

Chapter 3

New Protocol

14

3.1

Deﬁnitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . .

14

3.2

SAS-2 Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2.1

Registration Phase of the SAS-2 Protocol . . . . . . . . . . . . .

15

3.2.2

Authentication Phase of the SAS-2 Protocol . . . . . . . . . . . .

16

SAS-2 Protocol Using a Challenge Response Method . . . . . . . . . . .

19

3.3

– ii –

Contents

3.4

3.3.1

Registration Phase Using a Challenge Response Method . . . . .

19

3.3.2

Authentication Phase Using a Challenge Response Method . . .

20

Protocol Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

Chapter 4
4.1

27

4.1.1

Attacks on One-Time Password Methods . . . . . . . . . . . . .

27

Replay Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Forgery Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Impersonation Attack . . . . . . . . . . . . . . . . . . . . . . . .

29

Denial of Service Attack . . . . . . . . . . . . . . . . . . . . . . .

30

Considerations on the SAS-2 . . . . . . . . . . . . . . . . . . . .

31

Performance Considerations . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.2.1

Calculation Costs . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.2.2

Mutual Authentication . . . . . . . . . . . . . . . . . . . . . . . .

33

Chapter 5
5.1

27

Security Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.2
4.2

Security and Performance Analysis

Algorithm Variations of the SAS-2

34

Combination Variations . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

5.1.1

Useful Data and Necessary Data . . . . . . . . . . . . . . . . . .

34

5.1.2

Combination Type . . . . . . . . . . . . . . . . . . . . . . . . . .

35

5.1.3

Operators for the SAS-2 . . . . . . . . . . . . . . . . . . . . . . .

36

5.2

Preconditions for Secure Variations . . . . . . . . . . . . . . . . . . . . .

38

5.3

Secure Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

5.4

Defective Combinations on the SAS-2 . . . . . . . . . . . . . . . . . . .

41

5.5

Strong Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

5.6

Considerations of the SAS-2 Variations . . . . . . . . . . . . . . . . . . .

44– iii –

Contents

Chapter 66.1

45

An Application for Key-Free Systems . . . . . . . . . . . . . . . . . . . .

45

6.1.1

The SAS-2 Protocol for Key-Free Systems . . . . . . . . . . . . .

45

Registration Phase for Key-Free Systems . . . . . . . . . . . . .

45

Authentication Phase for Key-Free Systems . . . . . . . . . . . .

46

Way to cut Calculation Cost . . . . . . . . . . . . . . . . . . . .

49

Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

6.1.2
6.2

Applications

Chapter 7

Conclusions and Discussions

51

Acknowledgement

52

References

53– iv –

List of Figures
2.1

Registration phase of Lamport’s method . . . . . . . . . . . . . . . . . .

7

2.2

The ith authentication phase of Lamport’s method . . . . . . . . . . . .

8

2.3

Registration phase of the revised SAS . . . . . . . . . . . . . . . . . . .

10

2.4

The ith authentication phase of the revised SAS . . . . . . . . . . . . .

12

3.1

Registration phase of the SAS-2 . . . . . . . . . . . . . . . . . . . . . . .

15

3.2

The ith authentication phase of the SAS-2 . . . . . . . . . . . . . . . . .

18

3.3

Registration phase using a challenge response method . . . . . . . . . .

19

3.4

The ith authentication phase using a challenge response method . . . .

22

3.5

An Lamport type procedure . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.6

An SAS type procedure . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.7

An SAS-2 type procedure . . . . . . . . . . . . . . . . . . . . . . . . . .

25

5.1

Probability of dangerous combinations . . . . . . . . . . . . . . . . . . .

42

5.2

Diﬀerence between defective combinations and strong combinations . . .

43

6.1

Registration phase for key-free systems . . . . . . . . . . . . . . . . . . .

46

6.2

The ith authentication phase for key-free systems . . . . . . . . . . . . .

47

–v–

List of Tables
4.1

Performance evaluations of the SAS-2 and other methods . . . . . . . .

32

5.1

Results of 1bit calculation . . . . . . . . . . . . . . . . . . . . . . . . . .

36

5.2

Evaluation of operator values . . . . . . . . . . . . . . . . . . . . . . . .

37– vi –

Chapter 1

Introduction
1.1

Background

The Internet and mobile communications have been developing, and related
applications for managing money or personal information are increasing in number.
However, there is a risk that such private data can be wiretapped. Therefore, it isnecessary to authenticate users. If a user sends the same password every session, an
attacker can masquerade as the user, because the attacker can get the user’s password
via the Internet. So, the user requires one-time password authentication methods thatchange the veriﬁer every time.
Those techniques are guaranteed secure by the use of a one-way function withwhich it is easy to compute f (x) from x and diﬃcult to compute x such that y = f (x).
Usually hash functions such as MD5 (Message Digest 5) [6], SHA-1 (Secure Hash
Algorithm 1) [7], [8] or RIPEMD-160 (RACE Integrity Primitives Evaluation Message
Digest 160) [9] are employed for this purpose. In the same manner, with a one-way
function it is easy to compute g(s, t) from s and t, but diﬃcult to compute s suchthat y = g(s, t) from y and t.

Usually common-key cryptosystems such as DES(Data Encryption Standard) [1], FEAL (Fast Data Encryption Algorithm) [2], MISTY(Mitsubishi Electric’s Information Security Technology) [3], Rijndael [4], [5] be AES(Advanced Encryption Standard) are employed for this purpose.
Public-key cryptosystems are one-way functions, too. The K1P method [10], [11]–1–

1.2 Existing Studies

and the OKGS method [12] are one-time password authentication methods. Those
methods apply public-key cryptosystems and hash functions.

However, public-key

encryptions have high calculation costs in comparison with hash or common-key
encryptions. In this thesis, I set forth one-time password authentication methods that
apply hash functions or common-key cryptosystems.

1.2

Existing Studies

When a user logs in to the system, the user sends masking data to the server, andthe server certiﬁes the user using those masking data and the stored veriﬁer. Then theuser and the server use a one-time password authentication method apply a one-way
function.
Lamport’s method [19] is a one-time password authentication method, and uses a
one-way function, but this method has two practical diﬃculties: high hash overhead
and the requirement of resetting the veriﬁer.

The CINON (chained one-way data

veriﬁcation method) [20], [21] has solved those problems, but that method has anotherproblem in that the user must memorize a random number. The PERM (Privacy
Enhanced information Reading and writing Management method) [23] eliminates thisproblem by generating and sending a random number from the server. A. Shimizu
et al. have detected a possible security ﬂaw in both CINON and PERM methods: akind of ‘Man in the Middle’ attack that modiﬁes the authentication data by tapping
the communication data in two consecutive sessions. To counter this, M. Sandirigama
et al. propose the SAS (Simple And Secure) password authentication protocol [24],which eliminates the ‘Man in the Middle’ attack and reduces storage, processing, andtransmission overhead. However, the method suﬀers from vulnerability to both replay–2–

1.3 Statememt Problems

and denial of service attacks [25].
C. L. Lin et al. have argued that the OSPA (Optimal Strong-Password Authentication) [25] method and the revised SAS [26] method have solved those security
problems, but C. -M. Chen et al. found a stolen-veriﬁer problem on those methods[28]. This attacker has to steal the veriﬁer from the server, but the attack will be
unsuccessful if the server has strong management.
The authors have performed successful impersonation attacks on the OSPA
method [29]. In this attack, the attacker intercepts the authentication data from theInternet and impersonates the user using the previous veriﬁers. Therefore, the only
secure protocol with a one-time password method for changing veriﬁers inﬁnitely is therevised SAS.

1.3

Statememt Problems

The revised SAS method uses a one-way function ﬁve times. This function has
high overhead, because a one-way function apply hash functions or common-key
cryptosystems. It’s desirable to reduce the number of times this function is used in
the revised SAS method, because authentication methods are now being applied tomobile communications and Internet protocols. The revised SAS and other methods
are useless for low spec machines such as mobile phones.
It is possible that communications on the Internet can be interrupted and become
asynchronous. In that case, an authentication method has to maintain the security ofthe system, but previous authentication methods have coped with those problems.

–3–

1.4 Objective

1.4

Objective

The Internet and mobile communications have been developing, and related
applications for managing money or personal information have to authenticate the user.
However, one-time password authentication methods use one-way functions extensively.
So, I reduce the times a one-way function is used.
Moreover, a synchronous data communication procedure is possible for one-time
password authentication methods. I realized mutual authentication using a one-time
password method.

1.5

Study Scope and Contents

In this thesis, I propose a new method, Simple And Secure password authentication
protocol, ver.2 (SAS-2) [27], applying a one-way function only three times by using
two veriﬁers and another for masking. This reduces hash overhead by about 40%
in comparison with the revised SAS. SAS-2 and other methods generate a random
number, but this operation has high overhead such as the calculation of a one-way
function. In consideration of that problem, I appended a procedure which can use averiﬁer instead of a random number. In addition, a synchronous data communication
procedure is possible for one-time password authentication methods.

The SAS-2

method solved this problem using a mutual authentication protocol.
The SAS-2 method has variations, and I have considered all variations of theSAS-2 and produced safe combinations. Moreover, I examined problems in the SAS-2
protocol and determined the most secure combinations remaining [30]. In addition I
suggest here an application for key-free systems using the SAS-2 method. In addition,
I have written a paper about this thesis, and have submitted it to a learned society.

–4–1.5 Study Scope and Contents

In chapter 2, secure one-time password methods are explained. Those methods
have some problems, which I discuss here. In chapter 3, SAS-2 protocol is explained.
As well, I illustrate the SAS-2 protocol using a challenge response method. In chapter
4, security and performance analysis of SAS-2 is discussed. Security is proven byelimination of existing attacks. Performance evaluations are shown for some costs.
Moreover, I discuss mutual authentication. The SAS-2 has algorithm variations. In thechapter 5, I show how to make such algorithm variations, and lay out preconditions
for secure variations. Moreover, I discuss defective combinations of SAS-2, and show 7
strong variations. In chapter 6, applications apply SAS-2 are presented.

–5–Chapter 2

Secure One-Time Password
Authentication Protocols
Secure one-time password authentication methods are Lamport’s method and therevised SAS method. In this chapter, those two procedures are explained.

2.1

Definitions and Notations

The following deﬁnitions and notations are used throughout in this chapter.

• User is a computer user who employs the protocol for authentication.
• Server is the server that authenticates users.
• ID is the user’s identity.
• x and P are user’s passwords.
• M is the maximum number of hash iterations (ranging from about 500 to 1000).
• i is an integer indicating the number of authentication sessions.
• Ni represents a random number corresponding to the ith authentication.
• F and E are one-way hash functions. For example, F (x) means x is hashed once,
Ein means x is hashed nth using the randome number for the ith veriﬁer.
• ⊕ represents a bitwise XOR operation.

–6–

2.2 Lamport’s Protocol

2.2

Lamport’s Protocol

The mechanism of Lamport’s method consists of two phases: the registration
phase and the authentication phase. The registration process is performed only once,
and the authentication procedure is executed every time the user logs in to the system.
These two phases are described below.

2.2.1

Registration Phase of Lamport’s Protocol

Figure 2.1 shows the initial registration phase of Lamport’s method.

Fig. 2.1 Registration phase of Lamport’s method

1. The user inputs own password and calculates the veriﬁer for the 1st authentication
session. The user inputs the user’s password x and sets M when registering inthe systems; then calculates F M (x) equals F (F (· · · F (x) · · ·)) using the password x.
2. The user sends the registration data to the server for subsequent authentication.
The user sends F M (x) to the server through a secure channel.

–7–2.2 Lamport’s Protocol

3. The server stores the veriﬁer for subsequent authentication.

The server stores

F M (x) for subsequent authentication.

2.2.2

Authentication Phase of Lamport’s Protocol

To log in, the user executes the ith authentication session of Lamport’s protocol.
Then the server stores the veriﬁer F M −i+1 (x). Figure 2.2 shows the ith authentication
phase of the SAS-2 protocol.

Fig. 2.2 The ith authentication phase of Lamport’s method

1. The user inputs own password and calculates authentication data for the ith
authentication session. The user inputs the user’s password P when joining thesystem. Then the user calculates F M −i (x) equals F (F (· · · F (x) · · ·)) using input
data.

–8–

2.3 The Revised SAS Protocol

2. The user sends the authentication data to be authenticated by the server. The user
sends F M −i (x) to the server through a common network such as the Internet.

3. The server authenticates the user with the stored veriﬁer and the transmission
data. The server compares the veriﬁer F M −i+1 (x) and the computed F (F M −i (x)).
Then if they don’t match, the user is rejected and the server refuses the user. Ifthey do match, the user is authenticated and the next process is executed.

4. The server stores the veriﬁer for the next authentication session. The server stores
F M −i (x) in place of F M −i+1 (x) for the next authentication session.

2.2.3

Considerations of Lamport’s protocol

Lamport’s method is a simple procedure, but the user must use a one-way hashfunction many times in every authentication session. This technique is useless because
the method costs a lot of loads and times. Moreover, the user has to register after the
M th authentication session. The registration step is troublesome to the user.
Those problems are solved by changing the veriﬁer every session.

2.3

The Revised SAS Protocol

Lamport’s method has two practical diﬃculties: high hash overhead and therequirement of resetting the veriﬁer. Some one-time password authentication methods
have solved such problems. However, most of those methods have security problems.
The revised SAS is the only surviving one-time password authentication method which
can change veriﬁers without limit.

–9–2.3 The Revised SAS Protocol

The mechanism of the revised SAS method consists of two phases: the registration
phase and the authentication phase. The registration process is performed only once,
and the authentication procedure is executed every time the user logs in to the system.
These two phases are described below.

2.3.1

Registration Phase of the Revised SAS Protocol

Figure 2.3 shows the initial registration phase of the revised SAS protocol.

Fig. 2.3 Registration phase of the revised SAS

1. The user inputs own personal data and calculates the veriﬁer for the 1st authentication session. The user inputs the user’s identity ID and password P whenregistering in the systems; then generates and stores a random number N1 , andcalculates E12 equals E(E(P ⊕ N1 )) using the random number and input data.

– 10 –

2.3 The Revised SAS Protocol

2. The user sends the registration data to the server for subsequent authentication.
The user sends ID and E12 to the server through a secure channel.
3. The server stores the veriﬁer for subsequent authentication. The server stores E12with ID for subsequent authentication.

2.3.2

Authentication Phase of the Revised SAS Protocol

To log in, the user executes the ith authentication session of the revised SAS
protocol. Then the user stores Ni , and the server stores the veriﬁer Ei2 with ID. Figure
2.4 shows the ith authentication phase of the revised SAS protocol.

1. The user inputs own personal data and calculates two data for the ith authentication
session. The user inputs the user’s identity ID and password P when joining thesystem. Then the user calculates Ei1 equals E(P ⊕ Ni ) and Ei2 equals E(Ei1 ) using
input data and the stored Ni . Next the user generates a random number Ni+1 and2
3equals E 2 (P ⊕ Ni+1 ) and Ei+1
equalsstores Ni+1 . Then the user calculates Ei+1
2
2
) using the random number Ni+1 and input data, where Ei+1
is the next
E(Ei+12
3⊕ Ei2 and β equals Ei1 ⊕ Ei+1.
veriﬁer. Next the user computes α equals Ei+1

2. The user sends the authentication data to be authenticated by the server. The user
sends ID, α, and β to the server through a common network such as the Internet.

3. The server authenticates the user with the stored veriﬁer and the transmission
2
from α ⊕ Ei2 with the stored veriﬁer Ei2 and getsdata. The server retrieves Ei+1
3
2
using E(Ei+1). Next the server compares the computed E(Ei1 )Ei1 from β ⊕ Ei+1

– 11 –

2.3 The Revised SAS Protocol

and the stored Ei2 . If they don’t match, the attempt is rejected and the serverrefuses the user. If they do match, the user is authenticated and the next process
is executed.

4. The server stores the veriﬁer for the next authentication session. The server stores
2in place of Ei2 for the next authentication session.
Ei+1

Fig. 2.4 The ith authentication phase of the revised SAS– 12 –

2.3 The Revised SAS Protocol

2.3.3

Considerations of the Revised SAS protocol

The revised SAS method uses a one-way function ﬁve times. This function has
high overhead, because a one-way function apply hash functions or common-key
cryptosystems. It’s desirable to reduce the number of times this function is used in
the revised SAS method, because authentication methods are now being applied tomobile communications and Internet protocols. The revised SAS and other methods
are useless for low spec machine such as mobile phones.
In the revised SAS method, a one-way hash function is used ﬁve times to generate
the authentication data. The functions of each encryption are the following in the ith
authentication session.

1. Ei1 is used to authenticate the user on the ith authentication session.
2. Ei2 is the veriﬁer of the ith authentication session, and this veriﬁer is used to remove
the masking data on this authentication session.
1
is used to authenticate the user on the next authentication session.
3. Ei+1
2
is the veriﬁer of the next authentication session.
4. Ei+1
3
is used for masking the authentication data.
5. Ei+1

When the server authenticates the user on the ith authentication session, the Ei1
is necessary because the server veriﬁes the legal user by the hashed Ei1 . The user has
22, because the Ei+1
is used on the next authentication session. Before
to make the Ei+12
1
2
is calculated, the user must calculate the Ei+1
. Therefore, the Ei+1
is needful,the Ei+1
3
is necessary for masking the authentication data.
too. Moreover, the Ei+1

The Ei2 is maybe needless, because the user can substitute the other data for theEi2 . Moreover, the user can reduce the hash overhead by using epochal new method.

– 13 –

Chapter 3

New Protocol
The SAS-2 method can change veriﬁers every time and without limit. Moreover,SAS-2 applyies its function only three times by using two veriﬁers and another formasking. This reduces hash overhead by about 40% in comparison with the revised
SAS. In addition, SAS-2 has a synchronous data communication procedure.

3.1

Definitions and Notations

The following deﬁnitions and notations are used throughout this thesis.

• User is a computer user who employs the protocol for authentication.
• Server is the server that authenticates users.
• ID is the user’s identity.
• P is the user’s password.
• X, F and H are one-way hash functions. For example, H(x) means x is hashedonce.
• i is an integer indicating the number of authentication sessions.
• Ni represents a random number corresponding to the ith authentication.
• + represents the addition operation.
• ⊕ represents a bitwise XOR operation.

– 14 –

3.2 SAS-2 Protocol

3.2

SAS-2 Protocol

The SAS-2 protocol consists of two phases: the registration phase and the authentication phase. The registration process is performed only once, and the authentication
procedure is executed every time the user logs in to the system. These two phases aredescribed below.

3.2.1

Registration Phase of the SAS-2 Protocol

Figure 3.1 shows the initial registration phase of the SAS-2 protocol.

Fig. 3.1 Registration phase of the SAS-2

1. The user inputs own personal data and calculates the veriﬁer for the 1st authentication session. The user inputs the user’s identity ID and password P whenregistering in the systems; then generates and stores a random number N1 , andcalculates A equals X(ID, P ⊕ N1 ) using the random number and input data.

– 15 –

3.2 SAS-2 Protocol

2. The user sends the registration data to the server for subsequent authentication.
The user sends ID and A to the server through a secure channel.
3. The server stores the veriﬁer for subsequent authentication. The server stores A
with ID for subsequent authentication.

3.2.2

Authentication Phase of the SAS-2 Protocol

To log in, the user executes the ith authentication session of the SAS-2 protocol.
Then the user is storing Ni , and the server stores the veriﬁer A with ID. Figure 3.2
shows the ith authentication phase of the SAS-2 protocol.

1. The user inputs own personal data and calculates two data for the ith authentication session. The user inputs the user’s identity ID and password P when
joining the system.

Then the user calculates A equals X(ID, P ⊕ Ni ) using

input data and the stored Ni . Next the user generates a random number Ni+1
and stores Ni+1 . At that time, the user can use A instead of Ni+1 . Then theuser calculates C = X(ID, P ⊕ Ni+1 ) and F (C) = F (ID, C) using the random
number Ni+1 and input data, where C is the next veriﬁer. Next the user computes
α = C ⊕ (F (C) + A) and β = F (C) ⊕ A. Then the user can substitute othercombinations for α and β.

2. The user sends the authentication data to be authenticated by the server. The user
sends ID, α, and β to the server through a common network such as the Internet.

– 16 –

3.2 SAS-2 Protocol

3. The server authenticates the user with the stored veriﬁer A and the transmission
data. The server retrieves F (C) from β ⊕ A with the stored veriﬁer A and gets
C from α ⊕ (F (C) + A) using F (C). Next the server compares F (C) and thecomputed F (ID, C). If they don’t match, the attempt is rejected and the serverrefuses the user. If they do match, the user is authenticated and the next process
is executed.

4. The server stores the veriﬁer for the next authentication session and calculates thedata for a mutual authentication protocol. The server stores C in place of A for
the next authentication session, and calculates γ equals H(ID, F (C)).

5. The server sends the authentication data to be authenticated by the user. The
server sends γ to the user through a common network.

6. The user authenticates the server with the transmission data and the data which
was used in the user’s authentication.

The user calculates H(ID, F (C)) andcompares H(ID, F (C)) , which is transmission data γ. If they match, the server isauthenticated. If they don’t match, the user tries to log in again.

– 17 –

3.2 SAS-2 Protocol

Fig. 3.2 The ith authentication phase of the SAS-2– 18 –

3.3 SAS-2 Protocol Using a Challenge Response Method

3.3

SAS-2 Protocol Using a Challenge Response
MethodIf user can’t store any data, the system can use the SAS-2 protocol using achallenge response method. In this procedure, the user need not store the random
number, but transmission iterations are increased.

3.3.1

Registration Phase Using a Challenge Response Method

Figure 3.3 shows the initial registration phase of the SAS-2 protocol using achallenge response method.

Fig. 3.3 Registration phase using a challenge response method

1. The user inputs own personal data and calculates the veriﬁer for the 1st authentication session. The user inputs the user’s identity ID and password P whenregistering in the systems; then generates a random number N1 , and calculates A– 19 –

3.3 SAS-2 Protocol Using a Challenge Response Method

equals X(ID, P ⊕ N1 ) using the random number and input data.
2. The user sends the registration data to the server for subsequent authentication.
The user sends ID, A, and N1 to the server through a secure channel.
3. The server stores the veriﬁer for subsequent authentication. The server stores A
and N1 with ID for subsequent authentication.

3.3.2

Authentication

Phase

Using

a

Challenge

Response

MethodTo log in, the user executes the ith authentication session of the SAS-2 protocol
using a challenge response method. Then the user is storing Ni , and the server storesthe veriﬁer A with ID. Figure 3.4 shows the ith authentication phase of the SAS-2
protocol using a challenge response method.

1. The user inputs own personal data and sends the service request to log in. The
user inputs the user’s identity ID and password P when joining the system. Next
the user sends the service request along with ID to the server.

2. The server receives the seed to the user. The server receives the random number
Ni to the user.
3. The user calculates two data for the ith authentication session. The user calculates
A equals X(ID, P ⊕ Ni ) using input data and the stored Ni .

Next the user

generates a random number Ni+1 . At that time, the user can use A instead of
Ni+1 . Then the user calculates C = X(ID, P ⊕ Ni+1 ) and F (C) = F (ID, C)– 20 –

3.3 SAS-2 Protocol Using a Challenge Response Method

using the random number Ni+1 and input data, where C is the next veriﬁer. Next
the user computes α = C ⊕ (F (C) + A) and β = F (C) ⊕ A. Then the user can
substitute other combinations for α and β.

4. The user sends the authentication data to be authenticated by the server. The user
sends α, β, and Ni+1 to the server through a common network such as the Internet.
5. The server authenticates the user with the stored veriﬁer A and the transmission
data. The server retrieves F (C) from β ⊕ A with the stored veriﬁer A and gets
C from α ⊕ (F (C) + A) using F (C). Next the server compares F (C) and thecomputed F (ID, C). If they don’t match, the attempt is rejected and the serverrefuses the user. If they do match, the user is authenticated and the next process
is executed.

6. The server stores the veriﬁer for the next authentication session and calculates thedata for a mutual authentication protocol. The server stores C and Ni+1 in place ofA and Ni for the next authentication session, and calculates γ equals H(ID, F (C)).
7. The server sends the authentication data to be authenticated by the user. The
server sends γ to the user through a common network.

8. The user authenticates the server with the transmission data and the data which
was used in the user’s authentication.

The user calculates H(ID, F (C)) andcompares H(ID, F (C)) , which is transmission data γ. If they match, the server isauthenticated. If they don’t match, the user tries to log in again.

– 21 –

3.3 SAS-2 Protocol Using a Challenge Response Method

Fig. 3.4 The ith authentication phase using a challenge response method– 22 –

3.4 Protocol Considerations

3.4

Protocol Considerations

The SAS-2 protocol eliminates hash overhead by using a radical new method.
The theories of existing one-time password authentication methods are two kinds:
procedures such as Lamport’s method and techniques such as the SAS method. Figure
3.5 shows such a procedure:Fig. 3.5 An Lamport type procedure

1. The user calculates the authentication data F (x) with the user’s identity numberID, the user’s password P , and a random number N .
2. The user send the authentication data F (x) to the server.
3. The server compares the stored veriﬁer F 2 (x) and the calculated F (F (x)).

This process is simple, but it can’t change the veriﬁer adinﬁnitum. This problem issolved by the user sending two veriﬁers at the same time. Figure 3.6 shows an SAS– 23 –

3.4 Protocol Considerations

type procedure which eliminates such problem (U (s) using a masking function using ⊕and +).

Fig. 3.6 An SAS type procedure

1. The user calculates the authentication data A1 , A2 , C 1 , C 2 , C 3 with the user’s identity number ID, the user’s password P , and a random number N .
2. The user calculates the masking data U (s) with the authentication data.
3. The user send the masking data U (s) to the server.
4. The server gets A1 using the stored veriﬁer A2 .
5. The server compares the stored veriﬁer A2 and the calculated F (A1 ).

– 24 –

3.4 Protocol Considerations

This procedure can change the veriﬁer adinﬁnitum, but uses a one-way function a lot
on low spec machines. Figure 3.7 shows an SAS-2 type procedure which solves suchcost as below.

Fig. 3.7 An SAS-2 type procedure

1. The user calculates the authentication data A, C, F (C) with the user’s identity
number ID, the user’s password P , and a random number N .
2. The user calculates the masking data U (s) with the authentication data.
3. The user send the masking data U (s) to the server.
4. The server gets C and F (C) using the stored veriﬁer A.
5. The server compares the retrieved F (C) and the calculated F (ID, C).

– 25 –

3.4 Protocol Considerations

In existing protocols, the user is authenticated when the server compares thestored veriﬁer and the retrieved and hashed data using the authentication data andthe veriﬁer. In the new method proposed us here, the user is authenticated when theserver compares the retrieved data and the retrieved and hashed data using the veriﬁer
and the authentication data. In this way, the number of hash iterations are reduced.
Moreover, the SAS-2 protocol can authenticate the server using the authentication
data. If the system doesn’t need such a function, the SAS-2 can remove it.

– 26 –

Chapter 4

Security and Performance
Analysis
The SAS-2 method eliminates previous attacks, and the SAS-2 method is the mosteﬃcient of the one-time password methods.

4.1

Security Considerations

One-time password authentication methods are vulnerable to certain kinds ofattacks [22] , [25] , [29]. The security of the SAS-2 method was evaluated in this study.

4.1.1

Attacks on One-Time Password Methods

Attacks on one-time password authentication methods are the replay attack, theforgery attack, the impersonation attack, and the denial of service attack.

– 27 –

4.1 Security Considerations

Replay Attack
The replay attack replays communication data and changes the veriﬁer.

Theattacker intercepts authentication data and replaces the next veriﬁer after the authentication session. Then the attacker can impersonate the user or confuse the server.
It assumes that an attacker has intercepted the following two sets continuously
from the Internet.
αi ← F (C) ⊕ F (A) ,βi ← C ⊕ A ,and
αi+1 ← F (E) ⊕ F (C) ,βi+1 ← E ⊕ C .
Then the replay attack succeeds by replacing the authentication data with the following
data.
αi+1 ← αi = F (A) ⊕ F (C) ,← βi = A ⊕ C .
βi+1

In this way, the attacker will be able to impersonate the user from the next authentication session.

Forgery Attack
When an attacker steals communication data from some continuous authentication
sessions, the attacker can change the veriﬁer using assorted authentication data. Thenthe attacker can impersonate the user or replace the veriﬁer in the server.
If a user sends the following data,– 28 –

4.1 Security Considerations

αi ← F (A) ⊕ A ,βi ← C ⊕ A .
β is meaningless, because C isn’t used in α. Then an attacker can intercept those data,
set x to any value, and forge as below.
αi ← αi = F (A) ⊕ A ,βi ← x .
Due to the sending of those data, the ith user’s authentication is successful. Therefore,
the attacker can’t impersonate the user, but the user will be denied from the next
authentication session.

Impersonation Attack
An attacker replaces the intended veriﬁer using a replay attack or a forgery attack.
Then the attacker can impersonate the user from the next authentication session
onward.
For example, a user sends the following data using the veriﬁers A and C (J(x, y)
where J is a masking function using x and y),αi ← Jα (A, C) ,βi ← Jβ (A, C) .
Then an attacker intercepts transmission data up to the ith authentication session.
The attacker then computes the following data where (K(x, y) is a masking function
using x and y).
αi ← Kα (A, y) ,βi ← Kβ (A, y) .

– 29 –

4.1 Security Considerations

Therefore, the attacker will be able to impersonate the user using the next veriﬁer yon the next authentication session. In the same manner, the attacker will be able toimpersonate from the (i + 2)th authentication session.

Denial of Service Attack
The denial of service attack rejects all or speciﬁc users by means of an oﬀensive
action on the server or by means of a falsiﬁcation of user’s veriﬁer. Then the attacker
can inconvenience the user but cannot imitate the user.
When a user sends the following data using the veriﬁers A and C where (J (x, y)
is a masking function using x and y),αi ← Jα (A, C) ,βi ← Jβ (A, C) .
Then an attacker can intercept transmission data until the ith authentication session,and compute the following data. However, the attacker can’t know the next veriﬁer z
where (L(x, y) is a masking function using x and y).
αi ← Lα (A, z) ,βi ← Lβ (A, z) .
Therefore, the attacker can’t impersonate, but the user will be denied from the next
authentication session.

– 30 –

4.1 Security Considerations

4.1.2

Considerations on the SAS-2

When a user tries to be authenticated by the server on the (i + 1)th authentication
session, it is assumed that an attacker has intercepted transmission data before the(i + 1)th authentication sessions. Then the user sends the following authenticationdata.
αi+1 ← E ⊕ (F (E) + C) ,βi+1 ← F (E) ⊕ C ,and ID.
If the attacker takes the oﬀensive, he has to send the following data.
αi+1 ← x ⊕ (F (x) + C) ,
← F (x) ⊕ C ,βi+1

and ID.
However, the attacker can’t make those combinations with the transmission data untilthe (i + 1)th authentication session, because the combination such (F (x) + C) isn’t
used for creating the authentication data. Therefore, the SAS-2 method is secure.

– 31 –

4.2 Performance Considerations

4.2

Performance Considerations

Secure one-time password authentication methods include the Lamport, therevised SAS, and the SAS-2. Those methods’ performance are evaluated here.
Table 4.1 summarizes the performance of the Lamport, the revised SAS, and theSAS-2 in the ith authentication session. M is the maximum number of hash iterations(ranging from about 500 to 1000), h represents the hash value, Vi is the veriﬁer in ith
authentication session, and L(x) represents the data length of x.

Table 4.1 Performance evaluations of the SAS-2 and other methods

4.2.1

Calculation Costs

In Lamport’s method, the user used hash functions extensively and had to register
the veriﬁer before it expired. Those problems were solved with the revised SAS, butthere was a little more overhead. The SAS-2 method uses a hash function only threetimes in comparison with ﬁve times in the revised SAS method. This means that hashoverhead is reduced by about 40%, and the server uses a hash function only once. Then

– 32 –

4.2 Performance Considerations

other performances are under the same or better conditions, data storage, transmission
iterations, and transmission bulk.

4.2.2

Mutual Authentication

A synchronous data communication procedure is possible for one-time password
authentication methods. The SAS-2 method solved this problem by using a mutual
authentication protocol. When carrying out a mutual authentication in the SAS-2
method, the user uses a hash function four times and the server uses it twice.

– 33 –

Chapter 5

Algorithm Variations of theSAS-2
The base type of the SAS-2 is deﬁned by the following two data.
α ← C ⊕ (F (C) + A)
β ← F (C) ⊕ A
The SAS-2 method is capable of other variations without additional overhead.
This section deals with SAS-2 variations.

5.1

Combination Variations

The SAS-2 method has some elements that are useful data, combination types,
and operations. Those factors are considered here.

5.1.1

Useful Data and Necessary Data

In the base type, the user uses A, C, and F (C). The user uses other data ID (orother arbitrary number), P , Ni and Ni+1 in the ith authentication session of the SAS-2
system. As well the user can use F (A) in place of F (C). However, P, Ni , and Ni+1

– 34 –

5.1 Combination Variations

shouldn’t be adopted, because that allows a veriﬁer to be created by an attacker.
In view of these facts, the useful data are ID (or other arbitrary number), A, C,
and F (C) (or F (A)). Even if the user uses those data, the calculation load doesn’t
improve.
It is necessary to adopt A (or F (A)) and C because A (or F (A)) is used to remove
masking data in this authentication session and C is used to authenticate the user in
the next authentication session.

5.1.2

Combination TypeIn the base type, a one sum operation and two XOR operations are used. Consequently, the user can create a combination type as follows.
α ← s ⊕ (t + u)
β ← v⊕w
We can use other types in place of those combinations, for example as follows.
α ← s ⊕ (t + u)
β ← v ⊕ (w + x)
But these are defective in that not only are operations increased but also an attacker
can crack or impersonate easily, because this method makes the same styles and works
from a small amount of data.

– 35 –

5.1 Combination Variations

5.1.3

Operators for the SAS-2

In the base type, a user uses only XOR and addition operations. I considered
the usefulness of other operators: NOT, AND, OR, subtraction, multiplication, anddivision.
Division is useless, because the SAS-2 method uses 0, and 0 has no factors. Table
5.1 shows results of 1 bit calculation using 6 operators, provided that 1 + 1 = 0 and
0 − 1 = 1.

Table 5.1 Results of 1bit calculation

x

y

XOR

AND

OR

additionsubtraction

multiplication

0

0

0

0

0

0

0

0

0

1

1

0

1

1

1

0

1

0

1

0

1

1

1

0

1

1

0

1

1

0

0

1

sum

2

1

3

2

2

1

Table 5.2 shows an evaluation of operator values. Hamming distance represents
the distance of expectations from half. If Hamming distance is 0, the operators areuseful. However, if it isn’t 0, the operators are useless. In calculations with othernumbers of bits, Hamming distances are similar.
If the AND operator is used, the results don’t occur with equal frequency. As aresult the AND creates weak combinations, which is an issue. In the same manner,
the operators OR and multiplication are not feasible. Therefore, a user can use XOR,
addition, and subtraction.

– 36 –

5.1 Combination Variations

Table 5.2 Evaluation of operator values

XOR

AND

OR

additionsubtraction

multiplication

expectation

1
2

1
4

3
4

1
2

1
2

1
4

Hamming distance

0

1
4

1
4

0

0

1
4

The NOT has no problem but it is useless because it increases calculation costs,
and it isn’t strong in the SAS-2 protocol. Its meaning is shown below.
The following relational expression is realized for NOT calculations.
A ⊕ {not(A ⊕ B)} = not{A ⊕ A ⊕ B} = not(B)It is clear that those combinations are useless. In the same way, the following relational
expression is realized.
A ⊕ {not(B + C)} = not{A ⊕ (B + C)}
This means that the following expressions have the same strength.
A ⊕ {not(B + C)}
A ⊕ (B + C)
Therefore, the NOT is useless on the SAS-2 protocol.
In the SAS-2 method, the user can use subtraction in place of addition, but
subtraction complicates the operation. Therefore, it is preferable that the user uses
XOR and addition operators.

– 37 –

5.2 Preconditions for Secure Variations

5.2

Preconditions for Secure Variations

It is assumed that the user sends the authentication data as below.
α ← s ⊕ (t + u)
β ← v⊕w
The following are preconditions for secure variations of the SAS-2.
• One of A or F (A) has to be used in s, v, or w.
The characteristics of the SAS-2 authentication protocol are the following two
operations.

One is taking out C or F (C) with A or F (A), and the other is

conﬁrmation that an expression using F (C) (or C) is regular.

A or F (A) is

necessary when the user retrieves C or F (C) from the communication data,
because only A is stored in the server, and the server can make F (A) from A.

• C or F (C) have to be used in α(β).
If α(β) is made from ID, A, and F (A), an attacker can change β(α) at will.
Therefore, a denial of service attack can succeed. For example, if α and β are as
follows,
α ← F (A) ⊕ (A + ID)
β ← C ⊕ F (A) ,the attacker can change β to anything, and the authentication will be successful,
because there is only one C , and C isn’t related to the authentication.

• It is necessary that v be diﬀerent from w.
If v equals w, then β equals 0, and the expression β is meaningless. Then theserver can’t authenticate the user using only α.

– 38 –

5.2 Preconditions for Secure Variations• The user has to use A, C, or F (C) ( or F (A)) in s, v, and w.
If expressions adopt ID or other arbitrary numbers in a, v or w, an attacker could
remove the masking data.

• In α , t must not be identical with u.
If they are same, t + u equals 2t. Then an attack becomes simple.
Now, let α and β be deﬁned as follows.
α ← F (C) ⊕ (A + A)
β ←C⊕A
Then an attacker can compute 2β equals 2C⊕2A, and calculate α ← F (C)⊕(C+C)
with α ⊕ 2β. Next the attacker sends α with β  ← C ⊕ C (= 0). Therefore, he canimpersonate the user from the next authentication session.

• The user must use F (C) or F (A).
It is clear that an attack is easy if the user creates α and β without using F (C)and F (A) as follows.
α ← A ⊕ (C + ID)
β ←C⊕A
Then an attacker could compute C ⊕ (C + ID) from α ⊕ β, and send it with C ⊕ C,
and thus impersonate the user.

– 39 –

5.3 Secure Variations

5.3

Secure Variations

Attacks were tried on all variations of the SAS-2, and 32 secure variations were
found that met the preconditions. These patterns have the same calculation cost as
the base type. The following combinations are 32 secure variations.

1. α ← C ⊕ (F (C) + A) ,β ← F (C) ⊕ A

2. α ← C ⊕ (F (C) + ID) ,β ← F (C) ⊕ A

3. α ← C ⊕ (A + ID) ,β ← F (C) ⊕ A

4. α ← A ⊕ (F (C) + C) ,β ← F (C) ⊕ A

5. α ← A ⊕ (C + ID) ,β ← F (C) ⊕ A

6. α ← A ⊕ (C + A) ,β ← F (C) ⊕ A

7. α ← F (C) ⊕ (C + ID) ,β ← F (C) ⊕ A

8. α ← F (C) ⊕ (C + F (C)) ,β ← F (C) ⊕ A

9. α ← F (C) ⊕ (C + A) ,β ← F (C) ⊕ A

10. α ← A ⊕ (F (C) + ID) ,β ← F (C) ⊕ C

11. α ← A ⊕ (F (C) + A) ,β ← F (C) ⊕ C

12. α ← A ⊕ (C + ID) ,β ← F (C) ⊕ C

13. α ← A ⊕ (C + A) ,β ← F (C) ⊕ C

14. α ← F (A) ⊕ (C + ID) ,β ← F (A) ⊕ C

15. α ← F (A) ⊕ (C + F (A)) ,β ← F (A) ⊕ C

16. α ← F (A) ⊕ (C + A) ,β ← F (A) ⊕ C

17. α ← C ⊕ (C + ID) ,β ← F (A) ⊕ C

18. α ← C ⊕ (C + F (A)) ,β ← F (A) ⊕ C

19. α ← C ⊕ (C + A) ,β ← F (A) ⊕ C

20. α ← A ⊕ (C + ID) ,β ← F (A) ⊕ C– 40 –

5.4 Defective Combinations on the SAS-2

21. α ← A ⊕ (C + F (A)) ,β ← F (A) ⊕ C

22. α ← A ⊕ (C + A) ,β ← F (A) ⊕ C

23. α ← F (C) ⊕ (A + ID) ,β ←C ⊕A

24. α ← F (C) ⊕ (A + F (C)) ,β ←C ⊕A

25. α ← F (C) ⊕ (A + C) ,β ←C ⊕A

26. α ← F (A) ⊕ (C + ID) ,β ←C ⊕A

27. α ← F (A) ⊕ (C + F (A)) ,β ←C ⊕A

28. α ← F (A) ⊕ (C + A) ,β ←C ⊕A

29. α ← C ⊕ (A + F (C)) ,β ←C ⊕A

30. α ← C ⊕ (C + F (A)) ,β ←C ⊕A

31. α ← A ⊕ (A + F (C)) ,β ←C ⊕A

32. α ← A ⊕ (C + F (A)) ,β ←C ⊕A

5.4

Defective Combinations on the SAS-2

One-time password authentication methods are vulnerable to some kinds ofattacks. The SAS-2 method has another problem.
If the user sends the following combinations, the danger of attack is higher thanwith other strong combinations.
α ← F (C) ⊕ (A + F (C))β ←C⊕A
Then there is a high probability that α is the same as A.
probability of dangerous combinations.

– 41 –

Figure 5.1 shows the5.4 Defective Combinations on the SAS-2

Fig. 5.1 Probability of dangerous combinations

400
The equation of this curve is y1 =×
3
the probability approaches 0 %.

 x
3
. If the hash length is enough long,
4

Figure 5.2 shows the diﬀerence between defective combinations and strong combinations.
 x
1
The equation of the secure combination curve is y2 = 100 ×. The probabili2
ties shown are asymptotic for long bits, but the probabilities of defective combinations
are high for small bits. This result means that defective combinations are weak because
low bits can be discovered easily.
If an attacker computes A from α, the attacker can generate x freely and create
the following data using A (= α).
α ← F (x) ⊕ (A + F (x))β ← x ⊕ A
When the attacker sends those data, the attacker can impersonate the user from thenext authentication session using a substituted x.

– 42 –

5.4 Defective Combinations on the SAS-2

Fig. 5.2 Diﬀerence between defective combinations and strong combinations

Some other combinations are similarly dangerous. For example, the following
combinations are defective.
α ← A ⊕ (C + A)
β ← F (C) ⊕ Aorα ← A ⊕ (F (C) + A)
β ← F (C) ⊕ C
These two combinations use A in both neighborhoods of α. Then an attacker can
extract C or F (C) easily. Therefore, the attacker can impersonate the user.

– 43 –

5.5 Strong Variations

5.5

Strong Variations

The following strong variations of the SAS-2 have no defective combinations. 7
combinations survived as strong variations among the 32 patterns.

1. α ← C ⊕ (F (C) + A) ,β ← F (C) ⊕ A

2. α ← C ⊕ (F (C) + ID) ,β ← F (C) ⊕ A

3. α ← C ⊕ (A + ID) ,β ← F (C) ⊕ A

4. α ← A ⊕ (C + ID) ,β ← F (C) ⊕ A

5. α ← F (C) ⊕ (C + ID) ,β ← F (C) ⊕ A

6. α ← A ⊕ (F (C) + ID) ,β ← F (C) ⊕ C

7. α ← A ⊕ (C + ID) ,β ← F (C) ⊕ C

5.6

Considerations of the SAS-2 Variations

The SAS-2 method has 32 secure variations and 7 strong variations among the
32 patterns. The 32 secure variations have defective combinations. However, thosecombinations are secure enough if the hash length is long bit. Therefore, the system
can choose and use a combination from those 32 patterns.

– 44 –

Chapter 6

Applications
6.1

An Application for Key-Free Systems

Here I introduce key-free systems as one type of application system. These systems
open and shut a key using the SAS-2 method, and this system is practicable not only
in cars but also in cellular phones, PDAs, and ICs. Further more, in this system, one
key device can deal with many open and shut devices. Moreover, it is easy to have aspare key.

6.1.1

The SAS-2 Protocol for Key-Free Systems

Key-free systems consist of two phases: the registration phase and the authentication phase. The registration process is performed only once, and the authentication
procedure is executed every time the user opens or closes a lock such as a door. We
describe these two phases below.

Registration Phase for Key-Free Systems
Figure 6.1 shows the initial registration phase of key-free systems. Then a lock has
its own identity ID, the key’s identity K, and secret key P .

– 45 –

6.1 An Application for Key-Free Systems

Fig. 6.1 Registration phase for key-free systems

1. The lock calculates the veriﬁer for the 1st authentication session. The lock generates
and stores a random number N1 , and calculates A1 = X(ID ⊕ K, P ⊕ N1 ) using
the random number and input data.
2. The lock sends the registration data to the key for the subsequent authentication.
The lock sends ID, K, and A to the key through a secure channel.
3. The key stores the veriﬁer for subsequent authentication. The key stores A with ID
and K for subsequent authentication.

Authentication Phase for Key-Free Systems
When the user wants to open or close the lock, the following ith authentication
protocol is executed on the lock and the key. Then the key has stored A with ID, andthe apparatus has stored ID, K, P , and Ni . Figure 6.2 shows the ith authentication
phase of key-free systems.

– 46 –

6.1 An Application for Key-Free Systems

Fig. 6.2 The ith authentication phase for key-free systems– 47 –

6.1 An Application for Key-Free Systems

1. The key sends the key’s identity to open or close the lock. The key sends the key’s
identity K to the lock.
2. The lock calculates two data for the ith authentication session. The lock calculates
A = X(ID⊕, P ⊕ Ni ) using stored ID, P, K, and Ni . Then the lock generates andstores a random number Ni+1 . At that time the lock can use A instead of Ni+1 .
Next the lock calculates C = X(ID⊕K, P ⊕Ni+1 ) and F (C) = F (ID⊕K, C) using
the random number and stored data. Then the lock computes α = C ⊕ (F (C) + A)
and β = F (C) ⊕ A.
3. The lock sends the authentication data to be authenticated by the key. The locksends ID, α and β to the key through a common network such as the Internet.
4. The key authenticates the lock with the stored veriﬁer A and the transmission data.
The key retrieves F (C) from β ⊕ A with the stored veriﬁer A, and gets C fromα ⊕ (F (C) + A) using F (C). Next the key compares F (C) and the computed
F (ID ⊕ K, C). If they don’t match, the attempt is rejected. If they do match, thenext process is executed.
5. The key stores the veriﬁer for the next authentication session and calculates thedata for a mutual authentication protocol. The key stores C in place of A for the
next authentication session, and calculates γ equals F (ID ⊕ K, F (C)).
6. The key sends the authentication data to be authenticated by the lock. The key sends
γ to the lock through a common network.
7. The lock authenticates the key with the transmission data and the data which wasused on the lock’s authentication. The lock calculates F (ID ⊕ K, F (C)) and compares F (ID ⊕ K, F (C)) which is transmission data γ. If they match, the key isauthenticated and the lock opens or shuts. If they don’t match, the user tries
again.

– 48 –

6.2 Other Applications

6.1.2

Way to cut Calculation Cost

When this system is used on low spec machines such as key devices, it operates
well at low cost. We suggest using XOR operations in place of hash functions.
For example, let a hash function be applied to data E, and let L denote the left
half of E, and R denote the right half of E. Then the hash function F is calculated asfollows.
L ←L⊕RR ← L⊕R
Further let L1 denote the left half of L, and L2 denote the right half of L. In the same
way let R1 and R2 be the half of R. Then the hash function H functions as follows.
L1 ← L1 ⊕ L2
L2 ← L1 ⊕ L2
R1 ← R1 ⊕ R2
R2 ← R1 ⊕ R2
If these operations are used, the quality of security drops, but costs are lowered
considerably, because only XOR operations are managed on the SAS-2 method.

6.2

Other Applications

Lamport’s method is applied to an S/KEY one-time password system in UNIX[16] , [17]. Consequently one-time password authentication methods can be regarded
as practical techniques.
Some authentication systems using hash algorithms exist on the Internet: HMAC

– 49 –

6.2 Other Applications(The Key-Hash Massage Authentication Code) [13], [14] and TLS (Transport Layer
Security) [15]. Lamport’s method maybe unﬁt for Internet protocols because Lamport’s
method has high hash overhead. Besides, an authentication procedure must be lightbecause the systems on the Internet manage many users. The hash iterations in theSAS-2 method are the same in number as in HMAC. Therefore, SAS-2 can be used on
Internet protocols.
The SAS method is applied to billing systems [18] for mobile phones. The SAS-2
method is useful for low spec machines such as the cellular phone because the SAS-2
method is light and such machines cannot bear heavy calculation costs.
The SAS-2 is a simple and limitless authentication method. Therefore, the SAS-2
is suitable for application in low spec machines and in Internet protocols.

– 50 –

Chapter 7

Conclusions and Discussions
In this thesis, I focused on hash overhead, and proposed a new method, SAS-2,
which eliminates 40% overhead of hash function adaptation.

The method has amutual authentication phase which maintains synchronous data communications in anauthentication procedure.
The SAS-2 method has many variations, and those algorithm variations are
examined here. Then 7 strong patterns were identiﬁed. Moreover, the SAS-2 can beapplied to low spec machines and Internet protocols.
One-time password authentications suﬀer from the stolen-veriﬁer problem in which
the attacker steals the user’s veriﬁer from the server and impersonates the user. The
SAS-2 method suﬀers from this problem. Future research will examine new methods
to eliminate such problems. It seems clear that this strong method will be applied toremote control systems.
One-time password authentication methods use two veriﬁers, one to authenticate the user, and the other after the authentication session.

Those two veriﬁers

have to be encrypted by a one-way function. This means that the user must use aone-way function twice. Therefore, a method using a one-way function twice is theminimum one-time password authentication method. I will research such minimum
methods, as well. Such a fast method will be applicable to strong authentication servers.

– 51 –

Acknowledgement
I would like to express my deep gratitude to my thesis advisor, Professor Akihiro
Shimizu, for his enthusiastic guidance, constructive criticism, and superior suggestions
throughout the study. My grateful appreciation is extended to Professor Makoto Iwata
and Professor Masanori Hamamura for their kindness and valuable advice. I would
also like to thank Professor Takahiko Mendori for his instructions.
Grateful thanks are also extended to Professor Lawrence Hunter and Professor
Mikio Kadota for their helpful English teaching towards the writing of this thesis.
Thanks a lot to Mr. Takashi Kamioka and Ms. Yoko Tanaka for their helpful inthe analysis of proposed new methods. I would also like to thank the members of the
Shimizu Laboratory for their precious opinions and support.
I would like to give special thanks to the faculty and staﬀ of the Course ofInformation Systems Engineering during my studies at Kochi University of Technology.
Finally, deep thanks are extended to my father, mother, and brother for theirendless love and emotional support.

– 52 –

References[1] NBS, “Data Encryption Standard,” FIPS-PUB-45, 1977.
[2] A. Shimizu, and S. Miyaguchi, “Fast data encipherment algorithm FEAL,” IEICE
Trans., vol.J70-D, no.7, pp.1413-1423, July 1987. (Japanese)[3] M. Matsui, “New block encryption algorithm MISTY,” Lecture Notes in Computer
Science, FSE 1997, pp.54-68, 1997.
[4] J. Daemen and V. Rijmen, “The block cipher rijndael,” Smart Card Research andApplications, LNCS 1820, J.-J. Quisquater and B. Schneier, Eds., Springer-Verlag,
pp.288-296, 2000.
[5] J. Daemen and V. Rijmen, “Rijndael, the advanced encryption standard,” Dr.
Dobb’s Journal, vol.26, no.3, pp.137-139, March 2001.
[6] R. Rivest, “The MD5 message-digest algorithm,” Internet Request For Comments
1321, April 1992.
[7] National Institute of Standards and Technology, “Secure hash standard,” FIPS
Publication 180-1, April 1995.
[8] W. Stallings, “Secure hash algorithm,” in Cryptography and Network Security:
Principles and Practice Second Edition, pp.193-197, Prentice-Hall, 1999.
[9] H. Dobbertin, A. Bosselaers and B. Preneel, “RIPEMD-160: A strengthened version of RIPEMD,” Fast Software Encryption, Third International Workshop, Lecture Notes in Computer Science 1039, Springer-Verlag, pp.71-82, 1996.
[10] T. Kwon, and J. Song, “Eﬃcient key exchange and authentication protocols protecting weak secrets,” IEICE Trans. Commun., vol.E81-A, no.1, pp.156-163, January 1998.
[11] T. Kwon, M. Kang, S. Jung, and J. Song, “An improvement of the password-based– 53 –

References

authentication protocol (K1P) on Security against replay attacks,” IEICE Trans.
Commun., vol.E82-B, no.7, pp.991-997, July 1999.
[12] J.-Y. Park, D.-I. Lee, H.-H. Lee, and J.-G. Park, “One-time key generation system
for agent data protection,” IEICE Trans. Commun., vol.E85-D, no.3, pp.535-545,
March 2002.
[13] H. Krawczyk, M. Bellare, and R. Coretti, “HMAC: Keyed-hashing for massage
authentication,” Request For Comments 2104, February 1997.
[14] H. Krawczyk, M. Bellare, and R. Coretti, “The key-hash massage authentication
code(HMAC),” Federal Information Processing Standards Publication 198, March
2002.
[15] T.Dierks, and C. Allen, “The TLS protocol version 1.0,” Request For Comments
2246, January 1999.
[16] N. Haller, “The S/KEY(TM) one-time password system,” Proc. Internet Society
Symposium on Network and Distributed System Security, pp.151-158, 1994.
[17] N. Haller, C. Metz, P. Nesser, and M. Straw, “A one-time password system,”
Request For Comments 2289, February 1998.
[18] M. Sandirigama, A. Shimizu, and M.T. Noda, “Simple and secure coin(SAS-Coin)- A practical micropayment system,” IEICE Trans. Commun., vol. E83-A, no.12,
pp.2679-2688, December 2000.
[19] L. Lamport, “Password authentication with insecure communication,” Communications of the ACM, vol.24, no.11, pp.770-772, 1981.
[20] A. Shimizu, “A dynamic password authentication method by one-way function,”
IEICE Trans., vol.J73-D-I, no.7, pp.630-636, July 1990. (Japanese)[21] A. Shimizu, “A dynamic password authentication method by one-way function,”
System and Computers in Japan, vol.22, no.7, 1991.
[22] N. Haller, and R. Atkinson, “On Internet Authentication,” Request For Comments– 54 –

References

1704, October 1994.
[23] A. Shimizu, T. Horioka, and H. Inagaki, “A password authentication method forcontents communication on the internet,” IEICE Trans. Commun., vol.E81-B, no.8,
pp.1666-1673, August 1998.
[24] M. Sandirigama, A. Shimizu, and M.T. Noda, “Simple and secure password authentication protocol (SAS),” IEICE Trans. Commun., vol.E83-B, no.6, pp.1363-1365,
June 2000.
[25] C. Lin, H. Sun, and T. Hwang, “Attacks and solutions on strong-password authentication,” IEICE Trans. Commun., vol.E84-B, no.9, pp.2622-2627, September
2001.
[26] T. Kamioka, and A. Shimizu, “The examination of the security of SAS one-time
password authentication,” IEICE Technical Report, OFS2001-48, no.435, pp.53-58,
2001.
[27] T. Tsuji, T. Kamioka, and A. Shimizu, “Simple and secure password authentication
protocol, ver.2 (SAS-2),” IEICE Technical Report, OIS2002-30, vol.102, no.314,
pp.7-11, September 2002.
[28] C.-M. Chen and W.-C Ku, “Stolen-veriﬁer attack on two new strong-password authentication protocols,” IEICE Transactions on Communications, vol.E85-B, no.11,
pp.2519–2521, November 2002.
[29] T. Tsuji, and A. Shimizu, “An impersonation attack on one-time password authentication protocol OSPA,” IEICE Technical Report, ISEC2002-81, vol.102, no.436,
pp.67-72, November 2002.
[30] T. Tsuji, and A. Shimizu, “Algorithm variations of SAS-2,” IEICE Technical Report, IN2002-149, vol.102, no.498, pp.25-30, December 2002.

– 55 –