# Cryptanalysis of Three Password-Based Remote User Authentication Schemes with Non-Tamper-Resistant Smart Card

Authors: Chenyu Wang; Guoai Xu
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Remote user authentication is the first step to guarantee the security of online services. Online services grow rapidly and numerous remote user authentication schemes were proposed with high capability and efficiency. Recently, there are three new improved remote user authentication schemes which claim to be resistant to various attacks. Unfortunately, according to our analysis, these schemes all fail to achieve some critical security goals. This paper demonstrates that they all suffer from offline dictionary attack or fail to achieve forward secrecy and user anonymity. It is worth mentioning that we divide offline dictionary attacks into two categories: (1) the ones using the verification from smart cards and (2) the ones using the verification from the open channel. The second is more complicated and intractable than the first type. Such distinction benefits the exploration of better design principles. We also discuss some practical solutions to the two kinds of attacks, respectively. Furthermore, we proposed a reference model to deal with the first kind of attack and proved its effectiveness by taking one of our cryptanalysis schemes as an example.


---

## Body

## 1. Introduction

These days an increasing number of online services (E-Health, E-Banking, and E-Shopping) have been provided for people’s daily life with the rapid development of the Internet. Moreover, modern terminal equipment, like smartphones, smartwatches, and Google’s Project Glass glasses, has become widespread. The growth of online services and terminal equipment makes the authentication process more important and difficult. Remote authentication is an essential part to guarantee both the claimed user and server are legitimate. In other words, authentication ensures that only the legitimate users can access the resources on the target server. And authentication protocols have been widely used for various fields, including cloud computing, E-Health, and wireless sensor [1–4].In 1981, Lamport [5] designed the first authentication scheme based on password, while this scheme was pointed out as being insecure shortly: (1) the server having to maintain a password table and (2) high hash overhead. Therefore, many advanced schemes [6–8] were proposed with a lower overhead for the hash function to improve the computing performance of Lamport’s scheme, while most of them still require a verification table.To tackle this problem, Hwang et al. [9] developed a noninteractive password authentication scheme which discards the verification table but using smart card instead in 1990. The main drawback lies in the hardship of changing password. Because the password is related to the ID, for the sake of security, the ID has to be changed once the password is changed. However, it is not easy to change the ID. In 1991, Chang and Wu [10] also developed a scheme using smart card for storing sensitive information to help the authentication. Since then, smart cards have been applied to user authentication schemes widely, and some notable ones include [11–14]. Furthermore, these years many schemes used biometrics characteristic as an additional factor to provide the authentication [15–17].From 1990 to 2004, numerous remote user authentication schemes with smart card were designed, while almost all were proved to be flawed. However after these years of research, remote user authentication has made great progress: on the one hand, the problem of maintaining the verification table was almost settled, and smart cards got widely used; on the other hand, the authentication schemes became more sophisticated to withstand the increasing new attacks or to meet more requirements (setting and changing the password freely, no verification table, etc.). Furthermore, ID protection was regarded as an important attribute to be noticed by researchers around 2000. In fact, in this period, most of the proposed schemes used a static user identity in the open communication channel, thus resulting in the ID theft problem. To deal with this problem, in 2004, Das et al. [18] designed a dynamic ID-based scheme, which became a landmark in the history of remote user authentication. The dynamic ID technique is able to conceal the real ID by using random numbers to generate a pseudo identity. As a good and new method to deal with ID theft, Das’s scheme draws much attention. However, from then on, many authors raised concerns [19, 20] about Das’s scheme and devised a variety of improved schemes. In 2005, Chien and Chen [21] criticized Das’s scheme of its incapability of preserving user anonymity and proposed an enhanced one. In 2009, Wang et al. [22] also revealed that Das’s scheme was completely insecure for its incapability of password-dependent goal, mutual authentication, and resistance of impersonation attack. In this period, most of the schemes (before or around 2004) assumed the smart cards are tamper resistant; that is, the parameters in the smart cards are unaccessible to adversaries.Later, however, researchers demonstrated that the message stored in smart card can be easily extracted by reverse engineering techniques [23, 24] and power analysis [25, 26], which becomes another important landmark in remote user authentication area. Since then, most of schemes prefer to use non-tamper-resistant smart cards.In 2010, Li et al. [27] proposed a password-authenticated key agreement scheme, while Tasi et al. [28] demonstrated it cannot be resistant to desynchronization attack and thus developed a new one. Unfortunately, in 2015 Wang et al. [29] showed Tsai’s scheme suffers from smart card loss attack. Song [30] in 2010 revealed that the scheme [31] of Xu et al.’s is vulnerable to impersonation attack and thus designed a new one using symmetric key cryptosystem. Sandeep et al. [32], in the same year, also proved that Xu et al.’s scheme is not resistant to impersonation attack and offline dictionary attack and then devised a new enhanced one. Shortly after, however, Chen et al. [33] found that both the schemes of Song and Stood et al. are not secure: the scheme of Song cannot be resistant to smart card loss attack and offline dictionary attack; the scheme of Stood et al. fails to achieve mutual authentication. So Chen et al. designed an enhanced remote user authentication scheme. While this scheme was also proved by Kumari and Khan [34] it suffered from insider attack and impersonation attack. Li et al. [35], in 2013, reanalyzed Chen et al.’s scheme and then indicated that it cannot promise forward secrecy.Till recent years, remote user authentication schemes display several distinctive features:(1)
Some attacks, including parallel session attacks, have stolen verifier attacks, and replay attacks are rarely mentioned, which means most schemes can resist these attacks.(2)
Smart card loss attack and offline dictionary attack draw more and more attentions:
(i)
Ma et al. [36] showed that the public key algorithm is required to resist offline dictionary attack (also called offline-password guessing attack). It is worth mentioning that we will show the following in later section: here the method is specifically applied to the offline dictionary attack using the verification from the open channel, while it is not applied to the offline dictionary attack using the verification from the smart card;(ii)
Wang et al. [29] demonstrated that there is an unavoidable trade-off between changing password locally and resisting smart card loss attack (including offline-password attack). As shown in [37], here the offline dictionary attack should be specific to the offline dictionary attack using the verification from the smart card, but not to offline dictionary attack using the verification from the open channel;(iii)
in [38], Wang gave an analysis to offline dictionary attack and proposed several security models.(3)
User anonymity and forward secrecy attract many discussions: Ma et al. [36] proved that public key algorithm is necessary to protect user anonymity; to achieve forward secrecy, the server side needs to conduct two exponentiation operations at least [36].Although numerous user remote schemes were proposed, people are still confused about how to assess which scheme is better or whether a scheme is secure enough. Thus Madhusudhan and Mittal [39] tried to answer the question by giving nine security requirements and ten desirable attributes of a sound smart card-based authentication scheme, which we think is another landmark in the history of remote user authentication. Those security requirements and desirable attributes are shown in Tables 1 and 2. They have become an important criterion of an ideal remote authentication scheme. Most of remote user authentication schemes [4, 40–42] are designed and evaluated according to them, while none of the schemes could actually satisfy them simultaneously. Therefore, many researchers begin to pay more attention to exploring the design principles and assessment criteria of authentication schemes. The most recent one is from Wang et al. [29, 37]. These two papers explored the relationship between the security requirements and desirable attributes and gave two significant tables to show the relationships. However, how to assess an authentication scheme is still an unsettled issue. Furthermore, in [11], D. Wang and P. Wang for the first time integrated “honeywords” and “fuzzy-verifiers” to settle a long-standing security-usability conflict (i.e., the trade-off between changing password locally and resisting smart card loss attack). It is a remarkable breakthrough in this area, and we will give more details in later section.Table 1
Security requirements.
1
Denial of Service (DoS) attack
2
Forgery attack (impersonation attack)
3
Replay attack
4
Stolen verifier attack
5
Parallel session attack
6
Password guessing attack
7
Smart card loss attack
8
Reflection attack
9
Insider attackTable 2
Desirable attributes.
1
No password reveal
2
Password dependent
3
No verification table
4
Freely chosen password by the users
5
Forward secrecy
6
User anonymity
7
Mutual authentication
8
Efficiency for wrong password login
9
Smart-card revocation
10
Session key agreementThroughout the history of two-factor authentication, it is easy to find the following: although there have been dozens of works endeavored to construct practical remote user authentication schemes, no one has succeeded in withstanding various attacks or satisfying various desirable attributes. The main reason is the chaos of some essential issue, for example, the sound assessment criterion, the reasonable classification, and definition of attacks in smart card-based scheme. Our work tries to give some inspiration on exploring better proposals.


### 1.1. Our Contributions

Most recently, Yeh [43] proved Chang et al.’s scheme [20] is vulnerable to replay attack, user impersonation attack, and so on and therefore proposed a new authentication scheme with user untraceability. In 2016, Kang et al. [44] showed that Djellali et al.’s scheme [45] suffers from offline dictionary attack, impersonation attack, and replay attack and then developed an enhanced scheme that achieves user anonymity with a Markov chain; and Kaul et al. [46] also designed an improved authentication scheme based on Kumari et al.’s scheme [34]. These schemes all claim to be resistant to various attacks, such as offline dictionary attack and impersonation attack. Unfortunately, according to our analysis, they fail to withstand those attacks as claimed. We summarize our contributions as follows:(1)
This paper demonstrates that the three schemes all suffer from offline dictionary attack, man-in-the-middle attack, and impersonation attack, as well as failing to preserve user anonymity or forward secrecy.(2)
Furthermore, we for the first time divide offline dictionary attacks into two categories: (1) the ones using the verification from smart cards and (2) the ones using the verification from the open channel. The second is more complicated and intractable than the first type. We show that treating them with no difference arouses confusion and misleads the related research. Such distinction which benefits the exploration of better design principles is requisite and significant.(3)
Remarkably, we explore the solution to such two kinds of attacks and propose a reference model to settle the offline dictionary attack using the verification from the open channel and then use Yeh’s scheme to check the effectiveness of our reference model; the result shows that our reference model actually works.The remainder of this paper is organized as follows: in Section2, the system architecture and the capacities of adversary are explained. In Section 3, we give a cryptanalysis of Yeh’s scheme. We review Kang et al.’s scheme in Section 4 and Kaul et al.’s scheme in Section 5. Section 6 analyzes the two kinds of offline-password guessing attacks. And Section 7 gives a conclusion.


## 1.1. Our Contributions

Most recently, Yeh [43] proved Chang et al.’s scheme [20] is vulnerable to replay attack, user impersonation attack, and so on and therefore proposed a new authentication scheme with user untraceability. In 2016, Kang et al. [44] showed that Djellali et al.’s scheme [45] suffers from offline dictionary attack, impersonation attack, and replay attack and then developed an enhanced scheme that achieves user anonymity with a Markov chain; and Kaul et al. [46] also designed an improved authentication scheme based on Kumari et al.’s scheme [34]. These schemes all claim to be resistant to various attacks, such as offline dictionary attack and impersonation attack. Unfortunately, according to our analysis, they fail to withstand those attacks as claimed. We summarize our contributions as follows:(1)
This paper demonstrates that the three schemes all suffer from offline dictionary attack, man-in-the-middle attack, and impersonation attack, as well as failing to preserve user anonymity or forward secrecy.(2)
Furthermore, we for the first time divide offline dictionary attacks into two categories: (1) the ones using the verification from smart cards and (2) the ones using the verification from the open channel. The second is more complicated and intractable than the first type. We show that treating them with no difference arouses confusion and misleads the related research. Such distinction which benefits the exploration of better design principles is requisite and significant.(3)
Remarkably, we explore the solution to such two kinds of attacks and propose a reference model to settle the offline dictionary attack using the verification from the open channel and then use Yeh’s scheme to check the effectiveness of our reference model; the result shows that our reference model actually works.The remainder of this paper is organized as follows: in Section2, the system architecture and the capacities of adversary are explained. In Section 3, we give a cryptanalysis of Yeh’s scheme. We review Kang et al.’s scheme in Section 4 and Kaul et al.’s scheme in Section 5. Section 6 analyzes the two kinds of offline-password guessing attacks. And Section 7 gives a conclusion.


## 2. System Architecture and the Capacities of Adversary

In this section, we first list the notations used in the three schemes and then briefly introduce the system architecture and the capacities of the adversary in the schemes.


### 2.1. Notations and Abbreviations

The notations in the three schemes are shown in Notations and Abbreviations at the end of the paper.


### 2.2. System Architecture

