# A General Architecture for Multiserver Authentication Key Agreement with Provable Security

Authors: Yunru Zhang; Min Luo; Kim-Kwang Raymond Choo; Debiao He
Journal: Security and Communication Networks
 (2018)

---

## Abstract

In a typical single-server architecture, when a user wishes to access multiple servers to obtain different services, the user needs to register with every single server. This results in multiple identities and password pairs. To eliminate the limitation of the user having to possess and remember multiple identities and password pairs, a number of multiserver authentication protocols have been proposed where a user only needs to register once. However, most existing protocols are subsequently found to be insecure and this topic remains one of the ongoing research interests. Thus, in this paper, we present a multiserver authentication key agreement protocol. We then demonstrate the security of the protocol under the random oracle model, as well as the practicality of the protocol in terms of low computation and communication costs, minimal storage requirements, and operation costs.


---

## Body

## 1. Introduction

With the constant development in information and communications technologies (ICT) and digitization of our society, there is an increased trend of users accessing online service (e.g., electronic commerce transactions). Generally speaking, the user interacts with the remote server (e.g., service provider) in an open environment, where an adversary can intercept, modify, or delete data-in-transmit (e.g., messages and transactions between devices and users) [1–4]; see Figure 1. One solution is using authentication or key agreement protocols to authenticate parties involved [5–9]. If the identities of both parties can be verified, then the protocol is said to provide mutual authentication.Figure 1
An example model of communication between users and remote servers.Due to the popularity of smart cards, a number of authentication protocols for smart cards in single-server environments have been proposed [10–12]. However, in single-server environments, a user must register on every server that the user wishes to access. This results in the need of users to maintain and ensure the security of the corresponding identities and passwords pairs. Thus, designing secure authentication protocols for smart cards in a multiserver environment has been studied by security researchers [13–16].Once a user registered (and only once) in a multiserver setting, the user can access services from participating servers using the (one) identities and passwords pair. This benefits both users and servers, in the sense that it reduces the number of identities and password pairs for the user and the size of the verification tables for the servers. For example, in 2001, Li et al. [17] proposed a multiserver architecture based on neural networks. Later in 2003, Lin et al. [18] revealed weaknesses in Li et al.’s protocol, and the time required to train the underpinning neural network limits the utility of the protocol. Hence, Lin et at. proposed a multiserver architecture based on discrete logarithms to achieve better performance which was subsequently found to be insecure against impersonation attack [19]. Juang et al. [20] also presented a protocol designed for symmetric cryptosystem, but this protocol does not provide insider attack resilience and has a high computation cost. The protocol of Chang and Lee [21] for multiserver structure requires that all participants be trusted, which may not be a realistic assumption in practice. In addition, due to the requirement for all servers to be trusted, the protocol is not secure against privileged insider attack.In a latter work, Tsai et al. [22] presented a protocol and the authors use a one-way hash function to reduce the computation cost (since no verification table is required). However, Chen et al. [23] pointed out that Tsai et al.’s protocol is vulnerable to server spoofing attacks. In order to achieve user anonymity, Liao et al. [24] proposed a multiserver authentication protocol with dynamic identities, although it was subsequently pointed out that this protocol does not forward secrecy [25]. Independently, Hsiang et al. [26] revealed other security vulnerabilities in the protocol of Liao et al. [24] (e.g., insecurity against insider attack and server spoofing attack) and proposed an improved protocol. The latter protocol was found to be insecure against server spoofing attack [27], contrary to its security claims. An improved protocol is again proposed [27]. While pointing out that the (improved) protocol in [27] cannot resist impersonation attack and smart card stolen attack, the authors in [28] presented an enhanced multiserver architecture with dynamic identities. Separately, Li et al. [29] revealed that the protocol of Lee et al. [27] cannot resist server spoofing attack and the protocol of Sood et al. [28] cannot resist smart card stolen attack, prior to presenting a smart card-based protocol for a multiserver architecture. However, to achieve mutual authentication, Li et al.’s scheme requires a control server.It is clear that most existing protocols are not able to resist a range of attacks and this is the contribution we seek to make in this paper. Specifically, we present a general secure architecture for multiserver authentication key agreement protocol. We then prove that the protocol is secure under the random oracle model. We also demonstrate that the architecture enjoys better performance, in the sense of lower computation and communication costs, minimal storage requirements, and lower operation costs.In the next section, we describe the general architecture of the proposed multiserver authentication protocol. Then in Sections3 and 4, we analyze the security and performance of the proposed protocol, respectively. We conclude the paper in the last section.


## 2. Preliminaries

We define the computationally hard mathematical problems.Computational Diffie-Hellman (CDH) Problem. Given a tuple (g,e,P,Q,aP,bQ) in which (a,b)∈Zq∗, P, Q, and g are the generators of G1, G2, and GT, respectively, the purpose ofCDH problem is to compute ω=gab∈GT, in which (a,b)∈Zq∗ are unknown.


### 2.1. Security Requirements

Single Registration. For the convenience of the user, the proposed protocol for multiserver architecture should provide single registration. The user only needs to register at registration center and can freely access services.Mutual Authentication. To protect the safety of participants, the proposed protocol should provide mutual authentication. The communicating participants should authenticate each other.User Anonymity. To protect user’s privacy, the proposed protocol should provide user anonymity. Even though the adversary can interact with the messages, he/she cannot get user’s identity.Untraceability. To provide better privacy protection, the proposed protocol for multiserver architecture should support untraceability. The adversary cannot find any relation and trace users from the messages sent by users.Secure Session Key Agreement.To ensure the security of the messages transmitted in the continuous communication, the proposed protocol should provide a secure session key shared between the participants to encrypt messages.Backward and Forward Secrecy.To ensure the security of the messages transmitted in the previous and future communication, the proposed protocol should provide backward and forward secrecy. Even though the adversary can get the current session key, he/she cannot get the session key generated in the previous and future session.Resistance of Various Attacks.To withstand various attacks in the real environment, the proposed protocol for multiserver architecture should provide resistance to various attacks.


## 2.1. Security Requirements

