Advanced
A Secure and Efficient Remote User Authentication Scheme for Multi-server Environments Using ECC
A Secure and Efficient Remote User Authentication Scheme for Multi-server Environments Using ECC
KSII Transactions on Internet and Information Systems (TIIS). 2014. Aug, 8(8): 2930-2947
Copyright © 2014, Korean Society For Internet Information
  • Received : October 24, 2013
  • Accepted : July 14, 2014
  • Published : August 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Junsong Zhang
School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China
Jian Ma
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications
Xiong Li
School of Computer Science and Engineering, Hunan University of Science and Technology Xiangtan 411201, China
Wendong Wang
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications

Abstract
With the rapid growth of the communication technology, intelligent terminals (i.e. PDAs and smartphones) are widely used in many mobile applications. To provide secure communication in mobile environment, in recent years, many user authentication schemes have been proposed. However, most of these authentication schemes suffer from various attacks and cannot provide provable security. In this paper, we propose a novel remote user mutual authentication scheme for multi-server environments using elliptic curve cryptography (ECC). Unlike other ECC-based schemes, the proposed scheme uses ECC in combination with a secure hash function to protect the secure communication among the users, the servers and the registration center (RC). Through this method, the proposed scheme requires less ECC-based operations than the related schemes, and makes it possible to significantly reduce the computational cost. Security and performance analyses demonstrate that the proposed scheme can solve various types of security problems and can meet the requirements of computational complexity for low-power mobile devices.
Keywords
1. Introduction
N owadays, mobile devices (i.e. smart phones, PDAs) are popular and widely used in many mobile applications, such as online shopping, mobile pay-TV, and electronic transactions. Along with the increasing number of mobile applications, the security issues have been received more and more attention. Generally, the user must be authenticated by the remote server before he accesses the services provided by the remote servers. The password-based authentication scheme is one of widely used mechanisms to verify the validity of the remote users over an insecure communication channel, and is a protective barrier that can prevent unauthorized personnel from accessing services provided by the application server.
In 1981, Lamport [1] first proposed a password-based remote authentication scheme for insecure communication. In Lamport’s scheme, the user submits a message which contains his/her identity and password to the remote server, and then he/she can access to the remote server if the submitted information is matched with the information stored in the server’s memory. This method is simple and practical, but it has some inherent drawbacks. The most serious problem is that the server has to store and maintain a verification table to verify the validity of the users, and then it will suffer from the password related attacks, such as stolen-verifier attack, off-line password dictionary attack, password table tampering and corruption attack. Later, some research activities [2] [3] focused on the password-based authentication schemes without verification tables. However, only password-based user authentication scheme is not sufficient to fulfill the security requirements of various applications. Since the smart card has the functions of storage, encryption, computation, etc., many smart card based password authentication schemes have been proposed [4] [5] [6] [7] [8] [21] by researchers. The smart card based password authentication schemes can not only solve the problem of storing the password table in the server, but can enhance the security of their schemes.
However, most of smart card based user authentication schemes are designed for the single server environments. In the practical application, it is extremely hard for a user to remember these different numerous identities and passwords when he/she uses the single-server authentication scheme to login and access to different remote servers. For this reason, there are also some other research activities [9] [10] [11] [12] [20] contributed to the authentication schemes for multi-server environments. The multi-server authentication scheme resolves the repeated registration problem of single-server authentication scenario where the user has to register at different servers to access to different types of network services. In 2001, Li et al . [9] proposed a multi-server user authentication protocol based on neural networks, however, it was found that the computational complexity of their scheme is too high [10] . To remedy the efficiency problem of Li et al .’s scheme, Juang [10] proposed a new multi-server password authentication protocol using the hash function and symmetric key cryptosystem. However, Chang and Lee [11] pointed out that Juang’s protocol lacks efficiency and is vulnerable to off-line dictionary attack. Therefore, Chang and Lee proposed a novel authentication scheme to remedy these weaknesses. Nevertheless, their protocol was found to be vulnerable to insider attack, spoofing attack and registration center spoofing attack [12] . Then, Tsai [12] proposed an efficient multi-server authentication protocol based on one-way hash function.
However, all of the above smart card based multi-server authentication schemes are based on static ID, which gives the adversary a chance to trace a legal user. Consequently, to deal with this problem, some dynamic identity based user authentication schemes for multi-server environments have been proposed [13] [14] [15] [19] [22] . In 2009, Liao and Wang [13] proposed a dynamic identity based authentication scheme for multi-server architecture. They claimed that their scheme can resist various attacks and can achieve mutual authentication. However, Hsiang and Shih [14] pointed out that Liao-Wang’s scheme is still suffering from a variety of different attacks. Besides, Hsiang and Shih found that Liao-Wang’s scheme cannot achieve mutual authentication. To solve these problems, Hsiang and Shih [14] proposed an improved protocol on Liao-Wang’s protocol. Unfortunately, Lee et al . [15] , Sood et al . [16] , and Chuang and Tseng [17] respectively pointed out that Hsiang and Shih’s scheme still suffers from different kinds of attacks, and they are all proposed the enhanced scheme. Later, Li et al . [18] and Li et al . [19] respectively pointed out Lee et al .’s scheme [15] and Sood et al .’s scheme [16] are both not secure to resist attacks.
Recently, many pairing-based or ECC-based remote user authentication schemes with smart cards were proposed in [17] [23] [24] [25] . In 2006, Das et al . [23] proposed a pairing-based remote client authentication scheme with smart cards. However, their scheme suffered from a forgery attack. Later, Fang and Huang [24] proposed an improvement to overcome drawback of Das et al .’s scheme. However, Giri and Srivastava [25] found that Fang and Huang’s scheme is still suffering from another type of forgery attack. Then, Giri and Srivastava [25] presented another improvement to withstand the forgery attack. In 2012, Chuang and Tseng [17] proposed an ID-based mutual authentication and key agreement scheme based on bilinear maps for mobile multi-server environment. In 2013, Liao and Hsiao [4] proposed a pairing-based remote user authentication scheme which uses secure key distribution based on self-certified public keys among the service servers. However, the computational cost of pairing operation is approximately 20 times higher than that of the scalar multiplication with the same order. Then, several ID-based authentication protocols on ECC are proposed. In 2009, Yang and Chang [26] proposed an ID-based remote mutual authentication with key agreement protocol on ECC. In 2012, He et al . [5] propose an ID-based remote mutual authentication with key agreement scheme on ECC. However, He et al .’s scheme cannot support the multi-server environment.
In general, a secure and efficient remote user authentication scheme should satisfy the following requirements [18] .
•User anonymity: The adversary cannot track a special user by the user’s identity, therefore it can protect the user’s privacy.
•Single registration: The scheme allows the user to register only once at the registration center and then the user can access to all the permitted services in the whole network.
•No password table: The registration center should be without the user’s password table to authenticate the users.
•Low computation and communication cost: Due to the limited energy, processing and storage resources of mobile devices, the design of authentication scheme must take computation efficiency into consideration.
•Mutual authentication and session key agreement: In mutual authentication scheme, the server and the user must be able to authenticate each other via message exchange (mutual authentication). Through the mutual authentication procedure, the server and the user can negotiate and agree on a session key that is used in the following secret communication.
•Security: The authentication scheme must be able to prevent from various kinds of attacks.
In this paper, we propose a novel remote user mutual authentication scheme with key agreement protocol for mobile multi-server environments. Unlike other ECC-based researches, the proposed scheme uses a secure hash function to protect both the users’ and the servers’ secret values. Besides, the proposed scheme uses ECC in combination with a secure hash function to protect the secure communication among the users, the servers and the registration center (RC for short, which is responsible for system initialization, user and server registration and authentication).. Through this method, the proposed scheme requires less ECC-based operations than the related schemes. Performance analysis is made to show that our scheme has better performance than the related schemes [5] [17] [26] . The security analysis shows that the proposed scheme can withstand various possible attacks. Compared with the related works, the proposed scheme is more secure and efficient for remote authentication.
The remainder of this paper is organized as follows. In Section 2, we briefly review the basic concepts of ECC and some related mathematical preliminaries. Section 3 describes the proposed authentication and key agreement scheme. Then, we present the security analysis and performance evaluation about the proposed scheme in Section 4 and Section 5, respectively. Finally, Section 6 concludes the paper.
2. Preliminaries
In this section, we briefly introduce the basic concepts of the elliptic curve and its related mathematical properties. The elliptic curve cryptography (ECC) was first proposed by Miller and Koblitz (1985), respectively. The security of ECC is dependent on the difficulty of solving the elliptic curve discrete logarithm problem (ECDLP). Due to the difficulty in breaking its encryption, Elliptic Curve Cryptography can provide the same level of RSA encryption at a greatly reduced bit size [26] [27] .
- 2.1 Elliptic Curve Cryptography (ECC)
Let p be a prime number, and let GF ( p ) denote the field of integers modulo p . An elliptic curve E over GF ( p ) is defined by an equation of the form:
PPT Slide
Lager Image
where a , b GF ( p ), and satisfies 4 a 3 + 27 b 2 ≠ 0 (mod p ) . A pari Q ( x 1 , y 1 ) is a point on the curve if Q( x 1 , y 1 ) satisfies the equation (1), where x 1 , y 1 GF ( p ). The point at infinity, denoted by , is also said to be on the curve. Any point pair Q ( x , y ) which satifies the above equation together with , called ‘point at infinity’, form an additive cyclic group E ( Fp ) = {( x , y ) | x , y GF ( p ) satisfy y 2 = x 3 + ax + b (mod p )}∪ . The scalar multiplication of a point P over Ep ( a , b ) is computed by repeated addition as, k · P = P + P + · · · + P ( k times), where k is a constant integer and P is a point on the curve E . For simplicity, we omit the details and the readers can refer to the related references [27] .
- 2.2 Computational Problems
To prove the security of our proposed protocol, we present some important mathematical properties of ECC as follows.
Definition 1. Elliptic Curve Discrete Logarithm Problem (ECDL Problem): Given an elliptic curve E defined over a finite field GF ( p ), and two points Q , P E , it is hard to find an integer k Zq * such that Q = k · P .
Definition 2. Computational Diffie-Hellman Problem (CDH Problem): Given an elliptic curve E defined over a finite field GF ( p ), a point P E of order q , and points A = a · P ; B = b · P , it is hard to find the point C = abP .
Definition 3. The Elliptic Curve Decision Diffie-Hellman Problem (ECDDH Problem): Given an elliptic curve E defined over a finite field GF ( p ), a point P of order q , and points A = a · P , B = b · P , and C = c · P , determine whether or not C = abP , equivalently, whether c a · b (mod p ) or not.
To the best of our knowledge, there is no polynomial time algorithm to solve any of the above-mentioned problems with non-negligible probability [28] .
- 2.3 Hash function
Hash function [29] is an algorithm that takes an arbitrary block of data and returns a fixed-size bit string, and it is easy to compute on every input but hard to compute the input from a given output. Here "easy" and "hard" are to be understood in the sense of computational complexity theory. The one-way hash function has the following properties.
  • • The hash function can be applied to a data block of all sizes.
  • • For any given inputx, it is esay to compute the output.
  • • It is infeasible to derivingxfrom the given valuey=h(x).
  • • It is infeasible to find two different inputs with the same output.
  • • It is infeasible to find two different inputs with the same output.