Like many other smart card-based authentication methods, the three schemes involve a set of users and a single server. Users access the resources by mutual authentication with server. The authentication usually includes four basic phases: registration, login, authentication, and password change. Firstly, a user submits personal information to the server to register. Then the server issues the user a smart card with security parameters. The registration phase is only performed once unless the user reregisters for special reasons. After that, in the login phase, the user will send the access request. Then the server and the user authenticate each other in verification phase to finish the authentication. The phases of login and verification usually will be carried out many times. A sound two-factor authentication schemes should ensure that only the user who owns the smart card and submits the corresponding password can access the server successfully. As a realistic problem, the password change phase attracts more and more attention these years where the user can change his/her password locally or remotely.


### 2.3. The Capacities of Adversary

In the cryptanalysis of the two-factor authentication schemes, the adversaryA is also supposed to have the following capacities [29, 47–49]:(1)
A can fully control the open communication channel; that is, A can modify, intercept, delete, and resend the eavesdropped messages over an open channel.(2)
A can enumerate all the items in Dpw∗Did in polynomial time, where Dpw and Did denote the password space and the identity space, respectively.(3)
A can acquire the password of a legitimate user by a malicious card reader or get the parameters in smart card but cannot achieve both.(4)
When evaluating forward secrecy,A can get the server’s secret key.


## 2.1. Notations and Abbreviations

The notations in the three schemes are shown in Notations and Abbreviations at the end of the paper.


## 2.2. System Architecture

Like many other smart card-based authentication methods, the three schemes involve a set of users and a single server. Users access the resources by mutual authentication with server. The authentication usually includes four basic phases: registration, login, authentication, and password change. Firstly, a user submits personal information to the server to register. Then the server issues the user a smart card with security parameters. The registration phase is only performed once unless the user reregisters for special reasons. After that, in the login phase, the user will send the access request. Then the server and the user authenticate each other in verification phase to finish the authentication. The phases of login and verification usually will be carried out many times. A sound two-factor authentication schemes should ensure that only the user who owns the smart card and submits the corresponding password can access the server successfully. As a realistic problem, the password change phase attracts more and more attention these years where the user can change his/her password locally or remotely.


## 2.3. The Capacities of Adversary

In the cryptanalysis of the two-factor authentication schemes, the adversaryA is also supposed to have the following capacities [29, 47–49]:(1)
A can fully control the open communication channel; that is, A can modify, intercept, delete, and resend the eavesdropped messages over an open channel.(2)
A can enumerate all the items in Dpw∗Did in polynomial time, where Dpw and Did denote the password space and the identity space, respectively.(3)
A can acquire the password of a legitimate user by a malicious card reader or get the parameters in smart card but cannot achieve both.(4)
When evaluating forward secrecy,A can get the server’s secret key.


## 3. Cryptanalysis of Yeh’s Scheme

### 3.1. Review of Yeh’s Scheme

This section gives a brief review of Yeh’s [43] scheme with user untraceability (shown in Figure 1).Figure 1
The scheme of Yeh et al.


#### 3.1.1. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and two random numbers r1, r2 and then sends {IDi,PWi,r1,r2} to S via a secure channel.Step 2 (S⇒Ui).
S computes Mi=h(y∥r2)⊕h(PWi∥r1) and Ni=h(IDi∥x)⊕h(PWi∥r1) and then sends Ui a smart card with security parameters {Mi,Ni,r1,h(·)} via a secure channel and stores h(h(y∥r2)) in a table.


#### 3.1.2. Login Phase and Authentication Phase

Step 1 (Ui→S).
U
i inputs IDi′, PWi′. The smart card generates a random number r3, computes A = Mi⊕h(PWi′∥r1) = h(y∥r2), D=r3⊕h(A), B = Ni⊕h(PWi′∥r1) = h(IDi′∥x), Ni′ = Ni⊕h(h(A∥r3)), CIDi = IDi′⊕h(Ni∥h(A)∥r3), and C = h(Ni∥h(A)∥B∥r3), and then sends {D,CIDi,Ni′,C} to S.Step 2 (S→Ui).
S traverses the h(h(y∥r2))∗ in table T, computes r3∗ = D⊕h(h(y∥r2))∗, Ni∗ = Ni′⊕h(h(h(y∥r2))∗∥r3∗), IDi∗=CIDi⊕h(Ni∗∥h(h(y∥r2))∗∥r3), B∗=h(IDi∗∥x), and C∗=h(Ni∗∥h(h(y∥r2))∗∥B∗∥r3∗), and then checks C∗=?C. If none of the value h(h(y∥r2))∗ satisfies the equation, end the session. Otherwise, S examines the freshness of r3 and whether {D,CIDi,Ni′,C} has been received before. If one of the conditions is invalid, terminate the session. Otherwise, S generates a random number r4, computes a=h(B∗∥h(h(y∥r2))∗∥r4), and sends {a,r4} to Ui.Step 3.
The smart card firstly checksr4, then computes a′=h(B∥h(A)∥r4), and checks whether a′ equals a. If true, Ui authenticates S.


#### 3.1.3. Password Change Phase

IfUi wants to change the password, he/she inserts the smart card to the card reader and inputs IDi, PWi, and a new password PWinew. Then the smart card computes Minew=Mi⊕h(PWi∥r1)⊕h(PWinew∥r1) and Ninew=Ni⊕h(PWi∥r1)⊕h(PWinew∥r1) and then replaces Mi and Ni with Minew and Ninew.


### 3.2. Cryptanalysis of Yeh’s Schemes

In this section we show that Yeh’s scheme cannot resist various attacks, such as password guessing attack, impersonation attack, and desynchronization attack.


#### 3.2.1. Offline Dictionary Attack via Verification Value in Channel

Supposing the adversaryA stole Ui’s smart card and then got security parameters Ni, r1, and Mi from the smart card, A also has {Di,CIDi,Ni′,C} through eavesdropping the open channel between Ui and S; then A can perform the attack by the following steps:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
ComputeA∗=Mi⊕h(PWi∗∥r1) = h(y∥r2)∗; Mi and r1 are extracted from the smart card.(3)
Computer3∗=D⊕h(A∗); D is eavesdropped from the open channel.(4)
ComputeB∗=Ni⊕h(PWi∗∥r1); Ni and r1 are extracted from the smart card.(5)
ComputeC∗=h(Ni∥h(A∗)∥B∗∥r3∗); Ni is extracted from the smart card.(6)
Verify the correctness ofPWi∗ by checking if C∗=?C, C is from the open channel.(7)
Repeat Steps (1), (2), (3), (4), (5), and (6) until the correct value ofPWi∗ is found.The time complexity of the above attack isO(|Dpw|∗(3TH+3TR)). TH is the running time for hash computation. TR is the running time for exclusive-or operation. |Dpw| denotes the number of passwords in Dpw, and |Dpw| is very limited in practice [49, 50]; usually |Dpw|≤106; so the above attack is quite efficient.Remark 1.
The offline dictionary attack here uses the verification from the open channel. The inherent reason for this attack is that (1) the adversary can find a verification to check whether the guessing value is correct; (2) the password is the only unknown value to the adversary; that is, the adversary can get other parameters consisting of the verification, except the password or the identity. To such attack, the lightweight public key algorithm is the necessary condition, as explained in [36].


#### 3.2.2. User Anonymity

Once the adversaryA gets the password through “offline dictionary attack,” he can get the user’s ID by the following steps:(1)
ComputeA=Mi⊕h(PWi∗∥r1)=h(y∥r2); Mi and r1 are from the smart card.(2)
Computer3=D⊕h(A); D is from open channel.(3)
ComputeIDi∗=CIDi⊕h(Ni∥h(A)∥r3); Ni is from smart card; CIDi is from open channel.In computingIDi, what the server knows more than the adversary is h(h(y∥r2)), while, after getting the PWi, the adversary can get h(h(y∥r2)) by Mi⊕h(PWi∗∥r1), so in fact the adversary A has the same capacity as the server; thus A can get IDi according to the way the server does.


#### 3.2.3. User Impersonation Attack

With thePWi∗ and the IDi∗, the adversary A can impersonate Ui as follows:(1)
ComputeA=Mi⊕h(PWi∗∥r1)=h(y∥r2); Mi and r1 are from the smart card.(2)
Generate a random numberr3.(3)
ComputeDa=r3⊕h(A).(4)
ComputeB=Ni⊕h(PWi∗∥r1)=h(IDi∗∥x).(5)
ComputeNa′=Ni⊕h(h(A∥r3)); Ni is extracted from the smart card.(6)
ComputeCIDa=IDi∗⊕h(Ni∥h(A)∥r3).(7)
ComputeCa=h(Ni∥h(A)∥B∥r3).(8)
Interrupt{D,CIDi,Ni′,C}; send {Da,CIDa,Na′, Ca} to S to impersonate Ui.As for the serverS, it computes r3∗=Da⊕h(h(y∥r2))∗, Ni∗=Na′⊕h(h(h(y∥r2))∗∥r3∗), IDi′=CIDa⊕h(Ni∗∥h(h(y∥r2))∗∥r3∗), B∗=h(IDi∗∥x), and C∗=h(Ni∗∥h(h(y∥r2))∗∥B∗∥r3∗) and then checks (1) C∗=?Ca; (2) the freshness of r3; and (3) whether {Da,CIDa,Na′,Ca} has ever been received before. All of them are satisfied, so A is authenticated by S successfully.WithPWi, IDi, and smart card, the adversary A has the same capacity as the legitimate user; that is, A can impersonate the user to the server successfully. The original reason for this attack is the offline dictionary attack.


#### 3.2.4. Server Impersonation Attack

With thePWi∗, A can impersonate S as follows:(1)
Computeh(y∥r2)=Mi⊕h(PWi∗∥r1); Mi and r1 are extracted the from smart card.(2)
ComputeB∗=Ni⊕h(PWi∗∥r1)=h(IDi∗∥x); Ni is extracted from the smart card.(3)
Generate a random numberr4; compute aa=h(B∗∥h(h(y∥r2))∥r4a).(4)
Interrupt{a,r4}, and send {aa,r4a} to the user Ui to impersonate the server S.On the user side,Ui computes a′ = h(B∥h(A)∥r4a), as a′ = aa; A is authenticated by the user Ui successfully.In most cases, the capacity of legitimate user and remote server is the same; to be more precise, what the legitimate user knows can transform into what the remote server knows. So if the user impersonation attack can be performed, the server impersonation attack can be performed too.


#### 3.2.5. Man-in-the-Middle Attack

WithPWi∗ and IDi∗ that have been got from “password guessing attack” and “user anonymity,” respectively, A can execute a man-in-the-middle attack as follows:(1)
Interrupt{D,CIDi,Ni′,C} that Ui sends to S.(2)
Compute{Da,CIDa,Na′,Ca} as in “user impersonation attack,” and send them to S.(3)
Interrupt{a,r4} from S via an open channel.(4)
Compute{aa,r4a} as in “server impersonation attack,” and send them to Ui.Through above attack procedures, the adversaryA can execute a man-in-the-middle attack without being noticed by Ui or S.In fact, man-in-the-middle attack usually is a result of “server impersonation attack” and “user impersonation attack,” while offline dictionary attack is the original reason of these three attacks.


#### 3.2.6. Desynchronization Attack

As there is no any verification in password change phase, an adversaryA can execute desynchronization attack easily: stealing Ui’s smart card and inputting a random IDa, PWa, and a new password PWanew. According to the scheme, Mi and Ni will be replaced by Minew and Ninew, respectively, where Minew=Mi⊕h(PWa∥r1)⊕h(PWanew∥r1) and Ninew=Ni⊕h(PWa∥r1)⊕h(PWanew∥r1). As a result, even the legitimate user cannot login successfully.Desynchronization attack often happens in password change phase where the user, without inputting the correctPWi and IDi, can change the password successfully. This results in the that legitimate user with correct old password cannot login successfully. So if a user wants to change the password, he should be authenticated firstly, and there are usually two ways: interacting with the remote server like the authentication phase and interacting with the smart card. The second way requires a verification value from the smart card; thus such scheme is vulnerable to offline dictionary attack, but it helps detect wrong password input, which saves user’s time. The first one requires costing more time to make the user change the password and detect wrong password input.


#### 3.2.7. Insider Attack

In this scheme, the userUi submits a pair of PWi and IDi to the server S without any transformation or protection; thus the server S can get the PWi and IDi and carries out an insider attack to impersonate the user Ui.Insider attack is quite easy to deal with: do some transformation to thePWi and IDi, such as h(PWi∥b) and h(IDi∥b) (b is a random number).


## 3.1. Review of Yeh’s Scheme

This section gives a brief review of Yeh’s [43] scheme with user untraceability (shown in Figure 1).Figure 1
The scheme of Yeh et al.


