# An Enhanced User Authentication Protocol Based on Elliptic Curve Cryptosystem in Cloud Computing Environment

Authors: Chenyu Wang; Ke Ding; Bin Li; Yiming Zhao; Guoai Xu; Yanhui Guo; Ping Wang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

With the popularity of cloud computing, information security issues in the cloud environment are becoming more and more prominent. As the first line of defense to ensure cloud computing security, user authentication has attracted extensive attention. Though considerable efforts have been paid for a secure and practical authentication scheme in cloud computing environment, most attempts ended in failure. The design of a secure and efficient user authentication scheme for cloud computing remains a challenge on the one hand and user’s smart card or mobile devices are of limited resource; on the other hand, with the combination of cloud computing and the Internet of Things, applications in cloud environments often need to meet various security requirements and are vulnerable to more attacks. In 2018, Amin et al. proposed an enhanced user authentication scheme in cloud computing, hoping to overcome the identified security flaws of two previous schemes. However, after a scrutinization of their scheme, we revealed that it still suffers from the same attacks (such as no user anonymity, no forward secrecy, and being vulnerable to offline dictionary attack) as the two schemes they compromised. Consequently, we take the scheme of Amin et al. (2018) as a study case, we discussed the inherent reason and the corresponding solutions to authentication schemes for cloud computing environment in detail. Next, we not only proposed an enhanced secure and efficient scheme, but also explained the design rationales for a secure cloud environment protocol. Finally, we applied BAN logic and heuristic analysis to show the security of the protocol and compared our scheme with related schemes. The results manifest the superiority of our scheme.


---

## Body

## 1. Introduction

With the development of IT technology, cloud computing has become one of the hottest research directions in recent years. As a new type of service, cloud computing is rapidly integrated into our daily lives with its high scalability, high service efficiency, and low-cost charge [1]. It fundamentally changed the traditional model of service providers providing services and consumers’ access to resources: as a service provider (such as Google, Microsoft, Amazon) of cloud computing, it effectively improves the utilization of resources by centralizing the demands; consumers not only gain the convenience of using resources, but also reduce the using cost through paying on demand. Therefore, more and more big firms build their own cloud platforms and provide services, including Google App Engine, Amazon Web services, and IBM SmartCloud [2]. Furthermore, both the individuals and small companies enjoy the benefits of cloud services. Generally speaking, there are three kinds of cloud services: (1) Iaas, Infrastructure as a Service, which means providing user with the infrastructure such as storage and networks to use; (2) Paas, Platform as a Service, which means providing user with the platform to develop various applications; (3) Saas, Software as a Service, which means providing user with software applications [3, 4].However, with the increasing popularity of the cloud services, the security issues have become more prominent, how to protect user privacy and restrict data from being illegally accessed has become a challenging problem and research hotspot. The first step to solve these issues is user authentication which can verify the authenticity of communication participants. A secure user authentication scheme will firstly verify the authenticity of the user when he/she applies to access the cloud data; then to prevent a malicious cloud server trick users, the validity of the cloud server should be checked; once confirming the identity of the user and the cloud server, a session key will be established to encrypt the communication messages.Generally speaking, there are three ways to authenticate a user, which are based on the following:(1) what you know (such as the password); (2) what you have (such as the smart card); (3) who you are (such as the biometric characteristic: fingerprint and iris). Due to its simplicity and practicality, passwords have been used more widely. While a password-based authentication protocol has natural flaws, it cannot resist against offline dictionary guessing attacks. Consequently, as a factor to help enhance security, the smart card gets used [5–9]. A scheme combined two factors (such as the password and the smart card) is called two-factor user authentication scheme. The participants of the two-factor authentication scheme in cloud computing environment involves a user, a cloud server and a register authority. Note that among the three participants, only the register authority is trusted. At first, the user and the cloud server register to the register authority, respectively. Then the cloud server will send the user a smart card with some sensitive information and negotiate a shared secret parameter with the cloud server. Later on, when the user initiates an access request to the cloud server in login phase, the three participants will authenticate themselves to each other. If they all are authenticated, the user will be allowed to access the cloud server.Motivations. In 2013, Yang et al. [10] devoted to design a secure authentication scheme for cloud computing environment, while their scheme is vulnerable to dictionary attack. Then Yang et al. [11] proposed a new scheme; unfortunately, Chen et al. [12] then showed this scheme is not secure to insider attack and impersonation attack and proposed a new version which once again is broken by Wang et al. [13]. Wang et al. [13] pointed out that Chen et al.’s scheme [12] is subject to offline dictionary attack and impersonation attack. Most recently, Amin et al. [3] identified the security weaknesses in the schemes of Xue et al. [14] and Chuang et al. [15] by revealing the two schemes fail to provide user anonymity and forward secrecy while being not able to resist against offline password guessing attack and so on. Therefore, they designed a new scheme that claims to overcome the security flaws of the two schemes and be secure to various attacks. However, after a scrutinization of Amin et al.’s scheme, we found their scheme still cannot overcome their identified security threats.In these years, considerable efforts have been paid for a secure and practical authentication scheme in cloud computing environment, some typical schemes including [16–19], yet most of them are found having security flaws more or less. Designing of a secure authentication scheme for cloud computing environment is still a challenge. With the widespread use of cloud computing, the potential security threats will lead to greater harm. This unsatisfactory situation motivates us to explore the inherent reasons of the failure in those schemes, find the basic method to fix the security flaws, and design a robust and efficient user authentication protocol for cloud computing environment.Our contributions. Amin et al.’s scheme [3] is a very typical scheme which suffers from the common attacks, while the scheme’s structure is widely accepted. So we take Amin et al.’s protocol as a study case to elaborate the common issues (and its corresponding solutions) in most authentication schemes and provide rationales for designing a secure cloud environment protocol. In addition, based on the analysis, we design a secure authentication protocol. In a short, our contributions can be summarized as follows:(1)
We demonstrated that Amin et al.’s scheme [3] fails to achieve user anonymity and forward secrecy while being not able to resist against offline dictionary attack.(2)
We discussed the inherent reasons of the identified flaws and its corresponding solutions; furthermore, we realized the way of deploying a public key algorithm rightly is challenging. Therefore, we showed the essential points for deploying public key algorithms.(3)
We improved Amin et al.’s scheme from security and effectiveness two aspects, proved the security of our scheme via BAN logic and heuristic analysis and, finally, compared our scheme with other related schemes. The results show that our scheme is more suitable for cloud computing environment.The remainder of this paper is organized as follows: Section2 sketches complexity assumptions and extends adversary model; then, Amin et al.’s scheme is reviewed and analyzed in Section 3; in Section 4, we propose a secure scheme and elaborate on design rationales; Section 5 proves the security of our scheme; in Section 6, we compare our scheme with other related schemes; finally, the conclusion is drawn in Section 7.


## 2. Preliminary

This section introduces the preliminary of the whole paper, including complexity assumptions in designing a scheme and some notations and abbreviations.


### 2.1. Computational Problems

Given two large primesp and q, let Fp be a finite field, E/Fp be an elliptic curve over Fp, and G be a q-order subgroup of E/Fp. For α,β∈Zp∗ and a point P in G, we can define the discrete logarithm problem as follows:(1)
Elliptic curve discrete logarithm (ECDL) problem: given (P, αP), it is impossible to compute α within polynomial time.(2)
Elliptic curve computational Diffie-Hellman (ECCDH) problem: given (αP,βP), it is impossible to compute αβP within polynomial time.


### 2.2. Adversary Models

Understanding the adversary models is the most basic step to design and analyze a protocol. In 2015, Wang et al. [20] proposed the capabilities of adversary in distributed systems: (1) exhaust passwords and identities; (2) learn IDi when evaluating security strength; (3) control of the open communication channel; (4) learn PWi or extract information in the smart card; (5) acquire previous session keys; (6) know the long-term secret key x when considering forward secrecy. As both the distributed systems and the cloud computing systems have similar network environment, their adversary models are also similar too. Therefore, we adopt Wang et al.’s adversary models [20] which have been accepted by various schemes [21–23].


### 2.3. Notations and Abbreviations

As shown in Table1, we summarize the notations and abbreviations used in this paper.Table 1
Notations and abbreviations.
Symbol Description Ui i t h user CSj j t h cloud server RA the register authority A the adversary x the long term secret key ofRA y the secret key ofRA IDi identity ofUi PWi password ofUi SIDj identity ofCSj Skeyj shared key betweenGk and CSj ⊕ bitwise XOR operation ∥ concatenation operation h(⋅) one-way hash function → a common channel ⇒ a secure channel


## 2.1. Computational Problems

Given two large primesp and q, let Fp be a finite field, E/Fp be an elliptic curve over Fp, and G be a q-order subgroup of E/Fp. For α,β∈Zp∗ and a point P in G, we can define the discrete logarithm problem as follows:(1)
Elliptic curve discrete logarithm (ECDL) problem: given (P, αP), it is impossible to compute α within polynomial time.(2)
Elliptic curve computational Diffie-Hellman (ECCDH) problem: given (αP,βP), it is impossible to compute αβP within polynomial time.


## 2.2. Adversary Models

Understanding the adversary models is the most basic step to design and analyze a protocol. In 2015, Wang et al. [20] proposed the capabilities of adversary in distributed systems: (1) exhaust passwords and identities; (2) learn IDi when evaluating security strength; (3) control of the open communication channel; (4) learn PWi or extract information in the smart card; (5) acquire previous session keys; (6) know the long-term secret key x when considering forward secrecy. As both the distributed systems and the cloud computing systems have similar network environment, their adversary models are also similar too. Therefore, we adopt Wang et al.’s adversary models [20] which have been accepted by various schemes [21–23].


## 2.3. Notations and Abbreviations

As shown in Table1, we summarize the notations and abbreviations used in this paper.Table 1
Notations and abbreviations.
Symbol Description Ui i t h user CSj j t h cloud server RA the register authority A the adversary x the long term secret key ofRA y the secret key ofRA IDi identity ofUi PWi password ofUi SIDj identity ofCSj Skeyj shared key betweenGk and CSj ⊕ bitwise XOR operation ∥ concatenation operation h(⋅) one-way hash function → a common channel ⇒ a secure channel


## 3. Cryptanalysis of Amin et al.’s Scheme

After identifying the security pitfalls in other two user authentication schemes, Amin et al. [3] attempted to design a new light weight protocol in cloud computing environment. After analyzing their scheme using AVISPA tool, they claimed the new scheme achieves forward security while being resistant to various attacks. However, this section will show that, under the assumptions on adversary capabilities in Section 2.2, their scheme cannot provide forward security while being subject to two kinds of offline dictionary attacks [27] and so on. Thus their scheme is not a truly two-factor scheme. To address these issues, this section first reviews the scheme of Amin et al. and then analyzes Amin et al.’s scheme [3].


### 3.1. Review of Amin et al.’s Scheme