In the proposed scheme, two kinds of hash function will be used: h (·) and H (·). The hash function h (·) maps binary strings of an arbitrary length to an integer of fixed bit length ( h : {0, 1} * → Z q * ). The hash function H (·) maps a point over the elliptic curve E to a binary strings of a fixed length (H: Ep ( a , b ) → {0, 1} 1 , l is the length of the string). In our scheme, H (·) can be constructed by the hash function h (·): Let Pi be a point over the elliptic curve E , let Px and Py be the X-coordinate and the Y-coordinate of the point Pi , respectively. Then, H (·) can be sonstructed as H ( Pi ) = h ( Px )║ h ( Py ), where ║ is string concatenation operation.
3. The Proposed Scheme
In this section, we propose a novel authentication scheme using ECC to avoid various attacks. ECC is one of the most efficient public key systems nowadays. It has been shown that the ECC has been proven to be successful on the limited hardware [30] . The main idea of the proposed scheme is using the ECC in combination with a secure hash function to encrypt the exchange messages among the user, the server and the registration center ( RC ). Without loss of generality, the proposed authentication scheme consists of four phases: the registration phase, the login phase, the authentication and session key agreement phase and the password change phase. The login and authentication phases are depicted in Fig. 1 , and more details of all these phases are describe as follows.
PPT Slide
Lager Image
The login and authentication phases of our scheme
For the sake of clarity, the notations used in this paper are summarized and defined in Table 1 .
List of notations
PPT Slide
Lager Image
List of notations
- 3.1 System Initialization
Without loss of generality, it is assumed that the multi-server environment includes three kinds of participants: a trusted registration center ( RC ), users and servers. RC is responsible for system initialization, user and server registration and authenticaion. The detailed initialization steps are performed as follows.
At the beginning, RC chooses a prime number p and an elliptic curve equation E over the finite field GF ( p ), and then selects a base point P with the order q over E , where q is a 512-bit prime number and q p . Then, RC selects a random number s Zq * as the master secret key, and computes the public key Ppub = s · P .
Next, RC chooses two secret keys x , y Zq * , and chooses two secure hash functions h (·) and H (·), where h : {0, 1} => Zp * , and H : Ep ( a , b ) => {0, 1} l , l is the length of the string.
Then, RC computes h ( SIDj y ) and h ( SIDj y ), and shares these authentication certificate with the corresponding server Sj via a secure channel.
In the end, RC publishes the public system parameters as { E , GF ( p ), q , P , Ppub , h (·), H (·)} and keeps the master secret key s and values x and y secretly.
- 3.2 The Registration Phase
When a user Ui wants to use this system, he/she has to submit his/her identity and password to RC for registration. The steps of the registration phase are as follows:
Step R1. Ui RC : { IDi , h ( b PWi )}.
The user Ui chooses his/her identity IDi and password PWi freely. Ui ’s terminal generates a random number b . Then, Ui computes h ( b PWi ) and sends the message { IDi , h ( b PWi )} to RC via a common channel.
Step R2. RC computes
Ti = h ( IDi x ) ,
Qi = h ( Ti ),
Vi = Ti h ( IDi h ( b PWi ))
Ri = h ( IDi h ( b PWi )║ x ).
Step R3. RC issues a smart card to Ui , and the card contains { Vi , Hi , Ri , h (·), H (·), E , P }.
Step R4. Ui ’s terminal inserts the value b into the smart card. At last, the smart card contains { Vi , Hi , Ri , b , h (·), H (·), E , P }.
- 3.3 The Login Phase
When the user Ui wants to login to the server Sj , he/she inserts his/her smart card to a terminal (smart phone or PDA) and inputs his/her identity IDi and password PWi .
Step L1. The smart card computes Ti * = Vi h ( IDi h ( b PWi )), Qi * = h ( Ti * ), and checks whether Qi * is equal to Qi . If they are equal, the terminal proceeds to the next step. Otherwise, the smart card rejects this request.
Step L2. Ui Sj : { C 1 , C 2 , TUi }. The smart card chooses a random number k Zq * and computes:
wi = TUi ⊕( IDi h ( b PWi )║ SIDj Ri ),
C 1 = k · P , Pur = k · Ppub ,
C 2 = wi H ( Pur ),
where TUi denotes the current timestamp and SIDj denotes the identity of the destination server. Then, Ui sends the login request { C 1 , C 2 , TUi } to the server Sj for authentication.
- 3.4 The Authentication and Session Key Agreement Phase
Step A1. Sj RC : { SIDj , C 1 , C 2 , C 3 , Nj , TUi , aP }.
When the server Sj receives the login request { C 1 , C 2 , TUi }, it checks whether TUi Ts ≼ △ T , where Ts is the time when Sj receives this request and △ T is the expected time interval for the transmission delay. If so, Sj generates a random number Nj Zq * , then computes m 1 = h ( SIDj y )║ Nj , C 3 = m 1 H ( a · Ppub ), where a is the server Sj ’s master key.
Then, Sj sends the registration request { SIDj , C 1 , C 2 , C 3 , Nj , TUi , aP } to RC via a common channel.
Step A2. Upon receiving { SIDj , C 1 , C 2 , C 3 , Nj , TUi , aP }, RC checks whether TUi TRC ≼ △ T , where TRC is the time when RC receives the above message. If so, RC computes:
Pru = s · C 1 ,
wi * = C 2 H ( Pru ),
m 1 * = C 3 H ( s ·( aP )).
The above formulae can be deduced as follows:
wi * = C 2 H ( Pru ) = C 2 H ( s · C 1 ) = C 2 H ( s ·( k · P )) = C 2 H ( k ·( s · P )) = C 2 H ( k · Ppub ) = C 2 H ( Pur ) = wi = TUi ⊕( IDi h ( b PWi )║ SIDj Ri ),
m 1 * = C 3 H ( s ·( aP )) = C 3 H ( a ·( sP )) = C 3 H ( a · Ppub ) = m 1 = h ( SIDj y )║ Nj .
Therefore, RC can extract the user’s identity IDi and h ( b PWi ) by computing wi TUi . At this point, RC has both Ui ’s and Sj ’s identity. RC computes h ( SIDj y ) and compares it with the value extracted from m 1 * . If they are equal, RC considers Sj as a legal server. Then RC computes h ( IDi h ( b PWi )║ x ) and compares it with the value Ri which is extracted from wi * . If h ( IDi h ( b PWi )║ x ) = Ri , RC considers Ui as a legal user. Then RC sends a message to Sj in the next step.
Step A3. RC Sj : { C 4 , C 5 , TUi }. The RC computes:
m 2 = h ( SIDj y )║ IDi h ( IDi x ),
m 3 = h ( IDi x )║ SIDj Nj h ( SIDj y ),
C 4 = m 2 H ( s ·( aP )),
C 5 = m 3 H ( Pru ).
Then, RC sends the message { C 4 , C 5 , TUi } to the server Sj via a common channel.
Step A4. Sj Ui : { C 5 , Nj , TUi }. Upon receiving { C 4 , C 5 , TUi }, Sj computes m 2 * = C 4 H ( a ·( Ppub )), where a is Sj ’s master key. Then, Sj extracts the value h ( SIDj y ) from m 2 * and compares it with of h ( SIDj y ) stored in its memory to verify RC . If they are equal, Sj considers Ui as a legal user and sends the message { C 5 , Nj , TUi } to the user Ui . Sj further computes SK = h ( h ( IDi x )║ h ( SIDj y )║ TUi Nj ) as the session key for securing communications with Ui .
Step A5. After receiving { C 5 , Nj , TUi }, Ui computes m 3 * = C 5 H ( k · Ppub ), then Ui extracts the value h ( IDi x ) from m 3 * and computes Hi * = h ( h ( IDi x )). Next, Ui compares Hi * with Hi . If they are equal, Ui considers Sj as a legal server and further computes SK = h ( h ( IDi x )║ h ( SIDj y )║ TUi Nj ) as the session key for securing communications with Sj .
- 3.5 The Password Change Phase
This phase is invoked whenever Ui wants to change his/her password PWi to a new password PWnew . The steps of the password change phase are as follows.
Step P1. Ui inserts his/her smart card into the terminal and then keys his/her IDi and PWi .
Step P2. The smart card computes Ti = Vi h ( IDi h ( b PWi )), Qi * = h ( Ti ) and checks whether Qi * is equal to Qi , If they are equal, the smart card lets Ui choose a new password PWnew and a new random number bnew to compute:
h ( bnew PWnew ),
Vnew = Ti h ( IDi h ( bnew PWnew )),
C 6 = ( IDi h ( bnew PWnew ))⊕ H ( k · Ppub ).
Then, Ui sends the message { IDi , C 1 , C 2 , C 6 , TUi } to RC via a secure channel. Step P3. Upon receiving { IDi , C 1 , C 2 , C 6 , TUi }, RC checks whether the time stamp TUi is valid. If so, RC determines the legitimacy of Ui using the values C 1 and C 2 . Then, RC computes C 6 H ( s · C 1 ) = C 6 H ( s ·( k · P )) = C 6 H ( k · Ppub ) = IDi h ( bnew PWnew ).
Step P4. RC calculates Rnew = h ( IDi h ( bnew PWnew )║ x ), C 7 = ( Rnew h ( IDi x )║ TUi )⊕ H ( s · C 1 ) and then sends the message { IDi , C 7 , TUi } to Ui .
Step P5. After receiving { IDi , C 7 , TUi }, Ui computes C 7 H ( k · Ppub ) = C 7 H ( s ·( k · P )) = C 7 H ( s · C 1 ) = Rnew h ( IDi x )║ TUi . Then, Ui computes Qi * = h ( h ( IDi x )) and compares it with Qi stored in his/her smart card to check the validity of this message. If they are the same, the smart card replaces b , Vi , Ri with bnew , Vnew , and Rnew , respectively.
4. Security Analysis of the Proposed Scheme
In this section, we use the random oracle model to analyze the security of our scheme. The random oracle model is often used to verify the security of the key establishment protocol or the signature scheme. In the model, each participant appeared in the authentication and key agreement scheme is treated as an oracle, and the adversary can access these oracles by sending some queries.
- 4.1 Adversarial Model
In this section, we define the adversarial model of a mutual authentication and key agreement protocol. Readers can refer to [33] to get the detailed descriptions about the following definitions. Assume that the multi-server environment contains three types of participants: n users U = { U 1 , U 2 , …, Un }, m servers S = { S 1 , S 2 , …, Sm } and a registration center ( RC ). The lth instance of Ui (resp. Sj ) is denoted by Π l U (resp. Π l S ). An adversary A is a probabilistic polynomial time machine. It is assumed that A is able to potentially control all common communications in the proposed scheme via accessing to a set of oracles (as defined below). The proposed scheme’s public parameters are known by each participant (including the users, servers and RC ).
Extract ( IDi ): In this query model, an adversary A is able to get the private key of IDi .
•Send(Π kc , M ): The adversary A can send a message M to the oracle Π kc , where c ∈ { U , S , RC }. When receiving the message M , Π kc responds to A according to the proposed scheme.
h ( mi ): When an adversary A makes this hash query with the message mi , the oracle Π kc returns a random number r 1 and records ( mi , r 1 ) into a list Lh . The list is initially empty.
H ( Pi ): When an adversary A makes this hash query with a point Pi over the curve E , the oracle Π kc returns a random number r 2 and records ( Pi , r 2 ) into a list LH . The list is also empty initially.
Reveal kc ): In this query model, the adversary A can obtain a session key SK from the oracle Π kc if the oracle has accepted. Otherwise, Π kc returns a null to A .
Corrupt ( IDi ): The adversary A can issue this query to IDi and gets back its private key.
Test kc ): When A asks this query to an oracle Π kc , the oracle chooses a random bit b ∈{0, 1}. If b = 1, then Π kc returns the session key. Otherwise, it returns a random value. This query measures the semantic security of the session key.
In this model, the adversary A can make Send , Reveal , Corrupt and Test queries. Note that the capabilities of the adversary can make finite queries under adaptive chosen message attacks [33] .
- 4.2 Security Analysis
In this subsection, we first demonstrate that the proposed scheme can achieve the secure authentication and key agreement under the random oracle model. Then, we analyze the other security properties about the proposed scheme.
- 4.2.1 Formal analysis under the random oracle model
In this subsection, we show that the proposed scheme can provide the secure authentication and key agreement under the computational Diffie-Hellman problem (CDH) assumption.
Theorem 1 . Assume that an adversary A can violate the proposed scheme with a non-negligible advantage ε and makes at most qu , qs , qh , and qH queries to the oracle of the user Π i U , oracle of the server Π j S , h , and H , respectively. Then we can construct an algorithm to solve the CDH problem with a non-negligible advantage.
Proof. We first classify the types of attack into two categories: impersonating the user to communicate with RC and impersonating the server to communicate with RC . Then we can construct an algorithm to solve the CDH problem.
For an instance of the CDH problem { q , P , Q 1 = xP , Q 2 = yP }, B simulates the system initializing algorithm to generate the system parameters { E , q , P , Ppub = Q 2 , h , H }. h and H are random oracles controlled by B . Then, B gives the system parameters to A . B interacts with A as follows.
h-query : B maintains a list Lh of tuples ( stri , hi ). When A queries the oracle h on ( stri , hi ), B responds as follows:
If stri is on Lh , then B responds with hi . Otherwise, B randomly chooses an integer hi that is not found in Lh , and adds ( stri , hi ) into Lh , then responds with hi .
H-query : B maintains a list LH of tuples ( Pc , Hc ). When A queries the oracle H on ( Pc , Hc ), B responds as follows:
If Pc is on LH , then B responds with Hc . Otherwise, B randomly chooses an integer Hc that is not found in LH , and adds ( Pc , Hc ) into LH , then responds with Hc .
Reveal-query : When the adversary A makes a Reveal mc ) query, B responds as follows. If Π mc is not accepted, B responds none. Otherwise, B examines the list Lh and responds with the corresponding hi .
Send-query : When the adversary A makes a Send mc , “start”) query, B responds as follows. If Π mc = Π m u , B sets C 1 Q 1 , and randomly generates the values C 2 and TUi , and responds with { C 1 , C 2 , TUi }. Otherwise, B generates a random number k and computes C 1 = kP , C 2 = wi kPpub and responds with { C 1 , C 2 , TUi }, where wi is generated by B . The simulation works correctly since A cannot distinguish whether wi is valid or not unless A knows the RC ’s private key.
When the adversary A makes a Send mc , ( SIDj , C 1 , C 2 , C 3 , Nj , TUi , aP )) query, B responds as follows. If the Π m c matches the Π m u , B cancels the game. Otherwise, B computes wi = C 2 H ( Pru ), where Pru is generated in Send mc , “start”). Then B responds the corresponding message according to the description of the proposed scheme.
When the adversary A makes a Send mc , ( C 5 , Nj , TUi )) query, B responds as follows. If the Π mc matches the Π mS , B cancels the game. Otherwise, B computes m 3 * = C 5 H ( pur ) and then checks the RC . If so, B computes the session key SK = h ( h ( IDi x )║ h ( SIDj y )║ TUi Nj ), where h ( SIDj y ) is extracted from m 3 * , and h ( IDi x ) is extracted from Lh .
If the adversary A can violate a user to the RC authentication, it means that A can get the values of h ( IDi x ) and Ri = h ( IDi h ( b PWi )║ x ) from the list Lh and then compute the values of C 1 and C 2 . In such case B can extract the corresponding Hc = s ·( kP ) in LH using Q 2 = Ppub , C 1 = kP with non-negligible probability. Therefore, if the adversary A can violate a user to the RC authentication, then B is able to solve the CDH problem with non-negligible probability. It is a contradicting to the intractability of the CDH problem. In addition, x is the RC ’s secret value and h is a secure hash function. Therefore, the probability that A can compute the value Ri = h ( IDi h ( b PWi )║ x ) is negligible. From the above analysis, we can see that the probability that A can violate the user to the RC authentication is negligible.
If the adversary A can violate the server to RC authentication, it means that A can get h ( SIDj y ) and Hc = aP from the lists Lh and LH , respectively, and further computes C 3 = m 1 H ( a · Ppub ) and makes a Send mc , ( SIDj , C 1 , C 2 , C 3 , Nj , TUi , aP )) query. Then B must have made the corresponding Hc = a ·( Ppub ) = s ·( aP ) from the list LH with non-negligible probability. Consequently, B is able to solve the CDH problem with non-negligible probability, which is a contradicting to the intractability of the CDH problem. Besides, y is the RC ’s secret value that the adversary cannot obtain, the hash functions h and H are collision-resistant hash functions. Therefore, the probability that A can violate the server to the RC authentication is negligible.
If B is able to win such a game, then B must have made the corresponding h query of the form ( stri , hi ) to find the correct hi (the session key) with non-negligible probability since h is a random oracle. The string stri contains the values of h ( IDi x ), h ( SIDj y ), TUi and Nj . If B can get the value h ( IDi x ), it can find the corresponding Hc in LH with the probability 1/ qH and output the corresponding Pc as a solution to the CDH problem. Therefore, if the adversary A can compute the correct session key with non-negligible probability ε , then the probability that B solves the CDH problem is ε / qh · qH . It is a contradicting to the intractability of the CDH problem.
- 4.2.2 Other security features
- •Replay attack
A replay attack is a form of network attack where an authentication session is replayed by an attacker to fool a computer into granting access. In the proposed scheme, the time stamp TUi is used to resist this type of attack. After incepting the previous login request { C 1 , C 2 , TUi } from the user Ui , the adversary may replay the same message to the service Sj . However, he/she cannot launch a replay attack. Since the time stamp TUi is a parameter of the value C 2 , the replay attack can be filtered obviously by the server. After receiving the message { C 1 , C 2 , TUi }, the server firstly checks the validity of time stamp TUi . If the time stamp is not valid, the request will be rejected. If the adversary modifies the time stamp TUi with a new time stamp TUi * , he/she cannot compute the corresponding C 2 * without the knowledge of H ( k · Ppub ). Thus, the bogus TUi * can be found by checking C 2 .
In addition, when an attacker replays the message { SIDj , C 1 , C 2 , C 3 , Nj , TUi , aP } or { C 5 , Nj , TUi } to impersonate as a legal server Sj , he/she has no capacity to compute the value C 3 or C 5 . In the proposed scheme, the values of C 3 and C 5 are computed as C 3 = m 1 H ( a · Ppub ), C 5 = m 3 H ( s · C 1 ). Since Nj is a parameter of m 1 and m 3 , any change of Nj can affect the values of C 3 and C 5 , indirectly. When the adversary modifies the value of Nj , RC or users can detect the replay attack immediately. From the above analysis, we can see that our scheme can resist replay attack.
- •Stolen smart card attack
We assume that the user Ui ’s smart card has been lost or stolen, so the attacker can breach the values { Vi , Hi , Ri , b , h (·), H (·), E , P } which are stored in the smart card. It is important to note that the adversary cannot get the RC ’s secret value x , hence he/she cannot guess the Ui ’s identity IDi and password PWi from the breached values in polynomial time since they are protected by a secure hash function. Consequently, the adversary cannot compute h ( b PWi ) and further compute the correct wi = TUi ⊕( IDi h ( b PWi )║ SIDj Ri ). As a result, the adversary cannot use the lost or stolen smart card to carry out impersonation attack. From the above analysis, it can be seen that the proposed scheme effectively resists the stolen smart card attack.
- •Impersonation attack
In the proposed scheme, every legal user must be registered in the RC when he/she wants to use this authentication scheme. Then, the RC issues Ui a unique value Ri = h ( IDi h ( b PWi )║ x ), where x is the RC ’s secret value and PWi is Ui ’s password. If an adversary wants to impersonate as the user Ui to communicate with the RC , he/she cannot compute the correct C 2 without the knowledge of Ri . Thus, the attacker has no way to impersonate a legitimate user to make a request.
In addition, every server has a unique value h ( SIDj y ) and only the RC knows all the servers’ authentication certificates. If an adversary wants to impersonate as the server to communicate with the RC , he/she cannot compute the correct C 3 without the authentication certificate of h ( SIDj y ). Thus, the adversary cannot impersonate as a server to communicate with other entities. From the user’s or the server’s perspective, only the legal RC has the secret values x and y . Consequently, there is no way for an attacker to impersonate as the RC . From the above analysis, it can be seen that the proposed scheme can withstand this type of attack.
- •User’s anonymity
In the registration phase and password change phase of our authentication scheme, the user communicates with the RC via a secure channel. Therefore, other entities (including the adversary and other users) cannot obtain the user’s identity. In the login phase of the proposed scheme, the user Ui submits the message { C 1 , C 2 , TUi } to the server Sj for authentication. However, Ui ’s identity IDi is contained in the value C 2 . The adversary cannot extract Ui ’s identity without the knowledge of H ( Pur ). In the authentication and session key agreement phase of the proposed scheme, the RC responds the message { C 4 , C 5 , TUi } to the server Sj . The value h ( IDi x ) is contained in C 4 and C 5 , respectively. The adversary cannot extract h ( IDi x ) unless he/she gets the values of H ( s ·( aP )) and H ( Pru ). In addition, since the time stamp TUi is a parameter of the value C 2 , C 2 will be different for each session when the user logins to the system at different time. Therefore, the attacker cannot distinguish a certain user from different sessions. From the above analysis, it can be seen that our proposed protocol can provide user’s anonymity.
- •Man-in-the-middle attack
A man-in-the-middle attack would be able to successfully only when the attacker can impersonate each party to cheat other parties. In the proposed scheme, the exchange values C 2 , C 3 , C 4 , and C 5 are XORed by H ( Pur ) and H ( a · Ppub ), respectively. Since the adversary cannot compute the values of H ( Pur ) and H ( a · Ppub ), he/she cannot extract the detailed information ( IDi , h ( b PWi ), h ( SIDj y ), etc.) from the values of C 2 , C 3 , C 4 , and C 5 . Thus, it is clear that the adversary cannot launch the man-in-the-middle attack to cheat the user or the server.
5. Performance Evaluation
In this section, we evaluate the performance of our scheme and compare it with other related authentication schemes. It is generally known that most of the mobile devices have limited power resources and computing capability. Therefore, one of the most important concerns of design authentication scheme in mobile environment is power consumption (include computation cost and communication cost). We first evaluate the computational cost and then focus on the communication cost of the proposed scheme. Since exclusive-OR operation requires extremely small computational cost, we neglect its computation cost.
For the convenience of evaluating the computational cost, we define some notations as follows.
  • •Tmul: The time of executing a scalar multiplication operation of point.
  • •Tadd: The time of executing an addition operation of points.
  • •Tpair: The time of executing a bilinear pairing operation.
  • •Th: The time of executing a one-way hash function.
  • •Tmtph: The time of executing a map-to-point hash function.
  • •TH: The time of executing a hash functionH(·) used in this paper.
  • •Texp: The time of executing a modular exponential operation.