### 3.1.1. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and two random numbers r1, r2 and then sends {IDi,PWi,r1,r2} to S via a secure channel.Step 2 (S⇒Ui).
S computes Mi=h(y∥r2)⊕h(PWi∥r1) and Ni=h(IDi∥x)⊕h(PWi∥r1) and then sends Ui a smart card with security parameters {Mi,Ni,r1,h(·)} via a secure channel and stores h(h(y∥r2)) in a table.


### 3.1.2. Login Phase and Authentication Phase

Step 1 (Ui→S).
U
i inputs IDi′, PWi′. The smart card generates a random number r3, computes A = Mi⊕h(PWi′∥r1) = h(y∥r2), D=r3⊕h(A), B = Ni⊕h(PWi′∥r1) = h(IDi′∥x), Ni′ = Ni⊕h(h(A∥r3)), CIDi = IDi′⊕h(Ni∥h(A)∥r3), and C = h(Ni∥h(A)∥B∥r3), and then sends {D,CIDi,Ni′,C} to S.Step 2 (S→Ui).
S traverses the h(h(y∥r2))∗ in table T, computes r3∗ = D⊕h(h(y∥r2))∗, Ni∗ = Ni′⊕h(h(h(y∥r2))∗∥r3∗), IDi∗=CIDi⊕h(Ni∗∥h(h(y∥r2))∗∥r3), B∗=h(IDi∗∥x), and C∗=h(Ni∗∥h(h(y∥r2))∗∥B∗∥r3∗), and then checks C∗=?C. If none of the value h(h(y∥r2))∗ satisfies the equation, end the session. Otherwise, S examines the freshness of r3 and whether {D,CIDi,Ni′,C} has been received before. If one of the conditions is invalid, terminate the session. Otherwise, S generates a random number r4, computes a=h(B∗∥h(h(y∥r2))∗∥r4), and sends {a,r4} to Ui.Step 3.
The smart card firstly checksr4, then computes a′=h(B∥h(A)∥r4), and checks whether a′ equals a. If true, Ui authenticates S.


### 3.1.3. Password Change Phase

IfUi wants to change the password, he/she inserts the smart card to the card reader and inputs IDi, PWi, and a new password PWinew. Then the smart card computes Minew=Mi⊕h(PWi∥r1)⊕h(PWinew∥r1) and Ninew=Ni⊕h(PWi∥r1)⊕h(PWinew∥r1) and then replaces Mi and Ni with Minew and Ninew.


## 3.1.1. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and two random numbers r1, r2 and then sends {IDi,PWi,r1,r2} to S via a secure channel.Step 2 (S⇒Ui).
S computes Mi=h(y∥r2)⊕h(PWi∥r1) and Ni=h(IDi∥x)⊕h(PWi∥r1) and then sends Ui a smart card with security parameters {Mi,Ni,r1,h(·)} via a secure channel and stores h(h(y∥r2)) in a table.


## 3.1.2. Login Phase and Authentication Phase

Step 1 (Ui→S).
U
i inputs IDi′, PWi′. The smart card generates a random number r3, computes A = Mi⊕h(PWi′∥r1) = h(y∥r2), D=r3⊕h(A), B = Ni⊕h(PWi′∥r1) = h(IDi′∥x), Ni′ = Ni⊕h(h(A∥r3)), CIDi = IDi′⊕h(Ni∥h(A)∥r3), and C = h(Ni∥h(A)∥B∥r3), and then sends {D,CIDi,Ni′,C} to S.Step 2 (S→Ui).
S traverses the h(h(y∥r2))∗ in table T, computes r3∗ = D⊕h(h(y∥r2))∗, Ni∗ = Ni′⊕h(h(h(y∥r2))∗∥r3∗), IDi∗=CIDi⊕h(Ni∗∥h(h(y∥r2))∗∥r3), B∗=h(IDi∗∥x), and C∗=h(Ni∗∥h(h(y∥r2))∗∥B∗∥r3∗), and then checks C∗=?C. If none of the value h(h(y∥r2))∗ satisfies the equation, end the session. Otherwise, S examines the freshness of r3 and whether {D,CIDi,Ni′,C} has been received before. If one of the conditions is invalid, terminate the session. Otherwise, S generates a random number r4, computes a=h(B∗∥h(h(y∥r2))∗∥r4), and sends {a,r4} to Ui.Step 3.
The smart card firstly checksr4, then computes a′=h(B∥h(A)∥r4), and checks whether a′ equals a. If true, Ui authenticates S.


## 3.1.3. Password Change Phase

IfUi wants to change the password, he/she inserts the smart card to the card reader and inputs IDi, PWi, and a new password PWinew. Then the smart card computes Minew=Mi⊕h(PWi∥r1)⊕h(PWinew∥r1) and Ninew=Ni⊕h(PWi∥r1)⊕h(PWinew∥r1) and then replaces Mi and Ni with Minew and Ninew.


## 3.2. Cryptanalysis of Yeh’s Schemes

In this section we show that Yeh’s scheme cannot resist various attacks, such as password guessing attack, impersonation attack, and desynchronization attack.


### 3.2.1. Offline Dictionary Attack via Verification Value in Channel

Supposing the adversaryA stole Ui’s smart card and then got security parameters Ni, r1, and Mi from the smart card, A also has {Di,CIDi,Ni′,C} through eavesdropping the open channel between Ui and S; then A can perform the attack by the following steps:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
ComputeA∗=Mi⊕h(PWi∗∥r1) = h(y∥r2)∗; Mi and r1 are extracted from the smart card.(3)
Computer3∗=D⊕h(A∗); D is eavesdropped from the open channel.(4)
ComputeB∗=Ni⊕h(PWi∗∥r1); Ni and r1 are extracted from the smart card.(5)
ComputeC∗=h(Ni∥h(A∗)∥B∗∥r3∗); Ni is extracted from the smart card.(6)
Verify the correctness ofPWi∗ by checking if C∗=?C, C is from the open channel.(7)
Repeat Steps (1), (2), (3), (4), (5), and (6) until the correct value ofPWi∗ is found.The time complexity of the above attack isO(|Dpw|∗(3TH+3TR)). TH is the running time for hash computation. TR is the running time for exclusive-or operation. |Dpw| denotes the number of passwords in Dpw, and |Dpw| is very limited in practice [49, 50]; usually |Dpw|≤106; so the above attack is quite efficient.Remark 1.
The offline dictionary attack here uses the verification from the open channel. The inherent reason for this attack is that (1) the adversary can find a verification to check whether the guessing value is correct; (2) the password is the only unknown value to the adversary; that is, the adversary can get other parameters consisting of the verification, except the password or the identity. To such attack, the lightweight public key algorithm is the necessary condition, as explained in [36].


### 3.2.2. User Anonymity

Once the adversaryA gets the password through “offline dictionary attack,” he can get the user’s ID by the following steps:(1)
ComputeA=Mi⊕h(PWi∗∥r1)=h(y∥r2); Mi and r1 are from the smart card.(2)
Computer3=D⊕h(A); D is from open channel.(3)
ComputeIDi∗=CIDi⊕h(Ni∥h(A)∥r3); Ni is from smart card; CIDi is from open channel.In computingIDi, what the server knows more than the adversary is h(h(y∥r2)), while, after getting the PWi, the adversary can get h(h(y∥r2)) by Mi⊕h(PWi∗∥r1), so in fact the adversary A has the same capacity as the server; thus A can get IDi according to the way the server does.


### 3.2.3. User Impersonation Attack

With thePWi∗ and the IDi∗, the adversary A can impersonate Ui as follows:(1)
ComputeA=Mi⊕h(PWi∗∥r1)=h(y∥r2); Mi and r1 are from the smart card.(2)
Generate a random numberr3.(3)
ComputeDa=r3⊕h(A).(4)
ComputeB=Ni⊕h(PWi∗∥r1)=h(IDi∗∥x).(5)
ComputeNa′=Ni⊕h(h(A∥r3)); Ni is extracted from the smart card.(6)
ComputeCIDa=IDi∗⊕h(Ni∥h(A)∥r3).(7)
ComputeCa=h(Ni∥h(A)∥B∥r3).(8)
Interrupt{D,CIDi,Ni′,C}; send {Da,CIDa,Na′, Ca} to S to impersonate Ui.As for the serverS, it computes r3∗=Da⊕h(h(y∥r2))∗, Ni∗=Na′⊕h(h(h(y∥r2))∗∥r3∗), IDi′=CIDa⊕h(Ni∗∥h(h(y∥r2))∗∥r3∗), B∗=h(IDi∗∥x), and C∗=h(Ni∗∥h(h(y∥r2))∗∥B∗∥r3∗) and then checks (1) C∗=?Ca; (2) the freshness of r3; and (3) whether {Da,CIDa,Na′,Ca} has ever been received before. All of them are satisfied, so A is authenticated by S successfully.WithPWi, IDi, and smart card, the adversary A has the same capacity as the legitimate user; that is, A can impersonate the user to the server successfully. The original reason for this attack is the offline dictionary attack.


### 3.2.4. Server Impersonation Attack

With thePWi∗, A can impersonate S as follows:(1)
Computeh(y∥r2)=Mi⊕h(PWi∗∥r1); Mi and r1 are extracted the from smart card.(2)
ComputeB∗=Ni⊕h(PWi∗∥r1)=h(IDi∗∥x); Ni is extracted from the smart card.(3)
Generate a random numberr4; compute aa=h(B∗∥h(h(y∥r2))∥r4a).(4)
Interrupt{a,r4}, and send {aa,r4a} to the user Ui to impersonate the server S.On the user side,Ui computes a′ = h(B∥h(A)∥r4a), as a′ = aa; A is authenticated by the user Ui successfully.In most cases, the capacity of legitimate user and remote server is the same; to be more precise, what the legitimate user knows can transform into what the remote server knows. So if the user impersonation attack can be performed, the server impersonation attack can be performed too.


### 3.2.5. Man-in-the-Middle Attack

WithPWi∗ and IDi∗ that have been got from “password guessing attack” and “user anonymity,” respectively, A can execute a man-in-the-middle attack as follows:(1)
Interrupt{D,CIDi,Ni′,C} that Ui sends to S.(2)
Compute{Da,CIDa,Na′,Ca} as in “user impersonation attack,” and send them to S.(3)
Interrupt{a,r4} from S via an open channel.(4)
Compute{aa,r4a} as in “server impersonation attack,” and send them to Ui.Through above attack procedures, the adversaryA can execute a man-in-the-middle attack without being noticed by Ui or S.In fact, man-in-the-middle attack usually is a result of “server impersonation attack” and “user impersonation attack,” while offline dictionary attack is the original reason of these three attacks.


### 3.2.6. Desynchronization Attack

As there is no any verification in password change phase, an adversaryA can execute desynchronization attack easily: stealing Ui’s smart card and inputting a random IDa, PWa, and a new password PWanew. According to the scheme, Mi and Ni will be replaced by Minew and Ninew, respectively, where Minew=Mi⊕h(PWa∥r1)⊕h(PWanew∥r1) and Ninew=Ni⊕h(PWa∥r1)⊕h(PWanew∥r1). As a result, even the legitimate user cannot login successfully.Desynchronization attack often happens in password change phase where the user, without inputting the correctPWi and IDi, can change the password successfully. This results in the that legitimate user with correct old password cannot login successfully. So if a user wants to change the password, he should be authenticated firstly, and there are usually two ways: interacting with the remote server like the authentication phase and interacting with the smart card. The second way requires a verification value from the smart card; thus such scheme is vulnerable to offline dictionary attack, but it helps detect wrong password input, which saves user’s time. The first one requires costing more time to make the user change the password and detect wrong password input.


### 3.2.7. Insider Attack

In this scheme, the userUi submits a pair of PWi and IDi to the server S without any transformation or protection; thus the server S can get the PWi and IDi and carries out an insider attack to impersonate the user Ui.Insider attack is quite easy to deal with: do some transformation to thePWi and IDi, such as h(PWi∥b) and h(IDi∥b) (b is a random number).


## 3.2.1. Offline Dictionary Attack via Verification Value in Channel

Supposing the adversaryA stole Ui’s smart card and then got security parameters Ni, r1, and Mi from the smart card, A also has {Di,CIDi,Ni′,C} through eavesdropping the open channel between Ui and S; then A can perform the attack by the following steps:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
ComputeA∗=Mi⊕h(PWi∗∥r1) = h(y∥r2)∗; Mi and r1 are extracted from the smart card.(3)
Computer3∗=D⊕h(A∗); D is eavesdropped from the open channel.(4)
ComputeB∗=Ni⊕h(PWi∗∥r1); Ni and r1 are extracted from the smart card.(5)
ComputeC∗=h(Ni∥h(A∗)∥B∗∥r3∗); Ni is extracted from the smart card.(6)
Verify the correctness ofPWi∗ by checking if C∗=?C, C is from the open channel.(7)
Repeat Steps (1), (2), (3), (4), (5), and (6) until the correct value ofPWi∗ is found.The time complexity of the above attack isO(|Dpw|∗(3TH+3TR)). TH is the running time for hash computation. TR is the running time for exclusive-or operation. |Dpw| denotes the number of passwords in Dpw, and |Dpw| is very limited in practice [49, 50]; usually |Dpw|≤106; so the above attack is quite efficient.Remark 1.
The offline dictionary attack here uses the verification from the open channel. The inherent reason for this attack is that (1) the adversary can find a verification to check whether the guessing value is correct; (2) the password is the only unknown value to the adversary; that is, the adversary can get other parameters consisting of the verification, except the password or the identity. To such attack, the lightweight public key algorithm is the necessary condition, as explained in [36].