Single Registration. For the convenience of the user, the proposed protocol for multiserver architecture should provide single registration. The user only needs to register at registration center and can freely access services.Mutual Authentication. To protect the safety of participants, the proposed protocol should provide mutual authentication. The communicating participants should authenticate each other.User Anonymity. To protect user’s privacy, the proposed protocol should provide user anonymity. Even though the adversary can interact with the messages, he/she cannot get user’s identity.Untraceability. To provide better privacy protection, the proposed protocol for multiserver architecture should support untraceability. The adversary cannot find any relation and trace users from the messages sent by users.Secure Session Key Agreement.To ensure the security of the messages transmitted in the continuous communication, the proposed protocol should provide a secure session key shared between the participants to encrypt messages.Backward and Forward Secrecy.To ensure the security of the messages transmitted in the previous and future communication, the proposed protocol should provide backward and forward secrecy. Even though the adversary can get the current session key, he/she cannot get the session key generated in the previous and future session.Resistance of Various Attacks.To withstand various attacks in the real environment, the proposed protocol for multiserver architecture should provide resistance to various attacks.


## 3. General Architecture for Proposed Multiserver Authentication Protocol

In this section, we proposed the general architecture for multiserver authentication protocol. The protocol comprises three parties (i.e., user, server, and registration center) and three phases (i.e., user registration, server registration, and authentication). Prior to communication between a user, sayUi, and a server, say Sj, both parties need to register with a registration center RC; see Figure 2.Figure 2
A typical multiserver communication architecture.The protocol is based on elliptic curve cryptosystem (ECC).RC chooses an elliptic curve Ep in the finite field GF(p), where P∈G. There is an additive cyclic group G which has n elements in Ep. RC then selects a random number s∈0,1160 as its private key and computes its public key Ppub=s·P. Table 1 describes the notations used in the remaining of this paper.Table 1
Summary of notations.
Notation Description Ui user i Sj server j R C the registration center I D U i the identity of the user i P W U i the password of the user i I D S j the identity of the server j r random number selected by the user i s the secret key ofRC n the number of elements onEp P the point on the elliptic curve K U i a secret value of the user i K S j a secret value of the server j h ( ⋅ ) one-way hash function ⊕ bitwise XOR operation ∥ concatenation operation


### 3.1. User Registration Phase

The userUi sends the registration request IDUi and PWUi to RC and receives a smart card including the private key in this phase. Ui stores the random number on the smart card, and RC stores IDUi and hIDUi∥s in the list. Figure 3 outlines the user registration phase.Figure 3
User registration phase in the proposed protocol.Step 1 (Ui→RC:IDUi,hPWUi∥r).
The userUi chooses IDUi and PWUi at first and then selects a random number r∈0,1160 and computes h(PWUi∥r). At last he sends IDUi,hPWUi∥r to RC.Step 2 (RC→Ui:Bi).
Upon receiving the messages formUi, RC computes Ai=h(IDUi∥s) and Bi=Ai⊕h(PWUi∥r). Then RC stores IDUi and h(IDUi∥s) into the Hash List and sends smart card including Bi to Ui through a secure channel.Step 3.
When receiving smart card formRC, the user Ui stores his identity IDUi and the random number r in the smart card.


### 3.2. Server Registration Phase

The serverSj sends its registration request that is IDSj to RC and receives its secret key in this phase. RC stores IDSj and h(IDSj∥s) into the list. Figure 4 outlines the server registration phase.Figure 4
Server registration phase in the proposed protocol.Step 1 (Sj→RC:IDSj).
The serverSj chooses IDSj and then sends IDSj to RC.Step 2 (RC→Sj:Aj).
Upon receiving the messages formSj, RC computes Aj=h(IDSj∥s) and sends Aj to Sj. At last RC stores IDSj and hIDSj∥s into the list.Step 3.
When receiving the messages formRC, Sj stores the message Aj.


### 3.3. Authentication Phase

U i and Sj authenticate each other by means of RC, and transmitted messages between both parties are verified. A session key is also established between Ui and Sj. The detailed authentication phase is shown in Figure 5.Figure 5
Authentication phase in the proposed protocol.Step 1 (Ui→Sj:m1).
U i inserts the smart card into the terminal and then enters the identity IDUi and password PWUi. Afterwards the smart card computes the value of Ai; that is, Ai=Bi⊕h(PWUi∥r). The smart card also selects a secret value KUi (e.g., ga or aQ, where g is the generator in a multiplicative group and Q is the generator in elliptic curve). Finally, he uses RC’s public key Ppub to encrypt the secret value and user’s identity, computes m1=EPpub(Ai,IDUi,KUi,IDSj∗), and sends the message m1 to RC.Step 2 (Sj→RC:m2).
Upon receiving the message fromUi, Sj selects another secret value KSj. Afterwards Sj computes m2=EPpub(Aj,IDSj,KSj,m1) using RC’s public key Ppub and sends m2 to RC.Step 3 (RC→Sj:c1,AuthRC).
(a)
Upon receiving the message fromSj, RC decrypts m2 with its secret key, that is, Ds(m2)=Aj,IDSj,KSj,m1. Then RC decrypts m1 with its secret key, that is, Ds(m1)=Ai,IDUi,KUi,IDSj∗. (b)
R C computes h(IDSj∗∥s) and compares it with Aj; if the messages are not equal, then RC terminates this session. Otherwise RC authenticates Sj and proceeds as per protocol specification. Then, it computes hIDUi∥s and compares it with Ai. If they are not equal, RC cancels this session. Otherwise RC authenticates Ui and proceeds as per protocol specification. (c)
R C encrypts some information with Sj’s secret value KSj and computes the authentication message AuthRC, that is c1=EKSj∗P(IDUi,KUi,hIDUi∥s), AuthRC=MACKSj(KUi,KSj,hIDSj∗∥s). Finally, RC sends AuthRC and c1 to Sj.Step 4 (Sj→Ui:c2,AuthSj).
(a)
Upon receiving the messages fromRC, Sj decrypts c1 with its secret value KSj, that is, DKSj(c1)=IDUi,KUi,hIDUi∥s, and verifies the validity of AuthRC. If the verification fails, Sj cancels this session. Otherwise, Sj authenticates RC and proceeds as per protocol specification. (b)
S j computes the session key and the authentication message AuthSj and encrypts some information with Ui’s secret value KUi, i.e., SK=KUi∗KSj∗P, AuthSj=MACKUi(KUi,KSj,SK), c2=EKUi∗P(IDSj,KSj,h(IDUi∥s)). Finally, Sj sends AuthSj and c2 to Ui.Step 5 (Ui verifies Sj).
(a)
Upon receiving the messages fromSj, Ui decrypts c2 with its secret value KUi, that is, DKUi(c2)=IDSj,KSj,hIDUi∥s. Since only Ui and RC know the value of hIDUi∥s, Ui compares Ai with hIDUi∥s and cancels this session if the verification fails. Otherwise, Ui authenticates RC. (b)
U i computes the session key SK=KUi∗KSj∗P and verifies the validity of AuthSj. If it is invalid, then Ui cancels this session. Otherwise, Ui authenticates Sj and proceeds as per protocol specification.


