# A Secure and Anonymous Two-Factor Authentication Protocol in Multiserver Environment

Authors: Chenyu Wang; Guoai Xu; Wenting Li
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the great development of network technology, the multiserver system gets widely used in providing various of services. And the two-factor authentication protocols in multiserver system attract more and more attention. Recently, there are two new schemes for multiserver environment which claimed to be secure against the known attacks. However, after a scrutinization of these two schemes, we found that(1) their description of the adversary’s abilities is inaccurate; (2) their schemes suffer from many attacks. Thus,firstly, we corrected their description on the adversary capacities to introduce a widely accepted adversary modeland then summarized fourteen security requirements of multiserver based on the works of pioneer contributors.Secondly, we revealed that one of the two schemes fails to preserve forward secrecy and user anonymity and cannot resist stolen-verifier attack and off-line dictionary attack and so forth and also demonstrated that another scheme fails to preserve forward secrecy and user anonymity and is not secure to insider attack and off-line dictionary attack, and so forth.Finally, we designed an enhanced scheme to overcome these identified weaknesses, proved its security via BAN logic and heuristic analysis, and then compared it with other relevant schemes. The comparison results showed the superiority of our scheme.


---

## Body

## 1. Introduction

The development of network technology has greatly changed the way people live and work. Internet brings our society into an information age, and it has become an indispensable element of people’s life. Nowadays, with the maturity and rapid development of Internet technology, people’s schedule was more convenient and efficient due to the increasing online services. However, the openness and virtuality of the Internet have resulted in the fact that the network environment became untrusted which is accompanied by the information security and privacy issues. In recent years, we have heard too many events about user privacy information being leaked; for example, in 2015, about 10 G user data of Ashley Madison (the world’s largest extramarital affairs web site who offers dating services for married people) has been exposed. In this event, many celebrities were exposed, and the whole society was surrounded by fear; Anthem lost 80 million user datasets including user name, birthday, social insurance code, phone number, email, and so on, which is the largest medical institution user data exposed event in the United States. For a more secure network environment, the cryptographic approach is one of the key technologies, among which a necessary part is to provide authentication and key agreement for remote entities. And this mechanism is called user authentication.Usually, a well-defined authentication scheme should promise that only the legitimate user can enjoy the service, and the corresponding server is exactly real and legitimate. At the beginning, the passwords, with its facility and accessibility, have been used widely in authentication process. While it has been found that the password-based single-server authentication protocols always risk in stolen-verifier attack, because the server has to maintain a password related table. Thus, the smart card, as a second security factor, gets widely used [1–5].Furthermore, the increasing demands in network life greatly prompted that service providers extend the traditional single-server environment into a multiserver one to offer more kinds of services and improve their quality of services. Then multiserver system comes into being. However, the single-server-based authentication scheme is not suitable to multiserver system any more: the single-server-based scheme asks a user to register on each server one by one, and so the users have to remember many different identities and passwords, which is bound to bring unnecessary trouble for the users; in order to remember a mountain of identities and passwords, a user is more likely to choose the same identity and password; thus, the information disclosure emerged in multiserver system.To solve this problem, scholars put forward the multiserver environment authentication mechanism whose goals are that the user only needs to register to the registration center, and then he/she can login to the corresponding different application servers using the same account. This ideal is also of high reference value to cloud computing, Internet of things, car networking, and so forth. In 2001, Li et al. [6] proposed a neural-networks-based scheme for multisever system: its communication and computation costs are very high and, furthermore, the users have to store large amount of data. In 2003, Lin et al. [7] proposed a new scheme with lower costs, which was pointed out to be inefficient by Juang [8]. Thus he recommended a symmetric-cryptography-based protocol which resolved the problem of reregistration with high computational efficiency. Unfortunately, Chang and Lee [9] revealed that Juang’s scheme suffers from off-line password guessing attack, and the users cannot change their password; therefore, they proposed a new improved scheme. In 2004, Tsaur et al. [10] demonstrated that Chang and Lee’s scheme is vulnerable to insider attack and forgery attack, so they designed a RSA-based scheme. Once again, their scheme was noted to be subjected to impersonation attack [11].Those schemes above have a common problem: the user identity is static; thus they usually fail to achieve perfect user anonymity. To remedy this problem, Liao and Wang [12] in 2009 proposed a dynamic-identity-based protocol, while later it was proved to be insecure to impersonation attack and insider attack by Hsiang and Shih [13]. Unfortunately, Sood et al. [14] revealed that Hsiang and Shih’s scheme is not as secure as they claimed.


### 1.1. Contributions

Recently, Li et al. [15] and Sood [16] proposed a user authentication scheme in multiserver networks; they both claimed to be secure to various known attacks. However, in 2016, Amin [17] demonstrated the two schemes cannot resist off-line guessing attack, insider attack, and so on, therefore providing a new enhanced protocol overcoming those weaknesses. In the same year, Maitra et al. [18] reexamined Leu and Hsieh’s scheme [19] and Li et al.’s scheme [20] and found that their schemes were subject to many security threats; thus they also put forward a new scheme using symmetric cryptosystem and aiming to resist various attacks with some desire attributes. Unfortunately, according to our analysis, their schemes, once again, fail to be a sound authentication protocol. To point out the common issues in the user authentication scheme, we use these two advanced and representative schemes as study case to show the possible weakness in most schemes. Then, based on the analysis, we propose an improved scheme trying to show a possible way to overcome those weakness. In a word, our contributions can be summarized as follows:(1)
We revealed the description of adversary’s abilities in many schemes are inaccurate and thus redescribed a widely accepted and practical adversary model.(2)
We summarized fourteen security requirements of multiserver environment based on the works of pioneer contributors.(3)
We demonstrate that Maitra et al.’s scheme [18] fails to preserve forward secrecy and user anonymity and cannot resist stolen-verifier attack and off-line dictionary attack and so on; Amin’s scheme [17] fails to preserve forward secrecy and user anonymity and is not secure to insider attack and off-line dictionary attack and so on.(4)
We propose an enhanced scheme with user anonymity and proved its security via BAN logic and heuristic analysis and, furthermore, compared it with other relevant schemes. The comparison result shows that our scheme, though increasing the costs slightly, achieves all the fourteen security requirements, so it is more suitable to multiserver.


### 1.2. Construction of the Paper

In Section2, we described the preliminaries and then analyzed Maitra et al.’s scheme [18] and Amin’s scheme [17] in Sections 3 and 4, respectively. And we proposed a new scheme in Section 5, proved its security in Section 6, and analyzed its performance in Section 7. The conclusion was given in Section 8.


## 1.1. Contributions

Recently, Li et al. [15] and Sood [16] proposed a user authentication scheme in multiserver networks; they both claimed to be secure to various known attacks. However, in 2016, Amin [17] demonstrated the two schemes cannot resist off-line guessing attack, insider attack, and so on, therefore providing a new enhanced protocol overcoming those weaknesses. In the same year, Maitra et al. [18] reexamined Leu and Hsieh’s scheme [19] and Li et al.’s scheme [20] and found that their schemes were subject to many security threats; thus they also put forward a new scheme using symmetric cryptosystem and aiming to resist various attacks with some desire attributes. Unfortunately, according to our analysis, their schemes, once again, fail to be a sound authentication protocol. To point out the common issues in the user authentication scheme, we use these two advanced and representative schemes as study case to show the possible weakness in most schemes. Then, based on the analysis, we propose an improved scheme trying to show a possible way to overcome those weakness. In a word, our contributions can be summarized as follows:(1)
We revealed the description of adversary’s abilities in many schemes are inaccurate and thus redescribed a widely accepted and practical adversary model.(2)
We summarized fourteen security requirements of multiserver environment based on the works of pioneer contributors.(3)
We demonstrate that Maitra et al.’s scheme [18] fails to preserve forward secrecy and user anonymity and cannot resist stolen-verifier attack and off-line dictionary attack and so on; Amin’s scheme [17] fails to preserve forward secrecy and user anonymity and is not secure to insider attack and off-line dictionary attack and so on.(4)
We propose an enhanced scheme with user anonymity and proved its security via BAN logic and heuristic analysis and, furthermore, compared it with other relevant schemes. The comparison result shows that our scheme, though increasing the costs slightly, achieves all the fourteen security requirements, so it is more suitable to multiserver.


## 1.2. Construction of the Paper

In Section2, we described the preliminaries and then analyzed Maitra et al.’s scheme [18] and Amin’s scheme [17] in Sections 3 and 4, respectively. And we proposed a new scheme in Section 5, proved its security in Section 6, and analyzed its performance in Section 7. The conclusion was given in Section 8.


## 2. Preliminaries

For better understanding of the two-factor authentication scheme in multiserver environment, it is necessary to describe the computational problems, communication model, adversary model, and security requirements firstly.


### 2.1. Computational Problems

(1)
Discrete logarithm problem: given (g,gα mod p), it is hard to compute α (α∈Zp∗) within the polynomial time, where g is the generator of cyclic group Zp∗. (2)
Computational Diffie-Hellman problem: given (gβ,gα mod p), it is hard to compute gαβ within the polynomial time, where α,β∈Zp∗.


### 2.2. Communication Model

A multiserver environment (shown in Figure2) refers to the fact that a service provider can offer a variety of services for the users, for example, Google, who not only provides mail service but also provides news, video, and other services. To a user, he/she only needs to have one account of Google and then can enjoy all the services provided by it. And the way to implement this function is what we know as the user authentication protocol in a multiserver environment. Usually, people may be more familiar with distributed systems (shown in Figure 1) where each service corresponds to a server, and it only involves two participants: a set of users and a single server. However, typically, a two-factor authentication protocol in multiserver environment involves three participants: a set of users, a set of servers, and a register center. Among these participants, only the register center is trusted; it may store some sensitive information in the database. Furthermore, the authentication process usually consists of four basic phases: registration, login, authentication, and password change phase. The registration phase includes two parts: user registration phase, where a user submits his/her personal information, and then the register center issues the user a smart card containing security messages; server registration phase, where the servers send their identities to the register center to get a secret key. In login phase, the user selects a server to offer service and sends a login request to the server. Then in authentication phase, the user and the server need to verify the legitimacy of each other. Furthermore, according to whether the registration center is involved in the authentication process, the multiserver authentication protocols can be divided into two categories: the registration center involved one; the registration center did not involve one. Among the four phases, only the registration phase is carried out via a secure channel and the others are all conducted via an insecure channel. And the notations used in the protocols are shown in Table 1.Table 1
Notations and abbreviations
Symbol Description Ui ith user Sj jth remote server RC The register center A The adversary x The secret key ofS IDi Identity ofUi PWi Password ofUi SIDj Identity ofSj Skeyj The shared secret key betweenRC and Sj ⊕ Bitwise XOR operation ∥ Concatenation operation h(⋅) One-way hash function → A common channel ⇒ A secure channelFigure 1
The architecture of the distributed system.Figure 2
The architecture of the multiserver system.


### 2.3. Adversary Model

In fact, both Amin [17] and Maitra et al. [18] described the capacities of the adversaries inaccurately. In their adversary model, there are three obvious flaws which are overlooked but critical in authentication protocol.The first one is about “whether an adversary can exhaust the password space and identity space to conduct off-line dictionary attack simultaneously?”. Many schemes [17, 18, 20, 21] think that A can exhaust either the password space or the identity space, but not simultaneously. While it is really not practical, Wang et al. [22] for the first time revealed that user-chosen passwords follow the Zipf-like distribution, a distribution far from uniform. This indicates that user-chosen passwords are prone to static guessing attacks. Furthermore, in [23] Section 4.2, we can see that even the adversary guesses the password and identity simultaneously and the whole attack can be finished within limited time. Therefore, the adversary can exhaust the password and identity space simultaneously, and many scholars follow this principle [2, 24–27].The second one is about “whether an adversary can easily get a user’s identity once owning the user’s smart card?”; the answer is also positive. As Wang et al. [28] explained, on the one hand, the identity usually is a static short string with limited space. And the same user is accustomed to using the same identity even for different service providers. So it is of high possibility that an adversary learns the identity from other common service providers; on the other hand, the users do not regard identity as a secret parameter, and, for easy remembrance, they will even write the identity on the card directly. So when cryptanalyzing a scheme, it is more practical to assume that the identity is an open parameter.The third one is about “whether an adversary can get the long term secret key?”. Maitra et al.’s work [18] just ignored this problem and supposed that the adversary can never learn about the long term secret key; as, for Amin’s work, he assumed that a valid user can always know the secret information and may provide it to the adversary, while, in fact, these two statements are both not accurate enough. A widely accepted assumption is that an adversary can know the long term secret key only when evaluating the forward secrecy [28–32].Besides, it is widely accepted that an adversary has the full control of the channel; that is,A can intercept, delete, modify, resend, and reroute the messages in an open channel [33–35]. Furthermore, A may also learn users’ passwords via a malicious terminal or extract the parameters from the smart card by side-channel attack, but cannot achieve both [2, 27, 36]. We summarize the capacities of the adversary A in Table 2.Table 2
The capacities of the adversary.
(1) A can intercept, modify, delete, and resend the messages between the users and the servers over the open channel.  (2) A can enumerate all the items in the password space and identity space simultaneously.  (3) When cryptanalyzing a scheme,A can know the identity of Ui.  (4) A knows the identity of Sj.  (5) A can learn the password of Ui by a malicious card reader, or extract the parameters from the smart, but cannot achieve both.  (6) When evaluating forward secrecy,A knows the long term secret key of the register center.


### 2.4. Security Requirements

According to the user authentication protocols in multiserver environment [34, 37, 38] and some works on analysis of security requirements in user authentication scheme [2, 4, 28], we describe the security requirements in a two-factor authentication scheme of multiserver in Table 3.Table 3
Security requirements.
S1: mutual authentication R C, Sj and Ui should authenticate each other to ensure their eligibility.  S2: user anonymity A can neither compute the identity of Ui nor link the message flows to Ui.  S3: key agreement S j and Ui should share a session key for further communication.  S4: forward secrecy Even gets the long term secret keyx, A still cannot compute the session key.  S5: password friendly The userUi can select and change his password locally.  S6: sound repairability U i can revoke the breached smart card and re-register with the same identity.  S7: no stolen-verifier attack EvenRC stores a verifier table, A gains no benefits from it.  S8: no insider attack The participants with the message their know cannot conduct an attack.  S9: no dictionary attack With all the abilities in Table2, A still cannot guess the IDi and PWi.  S10: no replay attack A cannot replay the eavesdropped messages to conduct an attack.  S11: no parallel session attack A may construct multi-session simultaneously, but A gains no benefits from it.  S12: no desynchronization attack On the one hand, the scheme should not suffer from desynchronization attackOn the other hand, it needs not to synchronize the clock.  S13: no impersonation attack A cannot impersonate the user or any other participants. It needs to note that (1) A here cannot breach the smart card, while in dictionary attack A has that capability; (2) A can be a legitimate user or server.  S14: no known key attack Knowing the current session keys,A cannot compute other session key in the future or in the past.


## 2.1. Computational Problems

(1)
Discrete logarithm problem: given (g,gα mod p), it is hard to compute α (α∈Zp∗) within the polynomial time, where g is the generator of cyclic group Zp∗. (2)
Computational Diffie-Hellman problem: given (gβ,gα mod p), it is hard to compute gαβ within the polynomial time, where α,β∈Zp∗.