## 3.2.2. User Anonymity

Once the adversaryA gets the password through “offline dictionary attack,” he can get the user’s ID by the following steps:(1)
ComputeA=Mi⊕h(PWi∗∥r1)=h(y∥r2); Mi and r1 are from the smart card.(2)
Computer3=D⊕h(A); D is from open channel.(3)
ComputeIDi∗=CIDi⊕h(Ni∥h(A)∥r3); Ni is from smart card; CIDi is from open channel.In computingIDi, what the server knows more than the adversary is h(h(y∥r2)), while, after getting the PWi, the adversary can get h(h(y∥r2)) by Mi⊕h(PWi∗∥r1), so in fact the adversary A has the same capacity as the server; thus A can get IDi according to the way the server does.


## 3.2.3. User Impersonation Attack

With thePWi∗ and the IDi∗, the adversary A can impersonate Ui as follows:(1)
ComputeA=Mi⊕h(PWi∗∥r1)=h(y∥r2); Mi and r1 are from the smart card.(2)
Generate a random numberr3.(3)
ComputeDa=r3⊕h(A).(4)
ComputeB=Ni⊕h(PWi∗∥r1)=h(IDi∗∥x).(5)
ComputeNa′=Ni⊕h(h(A∥r3)); Ni is extracted from the smart card.(6)
ComputeCIDa=IDi∗⊕h(Ni∥h(A)∥r3).(7)
ComputeCa=h(Ni∥h(A)∥B∥r3).(8)
Interrupt{D,CIDi,Ni′,C}; send {Da,CIDa,Na′, Ca} to S to impersonate Ui.As for the serverS, it computes r3∗=Da⊕h(h(y∥r2))∗, Ni∗=Na′⊕h(h(h(y∥r2))∗∥r3∗), IDi′=CIDa⊕h(Ni∗∥h(h(y∥r2))∗∥r3∗), B∗=h(IDi∗∥x), and C∗=h(Ni∗∥h(h(y∥r2))∗∥B∗∥r3∗) and then checks (1) C∗=?Ca; (2) the freshness of r3; and (3) whether {Da,CIDa,Na′,Ca} has ever been received before. All of them are satisfied, so A is authenticated by S successfully.WithPWi, IDi, and smart card, the adversary A has the same capacity as the legitimate user; that is, A can impersonate the user to the server successfully. The original reason for this attack is the offline dictionary attack.


## 3.2.4. Server Impersonation Attack

With thePWi∗, A can impersonate S as follows:(1)
Computeh(y∥r2)=Mi⊕h(PWi∗∥r1); Mi and r1 are extracted the from smart card.(2)
ComputeB∗=Ni⊕h(PWi∗∥r1)=h(IDi∗∥x); Ni is extracted from the smart card.(3)
Generate a random numberr4; compute aa=h(B∗∥h(h(y∥r2))∥r4a).(4)
Interrupt{a,r4}, and send {aa,r4a} to the user Ui to impersonate the server S.On the user side,Ui computes a′ = h(B∥h(A)∥r4a), as a′ = aa; A is authenticated by the user Ui successfully.In most cases, the capacity of legitimate user and remote server is the same; to be more precise, what the legitimate user knows can transform into what the remote server knows. So if the user impersonation attack can be performed, the server impersonation attack can be performed too.


## 3.2.5. Man-in-the-Middle Attack

WithPWi∗ and IDi∗ that have been got from “password guessing attack” and “user anonymity,” respectively, A can execute a man-in-the-middle attack as follows:(1)
Interrupt{D,CIDi,Ni′,C} that Ui sends to S.(2)
Compute{Da,CIDa,Na′,Ca} as in “user impersonation attack,” and send them to S.(3)
Interrupt{a,r4} from S via an open channel.(4)
Compute{aa,r4a} as in “server impersonation attack,” and send them to Ui.Through above attack procedures, the adversaryA can execute a man-in-the-middle attack without being noticed by Ui or S.In fact, man-in-the-middle attack usually is a result of “server impersonation attack” and “user impersonation attack,” while offline dictionary attack is the original reason of these three attacks.


## 3.2.6. Desynchronization Attack

As there is no any verification in password change phase, an adversaryA can execute desynchronization attack easily: stealing Ui’s smart card and inputting a random IDa, PWa, and a new password PWanew. According to the scheme, Mi and Ni will be replaced by Minew and Ninew, respectively, where Minew=Mi⊕h(PWa∥r1)⊕h(PWanew∥r1) and Ninew=Ni⊕h(PWa∥r1)⊕h(PWanew∥r1). As a result, even the legitimate user cannot login successfully.Desynchronization attack often happens in password change phase where the user, without inputting the correctPWi and IDi, can change the password successfully. This results in the that legitimate user with correct old password cannot login successfully. So if a user wants to change the password, he should be authenticated firstly, and there are usually two ways: interacting with the remote server like the authentication phase and interacting with the smart card. The second way requires a verification value from the smart card; thus such scheme is vulnerable to offline dictionary attack, but it helps detect wrong password input, which saves user’s time. The first one requires costing more time to make the user change the password and detect wrong password input.


## 3.2.7. Insider Attack

In this scheme, the userUi submits a pair of PWi and IDi to the server S without any transformation or protection; thus the server S can get the PWi and IDi and carries out an insider attack to impersonate the user Ui.Insider attack is quite easy to deal with: do some transformation to thePWi and IDi, such as h(PWi∥b) and h(IDi∥b) (b is a random number).


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

### 4.1. Review of Kang et al.’s Scheme

This section gives a brief review of Kang et al.’s scheme [44] (Figure 2). As little relevance as password change phase, we omit it.Figure 2
The scheme of Kang et al.


### 4.2. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and a random number b and computes RPWi=h(PWi∥b) and then sends {IDi,RPWi} to the server S via a secure channel.Step 2 (S⇒Ui).
S generates Pi×i and yi, where i∈[1,n], yi∈[1,n], and n is a small number, computes πyi from π=πP and πyi′=Shiftd(πyi), computes TPWi=h(RPWi∥IDi), Pi = h(x∥πyi′), Qi = h(πyi′∥x)⊕Pi, Ai=h(IDi∥πyi′)⊕Pi, and Bi=RPWi⊕Qi, and then issues the user Ui a smart card containing {TPWi,Ai,Bi,πyi′,h(·)} via a secure channel.Step 3.
U
i inputs b into the smart card.


#### 4.2.1. Login Phase and Authentication Phase

Step 1 (Ui→S).
U
i inserts his smart card and inputs IDi′, PWi′. The smart card computes RPWi′=h(PWi′∥b) and TPWi′=h(RPWi′∥IDi′) and then checks TPWi′=?TPWi. If not satisfied, reject the request. Otherwise, the smart card computes Pi′=Ai⊕h(IDi′∥πyi′), Qi′=Bi⊕RPWi′, and Ki′=Pi′⊕Qi′, generates a random number a and time stamp T1, computes TIi=TPWi′⊕Ki′, Li=Ki′⊕a, and Ci=h(TPWi′∥Ki′∥T1), and finally sends {TIi,Li,Ci,T1,πyi′} to S.Step 2 (S→Ui).
S firstly checks the freshness of T1, then calculates Ki=h(πyi′∥x), Ni=TIi⊕Ki, and Ci′ = h(Ni∥Ki∥T1), and compares Ci′ with Ci. If their values are not the same, reject the request; else generate a random number z and then compute a′=Li⊕Ki, and the session key SK=h(a′∥z∥T1∥T2), where T2 is the time stamp, Mi=h(SK∥Ki), and Ji=z⊕a′. After that S sends {Ji,Mi,T2} to Ui.Step 3.
U
i firstly checks the freshness of T2 and then computes z′=Ji⊕a, SK′=h(a∥z′∥T1∥T2), and Mi′=h(SK′∥Ki′) and verifies S through comparing Mi′ with Mi. If the values of them are the same, Ui authenticates S, and accepts SK as the session key. Otherwise, end the session.


### 4.3. Cryptanalysis of Kang et al.’s Schemes

#### 4.3.1. Offline Dictionary Attack via Verification Value in Channel

Supposing the adversaryA got Ui’s smart card and then acquired security parameters TPWi, Ai, b, and Bi from the smart card, A also has {TIi,Li,Ci,T1,πyi′} through eavesdropping the open channel between Ui and S; then A can perform the attack by the following steps:(1)
GuessPWi to be PWi∗ and IDi to be IDi∗.(2)
ComputeRPWi∗ = h(PWi∗∥b), TPWi∗ = h(RPWi∗∥IDi∗), Pi∗ = Ai⊕h(IDi∗∥πyi′), Qi∗ = Bi⊕RPWi∗, and Ki∗ = Pi∗⊕Qi∗; TPWi, Ai, b, Bi are extracted from the smart card.(3)
ComputeNi = TIi⊕Ki∗ and Ci∗ = h(Ni∥Ki∗∥T1), and {TIi,Li,T1,πyi′} is from the channel.(4)
Verify the correctness ofPWi∗ and IDi∗ by checking Ci∗=?Ci; Ci is from the channel.(5)
Repeat Steps (1), (2), (3), and (4) until the correct values ofPWi∗ and IDi∗ are found.The time complexity isO(|Dpw|∗4(TH+TR)), so the above attack is quite efficient. Once A has the PWi, he/she also can carry out user impersonation attack, server impersonation attack, and man-in-the-middle attack. And as the methods to those attacks are similar to the methods in Yeh’s schemes, it is unnecessary to go into details here.


#### 4.3.2. Offline Dictionary Attack via Verification Value in Smart Card

Supposing an adversaryA got Ui’s smart card and then acquired security parameters TPWi, Ai, b, and Bi from the smart card, then A can perform the attack as follows:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw and IDi to be IDi∗ from the identity dictionary space Did.(2)
ComputeRPWi∗ = h(PWi∗∥b) and TPWi∗ = h(RPWi∗∥IDi∗); b is from the smart card.(3)
Verify the correctness ofPWi∗ and IDi∗ by checking whether TPWi∗=?TPWi; TPWi is extracted from the smart card.(4)
Repeat Steps (1), (2), and (3) until thePWi∗ and IDi∗ are found.Remark 2.
The time complexity isO(|Dpw|∗2TH), so the above attack is quite efficient. This kind of offline dictionary attack above uses the verification from the smart card, while with the verification the user can change password locally. This is exactly what Wang et al. [29] demonstrated which is the trade-off between changing password locally and resisting offline-password attack. Luckily, in [11], D. Wang and P. Wang for the first time integrated “honeywords” and “fuzzy-verifiers” to settle such a long-standing security-usability conflict. So according to [11], we simply give an improved way to avoid such conflict. Let the verification TPWi = h((h(PWi∥b)∥IDi) mod n0), where 24≤n0≤28 and n0 determines the capacity of the pool of the (ID,PW). So now there are |Dpw|∗Did∖n0≈232 candidates of (ID,PW) pair for adversary to guess when n0=28 and |Dpw|=Did=26. For these candidates, the adversary can only guess the right one from online guessing, while there is also a way called “honeywords” to avoid such online dictionary guessing; “honeywords” in fact is a word list to timely detect whether the smart card is extracted.


#### 4.3.3. Forward Secrecy

SupposingA knew S’s secret key x, then he can calculate the session key SK as follows:(1)
Interrupt{TIi,Li,Ci,T1,πyi′} that Ui sends to S.(2)
ComputeKi=h(πyi′∥x); πyi′ is from smart card.(3)
Computea′=Li⊕Ki.(4)
Interrupt{Ji,Mi,T2} that S sends to Ui.(5)
Computez′=Ji⊕a′.(6)
ComputeSK=h(a′∥z′∥T1∥T2); at this point the user A gets SK successfully.In this scheme, the session key consists of a random numbera from Ui, a random number z from S, and two open time stamps T1 and T2. The key parameters are the two random number, while, compared to the adversary, what the server only knows more is the secret key x, so once the adversary knows the secret key x, he can compute the random number a′ chosen by Ui as the way the server does. On the other hand, in computing SK, what the user only knows more than the adversary is the random number a. While the adversary has known a now, thus the adversary also can compute the random number z chosen by the server as the user does. With a and z, the adversary gets sk. Furthermore, it proves that “more than two exponentiation operations conducted on the server side are necessary to achieve forward secrecy” [36].