## 3.1. User Registration Phase

The userUi sends the registration request IDUi and PWUi to RC and receives a smart card including the private key in this phase. Ui stores the random number on the smart card, and RC stores IDUi and hIDUi∥s in the list. Figure 3 outlines the user registration phase.Figure 3
User registration phase in the proposed protocol.Step 1 (Ui→RC:IDUi,hPWUi∥r).
The userUi chooses IDUi and PWUi at first and then selects a random number r∈0,1160 and computes h(PWUi∥r). At last he sends IDUi,hPWUi∥r to RC.Step 2 (RC→Ui:Bi).
Upon receiving the messages formUi, RC computes Ai=h(IDUi∥s) and Bi=Ai⊕h(PWUi∥r). Then RC stores IDUi and h(IDUi∥s) into the Hash List and sends smart card including Bi to Ui through a secure channel.Step 3.
When receiving smart card formRC, the user Ui stores his identity IDUi and the random number r in the smart card.


## 3.2. Server Registration Phase

The serverSj sends its registration request that is IDSj to RC and receives its secret key in this phase. RC stores IDSj and h(IDSj∥s) into the list. Figure 4 outlines the server registration phase.Figure 4
Server registration phase in the proposed protocol.Step 1 (Sj→RC:IDSj).
The serverSj chooses IDSj and then sends IDSj to RC.Step 2 (RC→Sj:Aj).
Upon receiving the messages formSj, RC computes Aj=h(IDSj∥s) and sends Aj to Sj. At last RC stores IDSj and hIDSj∥s into the list.Step 3.
When receiving the messages formRC, Sj stores the message Aj.


## 3.3. Authentication Phase

U i and Sj authenticate each other by means of RC, and transmitted messages between both parties are verified. A session key is also established between Ui and Sj. The detailed authentication phase is shown in Figure 5.Figure 5
Authentication phase in the proposed protocol.Step 1 (Ui→Sj:m1).
U i inserts the smart card into the terminal and then enters the identity IDUi and password PWUi. Afterwards the smart card computes the value of Ai; that is, Ai=Bi⊕h(PWUi∥r). The smart card also selects a secret value KUi (e.g., ga or aQ, where g is the generator in a multiplicative group and Q is the generator in elliptic curve). Finally, he uses RC’s public key Ppub to encrypt the secret value and user’s identity, computes m1=EPpub(Ai,IDUi,KUi,IDSj∗), and sends the message m1 to RC.Step 2 (Sj→RC:m2).
Upon receiving the message fromUi, Sj selects another secret value KSj. Afterwards Sj computes m2=EPpub(Aj,IDSj,KSj,m1) using RC’s public key Ppub and sends m2 to RC.Step 3 (RC→Sj:c1,AuthRC).
(a)
Upon receiving the message fromSj, RC decrypts m2 with its secret key, that is, Ds(m2)=Aj,IDSj,KSj,m1. Then RC decrypts m1 with its secret key, that is, Ds(m1)=Ai,IDUi,KUi,IDSj∗. (b)
R C computes h(IDSj∗∥s) and compares it with Aj; if the messages are not equal, then RC terminates this session. Otherwise RC authenticates Sj and proceeds as per protocol specification. Then, it computes hIDUi∥s and compares it with Ai. If they are not equal, RC cancels this session. Otherwise RC authenticates Ui and proceeds as per protocol specification. (c)
R C encrypts some information with Sj’s secret value KSj and computes the authentication message AuthRC, that is c1=EKSj∗P(IDUi,KUi,hIDUi∥s), AuthRC=MACKSj(KUi,KSj,hIDSj∗∥s). Finally, RC sends AuthRC and c1 to Sj.Step 4 (Sj→Ui:c2,AuthSj).
(a)
Upon receiving the messages fromRC, Sj decrypts c1 with its secret value KSj, that is, DKSj(c1)=IDUi,KUi,hIDUi∥s, and verifies the validity of AuthRC. If the verification fails, Sj cancels this session. Otherwise, Sj authenticates RC and proceeds as per protocol specification. (b)
S j computes the session key and the authentication message AuthSj and encrypts some information with Ui’s secret value KUi, i.e., SK=KUi∗KSj∗P, AuthSj=MACKUi(KUi,KSj,SK), c2=EKUi∗P(IDSj,KSj,h(IDUi∥s)). Finally, Sj sends AuthSj and c2 to Ui.Step 5 (Ui verifies Sj).
(a)
Upon receiving the messages fromSj, Ui decrypts c2 with its secret value KUi, that is, DKUi(c2)=IDSj,KSj,hIDUi∥s. Since only Ui and RC know the value of hIDUi∥s, Ui compares Ai with hIDUi∥s and cancels this session if the verification fails. Otherwise, Ui authenticates RC. (b)
U i computes the session key SK=KUi∗KSj∗P and verifies the validity of AuthSj. If it is invalid, then Ui cancels this session. Otherwise, Ui authenticates Sj and proceeds as per protocol specification.


## 4. Security Model and Security Proof

Prior to demonstrating the security of the protocol, we describe the model we work with.


### 4.1. Security Model