## 2.2. Communication Model

A multiserver environment (shown in Figure2) refers to the fact that a service provider can offer a variety of services for the users, for example, Google, who not only provides mail service but also provides news, video, and other services. To a user, he/she only needs to have one account of Google and then can enjoy all the services provided by it. And the way to implement this function is what we know as the user authentication protocol in a multiserver environment. Usually, people may be more familiar with distributed systems (shown in Figure 1) where each service corresponds to a server, and it only involves two participants: a set of users and a single server. However, typically, a two-factor authentication protocol in multiserver environment involves three participants: a set of users, a set of servers, and a register center. Among these participants, only the register center is trusted; it may store some sensitive information in the database. Furthermore, the authentication process usually consists of four basic phases: registration, login, authentication, and password change phase. The registration phase includes two parts: user registration phase, where a user submits his/her personal information, and then the register center issues the user a smart card containing security messages; server registration phase, where the servers send their identities to the register center to get a secret key. In login phase, the user selects a server to offer service and sends a login request to the server. Then in authentication phase, the user and the server need to verify the legitimacy of each other. Furthermore, according to whether the registration center is involved in the authentication process, the multiserver authentication protocols can be divided into two categories: the registration center involved one; the registration center did not involve one. Among the four phases, only the registration phase is carried out via a secure channel and the others are all conducted via an insecure channel. And the notations used in the protocols are shown in Table 1.Table 1
Notations and abbreviations
Symbol Description Ui ith user Sj jth remote server RC The register center A The adversary x The secret key ofS IDi Identity ofUi PWi Password ofUi SIDj Identity ofSj Skeyj The shared secret key betweenRC and Sj ⊕ Bitwise XOR operation ∥ Concatenation operation h(⋅) One-way hash function → A common channel ⇒ A secure channelFigure 1
The architecture of the distributed system.Figure 2
The architecture of the multiserver system.


## 2.3. Adversary Model

In fact, both Amin [17] and Maitra et al. [18] described the capacities of the adversaries inaccurately. In their adversary model, there are three obvious flaws which are overlooked but critical in authentication protocol.The first one is about “whether an adversary can exhaust the password space and identity space to conduct off-line dictionary attack simultaneously?”. Many schemes [17, 18, 20, 21] think that A can exhaust either the password space or the identity space, but not simultaneously. While it is really not practical, Wang et al. [22] for the first time revealed that user-chosen passwords follow the Zipf-like distribution, a distribution far from uniform. This indicates that user-chosen passwords are prone to static guessing attacks. Furthermore, in [23] Section 4.2, we can see that even the adversary guesses the password and identity simultaneously and the whole attack can be finished within limited time. Therefore, the adversary can exhaust the password and identity space simultaneously, and many scholars follow this principle [2, 24–27].The second one is about “whether an adversary can easily get a user’s identity once owning the user’s smart card?”; the answer is also positive. As Wang et al. [28] explained, on the one hand, the identity usually is a static short string with limited space. And the same user is accustomed to using the same identity even for different service providers. So it is of high possibility that an adversary learns the identity from other common service providers; on the other hand, the users do not regard identity as a secret parameter, and, for easy remembrance, they will even write the identity on the card directly. So when cryptanalyzing a scheme, it is more practical to assume that the identity is an open parameter.The third one is about “whether an adversary can get the long term secret key?”. Maitra et al.’s work [18] just ignored this problem and supposed that the adversary can never learn about the long term secret key; as, for Amin’s work, he assumed that a valid user can always know the secret information and may provide it to the adversary, while, in fact, these two statements are both not accurate enough. A widely accepted assumption is that an adversary can know the long term secret key only when evaluating the forward secrecy [28–32].Besides, it is widely accepted that an adversary has the full control of the channel; that is,A can intercept, delete, modify, resend, and reroute the messages in an open channel [33–35]. Furthermore, A may also learn users’ passwords via a malicious terminal or extract the parameters from the smart card by side-channel attack, but cannot achieve both [2, 27, 36]. We summarize the capacities of the adversary A in Table 2.Table 2
The capacities of the adversary.
(1) A can intercept, modify, delete, and resend the messages between the users and the servers over the open channel.  (2) A can enumerate all the items in the password space and identity space simultaneously.  (3) When cryptanalyzing a scheme,A can know the identity of Ui.  (4) A knows the identity of Sj.  (5) A can learn the password of Ui by a malicious card reader, or extract the parameters from the smart, but cannot achieve both.  (6) When evaluating forward secrecy,A knows the long term secret key of the register center.


## 2.4. Security Requirements

According to the user authentication protocols in multiserver environment [34, 37, 38] and some works on analysis of security requirements in user authentication scheme [2, 4, 28], we describe the security requirements in a two-factor authentication scheme of multiserver in Table 3.Table 3
Security requirements.
S1: mutual authentication R C, Sj and Ui should authenticate each other to ensure their eligibility.  S2: user anonymity A can neither compute the identity of Ui nor link the message flows to Ui.  S3: key agreement S j and Ui should share a session key for further communication.  S4: forward secrecy Even gets the long term secret keyx, A still cannot compute the session key.  S5: password friendly The userUi can select and change his password locally.  S6: sound repairability U i can revoke the breached smart card and re-register with the same identity.  S7: no stolen-verifier attack EvenRC stores a verifier table, A gains no benefits from it.  S8: no insider attack The participants with the message their know cannot conduct an attack.  S9: no dictionary attack With all the abilities in Table2, A still cannot guess the IDi and PWi.  S10: no replay attack A cannot replay the eavesdropped messages to conduct an attack.  S11: no parallel session attack A may construct multi-session simultaneously, but A gains no benefits from it.  S12: no desynchronization attack On the one hand, the scheme should not suffer from desynchronization attackOn the other hand, it needs not to synchronize the clock.  S13: no impersonation attack A cannot impersonate the user or any other participants. It needs to note that (1) A here cannot breach the smart card, while in dictionary attack A has that capability; (2) A can be a legitimate user or server.  S14: no known key attack Knowing the current session keys,A cannot compute other session key in the future or in the past.


## 3. Review of the Scheme of Maitra et al.

In 2016, Maitra et al. [18] criticized two recent protocols, namely, Leu and Hsieh’s scheme [19] and Li et al.’s scheme [20], and pointed out that the two schemes are vulnerable to various attacks, such as forgery attack, and password guessing attack; therefore, they designed a new enhanced scheme being confident to resist a variety of known attacks and with some attractive attributes such as freely changing password and identity. However, when we reexamined their scheme, we found some serious security threats of the scheme and revealed that the scheme is not secure against verifier-stolen attack and off-line password guessing attack and also fails to provide forward secrecy and user anonymity.


### 3.1. The Scheme of Maitra et al.

In this section, we review Maitra et al.’s scheme [18] briefly, and as password change phase and identity change phase have little relevance to our work, we omit them.


#### 3.1.1. Initialization Phase

R C selects a secret long key x and a symmetric key encryption/decryption Enc/Dec algorithm (AES); then there is a hash function h(∗): {0,1}∗→{0,1}n.


#### 3.1.2. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: {Skeyj,SIDj}. RC first checks the availability of SIDj, then calculates Skeyj=h(SIDj∥x), and adds {SIDj,keysj} into the Server-list, where keysj=Skeyj⊕x, finally sends {Skeyj,SIDj} to Sj; otherwise, RC rejects the server Sj’s request.Step  3. Sj stores Skeyj.


#### 3.1.3. User Registration Phase

Step  1. Ui⇒RC: {DIDi,PWRi}. Ui selects PWi, IDi, and a random number bi, computes DIDi=h(IDi∥bi), PWRi=h(PWi∥bi), and then sends {DIDi,PWRi} to RC.Step  2. RC⇒Ui: a smart card with {Ci,Di,Ei}. RC tests DIDi by the User-list, chooses a random number yi, calculates Ci=h(x∥yi)⊕DIDi⊕PWRi, Ei=h(h(x∥yi)∥DIDi∥PWRi), and Di=Encx[DIDi∥PWRi], then stores DIDi into the User-list, and issues Ui a smart card with {Ci,Di,Ei}.Step  3. Ui computes b~i=bi⊕h(IDi∥PWi) and stores it.


#### 3.1.4. Login and Authentication Phase

Step  1. Ui→Sj: LoginUi. Ui inputs IDi and PWi. The card computes bi′=b~i⊕h(IDi∥PWi), DIDi′=h(IDi⊕bi′), PWRi′=h(PWi∥bi′), hx∥yi′=Ci⊕DIDi′⊕PWRi′, and Ei′=h(hx∥yi′∥DIDi′∥PWRi′). If Ei′≠Ei, end the session. Otherwise, the card chooses a random number ri and timestamp Ti1, computes Gi=ri⊕h(DIDi′∥PWRi′∥Ti1), Fij=h(DIDi′∥PWRi′∥ri∥Ti1∥SIDj), and sends LoginUi={Gi,Fij,Di,Fi,SIDj,Ti1} to Sj.Step  2. Sj→RC: LoginSj. Sj first checks SIDj and the freshness of Ti1, then computes Hji=EncSkeyj[rj∥LoginUi∥Tj1∥SIDj], and sends LoginSj={Hji,SIDj,Tj1} to RC.Step  3. RC→Sj: {Rrcij}. RC first tests Tj1 and SIDj, catches corresponding Skeyj (Skeyj=keySj⊕x) from the Server-list, decrypts Hji with Skeyj, and then checks Tj1 ?= Tj1∗ and SIDj ?= SIDj∗ ?= SIDj∗∗. If one of the equations does not hold, end the session. Otherwise, RC computes (DIDi∗∥PWRi∗)=Decx[Di∗], ri=Gi∗⊕h(DIDi∗∥PWRi∗∥Ti1∗) and compares h(DIDi∗∥PWRi∗∥Ti1∗∥SIDj) with Fij∗. If they are not equal, end the session. Otherwise RC computes Prcij=h(x∥rrc∥rj∥ri), Krcij=h(DIDi∥ri∥PWRi)⊕Prcij, Lrcij=Prcij⊕rj, Nrcij=h(rj∥SIDj∥Prcij), Rrcij=EncSkeyj[Krcij∥Lrcij∥Nrcij∥Trc] and finally answers Sj with {Rrcij}.Step  4. Sj→Ui: {Qji,Wji,Krcij†,Tj2}. Sj computes (Krcij†∥Lrcij†∥Nrcij†∥Trc†)=DecSkeyj[Rrcij], checks Trc†, then computes Prcij†=Lrcij†⊕rj. If h(rj∥SIDj∥Prcij†)==Nrcij†, Sj computes [h(DIDi∥ri∥PWRi)]†=Prcij†⊕Krcij†, Wji=nj⊕[h(DIDi∥ri∥PWRi)]†, Qji=h([h(DIDi∥ri∥PWRi)]†∥nj∥Tj2), where nj is a random number, and then sends Ui with {Qji,Wji,Krcij†,Tj2}. Otherwise, exit.Step  5. Ui→Sj: {Vi,Ti2}. The smart card first tests Tj2 and then computes nj′=Wji⊕h(DIDi∥ri∥PWRi), Qji′=h(h(DIDi∥ri∥PWRi)∥nj′∥Tj2). If Qji′==Qji, the smart card computes Prcij′=Krcij†⊕h(DIDi∥ri∥PWRi), the session key SKi=h(Prcij′∥nj′), Vi=h(SKi∥Ti2) and sends {Vi,Ti2} to Sj. Otherwise, end.Step  6. After checking the freshness of Ti2, Sj computes SKj=h(Prcij†∥nj); Vi′=h(SKj∥Ti2), compares Vi′ with the received Vi. If they are equal, the authentication is finished successfully; both Ui and Sj accept the session key SKi(=SKj).


### 3.2. Cryptanalysis of Maitra et al.’s Scheme

It has to admit that Maitra et al.’s scheme has many attractive advantages, such as providing password and identity change phase. Furthermore, the way to protect the real identity and password is somewhat illuminating. While it is regrettable that this scheme is still not secure against various attacks, including stolen-verifier attack, off-line password guessing attack, and no forward secrecy and user anonymity.


#### 3.2.1. Off-Line Dictionary Attack

In Section2.3, we explain that A can guess the identity and password simultaneously and also can learn the identity. No matter whether A knows about the identity, he/she can carry out the off-line dictionary attack. Here, we take A not knowing the identity as an example. Suppose A steals Ui’s smart card and extracts {Ci,Ei,b~i} from the smart card; then he can perform off-line dictionary attack as the following steps.Step  1. Guess the value of PWi to be PWi∗ from the password dictionary space Dpw, the value of IDi to be IDi∗ from the identity dictionary space Did.Step  2. Compute bi′=b~i⊕h(IDi∗∥PWi∗).Step  3. Compute DIDi′=h(IDi∗⊕bi′).Step  4. Compute PWRi′=h(PWi∗∥bi′).Step  5. Compute hx∥yi′=Ci⊕DIDi′⊕PWRi′.Step  6. Compute Ei′=h(hx∥yi′∥DIDi′∥PWRi′).Step  7. Verify the correctness of PWi and IDi by checking if Ei′=?Ei.Step  8. Repeat Steps 1~6 until the correct value of PWi and IDi are found.WithPWi and IDi, the adversary A can impersonate the user Ui to enjoy the service.The time complexity of the above attack isO(Dpw∗Did∗4TH), where TH is the running time for hash computation; Dpw and Did denote the number of passwords in Dpw and the number of identities in Did, respectively. Dpw is very limited due to the Zipf’s law in passwords [22]; Did is also very limited as generally Did<Dpw. So the attack can be finished in the polynomial time.


#### 3.2.2. Forward Secrecy

Suppose an adversaryA somehow learns the long term secret key x and eavesdrops the message in the open channel to get Hji, Rrcij, Wji; then he/she can compute the session key between Sj and Ui as follows.Step  1. Compute Sj’s secret key Skeyj=h(SIDj∥x), where SIDj is an open parameter.Step  2. Decrypt Hji with Skeyj, and get rj, LoginUi, where LoginUi={Gi,Fij,Di,Fi,SIDj,Ti1} and Hji is from the open channel.Step  3. Decrypt Di with x to get DIDi and PWRi, where Di is from the open channel.Step  4. Decrypt Rrcij with Skeyj to get Lrcij, where Rrcij is from the open channel.Step  5. Compute Prcij=Lrcij⊕rj.Step  6. Compute nj=Wji⊕h(DIDi∥ri∥PWRi), where Wji is from the open channel.Step  7. Compute the session key SKi=h(Prcij∥nj).The time complexity of the above attack isO(3TH+3TS), where TS is the running time of symmetric encryption operation. According to the TABLE VI. in [2], the attack can be finished within seconds. So the above attack can be completed in the polynomial time.


#### 3.2.3. Verifier-Stolen Attack