## 4.1. Review of Kang et al.’s Scheme

This section gives a brief review of Kang et al.’s scheme [44] (Figure 2). As little relevance as password change phase, we omit it.Figure 2
The scheme of Kang et al.


## 4.2. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and a random number b and computes RPWi=h(PWi∥b) and then sends {IDi,RPWi} to the server S via a secure channel.Step 2 (S⇒Ui).
S generates Pi×i and yi, where i∈[1,n], yi∈[1,n], and n is a small number, computes πyi from π=πP and πyi′=Shiftd(πyi), computes TPWi=h(RPWi∥IDi), Pi = h(x∥πyi′), Qi = h(πyi′∥x)⊕Pi, Ai=h(IDi∥πyi′)⊕Pi, and Bi=RPWi⊕Qi, and then issues the user Ui a smart card containing {TPWi,Ai,Bi,πyi′,h(·)} via a secure channel.Step 3.
U
i inputs b into the smart card.


### 4.2.1. Login Phase and Authentication Phase

Step 1 (Ui→S).
U
i inserts his smart card and inputs IDi′, PWi′. The smart card computes RPWi′=h(PWi′∥b) and TPWi′=h(RPWi′∥IDi′) and then checks TPWi′=?TPWi. If not satisfied, reject the request. Otherwise, the smart card computes Pi′=Ai⊕h(IDi′∥πyi′), Qi′=Bi⊕RPWi′, and Ki′=Pi′⊕Qi′, generates a random number a and time stamp T1, computes TIi=TPWi′⊕Ki′, Li=Ki′⊕a, and Ci=h(TPWi′∥Ki′∥T1), and finally sends {TIi,Li,Ci,T1,πyi′} to S.Step 2 (S→Ui).
S firstly checks the freshness of T1, then calculates Ki=h(πyi′∥x), Ni=TIi⊕Ki, and Ci′ = h(Ni∥Ki∥T1), and compares Ci′ with Ci. If their values are not the same, reject the request; else generate a random number z and then compute a′=Li⊕Ki, and the session key SK=h(a′∥z∥T1∥T2), where T2 is the time stamp, Mi=h(SK∥Ki), and Ji=z⊕a′. After that S sends {Ji,Mi,T2} to Ui.Step 3.
U
i firstly checks the freshness of T2 and then computes z′=Ji⊕a, SK′=h(a∥z′∥T1∥T2), and Mi′=h(SK′∥Ki′) and verifies S through comparing Mi′ with Mi. If the values of them are the same, Ui authenticates S, and accepts SK as the session key. Otherwise, end the session.


## 4.2.1. Login Phase and Authentication Phase

Step 1 (Ui→S).
U
i inserts his smart card and inputs IDi′, PWi′. The smart card computes RPWi′=h(PWi′∥b) and TPWi′=h(RPWi′∥IDi′) and then checks TPWi′=?TPWi. If not satisfied, reject the request. Otherwise, the smart card computes Pi′=Ai⊕h(IDi′∥πyi′), Qi′=Bi⊕RPWi′, and Ki′=Pi′⊕Qi′, generates a random number a and time stamp T1, computes TIi=TPWi′⊕Ki′, Li=Ki′⊕a, and Ci=h(TPWi′∥Ki′∥T1), and finally sends {TIi,Li,Ci,T1,πyi′} to S.Step 2 (S→Ui).
S firstly checks the freshness of T1, then calculates Ki=h(πyi′∥x), Ni=TIi⊕Ki, and Ci′ = h(Ni∥Ki∥T1), and compares Ci′ with Ci. If their values are not the same, reject the request; else generate a random number z and then compute a′=Li⊕Ki, and the session key SK=h(a′∥z∥T1∥T2), where T2 is the time stamp, Mi=h(SK∥Ki), and Ji=z⊕a′. After that S sends {Ji,Mi,T2} to Ui.Step 3.
U
i firstly checks the freshness of T2 and then computes z′=Ji⊕a, SK′=h(a∥z′∥T1∥T2), and Mi′=h(SK′∥Ki′) and verifies S through comparing Mi′ with Mi. If the values of them are the same, Ui authenticates S, and accepts SK as the session key. Otherwise, end the session.


## 4.3. Cryptanalysis of Kang et al.’s Schemes

### 4.3.1. Offline Dictionary Attack via Verification Value in Channel

Supposing the adversaryA got Ui’s smart card and then acquired security parameters TPWi, Ai, b, and Bi from the smart card, A also has {TIi,Li,Ci,T1,πyi′} through eavesdropping the open channel between Ui and S; then A can perform the attack by the following steps:(1)
GuessPWi to be PWi∗ and IDi to be IDi∗.(2)
ComputeRPWi∗ = h(PWi∗∥b), TPWi∗ = h(RPWi∗∥IDi∗), Pi∗ = Ai⊕h(IDi∗∥πyi′), Qi∗ = Bi⊕RPWi∗, and Ki∗ = Pi∗⊕Qi∗; TPWi, Ai, b, Bi are extracted from the smart card.(3)
ComputeNi = TIi⊕Ki∗ and Ci∗ = h(Ni∥Ki∗∥T1), and {TIi,Li,T1,πyi′} is from the channel.(4)
Verify the correctness ofPWi∗ and IDi∗ by checking Ci∗=?Ci; Ci is from the channel.(5)
Repeat Steps (1), (2), (3), and (4) until the correct values ofPWi∗ and IDi∗ are found.The time complexity isO(|Dpw|∗4(TH+TR)), so the above attack is quite efficient. Once A has the PWi, he/she also can carry out user impersonation attack, server impersonation attack, and man-in-the-middle attack. And as the methods to those attacks are similar to the methods in Yeh’s schemes, it is unnecessary to go into details here.


### 4.3.2. Offline Dictionary Attack via Verification Value in Smart Card

Supposing an adversaryA got Ui’s smart card and then acquired security parameters TPWi, Ai, b, and Bi from the smart card, then A can perform the attack as follows:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw and IDi to be IDi∗ from the identity dictionary space Did.(2)
ComputeRPWi∗ = h(PWi∗∥b) and TPWi∗ = h(RPWi∗∥IDi∗); b is from the smart card.(3)
Verify the correctness ofPWi∗ and IDi∗ by checking whether TPWi∗=?TPWi; TPWi is extracted from the smart card.(4)
Repeat Steps (1), (2), and (3) until thePWi∗ and IDi∗ are found.Remark 2.
The time complexity isO(|Dpw|∗2TH), so the above attack is quite efficient. This kind of offline dictionary attack above uses the verification from the smart card, while with the verification the user can change password locally. This is exactly what Wang et al. [29] demonstrated which is the trade-off between changing password locally and resisting offline-password attack. Luckily, in [11], D. Wang and P. Wang for the first time integrated “honeywords” and “fuzzy-verifiers” to settle such a long-standing security-usability conflict. So according to [11], we simply give an improved way to avoid such conflict. Let the verification TPWi = h((h(PWi∥b)∥IDi) mod n0), where 24≤n0≤28 and n0 determines the capacity of the pool of the (ID,PW). So now there are |Dpw|∗Did∖n0≈232 candidates of (ID,PW) pair for adversary to guess when n0=28 and |Dpw|=Did=26. For these candidates, the adversary can only guess the right one from online guessing, while there is also a way called “honeywords” to avoid such online dictionary guessing; “honeywords” in fact is a word list to timely detect whether the smart card is extracted.


### 4.3.3. Forward Secrecy

SupposingA knew S’s secret key x, then he can calculate the session key SK as follows:(1)
Interrupt{TIi,Li,Ci,T1,πyi′} that Ui sends to S.(2)
ComputeKi=h(πyi′∥x); πyi′ is from smart card.(3)
Computea′=Li⊕Ki.(4)
Interrupt{Ji,Mi,T2} that S sends to Ui.(5)
Computez′=Ji⊕a′.(6)
ComputeSK=h(a′∥z′∥T1∥T2); at this point the user A gets SK successfully.In this scheme, the session key consists of a random numbera from Ui, a random number z from S, and two open time stamps T1 and T2. The key parameters are the two random number, while, compared to the adversary, what the server only knows more is the secret key x, so once the adversary knows the secret key x, he can compute the random number a′ chosen by Ui as the way the server does. On the other hand, in computing SK, what the user only knows more than the adversary is the random number a. While the adversary has known a now, thus the adversary also can compute the random number z chosen by the server as the user does. With a and z, the adversary gets sk. Furthermore, it proves that “more than two exponentiation operations conducted on the server side are necessary to achieve forward secrecy” [36].


## 4.3.1. Offline Dictionary Attack via Verification Value in Channel

Supposing the adversaryA got Ui’s smart card and then acquired security parameters TPWi, Ai, b, and Bi from the smart card, A also has {TIi,Li,Ci,T1,πyi′} through eavesdropping the open channel between Ui and S; then A can perform the attack by the following steps:(1)
GuessPWi to be PWi∗ and IDi to be IDi∗.(2)
ComputeRPWi∗ = h(PWi∗∥b), TPWi∗ = h(RPWi∗∥IDi∗), Pi∗ = Ai⊕h(IDi∗∥πyi′), Qi∗ = Bi⊕RPWi∗, and Ki∗ = Pi∗⊕Qi∗; TPWi, Ai, b, Bi are extracted from the smart card.(3)
ComputeNi = TIi⊕Ki∗ and Ci∗ = h(Ni∥Ki∗∥T1), and {TIi,Li,T1,πyi′} is from the channel.(4)
Verify the correctness ofPWi∗ and IDi∗ by checking Ci∗=?Ci; Ci is from the channel.(5)
Repeat Steps (1), (2), (3), and (4) until the correct values ofPWi∗ and IDi∗ are found.The time complexity isO(|Dpw|∗4(TH+TR)), so the above attack is quite efficient. Once A has the PWi, he/she also can carry out user impersonation attack, server impersonation attack, and man-in-the-middle attack. And as the methods to those attacks are similar to the methods in Yeh’s schemes, it is unnecessary to go into details here.


## 4.3.2. Offline Dictionary Attack via Verification Value in Smart Card

Supposing an adversaryA got Ui’s smart card and then acquired security parameters TPWi, Ai, b, and Bi from the smart card, then A can perform the attack as follows:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw and IDi to be IDi∗ from the identity dictionary space Did.(2)
ComputeRPWi∗ = h(PWi∗∥b) and TPWi∗ = h(RPWi∗∥IDi∗); b is from the smart card.(3)
Verify the correctness ofPWi∗ and IDi∗ by checking whether TPWi∗=?TPWi; TPWi is extracted from the smart card.(4)
Repeat Steps (1), (2), and (3) until thePWi∗ and IDi∗ are found.Remark 2.
The time complexity isO(|Dpw|∗2TH), so the above attack is quite efficient. This kind of offline dictionary attack above uses the verification from the smart card, while with the verification the user can change password locally. This is exactly what Wang et al. [29] demonstrated which is the trade-off between changing password locally and resisting offline-password attack. Luckily, in [11], D. Wang and P. Wang for the first time integrated “honeywords” and “fuzzy-verifiers” to settle such a long-standing security-usability conflict. So according to [11], we simply give an improved way to avoid such conflict. Let the verification TPWi = h((h(PWi∥b)∥IDi) mod n0), where 24≤n0≤28 and n0 determines the capacity of the pool of the (ID,PW). So now there are |Dpw|∗Did∖n0≈232 candidates of (ID,PW) pair for adversary to guess when n0=28 and |Dpw|=Did=26. For these candidates, the adversary can only guess the right one from online guessing, while there is also a way called “honeywords” to avoid such online dictionary guessing; “honeywords” in fact is a word list to timely detect whether the smart card is extracted.


## 4.3.3. Forward Secrecy

SupposingA knew S’s secret key x, then he can calculate the session key SK as follows:(1)
Interrupt{TIi,Li,Ci,T1,πyi′} that Ui sends to S.(2)
ComputeKi=h(πyi′∥x); πyi′ is from smart card.(3)
Computea′=Li⊕Ki.(4)
Interrupt{Ji,Mi,T2} that S sends to Ui.(5)
Computez′=Ji⊕a′.(6)
ComputeSK=h(a′∥z′∥T1∥T2); at this point the user A gets SK successfully.In this scheme, the session key consists of a random numbera from Ui, a random number z from S, and two open time stamps T1 and T2. The key parameters are the two random number, while, compared to the adversary, what the server only knows more is the secret key x, so once the adversary knows the secret key x, he can compute the random number a′ chosen by Ui as the way the server does. On the other hand, in computing SK, what the user only knows more than the adversary is the random number a. While the adversary has known a now, thus the adversary also can compute the random number z chosen by the server as the user does. With a and z, the adversary gets sk. Furthermore, it proves that “more than two exponentiation operations conducted on the server side are necessary to achieve forward secrecy” [36].