Similar to the approaches in [30, 31], we assume that there are three entities in the model, namely, (protocol) participants, initialization, and the adversary capabilities respectively.Participants: The parties involved in the protocol are the userUi, server Sj, and registration center RC. let Uik/Sjk represent the k-th instance of Ui/Sj and execute a protocol, and each instance is also known as an oracle. In general there are three states of an oracle: Accept, Reject, ∗.A c c e p t: the k-th instance received correct message.R e j e c t: the k-th instance received wrong message.∗: the decision has not been achieved.Initialization:Ui receives a private key and a smart card from RC, and server Sj receives its private key similarly from RC. Participants can authenticate each other and establish a session key by executing the protocol. Once Uik and Sjk obtain Accept and a session key is established, it can be said that the three participants authenticate each other and SKUik=SKSjk.Adversary capabilities: The adversaryE has the capability to eavesdrop, intercept, and modify the messages during the protocol execution, with the aim of obtaining the session key.(i) h(m) : WhenE executes the query with the message m,RC generates a random ri∈Zq∗, stores (m,ri) into the Hash List, and returns ri toE.(ii) ExtractUser(IDUi): WhenE executes the query with the user Ui’s identity IDUi,RC generates Ui’s private key and stores it in the list LUK.(iii) ExtractServer(IDSj): WhenE executes the query with Sj’s identity IDSj,RC generates Sj’s private key and stores it in the list LSK.(iv) Send(Ui/Sj, m):E sends a message m to Ui/Sj. If m is valid and received by Uik/Sjk, then Ui/Sj sends a response to E, while accepting the session.(v) Execute(Ui, Sj):Uik and Sjk output the real messages transmitted in protocol process.(vi) Reveal(Ui):E queries and obtains session key(s) of session(s) other than the target session.(vii) Corrupt(Ui, PWUi ):E will receive Ui’s password PWUi, as long as the user is not associated with the target session (key).(viii) Corrupt(Ui, smartcard):E will receive Ui’s secret value Bi as long as the user is not associated with the target session (key).(ix) Test(Ui): To obtain the session key, E selects a target instance and initiates this query only once. The query is answered as blow:( 1 ) The queried instance Uik/Sjk randomly chooses a number b∈0,1. If b=1, then E will receive the session key. Otherwise, Uik/Sjk randomly chooses a value and returns it back to E.( 2 ) In other cases, the queried instance Uik/Sjk does not have the session key and returns ⊥ to adversary E.LetDHL denote the length of the Hash List and the protocol assume the intractability of the Elliptic Curve Diffie-Hellman Problem (ECDH) described below.Definition 1 Elliptic Curve Diffie-Hellman Problem (ECDH) [32]: There are two points aP and bP in an additive group G, and it is infeasible to compute point abP.


### 4.2. Security Proof (AKA Security)

E executes all the steps in time t; hence, he can make execution within qh hash-queries, qs send-queries, and qe execute-queries. Thus the advantage is as follows. (1)Advn,Dake≤qh22n-1+qe+qs22n-1+qh+qs+qe2n-1+2qsDHL+2Advn,DECDHt+qs+qeAdvMACtProof.
We demonstrate the security of the protocol using a series of games.Succi indicates that in the query ofTest(Ui)E can correctly guess the value of b for each game Gi(0≤i≤5), and the probability of E winning the game Gi(0≤i≤5) is Pr[Succi]. The series of games start from game G0 to game G5:
(i) GameG0:G0 is a game describing the real word with random oracles. In this game,E can access the messages transmitted during authentication process by executing the oracles. IfE can win this game, then we can get:(2)Advn,DakeE=2∗PrSucc0-1
(ii) GameG1: In this game,E simulates the send- and hash-oracle-queries by accessing the Hash List. The send-queries contain five cases: Send(Sj, m1), Send(RC, m2), Send(Sj, AuthRC), Send(Ui, AuthSj), and Send(Sj, AuthUi). The Hash List consists of x,hx, where x is the input of the hash function and h(x) is the output of the value. If x is in the record, then h(x) is the returned value. Otherwise, a value h(x) randomly chosen from 0,1160 is returned and x,hx is recorded in the Hash List.E cannot distinguish G1 from G0. If the adversaryE can win this game, then we can get:(3)PrSucc1-PrSucc0=0
(iii) GameG2: Assume that in the previous games, all send- and hash-oracle-queries are executed correctly, except when a valid IDUi is queried. As discussed in Sections 3.1 and 3.2, we know thatRC stores h(IDUi/IDSj∥s). OnceE queries a valid IDUi,E obtains Ui/Sj’s private key h(IDUi/IDSj∥s). The distribution of the Hash List is restricted for any hash function; thus, the collisions may occur in hash oracle [33], or in the messages transmitted during protocol execution. G2 and G1 are not distinguishable; only if the above conditions occur, we can get the following.(4)PrSucc2-PrSucc1≤qh22n+qe+qs22n
(iv) GameG3: We consider that all the oracle queries are executed correctly in the previous games, except the authentication messages m1,m2,AuthRC,AuthUi,AuthSj guessed byE. In other words,E executes Send(Ui/Sj,m) and Execute(Ui,Sj) oracles and receives the corresponding correct answers: Send(Sj, m1), Send(RC, m2), Send(Sj, AuthRC), Send(Ui, AuthSj), Send(Sj, AuthUi), Execute(Ui, Sj), Execute(Sj, RC). G3 and G2 are not distinguishable unless the oracle queries are rejected. IfE wins this game, we can get the following.(5)PrSucc3-PrSucc2≤qh+qs+qe2n
(v) GameG4: In this game, we assume that all oracle queries are executed correctly in the previous games. However only ifE guesses the correct private key Ai/Aj, then the game will be terminated. IfE guesses the correct Ai=h(IDUi∥s),E can impersonate Ui by selecting a secret value KE and computing m1. In the same way,E can impersonate Sj ifE correctly guesses Aj=h(IDSj∥s). At the same time, ifE guesses the correct private key Ai/Aj,E can distinguish the session key from the random value, whereasE will obtain the correct hash values by guessing the hash one at a time. IfE can win this game, then we can get the following.(6)PrSucc4-PrSucc3≤qsDHL
(vi) GameG5: We embed the ECDH problem into the simulation process: namely, An ECDH instance means that given the two points a∗P and b∗P, we need to compute a∗b∗P without knowing the secret values a and b. We can first select a target session to challenge, andE will conduct the corresponding oracle queries. We embed the ECDH instance of a∗P and b∗P to take the place of KUi∗P and KSj∗P. Suppose thatE can decrypt the MAC algorithm in the time range of t.
Under these circumstances, we cannot distinguish the gameG5 from G4 unlessE can intercept or guess the correct secret values KUi and KSj and break the security of the underlying MAC algorithm. ThusE must compute SK=ECDH(KUi,KSj).(7)PrSucc5-PrSucc4≤Advn,DECDHt+qs+qeAdvMACt2
From the previous games, it is clear that there are no collisions on the authentication process and queries. At the same time, the authentication values and the hash value cannot be guessed correctly by the adversaryE. Therefore, the previous games are independent of each other. The only way thatE can win the game is to guess the value of b. Thus we know the following.(8)PrSucc5=12