As we mentioned before, only the register center is trusted, the user and the server are both likely to be an adversaryA to conduct an attack. Consider such a condition where the legitimate server Sj somehow gets the verifier table in the database of register center. Then this adversary A can also compute x and, furthermore, damage the whole system as follows.Step  1. Compute x=keysj⊕Skeyj, where keySj is from the list {SIDj,keyj} of the verifier table.Step  2. Compute any other server Sk’s private secret key Skeyk=KeySk⊕x, where KeySk is from the list {SIDk,keyk} of the verifier table.The operations in the above procedure are some lightweight operation and the procedure is very simple.Withx and the verifier table, A has the same capacity with the register center. Thus A can impersonate RC to the user and the other server. What is more, with x, once A intercepts the message Hji or Hki (k≠j), A can compute any user’s PWRi and DIDi as the way RC do. Furthermore, with Skeyk, A has the same capacity with other server, so he/she can also impersonate other servers to RC and the users. Therefore, the security of the whole system is compromised.


#### 3.2.4. User Anonymity

In this era of information explosion, user privacy protection is extremely important to the individuals. And user anonymity, as a pivotal way to protect the user privacy, contains two requirements: do not expose the identity directly; keep the identity untraceable. Once user anonymity cannot get guaranteed, the adversary may link the different communication in open channel to the same user and thus learns his preference and personal information for marketing purpose or other horrible purpose.In Maitra et al.’s scheme [18], there is a static value Di in the open channel. More specifically, to the same user, Di is unchanged (Di=Encx[DIDi∥PWRi]) unless Ui changes his identity and password. While the frequency of changing the identity or the password is so low, which means every time Ui initiates an access request to any servers, the same Di will be transmitted in the open channel in most occasions. Therefore, an adversary A can link the access request to the same user from the huge amounts of data to learn the user’s habits and preferences. So this scheme violates user untraceability.More specifically, an adversary can eavesdrop the open channel and then get the following message:(1)LoginUi1=Gi1,Fij1,Di1,Fi1,SIDj,Ti11,LoginUm1=Gm1,Fmj1,Dm1,Fm1,SIDj,Tm11,LoginUg1=Gg1,Fgj1,Dg1,Fg1,SIDj,Tg11,LoginUi2=Gi2,Fij2,Di2,Fi2,SIDk,Ti12,LoginUm2=Gm2,Fmj2,Dm2,Fm2,SIDk,Tm12,LoginUg2=Gg2,Fgj2,Dg2,Fg2,SIDk,Tg12,⋮LoginUin=Gin,Fijn,Din,Fin,SIDm,Ti1n,LoginUmn=Gmn,Fmjn,Dmn,Fmn,SIDm,Tm1n,LoginUgn=Ggn,Fgjn,Dgn,Fgn,SIDm,Tg1n.As Di1==Di2==Din==Di== a constant value, the adversary knows that among those messages, LoginUi1, LoginUi2, and LoginUi3 were sent by the same user; this user usually accesses Sj, Sk, and Sm at times Ti11, Ti12, and Ti1n, respectively. Thus the user untraceability is violated. Furthermore, once the adversary acquires IDi and PWi as we showed in Section 3.2.1, he can compute Di and thus traces the specific user Ui and learns more about the victim’s habits.


## 3.1. The Scheme of Maitra et al.

In this section, we review Maitra et al.’s scheme [18] briefly, and as password change phase and identity change phase have little relevance to our work, we omit them.


### 3.1.1. Initialization Phase

R C selects a secret long key x and a symmetric key encryption/decryption Enc/Dec algorithm (AES); then there is a hash function h(∗): {0,1}∗→{0,1}n.


### 3.1.2. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: {Skeyj,SIDj}. RC first checks the availability of SIDj, then calculates Skeyj=h(SIDj∥x), and adds {SIDj,keysj} into the Server-list, where keysj=Skeyj⊕x, finally sends {Skeyj,SIDj} to Sj; otherwise, RC rejects the server Sj’s request.Step  3. Sj stores Skeyj.


### 3.1.3. User Registration Phase

Step  1. Ui⇒RC: {DIDi,PWRi}. Ui selects PWi, IDi, and a random number bi, computes DIDi=h(IDi∥bi), PWRi=h(PWi∥bi), and then sends {DIDi,PWRi} to RC.Step  2. RC⇒Ui: a smart card with {Ci,Di,Ei}. RC tests DIDi by the User-list, chooses a random number yi, calculates Ci=h(x∥yi)⊕DIDi⊕PWRi, Ei=h(h(x∥yi)∥DIDi∥PWRi), and Di=Encx[DIDi∥PWRi], then stores DIDi into the User-list, and issues Ui a smart card with {Ci,Di,Ei}.Step  3. Ui computes b~i=bi⊕h(IDi∥PWi) and stores it.


### 3.1.4. Login and Authentication Phase

Step  1. Ui→Sj: LoginUi. Ui inputs IDi and PWi. The card computes bi′=b~i⊕h(IDi∥PWi), DIDi′=h(IDi⊕bi′), PWRi′=h(PWi∥bi′), hx∥yi′=Ci⊕DIDi′⊕PWRi′, and Ei′=h(hx∥yi′∥DIDi′∥PWRi′). If Ei′≠Ei, end the session. Otherwise, the card chooses a random number ri and timestamp Ti1, computes Gi=ri⊕h(DIDi′∥PWRi′∥Ti1), Fij=h(DIDi′∥PWRi′∥ri∥Ti1∥SIDj), and sends LoginUi={Gi,Fij,Di,Fi,SIDj,Ti1} to Sj.Step  2. Sj→RC: LoginSj. Sj first checks SIDj and the freshness of Ti1, then computes Hji=EncSkeyj[rj∥LoginUi∥Tj1∥SIDj], and sends LoginSj={Hji,SIDj,Tj1} to RC.Step  3. RC→Sj: {Rrcij}. RC first tests Tj1 and SIDj, catches corresponding Skeyj (Skeyj=keySj⊕x) from the Server-list, decrypts Hji with Skeyj, and then checks Tj1 ?= Tj1∗ and SIDj ?= SIDj∗ ?= SIDj∗∗. If one of the equations does not hold, end the session. Otherwise, RC computes (DIDi∗∥PWRi∗)=Decx[Di∗], ri=Gi∗⊕h(DIDi∗∥PWRi∗∥Ti1∗) and compares h(DIDi∗∥PWRi∗∥Ti1∗∥SIDj) with Fij∗. If they are not equal, end the session. Otherwise RC computes Prcij=h(x∥rrc∥rj∥ri), Krcij=h(DIDi∥ri∥PWRi)⊕Prcij, Lrcij=Prcij⊕rj, Nrcij=h(rj∥SIDj∥Prcij), Rrcij=EncSkeyj[Krcij∥Lrcij∥Nrcij∥Trc] and finally answers Sj with {Rrcij}.Step  4. Sj→Ui: {Qji,Wji,Krcij†,Tj2}. Sj computes (Krcij†∥Lrcij†∥Nrcij†∥Trc†)=DecSkeyj[Rrcij], checks Trc†, then computes Prcij†=Lrcij†⊕rj. If h(rj∥SIDj∥Prcij†)==Nrcij†, Sj computes [h(DIDi∥ri∥PWRi)]†=Prcij†⊕Krcij†, Wji=nj⊕[h(DIDi∥ri∥PWRi)]†, Qji=h([h(DIDi∥ri∥PWRi)]†∥nj∥Tj2), where nj is a random number, and then sends Ui with {Qji,Wji,Krcij†,Tj2}. Otherwise, exit.Step  5. Ui→Sj: {Vi,Ti2}. The smart card first tests Tj2 and then computes nj′=Wji⊕h(DIDi∥ri∥PWRi), Qji′=h(h(DIDi∥ri∥PWRi)∥nj′∥Tj2). If Qji′==Qji, the smart card computes Prcij′=Krcij†⊕h(DIDi∥ri∥PWRi), the session key SKi=h(Prcij′∥nj′), Vi=h(SKi∥Ti2) and sends {Vi,Ti2} to Sj. Otherwise, end.Step  6. After checking the freshness of Ti2, Sj computes SKj=h(Prcij†∥nj); Vi′=h(SKj∥Ti2), compares Vi′ with the received Vi. If they are equal, the authentication is finished successfully; both Ui and Sj accept the session key SKi(=SKj).


## 3.1.1. Initialization Phase

R C selects a secret long key x and a symmetric key encryption/decryption Enc/Dec algorithm (AES); then there is a hash function h(∗): {0,1}∗→{0,1}n.


## 3.1.2. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: {Skeyj,SIDj}. RC first checks the availability of SIDj, then calculates Skeyj=h(SIDj∥x), and adds {SIDj,keysj} into the Server-list, where keysj=Skeyj⊕x, finally sends {Skeyj,SIDj} to Sj; otherwise, RC rejects the server Sj’s request.Step  3. Sj stores Skeyj.


## 3.1.3. User Registration Phase

Step  1. Ui⇒RC: {DIDi,PWRi}. Ui selects PWi, IDi, and a random number bi, computes DIDi=h(IDi∥bi), PWRi=h(PWi∥bi), and then sends {DIDi,PWRi} to RC.Step  2. RC⇒Ui: a smart card with {Ci,Di,Ei}. RC tests DIDi by the User-list, chooses a random number yi, calculates Ci=h(x∥yi)⊕DIDi⊕PWRi, Ei=h(h(x∥yi)∥DIDi∥PWRi), and Di=Encx[DIDi∥PWRi], then stores DIDi into the User-list, and issues Ui a smart card with {Ci,Di,Ei}.Step  3. Ui computes b~i=bi⊕h(IDi∥PWi) and stores it.


## 3.1.4. Login and Authentication Phase

Step  1. Ui→Sj: LoginUi. Ui inputs IDi and PWi. The card computes bi′=b~i⊕h(IDi∥PWi), DIDi′=h(IDi⊕bi′), PWRi′=h(PWi∥bi′), hx∥yi′=Ci⊕DIDi′⊕PWRi′, and Ei′=h(hx∥yi′∥DIDi′∥PWRi′). If Ei′≠Ei, end the session. Otherwise, the card chooses a random number ri and timestamp Ti1, computes Gi=ri⊕h(DIDi′∥PWRi′∥Ti1), Fij=h(DIDi′∥PWRi′∥ri∥Ti1∥SIDj), and sends LoginUi={Gi,Fij,Di,Fi,SIDj,Ti1} to Sj.Step  2. Sj→RC: LoginSj. Sj first checks SIDj and the freshness of Ti1, then computes Hji=EncSkeyj[rj∥LoginUi∥Tj1∥SIDj], and sends LoginSj={Hji,SIDj,Tj1} to RC.Step  3. RC→Sj: {Rrcij}. RC first tests Tj1 and SIDj, catches corresponding Skeyj (Skeyj=keySj⊕x) from the Server-list, decrypts Hji with Skeyj, and then checks Tj1 ?= Tj1∗ and SIDj ?= SIDj∗ ?= SIDj∗∗. If one of the equations does not hold, end the session. Otherwise, RC computes (DIDi∗∥PWRi∗)=Decx[Di∗], ri=Gi∗⊕h(DIDi∗∥PWRi∗∥Ti1∗) and compares h(DIDi∗∥PWRi∗∥Ti1∗∥SIDj) with Fij∗. If they are not equal, end the session. Otherwise RC computes Prcij=h(x∥rrc∥rj∥ri), Krcij=h(DIDi∥ri∥PWRi)⊕Prcij, Lrcij=Prcij⊕rj, Nrcij=h(rj∥SIDj∥Prcij), Rrcij=EncSkeyj[Krcij∥Lrcij∥Nrcij∥Trc] and finally answers Sj with {Rrcij}.Step  4. Sj→Ui: {Qji,Wji,Krcij†,Tj2}. Sj computes (Krcij†∥Lrcij†∥Nrcij†∥Trc†)=DecSkeyj[Rrcij], checks Trc†, then computes Prcij†=Lrcij†⊕rj. If h(rj∥SIDj∥Prcij†)==Nrcij†, Sj computes [h(DIDi∥ri∥PWRi)]†=Prcij†⊕Krcij†, Wji=nj⊕[h(DIDi∥ri∥PWRi)]†, Qji=h([h(DIDi∥ri∥PWRi)]†∥nj∥Tj2), where nj is a random number, and then sends Ui with {Qji,Wji,Krcij†,Tj2}. Otherwise, exit.Step  5. Ui→Sj: {Vi,Ti2}. The smart card first tests Tj2 and then computes nj′=Wji⊕h(DIDi∥ri∥PWRi), Qji′=h(h(DIDi∥ri∥PWRi)∥nj′∥Tj2). If Qji′==Qji, the smart card computes Prcij′=Krcij†⊕h(DIDi∥ri∥PWRi), the session key SKi=h(Prcij′∥nj′), Vi=h(SKi∥Ti2) and sends {Vi,Ti2} to Sj. Otherwise, end.Step  6. After checking the freshness of Ti2, Sj computes SKj=h(Prcij†∥nj); Vi′=h(SKj∥Ti2), compares Vi′ with the received Vi. If they are equal, the authentication is finished successfully; both Ui and Sj accept the session key SKi(=SKj).


## 3.2. Cryptanalysis of Maitra et al.’s Scheme

It has to admit that Maitra et al.’s scheme has many attractive advantages, such as providing password and identity change phase. Furthermore, the way to protect the real identity and password is somewhat illuminating. While it is regrettable that this scheme is still not secure against various attacks, including stolen-verifier attack, off-line password guessing attack, and no forward secrecy and user anonymity.


### 3.2.1. Off-Line Dictionary Attack

In Section2.3, we explain that A can guess the identity and password simultaneously and also can learn the identity. No matter whether A knows about the identity, he/she can carry out the off-line dictionary attack. Here, we take A not knowing the identity as an example. Suppose A steals Ui’s smart card and extracts {Ci,Ei,b~i} from the smart card; then he can perform off-line dictionary attack as the following steps.Step  1. Guess the value of PWi to be PWi∗ from the password dictionary space Dpw, the value of IDi to be IDi∗ from the identity dictionary space Did.Step  2. Compute bi′=b~i⊕h(IDi∗∥PWi∗).Step  3. Compute DIDi′=h(IDi∗⊕bi′).Step  4. Compute PWRi′=h(PWi∗∥bi′).Step  5. Compute hx∥yi′=Ci⊕DIDi′⊕PWRi′.Step  6. Compute Ei′=h(hx∥yi′∥DIDi′∥PWRi′).Step  7. Verify the correctness of PWi and IDi by checking if Ei′=?Ei.Step  8. Repeat Steps 1~6 until the correct value of PWi and IDi are found.WithPWi and IDi, the adversary A can impersonate the user Ui to enjoy the service.The time complexity of the above attack isO(Dpw∗Did∗4TH), where TH is the running time for hash computation; Dpw and Did denote the number of passwords in Dpw and the number of identities in Did, respectively. Dpw is very limited due to the Zipf’s law in passwords [22]; Did is also very limited as generally Did<Dpw. So the attack can be finished in the polynomial time.


### 3.2.2. Forward Secrecy