This section briefly reviews the scheme of Amin et al. [3]; their scheme consists of five phases. As the password change phase and identity update phase have little relevance, we omit them. Furthermore, we adjust some symbols of their scheme for the ease of reading and the unity of the paper.Registration Phase(1) Cloud Server Registration PhaseStep 1.
C S j ⇒ R A: {SIDj,d}.  d is a random number.Step 2.
R A ⇒ C S j: {Skeyj}.  RA computes PSIDj = hSIDj∥d, Skeyj = hPSIDj∥y.Step 3.
C S j keeps {Skeyj,d}.(2) User Registration PhaseStep 1.
U i ⇒ R A: {Ai,PIDi}. Ai = h(PWi∥b1), PIDi = h(IDi∥b2), bbi = b2⊕Ai where b1, b2 are two random number chosen by Ui.Step 2.
R A ⇒ U i: smart card {Ci,Ei,bbi,DP,h(·)}. RA calculates Ci = h(Ai∥PIDi), Di = h(PIDi∥x), Ei = Di⊕Ai.Step 3.
U i inputs DP,bbi into the card where DP = h(IDi∥PWi)⊕b1.Login and Authentication PhaseStep 1.
U i → C S j: {Gi,Fi,Zi,PIDi,TSi}. After Ui inputs IDi and PWi, the card computes b1∗ = DP⊕h(IDi∗∥PWi∗), Ai∗ = h(PWi∗∥b1∗), b2∗ = bbi⊕Ai∗, PIDi∗ = h(IDi∗∥b2∗), Ci∗ = h(Ai∗∥PIDi∗). If (Ci∗==Ci), the card produces a random number Ni (128 bit) and computes Di = Ei⊕Ai, Gi = h(PIDi∥SIDj∥Ni∥TSi∥Di), Fi = Di⊕Ni, Zi = SIDj⊕h(Di∥Ni).Step 2.
C S j → R A: {Ji,Ki,PSIDj,Gi,Fi,Zi,PIDi,TSi,TSj}. CSj first checks (TSj-TSi<ΔT), then selects a 128 bit random number Nj, and computes Ji = Skeyj⊕Nj, Ki = h(Nj∥Skeyj∥Gi∥TSj).Step 3.
R A → C S j: {Pcs,Rcs,Qcs,Vcs}. RA checks (TScs-TSj<ΔT∗) and computes Di = h(PIDi∥x), Ni∗ = Fi⊕Di, SIDj∗ = Zi⊕h(Di∥Ni∗), Gi∗ = h(PIDi∥SIDj∗∥Ni∗∥Di∥TSi).
If(Gi∗==Gi), compute Skeyj∗ = h(PSIDj∥y), Nj∗ = Skeyj∗⊕Ji, Ki∗=h(Skeyj∗∥Nj∗∥Gi∥TSj).
If(Ki∗==Ki), compute Pcs = Nj⊕Ncs⊕h(Ni∥Di), Rcs = Ni⊕Ncs⊕h(Skeyj∗∥Nj∗), SKcs = h(Ni⊕Nj⊕Ncs), Qcs = h((Nj⊕Ncs)∥SKcs), Vcs = h((Ni∥Ncs)∥SKcs)Step 4.
C S j → U i: {Pcs,Qcs}. CSj computes Wj = h(Skeyj∥Nj), Ni⊕Ncs=Rcs⊕Wj, SKj = h(Ni⊕Ncs⊕Nj), Vcs∗ = h((Ni⊕Ncs)∥SKj). If (Vcs∗≠Vcs), send Pcs,Qcs to Ui.Step 5.
U i computes Li= h(Ni∥Di), Nj⊕Ncs = Pcs⊕Li, SKi = h(Nj⊕Ncs⊕Ni), Qcs∗ = h((Nj⊕Ncs)∥SKi). If (Qcs∗==Qcs), the whole authentication phase finishes successfully.


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

Amin et al.’s scheme [3] does not point out the adversarial model, while, according to their attack on the scheme of Xue et al. [14] and Chuang et al. [15], we can infer their adversary model which is included into our model (see Section 2.2). Although Amin et al.’s scheme [3] provides many admirable features, such as changing password locally and high efficiency, it still suffers from various attacks like most authentication protocol in cloud computing environment. Therefore, their scheme is a typical case to show the security threat in cloud environment. Through Amin et al.’s scheme, we can get insight into the inherent reasons of the failure in other authentication protocols for cloud and, based on it, learn to design a secure one. In brief, this section, on one hand, demonstrates that Amin et al.’s scheme [3] is vulnerable to various attacks and, on the other hand, indicates the failure reasons of their scheme.Off-Line Dictionary Attack I. (i) The adversary’s capability: it obtains the message {Ci,Ei,bbi,DP} in Ui’s smart card.(ii) The attack steps:the steps are as follows.Step 1.
GuessPWi to be PWi∗, IDi to be IDi∗. Note that, it is quite realistic for A to obtain the password and identity simultaneously, because their spaces are limited [28].Step 2.
Computeb1∗ = DP⊕h(IDi∗∥PWi∗).Step 3.
ComputeAi∗ = h(PWi∗∥b1∗).Step 4.
Computeb2∗ = bbi⊕Ai∗.Step 5.
ComputePIDi∗ = h(IDi∗∥b2∗).Step 6.
ComputeCi∗ = h(Ai∗∥PIDi∗).Step 7.
Verify the correctness ofPWi and IDi by checking if (Ci∗=?Ci).Step 8.
Repeat steps1~6 until the correct values of PWi and IDi are found.(iii) The time complexity: O(|Dpw|∗|Did|∗4TH), where TH is the time of hash-function.Remark. Generally speaking, achieving two-factor security is the most essential requirement of a two-factor authentication protocol; that is, any one of the factors being broken will not trigger the security of another factor, which in turn threatens the entire system. In recent years, many protocols have tried to propose a secure two-factor security protocol, but most have failed. It was not until the work of Ma et al. [29] and Wang et al. [20, 30] did such a stagnant situation completely changed. In 2012, Ma et al. [29] pointed out that public key algorithm is necessary to design a secure two-factor authentication scheme; in 2015, Wang et al. [20] found that there is a conflict between changing password locally and resisting against smart card loss attack under the current technique; therefore, Wang et al. [30] put forward a way of “honeywords”+“fuzzy-verifier” to solve the conflict; in 2016, Wang et al. [27] further pointed out that there are two offline dictionary attacks and then combined with the results of [29, 30] and matched the corresponding solutions for each attack.In this paper, we follow the classification method of Wang et al. [27] and demonstrate that Amin et al.’s scheme [3] cannot resist against the two kinds of dictionary attack. Looking back at the above attack process, we can find that the key to the problem is that A can find the verification value Ci to check the correctness of the guessed result. According to Wang et al. [30], this issue can be settled with the integration of “fuzzy-verifier” and “honeywords”: let Ci = h(Ai∥PIDi∥Di) mod n0 where n0 is a integer (24≤n0≤28). The detailed explanation on this method can be found in Section IV of [30] or Section 5.2 of this paper.Off-Line Dictionary Attack II. (i) The adversary’s capability: (1) it eavesdrops on one of Ui’s login requests {Gi,Fi,Zi,PIDi,TSi} and (2) obtains the message {Ci,Ei,bbi,DP} in Ui’s smart card.(ii) The attack steps:the steps are as follows.Step 1.
GuessPWi to be PWi∗, IDi to be IDi∗.Step 2.
Computeb1∗ = DP⊕h(IDi∗∥PWi∗).Step 3.
ComputeAi∗ = h(PWi∗∥b1∗).Step 4.
ComputeDi∗ = Ei⊕Ai∗.Step 5.
ComputeNi∗ = Fi⊕Di∗.Step 6.
ComputeGi∗ = h(PIDi∥SIDj∥Ni∗∥TSi∥Di∗). Note that Amin et al. [3] view SIDj as a secret only known to the legitimate user. However, it not practical: A at least can register as a legitimate user to get SIDj.Step 7.
Verify the correctness ofPWi and IDi by checking if (Gi∗ == Gi).Step 8.
Repeat steps1~6 until the correct values of PWi and IDi are found.(iii) The time complexity: O(|Dpw|∗|Did|∗3TH).Remark. In this attack, the pivotal parameter is Gi. To adversary A, the only challenge in computing Gi is the value of Di which can be derived from (IDi,PWi), so once A guesses the value of (IDi,PWi), he/she can check the correctness of them via Gi. Now considering a situation where Gi consists of the secret shared Di and an another nonpublic dynamic parameter which should not be derived from (IDi,PWi). In this situation, A cannot use Gi to check the guessed value anymore, since there is another uncertain parameter besides Di. Consequently, constructing such a dynamic parameter which is known to Ui and RA is our critical step to address this attack. Taking into account the fact that Ma et al.’s emphasizes [29] on the necessity of lightweight public-key algorithm in designing a secure authentication protocol, we then apply a lightweight public-key algorithm to construct such a dynamic parameter. In addition, our specific ideas on solving this attack are shown in Section 4.User anonymity: these days user anonymity has become one of the security issues that people are widely concerned about, especially in the case of cloud computing and the Internet of Things that involve massive data. The adversary can acquire people’s sensitive personal information via various ways including analyzing the session transcript in the open channel when the services are accessed [31]. Moreover, with the development of the technology, the adversary may even trace users’ movement and learn the location of their home or company, which triggers a huge potential threat [32]. Under these circumstances, user anonymity is a pivotal attribute of the authentication scheme to protect user privacy.Generally speaking, user anonymity covers two aspects [31]: (1) user identity protection; (2) user untraceability. The former requires the scheme does not expose users’ identity; and the latter prevents an adversary from linking the session transcripts to a specific user or distinguishes the sessions sent by different users. This definition on user anonymity is widely applied in most authentication schemes [8, 24, 33, 34]. Unfortunately, in Amin et al.’s scheme, the parameter PIDi that identifies the user identity is a static value exposed in the insure channel, which means the adversary can trace Ui via PIDi. Consequently, Amin et al.’s scheme cannot provide user anonymity. As we can see, one of the keys to achieve user anonymity is concealing the real identity with a dynamic parameter. The way to implement this is called dynamic-ID technique [20]. According to Wang et al.’s suggestion [31], we can employ the dynamic-ID technique to protect user anonymity via applying a lightweight public-key algorithm to the authentication schemes as described in Section 4.Forward Secrecy. (i) The adversary’s capability: (1) it eavesdrops on {Fi,PIDi} and {Pcs} and (2) obtains the long-term key x.(ii) The attack steps:the steps are as follows.Step 1.
ComputeDi∗ = h(PIDi∥x).Step 2.
ComputeNi∗ = Fi⊕Di∗.Step 3.
ComputeLi∗ = h(Ni∗∥Di∗).Step 4.
Compute(Nj⊕Ncs)∗ = Li∗⊕Pcs.Step 5.
ComputeSK = h((Nj⊕Ncs)∗)⊕Ni∗.(iii) The time complexity:  O(|Dpw|∗|Did|∗3TH).Remark. In Amin et al.’ scheme [3], there are two secret keys (x,y) in the register authority. We have shown that the leakage of the long-term key x will lead to the exposure of previous sessions key. In the following attack, we can see that the leakage of y leading to the same question too. As a result, the use of two system parameters is of little significance but consumes resource.(i) The adversary’s capability: (1) it eavesdrops on {Ji,PSIDj} and {Rcs} and (2) obtains the secret key y.(ii) The attack steps:the steps are as follows.Step 1.
ComputeSkeyj∗ = h(PIDj∥y).Step 2.
ComputeNj∗ = Ji⊕Skeyj∗.Step 3.
ComputeWj∗ = h(Skeyj∗∥Nj).Step 4.
Compute(Ni⊕Ncs)∗ = Wj∗⊕Rcs.Step 5.
ComputeSK = h(Nj⊕(Ni⊕Ncs)∗).(iii) The time complexity:  O(|Dpw|∗|Did|∗3TH).Remark. When considering the forward secrecy, the adversary almost has the same capacity with RA except that A does not know the verifier-table. As a result, if RA can compute the session key according to the processes of the scheme, then A is very likely to break the session key. For the above considerations, we do not recommend that RA have the ability to calculate session keys. To achieve this, a public-key algorithm is suggested too [29]. In addition, the more concrete improved methods will be explained in Section 4.Other flaws: using timestamps to resist replay attack is not recommended. As we all know, due to the network congestion, network latency, or other issues, maintaining a consistent network clock between different systems is very difficult, which often results in the desynchronization attacks. As a matter of fact, many papers [20, 30] in their evaluation criteria pointed out that a protocol using timestamps cannot resist against desynchronization attacks. Furthermore, determining an appropriate value of Δt always faces many challenges in practice: if this value is too big, a replay attack occurs; if it is too small, a valid participant may be stopped. Therefore, in protocol design, the use of random numbers is usually a more recommended way. Unfortunately, the timestamps method was applied in Amin et al.’s scheme.Insecure identity update phase: similar to the process in “offline dictionary attack II” of Section3.2, an adversary can carry out an offline dictionary attack via using DDi or DDs as the verification parameter when Ui tries to update his/her identity.