### 4.3. Analysis of Security Requirements

Single Registration: In this proposed protocol, the user only needs to register at registration center. When user logs in to any server in the system, the login information is sent toRC and verified byRC. Therefore, the protocol can provide single registration.Mutual Authentication: In Section 3.3,RC, Ui, and Sj will authenticate each other.(i)
RC authenticates Ui and Sj. Upon receiving message m2,RC decrypts it and m1 and gets Aj,IDSj,KSj,Ai,IDUi,KUi,IDSj∗. Due to not guessing s, there are onlyRC and Sj computing or knowing h(IDSj∥s) even ifE gets Sj’s identity IDSj. Thus,RC computes h(IDSj∗∥s) and compares it with Aj. If they are equal, it can be said thatRC authenticates Sj. Afterwards the reason whyRC authenticates Ui is the same as that of why it authenticates Sj. Thus it can be said thatRC authenticates Ui.(ii)
Ui and Sj authenticateRC. Upon receiving message {c1,AuthRC}, Sj decrypts c1 and gets KUi. Then it verifies the validity of AuthRC with the value of KUi. If it is valid, it can be said that Sj authenticatesRC. Ui decrypts c2 and compares Ai with h(IDUi∥s). If they are equal, it can be said that Ui authenticatesRC.(iii)
Ui and Sj authenticate each other. Ui computes session key and verifies AuthSj on receiving message {c1,AuthRC}. If it is valid, it can be said that Ui authenticates Sj. Sj authenticates Ui by verifying AuthUi with the same argument. If it is valid, it can be said that Sj authenticates Ui.Therefore, the protocol can achieve mutual authentication.User Anonymity: During the execution of protocol, Ui’s identity IDUi is only contained in messages m1 and c1. While the messages are encrypted by Ppub and KSj, respectively, that is, m1=EPpub(Ai,IDUi,KUi) and c1=EKSj(IDUi,KUi,h(IDUi∥s)), even thoughE intercepts the messages, as long as he cannot getRC’s private key s or server Sj’s secret value KSj,E cannot get IDUi.Untraceability: During the execution of protocol, the user generates a random secret value KUi to compute message m1=EPpub(Ai,IDUi,KUi). According to the protocol, we know that user will randomly generate secret values at each execution. Thus the adversary cannot find any relation from the messages sent by Ui and also cannot trace users. Therefore, the protocol can provide untraceability.Secure Session Key Agreement: U i and Sj compute the session key SK=ECDH(KUi,KSj) independently. Ui checks the validity of SK by verifying AuthSj, where AuthSj is encrypted by Ui’s private key KUi. Sj checks the validity of SK by verifying AuthUi, where AuthUi is encrypted by Sj’s private key KSj. The valid SK can be used in the future communication. Therefore, the proposed protocol is able to provide secure session key agreement.Backward and Forward Secrecy: Assume thatE knows the current SK. Owing to the session key SK=ECDH(KUi,KSj), where the secret values KUi and KSj are randomly selected by Ui and Sj. Different KUi and KSj are selected with the execution of protocol, and each session key is independent; thus, even if the current session key is known byE, he cannot know the previous and coming session key.Resistance of Various Attacks: We will show that the protocol can withstand insider attack, off-line password guessing attack, user impersonation attack, server spoofing attack, modification attack, stolen card attack, and man-in-the-middle attack. The details are shown as follows.(i)
Insider Attack: In registration phase, Ui sends IDUi,hPWUi∥r toRC. Suppose that an insider attacker can get user’s information; however, obviously the password PWUi is not in plain text. Thus the adversary cannot get correct password from the messages. In addition,RC stores IDUi,hIDUi∥s in a list, and the insider attacker cannot get password from the list. Therefore, the protocol can resist the insider attack.(ii)
Off-line Password Guessing Attack: Assume that the adversary steals user’s smart card and can extract the information {IDUi,Bi,r} by the side channel attack, where Bi=hIDUi∥s⊕hPWUi∥r, s isRC’s private key. The adversary can guess the password PWUi∗. However,E cannot verify the correctness from Bi because the password is protected by the secure hash function andRC’s private key s. Therefore, the protocol can resist off-line password guessing attack.(iii)
User Impersonation Attack: E wants to impersonate Ui; he should send message mE to Sj and be verified byRC.E selects two random numbers as his identity IDE and his secret value KE. ThenE computes AE=h(IDE∥s∗), where s∗ is guessed byE asRC’s private key.E computes mE=EPpub(AE,IDE,KE) and sends mE to Sj. Upon receiving the message m2,RC decrypts mE and computes h(IDE∥s) where s isRC’s real private key and compares it with AE. However,E does not knowRC’s private key s. ThusRC cannot authenticate the impersonated user and the protocol can resist user impersonation attack.(iv)
Server Spoofing Attack: E wants to impersonate Sj; he should send legal message mE toRC and be verified byRC.E selects two random numbers as his identity IDE and his secret value KE. ThenE computes AE=h(IDE∥s∗), where s∗ is guessed asRC’s private key.E computes mE=EPpub(AE,IDE,KE,m1) and sends mE toRC. Upon receiving the message mE,RC decrypts mE and m1, then computes h(IDSj∗∥s), and compares it with AE. However,E does not knowRC’s private key s. ThusRC cannot authenticate the server and the protocol can resist server spoofing attack.(v)
Stolen Card Attack: Assume that the adversary steals user’s smart card and can extract the information {IDUi,Bi,r} by the side channel attack, where Bi=h(IDUi∥s)⊕h(PWUi∥r), s isRC’s private key. The adversary can guess the password PWUi∗. However,E cannot verify the correctness from Bi because the password is protected by the secure hash function andRC’s private key s. Therefore, the protocol can resist stolen cards attack.(vi)
Modification Attack: According to the authentication phase, we know that authentication messages m1,m2 are encrypted by public keys.RC can find any modification by checking the equations Aj=h(IDSj∥s) and Ai=h(IDUi∥s). c1,AuthRC,AuthUi are encrypted by Sj’s secret value, and Sj cannot decrypt the messages once the messages are modified. c2,AuthSj, are encrypted by Ui’s secret value, and Ui cannot decrypt the messages once they are modified. Therefore, the protocol can resist modification attack.(vii)
Man-in-the-Middle Attack: Based on the above analysis, we conclude that the proposed protocol can provide mutual authentication. Thus the protocol can resist man-in-the-middle attack.