Suppose an adversaryA somehow learns the long term secret key x and eavesdrops the message in the open channel to get Hji, Rrcij, Wji; then he/she can compute the session key between Sj and Ui as follows.Step  1. Compute Sj’s secret key Skeyj=h(SIDj∥x), where SIDj is an open parameter.Step  2. Decrypt Hji with Skeyj, and get rj, LoginUi, where LoginUi={Gi,Fij,Di,Fi,SIDj,Ti1} and Hji is from the open channel.Step  3. Decrypt Di with x to get DIDi and PWRi, where Di is from the open channel.Step  4. Decrypt Rrcij with Skeyj to get Lrcij, where Rrcij is from the open channel.Step  5. Compute Prcij=Lrcij⊕rj.Step  6. Compute nj=Wji⊕h(DIDi∥ri∥PWRi), where Wji is from the open channel.Step  7. Compute the session key SKi=h(Prcij∥nj).The time complexity of the above attack isO(3TH+3TS), where TS is the running time of symmetric encryption operation. According to the TABLE VI. in [2], the attack can be finished within seconds. So the above attack can be completed in the polynomial time.


### 3.2.3. Verifier-Stolen Attack

As we mentioned before, only the register center is trusted, the user and the server are both likely to be an adversaryA to conduct an attack. Consider such a condition where the legitimate server Sj somehow gets the verifier table in the database of register center. Then this adversary A can also compute x and, furthermore, damage the whole system as follows.Step  1. Compute x=keysj⊕Skeyj, where keySj is from the list {SIDj,keyj} of the verifier table.Step  2. Compute any other server Sk’s private secret key Skeyk=KeySk⊕x, where KeySk is from the list {SIDk,keyk} of the verifier table.The operations in the above procedure are some lightweight operation and the procedure is very simple.Withx and the verifier table, A has the same capacity with the register center. Thus A can impersonate RC to the user and the other server. What is more, with x, once A intercepts the message Hji or Hki (k≠j), A can compute any user’s PWRi and DIDi as the way RC do. Furthermore, with Skeyk, A has the same capacity with other server, so he/she can also impersonate other servers to RC and the users. Therefore, the security of the whole system is compromised.


### 3.2.4. User Anonymity

In this era of information explosion, user privacy protection is extremely important to the individuals. And user anonymity, as a pivotal way to protect the user privacy, contains two requirements: do not expose the identity directly; keep the identity untraceable. Once user anonymity cannot get guaranteed, the adversary may link the different communication in open channel to the same user and thus learns his preference and personal information for marketing purpose or other horrible purpose.In Maitra et al.’s scheme [18], there is a static value Di in the open channel. More specifically, to the same user, Di is unchanged (Di=Encx[DIDi∥PWRi]) unless Ui changes his identity and password. While the frequency of changing the identity or the password is so low, which means every time Ui initiates an access request to any servers, the same Di will be transmitted in the open channel in most occasions. Therefore, an adversary A can link the access request to the same user from the huge amounts of data to learn the user’s habits and preferences. So this scheme violates user untraceability.More specifically, an adversary can eavesdrop the open channel and then get the following message:(1)LoginUi1=Gi1,Fij1,Di1,Fi1,SIDj,Ti11,LoginUm1=Gm1,Fmj1,Dm1,Fm1,SIDj,Tm11,LoginUg1=Gg1,Fgj1,Dg1,Fg1,SIDj,Tg11,LoginUi2=Gi2,Fij2,Di2,Fi2,SIDk,Ti12,LoginUm2=Gm2,Fmj2,Dm2,Fm2,SIDk,Tm12,LoginUg2=Gg2,Fgj2,Dg2,Fg2,SIDk,Tg12,⋮LoginUin=Gin,Fijn,Din,Fin,SIDm,Ti1n,LoginUmn=Gmn,Fmjn,Dmn,Fmn,SIDm,Tm1n,LoginUgn=Ggn,Fgjn,Dgn,Fgn,SIDm,Tg1n.As Di1==Di2==Din==Di== a constant value, the adversary knows that among those messages, LoginUi1, LoginUi2, and LoginUi3 were sent by the same user; this user usually accesses Sj, Sk, and Sm at times Ti11, Ti12, and Ti1n, respectively. Thus the user untraceability is violated. Furthermore, once the adversary acquires IDi and PWi as we showed in Section 3.2.1, he can compute Di and thus traces the specific user Ui and learns more about the victim’s habits.


## 3.2.1. Off-Line Dictionary Attack

In Section2.3, we explain that A can guess the identity and password simultaneously and also can learn the identity. No matter whether A knows about the identity, he/she can carry out the off-line dictionary attack. Here, we take A not knowing the identity as an example. Suppose A steals Ui’s smart card and extracts {Ci,Ei,b~i} from the smart card; then he can perform off-line dictionary attack as the following steps.Step  1. Guess the value of PWi to be PWi∗ from the password dictionary space Dpw, the value of IDi to be IDi∗ from the identity dictionary space Did.Step  2. Compute bi′=b~i⊕h(IDi∗∥PWi∗).Step  3. Compute DIDi′=h(IDi∗⊕bi′).Step  4. Compute PWRi′=h(PWi∗∥bi′).Step  5. Compute hx∥yi′=Ci⊕DIDi′⊕PWRi′.Step  6. Compute Ei′=h(hx∥yi′∥DIDi′∥PWRi′).Step  7. Verify the correctness of PWi and IDi by checking if Ei′=?Ei.Step  8. Repeat Steps 1~6 until the correct value of PWi and IDi are found.WithPWi and IDi, the adversary A can impersonate the user Ui to enjoy the service.The time complexity of the above attack isO(Dpw∗Did∗4TH), where TH is the running time for hash computation; Dpw and Did denote the number of passwords in Dpw and the number of identities in Did, respectively. Dpw is very limited due to the Zipf’s law in passwords [22]; Did is also very limited as generally Did<Dpw. So the attack can be finished in the polynomial time.


## 3.2.2. Forward Secrecy

Suppose an adversaryA somehow learns the long term secret key x and eavesdrops the message in the open channel to get Hji, Rrcij, Wji; then he/she can compute the session key between Sj and Ui as follows.Step  1. Compute Sj’s secret key Skeyj=h(SIDj∥x), where SIDj is an open parameter.Step  2. Decrypt Hji with Skeyj, and get rj, LoginUi, where LoginUi={Gi,Fij,Di,Fi,SIDj,Ti1} and Hji is from the open channel.Step  3. Decrypt Di with x to get DIDi and PWRi, where Di is from the open channel.Step  4. Decrypt Rrcij with Skeyj to get Lrcij, where Rrcij is from the open channel.Step  5. Compute Prcij=Lrcij⊕rj.Step  6. Compute nj=Wji⊕h(DIDi∥ri∥PWRi), where Wji is from the open channel.Step  7. Compute the session key SKi=h(Prcij∥nj).The time complexity of the above attack isO(3TH+3TS), where TS is the running time of symmetric encryption operation. According to the TABLE VI. in [2], the attack can be finished within seconds. So the above attack can be completed in the polynomial time.


## 3.2.3. Verifier-Stolen Attack

As we mentioned before, only the register center is trusted, the user and the server are both likely to be an adversaryA to conduct an attack. Consider such a condition where the legitimate server Sj somehow gets the verifier table in the database of register center. Then this adversary A can also compute x and, furthermore, damage the whole system as follows.Step  1. Compute x=keysj⊕Skeyj, where keySj is from the list {SIDj,keyj} of the verifier table.Step  2. Compute any other server Sk’s private secret key Skeyk=KeySk⊕x, where KeySk is from the list {SIDk,keyk} of the verifier table.The operations in the above procedure are some lightweight operation and the procedure is very simple.Withx and the verifier table, A has the same capacity with the register center. Thus A can impersonate RC to the user and the other server. What is more, with x, once A intercepts the message Hji or Hki (k≠j), A can compute any user’s PWRi and DIDi as the way RC do. Furthermore, with Skeyk, A has the same capacity with other server, so he/she can also impersonate other servers to RC and the users. Therefore, the security of the whole system is compromised.


## 3.2.4. User Anonymity

In this era of information explosion, user privacy protection is extremely important to the individuals. And user anonymity, as a pivotal way to protect the user privacy, contains two requirements: do not expose the identity directly; keep the identity untraceable. Once user anonymity cannot get guaranteed, the adversary may link the different communication in open channel to the same user and thus learns his preference and personal information for marketing purpose or other horrible purpose.In Maitra et al.’s scheme [18], there is a static value Di in the open channel. More specifically, to the same user, Di is unchanged (Di=Encx[DIDi∥PWRi]) unless Ui changes his identity and password. While the frequency of changing the identity or the password is so low, which means every time Ui initiates an access request to any servers, the same Di will be transmitted in the open channel in most occasions. Therefore, an adversary A can link the access request to the same user from the huge amounts of data to learn the user’s habits and preferences. So this scheme violates user untraceability.More specifically, an adversary can eavesdrop the open channel and then get the following message:(1)LoginUi1=Gi1,Fij1,Di1,Fi1,SIDj,Ti11,LoginUm1=Gm1,Fmj1,Dm1,Fm1,SIDj,Tm11,LoginUg1=Gg1,Fgj1,Dg1,Fg1,SIDj,Tg11,LoginUi2=Gi2,Fij2,Di2,Fi2,SIDk,Ti12,LoginUm2=Gm2,Fmj2,Dm2,Fm2,SIDk,Tm12,LoginUg2=Gg2,Fgj2,Dg2,Fg2,SIDk,Tg12,⋮LoginUin=Gin,Fijn,Din,Fin,SIDm,Ti1n,LoginUmn=Gmn,Fmjn,Dmn,Fmn,SIDm,Tm1n,LoginUgn=Ggn,Fgjn,Dgn,Fgn,SIDm,Tg1n.As Di1==Di2==Din==Di== a constant value, the adversary knows that among those messages, LoginUi1, LoginUi2, and LoginUi3 were sent by the same user; this user usually accesses Sj, Sk, and Sm at times Ti11, Ti12, and Ti1n, respectively. Thus the user untraceability is violated. Furthermore, once the adversary acquires IDi and PWi as we showed in Section 3.2.1, he can compute Di and thus traces the specific user Ui and learns more about the victim’s habits.


## 4. Review of the Scheme of Amin

In 2016, Amin [17] showed two protocols [15, 16] both suffer from off-line guessing attack, impersonation attack, and so forth; thus he improved the two schemes to a new one claiming to be resistant to all known attacks, while, once again, we found Amin’s scheme is not as secure as his claim. In this section, we demonstrate that this scheme is vulnerable to off-line dictionary attack and insider attack and fails to achieve forward secrecy and user anonymity.


### 4.1. The Scheme of Amin

The authentication process of Amin’s scheme [17] is shown as follows briefly.


#### 4.1.1. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: RC calculates Skeyj=h(SIDj∥x) and then sends {Skeyj} to Sj.Step  3. Sj keeps {Skeyj} as his secret key.


#### 4.1.2. User Registration Phase

Step  1. Ui⇒RC: {IDi,PWRi}. Ui selects PWi, IDi, and a random number bi, computes PWRi=h(PWi∥bi), and then sends {IDi,PWRi}.Step  2. RC⇒Ui: smart card {CIDi,Ei,Ti,yi,h(·)}. RC calculates CIDi=h(IDi⊕yi⊕x), where yi is a random number, then checks the availability of CIDi, stores CIDi into User-list, computes Ei=h(IDi∥PWRi∥CIDi), Ti=h(CIDi∥x)⊕PWRi, finally, stores {CIDi,Ei,Ti,yi,h(·)} into a smart card, and sends it to Ui.Step  3. Ui inputs bi into the card.


#### 4.1.3. Login and Authentication Phase

Step  1. Ui→RC: {CIDi,SIDj,Ti,L3,L2,N3}. Ui inputs IDi and PWi. The card computes PWRi∗=h(PWi⊕bi), Ei∗=h(IDi∥PWi∥CIDi). If Ei∗≠Ei, exit the session. Otherwise, the card generates two random numbers N1 and N2 and computes L1=Ti⊕PWRi∗, N3=N1⊕N2, L2=N2⊕PWRi∗, L3=h(L1∥SIDj∥N1∥L2∥N3).Step  2. RC→Sj: {CIDi,A4,A3,N5}. RC first checks CIDi and SIDj and then computes Ai=h(CIDi∥x), PWRi′=Ti⊕Ai, N2′=L2⊕PWRi′, N1′=N3⊕N2′, L3′=h(A1∥SIDj∥N1′∥L2∥N3). If L3′≠L3, reject the request; otherwise, RC computes A2=h(SIDj∥x), A3=A2⊕N4, N5=N1′⊕N4, A4=h(A2∥N4∥N1∥CIDi).Step  3. Sj→Ui:{SIDj,A5,N7}. Sj computes N4′=Skeyj⊕A3, N1′=N4′⊕N5, A4′=h(Skeyj∥N4′∥N1′∥CIDi). If A4′≠A4, exit; otherwise, Sj authenticates RC, chooses a random number N6, and computes N7=N1′⊕N6, SKj=h(SIDj∥CIDi∥N6∥N1′), A5=h(SKj∥N6).Step  4. The smart card computes N6′=N7⊕N1, SKi=h(SIDj∥CIDi∥N6′∥N1), A5′=h(SKi∥N6′). If A5′==A5, Ui authenticates Sj and accepts SKi as their session key.


### 4.2. Cryptanalysis of Amin’s Scheme

This section will demonstrate that Amin’s scheme suffers from insider attack and off-line dictionary attackl furthermore, it fails to achieve forward secrecy and user anonymity.


#### 4.2.1. Off-Line Dictionary Attack

IfA steals Ui’s smart card and gets {CIDi,Ei,b} from the card, then a dictionary attack can be performed as follows:Step  1. Guess PWi to be PWi∗ and IDi to be IDi∗.Step  2. Compute PWRi∗=h(PWi⊕bi).Step  3. Compute Ei∗=h(IDi∥PWi∥CIDi).Step  4. Verify the correctness of PWi and IDi by checking if Ei∗ == Ei.Step  5. Repeat Steps 1~4 until the correct values of PWi and IDi are found.Once the adversaryA gets PWi and IDi, he/she can impersonate Ui. And the time complexity of the attack is O(Dpw∗Did∗2TH), so the attack is efficient.


#### 4.2.2. User Impersonation Attack

SupposeA is also a legitimate server Sj; then Sj can impersonate Ui to RC as follows.Step  1. Eavesdrop {CIDi,SIDj,Ti,L3,L2,N3} from Ui via the open channel.Step  2. Follow the protocol steps as a legitimate server to gain the response {CIDi,A4,A3,N5} from RC.Step  3. Continue acting as a legitimate server to compute N4=Skeyj⊕A3, N1=N4⊕N5.Step  4. Record N1.Step  5. Compute N2=N3⊕N1, where N3 is from Step 1.Step  6. Compute PWRi=L2⊕N2.The above procedure only involves the lightweight XOR operation; thus it is quite efficient. Now,A (also Sj) knows Ui’s PWRi; then he/she can forge Ui’s request message as {CIDi,SIDk,Ti,L3a,L2a,N3a} to other server Sk to enjoy the service. What is more, A can perform the above attack to all the users who have ever requested to login Sj. So such attack is terrible and has a huge effect to the system.In fact, after recordingN1, the adversary A can directly replay the access request as {CIDi,SIDk,Ti,L3a,L2,N3} to Sk, where L3a=h(L1∥SIDk∥N1∥L2∥N3); then, with the knowledge of N1, Sj can always compute the correct session key as N6′=N7⊕N1, SKi=h(SIDk∥CIDi∥N6′∥N1).


#### 4.2.3. Forward Secrecy

