158 ECC-BASED THREE-FACTOR AUTHENTICATION SCHEME FOR MULTI-SERVER ENVIRONMENT Rahul Kumar*, Mridul K. Gupta and Saru Kuamri Chaudhry Charan Singh University, Meerut, India Abstract Due to advances in computing technology and constraints in the design of the authentication protocols for single-server environment, the authentication protocols for multi-server settings have been a preferred field of research. Recently, Ali and Pal designed a three factor-based authentication protocol for multi-server environment using ECC and they claimed that their protocol is secure against numerous attacks. They also asserted that their protocol is quite efficient. In this paper, we investigate Ali and Pal's protocol and point out that their protocol is not secure against replay attack and session-specific temporary information attack. We also present an improvement of Ali and Pal's protocol. Keywords 1 Multi-Server, Authentication, Replay Attack 1. Introduction 2. Preliminaries In the digital information world, users can easily obtain various kind of services from the Table 1 shows symbols and their meaning. distributed networks anywhere and anytime such as online shopping, online bank and pay- 3. Review of Ali and Pal’s protocol TV. Ordinary user authentication protocols are fit to tackle security issues for the single Ali and Pal’s protocol includes six phases. user/server design scenarios. Nowadays, authentication protocols for multi-server Beginning from initialization phase, they architectures play a prime role in the Internet discussed server enrollment phase, user world. The multi-server system contains three enrollment phase, login phase, authentication participants, including users, servers, and the and key agreement phase and password change registration centre. The registration centre as phase. the relied third-party, administers all registered servers and users. A multi-server authentication 3.1. Initialization Phase scheme offers services to be accessed from different servers with one time registration. To boot up the system, RC selects a generator P of elliptic curve and chooses a Ali and Pal [1] presented a three factor-based secret key y as the system parameter. authentication scheme in a multi-server environment using ECC. This paper reviews Ali and Pal’s protocol [1] and shows its weaknesses, 3.2. Server Enrollment Phase such as session-specific temporary information leakage attack and replay attack. To conquer specific The server enrolls itself at the registration weaknesses, we design an amended protocol. center RC. Server selects its own identity SIDj ISIC2021: International Semantic Intelligence Conference, February 25–27, 2021, New Delhi, India EMAIL: rahulss.rahul1991@gmail.com (A. 1); mkgupta2002@hotmail.com (A. 2); saryusiirohi@gmail.com (A. 3) ORCID: 0000-0002-2673-2109 (A. 1) ©️ 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 159 and transfers {SIDj} to RC through open h(UIDi*||PWi*||H(Bi*)) and checks Zi* =? Zi. If channel. When the message {SIDj} is received the equality does not hold then the connection by RC from the server, then RC evaluates AH = is disrupted by the user. Otherwise, the user h(SIDj || y). RC transmits the information {AH} chooses a random number Jc and evaluates A1 = to the server through secure channel. Jc·P, A2 = H(B1)·P + A1, A3 = h(UIDi || A1 || SIDj || Hi) and user transmits the login message Table 1 {HIDi, Hi, A2, A3} to RC through open channel. Symbol Meaning Sj jth server 3.5. Authentication and Key RC The registration centre agreement Phase Ui The user When the login request message {HIDi, Hi, P Generator of elliptic curve A2, A3} is received from the user then RC SIDj Server’s identity evaluates Dech(x)(HIDi) = [UIDi, J], Mi* = Hi – h(UIDi || y)·P, A1* = A2 – Mi*, A3* = h(UIDi || A1* UIDi User’s identity || SIDj || Hi) and checks A3* =? A3. If the equality Bi User’s biometric does not hold then the request is dropped by RC. Otherwise, RC chooses an arbitrary number Js H(·) Bio-hash function and evaluates HIDinew = Ench(x)(UIDi || Jsc), Xi = h(·) Hash function Ench(SIDj||y)[UIDj || A1 || H(Bi)], A4 = Jsc·P, A5 = A4 + H(Bi) ·P, A6 = h(A4 || HIDinew || SIDj) and PWi User’s password transmits the message{A5, A6, HIDinew, Xi} to J, Jc, Js, jsc Random numbers the server through open channel. After receiving the message {A5, A6, HIDinew, T1, T2, T3, T4, Timestamps Xi} from RC, server evaluates Dech(SIDj||y)(Xi) = T5 [UIDi || A1 || H(Bi)], A4* = A5 – H(Bi)·P, A6* = SC Smart card h(A4* || HIDinew || UIDi || SIDj) and checks A6* =? A6. If the equality does not hold then the SK Session key connection is disrupted by the server. || Concatenation Otherwise, server chooses Js and evaluates A7 = Js·P, A8 = A7 + A1, A9 = h(HIDinew || A7 || A4 || H(Bi)·P) and transmits the message {HIDinew, A9, A8, A5} to the user. 3.3. User Enrollment Phase After receiving the message {HIDinew, A9, A8, A5} from the server, user evaluates A7* = A8 – First, user selects his/her identity UIDi, A1, A4* = A5 – H(Bi)·P, A9* = h(HIDinew || A7* || imprints Bi and forwards the message {UIDi, A4* || H(Bi)·P) and checks A9* =? A9. If the H(Bi)} to RC through open channel. When a equality does not hold then the connection is request message is received form the user then disrupted by the user. Otherwise, user evaluates RC selects a random number J and evaluates SK = h(Jc·P || Jsc·P || Js·P), Ni = SK·P + h(IDi || HIDi = Ench(x) (UIDi || J), Mi = H(Bi)·P, Ei = H(Bi))·P. Now the user transmits message {Ni} h(UIDi || y)·P, Hi = Mi + Ei. Now RC inserts all to the server through open channel. Note that information {Hi, HIDi, P, Ek/Dk, h(·), H(·)} into the user changes HIDinew with HIDi into SC to SC and forwards {SC} to the user. After avoid user untraceability attack. receiving the message {SC} from RC, user After receiving the message {Ni} from the evaluates Zi = h(UIDi || PWi || H(Bi)) and also user, the server evaluates SK* = h(Jc·P || Jsc·P || inserts Zi into SC. Js·P), Ni* = SK*·P + h(UIDi || H(Bi)·P) and checks Ni* =? Ni. If the equality does not hold then the connection is disrupted by the server. 3.4. Login Phase Otherwise, the connection is created. User embeds SC and enters UIDj*, PWi* and imprints Bi*. Now SC evaluates Zi* = 160 3.6. Password Change Phase to the user. After getting the information A8, ℋ can compute A7* = A1* – A8 = Js·P. Step 5: After evaluating all the temporary User can modify his/her password easily random numbers Jsc and Js from Jc, ℋ can find without interfering with the server. First, user out SK = h(Jc·P || Jsc·P || Js·P) by using these inserts his/her smartcard into a card reader and information. Therefore, Ali and Pal’s protocol enters UIDj*, PWi* and also imprints Bi*. Now, is suffers from session-specific temporary the smartcard reader evaluates Zi* = h(UIDj* || information attack. PWi* || H(Bi*)) and verifies Vi* =? Vi. If the equality does not hold then the connection is ended. Otherwise, the user selects new If Jc is compromised and becomes known to the password PWinew and evaluates Zinew = h(UIDi || attacker, then the attacker eavesdrops the PWinew || H(Bi*)). Finally, it interchanges Zi with messages {HIDi, Hi, A2, A3}, {A5, A6, HIDinew, Zinew in memory of the smartcard. Xi} and {HIDinew, A9, A8, A5} transmitted via insecure channel. Now, the attacker has Jc, A2, A5 and A8. 4. Cryptanalysis of Ali and Pal’s Attacker computes Protocol A1* = Jc ·P …………………………..……..(1) H(Bi)*·P = A1* – A2 In this phase, we describe the weaknesses of A4* = H(Bi)*·P – A5 = Jsc·P …………....……(2) Ali and Pal’s protocol. A7* = A1* – A8 = Js·P …………….…...….….(3) From (1), (2) and (3), the attacker has the information Jc ·P, Jsc·P, Js·P and he can easily 4.1. Session-Specific Temporary compute the session key, as Information Leakage Attack SK = h(Jc ·P || Jsc·P || Js·P) Figure 1. Session-Specific Temporary Ali and Pal’s protocol suffers from session-specific Information Leakage attack temporary information attack as the explanation follows. Suppose, if random number Jc is 4.2. Replay attack compromised by any attacker ℋ, then ℋ can harm the valid user. ℋ can compute easily other random numbers Jsc, Js by some mechanism. By using the Assuming that the login request message information about Jc·P, Jsc·P, and Js·P, ℋ can {HIDi, Hi, A2, A3} is eavesdropped by ℋ, compute SK = h(Jc·P || Jsc·P || Js·P). It is a very which was sent by a legal user to the legal serious flaw in their protocol. server. After some time, ℋ transmits the same Suppose temporary random number Jc is leaked login request message {HIDi, Hi, A2, A3} to the somehow, then ℋ can evaluate session key legal server. When the login request message is easily from the known temporary random received then the server cannot recognize the number in the following steps (also shown in freshness of the message and evaluates Fig.1). Dech(y)(HIDi) = [UIDi, J], Mi* = Hi – h(UIDi || Step 1: First, ℋ eavesdrops the login request y)·P, A1* = A2 – Mi*, A3* = h(UIDi || A1* || SIDj || message {HIDi, Hi, A2, A3} and also other Hi) and checks A3* =? A3. Obviously, the request messages {A5, A6, HIDinew, Xi}, equality will hold and the server accepts the {HIDinew, A9, A8, A5} at the time of login request of the ℋ. The freshness of the authentication and key agreement phase. login request message is not check by the server Step 2: After this ℋ computes A1 = Jc·P and in Ali and Pal’s protocol. Therefore, Ali and H(Bi)*·P = A1 – A2. A2 is taken from Pal’s protocol is suffering from replay attack. eavesdropped message {HIDi, Hi, A2, A3}. Step 3: ℋ also uses eavesdropped message {A5, 5. The Proposed Protocol A6, HIDinew, Xi} to get A5, which is sent by registration center to the server. Now ℋ Our proposed protocol includes six phases: evaluates A4* = H(Bi)*·P – A5 = Jsc·P. Here, Jsc initialization phase, server enrollment phase, is a random number, chosen by RC. user enrollment phase, login phase, Step 4: Now ℋ wants to compute Js. A8 is authentication and key agreement phase and retrieved from eavesdropped message {HIDinew, password change phase. A9, A8, A5}, which is transmitted by the server 161 5.1. Initialization Phase A2, A3, T1} to RC through open channel as shown in Figure 4. To boot up the system, RC selects a generator P of elliptic curve and chooses a Uj RC secret key y as the system parameter. Select UIDi and imprint Bi {UIDi, H(Bi)} 5.2. Server Enrollment Phase Choose J HIDi = Ench(x) (UIDi || J) In this phase, the server enrolls itself at the Mi = H(Bi)·P registration center RC. The server selects its Ei = h(UIDi || y)·P own identity SIDj and transmits the message Hi = Mi + Ei {SIDj} to RC through open channel. When SIDj Insert is picked up from the server then RC evaluates {Hi, HIDi, P, Ek/Dk, h(·), H(·)} AH = h(SIDj || y) and RC transmits the message into SC {AH} to the server through open channel as {SC} shown in Figure 2. Zi = h(UIDi || PWi || H(Bi)) Sj RC Insert into Zi into SC Select SIDj Figure 2. User Enrollment Phase of the {SIDj} proposed protocol Compute MK = h(SIDj || y) {MK} Uj RC Insert SC Figure 2. Server Enrollment Phase of the Enter UIDi*, PWj* and imprint Bi* proposed protocol Calculate Zi* = h(UIDi*||PWi*||H(Bi*)) Check Zi* =? Zi. 5.3. User Enrollment Phase Choose Jc Compute A1 = Jc·P A2 = H(B1)·P + A1 First, user selects his/her identity UIDi, A3 = h(UIDi || A1 || SIDj || Hi) imprints Bi and transmits the message {UIDi, {HIDi, Hi, A2, A3, T1} H(Bi)} to RC through open channel. When the request message is received from the user then Figure 4. Login Phase of the proposed protocol RC selects a random number J and evaluates HIDi = Ench(x) (UIDi || J), Mi = H(Bi)·P, Ei = h(UIDi || y)·P, Hi = Mi + Ei. Now, RC inserts all 5.5. Authentication and Key information {Hi, HIDi, P, Ek/Dk, h(·), H(·)} into Agreement Phase SC and transmits {SC} to the user. After receiving {SC} from RC, user evaluates Zi = After receiving the login request message h(UIDi || PWi || H(Bi)) and inserts Zi into SC as {HIDi, Hi, A2, A3, T1} from the user, RC checks shown in Figure 3. T2 – T1 ≤ ∆T and evaluates Dech(x)(HIDi) = [UIDi, J], Mi* = Hi – h(UIDi || y)·P, A1* = A2 – 5.4. Login Phase Mi*, A3* = h(UIDi || A1* || SIDj || Hi) and checks A3* =? A3. If the equality does not hold then the User embeds SC into the card reader and enters connection is stopped by RC. Otherwise, RC UIDj*, PWi* and imprints Bi*. Now SC evaluates chooses Js and evaluates HIDinew = Ench(x)(UIDi Zi* = h(UIDi*||PWi*||H(Bi*)) and checks Zi* =? Zi. || Jsc), Xi = Ench(SIDj||y)[UIDj || A1 || H(Bi)], A4 = If the equality does not hold then the connection Jsc·P, A5 = A4 + H(Bi) ·P, A6 = h(A4 || HIDinew || is stopped. Otherwise, user chooses a random SIDj). RC transmits the message {A5, A6, number Jc and evaluates A1 = Jc·P, A2 = H(B1)·P HIDinew, Xi, T2} to the server through open + A1, A3 = h(UIDi || A1 || SIDj || Hi). Now, user channel. transmits the login request message {HIDi, Hi, When the message {A5, A6, HIDinew, Xi, T2} is picked up from RC then server checks T3 – T2 ≤ 162 ∆T and evaluates Dech(SIDj||y)(Xi) = [UIDi || A1 || Suppose the temporary arbitrary number Jc H(Bi)], A4* = A5 – H(Bi)·P, A6* = h(A4* || HIDinew is leaked by the server to the attacker ℋ then ℋ || UIDi || SIDj) and checks A6* =? A6. If the will try to evaluate session key from the known equality does not hold then the connection is temporary random number in the following stopped by the server. Otherwise, server manner. First, ℋ computes A1* = Jc•P, chooses Js and evaluates A7 = Js·P, A8 = A7 + A1, H(Bi)*•P = A1* – A2, A4* = H(Bi)*•P – A5 = A9 = h(HIDinew || A7 || A4 || H(Bi)·P). Now, server Jsc•P and A7* = A1* – A8 = Js•P. After evaluating transmits the message {HIDinew, A9, A8, A5, T3} the all temporary random numbers Jsc and Js to the user. from Jc, But the session key SK = h(Jc•P || Jsc•P After receiving the message {HIDinew, A9, A8, || Js•P || UIDj) could not calculate by ℋ without A5, T3} from the server, user checks T4 – T3 ≤ knowing UIDj. Therefore, our proposed ∆T and evaluates A7* = A8 – A1, A4* = A5 – protocol prevents session- specific temporary H(Bi)·P, A9* = h(HIDinew || A7* || A4* || H(Bi)·P) information attack. and checks A9* =? A9. If the equality does not hold then the connection is stopped by the user. Uj RC Sj Otherwise, user evaluates SK = h(Jc·P || Jsc·P || Check T2 – T1 ≤ ∆T Js·P || UIDi), Ni = SK·P + h(UIDi || H(Bi))·P. Evaluate Dech(x)(HIDi) = [UIDi, J] Now, user transmits the message {Ni, T4} to the Mi* = Hi – h(UIDi || y)·P server through open channel. Note that the user A1* = A2 – Mi* replaces HIDinew with HIDi into SC to avoid user A3* = h(UIDi || A1* || SIDj || Hi) untraceability attack. Check A3* =? A3. Choose Js and Evaluate After receiving the message {Ni, T4} from the HIDinew = Ench(x)(UIDi || Jsc) user, server checks T5 – T4 ≤ ∆T and evaluates Xi = Ench(SIDj||y)[UIDi || A1 || H(Bi)] SK* = h(Jc·P || Jsc·P || Js·P || UIDi), Ni* = SK*·P A4 = Jsc·P, A5 = A4 + H(Bi) ·P + h(UIDi || H(Bi)·P). After that, the server A6 = h(A4 || HIDinew || SIDj) checks Ni* =? Ni. If the equality does not hold {A5, A6, HIDinew, Xi, T2} then the connection is stopped by the server. Otherwise, the connection is established Check T3 – T2 ≤ ∆T between the user and the server as shown in Evaluate Figure 5. Dech(SIDj||y)(Xi) = [UIDi || A1 || H(Bi)] A4* = A5 – H(Bi)·P A6* = h(A4* || HIDinew || UIDi || SIDj) 5.6. Password Change Phase Check A6* =? A6 Choose Js and Evaluate A7 = Js·P A8 = A 7 + A1 User can modify his/her password easily A9 = h(HIDinew || A7 || A4 || H(Bi)·P) without interacting with the server. First, user injects his/her smartcard into a card reader and {HIDinew, A9, A8, A5, T3} chooses UIDi*, PWi* and also imprints Bi*. Now, Check T4 – T3 ≤ ∆T the card reader evaluates Vi* = h(UIDi* || PWi* || Evaluate A7* = A8 – A1 H(Bi*)) and verifies Vi* =? Vi. If it is not A4* = A5 – H(Bi)·P satisfied, then the connection is ended. A9* = h(HIDinew || A7* || A4* || H(Bi)·P) Otherwise, user selects a new Password PWinew Check A9* =? A9. Evaluate and evaluates Vinew = h(UIDi || PWinew || H(Bi*)). SK = h(Jc·P || Jsc·P || Js·P || UIDi) Finally, it displaces Vi with Vinew in the memory Ni = SK·P + h(UIDi || H(Bi)·P) of the smartcard. changes HIDinew with HIDi into SC {Ni, T4} 6. Security Analysis Check T5 – T4 ≤ ∆T Evaluate 6.1. Prevents Session-Specific SK* = h(Jc·P || Jsc·P || Js·P || UIDi) Ni* = SK*·P + h(UIDi || H(Bi)·P) Temporary Information Leakage Check Ni* =? Ni attack Figure 5. Authentication and Key Agreement Phase 163 6.2. Replay attack Table 2 Comparison of Computation Cost Ali and Pal [4] Our protocol Assume that the previous login request Computation cost of 4TH + 2TPM + 3TH + 2TPM + registration phase 1TS 1TS message {HIDi, Hi, A2, A3, T1} is eavesdropped Computation cost of 13TH + 9TPM + 12TH + 9TPM by an adversary, which was sent by a legal user login and 4TS + 4TS to the legal server. After some time, ℋ authentication phase transmits the same login request message Total computation 17TH + 11TPM + 15TH + 11TPM {HIDi, Hi, A2, A3, T1} to the legal server. When cost 5TS + 5TS the login request message is received by the server then the server checks the freshness of Table 3: Comparison of Security Features the timestamp and stops the connection if T1 is Attacks Ali and Pal Our protocol not fresh. Therefore, our proposed protocol [4] Prevents session ˟ ✓ prevents the replay attack. specific temporary information leakage attack 7. Security and Performance Prevents replay ˟ ✓ attack Comparison This section describes the performance and security comparison, along with other related 8. Conclusion protocols [1]. Some notations are defined as TH indicates one way hash function, TPM means scalar In this paper, we have investigated Ali and point multiplication and TS indicates symmetric Pal’s protocol. We have revealed that their decryption/encryption functions, as shown in Table protocol is suffering from replay attack and 2. session-specific temporary information leakage Table 2 shows the computation cost attack. To reduce these vulnerabilities, we have comparison of the proposed protocol with the proposed an improved protocol. We have used protocols in [1]. Ali and Pal’s protocol needs to timestamps in our proposed protocol to prevent perform total 17 hash functions, 11 scalar replay attack. Our proposed protocol is more multiplication operations and 5 symmetric robust than Pal and Ali’s scheme, and there is encryption/decryption functions i.e., 17TH + no extra computation needed in our scheme. We 11TPM + 5TS. On the other hand, our proposed will propose a lightweight scheme for multi- protocol needs to perform 15 hash functions, 11 server environment with low computation cost scalar multiplication operations and 5 and better security in future work. symmetric encryption/decryption functions, i.e., 15TH + 11TPM + 5TS. According to Table 2, our proposed protocol’s computation overhead, 9. Acknowledgements and Ali and Pal’s protocol are identical. The only change is the reduction of 2 hash functions The first author gratefully acknowledges the in our proposed protocol. Nevertheless, our financial support received from CSIR (India) in protocol is secure against the attacks to which the form of Junior Research Fellowship CSIR Ali and Pal’s protocol is not resistant. award no. 09/113(0020)/2018-EMR-I. Table 3 compares the proposed protocol's security features with the protocols in [1]. As References shown in Table 3, our protocol gives security against replay attack and session-specific [1] R. Ali, A. K. Pal, An efficient three factor– temporary information leakage attack. Still, Ali based authentication scheme in multi- and Pal's protocol doesn't offer protection server environment using ECC, Int. J. against the above vulnerabilities. Therefore, our Commun. Syst. 31(4) (2017) 1-22. proposed protocol is more effective and secure than the protocol in [1].