## 3.1. Review of Amin et al.’s Scheme

This section briefly reviews the scheme of Amin et al. [3]; their scheme consists of five phases. As the password change phase and identity update phase have little relevance, we omit them. Furthermore, we adjust some symbols of their scheme for the ease of reading and the unity of the paper.Registration Phase(1) Cloud Server Registration PhaseStep 1.
C S j ⇒ R A: {SIDj,d}.  d is a random number.Step 2.
R A ⇒ C S j: {Skeyj}.  RA computes PSIDj = hSIDj∥d, Skeyj = hPSIDj∥y.Step 3.
C S j keeps {Skeyj,d}.(2) User Registration PhaseStep 1.
U i ⇒ R A: {Ai,PIDi}. Ai = h(PWi∥b1), PIDi = h(IDi∥b2), bbi = b2⊕Ai where b1, b2 are two random number chosen by Ui.Step 2.
R A ⇒ U i: smart card {Ci,Ei,bbi,DP,h(·)}. RA calculates Ci = h(Ai∥PIDi), Di = h(PIDi∥x), Ei = Di⊕Ai.Step 3.
U i inputs DP,bbi into the card where DP = h(IDi∥PWi)⊕b1.Login and Authentication PhaseStep 1.
U i → C S j: {Gi,Fi,Zi,PIDi,TSi}. After Ui inputs IDi and PWi, the card computes b1∗ = DP⊕h(IDi∗∥PWi∗), Ai∗ = h(PWi∗∥b1∗), b2∗ = bbi⊕Ai∗, PIDi∗ = h(IDi∗∥b2∗), Ci∗ = h(Ai∗∥PIDi∗). If (Ci∗==Ci), the card produces a random number Ni (128 bit) and computes Di = Ei⊕Ai, Gi = h(PIDi∥SIDj∥Ni∥TSi∥Di), Fi = Di⊕Ni, Zi = SIDj⊕h(Di∥Ni).Step 2.
C S j → R A: {Ji,Ki,PSIDj,Gi,Fi,Zi,PIDi,TSi,TSj}. CSj first checks (TSj-TSi<ΔT), then selects a 128 bit random number Nj, and computes Ji = Skeyj⊕Nj, Ki = h(Nj∥Skeyj∥Gi∥TSj).Step 3.
R A → C S j: {Pcs,Rcs,Qcs,Vcs}. RA checks (TScs-TSj<ΔT∗) and computes Di = h(PIDi∥x), Ni∗ = Fi⊕Di, SIDj∗ = Zi⊕h(Di∥Ni∗), Gi∗ = h(PIDi∥SIDj∗∥Ni∗∥Di∥TSi).
If(Gi∗==Gi), compute Skeyj∗ = h(PSIDj∥y), Nj∗ = Skeyj∗⊕Ji, Ki∗=h(Skeyj∗∥Nj∗∥Gi∥TSj).
If(Ki∗==Ki), compute Pcs = Nj⊕Ncs⊕h(Ni∥Di), Rcs = Ni⊕Ncs⊕h(Skeyj∗∥Nj∗), SKcs = h(Ni⊕Nj⊕Ncs), Qcs = h((Nj⊕Ncs)∥SKcs), Vcs = h((Ni∥Ncs)∥SKcs)Step 4.
C S j → U i: {Pcs,Qcs}. CSj computes Wj = h(Skeyj∥Nj), Ni⊕Ncs=Rcs⊕Wj, SKj = h(Ni⊕Ncs⊕Nj), Vcs∗ = h((Ni⊕Ncs)∥SKj). If (Vcs∗≠Vcs), send Pcs,Qcs to Ui.Step 5.
U i computes Li= h(Ni∥Di), Nj⊕Ncs = Pcs⊕Li, SKi = h(Nj⊕Ncs⊕Ni), Qcs∗ = h((Nj⊕Ncs)∥SKi). If (Qcs∗==Qcs), the whole authentication phase finishes successfully.


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

Amin et al.’s scheme [3] does not point out the adversarial model, while, according to their attack on the scheme of Xue et al. [14] and Chuang et al. [15], we can infer their adversary model which is included into our model (see Section 2.2). Although Amin et al.’s scheme [3] provides many admirable features, such as changing password locally and high efficiency, it still suffers from various attacks like most authentication protocol in cloud computing environment. Therefore, their scheme is a typical case to show the security threat in cloud environment. Through Amin et al.’s scheme, we can get insight into the inherent reasons of the failure in other authentication protocols for cloud and, based on it, learn to design a secure one. In brief, this section, on one hand, demonstrates that Amin et al.’s scheme [3] is vulnerable to various attacks and, on the other hand, indicates the failure reasons of their scheme.Off-Line Dictionary Attack I. (i) The adversary’s capability: it obtains the message {Ci,Ei,bbi,DP} in Ui’s smart card.(ii) The attack steps:the steps are as follows.Step 1.
GuessPWi to be PWi∗, IDi to be IDi∗. Note that, it is quite realistic for A to obtain the password and identity simultaneously, because their spaces are limited [28].Step 2.
Computeb1∗ = DP⊕h(IDi∗∥PWi∗).Step 3.
ComputeAi∗ = h(PWi∗∥b1∗).Step 4.
Computeb2∗ = bbi⊕Ai∗.Step 5.
ComputePIDi∗ = h(IDi∗∥b2∗).Step 6.
ComputeCi∗ = h(Ai∗∥PIDi∗).Step 7.
Verify the correctness ofPWi and IDi by checking if (Ci∗=?Ci).Step 8.
Repeat steps1~6 until the correct values of PWi and IDi are found.(iii) The time complexity: O(|Dpw|∗|Did|∗4TH), where TH is the time of hash-function.Remark. Generally speaking, achieving two-factor security is the most essential requirement of a two-factor authentication protocol; that is, any one of the factors being broken will not trigger the security of another factor, which in turn threatens the entire system. In recent years, many protocols have tried to propose a secure two-factor security protocol, but most have failed. It was not until the work of Ma et al. [29] and Wang et al. [20, 30] did such a stagnant situation completely changed. In 2012, Ma et al. [29] pointed out that public key algorithm is necessary to design a secure two-factor authentication scheme; in 2015, Wang et al. [20] found that there is a conflict between changing password locally and resisting against smart card loss attack under the current technique; therefore, Wang et al. [30] put forward a way of “honeywords”+“fuzzy-verifier” to solve the conflict; in 2016, Wang et al. [27] further pointed out that there are two offline dictionary attacks and then combined with the results of [29, 30] and matched the corresponding solutions for each attack.In this paper, we follow the classification method of Wang et al. [27] and demonstrate that Amin et al.’s scheme [3] cannot resist against the two kinds of dictionary attack. Looking back at the above attack process, we can find that the key to the problem is that A can find the verification value Ci to check the correctness of the guessed result. According to Wang et al. [30], this issue can be settled with the integration of “fuzzy-verifier” and “honeywords”: let Ci = h(Ai∥PIDi∥Di) mod n0 where n0 is a integer (24≤n0≤28). The detailed explanation on this method can be found in Section IV of [30] or Section 5.2 of this paper.Off-Line Dictionary Attack II. (i) The adversary’s capability: (1) it eavesdrops on one of Ui’s login requests {Gi,Fi,Zi,PIDi,TSi} and (2) obtains the message {Ci,Ei,bbi,DP} in Ui’s smart card.(ii) The attack steps:the steps are as follows.Step 1.
GuessPWi to be PWi∗, IDi to be IDi∗.Step 2.
Computeb1∗ = DP⊕h(IDi∗∥PWi∗).Step 3.
ComputeAi∗ = h(PWi∗∥b1∗).Step 4.
ComputeDi∗ = Ei⊕Ai∗.Step 5.
ComputeNi∗ = Fi⊕Di∗.Step 6.
ComputeGi∗ = h(PIDi∥SIDj∥Ni∗∥TSi∥Di∗). Note that Amin et al. [3] view SIDj as a secret only known to the legitimate user. However, it not practical: A at least can register as a legitimate user to get SIDj.Step 7.
Verify the correctness ofPWi and IDi by checking if (Gi∗ == Gi).Step 8.
Repeat steps1~6 until the correct values of PWi and IDi are found.(iii) The time complexity: O(|Dpw|∗|Did|∗3TH).Remark. In this attack, the pivotal parameter is Gi. To adversary A, the only challenge in computing Gi is the value of Di which can be derived from (IDi,PWi), so once A guesses the value of (IDi,PWi), he/she can check the correctness of them via Gi. Now considering a situation where Gi consists of the secret shared Di and an another nonpublic dynamic parameter which should not be derived from (IDi,PWi). In this situation, A cannot use Gi to check the guessed value anymore, since there is another uncertain parameter besides Di. Consequently, constructing such a dynamic parameter which is known to Ui and RA is our critical step to address this attack. Taking into account the fact that Ma et al.’s emphasizes [29] on the necessity of lightweight public-key algorithm in designing a secure authentication protocol, we then apply a lightweight public-key algorithm to construct such a dynamic parameter. In addition, our specific ideas on solving this attack are shown in Section 4.User anonymity: these days user anonymity has become one of the security issues that people are widely concerned about, especially in the case of cloud computing and the Internet of Things that involve massive data. The adversary can acquire people’s sensitive personal information via various ways including analyzing the session transcript in the open channel when the services are accessed [31]. Moreover, with the development of the technology, the adversary may even trace users’ movement and learn the location of their home or company, which triggers a huge potential threat [32]. Under these circumstances, user anonymity is a pivotal attribute of the authentication scheme to protect user privacy.Generally speaking, user anonymity covers two aspects [31]: (1) user identity protection; (2) user untraceability. The former requires the scheme does not expose users’ identity; and the latter prevents an adversary from linking the session transcripts to a specific user or distinguishes the sessions sent by different users. This definition on user anonymity is widely applied in most authentication schemes [8, 24, 33, 34]. Unfortunately, in Amin et al.’s scheme, the parameter PIDi that identifies the user identity is a static value exposed in the insure channel, which means the adversary can trace Ui via PIDi. Consequently, Amin et al.’s scheme cannot provide user anonymity. As we can see, one of the keys to achieve user anonymity is concealing the real identity with a dynamic parameter. The way to implement this is called dynamic-ID technique [20]. According to Wang et al.’s suggestion [31], we can employ the dynamic-ID technique to protect user anonymity via applying a lightweight public-key algorithm to the authentication schemes as described in Section 4.Forward Secrecy. (i) The adversary’s capability: (1) it eavesdrops on {Fi,PIDi} and {Pcs} and (2) obtains the long-term key x.(ii) The attack steps:the steps are as follows.Step 1.
ComputeDi∗ = h(PIDi∥x).Step 2.
ComputeNi∗ = Fi⊕Di∗.Step 3.
ComputeLi∗ = h(Ni∗∥Di∗).Step 4.
Compute(Nj⊕Ncs)∗ = Li∗⊕Pcs.Step 5.
ComputeSK = h((Nj⊕Ncs)∗)⊕Ni∗.(iii) The time complexity:  O(|Dpw|∗|Did|∗3TH).Remark. In Amin et al.’ scheme [3], there are two secret keys (x,y) in the register authority. We have shown that the leakage of the long-term key x will lead to the exposure of previous sessions key. In the following attack, we can see that the leakage of y leading to the same question too. As a result, the use of two system parameters is of little significance but consumes resource.(i) The adversary’s capability: (1) it eavesdrops on {Ji,PSIDj} and {Rcs} and (2) obtains the secret key y.(ii) The attack steps:the steps are as follows.Step 1.
ComputeSkeyj∗ = h(PIDj∥y).Step 2.
ComputeNj∗ = Ji⊕Skeyj∗.Step 3.
ComputeWj∗ = h(Skeyj∗∥Nj).Step 4.
Compute(Ni⊕Ncs)∗ = Wj∗⊕Rcs.Step 5.
ComputeSK = h(Nj⊕(Ni⊕Ncs)∗).(iii) The time complexity:  O(|Dpw|∗|Did|∗3TH).Remark. When considering the forward secrecy, the adversary almost has the same capacity with RA except that A does not know the verifier-table. As a result, if RA can compute the session key according to the processes of the scheme, then A is very likely to break the session key. For the above considerations, we do not recommend that RA have the ability to calculate session keys. To achieve this, a public-key algorithm is suggested too [29]. In addition, the more concrete improved methods will be explained in Section 4.Other flaws: using timestamps to resist replay attack is not recommended. As we all know, due to the network congestion, network latency, or other issues, maintaining a consistent network clock between different systems is very difficult, which often results in the desynchronization attacks. As a matter of fact, many papers [20, 30] in their evaluation criteria pointed out that a protocol using timestamps cannot resist against desynchronization attacks. Furthermore, determining an appropriate value of Δt always faces many challenges in practice: if this value is too big, a replay attack occurs; if it is too small, a valid participant may be stopped. Therefore, in protocol design, the use of random numbers is usually a more recommended way. Unfortunately, the timestamps method was applied in Amin et al.’s scheme.Insecure identity update phase: similar to the process in “offline dictionary attack II” of Section3.2, an adversary can carry out an offline dictionary attack via using DDi or DDs as the verification parameter when Ui tries to update his/her identity.