## 4.1. Security Model

Similar to the approaches in [30, 31], we assume that there are three entities in the model, namely, (protocol) participants, initialization, and the adversary capabilities respectively.Participants: The parties involved in the protocol are the userUi, server Sj, and registration center RC. let Uik/Sjk represent the k-th instance of Ui/Sj and execute a protocol, and each instance is also known as an oracle. In general there are three states of an oracle: Accept, Reject, ∗.A c c e p t: the k-th instance received correct message.R e j e c t: the k-th instance received wrong message.∗: the decision has not been achieved.Initialization:Ui receives a private key and a smart card from RC, and server Sj receives its private key similarly from RC. Participants can authenticate each other and establish a session key by executing the protocol. Once Uik and Sjk obtain Accept and a session key is established, it can be said that the three participants authenticate each other and SKUik=SKSjk.Adversary capabilities: The adversaryE has the capability to eavesdrop, intercept, and modify the messages during the protocol execution, with the aim of obtaining the session key.(i) h(m) : WhenE executes the query with the message m,RC generates a random ri∈Zq∗, stores (m,ri) into the Hash List, and returns ri toE.(ii) ExtractUser(IDUi): WhenE executes the query with the user Ui’s identity IDUi,RC generates Ui’s private key and stores it in the list LUK.(iii) ExtractServer(IDSj): WhenE executes the query with Sj’s identity IDSj,RC generates Sj’s private key and stores it in the list LSK.(iv) Send(Ui/Sj, m):E sends a message m to Ui/Sj. If m is valid and received by Uik/Sjk, then Ui/Sj sends a response to E, while accepting the session.(v) Execute(Ui, Sj):Uik and Sjk output the real messages transmitted in protocol process.(vi) Reveal(Ui):E queries and obtains session key(s) of session(s) other than the target session.(vii) Corrupt(Ui, PWUi ):E will receive Ui’s password PWUi, as long as the user is not associated with the target session (key).(viii) Corrupt(Ui, smartcard):E will receive Ui’s secret value Bi as long as the user is not associated with the target session (key).(ix) Test(Ui): To obtain the session key, E selects a target instance and initiates this query only once. The query is answered as blow:( 1 ) The queried instance Uik/Sjk randomly chooses a number b∈0,1. If b=1, then E will receive the session key. Otherwise, Uik/Sjk randomly chooses a value and returns it back to E.( 2 ) In other cases, the queried instance Uik/Sjk does not have the session key and returns ⊥ to adversary E.LetDHL denote the length of the Hash List and the protocol assume the intractability of the Elliptic Curve Diffie-Hellman Problem (ECDH) described below.Definition 1 Elliptic Curve Diffie-Hellman Problem (ECDH) [32]: There are two points aP and bP in an additive group G, and it is infeasible to compute point abP.


## 4.2. Security Proof (AKA Security)

E executes all the steps in time t; hence, he can make execution within qh hash-queries, qs send-queries, and qe execute-queries. Thus the advantage is as follows. (1)Advn,Dake≤qh22n-1+qe+qs22n-1+qh+qs+qe2n-1+2qsDHL+2Advn,DECDHt+qs+qeAdvMACtProof.
We demonstrate the security of the protocol using a series of games.Succi indicates that in the query ofTest(Ui)E can correctly guess the value of b for each game Gi(0≤i≤5), and the probability of E winning the game Gi(0≤i≤5) is Pr[Succi]. The series of games start from game G0 to game G5:
(i) GameG0:G0 is a game describing the real word with random oracles. In this game,E can access the messages transmitted during authentication process by executing the oracles. IfE can win this game, then we can get:(2)Advn,DakeE=2∗PrSucc0-1
(ii) GameG1: In this game,E simulates the send- and hash-oracle-queries by accessing the Hash List. The send-queries contain five cases: Send(Sj, m1), Send(RC, m2), Send(Sj, AuthRC), Send(Ui, AuthSj), and Send(Sj, AuthUi). The Hash List consists of x,hx, where x is the input of the hash function and h(x) is the output of the value. If x is in the record, then h(x) is the returned value. Otherwise, a value h(x) randomly chosen from 0,1160 is returned and x,hx is recorded in the Hash List.E cannot distinguish G1 from G0. If the adversaryE can win this game, then we can get:(3)PrSucc1-PrSucc0=0
(iii) GameG2: Assume that in the previous games, all send- and hash-oracle-queries are executed correctly, except when a valid IDUi is queried. As discussed in Sections 3.1 and 3.2, we know thatRC stores h(IDUi/IDSj∥s). OnceE queries a valid IDUi,E obtains Ui/Sj’s private key h(IDUi/IDSj∥s). The distribution of the Hash List is restricted for any hash function; thus, the collisions may occur in hash oracle [33], or in the messages transmitted during protocol execution. G2 and G1 are not distinguishable; only if the above conditions occur, we can get the following.(4)PrSucc2-PrSucc1≤qh22n+qe+qs22n
(iv) GameG3: We consider that all the oracle queries are executed correctly in the previous games, except the authentication messages m1,m2,AuthRC,AuthUi,AuthSj guessed byE. In other words,E executes Send(Ui/Sj,m) and Execute(Ui,Sj) oracles and receives the corresponding correct answers: Send(Sj, m1), Send(RC, m2), Send(Sj, AuthRC), Send(Ui, AuthSj), Send(Sj, AuthUi), Execute(Ui, Sj), Execute(Sj, RC). G3 and G2 are not distinguishable unless the oracle queries are rejected. IfE wins this game, we can get the following.(5)PrSucc3-PrSucc2≤qh+qs+qe2n
(v) GameG4: In this game, we assume that all oracle queries are executed correctly in the previous games. However only ifE guesses the correct private key Ai/Aj, then the game will be terminated. IfE guesses the correct Ai=h(IDUi∥s),E can impersonate Ui by selecting a secret value KE and computing m1. In the same way,E can impersonate Sj ifE correctly guesses Aj=h(IDSj∥s). At the same time, ifE guesses the correct private key Ai/Aj,E can distinguish the session key from the random value, whereasE will obtain the correct hash values by guessing the hash one at a time. IfE can win this game, then we can get the following.(6)PrSucc4-PrSucc3≤qsDHL
(vi) GameG5: We embed the ECDH problem into the simulation process: namely, An ECDH instance means that given the two points a∗P and b∗P, we need to compute a∗b∗P without knowing the secret values a and b. We can first select a target session to challenge, andE will conduct the corresponding oracle queries. We embed the ECDH instance of a∗P and b∗P to take the place of KUi∗P and KSj∗P. Suppose thatE can decrypt the MAC algorithm in the time range of t.
Under these circumstances, we cannot distinguish the gameG5 from G4 unlessE can intercept or guess the correct secret values KUi and KSj and break the security of the underlying MAC algorithm. ThusE must compute SK=ECDH(KUi,KSj).(7)PrSucc5-PrSucc4≤Advn,DECDHt+qs+qeAdvMACt2
From the previous games, it is clear that there are no collisions on the authentication process and queries. At the same time, the authentication values and the hash value cannot be guessed correctly by the adversaryE. Therefore, the previous games are independent of each other. The only way thatE can win the game is to guess the value of b. Thus we know the following.(8)PrSucc5=12


