Yang Junzuo,Wang Yongjian,Zhou Yuan

(National Computer Network Emergency Response Technical Team Coordination Center of China,Beijing,100029,P.R.China)

INTRODUCTION

Recently, the remote user authentication scheme using smart card has been deeply studied,and several schemes in this field have been proposed. Many pairing-based authentication schemes have also been designed.For example,Manik,et al proposed a novel remote user authentication scheme using bilinear pairings[1].However,one drawback of the scheme is that the smart card should contain a sensitive data of the card holder, which is generated from the password of the holder.

Basically,a password-based authentication scheme using smart card is called two-factor authentication.In the two-factor authentication setting,any one can impersonate to sever as authorized user if the smart card is lost and the password is revealed simultaneously. To strengthen the security, some researchers proposed three-factor authentication. For example,Goyal and Chahar proposed a novel password-based remote user authentication scheme using smart card with biometric[2].As three-factor authentication schemes are not convenient to be used in practice(three factors should be involved simultaneously), the password-based authentication using smart card is more common in the real applications.

In 2000,Hwang and Li proposed a new remote user authentication scheme,in which the remote system only kept a secret key x s for computing the user passwords and did not need to maintain password or verification tables for verifying legal user[3].However,Chan and Cheng pointed out that there was a weakness in the scheme[4].In 2003,to overcome this weakness,Shen, Lin and Hwang proposed a modified version and claimed that it was secure against Chan-Cheng’s attack[5].But Leung,et al showed that the weakness still existed in the Shen-Lin-Hwang’s scheme.And we can also find much recent work on authentication[6-9].

This paper points out that the homomorphic is the main insecure factor in the Shen-Lin-Hwang’s scheme,and proposes an improved version using one-way hash func tion.

Furthermore,based on the bilinear pairings,a new secure and efficient scheme is propsed.Both proposed schemes do not require that the smart card contains sensitive information(i.e.,some parameters generated from the password of the card holder).In fact,all the data stored in the card are public parameters.

1 REVIEW OF SHEN-LIN-HWANG’SSCHEME

In Ref.[5],Shen,Lin and Hwang used the concept of hiding identity and proposed an enhanced scheme to prevent from forgery attack[4]. The scheme involves the registration phase,the login phase and the authentication phase.In the registration phase,each user sends his identity to the system.After the user identity is affirmed,the system will issue a smart card,a″shadowed″identity and a password to him via a secure channel.When the user wants to access the remote system,he attaches his smart card to an input device,and keys in his ″shadowed″identity and a corresponding password. Then,the remote system will verify it in the authentication phase.

1.1 Registration phase

The system first prepares some system parameters as follows:

(1)p:A large prime number.

(2)x s:The secret key owned by the system.

(3)h(?):A public one-way hash function.

(4)RED(? ):A ″shadowed″identity of the device owned by the system.

Suppose that a new user Uiwants to register the system,he first submits his identity IDi to the system.After the identity IDi is identified,the system computes the″shadowed″identity SIDiand password PWi for Ui,that is

Herein,SIDi is the ″shadowed″identity,that is to say,a number as large as p,including the claimed identity IDi,half shorter than p,completed by a redundancy (the shadow)depending on IDi[10].Redundancy rules RED(or how constructing SIDi from IDi) are standardized[11].

At last,the system issues the smart card,which contains the public parameters(p,h(?))and(SIDi,PWi)to the user Ui through a secure channel.Note that the data stored in the smart card,i.e.,(p,h(?)),is the same for all users.

1.2 Login phase

User Ui attaches his smart card to the login device and keys in his SIDi and PWi.Then,the smart card performs as follows:

(1)Generate a random number r∈Z*p.

(2)Compute C1=SIDrimod p.

(3)Pick up the current date and time T of the login device,and compute t=h(T⊕PWi)mod(p-1).

(4)Compute M=SIDtimod p.

(5)Compute C2=M(PWi)rmod p.

(6)Send a message C=(C1,C2,T,SIDi)to the remote system.

1.3 Authentication phase

Suppose that the system receives the message C at T′,where T′is the current date and time of the system.

(1)Check the validity of″shadowed″identity SIDi,if the format is incorrect,the login request is rejected.