## 4. The Proposed Scheme

In this section, we design a secure, simple, and efficient user authentication scheme for cloud computing environment (as shown in Figures1 and 2) which overcomes all the flaws of Amin et al.’s scheme [3] but provides more attractive attributes, such as updating password and identity and user reregistering with same identity. As a matter of fact, we improve Amin et al.’s scheme from two aspects, efficiency and security. The designing rationales are sketched as follows.Figure 1
User registration phase.Figure 2
Login and authentication phase.(i) Improvements in Security. According to our discussion in Section 3.2, the public-key algorithm is indispensable to a secure two-factor user authentication scheme [20, 29, 31]. As a matter of fact, this theory has been widely accepted by massive new authentication schemes [26, 30, 35, 36], while the main difficulty lies in deploying the public key algorithm properly. Consequently, we will show the subtleties of deploying a public key algorithm in detail as follows.Note that, as its high efficiency, the elliptic curve cryptosystem has been used widely in authentication schemes [21, 37–39]. Therefore, our scheme deploys the elliptic curve algorithm to achieve our secure authentication scheme. Under this circumstance, compared with Amin et al.’s scheme [3], our scheme adds a parameter initialization process to set the parameters of elliptic curve cryptosystem.(1)
Apply public-key algorithm to resist against offline dictionary guessing attack II. In Section3.2, we have shown the pivotal point in addressing such an attack is to add a dynamic nonpublic parameter in Gi. Here we show the ideas about the way of achieving that, to Ui, the shared parameter Di between RA and Ui is an outcome derived by (IDi,PWi). So any parameter based on the transform of (IDi,PWi) is futile, as such an parameter is equivalent to Di. While, with the help of the public-key algorithm, Ui and RA can share a new parameter in every session. More specifically, Ui can choose a random number Ni, compute X1 = NiPub, X2 = NiP where Pub = xP, then let X1 be the dynamic parameter concealed in Gi. Note that, to Ui and RA, it is easy to compute X1, yet to A, there is another uncertain parameter in Gi, which stops A carrying out the offline dictionary attack II.(2)
Apply public-key algorithm to provide user anonymity. With the help ofX1, we conceal the identity related parameter PIDi in Fi as PIDi⊕h(X1). Since Fi is changed with Ni, user anonymity is provided. Note that X1 is the dynamic parameter we mention in “user anonymity” of Section 3.2.(3)
Apply public-key algorithm to achieve forward secrecy. We set the ECCDH problem in session key to achieve forward secrecy as follows: letSK consist of X3/Y3 where X3/Y3 = NiY2 = NiNjP = NjX2, Y2 = NjP. As a result, to the one (including RA) who does not know Ni/Nj, computing SK is equivalent to solve the ECCDH problem which cannot be solve in the polynomial time. Therefore, the forward secrecy is achieved.(4)
Following Wang et al.’s way [30] of resisting against offline dictionary attack I, as the detailed explanation on this method can be found in Section IV of [30], Section 6.2.4 of [24], or Section 5.2 of this paper, we do not repeat here.(ii) Improvements in Efficiency. Note that Amin et al.’s scheme [3] only involves some hash operation, while our scheme deploys a public-key algorithm, so the performance of our scheme is certainly not as efficient as Amin et al.’s scheme. However, except the increased cost of the public-key algorithm, we try to optimize other aspects of the performance in Amin et al.’s scheme through reducing unnecessary parameters or calculations as follows:(1)
Reduce the number of random numbers selected byUi to one during the user registration process. In Amin et al.’ scheme, there are two random numbers in the smart card. While they actually can derive from each other, in addition, the “ability” of computing them is the same, which means they are “equivalent”. As a result, using one random number is enough, which saves the storage space and computing resources.(2)
Reduce the number of secret keys inRA. As we see in Section 3.2, the secret key y is of little effect in improving the security. Furthermore, it makes the register phase of CSj and the authentication of CSj more complex. Therefore, we only set one system secret parameter and simplify the register phase of CSj. Such changes also bring other improvements on computing performance.


### 4.1. Registration

R A selects two large primes {p,q} and a medium integer n0 (24≤n0≤28). Let Fp be a finite field, E/Fp be an elliptic curve over Fp, and G be a q-order subgroup of E/Fp, then RA chooses a point P in G and a long-term secret key x∈Zp∗ and computes its public key Pub as xP. In our cloud computing environment, the cloud server and the user registration phases are conducted as follows.For the Cloud Server C S jStep 1.
C S j ⇒ R A: {SIDj}.Step 2.
R A ⇒ C S j: Skeyj = h(SIDj∥x).Step 3.
C S j stores Skeyj as a secret key.For the User U iStep 1.
U i ⇒ R A: {Ai,PIDi}. A new user Ui firstly selects the password PWi, identity IDi, and a random number bi as his/her personal information and then computes the registration parameters as follows: Ai = h(PWi∥bi), PIDi = h(IDi∥bi), and it initiates the registration phase via submitting the request {Ai,PIDi} to RA.Step 2.
R A ⇒ U i: a smart card with {Ci,Ei,Pub,n0,h(·)}. To guarantee the uniqueness of user identity, RA will firstly check whether the PIDi has been used via traverse user-list. If it is available, RA chooses a unique random number ri for Ui and computes Di = h(PIDi∥x∥ri), Ci = h(Ai∥PIDi∥Di) mod n0, Ei = Di⊕Ai, then inputs Ui related parameters {PIDi,ri,Honey_List=0} into User-list. Note that Honey_List will record the number of login failures. Finally RA accepts Ui’s registration through issuing him/she a smart card with {Ci,Ei,Pub,n0,h(·)}.Step 3.
U i inputs DP into the card where DP = h(IDi∥PWi)⊕bi.


### 4.2. Login phase

As shown in Figure1, if the user wants to access a cloud server, Ui will submit the information to prove his/her legitimacy in login phase. If the smart card has verified Ui’s legality, it initiates the access request to RA for Ui. In short, our login phase involves two aspects: (1) verifying the validity of Ui; (2) initiating the access request.Step 1.
U i → C S j: login request {Gi,Fi,Zi,X2}. Ui enters {IDi∗,PWi∗}, then the smart card computes bi∗ = DP⊕h(IDi∗∥PWi∗), Ai∗ = h(PWi∗∥bi∗), PIDi∗ = h(IDi∗∥bi∗), Di∗ = Ei⊕Ai∗, Ci∗ = h(Ai∗∥PIDi∗∥Di∗) mod n0. The card compares Ci∗ with the stored Ci to verify the valid Ui. If Ci∗≠Ci, exit the session.Step 2.
Otherwise, the card acceptsUi’s legitimacy and initiates an access request for Ui: select a random number Ni∈[1,q-1), computes X1 = NiPub, X2 = NiP, Gi = (PIDi∗∥SIDj∥X1∥Di∗), Fi = PIDi∗⊕h(X1∥X2), Zi = SIDj⊕h(Di∗∥X2), finally transmits {Gi,Fi,Zi,X2} to CSj.


### 4.3. Authentication Phase