Assume thatA gets x and eavesdrops CIDi, SIDj, Ti, L2, N3, and N7; then he/she can compute the session key by the following steps:Step  1. Compute Ai=h(CIDi∥x).Step  2. Compute PWRi=Ti⊕Ai.Step  3. Compute N2=L2⊕PWRi.Step  4. Compute N1=N3⊕N2.Step  5. Compute N1=N3⊕N2.Step  6. Compute N6=N7⊕N1.Step  7. Compute SK=h(SIDj∥CIDi∥N6∥N1).Till now,A gets session key SK, and the time complexity of the attack is 2TH which is a very short time.


#### 4.2.4. User Anonymity

Similar to Maitra et al.’s scheme [18], this scheme also has the static parameters Ti and CIDj to uniquely identify Ui; thus it fails to provide user anonymity.


## 4.1. The Scheme of Amin

The authentication process of Amin’s scheme [17] is shown as follows briefly.


### 4.1.1. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: RC calculates Skeyj=h(SIDj∥x) and then sends {Skeyj} to Sj.Step  3. Sj keeps {Skeyj} as his secret key.


### 4.1.2. User Registration Phase

Step  1. Ui⇒RC: {IDi,PWRi}. Ui selects PWi, IDi, and a random number bi, computes PWRi=h(PWi∥bi), and then sends {IDi,PWRi}.Step  2. RC⇒Ui: smart card {CIDi,Ei,Ti,yi,h(·)}. RC calculates CIDi=h(IDi⊕yi⊕x), where yi is a random number, then checks the availability of CIDi, stores CIDi into User-list, computes Ei=h(IDi∥PWRi∥CIDi), Ti=h(CIDi∥x)⊕PWRi, finally, stores {CIDi,Ei,Ti,yi,h(·)} into a smart card, and sends it to Ui.Step  3. Ui inputs bi into the card.


### 4.1.3. Login and Authentication Phase

Step  1. Ui→RC: {CIDi,SIDj,Ti,L3,L2,N3}. Ui inputs IDi and PWi. The card computes PWRi∗=h(PWi⊕bi), Ei∗=h(IDi∥PWi∥CIDi). If Ei∗≠Ei, exit the session. Otherwise, the card generates two random numbers N1 and N2 and computes L1=Ti⊕PWRi∗, N3=N1⊕N2, L2=N2⊕PWRi∗, L3=h(L1∥SIDj∥N1∥L2∥N3).Step  2. RC→Sj: {CIDi,A4,A3,N5}. RC first checks CIDi and SIDj and then computes Ai=h(CIDi∥x), PWRi′=Ti⊕Ai, N2′=L2⊕PWRi′, N1′=N3⊕N2′, L3′=h(A1∥SIDj∥N1′∥L2∥N3). If L3′≠L3, reject the request; otherwise, RC computes A2=h(SIDj∥x), A3=A2⊕N4, N5=N1′⊕N4, A4=h(A2∥N4∥N1∥CIDi).Step  3. Sj→Ui:{SIDj,A5,N7}. Sj computes N4′=Skeyj⊕A3, N1′=N4′⊕N5, A4′=h(Skeyj∥N4′∥N1′∥CIDi). If A4′≠A4, exit; otherwise, Sj authenticates RC, chooses a random number N6, and computes N7=N1′⊕N6, SKj=h(SIDj∥CIDi∥N6∥N1′), A5=h(SKj∥N6).Step  4. The smart card computes N6′=N7⊕N1, SKi=h(SIDj∥CIDi∥N6′∥N1), A5′=h(SKi∥N6′). If A5′==A5, Ui authenticates Sj and accepts SKi as their session key.


## 4.1.1. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: RC calculates Skeyj=h(SIDj∥x) and then sends {Skeyj} to Sj.Step  3. Sj keeps {Skeyj} as his secret key.


## 4.1.2. User Registration Phase

Step  1. Ui⇒RC: {IDi,PWRi}. Ui selects PWi, IDi, and a random number bi, computes PWRi=h(PWi∥bi), and then sends {IDi,PWRi}.Step  2. RC⇒Ui: smart card {CIDi,Ei,Ti,yi,h(·)}. RC calculates CIDi=h(IDi⊕yi⊕x), where yi is a random number, then checks the availability of CIDi, stores CIDi into User-list, computes Ei=h(IDi∥PWRi∥CIDi), Ti=h(CIDi∥x)⊕PWRi, finally, stores {CIDi,Ei,Ti,yi,h(·)} into a smart card, and sends it to Ui.Step  3. Ui inputs bi into the card.


## 4.1.3. Login and Authentication Phase

Step  1. Ui→RC: {CIDi,SIDj,Ti,L3,L2,N3}. Ui inputs IDi and PWi. The card computes PWRi∗=h(PWi⊕bi), Ei∗=h(IDi∥PWi∥CIDi). If Ei∗≠Ei, exit the session. Otherwise, the card generates two random numbers N1 and N2 and computes L1=Ti⊕PWRi∗, N3=N1⊕N2, L2=N2⊕PWRi∗, L3=h(L1∥SIDj∥N1∥L2∥N3).Step  2. RC→Sj: {CIDi,A4,A3,N5}. RC first checks CIDi and SIDj and then computes Ai=h(CIDi∥x), PWRi′=Ti⊕Ai, N2′=L2⊕PWRi′, N1′=N3⊕N2′, L3′=h(A1∥SIDj∥N1′∥L2∥N3). If L3′≠L3, reject the request; otherwise, RC computes A2=h(SIDj∥x), A3=A2⊕N4, N5=N1′⊕N4, A4=h(A2∥N4∥N1∥CIDi).Step  3. Sj→Ui:{SIDj,A5,N7}. Sj computes N4′=Skeyj⊕A3, N1′=N4′⊕N5, A4′=h(Skeyj∥N4′∥N1′∥CIDi). If A4′≠A4, exit; otherwise, Sj authenticates RC, chooses a random number N6, and computes N7=N1′⊕N6, SKj=h(SIDj∥CIDi∥N6∥N1′), A5=h(SKj∥N6).Step  4. The smart card computes N6′=N7⊕N1, SKi=h(SIDj∥CIDi∥N6′∥N1), A5′=h(SKi∥N6′). If A5′==A5, Ui authenticates Sj and accepts SKi as their session key.


## 4.2. Cryptanalysis of Amin’s Scheme

This section will demonstrate that Amin’s scheme suffers from insider attack and off-line dictionary attackl furthermore, it fails to achieve forward secrecy and user anonymity.


### 4.2.1. Off-Line Dictionary Attack

IfA steals Ui’s smart card and gets {CIDi,Ei,b} from the card, then a dictionary attack can be performed as follows:Step  1. Guess PWi to be PWi∗ and IDi to be IDi∗.Step  2. Compute PWRi∗=h(PWi⊕bi).Step  3. Compute Ei∗=h(IDi∥PWi∥CIDi).Step  4. Verify the correctness of PWi and IDi by checking if Ei∗ == Ei.Step  5. Repeat Steps 1~4 until the correct values of PWi and IDi are found.Once the adversaryA gets PWi and IDi, he/she can impersonate Ui. And the time complexity of the attack is O(Dpw∗Did∗2TH), so the attack is efficient.


### 4.2.2. User Impersonation Attack

SupposeA is also a legitimate server Sj; then Sj can impersonate Ui to RC as follows.Step  1. Eavesdrop {CIDi,SIDj,Ti,L3,L2,N3} from Ui via the open channel.Step  2. Follow the protocol steps as a legitimate server to gain the response {CIDi,A4,A3,N5} from RC.Step  3. Continue acting as a legitimate server to compute N4=Skeyj⊕A3, N1=N4⊕N5.Step  4. Record N1.Step  5. Compute N2=N3⊕N1, where N3 is from Step 1.Step  6. Compute PWRi=L2⊕N2.The above procedure only involves the lightweight XOR operation; thus it is quite efficient. Now,A (also Sj) knows Ui’s PWRi; then he/she can forge Ui’s request message as {CIDi,SIDk,Ti,L3a,L2a,N3a} to other server Sk to enjoy the service. What is more, A can perform the above attack to all the users who have ever requested to login Sj. So such attack is terrible and has a huge effect to the system.In fact, after recordingN1, the adversary A can directly replay the access request as {CIDi,SIDk,Ti,L3a,L2,N3} to Sk, where L3a=h(L1∥SIDk∥N1∥L2∥N3); then, with the knowledge of N1, Sj can always compute the correct session key as N6′=N7⊕N1, SKi=h(SIDk∥CIDi∥N6′∥N1).


### 4.2.3. Forward Secrecy

Assume thatA gets x and eavesdrops CIDi, SIDj, Ti, L2, N3, and N7; then he/she can compute the session key by the following steps:Step  1. Compute Ai=h(CIDi∥x).Step  2. Compute PWRi=Ti⊕Ai.Step  3. Compute N2=L2⊕PWRi.Step  4. Compute N1=N3⊕N2.Step  5. Compute N1=N3⊕N2.Step  6. Compute N6=N7⊕N1.Step  7. Compute SK=h(SIDj∥CIDi∥N6∥N1).Till now,A gets session key SK, and the time complexity of the attack is 2TH which is a very short time.


### 4.2.4. User Anonymity

Similar to Maitra et al.’s scheme [18], this scheme also has the static parameters Ti and CIDj to uniquely identify Ui; thus it fails to provide user anonymity.


## 4.2.1. Off-Line Dictionary Attack

IfA steals Ui’s smart card and gets {CIDi,Ei,b} from the card, then a dictionary attack can be performed as follows:Step  1. Guess PWi to be PWi∗ and IDi to be IDi∗.Step  2. Compute PWRi∗=h(PWi⊕bi).Step  3. Compute Ei∗=h(IDi∥PWi∥CIDi).Step  4. Verify the correctness of PWi and IDi by checking if Ei∗ == Ei.Step  5. Repeat Steps 1~4 until the correct values of PWi and IDi are found.Once the adversaryA gets PWi and IDi, he/she can impersonate Ui. And the time complexity of the attack is O(Dpw∗Did∗2TH), so the attack is efficient.


## 4.2.2. User Impersonation Attack

SupposeA is also a legitimate server Sj; then Sj can impersonate Ui to RC as follows.Step  1. Eavesdrop {CIDi,SIDj,Ti,L3,L2,N3} from Ui via the open channel.Step  2. Follow the protocol steps as a legitimate server to gain the response {CIDi,A4,A3,N5} from RC.Step  3. Continue acting as a legitimate server to compute N4=Skeyj⊕A3, N1=N4⊕N5.Step  4. Record N1.Step  5. Compute N2=N3⊕N1, where N3 is from Step 1.Step  6. Compute PWRi=L2⊕N2.The above procedure only involves the lightweight XOR operation; thus it is quite efficient. Now,A (also Sj) knows Ui’s PWRi; then he/she can forge Ui’s request message as {CIDi,SIDk,Ti,L3a,L2a,N3a} to other server Sk to enjoy the service. What is more, A can perform the above attack to all the users who have ever requested to login Sj. So such attack is terrible and has a huge effect to the system.In fact, after recordingN1, the adversary A can directly replay the access request as {CIDi,SIDk,Ti,L3a,L2,N3} to Sk, where L3a=h(L1∥SIDk∥N1∥L2∥N3); then, with the knowledge of N1, Sj can always compute the correct session key as N6′=N7⊕N1, SKi=h(SIDk∥CIDi∥N6′∥N1).


## 4.2.3. Forward Secrecy

Assume thatA gets x and eavesdrops CIDi, SIDj, Ti, L2, N3, and N7; then he/she can compute the session key by the following steps:Step  1. Compute Ai=h(CIDi∥x).Step  2. Compute PWRi=Ti⊕Ai.Step  3. Compute N2=L2⊕PWRi.Step  4. Compute N1=N3⊕N2.Step  5. Compute N1=N3⊕N2.Step  6. Compute N6=N7⊕N1.Step  7. Compute SK=h(SIDj∥CIDi∥N6∥N1).Till now,A gets session key SK, and the time complexity of the attack is 2TH which is a very short time.


## 4.2.4. User Anonymity

Similar to Maitra et al.’s scheme [18], this scheme also has the static parameters Ti and CIDj to uniquely identify Ui; thus it fails to provide user anonymity.


## 5. Proposed Scheme

To overcome the identified weaknesses, we designed a new enhanced scheme (shown in Figures3, 4, and 5). For better comprehension, we sketch the ideas behind our scheme:(i)
We adopt a way of “honeywords” + “fuzzy-verifiers” which is introduced by D. Wang and P. Wang [2] to settle the off-line dictionary attack in these two schemes. As we mentioned above, the inherent reason for such attack is the critical parameter Ei which can be used to test the correctness of the guessed IDi and PWi. However, in the way of “honeywords” + “fuzzy-verifiers”, Ei is recalculated as h(h(DIDi)∥h(PWRi)) mod n0 where n0 (24≤n0≤28) is a integer to determine the size of (ID,PW). Furthermore, there is a Honey_List maintained in RC to record the numbers of failed logins. Thus even if A finds a pair of {IDi′,PWi′} that satisfies the equation, he/she still cannot know whether IDi′=?IDi and PWi′=?PWi, for there are Dpw∗Did÷n0≈232 candidates of {IDi,PWi} pair. Then A has to verify these candidates online, but it is stopped by Honey_List.(ii)
We follow the principle in [39] to deploy a public key algorithm to achieve user anonymity. We conceal the identity IDi in Di, then the adversary cannot get IDi from Di unless he/she knows the secret long term key or solves the discrete logarithm program. Furthermore, Di is changed with the random number ri to avoid identity being traced.(iii)
From the verifier-stolen attack in Maitra et al.’s scheme, it is important to protect the long term secret keyx, “XOR” operation on x is a risky behavior which is likely to expose x. Thus, in our scheme, x is used in a form of h(SIDj∥x∥TSrg) and h(x∥yi∥Trg).(iv)
The serverSj in multiserver environment is a special adversary, which should be treated carefully. In Section 4.2.2, we witnessed how Sj carries out an attack. The key to prevent such attack is to let Sj not know the key parameter of Ui or RC. So we, on one hand, compute the shared key of Sj and RC as h(SIDj∥x∥TSrg) to make Sj learn nothing about x; on the other hand, we use the output of public key algorithm C2 concealed in Prcij for Ui to authenticate Sj (Sj does not know any key parameter such as PWRi of Ui).Figure 3
Server registration phase.Figure 4
User registration phase.Figure 5
Login and authentication phase.


### 5.1. Initialization Phase

R C selects a generator g of a multiplicative group G of prime order p and a secret long key x (x∈Zp) and then computes the public key y=gx mod p. Then, similar to Maitra et al.’s scheme [18], there is a symmetric key encryption/decryption algorithm and also a hash function h(·): {0,1}∗→{0,1}l.


### 5.2. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: {Skeyj}.RC researches the Server-list to check the valid of SIDj. If it is not in it, it computes Skeyj=h(SIDj∥x∥TSrg), where Trg is the register time. Then RC adds {SIDj,TSrg} into the Server-list, finally sends {Skeyj} to Sj; otherwise, RC rejects.Step  3. After getting {Skeyj}, Sj keeps it as its secret key.


### 5.3. User Registration Phase

