JIH-MSP-2013-03-005
Journal of Information Hiding and Multimedia Signal Processing?2013ISSN2073-4212 Ubiquitous International Volume4,Number3,July2013
Security Analysis of a new Ultra-lightweight RFID Protocol and Its Improvement
Xu Zhuang1,Zhi-Hui Wang2,Chin-Chen Chang3,4,Yan Zhu5
1School of Information Science and Technology
Southwest Jiaotong University
Chengdu,Sichuan,China
2School of Software
Dalian University of Technology
Dalian,Liaoning,China
Economy and Technology Development Area
Dalian,China,116620
wangzhihui1017@https://www.sodocs.net/doc/2f3999646.html,
+86-411-87571636
3Department of Information Engineering and Computer Science
Feng Chia University
Taichung City40724,Taiwan
4Department of Computer Science and Information Engineering
Asia University
Taichung41354,Taiwan
5School of Information Science and Technology
Southwest Jiaotong University
Chengdu,Sichuan,China
Received January,2013;revised March,2013
Abstract.Retrieval of texture images,especially those with di?erent orientation and
scale changes,is a challenging and important problem in image analysis.This paper
adopts spiking cortical model(SCM)to explore geometrical invariant texture retrieval
schemes based on Discrete Cosine Transform(DCT)coe?cients of pulse images.The
series of pulse images,outputs of SCM,have a robust talent for extracting edge,segment
and texture which are inherent in the original images,but they are large2-dimensional
image data so that it is di?cult tSome ultra-lightweight RFID protocols have recently
been developed.Unlike other RFID protocols,ultra-lightweight protocols generally only
need the simplest bitwise operations in the tag side,such as XOR,AND,and OR.In
2012,Tian etal.proposed a new ultra-lightweight RFID protocol named RAPP(RFID
authentication protocol with permutation)using a new bitwise operation P ermutation
in the protocol,which can achieve high security and privacy as claimed.Unfortunately,
because of the incomplete session that might occur in RAPP,we present a replay attack
which can lead to de-synchronization between a tag and the database,which means the
tag can no longer be authenticated by any reader.In addition,we also present a simple
de-synchronization attack that can break the synchronization state between a tag and
the database,like the replay attack.Some potential threats resulting in more security
concerns from RAPP are illustrated by using two properties of P ermutation revealed
in this paper.We also provide some countermeasures for RAPP to withstand attacks
mentioned in the paper.
Keywords:RFID;ultra-lightweight;security analysis;permutation;RAPP.
166
Security Analysis of a new Ultra-lightweight RFID Protocol and Its Improvement167 1.Introduction.Radio Frequency Identi?cation(RFID)systems use radio signals to identify a special target(called a tag).RFID systems usually have the ability to write and read the data in the target.Due to the low computation cost and ease of implementation, RFID systems have been widely used in many applications,such as access control systems, e-passports,and food security.However,security and privacy issues are two serious obstacles for the development of RFID.Security problems refer to whether an RFID system has the ability to withstand various attacks,such as DoS attacks,replay attacks, and de-synchronization attacks.Privacy problems are more special in RFID systems as the tag is attached to a certain product or its owner.For each authentication,the tag uses its identi?er for the authentication process.Thus,a malicious attacker can use this information to track a certain tag or reveal its locations privacy information.To deal with these problems,many researchers have proposed authentication protocols in order to achieve high performance in both security and privacy.However,many of these protocols do not consider the computation cost from the tag side;thus,although they can guarantee the security and privacy in their protocols,due to the high computation cost on the tag side,they are not applicable.Chien[3]classi?ed the RFID protocols into four groups:full-?edged,simple,lightweight,and ultra-lightweight.Unlike the other three groups of RFID protocols,which generally require a random number generator and some functions like the one-way hashing function and Cyclic Redundancy Code(CRC)on the tag side,ultra-lightweight RFID systems only need the simplest bitwise operations in the tag side,such as XOR,AND,and OR.In this paper,we focus on the ultra-lightweight group,which requires the lowest computation cost on the tag side.
Lopez etal.[4-6]proposed a series of ultra-lightweight RFID protocols called LMAP, M2AP,and EMAP in2006.All three protocols are designed to guarantee data con?-dentiality and data integrity of the protocol as well as prevent the RFID systems from various kinds of attacks,such as man-in-the-middle and replay attacks.However,Li and Wang[10]pointed out that the LMAP and M2AP are vulnerable to de-synchronization and full disclosure attacks[10].Later,as reported in[11],EMAP was also found to be vulnerable to de-synchronization and full disclosure attacks.In2007,Chien[3]pro-posed an ultra-lightweight protocol called SASI,which provides strong authentication and strong data integrity.Unfortunately,SASI is vulnerable to traceability,replay,and DoS attacks,as reported in[2,7,9].In2012,Tian etal.[12]proposed a new ultra-lightweight RFID protocol named RAPP,which uses a new bitwise operation called P ermutation in the protocol;the authors claimed that this protocol had the ability to withstand vari-ous attacks and provide strong data con?dentiality and integrity.However,utilizing the property of the invariance of Hamming weight of P ermutation,Avoine and Carpent[1] presented a traceability attack for it.More seriously,Wang etal.[8]proposed a way to fully compromise the secrets of a tag in RAPP,although their method is not e?cient as it requires about230times for an attacker to communicate with the target tag.In[13], Ahmadian etal.found an e?cient way to lead a de-synchronization attack on RAPP.
In this paper,we reveal a new replay attack that can break the synchronization between a tag and the database.Thus,the tag might fall into a DoS state in which the tag can no longer be authenticated by any reader.In addition,we explore the property found in[13] and give another simple de-synchronization attack.We then show some potential threats that can lead to some other security concerns in RAPP.The rest of the paper is organized as follows:Section2presents the notations used in this paper and an overview of RAPP protocol.Section3shows a replay attack and a de-synchronization attack that may cause a tag to fall into the DoS state.Some countermeasures to withstand our attacks are given in Section4,and the conclusions are summarized in Section5.
168X.Zhuang,Z.H.Wang,C.C.Chang,and Y.Zhu
2.Overview of RAPP.RAPP includes three parties:the readers,the tags,and a back-end database.Generally,we assume the channel between a reader and the back-end database to be secure while an attacker can steal all the messages transmitted between the reader and a tag.All notations used in this paper are shown in Figure1.
Figure1.Notations used in the paper
https://www.sodocs.net/doc/2f3999646.html,putations and updating of RAPP
Security Analysis of a new Ultra-lightweight RFID Protocol and Its Improvement 169
The bitwise operation Permutation is de?ned as follows [12]:
De?nition A and B are two n -bit binary strings,where A =a 1a 2...a n ,a i ∈{0,1},i =1,2,...,n ,B =b 1b 2...b n ,b i ∈{0,1},i =1,2,...,n ,Assume wt (B )=m (0≤m ≤n ),and b k 1=b k 2=...=b k m =1,b k m +1=b k m +2=...=b k n =0,where 1≤k 1 P er (A,B )=a k 1a k 2...a k m a k n a k n ?1...a k m +2a k m +1. Figure 3helps clarify the de?nition. RAPP is based on the use of index-pseudonym (IDS ),which is an index of a table containing all the secrets of a tag.There are two main advantages to using IDS :1)The database can identify a tag by its IDS without any information of its unique identi?er;in addition,the updating of IDS achieves the goal of preventing the privacy leakage problem of a tag;and 2)after receiving the IDS of a tag,the database can check the legality of the IDS with computation complexity O (1)instead of O (n ).RAPP is quite an e?cient RFID protocol as it just uses the simple bitwise operations XOR and Hamming weight based Rotation and P ermutation on the tag https://www.sodocs.net/doc/2f3999646.html,plex operations such as a random number generator are only needed on the reader side. Figure 2presents all the computations in the RAPP protocol.Each step is described as follows: Step1:Reader sends a “Hello”message to a tag to initiate a new protocol run. Step2:After receiving the query message,the tag responds to the reader with its IDS .Step3:The reader checks whether the received IDS matches the database.If the IDS matches,the reader generates a random number n 1and then computes messages A and B based on which IDS is found in the database (IDS old orIDS new ).Then the reader transmits A and B to the tag.If the IDS is not matched,the reader ends this session.Step4:Upon receiving the messages,the tag extracts n 1from A and uses local secret keys to compute B ′and check whether the equation B =B ′is true or not.If it is true,the tag computes message C and sends it to reader.Otherwise,the tag terminates the protocol.Step5:The reader checks the received C with its secrets.If the reader accepts C ,it generates a random number n 2,messages D and E .Then the reader updates all its secrets and transmits D and E to the tag.Otherwise,the reader ends the session.Step6:The tag gets n 2from message D and checks E .If the tag accepts E ,it updates all its secrets;otherwise,it terminates the protocol. 3.Security analysis of RAPP protocol.In this section,we give a replay attack and a de-synchronization attack that can both cause a tag to fall into a denial-of-service (DoS)state.This means that the tag can no longer be authenticated as valid.In addition,we discuss some potential attacks that might cause more security concerns in RAPP.Before presenting our attacks,it is necessary to discuss some properties of the operation P ermutation . Property 1:For P er (X,Y ),the lsb of Y does not in?uence the output of P er (X,Y ).Property 2:For P er (X,Y )and P er (X,Y ′)where Y ′=Y ⊕[0]1,0,if [Y ]1=[Y ]0,which means wt (Y )>0,[P er (X,Y ′)]n ?wt (Y )=[P er (X,Y )]n ?wt (Y )?1and [P er (X,Y ′)]n ?wt (Y )?1= [P er (X,Y )]n ?wt (Y )· Property 1is obviously true,so we just provide the proof for Property 2. 170X.Zhuang,Z.H.Wang,C.C.Chang,and Y.Zhu Proof for Property 2: Because [Y ]1=[Y ]0,Y ′=Y ⊕[0]1,0,we have [Y ]1⊕1=[Y ]0⊕1,hence [Y ′]1=[Y ′]0,wt (Y )=wt (Y ′). If [Y ]1=0,we get [Y ]0=1,[Y ′]1=1,[Y ′]0=0and [P er (X,Y )]n ?wt (Y )=[X ]0, [P er (X,Y )]n ?wt (Y )?1=[X ]1 Therefore,[P er (X,Y ′)]n ?wt (Y )=[X ]1,[P er (X,Y ′)]n ?wt (Y )?1=[X ]0.So that,we con-clude that [P er (X,Y ′)]n ?wt (Y )=[P er (X,Y )]n ?wt (Y )?1and [P er (X,Y ′)]n ?wt (Y )?1= [P er (X,Y )]n ?wt (Y )√2 If [Y ]0=0,we get [Y ]1=1,[Y ′]0=1,[Y ′]1=0and [P er (X,Y )]n ?wt (Y )=[X ]1, [P er (X,Y )]n ?wt (Y )?1=[X ]0. Therefore,[P er (X,Y ′)]n ?wt (Y )=[X ]0,[P er (X,Y ′)]n ?wt (Y )?1=[X ]1.Hence,we conclued that [P er (X,Y ′)]n ?wt (Y )=[P er (X,Y )]n ?wt (Y )?1and [P er (X,Y ′)]n ?wt (Y )?1= [P er (X,Y )]n ?wt (Y ). Q.E.D As shown in Figure 3,we use the example in [12]to describe the Property 2. Y ′=Y ⊕[0]1,0,the results P er (X,Y )and P er (X,Y ′)show that the (n ?wt (Y ))th and (n ?wt (Y )?1)th bits of P er (X,Y )and P er (X,Y ′)are exchanged. Figure 3.Example of Property 2 Avoine and Carpent [12]presented a traceability attack to RAPP.This attack uti-lizes the property that Permutation is Hamming weight-invariant,which means that wt (P er (X,Y ))=wt (X ).Thus,it is possible for an attacker to trace a victim tag.Based on the traceability in RAPP,we next describe a replay attack,which can lead a tag to a DoS state. 3.1.Replay attack.In RAPP,the end messages are sent from the reader to the tag,and it is not easy to ensure data integrity between the reader and the tag because a reader cannot check whether the tag has updated its secrets or not.Because of the incomplete session and the traceability of RAPP,an attacker can ?rst steal some messages transmitted between a reader and a tag and then use these messages to impersonate a valid reader to initiate some new sessions,which can make the tag carry out its updating while the reader does not,thereby breaking the synchronization between the reader and the tag.Figure 4shows all the procedures of our replay attack.We assume that there are initialization states for a reader R and a tag T shown in the ?rst two boxes in Figure 4.Then,the ?rst protocol run between R and T begins.In the ?rst protocol run,an attacker notes down all the messages in the transition and intercepts the messages D 2 Security Analysis of a new Ultra-lightweight RFID Protocol and Its Improvement171 Figure4.Example of replay attack and E2in the last step,so that T would not update its secrets while R does.The?rst updating for T and R are shown in Figure4. In the second protocol run,the attacker also intercepts the last two messages transmit-ted in the last step,which causes R to update all its secrets again while T does not.The second updating shown in Figure4presents the results of the second protocol run.When T leaves the valid range of the reader,the attacker impersonates a valid reader to send T a hello message to initiate a new protocol run.The replay attack is described as follows: Step1:Attacker→Tag:Hello.The attacker sends a hello message to T to initiate a new protocol run. Step2:Tag→Attacker:IDS2.Upon receiving the query,T responds the attacker with its IDS2. Step3:Attacker→Tag:A2,B2.After receiving IDS2,the attacker sends the stolen messages A2and B2to T. 172X.Zhuang,Z.H.Wang,C.C.Chang,and Y.Zhu Step4:Tag→Attacker:C2.Since A2and B2are generated by a valid reader using secrets K12,K22,K32,and a random number n1,the tag can extract n1from A2and accept B2. So T will compute C2and send it to the attacker. Step5:Attacker→Tag:D2,E2.The attacker can ignore the received C2and then send T D2and E2.After receiving D2and E2,T updates all its secrets to IDS3,K13,K23, and K33. As previously discussed,after this replay attack,the secrets stored in T are di?erent from the secrets stored in the database,which causes T to fall into a DoS state.However, in this replay attack,the attacker needs to trace a target tag,which is possible in RAPP, as pointed out in[12]. 3.2.De-synchronization attack:Changing messages A,B and E.In[13],Ah- madian and Salmasizadeh revealed Property2shown in this paper using another version that does not contain the relationship between the Hamming weight of Y and the output of P er(X,Y⊕[0]1,0).Using this property,Ahmadian and Salmasizadeh[13]presented a simple but e?cient de-synchronization attack for RAPP by changing message D.We found that this attack can be also applied to change message A,which we will explore next. Figure5.The second attack Assume that a reader R1and a tag T1have the initialization state shown in Figure2and there is a successive protocol run between R1and T1without the last step in the protocol. Thus,an attacker can note down all the messages(IDS,A,B,C,D,E)transmitted between R1and T1but does not send D and E to T1in the last step.This would cause R1to update its secrets while T1does not.After the protocol is run,the state of R1is {IDS old=IDS,K1old=K1,K2old=K2,K3old=K3,IDS new=IDS?,K1new=K1?, K2new=K2?,K3new=K3?}and the state of T1is{IDS,K1,K2,K3}.After T1leaves the valid range of R1,an attacker can send a hello message to T1to impersonate a valid reader to initiate a new protocol run.Upon receiving the query,T1responds to it with its IDS.Then the attacker sends T1messages A′and B′.Note that the operation on A actually changes the corresponding bits of the random number n1generated by R1in Step3.If T1accepts B′,it would respond to the attacker with message C.As message C in RAPP is used to authenticate the tag by a reader,the attacker can ignore it and send messages D and E′to T1.If T1accepts E′,it will update its secrets by using a modi?ed n1.This would cause a de-synchronization between the T1and the database.Next,we analyze the success rate of this attack,as shown in Figure5. As evident,changing[A] i and[A] i?1 actually changes[n1]i and[n1]i?1.We use the notation n1′to represent the changed n1.If[n1]i and[n1]i?1are di?erent,[n1]i⊕1 and[n1]i?1⊕1are also di?erent.In such a case,wt(n1)=wt(n1′).Thus,there is a 1/2probability that wt(n1)=wt(n1′).If[n1]i and[n1]i?1are rotated to the least two signi?cant bits after Rot(n1,n1),the least two signi?cant bits between Rot(n1,n1)and Security Analysis of a new Ultra-lightweight RFID Protocol and Its Improvement 173 Rot (n 1′,n 1′)are di?erent.For i =1and [n 1]1=[n 1]0,since 1≤wt (n 1)≤n ?1,the probability that [n 1]1and [n 1]0are shifted to the least two signi?cant bits after Rot (n 1,n 1)is 0;for i =1,the probability that [n 1]i and [n 1]i ?1are shifted to the least two signi?cant bits after Rot (n 1,n 1)is 1/(n -1).Thus,in the case of [n 1]i =[n 1]i ?1,the probability that [n 1]i and [n 1]i ?1are shifted to the least two bits after Rot (n 1,n 1)is 1 n ×0+n ?1n ×1n ?1=1 n (1) As the lsb of Rot (n 1,n 1)and Rot (n 1′,n 1′)do not in?uence the output of P er (K 1⊕K 2,Rot (n 1,n 1))and P er (K 1⊕K 2,Rot (n 1′,n 1′)),utilizing Property 2,we can ?nd that the (n ?wt (n 1))th and (n ?wt (n 1)?1)th bits of P er (K 1⊕K 2,Rot (n 1′,n 1′))are exchanged compared with P er (K 1⊕K 2,Rot (n 1,n 1)).If [P er (K 1⊕K 2,Rot (n 1,n 1))]n ?wt (n 1)= [P er (K 1⊕K 2,Rot (n 1,n 1))]n ?wt (n 2)?1,which indicates that [K 1⊕K 2]0=[K 1⊕K 2]1(see the proof of Property 2),there is a 1/2probability that P er (K 1⊕K 2,Rot (n 1,n 1))is unchanged.As such,there is a 1/4n probability that P er (K 1⊕K 2,Rot (n 1,n 1))is un-changed.In such a case,two bits of P er (n 1,K 1)are changed,which would cause two bits of B ′to change compared with B ,but it is not easy to ?nd the positions of these two bits.For A ′,which causes P er (K 1⊕K 2,Rot (n 1,n 1))to remain unchanged,the attacker can randomly change two bits of B to check whether T 1would respond to message C or not.This would be successful at most C 2n times,where n is the length of a binary string used in the protocol.So,for each test of n 1′,the probability that T 1accepts B ′is 1/4n at most C 2n times.Once T 1responds to the attacker’s message C ,it indicates that T 1 accepts message B ′.An attacker must note down the A ′and B ′,which leads to responses from T 1(denoted as A ′s and B ′s ).Then,the attacker sends messages D and E ′to T 1.Since P er (K 3,Rot (n 2,n 2))is unchanged and there should be two bits of P er (n 1,K 3⊕K 2)that are changed,the attacker can test all possible E ′to check whether T 1has done its updating by sending T 1a new hello message and checking the IDS .If the attacker fails in the last step,s/he can repeat these steps using A ′s ,B ′s ,D ,and another E ′in the attack.Once an attacker has found A ′s and B ′s ,T 1would accept E ′at most C 2n times attacks.Based on this discussion,it is obvious that this attack must be successful if an attacker can ?nd the A ′s and B ′s when there are no other mechanisms to prevent the protocol. For each test of n 1′and B ′,the success rate of acceptance of B ′by T 1is 14n ×C 2n .Once an attacker has found A ′s and B ′s ,for each test of message E ′,the success rate of acceptance of E ′by T 1is 1C 2n .3.3.Potential threats.In addition to the two aforementioned attacks and the one presented in [13],an attacker can utilize some potential threats to attack RAPP.In this subsection,we reveal some potential insecure factors of RAPP. The attack shown in [13],which changes message D and tries to lead the tag to update its secrets with a modi?ed n 2,still works when K 30=K 31.In such a case,two bits of E are exchanged,and one can test it at most C 2n times.If one can ?nd the correct bits that are exchanged,referring to Property 2,s/he ?nds the Hamming weight of n 2.This theory is also applied to ?nd the Hamming weight of n 1,but it may cost more times as there is an interference P er (n 1,K 1)in message B .Yet as one can prevent the updating for a tag and there is a responding message C ,it is quite useful for an attacker to test the changed bits.Moreover,once an attacker has found the Hamming weight of n 1,it is possible for her/him to reveal some potential relationships between the changed n 1and secret K 1by controlling the Hamming weight of n 1and keeping K 1unchanged.All these potential insecure factors might threaten the security and privacy of RAPP. 174X.Zhuang,Z.H.Wang,C.C.Chang,and Y.Zhu 4.Patches for RAPP.The replay attack shown in Section3is based on the traceability of RAPP;thus,one can consider thatXif the RAPP can resist the traceability attackXour replay attack might not work in such a case.However,in real life,it is quite easy for an attacker to trace a tag in a very short time as a tag is usually attached to a certain product or its owner.Thus,we must?nd a more e?cient way to withstand this replay attack. In the RFID system,we cannot really generate a complete message indicating that both the reader side and the tag side are carrying out their updating.Therefore,there are only two choices for the protocols’designers:the end messages are transmitted from a reader to a tag or from a tag to a reader.In the mechanism used in RAPP,the end messages are transmitted from a reader to a tag,which is considered as to be more secure than from a tag to a reader.However,in such a case,the reader cannot know the state of the tag. To avoid potential attacks caused by the incomplete session,some auxiliary data can be stored on the reader side rather than the tag side. 4.1.Denial of the old IDS.The state information with a tag used in LMAP+[6]is useful in RAPP,but this method needs much more space to store the potential index-pseudonyms.Thus,we present a more e?cient way to resist the de-synchronization state caused by our replay attack. If a reader receives an old IDS from a tag,indicating that the tag did not get messages D and E in the last protocol run and,thus,the tag did not update its secrets,it is not applicable for a reader to accept the old IDS and then begin the protocol again as it might be a trap made by an attacker.A more secure way is to make the tag and reader synchronous as soon as possible rather than treat it as a normal protocol run.To achieve this goal,the reader needs to store the random numbers n1and n2generated in the last protocol’s execution.The reader then uses the numbers n1and n2to begin a new protocol run,meaning that the messages A,B,C,D,and E will be the same as the last protocol. Note that,the so-called new protocol run is not a genuine authentication process as the reader received an old IDS,as we said before,and the reader must reject it straight away.Indeed,the purpose of the new protocol run is to make the tag and the reader synchronized. Figure6.Example for the patch of denial of the old IDS For example,the states of R and T and all messages generated in last protocol run between them are shown in Figure6.In the next protocol,upon receiving the old IDS of T,using the same random number n1,R sends A1and B1to T,who will respond to R with C1.In a normal protocol,C is used to authenticate the tag by a reader;however,in such case,as the IDS of T received by R is the old one,R accepts C1but it does not o?er “service”for the tag T and then sends D1and E1to T.If D1and E1can be received by T in the new protocol run,then T will update its secrets to IDS2,K12,K22,and K32, and R does not need update its secrets as the random numbers used in the new protocol Security Analysis of a new Ultra-lightweight RFID Protocol and Its Improvement175 run are same as the last protocol.Therefore,after this protocol,the secrets between R and T are synchronous and T can be authenticated by any reader again. In this way,our replay attack is useless and will not lead to some other replay attacks. In RAPP,after the mutual authentication phase(the reader accepts message C1),the reader must update its secrets.An attacker can get all messages(IDS1,A1,B1,C1,D1, and E1)transmitted in the protocol,but as the IDS1is the old IDS stored in the reader after updating,all messages related to IDS1cannot cause a real authentication protocol but rather serve as a trigger to lead the reader to synchronize the tag.Due to the constant space cost2n,where n is the length of binary string used in the protocol,this scheme is more e?cient than the one using state information proposed in[6],which costs kn space, where k is the number of times that a tag remains in the uncertainty state. 4.2.Modi?cations of messages A and B.The main idea of the second attack and the attack described in[13]is to utilize the two properties of the operation P ermutation presented in Section3.In order to withstand these attacks,we must ensure that changing messages A and D will cause a chain changing all factors of messages B and E so that one cannot?nd out how many and which positions are changed for B and E.In our improvement scheme,messages B and E are modi?ed as: L is the length of messages used in protocols https://www.sodocs.net/doc/2f3999646.html,parisons among our work and others’ B=P er(K2⊕n1,Rot(n1,n1))⊕P er(n1,n1⊕K1),(2) E=P er(K3⊕n2,Rot(n2,n2))⊕P er(n1,n2⊕K2).(3) Now,we will analyze the security of these modi?cations.For the second attack,chang- ing[n1] i and[n1] i?1 would cause[K2⊕n1]i,[K2⊕n1]i?1,[n1⊕K1]i and[n1⊕K1]i?1 to be changed,where i≥0.Assuming that[n1] i and[n1] i?1 are di?erent and are shifted to the least two signi?cant bits after Rot(n1,n1),the least two signi?cant bits between Rot(n1,n1)and Rot(n′1,n′1)are di?erent,where n′ 1=n1⊕[0]i,i?1.However, for the modi?ed B,since[K2⊕n1]i and[K2⊕n1]i?1are also changed,the output of P er(K2⊕n1,Rot(n1,n1))must be uncertain.In addition,the output of P er(n1,n1⊕K1)) also becomes quite uncertain as not only n1and n1⊕K1would be changed,but also the Hamming weight of n1⊕K1will be uncertain.Thus,due to the modi?cation of message B in our improvement scheme,it is quite di?cult for an attacker to?nd out which po-sitions of message Bare changed after the changing of n1.This means that the attacker cannot easily produce a B′that can be accepted by the tag.This analysis is also applied to message E.Ultimately,the improved scheme can prevent the system from the two aforementioned attacks. 176X.Zhuang,Z.H.Wang,C.C.Chang,and Y.Zhu In Figure7,we present comparisons among our work and others’using the format made in[12]without considering the storage cost caused by storing extra information to prevent schemes from replay attack. 5.Conclusions.Security and privacy are the two most important issues for RFID sys-tems.For ultra-lightweight RFID protocol,it is quite necessary to minimize the cost for the tags as even the simplest bitwise operations can be performed in these tags due to the extremely limited resources.To reduce the overhead of a tag,some new bitwise opera-tions are used in ultra-lightweight protocols,such as Hamming weight-based Rotation and P ermutation.But the most serious drawback of these two operations is their invariant Hamming weight.Moreover,since most the existing ultra-lightweight RFID protocols do not o?er mechanisms to prevent the systems from replay attack except for storing the old messages in the tag or reader side,it is quite easy for an attacker to use some stolen messages to break the synchronization between a tag and the database. In this paper,we presented two attacks that can cause a tag to fall into the DoS state for a recently proposed ultra-lightweight RFID protocol RAPP,meaning that the tag can no longer be authenticated by any reader.The?rst attack utilizes the incomplete session in RAPP while the second one utilizes the two properties shown in this paper.Furthermore, we discussed some potential threats for RAPP by revealing the Hamming weight of the two random numbers used in the protocol.As we can see,the recently proposed RAPP is vulnerable to the de-synchronization and replay attacks presented in this paper.We also give some countermeasures for RAPP to withstand the attacks discussed in this paper. The idea of withstanding the replay attack is quite useful for many other schemes as it does not increase the computation cost in the tag.The modi?cation versions of messages B and E are guides for RFID protocols’designers to conceal relationships among all factors in a message.The security analysis demonstrated that our improved scheme is more secure than RAPP. REFERENCES [1]G.Avoine,and X.Carpent,Yet another ultralightweight authentication protocol that is broken, Proc.of the8th Workshop on RFID Security,2012. [2]H.N.Sun,W.C.Ting,and K.H.Wang,On the security of chien’s ultralightweight RFID au- thentication protocol,IEEE Trans.Dependable and Secure Computing,vol.8,no.2,pp.315-317, 2011. [3]H.Y.Chien,SASI:A new ultralightweight RFID authentication protocol providing strong authen- tication and strong integrity,IEEE Trans.Dependable and Secure Computing,vol.4,no.4,pp. 337-340,2007. [4]P.Peris-Lopez,J.C.Hernandez-Castro,J.M.Estevez-Tapiador,and A.Ribagorda,M2AP:a min- imalist mutual-muthentication protocol for low-cost RFID tags,Proc.of the3rd international con-ference on Ubiquitous Intelligence and Computing,pp.912-923,2006. [5]P.Peris-Lopez,J.C.Hernandez-Castro,J.M.Estevez-Tapiador,and A.Ribagorda,EMAP:An e?cient mutual authentication protocol for low-cost RFID tags,Proc.of the international conference on On the Move to Meaningful Internet Systems,pp.352-361,2006. [6]P.Peris-Lopez,J.C.Hernandez-Castro,J.M.E.Tapiador,and A.Ribagorda,LMAP:a real light- weight mutual authentication protocol for low-cost RFID tags,Proc.of the2nd Workshop on RFID Security,2006. [7]R.C.W.Phan,Cryptanlysis of a new ultralightweight RFID authentication protocol-SASI,IEEE Trans.Dependable and Secure Computing,vol.6,no.4,pp.316-320,2009. [8]S.H.Wang,Z.J.Han,S.J.Liu,and D.W.Chen,Security analysis of RAPP:an RFID au- thentication protocol based on Permutation,Cryptology ePrint Archive2012/327,available at https://www.sodocs.net/doc/2f3999646.html,/2012/327.pdf. [9]T.Cao,E.Bertino,and H.Lei,Security analysis of the SASI protocol,IEEE Trans.Dependable and Secure Computing,vol.6,no.1,pp.73-77,2009. Security Analysis of a new Ultra-lightweight RFID Protocol and Its Improvement177 [10]T.Li,and G.Wang,Security analysis of two ultra-lightweight RFID authentication protocols,IFIP Advances in Information and Communication Technology,springer,vol.232,pp.109-120,2007. [11]T.Li,and R.Deng,Vulnerability analysis of EMAP-an e?cient RFID mutual authentication proto- col,Proc.of the2nd International Conference on Availability,Reliability and Security,pp.238-245, 2007. [12]Y.Tian,G Chen,and J.Li,A new ultralightweight RFID authentication protocol with permutation, Journal of IEEE Communications Letters,vol.16,no.5,pp.702-705,2012. [13]Z.Ahmadian,M.Salmasizadeh,and M.R.Aref,Desynchronization attack on RAPP ultralightweight authentication protocol,Cryptology ePrint Archive2012/490,available at https://www.sodocs.net/doc/2f3999646.html,/2012/490.pdf.