Once getting the access request, theCSj will do some calculation to embed its unique parameters and transmit the request to RA for it is unable to check the authenticity of the request. Then RA will check the validity of the user and the cloud server, respectively, and help them to negotiate the session key. The whole authentication steps are as follows.Step 1.
C S j → R A: {Y2,Ki,PSIDj,Gi,Fi,Zi,X2}. CSj selects a random number Nj, computes Y1 = NjPub, Y2 = NjP, PIDj = SIDj⊕Y1, Ki = h(Y1∥Skeyj∥Gi∥X2∥Zi), then it sends {Y2,Ki,PSIDj,Gi,Fi,Zi,X2} to RA.Step 2.
R A → C S j: {Vcs,Qcs}. RA will firstly verify Ui via computing the predefined shared parameter Di and potential shared secret parameters X1: X1′ = xX2, PIDi′ = Fi⊕h(X1′), Di′ = h(PIDi′∥x∥ri) where ri is retrieved from the User-list through PIDi′, SIDj′ = Zi⊕h(Di′∥X2). If Ui’s Hoeny-List exceeds a predetermined secure value or the received Gi≠(PIDi′∥SIDj′∥X1′∥Di′), RA views Ui as an adversary and let Hoeny-List = Hoeny-List+1 (if it exceeds the preset value, RA will suspend the card till Ui reregisters), then rejects the request.
Otherwise,RA will continue to verify the authenticity of the cloud server as follows: calculate Y1′′ = xY2, SIDj′′ = PSIDj⊕Y1. If SIDj′′≠SIDj, exit (RA thinks CSj is not the server which Ui actually desires to access); otherwise, continue to compute Skeyj′′ = h(SIDj′′∥x), Ki′′ = h(Y1′′∥Skeyj′′∥Gi∥X2∥Zi). Finally, RA tests the authenticity of CSj by checking whether Ki′′=?Ki. If they are not equal, CSj does not pass RA’s authentication, the session will be terminated.
Otherwise,RA authenticates CSj and then help them to establish the session key as follows: computes Vcs = h(Y1′′∥Y2∥Skeyj′′∥X2), Qcs = h(X1′∥X2∥Di|Y2), then responds {Vcs,Qcs} to CSj.
Note thatVcs and Qcs are used to CSj and Ui, respectively. They are used to verify the authenticity of RA and then convince CSj/Ui that X2/Y2 is truly generated by Ui/CSj.Step 3.
C S j → U i: {Y2,Qcs}. CSj computes Vcs∗ = h(Y1∥Y2∥Skeyj∥X2), then check whether Vcs∗=?Vcs. If the equation is not satisfied, CSj rejects Ui’s request. Otherwise, CSj believes that Ui is a legitimate user who generates X2, then CSj computes the session key as SKj = h(Y2∥X2∥Y3) where Y3 = NjX2. Finally, CSj transmits {Y2,Qcs} to Ui.Step 4.
On receiving this message,Ui will firstly check the valid of RA via comparing h(X1∥X2∥Di∗∥Y2) with the received Qcs. If they are equal, Ui trusts RA and CSj, then he/she computes their shared session key as X3 = Ni·Y2 (= Ni·(Nj·P) = Y3), SKi = h(Y2∥X2∥X3). Till now, the authentication phase finishes successfully.


### 4.4. Password Change Phase

Considering the security and user friendliness, our password change phase is conducted locally, which guarantees the efficiency. In other words, the user can change his/her password freely even when he/she does not connect the Internet. All in all, our password change phase is performed as follows.Step 1.
U i enters IDi, PWi, and new password PWinew.Step 2.
The smart card verifiedUi’s authenticity as step 1 of Section 4.2. If Ui is authenticated, the card will carry out the password change process as step 3; otherwise, the card will reject this request.Step 3.
The smart card computes some new parameters for new password as follows:Ainew = h(PWinew∥bi∗), Einew = Ei⊕Ai∗⊕Ainew, DPnew = h(IDi∥PWinew)⊕bi∗, Cinew = h(Ainew∥PIDi∗∥Di∗) mod n0. Note that bi∗,Ai∗,Di∗,PIDi∗ is acquired in step 2. Finally, replace {Ci,Ei,DP} with {Cinew,Einew,DPnew}.


### 4.5. Identity Update Phase

Considering the following occasions, a user sets the phone number as his/her identity, then when the phone number is changed, the user may also want to update the identity. Therefore, similar to password change, the user also needs to change the identity in practice, although it happens less often. Thus we provide the identity update phase as follows.Step 1.
U i enters IDi, PWi, and new password IDinew.Step 2.
The smart card verifiedUi’s authenticity as step 1 of Section 4.2. If Ui is not authenticated, the card will reject the request; otherwise the identity update process proceeds.Step 3.
As thePIDi stored in RA is related to IDi, the identity update phase involves the interaction with RA. On this occasion, the smart card submits {X2,Gi,Fi,NPIDi} to RA for requesting update identity, where Ni is a random number, X1 = NiPub, X2 = NiP, Gi = h(PIDi∗∥X1∥Di∗∥PIDinew), Fi = PIDi∗⊕h(X1∥X2), PIDinew = h(IDinew∥bi∗), NPIDi = PIDinew⊕h(X1∥X2).Step 4.
R A shall verify the valid of Ui as follows: compute X1′ = xX2, PIDi′ = Fi⊕h(X1′), Di′ = h(PIDi′∥x∥ri) where ri is from User-list, PIDinew′ = NPIDi⊕h(X1∥X2). If the Hoeny-List exceeds a predetermined value or the received Gi≠(PIDi′∥X1′∥Di∗∥PIDinew′), RA rejects the request and sets Hoeny-List = Hoeny-List+1. Once it exceeds the preset value, suspend the card.
Otherwise,RA updates PIDi with PIDinew′ in User-list and sends {Mcs,NDi} to Ui where Mcs = h(PIDinew′∥PIDi′∥Di′∥X1′), Dinew = h(PIDinew′∥x), NDi = Dinew⊕h(X1′).Step 5.
After receivingMcs from RA, the smart card authenticates RA via testing Mcs=?h(PIDinew∥PIDi∗∥Di∗∥X1). If the equation does not hold, exit the session; otherwise, finish the identity update process: DPnew = h(IDinew∥PWi)⊕bi∗, Dinew′ = NDi⊕h(X1), Einew = Dinew′⊕Ai∗, Cinew = h(Ai∗∥PIDinew∥Dinew′) mod n0. Finally, replace {Ci,Ei,DP} with {Cinew,Einew,DPnew}.


### 4.6. Re-Register Phase

IfUi’s smart card is suspended, then he/she shall reregister to RA:Step 1.
U i ⇒ R A: {Ai,PIDi,re-register}.Step 2.
R A firstly finds PIDi in User-list and checks whether Ui’s card is suspended. If so, RA accepts the request and performs the register phase as Section 4.1.


## 4.1. Registration

R A selects two large primes {p,q} and a medium integer n0 (24≤n0≤28). Let Fp be a finite field, E/Fp be an elliptic curve over Fp, and G be a q-order subgroup of E/Fp, then RA chooses a point P in G and a long-term secret key x∈Zp∗ and computes its public key Pub as xP. In our cloud computing environment, the cloud server and the user registration phases are conducted as follows.For the Cloud Server C S jStep 1.
C S j ⇒ R A: {SIDj}.Step 2.
R A ⇒ C S j: Skeyj = h(SIDj∥x).Step 3.
C S j stores Skeyj as a secret key.For the User U iStep 1.
U i ⇒ R A: {Ai,PIDi}. A new user Ui firstly selects the password PWi, identity IDi, and a random number bi as his/her personal information and then computes the registration parameters as follows: Ai = h(PWi∥bi), PIDi = h(IDi∥bi), and it initiates the registration phase via submitting the request {Ai,PIDi} to RA.Step 2.
R A ⇒ U i: a smart card with {Ci,Ei,Pub,n0,h(·)}. To guarantee the uniqueness of user identity, RA will firstly check whether the PIDi has been used via traverse user-list. If it is available, RA chooses a unique random number ri for Ui and computes Di = h(PIDi∥x∥ri), Ci = h(Ai∥PIDi∥Di) mod n0, Ei = Di⊕Ai, then inputs Ui related parameters {PIDi,ri,Honey_List=0} into User-list. Note that Honey_List will record the number of login failures. Finally RA accepts Ui’s registration through issuing him/she a smart card with {Ci,Ei,Pub,n0,h(·)}.Step 3.
U i inputs DP into the card where DP = h(IDi∥PWi)⊕bi.


## 4.2. Login phase

As shown in Figure1, if the user wants to access a cloud server, Ui will submit the information to prove his/her legitimacy in login phase. If the smart card has verified Ui’s legality, it initiates the access request to RA for Ui. In short, our login phase involves two aspects: (1) verifying the validity of Ui; (2) initiating the access request.Step 1.
U i → C S j: login request {Gi,Fi,Zi,X2}. Ui enters {IDi∗,PWi∗}, then the smart card computes bi∗ = DP⊕h(IDi∗∥PWi∗), Ai∗ = h(PWi∗∥bi∗), PIDi∗ = h(IDi∗∥bi∗), Di∗ = Ei⊕Ai∗, Ci∗ = h(Ai∗∥PIDi∗∥Di∗) mod n0. The card compares Ci∗ with the stored Ci to verify the valid Ui. If Ci∗≠Ci, exit the session.Step 2.
Otherwise, the card acceptsUi’s legitimacy and initiates an access request for Ui: select a random number Ni∈[1,q-1), computes X1 = NiPub, X2 = NiP, Gi = (PIDi∗∥SIDj∥X1∥Di∗), Fi = PIDi∗⊕h(X1∥X2), Zi = SIDj⊕h(Di∗∥X2), finally transmits {Gi,Fi,Zi,X2} to CSj.


## 4.3. Authentication Phase

Once getting the access request, theCSj will do some calculation to embed its unique parameters and transmit the request to RA for it is unable to check the authenticity of the request. Then RA will check the validity of the user and the cloud server, respectively, and help them to negotiate the session key. The whole authentication steps are as follows.Step 1.
C S j → R A: {Y2,Ki,PSIDj,Gi,Fi,Zi,X2}. CSj selects a random number Nj, computes Y1 = NjPub, Y2 = NjP, PIDj = SIDj⊕Y1, Ki = h(Y1∥Skeyj∥Gi∥X2∥Zi), then it sends {Y2,Ki,PSIDj,Gi,Fi,Zi,X2} to RA.Step 2.
R A → C S j: {Vcs,Qcs}. RA will firstly verify Ui via computing the predefined shared parameter Di and potential shared secret parameters X1: X1′ = xX2, PIDi′ = Fi⊕h(X1′), Di′ = h(PIDi′∥x∥ri) where ri is retrieved from the User-list through PIDi′, SIDj′ = Zi⊕h(Di′∥X2). If Ui’s Hoeny-List exceeds a predetermined secure value or the received Gi≠(PIDi′∥SIDj′∥X1′∥Di′), RA views Ui as an adversary and let Hoeny-List = Hoeny-List+1 (if it exceeds the preset value, RA will suspend the card till Ui reregisters), then rejects the request.
Otherwise,RA will continue to verify the authenticity of the cloud server as follows: calculate Y1′′ = xY2, SIDj′′ = PSIDj⊕Y1. If SIDj′′≠SIDj, exit (RA thinks CSj is not the server which Ui actually desires to access); otherwise, continue to compute Skeyj′′ = h(SIDj′′∥x), Ki′′ = h(Y1′′∥Skeyj′′∥Gi∥X2∥Zi). Finally, RA tests the authenticity of CSj by checking whether Ki′′=?Ki. If they are not equal, CSj does not pass RA’s authentication, the session will be terminated.
Otherwise,RA authenticates CSj and then help them to establish the session key as follows: computes Vcs = h(Y1′′∥Y2∥Skeyj′′∥X2), Qcs = h(X1′∥X2∥Di|Y2), then responds {Vcs,Qcs} to CSj.
Note thatVcs and Qcs are used to CSj and Ui, respectively. They are used to verify the authenticity of RA and then convince CSj/Ui that X2/Y2 is truly generated by Ui/CSj.Step 3.
C S j → U i: {Y2,Qcs}. CSj computes Vcs∗ = h(Y1∥Y2∥Skeyj∥X2), then check whether Vcs∗=?Vcs. If the equation is not satisfied, CSj rejects Ui’s request. Otherwise, CSj believes that Ui is a legitimate user who generates X2, then CSj computes the session key as SKj = h(Y2∥X2∥Y3) where Y3 = NjX2. Finally, CSj transmits {Y2,Qcs} to Ui.Step 4.
On receiving this message,Ui will firstly check the valid of RA via comparing h(X1∥X2∥Di∗∥Y2) with the received Qcs. If they are equal, Ui trusts RA and CSj, then he/she computes their shared session key as X3 = Ni·Y2 (= Ni·(Nj·P) = Y3), SKi = h(Y2∥X2∥X3). Till now, the authentication phase finishes successfully.