Step  1. Ui⇒RC: {DIDi,PWRi}. Ui chooses password PWi, identity IDi, and a random number bi, computes DIDi=h(IDi∥bi), PWRi=h(PWi∥bi), and then sends {DIDi,PWRi} to RC.Step  2. RC⇒Ui: a smart card with {Ci,Ei,n0,p,g,y,h(∗)}. RC tests the valid of DIDi from the user-list. If it has been used by other users, it asks Ui for a new identity; otherwise, it chooses a unique random number yi and calculates Ki=h(x∥yi∥Trg), Ci=Ki⊕DIDi⊕PWRi, Ei=h(h(DIDi)∥h(PWRi)) mod n0 where n0 is a integer and 24≤n0≤28 and then stores {DIDi,yi,Trg,Honey_List} into the User-list. It should be noted that Honey_List is to record the number of login failures and is initialized to 0. At last, RC issues Ui a smart card with {Ci,Ei,n0,p,g,y,h(∗)}.Step  3. Ui computes b~i=bi⊕h(IDi∥PWi) and enters b~i into the smart card.


### 5.4. Login and Authentication Phase

Step  1. Ui→Sj: LoginUi={Di,C1,Fij,SIDj}. Ui puts the smart card into a terminal and inputs IDi and PWi. The card computes bi′=b~i⊕h(IDi∥PWi), DIDi′=h(IDi⊕bi′), PWRi′=h(PWi∥bi′) and then verifies the legitimacy of Ui by testing Ei?=h(h(DIDi′)⊕h(PWRi′)) mod n0. If it is not equal, exit the session.Otherwise, the card selects a random numberri, computes C1=gri mod p, C2=yri mod p, Di=DIDi′⊕h(C1∥C2), Ki′=Ci⊕DIDi′⊕PWRi′, and Fij=h(DIDi′∥C1∥C2∥Ki′∥SIDj), then sends LoginUi={Di,C1,Fij,SIDj} to Sj.Step  2. Sj→RC: {Hji,SIDj}. Sj chooses a random number n as a “challenge”, computes: Hji=EncSkeyj[n∥LoginUi∥SIDj], and sends {Hji,SIDj} to RC.Step  3. RC→Sj: {Rrcij}. RC first checks the valid of SIDj, then gets TSrg from the Server-List, and computes: Skeyj′=h(SIDj∥x∥TSrg), n∗∥LoginUi∗∥SIDj∗=DecSkeyj′[Hji] where LoginUi∗={Di∗,C1∗,Fij∗,SIDj∗∗}; then RC tests SIDj?=SIDj∗?=SIDj∗∗ to verify the legitimacy of Sj. If they are not equal, end the session.Otherwise,RC continues computing C2∗=(C1∗)x mod p, DIDi∗=Di∗⊕h(C1∗∥C2∗), then acquires Trg and yi from the User-list, computes Ki=h(x∥yi∥Trg), and checks Fij∗?=h(DIDi∗∥C1∗∥C2∗∥Ki∥SIDj∗) to authenticate Ui. If Ui is not a valid user, RC sets Hoeny_List to be Hoeny_List + 1 and ends the session. Once the value of Honey_List≥ the predetermined threshold (such as 10), it is likely that the information in the smart card was exposed; thus RC suspends the card till Ui reregisters.Otherwise,RC continues computing Prcij=h(DIDi∗∥C1∗∥C2∗), Krcij=Prcij⊕n∗, Nrcij=h(n∗∥SIDj∥Prcij), Rrcij=Ench(Skeyj∥n∗)[Krcij∥Nrcij], finally responding to Sj with Rrcij.Step  4. Sj→Ui: {Qji,C3}. Sj first decrypts Rrcij with h(Skeyj∥n) to obtain Krcij† and Nrcij†, computes Prcij†=Krcij†⊕n∗, and then compares Nrcij† with h(n∥SIDj∥Prcij†) to authenticate RC. If the condition is not satisfied, exit.Otherwise,Sj selects a random number rj, computes C3=grj mod p, C4=(C1)rj mod p, SK†=h(Prcij†∥C1∥C4), Qji=h(Prcij†∥C1∥C3∥C4∥SK†), sends {Qji,C3} to Ui.Step  5. Ui→Sj: {Vi}. The smart card computes C4=(C3)ri mod p, Prcij′=h(DIDi∥C1∥C2), SK=h(Prcij′∥C1∥C4′). If Qji==h(Prcij′∥C1∥C3∥C4′∥SK), Ui believes that Sj is the desired server and accepts SK as the session key and then sends Vi=h(SK∥C4′∥C3) to Sj. Otherwise, exit the session.Step  6. Sj computes Vi†=h(SK†∥C4∥C3). If Vi†==Vi, Sj believes the legitimacy of Ui. Till now, the authentication phase finished successfully, and the session key is established.


### 5.5. Password Change Phase

When the user wants to change the password, he can perform the steps as follows.Step  1. Ui inputs IDi, PWi, and new password PWinew.Step  2. The card computes bi′=b~i⊕h(IDi∥PWi), DIDi′=h(IDi⊕bi′), PWRi′=h(PWi∥bi′), if Ei≠h(h(DIDi′)⊕h(PWRi′)) mod n0, the card rejects the request. Otherwise, it computes Cinew=Ci⊕PWRi′⊕PWRinew, Einew=h(h(DIDi′)∥h(PWRinew)) mod n0 and replaces Ci,Ei with Cinew,Einew.


### 5.6. Revocation Phase

Once the user realized the card is not in the control of himself, he can revoke the account as follows.Step  1. Ui firstly gets authenticated by the card in the same way as in Step 1 in Section 5.4.Step  2. Ui→RC: {Di,C1,Fij,revoke_request}. The way to compute Di, C1, and Fij is similar to Step 1 in Section 5.4, expect Fij=h(DIDi′∥C1∥C2∥Ki′).Step  3. RC authenticates Ui by computing C2∗=(C1∗)x mod p, DIDi∗=Di∗⊕h(C1∗∥C2∗), Ki=h(x∥yi∥Trg), Fij∗?=h(DIDi∗∥C1∗∥C2∗∥Ki∥). If RC accepts Ui, it sets yi=NULL to revoke the account. Otherwise, RC reject the request.


### 5.7. Reregistration Phase

IfUi with correct password and identity is still rejected by Sj, then he can reregister as follows.Step  1. Ui⇒RC: {DIDi,PWRi,reregister}.Step  2. RC first researches DIDi in the User-list and checks whether the account of Ui is revoked or the card is suspended. If so, RC accepts the request and conducts the register phase in Section 5.3.


## 5.1. Initialization Phase

R C selects a generator g of a multiplicative group G of prime order p and a secret long key x (x∈Zp) and then computes the public key y=gx mod p. Then, similar to Maitra et al.’s scheme [18], there is a symmetric key encryption/decryption algorithm and also a hash function h(·): {0,1}∗→{0,1}l.


## 5.2. Server Registration Phase

Step  1. Sj⇒RC: {SIDj}.Step  2. RC⇒Sj: {Skeyj}.RC researches the Server-list to check the valid of SIDj. If it is not in it, it computes Skeyj=h(SIDj∥x∥TSrg), where Trg is the register time. Then RC adds {SIDj,TSrg} into the Server-list, finally sends {Skeyj} to Sj; otherwise, RC rejects.Step  3. After getting {Skeyj}, Sj keeps it as its secret key.


## 5.3. User Registration Phase

Step  1. Ui⇒RC: {DIDi,PWRi}. Ui chooses password PWi, identity IDi, and a random number bi, computes DIDi=h(IDi∥bi), PWRi=h(PWi∥bi), and then sends {DIDi,PWRi} to RC.Step  2. RC⇒Ui: a smart card with {Ci,Ei,n0,p,g,y,h(∗)}. RC tests the valid of DIDi from the user-list. If it has been used by other users, it asks Ui for a new identity; otherwise, it chooses a unique random number yi and calculates Ki=h(x∥yi∥Trg), Ci=Ki⊕DIDi⊕PWRi, Ei=h(h(DIDi)∥h(PWRi)) mod n0 where n0 is a integer and 24≤n0≤28 and then stores {DIDi,yi,Trg,Honey_List} into the User-list. It should be noted that Honey_List is to record the number of login failures and is initialized to 0. At last, RC issues Ui a smart card with {Ci,Ei,n0,p,g,y,h(∗)}.Step  3. Ui computes b~i=bi⊕h(IDi∥PWi) and enters b~i into the smart card.


## 5.4. Login and Authentication Phase

Step  1. Ui→Sj: LoginUi={Di,C1,Fij,SIDj}. Ui puts the smart card into a terminal and inputs IDi and PWi. The card computes bi′=b~i⊕h(IDi∥PWi), DIDi′=h(IDi⊕bi′), PWRi′=h(PWi∥bi′) and then verifies the legitimacy of Ui by testing Ei?=h(h(DIDi′)⊕h(PWRi′)) mod n0. If it is not equal, exit the session.Otherwise, the card selects a random numberri, computes C1=gri mod p, C2=yri mod p, Di=DIDi′⊕h(C1∥C2), Ki′=Ci⊕DIDi′⊕PWRi′, and Fij=h(DIDi′∥C1∥C2∥Ki′∥SIDj), then sends LoginUi={Di,C1,Fij,SIDj} to Sj.Step  2. Sj→RC: {Hji,SIDj}. Sj chooses a random number n as a “challenge”, computes: Hji=EncSkeyj[n∥LoginUi∥SIDj], and sends {Hji,SIDj} to RC.Step  3. RC→Sj: {Rrcij}. RC first checks the valid of SIDj, then gets TSrg from the Server-List, and computes: Skeyj′=h(SIDj∥x∥TSrg), n∗∥LoginUi∗∥SIDj∗=DecSkeyj′[Hji] where LoginUi∗={Di∗,C1∗,Fij∗,SIDj∗∗}; then RC tests SIDj?=SIDj∗?=SIDj∗∗ to verify the legitimacy of Sj. If they are not equal, end the session.Otherwise,RC continues computing C2∗=(C1∗)x mod p, DIDi∗=Di∗⊕h(C1∗∥C2∗), then acquires Trg and yi from the User-list, computes Ki=h(x∥yi∥Trg), and checks Fij∗?=h(DIDi∗∥C1∗∥C2∗∥Ki∥SIDj∗) to authenticate Ui. If Ui is not a valid user, RC sets Hoeny_List to be Hoeny_List + 1 and ends the session. Once the value of Honey_List≥ the predetermined threshold (such as 10), it is likely that the information in the smart card was exposed; thus RC suspends the card till Ui reregisters.Otherwise,RC continues computing Prcij=h(DIDi∗∥C1∗∥C2∗), Krcij=Prcij⊕n∗, Nrcij=h(n∗∥SIDj∥Prcij), Rrcij=Ench(Skeyj∥n∗)[Krcij∥Nrcij], finally responding to Sj with Rrcij.Step  4. Sj→Ui: {Qji,C3}. Sj first decrypts Rrcij with h(Skeyj∥n) to obtain Krcij† and Nrcij†, computes Prcij†=Krcij†⊕n∗, and then compares Nrcij† with h(n∥SIDj∥Prcij†) to authenticate RC. If the condition is not satisfied, exit.Otherwise,Sj selects a random number rj, computes C3=grj mod p, C4=(C1)rj mod p, SK†=h(Prcij†∥C1∥C4), Qji=h(Prcij†∥C1∥C3∥C4∥SK†), sends {Qji,C3} to Ui.Step  5. Ui→Sj: {Vi}. The smart card computes C4=(C3)ri mod p, Prcij′=h(DIDi∥C1∥C2), SK=h(Prcij′∥C1∥C4′). If Qji==h(Prcij′∥C1∥C3∥C4′∥SK), Ui believes that Sj is the desired server and accepts SK as the session key and then sends Vi=h(SK∥C4′∥C3) to Sj. Otherwise, exit the session.Step  6. Sj computes Vi†=h(SK†∥C4∥C3). If Vi†==Vi, Sj believes the legitimacy of Ui. Till now, the authentication phase finished successfully, and the session key is established.


## 5.5. Password Change Phase

When the user wants to change the password, he can perform the steps as follows.Step  1. Ui inputs IDi, PWi, and new password PWinew.Step  2. The card computes bi′=b~i⊕h(IDi∥PWi), DIDi′=h(IDi⊕bi′), PWRi′=h(PWi∥bi′), if Ei≠h(h(DIDi′)⊕h(PWRi′)) mod n0, the card rejects the request. Otherwise, it computes Cinew=Ci⊕PWRi′⊕PWRinew, Einew=h(h(DIDi′)∥h(PWRinew)) mod n0 and replaces Ci,Ei with Cinew,Einew.


## 5.6. Revocation Phase

Once the user realized the card is not in the control of himself, he can revoke the account as follows.Step  1. Ui firstly gets authenticated by the card in the same way as in Step 1 in Section 5.4.Step  2. Ui→RC: {Di,C1,Fij,revoke_request}. The way to compute Di, C1, and Fij is similar to Step 1 in Section 5.4, expect Fij=h(DIDi′∥C1∥C2∥Ki′).Step  3. RC authenticates Ui by computing C2∗=(C1∗)x mod p, DIDi∗=Di∗⊕h(C1∗∥C2∗), Ki=h(x∥yi∥Trg), Fij∗?=h(DIDi∗∥C1∗∥C2∗∥Ki∥). If RC accepts Ui, it sets yi=NULL to revoke the account. Otherwise, RC reject the request.


## 5.7. Reregistration Phase

IfUi with correct password and identity is still rejected by Sj, then he can reregister as follows.Step  1. Ui⇒RC: {DIDi,PWRi,reregister}.Step  2. RC first researches DIDi in the User-list and checks whether the account of Ui is revoked or the card is suspended. If so, RC accepts the request and conducts the register phase in Section 5.3.


## 6. Security Analysis

In this section, we first use the Burrows-Abadi-Needham (BAN) logic [40] to prove the security of our scheme formally, then analyze it in a heuristic method. The results demonstrate the security and practicability of our scheme.


### 6.1. Formal Analysis Based on BAN Logic