## 4.3. Analysis of Security Requirements

Single Registration: In this proposed protocol, the user only needs to register at registration center. When user logs in to any server in the system, the login information is sent toRC and verified byRC. Therefore, the protocol can provide single registration.Mutual Authentication: In Section 3.3,RC, Ui, and Sj will authenticate each other.(i)
RC authenticates Ui and Sj. Upon receiving message m2,RC decrypts it and m1 and gets Aj,IDSj,KSj,Ai,IDUi,KUi,IDSj∗. Due to not guessing s, there are onlyRC and Sj computing or knowing h(IDSj∥s) even ifE gets Sj’s identity IDSj. Thus,RC computes h(IDSj∗∥s) and compares it with Aj. If they are equal, it can be said thatRC authenticates Sj. Afterwards the reason whyRC authenticates Ui is the same as that of why it authenticates Sj. Thus it can be said thatRC authenticates Ui.(ii)
Ui and Sj authenticateRC. Upon receiving message {c1,AuthRC}, Sj decrypts c1 and gets KUi. Then it verifies the validity of AuthRC with the value of KUi. If it is valid, it can be said that Sj authenticatesRC. Ui decrypts c2 and compares Ai with h(IDUi∥s). If they are equal, it can be said that Ui authenticatesRC.(iii)
Ui and Sj authenticate each other. Ui computes session key and verifies AuthSj on receiving message {c1,AuthRC}. If it is valid, it can be said that Ui authenticates Sj. Sj authenticates Ui by verifying AuthUi with the same argument. If it is valid, it can be said that Sj authenticates Ui.Therefore, the protocol can achieve mutual authentication.User Anonymity: During the execution of protocol, Ui’s identity IDUi is only contained in messages m1 and c1. While the messages are encrypted by Ppub and KSj, respectively, that is, m1=EPpub(Ai,IDUi,KUi) and c1=EKSj(IDUi,KUi,h(IDUi∥s)), even thoughE intercepts the messages, as long as he cannot getRC’s private key s or server Sj’s secret value KSj,E cannot get IDUi.Untraceability: During the execution of protocol, the user generates a random secret value KUi to compute message m1=EPpub(Ai,IDUi,KUi). According to the protocol, we know that user will randomly generate secret values at each execution. Thus the adversary cannot find any relation from the messages sent by Ui and also cannot trace users. Therefore, the protocol can provide untraceability.Secure Session Key Agreement: U i and Sj compute the session key SK=ECDH(KUi,KSj) independently. Ui checks the validity of SK by verifying AuthSj, where AuthSj is encrypted by Ui’s private key KUi. Sj checks the validity of SK by verifying AuthUi, where AuthUi is encrypted by Sj’s private key KSj. The valid SK can be used in the future communication. Therefore, the proposed protocol is able to provide secure session key agreement.Backward and Forward Secrecy: Assume thatE knows the current SK. Owing to the session key SK=ECDH(KUi,KSj), where the secret values KUi and KSj are randomly selected by Ui and Sj. Different KUi and KSj are selected with the execution of protocol, and each session key is independent; thus, even if the current session key is known byE, he cannot know the previous and coming session key.Resistance of Various Attacks: We will show that the protocol can withstand insider attack, off-line password guessing attack, user impersonation attack, server spoofing attack, modification attack, stolen card attack, and man-in-the-middle attack. The details are shown as follows.(i)
Insider Attack: In registration phase, Ui sends IDUi,hPWUi∥r toRC. Suppose that an insider attacker can get user’s information; however, obviously the password PWUi is not in plain text. Thus the adversary cannot get correct password from the messages. In addition,RC stores IDUi,hIDUi∥s in a list, and the insider attacker cannot get password from the list. Therefore, the protocol can resist the insider attack.(ii)
Off-line Password Guessing Attack: Assume that the adversary steals user’s smart card and can extract the information {IDUi,Bi,r} by the side channel attack, where Bi=hIDUi∥s⊕hPWUi∥r, s isRC’s private key. The adversary can guess the password PWUi∗. However,E cannot verify the correctness from Bi because the password is protected by the secure hash function andRC’s private key s. Therefore, the protocol can resist off-line password guessing attack.(iii)
User Impersonation Attack: E wants to impersonate Ui; he should send message mE to Sj and be verified byRC.E selects two random numbers as his identity IDE and his secret value KE. ThenE computes AE=h(IDE∥s∗), where s∗ is guessed byE asRC’s private key.E computes mE=EPpub(AE,IDE,KE) and sends mE to Sj. Upon receiving the message m2,RC decrypts mE and computes h(IDE∥s) where s isRC’s real private key and compares it with AE. However,E does not knowRC’s private key s. ThusRC cannot authenticate the impersonated user and the protocol can resist user impersonation attack.(iv)
Server Spoofing Attack: E wants to impersonate Sj; he should send legal message mE toRC and be verified byRC.E selects two random numbers as his identity IDE and his secret value KE. ThenE computes AE=h(IDE∥s∗), where s∗ is guessed asRC’s private key.E computes mE=EPpub(AE,IDE,KE,m1) and sends mE toRC. Upon receiving the message mE,RC decrypts mE and m1, then computes h(IDSj∗∥s), and compares it with AE. However,E does not knowRC’s private key s. ThusRC cannot authenticate the server and the protocol can resist server spoofing attack.(v)
Stolen Card Attack: Assume that the adversary steals user’s smart card and can extract the information {IDUi,Bi,r} by the side channel attack, where Bi=h(IDUi∥s)⊕h(PWUi∥r), s isRC’s private key. The adversary can guess the password PWUi∗. However,E cannot verify the correctness from Bi because the password is protected by the secure hash function andRC’s private key s. Therefore, the protocol can resist stolen cards attack.(vi)
Modification Attack: According to the authentication phase, we know that authentication messages m1,m2 are encrypted by public keys.RC can find any modification by checking the equations Aj=h(IDSj∥s) and Ai=h(IDUi∥s). c1,AuthRC,AuthUi are encrypted by Sj’s secret value, and Sj cannot decrypt the messages once the messages are modified. c2,AuthSj, are encrypted by Ui’s secret value, and Ui cannot decrypt the messages once they are modified. Therefore, the protocol can resist modification attack.(vii)
Man-in-the-Middle Attack: Based on the above analysis, we conclude that the proposed protocol can provide mutual authentication. Thus the protocol can resist man-in-the-middle attack.