## 4.4. Password Change Phase

Considering the security and user friendliness, our password change phase is conducted locally, which guarantees the efficiency. In other words, the user can change his/her password freely even when he/she does not connect the Internet. All in all, our password change phase is performed as follows.Step 1.
U i enters IDi, PWi, and new password PWinew.Step 2.
The smart card verifiedUi’s authenticity as step 1 of Section 4.2. If Ui is authenticated, the card will carry out the password change process as step 3; otherwise, the card will reject this request.Step 3.
The smart card computes some new parameters for new password as follows:Ainew = h(PWinew∥bi∗), Einew = Ei⊕Ai∗⊕Ainew, DPnew = h(IDi∥PWinew)⊕bi∗, Cinew = h(Ainew∥PIDi∗∥Di∗) mod n0. Note that bi∗,Ai∗,Di∗,PIDi∗ is acquired in step 2. Finally, replace {Ci,Ei,DP} with {Cinew,Einew,DPnew}.


## 4.5. Identity Update Phase

Considering the following occasions, a user sets the phone number as his/her identity, then when the phone number is changed, the user may also want to update the identity. Therefore, similar to password change, the user also needs to change the identity in practice, although it happens less often. Thus we provide the identity update phase as follows.Step 1.
U i enters IDi, PWi, and new password IDinew.Step 2.
The smart card verifiedUi’s authenticity as step 1 of Section 4.2. If Ui is not authenticated, the card will reject the request; otherwise the identity update process proceeds.Step 3.
As thePIDi stored in RA is related to IDi, the identity update phase involves the interaction with RA. On this occasion, the smart card submits {X2,Gi,Fi,NPIDi} to RA for requesting update identity, where Ni is a random number, X1 = NiPub, X2 = NiP, Gi = h(PIDi∗∥X1∥Di∗∥PIDinew), Fi = PIDi∗⊕h(X1∥X2), PIDinew = h(IDinew∥bi∗), NPIDi = PIDinew⊕h(X1∥X2).Step 4.
R A shall verify the valid of Ui as follows: compute X1′ = xX2, PIDi′ = Fi⊕h(X1′), Di′ = h(PIDi′∥x∥ri) where ri is from User-list, PIDinew′ = NPIDi⊕h(X1∥X2). If the Hoeny-List exceeds a predetermined value or the received Gi≠(PIDi′∥X1′∥Di∗∥PIDinew′), RA rejects the request and sets Hoeny-List = Hoeny-List+1. Once it exceeds the preset value, suspend the card.
Otherwise,RA updates PIDi with PIDinew′ in User-list and sends {Mcs,NDi} to Ui where Mcs = h(PIDinew′∥PIDi′∥Di′∥X1′), Dinew = h(PIDinew′∥x), NDi = Dinew⊕h(X1′).Step 5.
After receivingMcs from RA, the smart card authenticates RA via testing Mcs=?h(PIDinew∥PIDi∗∥Di∗∥X1). If the equation does not hold, exit the session; otherwise, finish the identity update process: DPnew = h(IDinew∥PWi)⊕bi∗, Dinew′ = NDi⊕h(X1), Einew = Dinew′⊕Ai∗, Cinew = h(Ai∗∥PIDinew∥Dinew′) mod n0. Finally, replace {Ci,Ei,DP} with {Cinew,Einew,DPnew}.


## 4.6. Re-Register Phase

IfUi’s smart card is suspended, then he/she shall reregister to RA:Step 1.
U i ⇒ R A: {Ai,PIDi,re-register}.Step 2.
R A firstly finds PIDi in User-list and checks whether Ui’s card is suspended. If so, RA accepts the request and performs the register phase as Section 4.1.


## 5. Security Analysis

In this section, we analyze the security of our scheme via two popular methods. The results demonstrate that our protocol is secure and effective for the cloud computing environment.


### 5.1. Formal Analysis Based on BAN Logic

In this section, we apply the BAN logic [40] which is a widely accepted way to analyze the design logic and security of the authentication scheme. Its particular notions to depict protocols are shown in Table 2.Table 2
Notations in BAN logic.
P ∣ ≡ X P believes X, i.e., the principal P believes the statement X is true.  P⊲X P sees X, i.e., the principal P receives a message that contains X.  P∣⇒X P has jurisdiction over X, i.e., the principal P can generates or computes X.  P∣~X P said X, i.e., the principal P has sent a message containing X.  ♯(X) X is fresh, i.e., X is sent in a message only at the current run of the protocol, it is usually a timestamp or a random number.  P⟷KQ K is the shared key for P and Q.  P⇌YQ 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.  XK X encrypted with K.  P ∣ ≡ P ⟷ K Q , P ⊲ { X } K P ∣ ≡ Q ∣ ~ X or P∣≡P⇌YQ,P⊲XYP∣≡Q∣~X R U L E ( 1 ): the message-meaning rule.  This rule will be used in the proving process.  P∣≡♯(X),P∣≡Q∣~XP∣≡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∣≡XP∣≡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.In BAN logic, the goals of our authentication scheme are defined as follows:(i)
Goal 1:Ui∣≡CSj∣≡(Ui⟷SKCSj).(ii)
Goal 2:Ui∣≡(Ui⟷SKCSj).(iii)
Goal 3:CSj∣≡Ui∣≡(Ui⟷SKCSj).(iv)
Goal 4:CSj∣≡(Ui⟷SKCSj).According to the proof steps in BAN logic, we redescribe our scheme into an idealized form:(i)
Message1: Ui→CSj: 〈X2,Gi,Fi,Zi,Ui⟷X1RA〉Ui⟷DiRA.(ii)
Message2: CSj→RA: 〈Message1,Y2,Ki,PSIDj〉CSj⟷SkeyjRA.(iii)
Message3: RA→CSj: 〈X2,Vcs,〈Qcs〉Di〉CSj⟷SkeyjRA.(iv)
Message4: CSj→Ui: 〈Y2,〈Qcs〉Di〉Ui⟷DiRA.Then, some assumptions are defined as follows:(i)
H1: Ui∣≡♯(X2).(ii)
H2: CSj∣≡♯(Y2).(iii)
H3: RA∣≡♯(X2).(iv)
H4: RA∣≡♯(Y2).(v)
H5: RA∣≡CSj⟷SkeyjRA.(vi)
H6: CSj∣≡CSj⟷SkeyjRA.(vii)
H7: RA∣≡Ui⟷DiRA.(viii)
H8: Ui∣≡Ui⟷DiRA.(ix)
H9: Ui∣≡CSj∣⇒Ui⟷SKCSj.(x)
H10: CSj∣≡Ui∣⇒Ui⟷SKCSj.Based on the definition above, we perform the BAN logic proof as follows:From M e s s a g e 2 (Message2 includes Message1), it is easy to get S1: RA⊲〈Message1,Y2,Ki,PSIDj〉Di.Then according toH7, S1, RULE(1), we get S2: RA∣≡Ui∣~〈X2,Gi,Fi,Zi,Ui⟷X1RA〉.According toH3 and RULE(4), we get S3: RA∣≡♯〈X2,Gi,Fi,Zi,Ui⟷X1RA〉.And according toS2, S3 and RULE(2), we get S4: RA∣≡Ui∣≡〈X2,Gi,Fi,Zi,Ui⟷X1RA〉.From the Message, we also getS5: CSj⊲〈Y2,Ki,PSIDj〉Skeyj.Then according toH7, S1, RULE(1), we get S6: CSj∣≡RA∣~〈Y2,Ki,PSIDj〉.According toH3 and RULE(4), we get S7: CSj∣≡♯〈Y2,Ki,PSIDj〉.And according toS2, S3 and RULE(2), we get S8: CSj∣≡RA∣≡〈Y2,Ki,PSIDj〉.From M e s s a g e 3, it is easy to get S9: RA⊲〈X2,Vcs,〈Qcs〉Di〉Skeyj.Then according toH7, S1, RULE(1), we get S10: RA∣≡CSj∣~〈X2,Vcs,〈Qcs〉Di〉.According toH3 and RULE(4), we get S11: RA∣≡♯〈X2,Vcs,〈Qcs〉Di〉.And according toS2, S3 and RULE(2), we get S12: RA∣≡CSj∣≡〈X2,Vcs,〈Qcs〉Di〉.From M e s s a g e 4, it is easy to get S13: Ui⊲〈Y2,〈Qcs〉Di〉Di.Then according toH7, S1, RULE(1), we get S14: Ui∣≡RA∣~〈Y2,〈Qcs〉Di〉.According toH3 and RULE(4), we get S15: Ui∣≡♯〈Y2,〈Qcs〉Di〉.And according toS2, S3 and RULE(2), we get S16: Ui∣≡RA∣≡〈Y2,〈Qcs〉Di〉.AsSK = h(Y2∥X2∥Ni·Y2), and combining S12, S16, we get: S17: Ui∣≡CSj∣≡Ui⟷SKCSj (Goal 1).Similarly, asSK = h(Y2∥X2∥Nj·X2), with S4, S8, we get S18: CSj∣≡Ui∣≡Ui⟷SKCSj (Goal 3).Finally, according toH2, S17, and RULE(3), we get S19: Ui∣≡(Ui⟷SKCSj) (Goal 2).And according toH10, S18, and RULE(3), we get S20: CSj∣≡(Ui⟷SKCSj) (Goal 4).In conclusion, our scheme achieves Goals 1~4, which promises (1)Ui and CSj have got authenticated mutually and (2) they negotiate the same session key SK.


### 5.2. Informal Analysis