As an efficient and simple way to analyze the design logic and security of the authentication scheme, BAN logic [40] has been widely used. As shown in Table 4, it uses some particular notions to depict a protocol.Table 4
Notations in BAN logic.
P ∣ ≡ X P believes X, that is, the principal P believes the statement X is true.  P ⊲ X P sees X, that is, the principal P receives a message that contains X.  P ∣ ⇒ X P has jurisdiction over X, that is, the principal P can generates or computes X.  P ∣ ~ X P said X, that is, the principal P has sent a message containing X.  ♯ ( X ) X is fresh, that is, X is sent in a message only at the current run of the protocol, it is usually a timestamp or a random number.  P ↔ K Q K is the shared key for P and Q.  P ⇌ Y Q Y is the secret known only to P and Q or some principals trusted by them.  〈 X 〉 Y X combined with Y, and Y usually is a secret.  { X } K X encrypted with K.  P∣≡P↔KQ,P⊲{X}KP∣≡Q∣~XorP∣≡P⇌YQ,P⊲〈X〉YP∣≡Q∣~X R U L E ( 1 ): the message-meaning rule. This rule will be used in the proving process.  P ∣ ≡ ♯ ( X ) , P ∣ ≡ Q ∣ ~ X P ∣ ≡ Q ∣ ≡ X R U L E ( 2 ): the nonce-verification rule. This rule will be used in the proving process.  P ∣ ≡ Q ∣ ⇒ X , P ∣ ≡ Q ∣ ≡ X P ∣ ≡ X R U L E ( 3 ): the jurisdiction rule. This rule will be used in the proving process.  P ∣ ≡ ♯ ( X ) P ∣ ≡ ♯ ( X , Y ) R U L E ( 4 ): the freshness-conjuncatenation rule. This rule will be used in the proving process.The goals of our proposed scheme are as follows: these four goals ensure that the server and the user get authenticated mutually (corresponding to our proposed S1, S10, and S13), and they build a session key successfully (corresponding to our proposed S14):(1)
Goal 1:Ui∣≡Sj∣≡(Ui↔SKSj).(2)
Goal 2:Ui∣≡(Ui↔SKSj).(3)
Goal 3:Sj∣≡Ui∣≡(Ui↔SKSj).(4)
Goal 4:Sj∣≡(Ui↔SKSj).According to the BAN logic, we first transform the scheme to an idealized one:M1: Ui→Sj: 〈DIDi,SIDj,C1,Ui↔C2RC〉Ui↔KiRC.M2: Sj→RC: 〈SIDj,Di,C1,Fij,n〉Sj↔SkeyjRC.M3: RC→Sj: 〈SIDj,n,Ui⇌PrcijSj〉Sj↔SkeyjRC.M4: Sj→Ui: 〈C1,C3,Ui↔SKSj〉Ui⇌PrcijSj.M5: Ui→Sj: 〈C3,Ui↔SKSj〉Ui↔C4Sj.Then, to analyze the scheme, we make some assumptions about its initial state as follows:H1: Ui∣≡♯(C1).H2: Sj∣≡♯(C3).H3: Sj∣≡♯(n).H4: Ui∣≡Ui↔KiRC.H5: RC∣≡Ui↔KiRC.H6: Ui∣≡Ui⇌PrcijSj.H7: Sj∣≡Sj↔SkeyjRC.H8: RC∣≡Sj↔SkeyjRC.H9: Sj∣≡Ui↔C4RC.H10: Ui∣≡Sj∣⇒Ui↔KiSj.H11: Sj∣≡Ui∣⇒Ui↔KiSj.H12: Sj∣≡RC∣⇒Ui⇌PrcijSj.Based on these assumptions above, we will prove the security of our protocol according to BAN logic as follows.From  M2, we have(2)S1:RC⊲SIDj,Di,C1,Fij,nSj↔SkeyjRC.Then according to H8,S1, RULE(1), it is obvious that(3)S2:RC∣≡Sj∣~SIDj,Di,C1,Fij,n.From  M1, we have(4)S3:RC⊲DIDi,SIDj,C1,Ui↔C2RCUi↔KiRC.Then according toH5, S3, RULE(1), it is obvious that (5)S4:RC∣≡Ui∣~DIDi,SIDj,C1,Ui↔C2RC.From  M3, we have (6)S5:Sj⊲SIDj,n,Ui⇌PrcijSjSj↔SkeyjRC.Then according toH7, S5, RULE(1), it is obvious that (7)S6:Sj∣≡RC∣~SIDj,n,Ui⇌PrcijSj.And according toH3, S6, RULE(4) and RULE(2), we get (8)S7:Sj∣≡RC∣~Ui⇌PrcijSj.And according toH12, S7, RULE(3), we can get (9)S8:Sj∣≡Ui⇌PrcijSj.From  M4, we have (10)S9:Ui⊲C1,C3,Ui↔SKSjUi⇌PrcijSj.Then according toH6, S9, RULE(1), it is obvious that(11)S10:Ui∣≡Sj∣~C1,C3,Ui↔SKSj.And according toH2, S10, RULE(4) and RULE(2), we get(12)S11:Ui∣≡Sj∣≡Ui↔SKSjGoal  1.And according toH10, S11, RULE(3), we can get(13)S12:Ui∣≡Ui↔SKSjGoal  2.From  M5, we have (14)S13:Sj⊲C3,Ui↔SKSjUi↔C4Sj.Then according toH9, S13, RULE(1), it is obvious that(15)S14:Sj∣≡Ui∣~C3,Ui↔SKSj.And according toH2, S13, RULE(4) and RULE(2), we get(16)S15:Sj∣≡Ui∣≡Ui↔SKSjGoal  3.And according toH11, S15, RULE(3), we can get(17)S16:Sj∣≡Ui↔SKSjGoal  4.Thus with Goals 1~4, we proved that the user Ui and the server Sj have authenticated to each other; furthermore they accepted and shared the session key SK.


### 6.2. Informal Analysis

The heuristic method without complex formula is a direct and simple way for a quick analysis of the security of the protocol. It plays a significant role in cryptoanalysis of authentication protocols, though its analytic process heavily depends on human experience rather than a set of scientific tools. This section uses a heuristic method to prove that our scheme not only provides desire attributes but also is resistant to various attacks.


#### 6.2.1. User Anonymity

In our scheme, on one hand, the adversaryA cannot get IDi: the user identity was concealed in DIDi where DIDi=h(IDi∥bi), so an adversary without bi cannot guess the value of IDi via dictionary attack; on the other hand, A cannot link the message flows to a certain user: though DIDi is a fixed value, it is transmitted in a form of Di=DIDi⊕h(C1∥C2), where C1 and C2 are changed with different turns of the protocol, and only the user and the one knowing the long term secret key can compute C2. This indicates that Di is changed with C1 and C2, and A cannot get C2. Thus A fails to link the message flows to a certain user. So our scheme achieves user anonymity.


#### 6.2.2. Forward Secrecy

The session keySK of the proposed scheme consists of two “special” parameters: Prcij and C4, where Prcij=h(DIDi∥C1∥C2) and C4=(C3)ri mod p=(C1)rj mod p=grirj mod p. Suppose that an adversary gets the secret key x, then he can intercept Di and C1 to compute DIDi and C2. However, computing C4 for A is equivalent to solving the DLP problem, which is bound to fail. So our scheme provides perfect forward security.


#### 6.2.3. Mutual Authentication

In Step 3 of Section5.4, RC with x verifies the validity of Ui by checking Fij, if Ui is legitimate, RC computes Prcij and constructs Rrcij to Sj. So with the help of RC, Sj authenticates Ui. In a short, both RC and Sj authenticate Ui.In Step 3 of Section5.4, RC with Skeyj authenticates Sj by checking SIDj. If Sj passes the test, RC respond to Sj’s challenge n with Rrcij which is an encryption with the key h(Skeyj∥n). Then Sj verifies RC’s validity by checking Nrcij. Furthermore, with Prcij in Qji, Ui verifies RC and Sj. So all in all, Sj authenticates RC and Ui; Ui authenticates RC and Sj.Therefore, our scheme achieves mutual authentication.


#### 6.2.4. Privileged Insider Attack

In the registration phase of our scheme,Ui submits {h(IDi∥bi),h(PWi∥bi)} to RC. From this message, RC learns nothing about Ui’s PWi or other useful information. Thus our scheme is resistant to privileged insider attack.


#### 6.2.5. Off-Line Dictionary Attack

Suppose an adversaryA has the full control of the open channel and obtains the information in the smart card; then we prove that our scheme can resist the off-line dictionary attack through two aspects.On one hand, withEi and b~i, A guesses IDi and PWi to be IDi′ and PWi′, respectively. Then A computes bi′=b~i⊕h(IDi′∥PWi′), DIDi′=h(IDi′⊕bi′), PWRi′=h(PWi′∥bi′), then verifies the correctness of IDi′ and PWi′ by testing Ei?=h(h(DIDi′)⊕h(PWRi′)) mod n0, and repeats these processes till the equation is satisfied. However, even if A finds such a pair of IDi′,PWi′, he still is not sure whether IDi′==IDi and PWi′==PWi, for there are Dpw∗Did∖n0≈232 candidates of {IDi,PWi} pair when n0=28 and Dpw=Did=26 [2]. Then A has to verify {IDi′,PWi′} in a manner of online, which will be stopped by the Honey_List.On the other hand,A may try another way to conduct an off-line dictionary attack: obtaining b~i, Ci and {Di,C1,Fij,SIDj}, using Fij to check the correctness of the guessed IDi′ and PWi′, while A has to compute C2 which is impossible for the entity (except Ui) without x as we explained in Section 6.2.1.In conclusion, our scheme is secure to dictionary attack.


#### 6.2.6. Verifier-Stolen Attack

In our scheme,RC maintains a User-list in form of {DIDi,yi,Trg,Hoeny_List} and a Server-list in form of {SIDj,TSrg}, while the parameters in the two list are not security-related. Thus an adversary with the verifier table has no security threat to the system.


#### 6.2.7. Replay Attack

We apply the random number to prevent replay attack. Suppose an adversaryA eavesdrops the message in the open channel, such as {Di,C1,Fij,SIDj}; then A replays the message flow to Sj. While without ri, A cannot construct a correct Vi to pass the verification of Sj. So A can neither gain any benefits from replaying the message nor be authenticated by Sj. Similarly, A also fails to carry out a replay attack on other message flows. Therefore, our scheme can resist replay attack.


#### 6.2.8. User Impersonation Attack

According to the analysis above, the adversaryA can neither guess IDi and PWi nor replay {Di,C1,Fij,SIDj} to impersonate Ui, so there is only one way left: constructing {Da,C1a,Fa,SIDj}. So A selects a random number ra and computes {C1a,C2a}, forges DIDa and Ka, then computes {Da,C1a,Fa,SIDj}, and sends it to RC. However, after RC computes C2a and obtains DIDa, RC either cannot find such a DIDa in User-list or computes Ka′ that is not equal to Ka. Both two conditions lead to the failure in authentication of Ui. That means that RC is bound to find that {Da,C1a,Fa,SIDj} is forged. Therefore, A cannot impersonate Ui.


#### 6.2.9. Server Impersonation Attack

On one hand, according to the analysis above, the adversaryA cannot replay the message flows to impersonate Sj; on the other hand, A finds no way to get the private key Skeyj. Thus our scheme is secure from server impersonation attack.


## 6.1. Formal Analysis Based on BAN Logic

As an efficient and simple way to analyze the design logic and security of the authentication scheme, BAN logic [40] has been widely used. As shown in Table 4, it uses some particular notions to depict a protocol.Table 4
Notations in BAN logic.
P ∣ ≡ X P believes X, that is, the principal P believes the statement X is true.  P ⊲ X P sees X, that is, the principal P receives a message that contains X.  P ∣ ⇒ X P has jurisdiction over X, that is, the principal P can generates or computes X.  P ∣ ~ X P said X, that is, the principal P has sent a message containing X.  ♯ ( X ) X is fresh, that is, X is sent in a message only at the current run of the protocol, it is usually a timestamp or a random number.  P ↔ K Q K is the shared key for P and Q.  P ⇌ Y Q Y is the secret known only to P and Q or some principals trusted by them.  〈 X 〉 Y X combined with Y, and Y usually is a secret.  { X } K X encrypted with K.  P∣≡P↔KQ,P⊲{X}KP∣≡Q∣~XorP∣≡P⇌YQ,P⊲〈X〉YP∣≡Q∣~X R U L E ( 1 ): the message-meaning rule. This rule will be used in the proving process.  P ∣ ≡ ♯ ( X ) , P ∣ ≡ Q ∣ ~ X P ∣ ≡ Q ∣ ≡ X R U L E ( 2 ): the nonce-verification rule. This rule will be used in the proving process.  P ∣ ≡ Q ∣ ⇒ X , P ∣ ≡ Q ∣ ≡ X P ∣ ≡ X R U L E ( 3 ): the jurisdiction rule. This rule will be used in the proving process.  P ∣ ≡ ♯ ( X ) P ∣ ≡ ♯ ( X , Y ) R U L E ( 4 ): the freshness-conjuncatenation rule. This rule will be used in the proving process.The goals of our proposed scheme are as follows: these four goals ensure that the server and the user get authenticated mutually (corresponding to our proposed S1, S10, and S13), and they build a session key successfully (corresponding to our proposed S14):(1)
Goal 1:Ui∣≡Sj∣≡(Ui↔SKSj).(2)
Goal 2:Ui∣≡(Ui↔SKSj).(3)
Goal 3:Sj∣≡Ui∣≡(Ui↔SKSj).(4)
Goal 4:Sj∣≡(Ui↔SKSj).According to the BAN logic, we first transform the scheme to an idealized one:M1: Ui→Sj: 〈DIDi,SIDj,C1,Ui↔C2RC〉Ui↔KiRC.M2: Sj→RC: 〈SIDj,Di,C1,Fij,n〉Sj↔SkeyjRC.M3: RC→Sj: 〈SIDj,n,Ui⇌PrcijSj〉Sj↔SkeyjRC.M4: Sj→Ui: 〈C1,C3,Ui↔SKSj〉Ui⇌PrcijSj.M5: Ui→Sj: 〈C3,Ui↔SKSj〉Ui↔C4Sj.Then, to analyze the scheme, we make some assumptions about its initial state as follows:H1: Ui∣≡♯(C1).H2: Sj∣≡♯(C3).H3: Sj∣≡♯(n).H4: Ui∣≡Ui↔KiRC.H5: RC∣≡Ui↔KiRC.H6: Ui∣≡Ui⇌PrcijSj.H7: Sj∣≡Sj↔SkeyjRC.H8: RC∣≡Sj↔SkeyjRC.H9: Sj∣≡Ui↔C4RC.H10: Ui∣≡Sj∣⇒Ui↔KiSj.H11: Sj∣≡Ui∣⇒Ui↔KiSj.H12: Sj∣≡RC∣⇒Ui⇌PrcijSj.Based on these assumptions above, we will prove the security of our protocol according to BAN logic as follows.From  M2, we have(2)S1:RC⊲SIDj,Di,C1,Fij,nSj↔SkeyjRC.Then according to H8,S1, RULE(1), it is obvious that(3)S2:RC∣≡Sj∣~SIDj,Di,C1,Fij,n.From  M1, we have(4)S3:RC⊲DIDi,SIDj,C1,Ui↔C2RCUi↔KiRC.Then according toH5, S3, RULE(1), it is obvious that (5)S4:RC∣≡Ui∣~DIDi,SIDj,C1,Ui↔C2RC.From  M3, we have (6)S5:Sj⊲SIDj,n,Ui⇌PrcijSjSj↔SkeyjRC.Then according toH7, S5, RULE(1), it is obvious that (7)S6:Sj∣≡RC∣~SIDj,n,Ui⇌PrcijSj.And according toH3, S6, RULE(4) and RULE(2), we get (8)S7:Sj∣≡RC∣~Ui⇌PrcijSj.And according toH12, S7, RULE(3), we can get (9)S8:Sj∣≡Ui⇌PrcijSj.From  M4, we have (10)S9:Ui⊲C1,C3,Ui↔SKSjUi⇌PrcijSj.Then according toH6, S9, RULE(1), it is obvious that(11)S10:Ui∣≡Sj∣~C1,C3,Ui↔SKSj.And according toH2, S10, RULE(4) and RULE(2), we get(12)S11:Ui∣≡Sj∣≡Ui↔SKSjGoal  1.And according toH10, S11, RULE(3), we can get(13)S12:Ui∣≡Ui↔SKSjGoal  2.From  M5, we have (14)S13:Sj⊲C3,Ui↔SKSjUi↔C4Sj.Then according toH9, S13, RULE(1), it is obvious that(15)S14:Sj∣≡Ui∣~C3,Ui↔SKSj.And according toH2, S13, RULE(4) and RULE(2), we get(16)S15:Sj∣≡Ui∣≡Ui↔SKSjGoal  3.And according toH11, S15, RULE(3), we can get(17)S16:Sj∣≡Ui↔SKSjGoal  4.Thus with Goals 1~4, we proved that the user Ui and the server Sj have authenticated to each other; furthermore they accepted and shared the session key SK.