## 5. Performance Analysis

In this section, we analyze the computation complexity, the resistance of various attacks, and communication cost of our architecture for multiserver authentication key agreement. And then we make the comparison with the protocols previously mentioned in the related work; they are the protocol of Sood et al. [28], the protocol of Lee et al. [27], and the protocol of Li et al. [29].Table2 is a comparative summary of the computation costs and analysis of various attacks for the four protocols, in which Th denotes the time complexity of completing a typical hash function, Tpm denotes the time complexity of completing an elliptic curve point multiplication operation, TMAC denotes the time complexity of completing a MAC algorithm, and TED is the time complexity of executing an encryption and decryption. Since the time complexity of an XOR operation is negligible compared to Th,TMAC,Tpm, and TED, thus we ignore the XOR operation time.Table 2
Comparative summary: computation costs and analysis of various attacks.
Protocols Sood et al. [28] Lee et al. [27] Li et al. [29] proposed protocol User side 9 T h + T p m 8 T h + T p m 8 T h + T p m 2 T h + T p m + 2 T E D + 2 T M A C Server side 11 T h + T p m 7 T h + T p m 4 T h + T p m T p m + 3 T E D + 3 T M A C RC side 4 T h 8 T h 13 T h 3 T h + 3 T E D + T M A C total 28 T h + 2 T p m 23 T h + 2 T p m 25 T h + 2 T p m 4 T h + 2 T p m + 8 T E D + 6 T M A C Resist Insider Attack yes yes yes yes Resist Off-line Password Guessing Attack yes yes yes yes Resist User Impersonation Attack no yes yes yes Resist Server Spoofing Attack yes yes yes yes Resist Stolen Card Attack no yes no yes Resist Modification Attack yes no yes yes Resist Man-in-the-middle Attack yes no no yesIn registration phase,Ui computes h(PWUi∥r) andRC needs to compute h(IDUi∥s) and h(IDSj∥s), which means that the computation cost is 3Th. In authentication phase, Ui computes h(PWUi∥r) and performs an encryption operation in Step 1. Then Ui carries out a decryption operation to authenticate Sj, computes the session key using the elliptic curve point multiplication operation, and performs MAC algorithm twice to authenticate server and be server-certified in Step 5. Thus the total computation cost for user is Th+Tpm+2TMAC+2TED.S j, during the second and fourth step in authentication phase, needs to encrypt a message and decrypt the authentication message fromRC, complete a MAC algorithm to authenticateRC, compute the session key with the elliptic curve point multiplication operation, and complete a MAC algorithm to be authenticated by Ui. In the last step, the server completes a MAC algorithm to identify Ui. Thus the total computation cost for server is Tpm+3TMAC+3TED. In the third step, RC carries out decryption operation twice to identify Ui and Sj. And then it encrypts a message and executes a MAC algorithm to be authenticated by Sj. The total computation cost for server is TMAC+3TED.From Table2, we can see that the protocol of Sood et al. [28] fails to resist user impersonation attack and stolen card attack, the protocol of Lee et al. [27] cannot resist user impersonation attack and man-in-the-middle attack, and the protocol of Li et al. [29] is sensitive to stolen card attack and man-in-the-middle attack.Table3 is a comparative summary of the communication costs for the four protocols. Suppose that the secure length of ECC cryptosystem is 160 bits. Thus, we can know that the length of the encrypted data is 160 bits and the output length of the MAC is equal to the input data. Our proposed protocol’s communication cost is, therefore, 2080 bits.Table 3
Comparative summary: communication costs.
Protocols computation cost Sood et al. [28] 4 messages (2240 bits) Lee et al. [27] 3 messages (1120 bits) Li et al. [29] 4 messages (2720 bits) proposed protocol 5 messages (2080 bits)


## 6. Conclusion

In this paper, we proposed a general architecture for multiserver authentication key agreement protocol. With it, the user can subscribe many kinds of services just needing one pair of identity and passwords. We prove the architecture is secure and can provide resistance to various attacks under the random oracle model. In addition, our proposed protocol has lower computation and communication costs and good computational efficiency in terms of storage and operation cost.



---

*Source: 2462901-2018-11-06.xml*