Looking at the history of protocol designing, due to its simplicity and effectiveness, the heuristic method “still plays an important role” in cryptanalysis of protocols [20], though it does not have a theoretical form and relies on human experience heavily. Therefore, this section gives the security analysis via the heuristic method.User Anonymity. As we mentioned in Section 3.2, user anonymity contains two aspects, we prove our user anonymity attribute from two points.( 1 )  A has no chance to acquire IDi. In our scheme, the identity is transmitted in a form of Fi where Fi = PIDi⊕h(X1), PIDi = h(IDi∥bi), it is obvious that A has two challenges in computing IDi: firstly, computing PIDi from Fi; then guessing IDi from PIDi. The one only with Ni or x can compute h(X1) successfully, while A has no way to get this two parameters. Furthermore, even with PIDi, A still cannot conduct a guessing attack to compute IDi for A does not know bi.( 2 )  A cannot track the users: as we discussed above, the user’s related unique identification is concealed in Fi. It consists of a dynamic parameter X1 whose value depends on Ni; that is, Fi changes with Ni in every session. So A can neither links the sessions to a specific user nor tells whether the two sessions are sent by a same user.Therefore our scheme achieves user anonymity.Forward Secrecy. Forward secrecy requires that even the lon- term secret key was exposed, the previous session is still secure. In our scheme, the session key SK = h(Y2∥X2∥X3) where X3 = NiY2 = NjX2 = NiNjP. With the help of x, and the intercepted parameters X2 and Y2 from the open channel, if A wants to compute X3, then he/she has to solve the ECCDH problem which cannot be finished in the polynomial time. As a matter of fact, once getting x, A almost has the same capacity with RA. If RA cannot compute SK in the scheme, A is probably not able to. This again confirms our previous view: for the security consideration, we shall not let RA know SK. All in all, our enhanced scheme provides forward security.Mutual Authentication. Mutual authentication is the most basic requirement of a user authentication scheme. In our scheme, RA firstly authenticates Ui through Gi which contains their preset shared secret parameter Di and the dynamic parameter X1 generated by the public-key algorithm in step 2 of Section 4.2. Then RA authenticates CSj through Ki with their shared secret value Skeyj. In a short, RA authenticates Ui and CSj after this process.If both ofUi and Gi are authenticated, RA further computes Qcs and Vcs. Then in step 3 of Section 4.2, CSj checks the validity of RA via Vcs. If RA is authentic, then CSj believes RA’s judgment on Ui, which means that CSj also trusts the legitimacy of Ui. In conclusion, CSj authenticates RA and Ui via this process.On receivingQcs, Ui verifies RA with Qcs in step 4 of Section 4.2. If RA is authenticated, then Ui also believes the validity of CSj. Therefore, Ui authenticates RA and CSj.In conclusion, our scheme achieves mutual authentication.Privileged Insider Attack. To avoid privileged insider attack, when Ui registers to RA, he/she does not submit the identity or password directly, but a transform of them: {Ai,PIDi}. Thus the identity and password are protected by bi. Even the administrator of RA cannot get bi to conduct an offline dictionary attack to guess the value of IDi and PWi. Therefore, our scheme is secure against privileged insider attack.Offline Dictionary Attack. As we mentioned when analyzing Amin et al.’s scheme [3] in Section 3.2, there are two common offline dictionary attacks. So we consider two kinds of adversary here.Suppose an adversaryA acquires {Ci,Ei,DP,n0} in the smart card, then A may conduct an offline dictionary attack as follows.Step 1.
GuessIDi and PWi to be IDi∗ and PWi∗, respectively.Step 2.
Computebi∗ = DP⊕h(IDi∗∥PWi∗) Section 4.1.Step 3.
ComputeAi∗ = h(PWi∗∥bi∗).Step 4.
ComputePIDi∗ = h(IDi∗∥bi∗).Step 5.
ComputeDi∗ = Ei⊕Ai∗.Step 6.
ComputeCi∗ = h(Ai∗∥PIDi∗∥Di∗) mod n0.Step 7.
Verify the correctness ofPWi and IDi by checking if (Ci∗ == Ci).Step 8.
Repeat steps1~7 until the correct valued of PWi and IDi are found.Now we supposeA has found such a pair of {IDi∗,PWi∗} after the above steps. While, due to the properties of equation Ci, even the pair satisfies the equations, it is likely that they are not equal to {IDi,PWi}, since there are |Dpw|∗|Did|\n0≈232 candidates of {IDi,PWi} pair when n0=28 and |Dpw|=|Did|=26 [30]. Consequently, A needs to verify {IDi∗,PWi∗} online, but it will be restrained by Honey_List. Once the failure numbers of user login exceeds the preset value, the smart card will be suspended. Accordingly, our scheme is secure against such an attack scenario.Suppose an adversaryA not only extracts the message in smart card, but also eavesdrops {Gi,Fi,Zi,X2} from the open channel, then A attempts to guess PWi and IDi. In this occasion, A wants to use Gi as the verification parameter to check the correctness of the guessed value of {PWi,IDi}. As Gi consists of PIDi, SIDj, X1 and Di, and according to our attack steps 1~5 above, A can compute the value of PIDi∗ and Di∗. Then A computes SIDj∗ as Zi⊕h(Di∗∥X2). Now A only needs to compute X1. While without x or Ni, computing X1 is equivalent to solving the ECDL problem which cannot be finished in the polynomial time. As a result, our scheme can prevent such an adversary.In conclusion, the proposed scheme is secure against dictionary attack.Verifier-Stolen Attack. In our scheme, RA only needs to maintain the User-list whose elements ({PIDi,ri,Hoeny_List}) are not security-related. Furthermore, even A steals User-list, he/she will learn nothing useful information to conduct an attack. Thus our scheme is resistant to verifier-stolen attack.Replay Attack. We prevent the replay attack via the random numbers to prevent replay attack. We take one of the message flow {Gi,Fi,Zi,X2} as an example to explain: suppose A eavesdrops {Gi,Fi,Zi,X2}, then replays it to CSj. While A does not know Ni, he/she cannot compute the correct session key though the replayed message can pass the verification of RA. Consequently, A gain no benefits from such an attack. Equally, it makes no sense for A to replay other message flows. Accordingly, our scheme is secure against replay attack.User Impersonation Attack. According to the definition on user impersonation attack in [24], A does not acquire the smart card (this condition is included in “offline dictionary attack”) here. As we analyzed above, A with smart card can neither guess IDi and PWi nor replay {Gi,Fi,Zi,X2} to impersonate Ui, let alone the adversary without smart card. So there is only one possible method left: constructing {Ga,Fa,Za,X2a}. To construct this message, A chooses Na, computes {X1a,X2a}, forges PIDa and Da, calculates {Ga,Fa,Za,X2a}, and finally sends it to RA. However, after RA gets C2a, and PIDa, RA may fail to find such a PIDa in User-list or computes a Da′ unequal to Da, both the two conditions lead to the failure in the authentication of Ui. As a result, RA finds that A is not a legitimate user, the attack fails.Server Impersonation Attack. According to the above analysis, A can neither conducts the replay attack to impersonate CSj/RA nor finds ways to compute Skeyj/x, so A cannot impersonate CSj/RA.


## 5.1. Formal Analysis Based on BAN Logic

In this section, we apply the BAN logic [40] which is a widely accepted way to analyze the design logic and security of the authentication scheme. Its particular notions to depict protocols are shown in Table 2.Table 2
Notations in BAN logic.
P ∣ ≡ X P believes X, i.e., the principal P believes the statement X is true.  P⊲X P sees X, i.e., the principal P receives a message that contains X.  P∣⇒X P has jurisdiction over X, i.e., the principal P can generates or computes X.  P∣~X P said X, i.e., the principal P has sent a message containing X.  ♯(X) X is fresh, i.e., X is sent in a message only at the current run of the protocol, it is usually a timestamp or a random number.  P⟷KQ K is the shared key for P and Q.  P⇌YQ 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.  XK X encrypted with K.  P ∣ ≡ P ⟷ K Q , P ⊲ { X } K P ∣ ≡ Q ∣ ~ X or P∣≡P⇌YQ,P⊲XYP∣≡Q∣~X R U L E ( 1 ): the message-meaning rule.  This rule will be used in the proving process.  P∣≡♯(X),P∣≡Q∣~XP∣≡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∣≡XP∣≡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.In BAN logic, the goals of our authentication scheme are defined as follows:(i)
Goal 1:Ui∣≡CSj∣≡(Ui⟷SKCSj).(ii)
Goal 2:Ui∣≡(Ui⟷SKCSj).(iii)
Goal 3:CSj∣≡Ui∣≡(Ui⟷SKCSj).(iv)
Goal 4:CSj∣≡(Ui⟷SKCSj).According to the proof steps in BAN logic, we redescribe our scheme into an idealized form:(i)
Message1: Ui→CSj: 〈X2,Gi,Fi,Zi,Ui⟷X1RA〉Ui⟷DiRA.(ii)
Message2: CSj→RA: 〈Message1,Y2,Ki,PSIDj〉CSj⟷SkeyjRA.(iii)
Message3: RA→CSj: 〈X2,Vcs,〈Qcs〉Di〉CSj⟷SkeyjRA.(iv)
Message4: CSj→Ui: 〈Y2,〈Qcs〉Di〉Ui⟷DiRA.Then, some assumptions are defined as follows:(i)
H1: Ui∣≡♯(X2).(ii)
H2: CSj∣≡♯(Y2).(iii)
H3: RA∣≡♯(X2).(iv)
H4: RA∣≡♯(Y2).(v)
H5: RA∣≡CSj⟷SkeyjRA.(vi)
H6: CSj∣≡CSj⟷SkeyjRA.(vii)
H7: RA∣≡Ui⟷DiRA.(viii)
H8: Ui∣≡Ui⟷DiRA.(ix)
H9: Ui∣≡CSj∣⇒Ui⟷SKCSj.(x)
H10: CSj∣≡Ui∣⇒Ui⟷SKCSj.Based on the definition above, we perform the BAN logic proof as follows:From M e s s a g e 2 (Message2 includes Message1), it is easy to get S1: RA⊲〈Message1,Y2,Ki,PSIDj〉Di.Then according toH7, S1, RULE(1), we get S2: RA∣≡Ui∣~〈X2,Gi,Fi,Zi,Ui⟷X1RA〉.According toH3 and RULE(4), we get S3: RA∣≡♯〈X2,Gi,Fi,Zi,Ui⟷X1RA〉.And according toS2, S3 and RULE(2), we get S4: RA∣≡Ui∣≡〈X2,Gi,Fi,Zi,Ui⟷X1RA〉.From the Message, we also getS5: CSj⊲〈Y2,Ki,PSIDj〉Skeyj.Then according toH7, S1, RULE(1), we get S6: CSj∣≡RA∣~〈Y2,Ki,PSIDj〉.According toH3 and RULE(4), we get S7: CSj∣≡♯〈Y2,Ki,PSIDj〉.And according toS2, S3 and RULE(2), we get S8: CSj∣≡RA∣≡〈Y2,Ki,PSIDj〉.From M e s s a g e 3, it is easy to get S9: RA⊲〈X2,Vcs,〈Qcs〉Di〉Skeyj.Then according toH7, S1, RULE(1), we get S10: RA∣≡CSj∣~〈X2,Vcs,〈Qcs〉Di〉.According toH3 and RULE(4), we get S11: RA∣≡♯〈X2,Vcs,〈Qcs〉Di〉.And according toS2, S3 and RULE(2), we get S12: RA∣≡CSj∣≡〈X2,Vcs,〈Qcs〉Di〉.From M e s s a g e 4, it is easy to get S13: Ui⊲〈Y2,〈Qcs〉Di〉Di.Then according toH7, S1, RULE(1), we get S14: Ui∣≡RA∣~〈Y2,〈Qcs〉Di〉.According toH3 and RULE(4), we get S15: Ui∣≡♯〈Y2,〈Qcs〉Di〉.And according toS2, S3 and RULE(2), we get S16: Ui∣≡RA∣≡〈Y2,〈Qcs〉Di〉.AsSK = h(Y2∥X2∥Ni·Y2), and combining S12, S16, we get: S17: Ui∣≡CSj∣≡Ui⟷SKCSj (Goal 1).Similarly, asSK = h(Y2∥X2∥Nj·X2), with S4, S8, we get S18: CSj∣≡Ui∣≡Ui⟷SKCSj (Goal 3).Finally, according toH2, S17, and RULE(3), we get S19: Ui∣≡(Ui⟷SKCSj) (Goal 2).And according toH10, S18, and RULE(3), we get S20: CSj∣≡(Ui⟷SKCSj) (Goal 4).In conclusion, our scheme achieves Goals 1~4, which promises (1)Ui and CSj have got authenticated mutually and (2) they negotiate the same session key SK.