In Table 2 , we summarize the computation cost of the proposed user authentication and key agreement scheme. The user’s terminal is a low-power computing device while the server and the RC are regarded as powerful devices. Since the authentication information contained by the user and the server (i.e. Ri = h ( IDi h ( b PWi )║ x ) and h ( SIDj y )) are protected by a secure hash function h (·), the RC needs only to compute several hash functions to authenticate the legality of both the user and the server. From Table 2 , we can see that the user requires only 2 Tmul + 2 Th + TH in login phase and 2 Th in authentication and key agreement phase. In authentication and key agreement phase, The RC and the server require only 2 Tmul + 5 Th + 2 TH and Tmul + 2 Th + TH , respectively.
Computation costs of the proposed scheme
PPT Slide
Lager Image
Computation costs of the proposed scheme
In order to present an objective and detailed comparison between our scheme and other related authentication schemes, we make the computation costs analysis on the basis of the implementation results in [31] . In [31] , The hardware platform is Philips HiPersmart card and Pentium IV offer maximum clock speeds of 36 MHz and 3 GHz, respectively. In order to provide adequate security, a popular and valid choice would be to use the elliptic curve y 2 = x 3 + ax + b defined on a finite field Fp with p = 512 bits and a large prime order q = 160 bits. All the operations are built with MIRACLE [32] , a standard cryptographic library. Table 3 lists the experimental data for related pairing-based operations on the Philips HiPersmart card and on the Pentium IV processor, respectively.
Computational cost on the client side and the server side
PPT Slide
Lager Image
Computational cost on the client side and the server side
In Table 4 , we demonstrate the comparisons between our proposed scheme and the previously authentication schemes on elliptic curve cryptography in terms of the computation cost, the execution time and security properties. The execution time appeared in Table 4 are measured based on the computational cost listed in Table 3 . In Table 4 , we assume that the execution time of the hash function H (·) used in our scheme is equal to Th because H (·) can be constructed by the hash function h (·): Let Pi be a point over E , let Px and Py be the X-coordinate and the Y-coordinate of the point Pi , respectively. Then, we can construct H (·) as H ( Pi ) = h ( Px Py ), where ║ is string concatenation operation. Therefore, we can see that TH is equal to Th . From Table 4 , we can see that Yang and Chang’s scheme suffered from impersonation attack. Based on an overall consideration of efficiency and security, our scheme is better than the previously proposed schemes listed in Table 4 . Therefore, the proposed scheme is more suitable for the mobile client server environments.
Comparisons between the previously proposed schemes and our scheme
PPT Slide
Lager Image
Comparisons between the previously proposed schemes and our scheme
The communication cost of the proposed scheme includes the exchange messages involved in the login and authentication phase. While, in the proposed authentication scheme, only the user’s terminal is a resource -constrained device. Thus, we do not consider the communication cost between the server and the RC . Therefore, the number of communication parameters includes { C 1 , C 2 , TUi } and { C 5 , Nj , TUi }. In order to provide adequate security, as mentioned above, we choose the elliptic curve E defined on a finite field Fp with p = 512 bits and a large prime order q = 160 bits. Thus, the bit-length of a point P is 1024 bits. Since the parameter C 1 is a point on the curve E , the bit-length of C 1 is 1024 bits, too. In addition, we set the bit-length of the time stamp ( TUi ), the identity number ( IDi , SIDj ) and the random number ( Nj ) are 32 bits, 128 bits and 128 bits, respectively. The bit-length of the hash functions h (·) and H (·) are 160 bits and 512 bits, respectively. Therefore, the communication cost { C 1 , C 2 , TUi } and { C 5 , Nj , TUi } is 1568 (1024+512+32) bits and 672 (512+128+32) bits, respectively. Therefore, the communication cost of the proposed scheme is 3264 bits, which is very small in practice. From the above analysis, we can see that the proposed scheme is well suited for mobile client server environment in term of the communication cost.
6. Conclusion
In this paper, we proposed a secure and efficient ECC-based authentication and key agreement scheme for multi-server environments and low-power mobile devices. Under the CDH problem assumption and the random oracle model, we demonstrated that the proposed scheme is secure against impersonation attack and provides the session key protection. Then, we analyze some other security features about our scheme such as replay attack and stolen smart card attack. According to the comparisons in Section 5, the proposed scheme is more efficient and practical than the other related authentication schemes, and is more suitable for multi-server environment with low-power devices.
Acknowledgements
The authors are grateful to the editor and anonymous reviewers for their valuable suggestions which improved this paper. This research was partially supported by Foundation of China and National High-Tech (863) Programs Grant No. 2011AA01A101, the National Natural Science Foundation of China under Grant No. 61300220 & 61271041, the National Major Science and Technology Special Project of China under Grant No.2012ZX03005008, and FP7 Integrated Project iCore (Internet Connected Objects for Reconfigurable Eco-systems) under Grant No. 287708.
BIO
Junsong Zhang received his master’s degree in computer software and theory from Zhengzhou University (ZZU) in 2008 and Ph.D. degree in computer science and technology from Beijing University of Posts and Telecommunications (BUPT) in 2014. Dr. Zhang is a lecturer of Zhengzhou University of Light Industry (ZZULI). His research interests include information security and mobile network, etc.
Jian Ma was born in 1959, obtained his Ph.D degree at Helsinki University of Technology in 1994. He is now a professor of Beijing University of Posts and Telecommunications. His research interests span the area of mobile internet, mobile internet of things, wireless sensing network and social network analysis. He has published more than 300 papers in different journals and conferences.
Xiong Li received his master’s degree in mathematics and cryptography from Shaanxi Normal University (SNNU) in 2009 and Ph.D. degree in computer science and technology from Beijing University of Posts and Telecommunications (BUPT) in 2012. Dr. Li now is a lecturer of Hunan University of Science and Technology (HNUST). He has published more than 15 referred journal papers. His research interests include cryptography and information security, etc.
Wendong Wang received the B.S. and M.E. degrees, both in computer science, from Beijing University of Posts and Telecommunications (BUPT), Beijing, China in 1985 and 1991, respectively. He is currently a professor of State Key Lab of Networking and Switching Technology at BUPT. His research interests are IP QoS, next generation Internet, and next generation internet services.
References
Lamport L. 1981 “Password authentication with insecure communication” Communication of ACM Article (CrossRef Link) 24 770 - 772    DOI : 10.1145/358790.358797
Horng G. 1995 “Password authentication without using password table” Information Processing Letters Article (CrossRef Link) 55 (5) 247 - 250    DOI : 10.1016/0020-0190(95)00087-S
Jan J. K. , Chen Y. Y. 1998 “Paramita Wisdom password authentication scheme without verification tables” The Journal of Systems and Software Article (CrossRef Link) 42 (1) 45 - 57    DOI : 10.1016/S0164-1212(98)00006-5
Liao Y. P. , Hsiao C. M. 2013 “A novel multi-server remote user authentication scheme using self-certified public keys for mobile clients” Future Generation Computer Systems Article (CrossRef Link) 29 (3) 886 - 900    DOI : 10.1016/j.future.2012.03.017
He D. , Chen J. H. , Hu J. 2012 “An ID-based client authentication with key agreement protocol for mobile client-server environment on ECC with provable security” Information Fusion Article (CrossRef Link) 13 (3) 223 - 230    DOI : 10.1016/j.inffus.2011.01.001
Hwang M. S. , Chong S. K. , Chen T. Y. 2010 “DoS-resistant ID-based password authentication scheme using smart cards” Journal of Systems and Software Article (CrossRef Link) 83 (1) 163 - 172    DOI : 10.1016/j.jss.2009.07.050
Song R. G. 2010 “Advanced smart card based password authentication protocol” Computer Standards & Interfaces Article (CrossRef Link) 32 (5-6) 321 - 325    DOI : 10.1016/j.csi.2010.03.008
Li X. , Niu J. W. , Khan M.K. , Liao J. G. 2013 “An enhanced smart card based remote user password authentication scheme” Journal of Network and Computer Applications Article (CrossRef Link) 36 (5) 1365 - 1371    DOI : 10.1016/j.jnca.2013.02.034
Li L. H. , Lin L. C. , Hwang M. S. 2001 “A remote password authentication scheme for multi-server architecture using neural networks” IEEE Transactions on Neural Networks Article (CrossRef Link) 12 (6) 1498 - 504    DOI : 10.1109/72.963786
Juang W. S. 2004 “Efficient multi-server password authenticated key agreement using smart cards” IEEE Transaction on Consumer Electronics Article (CrossRef Link) 50 (1) 251 - 255    DOI : 10.1109/TCE.2004.1277870
Chang C. C. , Lee J. S. 2004 “An efficient and secure multi-server password authentication scheme using smart cards” in Proc. of the third international conference on cyberworlds November Article (CrossRef Link) 417 - 22
Tsai J. L. 2008 “Efficient multi-server authentication scheme based on one-way hash function without verification table” Computers & Security Article (CrossRef Link) 27 (3-4) 115 - 21    DOI : 10.1016/j.cose.2008.04.001
Liao Y. P. , Wang S. S. 2009 “A secure dynamic ID based remote user authentication scheme for multi-server environment” Computer Standard & Interfaces Article (CrossRef Link) 31 (1) 24 - 29    DOI : 10.1016/j.csi.2007.10.007
Hsiang H. C. , Shih W. K. 2009 “Improvement of the secure dynamic ID based remote user authentication scheme for multi-server environment” Computer Standards & Interfaces Article (CrossRef Link) 31 (6) 1118 - 1123    DOI : 10.1016/j.csi.2008.11.002
Lee C. C. , Lin T. H. , Chang R. X. 2011 “A secure dynamic ID based remote user authentication scheme for multi-server environment using smart cards” Expert Systems with Applications Article (CrossRef Link) 38 (11) 13863 - 13870
Sood S. K. , Sarje A. K. , Singh K. 2011 “A secure dynamic identity based authentication protocol for multi-server architecture” Journal of Network and Computer Applications Article (CrossRef Link) 34 (2) 609 - 618    DOI : 10.1016/j.jnca.2010.11.011
Chuang Y. H. , Tseng Y. M. 2012 “Towards generalized ID-based user authentication for mobile multi-server environment” International Journal of Communication System Article (CrossRef Link) 25 (4) 447 - 460    DOI : 10.1002/dac.1268
Li X. , Ma J. , Wang W. D. , Xiong Y. P. , Zhang J. S. 2013 “A novel smart card and dynamic ID based remote user authentication scheme for multi-server environments” Mathematical and Computer Modelling Article (CrossRef Link) 58 (1-2) 85 - 95    DOI : 10.1016/j.mcm.2012.06.033
Li X. , Xiong Y. P. , Ma J. , Wang W. D. 2012 “An efficient and security dynamic identity based authentication protocol for multi-server architecture using smart cards” Journal of Network and Computer Applications Article (CrossRef Link) 35 (2) 763 - 769    DOI : 10.1016/j.jnca.2011.11.009
Li C. , Lee C. , Weng C. , Fan C. 2013 “An Extended Multi-Server-Based User Authentication and Key Agreement Scheme with User Anonymity” KSII Transactions on Internet & Information Systems Article (CrossRef Link) 7 (1) 119 - 131    DOI : 10.3837/tiis.2013.01.008
Li X. , Zhang Y. , Liu X. , Cao J. 2013 “A Lightweight Three-Party Privacy-preserving Authentication Key Exchange Protocol Using Smart Card” KSII Transactions on Internet & Information Systems Article (CrossRef Link) 7 (5) 1313 - 1327    DOI : 10.3837/tiis.2013.05.021
Nam J. , Choo K.K.R. , Kim M. , Paik J. , Won D. 2013 “Dictionary Attacks against Password-Based Authenticated Three-Party Key Exchange Protocols” KSII Transactions on Internet & Information Systems Article (CrossRef Link) 7 (12) 3244 - 3260    DOI : 10.3837/tiis.2013.12.016
Das M. L. , Saxena A. , Gulati V. P. , Phatak D. B. 2006 “A novel remote client authentication protocol using bilinear pairings” Computer and Security Article (CrossRef Link) 25 (3) 184 - 189    DOI : 10.1016/j.cose.2005.09.002
Fang G. F. , Huang G. X. “Improvement of recently proposed Remote User Authentication Schemes” http://eprint.iacr.org/2006/200
Giri D. , Srivastava P.D. “An improved remote client authentication protocol with smart cards using bilinear pairings” http://eprint.iacr.org/2006/274
Yang J. , Chang C. 2009 “An ID-based remote mutual authentication with key agreement protocol for mobile devices on elliptic curve cryptosystem” Computers and Security Article (CrossRef Link) 28 (3-4) 138 - 143    DOI : 10.1016/j.cose.2008.11.008
Hankerson D. , Menezes A. , Vanstone S. 2004 Guide to Elliptic Curve Cryptography Springer New York http://dl.acm.org/citation.cfm?id=940321
Li F. , Xin X. , Hu Y. 2008 “Identity-based broadcast signcryption” Computer Standard and Interfaces Article (CrossRef Link) 30 (1-2) 89 - 94    DOI : 10.1016/j.csi.2007.08.005
Rogaway P. , Shrimpton T. 2004 “Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance” Lecture Notes in Computer Science Article (CrossRef Link) 3017 371 - 388
David J. M. , Matt W. , Michael D. S. 2008 “Implementing Public-Key Infrastructure for Sensor Networks” ACM Transactions on Sensor Networks Article (CrossRef Link) 4 (4) 1 - 23
Scott M. , Costigan N. , Abdulwahab W. 2006 “Implementing cryptographic pairings on smartcards” Springer-Verlag in Proc. of Cryptographic Hardware and Embedded Systems - CHES 2006 LNCS, vol. 4249, Article (CrossRef Link) 134 - 147
Shamus Software http://www.shamus.ie/index.php.
Bellare M. , Pointcheval D. , Rogaway P. 2000 “Authenticated key agreement secure against dictionary attacks” Springer-Verlag in Proc. of the Advances in Cryptology - EUROCRYPT 2000 LNCS, vol. 1807, Article (CrossRef Link) 139 - 155