## 6.2. Informal Analysis

The heuristic method without complex formula is a direct and simple way for a quick analysis of the security of the protocol. It plays a significant role in cryptoanalysis of authentication protocols, though its analytic process heavily depends on human experience rather than a set of scientific tools. This section uses a heuristic method to prove that our scheme not only provides desire attributes but also is resistant to various attacks.


### 6.2.1. User Anonymity

In our scheme, on one hand, the adversaryA cannot get IDi: the user identity was concealed in DIDi where DIDi=h(IDi∥bi), so an adversary without bi cannot guess the value of IDi via dictionary attack; on the other hand, A cannot link the message flows to a certain user: though DIDi is a fixed value, it is transmitted in a form of Di=DIDi⊕h(C1∥C2), where C1 and C2 are changed with different turns of the protocol, and only the user and the one knowing the long term secret key can compute C2. This indicates that Di is changed with C1 and C2, and A cannot get C2. Thus A fails to link the message flows to a certain user. So our scheme achieves user anonymity.


### 6.2.2. Forward Secrecy

The session keySK of the proposed scheme consists of two “special” parameters: Prcij and C4, where Prcij=h(DIDi∥C1∥C2) and C4=(C3)ri mod p=(C1)rj mod p=grirj mod p. Suppose that an adversary gets the secret key x, then he can intercept Di and C1 to compute DIDi and C2. However, computing C4 for A is equivalent to solving the DLP problem, which is bound to fail. So our scheme provides perfect forward security.


### 6.2.3. Mutual Authentication

In Step 3 of Section5.4, RC with x verifies the validity of Ui by checking Fij, if Ui is legitimate, RC computes Prcij and constructs Rrcij to Sj. So with the help of RC, Sj authenticates Ui. In a short, both RC and Sj authenticate Ui.In Step 3 of Section5.4, RC with Skeyj authenticates Sj by checking SIDj. If Sj passes the test, RC respond to Sj’s challenge n with Rrcij which is an encryption with the key h(Skeyj∥n). Then Sj verifies RC’s validity by checking Nrcij. Furthermore, with Prcij in Qji, Ui verifies RC and Sj. So all in all, Sj authenticates RC and Ui; Ui authenticates RC and Sj.Therefore, our scheme achieves mutual authentication.


### 6.2.4. Privileged Insider Attack

In the registration phase of our scheme,Ui submits {h(IDi∥bi),h(PWi∥bi)} to RC. From this message, RC learns nothing about Ui’s PWi or other useful information. Thus our scheme is resistant to privileged insider attack.


### 6.2.5. Off-Line Dictionary Attack

Suppose an adversaryA has the full control of the open channel and obtains the information in the smart card; then we prove that our scheme can resist the off-line dictionary attack through two aspects.On one hand, withEi and b~i, A guesses IDi and PWi to be IDi′ and PWi′, respectively. Then A computes bi′=b~i⊕h(IDi′∥PWi′), DIDi′=h(IDi′⊕bi′), PWRi′=h(PWi′∥bi′), then verifies the correctness of IDi′ and PWi′ by testing Ei?=h(h(DIDi′)⊕h(PWRi′)) mod n0, and repeats these processes till the equation is satisfied. However, even if A finds such a pair of IDi′,PWi′, he still is not sure whether IDi′==IDi and PWi′==PWi, for there are Dpw∗Did∖n0≈232 candidates of {IDi,PWi} pair when n0=28 and Dpw=Did=26 [2]. Then A has to verify {IDi′,PWi′} in a manner of online, which will be stopped by the Honey_List.On the other hand,A may try another way to conduct an off-line dictionary attack: obtaining b~i, Ci and {Di,C1,Fij,SIDj}, using Fij to check the correctness of the guessed IDi′ and PWi′, while A has to compute C2 which is impossible for the entity (except Ui) without x as we explained in Section 6.2.1.In conclusion, our scheme is secure to dictionary attack.


### 6.2.6. Verifier-Stolen Attack

In our scheme,RC maintains a User-list in form of {DIDi,yi,Trg,Hoeny_List} and a Server-list in form of {SIDj,TSrg}, while the parameters in the two list are not security-related. Thus an adversary with the verifier table has no security threat to the system.


### 6.2.7. Replay Attack

We apply the random number to prevent replay attack. Suppose an adversaryA eavesdrops the message in the open channel, such as {Di,C1,Fij,SIDj}; then A replays the message flow to Sj. While without ri, A cannot construct a correct Vi to pass the verification of Sj. So A can neither gain any benefits from replaying the message nor be authenticated by Sj. Similarly, A also fails to carry out a replay attack on other message flows. Therefore, our scheme can resist replay attack.


### 6.2.8. User Impersonation Attack

According to the analysis above, the adversaryA can neither guess IDi and PWi nor replay {Di,C1,Fij,SIDj} to impersonate Ui, so there is only one way left: constructing {Da,C1a,Fa,SIDj}. So A selects a random number ra and computes {C1a,C2a}, forges DIDa and Ka, then computes {Da,C1a,Fa,SIDj}, and sends it to RC. However, after RC computes C2a and obtains DIDa, RC either cannot find such a DIDa in User-list or computes Ka′ that is not equal to Ka. Both two conditions lead to the failure in authentication of Ui. That means that RC is bound to find that {Da,C1a,Fa,SIDj} is forged. Therefore, A cannot impersonate Ui.


### 6.2.9. Server Impersonation Attack

On one hand, according to the analysis above, the adversaryA cannot replay the message flows to impersonate Sj; on the other hand, A finds no way to get the private key Skeyj. Thus our scheme is secure from server impersonation attack.


## 6.2.1. User Anonymity

In our scheme, on one hand, the adversaryA cannot get IDi: the user identity was concealed in DIDi where DIDi=h(IDi∥bi), so an adversary without bi cannot guess the value of IDi via dictionary attack; on the other hand, A cannot link the message flows to a certain user: though DIDi is a fixed value, it is transmitted in a form of Di=DIDi⊕h(C1∥C2), where C1 and C2 are changed with different turns of the protocol, and only the user and the one knowing the long term secret key can compute C2. This indicates that Di is changed with C1 and C2, and A cannot get C2. Thus A fails to link the message flows to a certain user. So our scheme achieves user anonymity.


## 6.2.2. Forward Secrecy

The session keySK of the proposed scheme consists of two “special” parameters: Prcij and C4, where Prcij=h(DIDi∥C1∥C2) and C4=(C3)ri mod p=(C1)rj mod p=grirj mod p. Suppose that an adversary gets the secret key x, then he can intercept Di and C1 to compute DIDi and C2. However, computing C4 for A is equivalent to solving the DLP problem, which is bound to fail. So our scheme provides perfect forward security.


## 6.2.3. Mutual Authentication

In Step 3 of Section5.4, RC with x verifies the validity of Ui by checking Fij, if Ui is legitimate, RC computes Prcij and constructs Rrcij to Sj. So with the help of RC, Sj authenticates Ui. In a short, both RC and Sj authenticate Ui.In Step 3 of Section5.4, RC with Skeyj authenticates Sj by checking SIDj. If Sj passes the test, RC respond to Sj’s challenge n with Rrcij which is an encryption with the key h(Skeyj∥n). Then Sj verifies RC’s validity by checking Nrcij. Furthermore, with Prcij in Qji, Ui verifies RC and Sj. So all in all, Sj authenticates RC and Ui; Ui authenticates RC and Sj.Therefore, our scheme achieves mutual authentication.


## 6.2.4. Privileged Insider Attack

In the registration phase of our scheme,Ui submits {h(IDi∥bi),h(PWi∥bi)} to RC. From this message, RC learns nothing about Ui’s PWi or other useful information. Thus our scheme is resistant to privileged insider attack.


## 6.2.5. Off-Line Dictionary Attack

Suppose an adversaryA has the full control of the open channel and obtains the information in the smart card; then we prove that our scheme can resist the off-line dictionary attack through two aspects.On one hand, withEi and b~i, A guesses IDi and PWi to be IDi′ and PWi′, respectively. Then A computes bi′=b~i⊕h(IDi′∥PWi′), DIDi′=h(IDi′⊕bi′), PWRi′=h(PWi′∥bi′), then verifies the correctness of IDi′ and PWi′ by testing Ei?=h(h(DIDi′)⊕h(PWRi′)) mod n0, and repeats these processes till the equation is satisfied. However, even if A finds such a pair of IDi′,PWi′, he still is not sure whether IDi′==IDi and PWi′==PWi, for there are Dpw∗Did∖n0≈232 candidates of {IDi,PWi} pair when n0=28 and Dpw=Did=26 [2]. Then A has to verify {IDi′,PWi′} in a manner of online, which will be stopped by the Honey_List.On the other hand,A may try another way to conduct an off-line dictionary attack: obtaining b~i, Ci and {Di,C1,Fij,SIDj}, using Fij to check the correctness of the guessed IDi′ and PWi′, while A has to compute C2 which is impossible for the entity (except Ui) without x as we explained in Section 6.2.1.In conclusion, our scheme is secure to dictionary attack.


## 6.2.6. Verifier-Stolen Attack

In our scheme,RC maintains a User-list in form of {DIDi,yi,Trg,Hoeny_List} and a Server-list in form of {SIDj,TSrg}, while the parameters in the two list are not security-related. Thus an adversary with the verifier table has no security threat to the system.


## 6.2.7. Replay Attack

We apply the random number to prevent replay attack. Suppose an adversaryA eavesdrops the message in the open channel, such as {Di,C1,Fij,SIDj}; then A replays the message flow to Sj. While without ri, A cannot construct a correct Vi to pass the verification of Sj. So A can neither gain any benefits from replaying the message nor be authenticated by Sj. Similarly, A also fails to carry out a replay attack on other message flows. Therefore, our scheme can resist replay attack.


## 6.2.8. User Impersonation Attack

According to the analysis above, the adversaryA can neither guess IDi and PWi nor replay {Di,C1,Fij,SIDj} to impersonate Ui, so there is only one way left: constructing {Da,C1a,Fa,SIDj}. So A selects a random number ra and computes {C1a,C2a}, forges DIDa and Ka, then computes {Da,C1a,Fa,SIDj}, and sends it to RC. However, after RC computes C2a and obtains DIDa, RC either cannot find such a DIDa in User-list or computes Ka′ that is not equal to Ka. Both two conditions lead to the failure in authentication of Ui. That means that RC is bound to find that {Da,C1a,Fa,SIDj} is forged. Therefore, A cannot impersonate Ui.


## 6.2.9. Server Impersonation Attack

On one hand, according to the analysis above, the adversaryA cannot replay the message flows to impersonate Sj; on the other hand, A finds no way to get the private key Skeyj. Thus our scheme is secure from server impersonation attack.


## 7. Performance Analysis

In this section, we compared our scheme with other two-factor authentication schemes for multiserver environment [17–20, 41–43]. As shown in Table 5, the result manifests the advantages of the proposed scheme in security attributes. We can see that our scheme satisfied all the security attributes, and it is the best one among these schemes, though its computation overhead and communication cost are higher, while others [17–20, 41–43] have weaknesses more or less. Actually, according to Wang et al. [28, 32], the public key algorithm is the key to achieve user anonymity and resistance against off-line dictionary attack, while the public key algorithm is bound to cost more than symmetric algorithm. So these schemes [17–19, 43] only using the symmetric algorithm need less communication cost than our scheme, but they are definitely not secure. Among the compared schemes, only these schemes [20, 41, 42] are equipped with the public key algorithm. Both the schemes of Kumari et al. [41] and Irshad et al. [42] cost more than our scheme. And our scheme does not spend much more communication cost or computation overhead than Lix et al.’s, while achieving all the fourteen evaluation criteria (Lix et al.’s scheme only nine). As a matter of fact, certain communication cost is a must for achieving better security. We think that ensuring the security of the protocol is the most important goal for an authentication scheme; furthermore, our scheme actually does not significantly increase the computation overhead and communication cost. Therefore, compared to those schemes vulnerable to attacks, our scheme is more suitable to multiserver environment.Table 5
Performance comparison among relevant schemes in multiserver.
Computation overhead Communication cost The proposed fourteen evaluation criteria Login Authentication Login Authentication S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 Leu and Hsieh (2009) [19] 8TH 10TH 512 bits 384 bits √ × √ × √ × □ √ × × √ √ × √ Li et al. (2012) [20] T E+5TH 3 T E+9TH 1280 bits 1280 bits √ × √ √ √ × □ √ × √ √ √ × √ Amin (2012) [17] 3 T H 9 T H 768 bits 896 bits √ × √ × √ × √ × × √ √ √ × √ Maitra et al. (2016) [18] 6 T H 5 T S+14TH 640 bits 1280 bits √ × √ × √ × × × × √ √ × √ √ Kumari et al. (2017) [41] 2 T M+3TH 6 T M+15TH 2176 bits 9088 bits √ √ √ √ √ × √ √ × √ √ √ √ √ Irshad et al. (2017) [42] 3 T M+TS+5TH 10 T M+TS+10TH 2176 bits 4480 bits √ √ √ √ √ × □ √ × √ √ √ × √ Irshad et al. (2017) [43] 8 T H 2 T S+10TH 384 bits 512 bits √ × √ × √ × □ × × √ √ √ × √ Our scheme 2 T E+8TH 4 T E+4TS+16TH 1408 bits 1664 bits √ √ √ √ √ √ √ √ √ √ √ √ √ √ T E is the time of modular exponentiation operation, TM is the time of scalar multiplication on elliptic curve, TH is the time of hash computation, and TS is the time of symmetric encryption/decryption; TE≫TM≫TH>TS and the lightweight operation such as “XOR” and “||” can be ignored [2]. Let n0 be 32-bit long; let IDi, PWi, h(∗), output of symmetric encryption, timestamp, and random numbers be 128-bit long; let p, g, y be 1024-bit long [2]. √ means the property is satisfied; × means the property is not satisfied; □ means the property is not related to the scheme.


## 8. Conclusion

In this paper, firstly, we described the communication model and adversary model of multiserver environment, pointing out that some of the adversary capacities in many schemes are impractical and unreasonable. Then based on the works of pioneer contributors, we summarized fourteen security requirements for user authentication in multiserver environment. Secondly, according to the adversary model and security requirements, we demonstrated the weakness in the scheme of Amin and Maitra et al. Thirdly, to overcome the identified weaknesses, we proposed a new improved scheme for multiserver environment and proved its security via BAN logic and heuristic analysis. Furthermore, the comparison results showed the superiority of our scheme.



---

*Source: 9062675-2018-04-15.xml*