## 5. Cryptanalysis of Kaul et al.’s Schemes

### 5.1. Review of Kaul et al.’s Scheme

This section gives a brief review of Kaul et al.’s scheme [46] (Figure 3), and password change phase is also omitted.Figure 3
The scheme of Kaul et al.


#### 5.1.1. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and a random number b, then computes RPWi = h(b∥PWi), and submits S{IDi,RPWi} via a secure channel.Step 2 (S⇒Ui).
S chooses a unique random number yi for Ui and computes αi=h((IDi⊕x)∥y), βi=αi⊕h(IDi⊕RPWi), γi=yi⊕h(αi⊕RPWi), and χi=h(IDi∥RPWi∥yi∥αi). Then S issues Ui a smart card with {βi,γ,χi,h(·)} via a secure channel.Step 3.
U
i enters ηi to the smart card.


#### 5.1.2. Login Phase and Authentication Phase

Step 1 (Ui⇒S).
UserUi inserts the smart card and inputs IDi∗ and PWi∗. Smart card computes b = ηi⊕h(IDi∗⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗=βi⊕h(IDi∗⊕RPWi∗), yi∗ = γi⊕h(αi∗⊕RPWi∗), and χi∗ = h(IDi∗∥RPWi∗∥yi∗∥αi∗). If χi∗≠χi, the smart card declines the request, otherwise it computes ωi = yi⊕h(IDi⊕αi)⊕h(IDi⊕αi⊕T) and ϑi = h(IDi∥αi∥yi(αi⊕yi)∥T) and sends {ID,ωi,ϑi,T} to S.Step 2 (S⇒Ui).
ServerS first checks whether (T′-T)≤δT, then computes αi∗ = h((IDi∗⊕x)∥y), yi∗ = ωi∗⊕h(IDi∗⊕αi∗)⊕h(IDi∗⊕αi∗⊕T), and ϑi∗ = h(IDi∗∥αi∗∥yi∗∥(αi∗⊕yi∗)∥T), and further checks computed ϑi∗?=ϑi. If the verification passed, it computes μi = h(IDi∥yi∥(αi⊕yi)∥Ts), where Ts is S’s current time, and sends {μi,Ts} to Ui.Step 3.
Smart card first checks the freshness ofTs, then computes μi∗ = h(IDi∥yi∥(αi⊕yi)∥Ts), and then verifies μi∗?=μi to authenticate server.Step 4.
BothS and Ui accept the common session key SK = h(IDi⊕αi⊕yi⊕T⊕Ts).


### 5.2. Cryptanalysis of Kaul et al.’s Schemes

#### 5.2.1. User Anonymity

User anonymity preserves an adversary from acquiring user’s privacy message including lifestyle, habit, and hobbies by analyzing the login history, communications, and services request. In an era of big data, user anonymity has a profound significance. A well-designed protocol needs to keep the identity notion not only unexposed, but also untraceable. The former requires that even if an adversary eavesdrops the message via the open channel, he still cannot know whose communication message it is; the latter requires that the adversary does not know whether the eavesdropped message is from the same user. In fact, the latter is more restrictive than the former. However, in this scheme the user identityIDi was exposed in the open channel; the adversary just needs to eavesdrop the open channel to get the user IDi. With the IDi, every time the user logs in, the adversary can know. So the privacy of the user was revealed.


#### 5.2.2. Offline Dictionary Attack via Verification Value in Channel

A who extracts ηi, βi from smart card, and {ID,ωi,ϑi,T} can perform an offline dictionary attack as follows:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
Computeb = ηi⊕h(IDi⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗ = βi⊕h(IDi∗⊕RPWi∗), yi∗ = ωi∗⊕h(IDi∗⊕αi∗)⊕h(IDi∗⊕αi∗⊕T), and ϑi∗ = h(IDi∗∥αi∗∥yi∗∥(αi∗⊕yi∗)∥T), and ηi, βi are from smart card and {ID,ωi,T} is from the open channel.(3)
Verify the correctness ofPWi∗ by checking whether ϑi∗?=ϑi, and ϑi is from smart card.(4)
Repeat Steps (1), (2), and (3) until the correctPWi∗ is found.The time complexity isO(Dpw∗6TH+9TR), so the above attack is quite efficient. With IDi and PWi, A can conduct further attack such as impersonation attack, man-in-the-middle attack, and getting session key by the ways described in Sections 3.2.3, 3.2.4, 3.2.5, and 4.3.3. Thus, the whole security of the system is compromised.


#### 5.2.3. Offline Dictionary Attack via Verification Value in Smart Card

An adversaryA who gets the smart card from Ui extracts security parameters βi, γ, χi, ηi. Further as shown in the previous paragraph, A also can easily get IDi. So now the adversary A can perform an offline dictionary attack by the following steps:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
Computeb = ηi⊕h(IDi∗⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗ = βi⊕h(IDi∗⊕RPWi∗), yi∗ = γi⊕h(αi∗⊕RPWi∗), and χi∗ = h(IDi∗∥RPWi∗∥yi∗∥αi∗); βi, γ, χi, and ηi are extracted from Ui’s smart card.(3)
Verify the correctness ofPWi∗ by checking whether χi∗?=χi; χi is extracted from the smart card.(4)
Repeat Steps (1), (2), and (3) until thePWi∗ is found.The time complexity isO(Dpw∗5TH+5TR), so the above attack is quite efficient.


## 5.1. Review of Kaul et al.’s Scheme

This section gives a brief review of Kaul et al.’s scheme [46] (Figure 3), and password change phase is also omitted.Figure 3
The scheme of Kaul et al.


### 5.1.1. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and a random number b, then computes RPWi = h(b∥PWi), and submits S{IDi,RPWi} via a secure channel.Step 2 (S⇒Ui).
S chooses a unique random number yi for Ui and computes αi=h((IDi⊕x)∥y), βi=αi⊕h(IDi⊕RPWi), γi=yi⊕h(αi⊕RPWi), and χi=h(IDi∥RPWi∥yi∥αi). Then S issues Ui a smart card with {βi,γ,χi,h(·)} via a secure channel.Step 3.
U
i enters ηi to the smart card.


### 5.1.2. Login Phase and Authentication Phase

Step 1 (Ui⇒S).
UserUi inserts the smart card and inputs IDi∗ and PWi∗. Smart card computes b = ηi⊕h(IDi∗⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗=βi⊕h(IDi∗⊕RPWi∗), yi∗ = γi⊕h(αi∗⊕RPWi∗), and χi∗ = h(IDi∗∥RPWi∗∥yi∗∥αi∗). If χi∗≠χi, the smart card declines the request, otherwise it computes ωi = yi⊕h(IDi⊕αi)⊕h(IDi⊕αi⊕T) and ϑi = h(IDi∥αi∥yi(αi⊕yi)∥T) and sends {ID,ωi,ϑi,T} to S.Step 2 (S⇒Ui).
ServerS first checks whether (T′-T)≤δT, then computes αi∗ = h((IDi∗⊕x)∥y), yi∗ = ωi∗⊕h(IDi∗⊕αi∗)⊕h(IDi∗⊕αi∗⊕T), and ϑi∗ = h(IDi∗∥αi∗∥yi∗∥(αi∗⊕yi∗)∥T), and further checks computed ϑi∗?=ϑi. If the verification passed, it computes μi = h(IDi∥yi∥(αi⊕yi)∥Ts), where Ts is S’s current time, and sends {μi,Ts} to Ui.Step 3.
Smart card first checks the freshness ofTs, then computes μi∗ = h(IDi∥yi∥(αi⊕yi)∥Ts), and then verifies μi∗?=μi to authenticate server.Step 4.
BothS and Ui accept the common session key SK = h(IDi⊕αi⊕yi⊕T⊕Ts).


## 5.1.1. Registration Phase

Step 1 (Ui⇒S).
U
i chooses IDi, PWi, and a random number b, then computes RPWi = h(b∥PWi), and submits S{IDi,RPWi} via a secure channel.Step 2 (S⇒Ui).
S chooses a unique random number yi for Ui and computes αi=h((IDi⊕x)∥y), βi=αi⊕h(IDi⊕RPWi), γi=yi⊕h(αi⊕RPWi), and χi=h(IDi∥RPWi∥yi∥αi). Then S issues Ui a smart card with {βi,γ,χi,h(·)} via a secure channel.Step 3.
U
i enters ηi to the smart card.


## 5.1.2. Login Phase and Authentication Phase

Step 1 (Ui⇒S).
UserUi inserts the smart card and inputs IDi∗ and PWi∗. Smart card computes b = ηi⊕h(IDi∗⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗=βi⊕h(IDi∗⊕RPWi∗), yi∗ = γi⊕h(αi∗⊕RPWi∗), and χi∗ = h(IDi∗∥RPWi∗∥yi∗∥αi∗). If χi∗≠χi, the smart card declines the request, otherwise it computes ωi = yi⊕h(IDi⊕αi)⊕h(IDi⊕αi⊕T) and ϑi = h(IDi∥αi∥yi(αi⊕yi)∥T) and sends {ID,ωi,ϑi,T} to S.Step 2 (S⇒Ui).
ServerS first checks whether (T′-T)≤δT, then computes αi∗ = h((IDi∗⊕x)∥y), yi∗ = ωi∗⊕h(IDi∗⊕αi∗)⊕h(IDi∗⊕αi∗⊕T), and ϑi∗ = h(IDi∗∥αi∗∥yi∗∥(αi∗⊕yi∗)∥T), and further checks computed ϑi∗?=ϑi. If the verification passed, it computes μi = h(IDi∥yi∥(αi⊕yi)∥Ts), where Ts is S’s current time, and sends {μi,Ts} to Ui.Step 3.
Smart card first checks the freshness ofTs, then computes μi∗ = h(IDi∥yi∥(αi⊕yi)∥Ts), and then verifies μi∗?=μi to authenticate server.Step 4.
BothS and Ui accept the common session key SK = h(IDi⊕αi⊕yi⊕T⊕Ts).


## 5.2. Cryptanalysis of Kaul et al.’s Schemes

### 5.2.1. User Anonymity

User anonymity preserves an adversary from acquiring user’s privacy message including lifestyle, habit, and hobbies by analyzing the login history, communications, and services request. In an era of big data, user anonymity has a profound significance. A well-designed protocol needs to keep the identity notion not only unexposed, but also untraceable. The former requires that even if an adversary eavesdrops the message via the open channel, he still cannot know whose communication message it is; the latter requires that the adversary does not know whether the eavesdropped message is from the same user. In fact, the latter is more restrictive than the former. However, in this scheme the user identityIDi was exposed in the open channel; the adversary just needs to eavesdrop the open channel to get the user IDi. With the IDi, every time the user logs in, the adversary can know. So the privacy of the user was revealed.


### 5.2.2. Offline Dictionary Attack via Verification Value in Channel

A who extracts ηi, βi from smart card, and {ID,ωi,ϑi,T} can perform an offline dictionary attack as follows:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
Computeb = ηi⊕h(IDi⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗ = βi⊕h(IDi∗⊕RPWi∗), yi∗ = ωi∗⊕h(IDi∗⊕αi∗)⊕h(IDi∗⊕αi∗⊕T), and ϑi∗ = h(IDi∗∥αi∗∥yi∗∥(αi∗⊕yi∗)∥T), and ηi, βi are from smart card and {ID,ωi,T} is from the open channel.(3)
Verify the correctness ofPWi∗ by checking whether ϑi∗?=ϑi, and ϑi is from smart card.(4)
Repeat Steps (1), (2), and (3) until the correctPWi∗ is found.The time complexity isO(Dpw∗6TH+9TR), so the above attack is quite efficient. With IDi and PWi, A can conduct further attack such as impersonation attack, man-in-the-middle attack, and getting session key by the ways described in Sections 3.2.3, 3.2.4, 3.2.5, and 4.3.3. Thus, the whole security of the system is compromised.


### 5.2.3. Offline Dictionary Attack via Verification Value in Smart Card

An adversaryA who gets the smart card from Ui extracts security parameters βi, γ, χi, ηi. Further as shown in the previous paragraph, A also can easily get IDi. So now the adversary A can perform an offline dictionary attack by the following steps:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
Computeb = ηi⊕h(IDi∗⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗ = βi⊕h(IDi∗⊕RPWi∗), yi∗ = γi⊕h(αi∗⊕RPWi∗), and χi∗ = h(IDi∗∥RPWi∗∥yi∗∥αi∗); βi, γ, χi, and ηi are extracted from Ui’s smart card.(3)
Verify the correctness ofPWi∗ by checking whether χi∗?=χi; χi is extracted from the smart card.(4)
Repeat Steps (1), (2), and (3) until thePWi∗ is found.The time complexity isO(Dpw∗5TH+5TR), so the above attack is quite efficient.


## 5.2.1. User Anonymity

User anonymity preserves an adversary from acquiring user’s privacy message including lifestyle, habit, and hobbies by analyzing the login history, communications, and services request. In an era of big data, user anonymity has a profound significance. A well-designed protocol needs to keep the identity notion not only unexposed, but also untraceable. The former requires that even if an adversary eavesdrops the message via the open channel, he still cannot know whose communication message it is; the latter requires that the adversary does not know whether the eavesdropped message is from the same user. In fact, the latter is more restrictive than the former. However, in this scheme the user identityIDi was exposed in the open channel; the adversary just needs to eavesdrop the open channel to get the user IDi. With the IDi, every time the user logs in, the adversary can know. So the privacy of the user was revealed.


## 5.2.2. Offline Dictionary Attack via Verification Value in Channel

A who extracts ηi, βi from smart card, and {ID,ωi,ϑi,T} can perform an offline dictionary attack as follows:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
Computeb = ηi⊕h(IDi⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗ = βi⊕h(IDi∗⊕RPWi∗), yi∗ = ωi∗⊕h(IDi∗⊕αi∗)⊕h(IDi∗⊕αi∗⊕T), and ϑi∗ = h(IDi∗∥αi∗∥yi∗∥(αi∗⊕yi∗)∥T), and ηi, βi are from smart card and {ID,ωi,T} is from the open channel.(3)
Verify the correctness ofPWi∗ by checking whether ϑi∗?=ϑi, and ϑi is from smart card.(4)
Repeat Steps (1), (2), and (3) until the correctPWi∗ is found.The time complexity isO(Dpw∗6TH+9TR), so the above attack is quite efficient. With IDi and PWi, A can conduct further attack such as impersonation attack, man-in-the-middle attack, and getting session key by the ways described in Sections 3.2.3, 3.2.4, 3.2.5, and 4.3.3. Thus, the whole security of the system is compromised.


## 5.2.3. Offline Dictionary Attack via Verification Value in Smart Card

An adversaryA who gets the smart card from Ui extracts security parameters βi, γ, χi, ηi. Further as shown in the previous paragraph, A also can easily get IDi. So now the adversary A can perform an offline dictionary attack by the following steps:(1)
Guess the value ofPWi to be PWi∗ from the password dictionary space Dpw.(2)
Computeb = ηi⊕h(IDi∗⊕PWi∗), RPWi∗ = h(b∥PWi∗), αi∗ = βi⊕h(IDi∗⊕RPWi∗), yi∗ = γi⊕h(αi∗⊕RPWi∗), and χi∗ = h(IDi∗∥RPWi∗∥yi∗∥αi∗); βi, γ, χi, and ηi are extracted from Ui’s smart card.(3)
Verify the correctness ofPWi∗ by checking whether χi∗?=χi; χi is extracted from the smart card.(4)
Repeat Steps (1), (2), and (3) until thePWi∗ is found.The time complexity isO(Dpw∗5TH+5TR), so the above attack is quite efficient.


## 6. A Deep Exploration to Offline Dictionary Attack

The scheme of Yeh, Kang et al., and Kaul et al. cannot resist offline-password guessing attacks, while this is exactly what most two-factor remote authentication schemes actually suffer from. As we mentioned before, such attack is also one of the original reasons for other attacks. In this section, we try to explain why it is so hard to avoid offline dictionary attack. Furthermore, we for the first time recommend distinguishingoffline dictionary attack via verification value in smart card (hereafter called Attack I) fromoffline dictionary attack via verification value in channel (hereafter called Attack II). When talking about offline dictionary attack, most papers [36, 51, 52] ignore the difference between them and collectively call them as offline dictionary attack (offline-password guessing attack). Although the basic principles of these two attacks are the same, the key parameters transmitted in the insecure channel or in smart card, having no “camouflage” by random numbers or other special parameters only owned by the user or the server, the adversary can get a verification (usually it is the key parameter for the server or the user to verify the validity of the other one) to perform dictionary attack. Where the verifications come from is different, Attack I uses the verification from the smart card and Attack II from the channel. Do not overlook this little difference; this results in the quite slight difference in the corresponding solutions. Distinguishing them contributes to in-depth analysis of design principles. In this section, we analyze these two attacks thoroughly.


### 6.1. Solutions to Offline Dictionary Attack via Verification Value in Smart Card

In the schemes of Kang et al. and Kaul et al., to achieve better user-friendliness, that is, changing password locally and detecting the wrong password-inputting timely, a verification for a smart card to authenticate the user is stored in smart card. This results inA getting the key parameters ϑi and TPWi in smart card, which leads to Attack I. What if there was no such verification parameters? Then the password change phase may be influenced, such as Yeh’s scheme which changes password remotely and fails to detect wrong password input timely. In fact, [29] points out that “there is an unavoidable trade-off when achieving the password change locally and resisting offline dictionary attack.” More specifically and accurately, the offline dictionary attack here should be specific to Attack I; it usually can be avoided by two ways:(i)
A new approach called “a fuzzy verifier” and “honeywords” [11], which is a new solution to such problem. This approach can greatly increase the cost of guessing password in respect of A. And we have given a simple application case in Section 4.3.2.(ii)
Sacrificing certain performance (e.g., not providing the attribute of changing password locally). In other words, it is a problem of the trade-off between security and effectiveness. According to this principle, some schemes [43, 53, 54] just simply remove the authentication between the user and the smart card. Therefore, this scheme is secure to Attack II, while the cost is failing to detect the wrong password input timely (costing more time).Obviously, Attack II is not included in the above situation. So just collectively calling the two attacks as offline dictionary attack will result in confusion and making the problem more complicated.


### 6.2. Solutions to Offline Dictionary Attack via Verification Value in Channel

In Yeh’s scheme, if we regard the parameters in smart card as opened, then the key parameters (i.e., the verification refers to the parameters used to verify the validity of the participants, and we useVeri_Vau to represent it) C=f(PWi,IDi,r3), where f() refers to a series of cryptographic operations in the protocol, and f(PWi,IDi,r3) means that those cryptographic operations are actually only related to PWi,IDi,r3. On the face of it, the Veri_VauC is protected by the random number r3. While with in-depth examination, it is clear that r3 can be computed by PWi. So in fact, the Veri_Vau=C=f(PWi,IDi). Then if an adversary guesses the PWi and IDi to be PWi∗ and IDi∗, he/she can use Veri_Vau to check the correct guessed value and thus carry out an offline dictionary attack, that is, Attack II.Typically, only when theVeri_Vau was “camouflaged” by random numbers or other special parameters which only the user and the server can get can the scheme resist Attack II, such as [11, 14, 55]. So how can we conceal the Veri_Vau and those sensitive parameters?Naturally, someone may think of a symmetric cryptography way: if the message transmitted in the open channel is encrypted, then only the one owning the key can read the message. It seems a good solution. However, it is far from practical: how can the key be distributed and stored? Especially to the users, where can they store that private key securely? Furthermore, with the number of servers accessed increasing, the number of the keys which the user needs to store increases too; for the servers, the storage of those keys is also a big problem; it will consume a lot of storage space, and once the storage space is leaked, the security of the system will run down. Anyway, symmetric cryptography is beyond our consideration. In this work, we focus on what Ma et al. [36] advised, that is, the public key algorithm to deal with Attack II. And here is our brief explanation about the necessary public-key algorithm (for more detail please refer to [36]).Getting a verification (Veri_Vau) by the adversary in open channel is the main reason for Attack II. So a well-designed scheme has to protect the Veri_Vau in the open channel. Then how can we protect them?On the one hand, the parameters in the smart card can be captured by the adversary. So if we do not consider a symmetric cryptography, the only way is to use random numbers as a camouflage to protect the Veri_Vau. What is more, the random number cannot be exposed to the open channel and cannot be computed only with PWi and IDi.On the other hand, the server needs to know the random number to compute the Veri_Vau. So based on the two points, the public key algorithm is a necessary approach. Moreover, smart cards always have limited memory and computing power; thus the lightweight public key operations are good choices.However, many schemes though equipped with a public key algorithm still fail to resist Attack II, such as [52, 56, 57]. The inherent reason is the incorrectness of deploying the public key algorithm. So how can we correctly apply the public key algorithm to a authentication protocol? We will give one of the solutions, although it is not the only one, but it actually is one of the many effective solutions. Furthermore, we will give an reference model of such solution (see Figure 4) and use Yeh’s scheme as an example to verify its feasibility.Figure 4
The reference model to employ a public key algorithm securely.As we all know, the nature of a authentication protocol is to provide a secure mutual authentication. And the basis for authentication in a password-based scheme with smart card is “what you know” and “what you have.” To a user, thePWi and IDi are what they know; the smart card is what they have. While as the parameters in the card can be extracted by the adversary and the card itself can easily be stolen, so it seems that the smart card acts as an assistant. To a server, the long term key x is what they know. The verifier table is what they have. Similarly, the verifier table actually also acts as an assistant.So when the server authenticates the user, the user has to prove that he really knowsPWi and IDi and has the corresponding smart card, while, in order to prevent inside attack and eavesdropping attack, the user cannot tell the server the value of PWi directly. Then a good way to solve such conflict is to negotiate an intermediate parameter Mid_Vau as a key evidence of authentication, where Mid_Vau=f(PWi,IDi,x). This step is finished in registration phase and the related auxiliary parameters are stored in the smart card. So if a user has the corresponding smart card, then he/she can computes the Mid_Vau as f(PWi,IDi). Therefore, with the Mid_Vau, we can verify not only whether the user knows about the PWi and IDi, but also whether the user has the corresponding smart card. However, as Mid_Vau=f(PWi,IDi) in helping with the smart card, if Veri_Vau=f(Mid_Vau), then once the adversary gets the smart card, he/she can guess the PWi and IDi to be PWi∗ and IDi∗, respectively, then intercept the Veri_Vau to check the correctness of the guessed value, and thus carry out Attack II. Take Yeh’s scheme as an example, in this scheme, the Mid_Vau=h(IDi∥x). To Ui, Mid_Vau=Ni⊕h(PWi∥r1), where Ni and r1 are from smart card, Veri_Vau=f(Mid_Vau)=f(PWi,IDi), and thus an adversary with the card conducts Attack II successfully.Therefore, besides theMid_Vau, there should be other key parameters which only S and Ui can compute. As PWi, IDi, and smart card have been used for Mid_Vau, it makes no sense to use them again. Thus now, to a user, he/she has no more things which can be used as evidence. The one good choice seems to initiate a challenge for the server to respond. Actually, the challenge is a random number, and the transmission and response to the challenge require the help of a public key algorithm. All in all, the other key parameters which consist of Veri_Vau should be equipped with a public key algorithm; then the Veri_Vau should be f(Mid_Vau,Pub_Vau), where the Pub_Vau refers to the parameters deploying a public key algorithm. To Ui, with the knowledge of the random number r, Pub_Vau=Pub_key(r,y), where y is the public key and Pub_key(r,y) refer to a series of public key operations; to S, with the knowledge of private key x, Pub_Vau=Pub_key(x,Tran_Vau), where Tran_Vau=Pub_key(r). All in all, to resist Attack II, the Veri_Vau should satisfy Veri_Vau=f(Mid_Vau,Pub_Vau); the Mid_Vau, PWi, IDi, r, and Pub_Vau cannot be exposed to the open channel; furthermore, Tran_Vau should be transmitted to the server. When Ui authenticates S, if only considering resisting Attack II, S only requires proving that it knows about the Mid_Vau and Pub_Vau. Furthermore, the parameters transmitted in the open channel follow the same principles as above.Now, we take Yeh’s scheme as an example to check the effectiveness of our reference model. And we select the Computational Diffie-Hellman problem to construct the public key algorithm. In Yeh et al.’s scheme, theMid_Vau has been designed well, so we only need to apply the Computational Diffie-Hellman problem to this scheme. The definition of the Computational Diffie-Hellman problem is as follows.g is the generator of a cyclic group Zp∗; then, given gβ and gα where β,α∈Zp∗, it is hard to compute α,β within a polynomial time.According to this, we can design a lightweight public key algorithm for the user and the server:S selects a larger prime p, a generator g of cyclic group Zp∗, and a secret key x and computes the public key Y=gx mod p. Then if Ui selects a random number r1, it computes M1=gr1 mod p and M2=Yr1 mod p and sends M1 to S. S can compute M2 as M1x mod p. Here, M1=Tran_Vau and M2=Pub_Vau; even the adversary intercepts the M1; he/she still cannot compute the M2. So then S only needs to prove that it knows about the M2. Furthermore, to Ui, M1=Pub_key(r) and M2=Pub_key(r,Y); to S, M2=Pub_key(x,Tran_Vau); it also follows the principles mentioned above. In short, we improve Yeh’s scheme as shown in Figure 5.Figure 5
Improving Yeh et al.’s scheme to resist Attack II.In the improved scheme,Veri_Vau=C=f(Mid_Vau, Pub_Vau); even the adversary guesses the PWi and IDi to be PWi∗ and IDi∗, while without Pub_Vau, he/she cannot find a verification to check the correctness of the guessed value and thus fails to perform Attack II. It should be noted that we only improve Yeh’s scheme to be secure to Attack II, and the reference model can only be applied to resisting Attack II.It is generally accepted that public key algorithm is necessary for resisting offline dictionary attack, while, according to our analysis, the offline dictionary attack here should be specific to Attack II, and Attack I is not included in it: the public key algorithm consists of a private key and a public key. In Attack II, the vulnerability takes place in the authentication between the server and the smart card. So the public key algorithm acts on the server and the smart card. Usually the server takes the responsibility to keep private keyx, while, in Attack I, the vulnerability takes place in the authentication between the user and the smart card. But it makes no sense to both of them to own such private key for two reasons at least:(i)
To the users: he always uses the password as the unique parameter to get authenticated, and the private key plays the same role as the password. Moreover, the private key is too long for the user to remember or preserve.(ii)
Smart card: as we have stated before, the parameters in the smart card can be easily obtained by an adversary.


## 6.1. Solutions to Offline Dictionary Attack via Verification Value in Smart Card

In the schemes of Kang et al. and Kaul et al., to achieve better user-friendliness, that is, changing password locally and detecting the wrong password-inputting timely, a verification for a smart card to authenticate the user is stored in smart card. This results inA getting the key parameters ϑi and TPWi in smart card, which leads to Attack I. What if there was no such verification parameters? Then the password change phase may be influenced, such as Yeh’s scheme which changes password remotely and fails to detect wrong password input timely. In fact, [29] points out that “there is an unavoidable trade-off when achieving the password change locally and resisting offline dictionary attack.” More specifically and accurately, the offline dictionary attack here should be specific to Attack I; it usually can be avoided by two ways:(i)
A new approach called “a fuzzy verifier” and “honeywords” [11], which is a new solution to such problem. This approach can greatly increase the cost of guessing password in respect of A. And we have given a simple application case in Section 4.3.2.(ii)
Sacrificing certain performance (e.g., not providing the attribute of changing password locally). In other words, it is a problem of the trade-off between security and effectiveness. According to this principle, some schemes [43, 53, 54] just simply remove the authentication between the user and the smart card. Therefore, this scheme is secure to Attack II, while the cost is failing to detect the wrong password input timely (costing more time).Obviously, Attack II is not included in the above situation. So just collectively calling the two attacks as offline dictionary attack will result in confusion and making the problem more complicated.


## 6.2. Solutions to Offline Dictionary Attack via Verification Value in Channel

In Yeh’s scheme, if we regard the parameters in smart card as opened, then the key parameters (i.e., the verification refers to the parameters used to verify the validity of the participants, and we useVeri_Vau to represent it) C=f(PWi,IDi,r3), where f() refers to a series of cryptographic operations in the protocol, and f(PWi,IDi,r3) means that those cryptographic operations are actually only related to PWi,IDi,r3. On the face of it, the Veri_VauC is protected by the random number r3. While with in-depth examination, it is clear that r3 can be computed by PWi. So in fact, the Veri_Vau=C=f(PWi,IDi). Then if an adversary guesses the PWi and IDi to be PWi∗ and IDi∗, he/she can use Veri_Vau to check the correct guessed value and thus carry out an offline dictionary attack, that is, Attack II.Typically, only when theVeri_Vau was “camouflaged” by random numbers or other special parameters which only the user and the server can get can the scheme resist Attack II, such as [11, 14, 55]. So how can we conceal the Veri_Vau and those sensitive parameters?Naturally, someone may think of a symmetric cryptography way: if the message transmitted in the open channel is encrypted, then only the one owning the key can read the message. It seems a good solution. However, it is far from practical: how can the key be distributed and stored? Especially to the users, where can they store that private key securely? Furthermore, with the number of servers accessed increasing, the number of the keys which the user needs to store increases too; for the servers, the storage of those keys is also a big problem; it will consume a lot of storage space, and once the storage space is leaked, the security of the system will run down. Anyway, symmetric cryptography is beyond our consideration. In this work, we focus on what Ma et al. [36] advised, that is, the public key algorithm to deal with Attack II. And here is our brief explanation about the necessary public-key algorithm (for more detail please refer to [36]).Getting a verification (Veri_Vau) by the adversary in open channel is the main reason for Attack II. So a well-designed scheme has to protect the Veri_Vau in the open channel. Then how can we protect them?On the one hand, the parameters in the smart card can be captured by the adversary. So if we do not consider a symmetric cryptography, the only way is to use random numbers as a camouflage to protect the Veri_Vau. What is more, the random number cannot be exposed to the open channel and cannot be computed only with PWi and IDi.On the other hand, the server needs to know the random number to compute the Veri_Vau. So based on the two points, the public key algorithm is a necessary approach. Moreover, smart cards always have limited memory and computing power; thus the lightweight public key operations are good choices.However, many schemes though equipped with a public key algorithm still fail to resist Attack II, such as [52, 56, 57]. The inherent reason is the incorrectness of deploying the public key algorithm. So how can we correctly apply the public key algorithm to a authentication protocol? We will give one of the solutions, although it is not the only one, but it actually is one of the many effective solutions. Furthermore, we will give an reference model of such solution (see Figure 4) and use Yeh’s scheme as an example to verify its feasibility.Figure 4
The reference model to employ a public key algorithm securely.As we all know, the nature of a authentication protocol is to provide a secure mutual authentication. And the basis for authentication in a password-based scheme with smart card is “what you know” and “what you have.” To a user, thePWi and IDi are what they know; the smart card is what they have. While as the parameters in the card can be extracted by the adversary and the card itself can easily be stolen, so it seems that the smart card acts as an assistant. To a server, the long term key x is what they know. The verifier table is what they have. Similarly, the verifier table actually also acts as an assistant.So when the server authenticates the user, the user has to prove that he really knowsPWi and IDi and has the corresponding smart card, while, in order to prevent inside attack and eavesdropping attack, the user cannot tell the server the value of PWi directly. Then a good way to solve such conflict is to negotiate an intermediate parameter Mid_Vau as a key evidence of authentication, where Mid_Vau=f(PWi,IDi,x). This step is finished in registration phase and the related auxiliary parameters are stored in the smart card. So if a user has the corresponding smart card, then he/she can computes the Mid_Vau as f(PWi,IDi). Therefore, with the Mid_Vau, we can verify not only whether the user knows about the PWi and IDi, but also whether the user has the corresponding smart card. However, as Mid_Vau=f(PWi,IDi) in helping with the smart card, if Veri_Vau=f(Mid_Vau), then once the adversary gets the smart card, he/she can guess the PWi and IDi to be PWi∗ and IDi∗, respectively, then intercept the Veri_Vau to check the correctness of the guessed value, and thus carry out Attack II. Take Yeh’s scheme as an example, in this scheme, the Mid_Vau=h(IDi∥x). To Ui, Mid_Vau=Ni⊕h(PWi∥r1), where Ni and r1 are from smart card, Veri_Vau=f(Mid_Vau)=f(PWi,IDi), and thus an adversary with the card conducts Attack II successfully.Therefore, besides theMid_Vau, there should be other key parameters which only S and Ui can compute. As PWi, IDi, and smart card have been used for Mid_Vau, it makes no sense to use them again. Thus now, to a user, he/she has no more things which can be used as evidence. The one good choice seems to initiate a challenge for the server to respond. Actually, the challenge is a random number, and the transmission and response to the challenge require the help of a public key algorithm. All in all, the other key parameters which consist of Veri_Vau should be equipped with a public key algorithm; then the Veri_Vau should be f(Mid_Vau,Pub_Vau), where the Pub_Vau refers to the parameters deploying a public key algorithm. To Ui, with the knowledge of the random number r, Pub_Vau=Pub_key(r,y), where y is the public key and Pub_key(r,y) refer to a series of public key operations; to S, with the knowledge of private key x, Pub_Vau=Pub_key(x,Tran_Vau), where Tran_Vau=Pub_key(r). All in all, to resist Attack II, the Veri_Vau should satisfy Veri_Vau=f(Mid_Vau,Pub_Vau); the Mid_Vau, PWi, IDi, r, and Pub_Vau cannot be exposed to the open channel; furthermore, Tran_Vau should be transmitted to the server. When Ui authenticates S, if only considering resisting Attack II, S only requires proving that it knows about the Mid_Vau and Pub_Vau. Furthermore, the parameters transmitted in the open channel follow the same principles as above.Now, we take Yeh’s scheme as an example to check the effectiveness of our reference model. And we select the Computational Diffie-Hellman problem to construct the public key algorithm. In Yeh et al.’s scheme, theMid_Vau has been designed well, so we only need to apply the Computational Diffie-Hellman problem to this scheme. The definition of the Computational Diffie-Hellman problem is as follows.g is the generator of a cyclic group Zp∗; then, given gβ and gα where β,α∈Zp∗, it is hard to compute α,β within a polynomial time.According to this, we can design a lightweight public key algorithm for the user and the server:S selects a larger prime p, a generator g of cyclic group Zp∗, and a secret key x and computes the public key Y=gx mod p. Then if Ui selects a random number r1, it computes M1=gr1 mod p and M2=Yr1 mod p and sends M1 to S. S can compute M2 as M1x mod p. Here, M1=Tran_Vau and M2=Pub_Vau; even the adversary intercepts the M1; he/she still cannot compute the M2. So then S only needs to prove that it knows about the M2. Furthermore, to Ui, M1=Pub_key(r) and M2=Pub_key(r,Y); to S, M2=Pub_key(x,Tran_Vau); it also follows the principles mentioned above. In short, we improve Yeh’s scheme as shown in Figure 5.Figure 5
Improving Yeh et al.’s scheme to resist Attack II.In the improved scheme,Veri_Vau=C=f(Mid_Vau, Pub_Vau); even the adversary guesses the PWi and IDi to be PWi∗ and IDi∗, while without Pub_Vau, he/she cannot find a verification to check the correctness of the guessed value and thus fails to perform Attack II. It should be noted that we only improve Yeh’s scheme to be secure to Attack II, and the reference model can only be applied to resisting Attack II.It is generally accepted that public key algorithm is necessary for resisting offline dictionary attack, while, according to our analysis, the offline dictionary attack here should be specific to Attack II, and Attack I is not included in it: the public key algorithm consists of a private key and a public key. In Attack II, the vulnerability takes place in the authentication between the server and the smart card. So the public key algorithm acts on the server and the smart card. Usually the server takes the responsibility to keep private keyx, while, in Attack I, the vulnerability takes place in the authentication between the user and the smart card. But it makes no sense to both of them to own such private key for two reasons at least:(i)
To the users: he always uses the password as the unique parameter to get authenticated, and the private key plays the same role as the password. Moreover, the private key is too long for the user to remember or preserve.(ii)
Smart card: as we have stated before, the parameters in the smart card can be easily obtained by an adversary.


## 7. Conclusion

In this paper, we demonstrated that the schemes of Yeh, Kang et al., and Kaul et al. all suffer from various attacks, such as offline dictionary attack and impersonation attack. Furthermore, we showed that offline dictionary attack is the original reason of many other attacks. Remarkably, we divide offline dictionary attacks into two categories: (1) the ones using the verification from smart cards and (2) the ones using the verification from the open channel. The solution to the first type involves the trade-off between the security and effectiveness, or “a fuzzy verifier” + “honeywords” as suggested in [11]. While the solution to the second is using a public key algorithm as advised by Ma et al. [36], this solution is not applicable to the first type. Furthermore, even many schemes using a public key algorithm still suffer from Attack II. The original reason is incorrectly deploying the public key algorithms. Thus, we proposed a reference model to guide the protocol designers to deploy the public key algorithms correctly. Our reference model is not the only way to deal with such problem, but it really is one of them. We hope that this work provides new insights into future research.



---

*Source: 1619741-2017-07-17.xml*