## 5.2. Informal Analysis

Looking at the history of protocol designing, due to its simplicity and effectiveness, the heuristic method “still plays an important role” in cryptanalysis of protocols [20], though it does not have a theoretical form and relies on human experience heavily. Therefore, this section gives the security analysis via the heuristic method.User Anonymity. As we mentioned in Section 3.2, user anonymity contains two aspects, we prove our user anonymity attribute from two points.( 1 )  A has no chance to acquire IDi. In our scheme, the identity is transmitted in a form of Fi where Fi = PIDi⊕h(X1), PIDi = h(IDi∥bi), it is obvious that A has two challenges in computing IDi: firstly, computing PIDi from Fi; then guessing IDi from PIDi. The one only with Ni or x can compute h(X1) successfully, while A has no way to get this two parameters. Furthermore, even with PIDi, A still cannot conduct a guessing attack to compute IDi for A does not know bi.( 2 )  A cannot track the users: as we discussed above, the user’s related unique identification is concealed in Fi. It consists of a dynamic parameter X1 whose value depends on Ni; that is, Fi changes with Ni in every session. So A can neither links the sessions to a specific user nor tells whether the two sessions are sent by a same user.Therefore our scheme achieves user anonymity.Forward Secrecy. Forward secrecy requires that even the lon- term secret key was exposed, the previous session is still secure. In our scheme, the session key SK = h(Y2∥X2∥X3) where X3 = NiY2 = NjX2 = NiNjP. With the help of x, and the intercepted parameters X2 and Y2 from the open channel, if A wants to compute X3, then he/she has to solve the ECCDH problem which cannot be finished in the polynomial time. As a matter of fact, once getting x, A almost has the same capacity with RA. If RA cannot compute SK in the scheme, A is probably not able to. This again confirms our previous view: for the security consideration, we shall not let RA know SK. All in all, our enhanced scheme provides forward security.Mutual Authentication. Mutual authentication is the most basic requirement of a user authentication scheme. In our scheme, RA firstly authenticates Ui through Gi which contains their preset shared secret parameter Di and the dynamic parameter X1 generated by the public-key algorithm in step 2 of Section 4.2. Then RA authenticates CSj through Ki with their shared secret value Skeyj. In a short, RA authenticates Ui and CSj after this process.If both ofUi and Gi are authenticated, RA further computes Qcs and Vcs. Then in step 3 of Section 4.2, CSj checks the validity of RA via Vcs. If RA is authentic, then CSj believes RA’s judgment on Ui, which means that CSj also trusts the legitimacy of Ui. In conclusion, CSj authenticates RA and Ui via this process.On receivingQcs, Ui verifies RA with Qcs in step 4 of Section 4.2. If RA is authenticated, then Ui also believes the validity of CSj. Therefore, Ui authenticates RA and CSj.In conclusion, our scheme achieves mutual authentication.Privileged Insider Attack. To avoid privileged insider attack, when Ui registers to RA, he/she does not submit the identity or password directly, but a transform of them: {Ai,PIDi}. Thus the identity and password are protected by bi. Even the administrator of RA cannot get bi to conduct an offline dictionary attack to guess the value of IDi and PWi. Therefore, our scheme is secure against privileged insider attack.Offline Dictionary Attack. As we mentioned when analyzing Amin et al.’s scheme [3] in Section 3.2, there are two common offline dictionary attacks. So we consider two kinds of adversary here.Suppose an adversaryA acquires {Ci,Ei,DP,n0} in the smart card, then A may conduct an offline dictionary attack as follows.Step 1.
GuessIDi and PWi to be IDi∗ and PWi∗, respectively.Step 2.
Computebi∗ = DP⊕h(IDi∗∥PWi∗) Section 4.1.Step 3.
ComputeAi∗ = h(PWi∗∥bi∗).Step 4.
ComputePIDi∗ = h(IDi∗∥bi∗).Step 5.
ComputeDi∗ = Ei⊕Ai∗.Step 6.
ComputeCi∗ = h(Ai∗∥PIDi∗∥Di∗) mod n0.Step 7.
Verify the correctness ofPWi and IDi by checking if (Ci∗ == Ci).Step 8.
Repeat steps1~7 until the correct valued of PWi and IDi are found.Now we supposeA has found such a pair of {IDi∗,PWi∗} after the above steps. While, due to the properties of equation Ci, even the pair satisfies the equations, it is likely that they are not equal to {IDi,PWi}, since there are |Dpw|∗|Did|\n0≈232 candidates of {IDi,PWi} pair when n0=28 and |Dpw|=|Did|=26 [30]. Consequently, A needs to verify {IDi∗,PWi∗} online, but it will be restrained by Honey_List. Once the failure numbers of user login exceeds the preset value, the smart card will be suspended. Accordingly, our scheme is secure against such an attack scenario.Suppose an adversaryA not only extracts the message in smart card, but also eavesdrops {Gi,Fi,Zi,X2} from the open channel, then A attempts to guess PWi and IDi. In this occasion, A wants to use Gi as the verification parameter to check the correctness of the guessed value of {PWi,IDi}. As Gi consists of PIDi, SIDj, X1 and Di, and according to our attack steps 1~5 above, A can compute the value of PIDi∗ and Di∗. Then A computes SIDj∗ as Zi⊕h(Di∗∥X2). Now A only needs to compute X1. While without x or Ni, computing X1 is equivalent to solving the ECDL problem which cannot be finished in the polynomial time. As a result, our scheme can prevent such an adversary.In conclusion, the proposed scheme is secure against dictionary attack.Verifier-Stolen Attack. In our scheme, RA only needs to maintain the User-list whose elements ({PIDi,ri,Hoeny_List}) are not security-related. Furthermore, even A steals User-list, he/she will learn nothing useful information to conduct an attack. Thus our scheme is resistant to verifier-stolen attack.Replay Attack. We prevent the replay attack via the random numbers to prevent replay attack. We take one of the message flow {Gi,Fi,Zi,X2} as an example to explain: suppose A eavesdrops {Gi,Fi,Zi,X2}, then replays it to CSj. While A does not know Ni, he/she cannot compute the correct session key though the replayed message can pass the verification of RA. Consequently, A gain no benefits from such an attack. Equally, it makes no sense for A to replay other message flows. Accordingly, our scheme is secure against replay attack.User Impersonation Attack. According to the definition on user impersonation attack in [24], A does not acquire the smart card (this condition is included in “offline dictionary attack”) here. As we analyzed above, A with smart card can neither guess IDi and PWi nor replay {Gi,Fi,Zi,X2} to impersonate Ui, let alone the adversary without smart card. So there is only one possible method left: constructing {Ga,Fa,Za,X2a}. To construct this message, A chooses Na, computes {X1a,X2a}, forges PIDa and Da, calculates {Ga,Fa,Za,X2a}, and finally sends it to RA. However, after RA gets C2a, and PIDa, RA may fail to find such a PIDa in User-list or computes a Da′ unequal to Da, both the two conditions lead to the failure in the authentication of Ui. As a result, RA finds that A is not a legitimate user, the attack fails.Server Impersonation Attack. According to the above analysis, A can neither conducts the replay attack to impersonate CSj/RA nor finds ways to compute Skeyj/x, so A cannot impersonate CSj/RA.


## 6. Performance Analysis

Some schemes like [41] which involve only two participants is essentially indistinguishable from the traditional client-server architecture and does not apply to cloud computing environments with multiple servers. Some schemes like [42] which are more concerned with authentication issues between wearable and smart phone belong to entity authentication rather than the user authentication discussed in this article. These schemes are not comparable to ours. Therefore, we only compare those having similar system architectures and application scenarios including [3, 25, 26].As shown in Table3, our security performance is obviously superior to other protocols: the proposed scheme achieves all security requirements, while others have more or less security flaws. More specifically, both the schemes of Maitra et al. [25] and Amin et al. [3] fail to achieve user anonymity and forward secrecy and cannot resist against offline dictionary attack, etc. The best one is Kumari et al.’s scheme [26] which can only provide 11 items of security requirements. In terms of computation or communication performance, as we mentioned in Section 4, the schemes only involving one-way hash operation are inevitable cost less in communication and computation than those deploying the public-key algorithm, but they certainly cannot guarantee the security of authentication. Therefore, among the compared schemes, the schemes of Amin et al. [3] and Maitra et al. [25] certainly cost less communication time and load for they only involve some one-way hash operations. However, sacrificing security to achieve high performance is inadvisable in authentication protocols. As a matter of fact, certain cost is unavoidable for security. Then compared with Kumari et al.’s scheme [26] which is equipped with public-key algorithm, our scheme costs 1ms in login phase and 2ms in authentication phase, while theirs is 2.3ms and 7ms, respectively, our computation overhead is better. Furthermore, our communication cost (1408bits in login phase and 4096 bits in authentication phase) is also lower than theirs (2176 bits and 9088 bits). In conclusion, our scheme with all security attributes is more suitable for cloud computing environment.Table 3
Performance comparison among relevant schemes in wireless sensor networks.
Computation overhead Communication cost The evaluation criteria in [24] Login(ms) Auth.(ms) Login Auth. S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 Maitra et al. (2016) [25] 6 T H ≈ 0.04 5 T S+14TH≈0.12 640 bits 1280 bits √ × √ × √ × × × √ √ × √ √ Kumari et al. (2017) [26] 2 T M+3TH≈2.3 6 T M+15TH≈7.0 2176 bits 9088 bits √ √ √ √ × √ √ × √ √ √ √ √ Amin et al. (2018) [3] 6 T H ≈ 0.004 17TH≈0.012 640 bits 1920 bits √ × √ × × √ √ × √ √ × √ √ Our scheme 2 T E+7TH≈1.0 4 T E+12TH≈2.0 1408 bits 4096 bits √ √ √ √ √ √ √ √ √ √ √ √ √ T M denotes the time of modular exponentiation operation, TE denotes scalar multiplication on elliptic curve, TH denotes hash computation, TS denotes symmetric encryption/decryption, TM≫TE≫TH>TS (TM≈1.169ms, TE≈0.508ms, TH≈0.693μs, TS≈0.541μs [20]). Let n0 be 32-bit long; Let IDi, PWi, h(⋅), output of symmetric encryption, timestamp, random numbers be 128-bit long; let P, x, y be 1024-bit long. √ means the property is satisfied; × means the property is not satisfied. Note that the evaluation criteria in [24] are also applied to cloud computing environment when regarding CSj as the sensor node, while the considerations on designing authentication scheme of this two environment are quite different due to their different network attributes.


## 7. Conclusion

The rapid development of cloud computing makes people’s lives more convenient, but also brings huge security concerns. In order to ensure user’s privacy and account security in the cloud environment, a large number of authentication schemes were proposed, but they were subsequently pointed out having one or more flaws. In order to explain the subtleties of designing an authentication protocol in the cloud environment, this paper took Amin et al.’s protocol as a study case to provide ideas for designing secure protocol for cloud environment through elaborating the security weaknesses existing in the protocol and its corresponding solutions. In addition, based on the analysis, we designed a secure authentication protocol, used the BAN logic and heuristic analysis method to prove the security of the protocol. When comparing it with related protocols, we found our scheme has obvious advantages.



---

*Source: 3048697-2018-10-01.xml*