(2)Check the time interval between T and T′,if(T′-T)≥ΔT,where ΔT is the expected legal time interval for transmission delay,the system rejects the login request.

(3)Check C2(C1x s)-1mod p=(SIDi)h(T⊕PWi).If it does hold,the system accepts the login request.Otherwise,the request is rejected.

Note that in the third step,the system has the capability of checking the equation as it knows the secret key xs,the data C2,C1,SIDi,and the public hash function h,and can compute the password PWi=SIDixsmod p.

2 IMPROVED SHEN-LIN-HWANG’SSCHEME

Although the Shen-Lin-Hwang’s scheme uses the concept of hiding identity,yet it still suffers from the forgery attack.Therefore,this paper improves the Shen-Lin-Hwang’s scheme.

2.1 Leung’s attack

In Ref.[6],Leung,et al presented an attack on the Shen-Lin-Hwang’s scheme.The attack is similar to the Chan-Cheng’s attack[4].

As an enhanced version of the Hwang-Li’s scheme,the Shen-Lin-Hwang’s scheme also does not keep any user or password table in the remote system.Therefore,an evil user can login to the remote system successfully if he gets a valid pair(SID v,PW v).

In the Leung’s attack,there is a legitimate user Ui,who with a valid pair(SIDi,PWi)can impersonate other legal users by the following tricks

where r is the random number chosen by the user Ui.Obviously(SID v,PW v)is a valid pair.As a result,the Shen-Lin-Hwang’s scheme can be forged.

Further studying the Shen-Lin-Hwang’s scheme, this paper finds that there is a homomorphic property in the scheme.Therefore,a slight change is made to improve the scheme.

2.2 Improved scheme

The improved scheme is composed of three phases:the registration phase,the login phase and the authentication phase.

2.2.1 Registration phase

The system first prepares the following system parameters:p,x s,h(?)are same with those in the Shen-Lin-Hwang’s scheme,and f(?)is a public one-way hash function.

When a new user Ui submits his identity IDi to the system for registration,the system first checks its validity and then computes the password PWi as

Then, the system stores the public parameters(p,h(? ),f(? ))to a smart card.

Finally,the system issues the smart card and PWi to the user Ui through a secure channel.

2.2.2 Login phase

User Ui attaches his smart card to the login device and keys in his IDi and PWi.Then,the smart card performs as follows:

(1)Generate a random number r∈Z*p.

(2)Compute C1=f(IDi)rmod p.

(3)Pick up T,and compute t=h(T⊕PWi)mod(p-1).

(4)Compute M=f(IDi)tmod p.

(5)Compute C2=M(PWi)rmod p.

(6)Send a message C=(C1,C2,T,IDi)to the remote system.

2.2.3 Authentication phase

Suppose that the remote system receives the message C at T′.

(1)Check the validity of identity IDi,if the format is incorrect,the login request is rejected.

(2)Check the time interval between T and T′,if(T′-T)≥ΔT,the system rejects the login request.

(3)Check C2 (C1x s)-1mod p =(f(IDi))h(T⊕PWi). If it does hold, the system accepts the login request.Otherwise,the request is rejected.

2.3 Security analysis

Generally,the adversaries are classified into two types:static and adaptive.An adversary is static if it can just eavesdrop over the channel,and adaptive if it can modify,delete,and insert the messages on the public channel.Hereafter,this paper focus on adaptiv e adversary for security analysis as it is more powerful than static one.It is proved that the improved scheme is secure even if the smart card is lost.Namely,any one who gets the user’s smart card,cannot impersonate the valid user to log into the system.

Theorem 1 The improved scheme is secure against adaptive adversary under card-compromise attack.

Proof If the smart card is compromised,the last protection for the user is the password PWi. Without PWi, the adversary cannot generate a valid C2that can pass the verification equation of Step(3)in the authentication phase.Moreover,a used valid C=(C1,C2,T,IDi)generated by the user cannot be used later as a time stamp is used in generating the message C.

From a valid transcript of the login phase,the adversary cannot mount off-line dictionary attack because he does not know the secret key x s

of the server and thus cannot check the verification equation.

Therefore,the login phase does not leak any information for PWi,and the scheme is secure against adaptive adversary under card-compromise attack.

Theorem 2 The improved scheme is secure against the Chan-Cheng’s attack[4]and the Leung’s attack[6].

Proof The improved scheme is similar to the Shen-Lin-Hwang’s scheme,and the main difference is f(?).Just as this,it eliminates homomorphic property.Therefore,the improved scheme can withstand the Chan-Cheng’s attack[4]and the Leung’s attack[6].

Suppose that a legitimate user Ui with a valid pair(IDi,PWi)can use the Chan-Cheng’s attack or the Leung’s attack to impersonate other legal users.For instance,he can obtain another valid pair(IDv,PWv)from the following equation

But the equation contradicts the fact that f(?)is a public one-way function.Therefore,he can not obtain ID v from f(ID v),thus the improved scheme is a secure one.

3 NEW SCHEME BASED ON BILINEAR PAIRINGS

Although the improved scheme can withstand the forgery attack,yet it still requires high computation cost in smart card device.Therefore,based on bilinear pairings,this paper presents a new secure and efficient scheme.

3.1 Bilinear pairings

Let G1 be a cyclic additive group and G2 a cyclic multiplicative group of the same prime order q. Assume that the discrete logarithm problems in both G1 and G2 are hard.A bilinear pairing is a map e:G1× G1→ G2,which satisfies the following properties:

(1)Bilinearity:For any P,Q∈ G1 and a,b∈,we have e(aP,bQ)=e(P,Q)ab.

(2)Non-degeneration:There exist P∈G1 and Q∈ G1,such that e(P,Q)≠ 1.

(3)Computability:Given P,Q∈G1,there is an efficient algorithm to compute e(P,Q)∈G2.

Such a bilinear pairing may be realized using the modified Weil pairing and Tate pairing associated with supersingular elliptic curve.And a more comprehensive description can be seen in Refs.[11-14].

3.2 New scheme

The new scheme also involves the registration phase, the login phase and the authentication phase.

3.2.1 Registration phase

The system prepares the following system parameters:

(1)q:A large prime number.

(2)G1:A cyclic additive group of order q.(3)G2: A cyclic multiplicative group of the same order q.

(4)P:A specific point in G1.

(5)e:G1× G1→ G2.

(6)x s:The secret key owned by the system.

(7)H:{0,1}*→G1:A secure one-way hash function.

When a new user Ui submits his identity IDi to the system for registration,the system first checks its validity and then computes the password PWi as follows

Then, the system stores the public parameters(q,G1,P)to a smart card.

Finally,the syste miss ues the smart card and PWi to the user Ui through a secure channel.

3.2.2 Login phase

User Uiattaches his smart card to the login device and keys in his IDi and PWi.Then,the smart card performs as follows:

(1)Generate a random number r∈Z*q.

(2)Compute C1=r?P.

(3)Pick up T.

(5)Send a message C=(C1,C2,T,IDi)to the remote system.

3.2.3 Authentication phase

Suppose that the remote system receives the message C at T′.

(1)Check the validity of identity IDi,if the format of IDiis incorrect,the login request is rejected.

(2)Check the time interval between T and T′,if(T′-T)≥ΔT,the system rejects the login request.

(3)Check e(T? P+ C1,C2)=e(P,x s?H(IDi)).If it holds,the system accepts the login request.Otherwise,the request is rejected.This is correct since that

3.3 Security analysis

Theorem 3 Any attacker cannot reveal the master key x s of the system.

Proof The security of the scheme is based on the one-way hash function and the hardness of discrete logarithm problem.

Any legal user Ui cannot derive the system secret x s from his password PWi.If he can,the discrete logarithm problem can be solved.

Theorem 4 New pairing-based scheme is secure against adaptive adversary under card-compromise attack.

Proof If the smart card is compromised,the last protection for the user is the password PWi.Without the knowledge of the password PWi=x s? H(IDi), the adversary cannot generate a valid C2that can pass the verification equation e(T? P+C1,C2)=e(P,x s? H(IDi))according to the property of the bilinear pairing.

Moreover,a used valid C=(C1,C2,T,IDi)generated by the user cannot be used later as a time stamp is used in generating the message C2.

From a valid transcript of the login phase,where C2 is the only data containing the password information,the adversary cannot mount off-line dictionary attack because he does not know the secret key x s of the server and thus cannot check the verification equation.

Therefore,the login phase does not leak any information for PWi,and the scheme is secure against adaptive adversary under cardcompromise attack.

Theorem 5 New pairing-based scheme is secure against the eavesdropper.

Proof Any attacker cannot forge another valid message C′={C′1,C′2,T′,IDi}from C=(C1,C2,T,IDi),where T′≠ T,C′1=r? P andIf he can,then from the factC2,he must know r,which contradicts the assumption that the discrete logarithm problem is hard.

Theorem 6 New pairing-based scheme is secure against the Chan-Cheng’s attack[4]and the Leung’s attack[6].

Proof Since it adopts the one-way hash function H on IDi,it also can withstand the Chan-Cheng’s attack[4]and the Leung’s attack[6].

3.4 Efficiency analysis

As the smart card is lower-powered and resource-constrained device,we should keep the computation cost down on user part.

Fortunately,in the new scheme,the most time-consuming pairing evaluation is not used on the user part,while only one inversion modulo q and two multiplication evaluations in G1 are required.Therefore,the efficiency requirements are satisfied.

4 CONCLUSION

This paper first reviews the Shen-Lin-Hwang’s modified remote user authentication scheme,and points out the homomorphic is the main insecure factor. Then,a corresponding improved version is proposed,which eliminates the homomorphic. And,a new secure and efficient scheme based on the bilinear pairings is proposed.Since both schemes use one-way hash function on user identity IDi,they can prevent from the Chan-Cheng’s attack and the Leung’s attack.

[1] Das M L,Saxena A,Gulati V P,et al.A novel remote user authentication scheme using bilinear pairings[J].Computers and Security,2006,25(3):184-189.

[2] Goyal K K,Chahar M S.A novel remote user authentication scheme using smart card with biometric based on ECDLP[J].International Journal of Information Technology and Knowledge Management,2011,4(2):649-651.

[3] Hwang M S,Li L H. A new remote user authentication scheme using smart cards[J].IEEE Trans Consumer Electron,2000,46(1):28-30.

[4] Chan C K,Cheng L M.Cryptanalysis of a remote user authentication scheme using smart cards[J].IEEE Trans Consumer Electron,2000,46(4):992-993.

[5] Shen J J,Lin CW,Hwang M S.A modified remote user authentication scheme using smart cards[J].IEEE Trans Consumer Electron,2003,49(2):414-416.

[6] Leung Kai-Chi,Cheng L M,Fong A S,et al.Cryptanalysis of a modified remote user authentication scheme using smart cards[J].IEEE Trans Consumer Electron,2003,49(4):1243-1245.

[7] Li C,Lee C.A novel user authentication and privacy preserving scheme with smart cards for wireless communications[J].Mathematical and Computer Modelling,2012,55(1/2):35-44.

[8] Tsaur W,Li J,Lee W.An efficient and secure multi-server authentication scheme with key agreement[J].Journal of Systems and Software,2012,85(4):876-882.

[9] Li Xiong,Xiong Yongping,Ma Jian,et al.An efficient and security dynamic identity based authentication protocol for multi-server architecture using smart cards[J].Journal of Network and Computer Applications,2012,35(2):763-769.

[10]Guillou L,Quisquater J.Efficient digital public-key signatures with shadow [J]. Advanced in Cryptology-Crypto,1987:223.

[11]Working group on JTC1/SC20/WG2. Digital signature scheme with shadow[S].ISO-DP 9796,1990.

[12]Boneh D,Franklin M.Identity-based encryption from the Weil pairing[J].Advances in Cryptology-Crypto 2001,Lecture Notes in Computer Science,2001:213-229.

[13]Camenisch J,Haralam biev K,Kohlw elss M,et al.Structure preserving CCA secure encryption and applications[J].Lecture Notes in Computer Science,2011,7073:89-106.

[14]Schage S.Tight proofs for signature schemes without random oracles[J].Lecture Notes in Computer Science,2011,6632:189-206.