each time the tag responds,as shown in Fig.5 Step 1(b).from TS where Time=ti".However,since there are many We see that the adversary simply knowing the entire Table V tags that respond at each time,all the adversary obtains is a set cannot determine whether two n values belong to the same of n values.The adversary cannot determine which n value user or not.The adversary can only determine which n values corresponds to his wi. belong to the same user after observing a user execute Query 1 Compromise RFID reader:An adversary controlling an multiple times.The reason is that the answer to Query 1 is the RFID reader will be able to read w,n from a tag (Step(2)in n value associated with a particular time.Since only a user Fig.5),and is assumed to know the location of the reader it has knows his own s values,successive Query 1 link the n values compromised.We allow the adversary to physically observe to the same user. a user transmitting a particular wi,ni once,in other words, Let us assume the adversary after some observation can being able to associate a user's identity to a wi.ni tuple.The determine that the times ti and ti,and the corresponding ni adversary succeeds if he is able to use this information to and nj belong to the same user.Now the adversary tries to determine additional information regarding that user. query LS to try and determine where this user has been.The One attack has the adversary trying to use wi,ni in querying table maintained by LS only contains a set of ws and their TS and LS.The adversary learns from querying TS.since he corresponding locations.There is no indication what time each already knows the time and n;values.Since the tag will use a w was obtained.The adversary cannot determine which w different n each time,the adversary cannot determine whether belongs to the user he is tracking because w =h(ID,n). other n values belong to the same user.Similarly,since the and that the adversary cannot link w=h(ID,ni)and n value is constantly changing,the adversary observing LS w=h(ID,nj)together without knowing the secret ID. cannot use wi to determine which ws belong to the same user. The property of separating time and location information Thus,no additional information can be obtained from I'S or into the TS and LS respectively defends against leaking LS from wi;ni. information in the more extreme instances where there are Another attack has the adversary after manually determining few users in the entire tracking system.Consider the tracking the identity associated with wi,ni,trying to determine if a system of an office building at night,and we have TS table, future wi,nj belongs to the same user.This is useful if the adversary controls the reader deployed outside an sensitive Time Random value 2:00am location like a clinic.Since the adversary cannot always be ni 2.2:15am physically present to determine a user's identity,this attack 几 allows the user to determine if the same user has visited Assuming there is no one else in the building,the adversary that location again in the future.However,since knowing the can infer that n;and n;belong to the same person.Now, ni and nj cannot be linked together because the ct value is the adversary can attempt to query LS to determine where incremented and hashed with a secret s known only the tag, that person has been.The adversary cannot determine any ws the resulting wi and wj cannot be linked together. from ni and nj,and can only issue a query "Select from Finally,we consider the scenario where the adversary LS where ID=*"to retrieve everything from LS to try and controls multiple RFID readers.Controlling multiple readers determine where this tag has been.Since LS does not store does not give the adversary any additional advantage,since time,the adversary cannot filter the LS data to narrow down a tag does not have to authenticate the RFID reader before possible locations the tag has been. transmission.The tag will always generate a different w,n Compromise LS server:Next we consider the adversary tuple to any reader that queries it. controlling the LS server.The adversary will now be able to access all the records such as those in Table VI,as well D.Protocol discussion as observe multiple queries (Query 2)made by a user and Our protocol uses the counter ct that automatically incre- the corresponding response.The adversary can also query the ments each time the tag is queried.This feature allows an TS using information from his observations.The goal of the adversary,using his own reader,to query the tag simply to adversary remains the same. increment the ct value.However,this behavior only degrades From controlling LS,the adversary knows the time and the user's performance,and does not help the adversary learn location associated with each w.Given that w=h(ID.n),anything about the user.A rational adversary will not launch RFID tags with different IDs will have different w values,and this type of attack. the same tag will also have different ws at different times since Our choice of w in the protocol is h(ID,n).Given an the n values will change due to n=h(s,ct),and the tag's ct adversary,a possible alternative is to set w as h(ID,t).This values increments each time it replies.Unlike controlling the will have the same properties as h(ID,n)since the time value TS,the adversary observing multiple Query 2 cannot assume t will only occur once and never repeat.Using h(ID,t)will they all belong to the same user and link the ws together.This also give better query performance,since the user can directly is because a user does not have to issue Query 2 more than determine the appropriate w and query the LS.instead of once to obtain an answer. doing a binary search on TS to determine n.The reason we do Let us assume that the adversary knows that wi is associated not use h(ID,t)is that different readers may have a slightly with time ti.The adversary can query TS doing"Select different clock skew.Thus,honest readers may issue the same t 58each time the tag responds, as shown in Fig. 5 Step 1(b). We see that the adversary simply knowing the entire Table V cannot determine whether two n values belong to the same user or not. The adversary can only determine which n values belong to the same user after observing a user execute Query 1 multiple times. The reason is that the answer to Query 1 is the n value associated with a particular time. Since only a user knows his own s values, successive Query 1 link the n values to the same user. Let us assume the adversary after some observation can determine that the times ti and tj , and the corresponding ni and nj belong to the same user. Now the adversary tries to query LS to try and determine where this user has been. The table maintained by LS only contains a set of ωs and their corresponding locations. There is no indication what time each ω was obtained. The adversary cannot determine which ω belongs to the user he is tracking because ω = h(ID, n), and that the adversary cannot link ω = h(ID, ni) and ω = h(ID, nj ) together without knowing the secret ID. The property of separating time and location information into the T S and LS respectively defends against leaking information in the more extreme instances where there are few users in the entire tracking system. Consider the tracking system of an office building at night, and we have T S table, Time Random value 1. 2:00 am ni 2. 2:15 am nj Assuming there is no one else in the building, the adversary can infer that ni and nj belong to the same person. Now, the adversary can attempt to query LS to determine where that person has been. The adversary cannot determine any ωs from ni and nj , and can only issue a query “Select * from LS where ID=*” to retrieve everything from LS to try and determine where this tag has been. Since LS does not store time, the adversary cannot filter the LS data to narrow down possible locations the tag has been. Compromise LS server: Next we consider the adversary controlling the LS server. The adversary will now be able to access all the records such as those in Table VI, as well as observe multiple queries (Query 2) made by a user and the corresponding response. The adversary can also query the T S using information from his observations. The goal of the adversary remains the same. From controlling LS, the adversary knows the time and location associated with each ω. Given that ω = h(ID, n), RFID tags with different IDs will have different ω values, and the same tag will also have different ωs at different times since the n values will change due to n = h(s, ct), and the tag’s ct values increments each time it replies. Unlike controlling the T S, the adversary observing multiple Query 2 cannot assume they all belong to the same user and link the ωs together. This is because a user does not have to issue Query 2 more than once to obtain an answer. Let us assume that the adversary knows that ωi is associated with time ti . The adversary can query T S doing “Select * from T S where Time=ti”. However, since there are many tags that respond at each time, all the adversary obtains is a set of n values. The adversary cannot determine which n value corresponds to his ωi . Compromise RFID reader: An adversary controlling an RFID reader will be able to read ω, n from a tag (Step (2) in Fig. 5), and is assumed to know the location of the reader it has compromised. We allow the adversary to physically observe a user transmitting a particular ωi , ni once, in other words, being able to associate a user’s identity to a ωi , ni tuple. The adversary succeeds if he is able to use this information to determine additional information regarding that user. One attack has the adversary trying to use ωi , ni in querying T S and LS. The adversary learns from querying T S, since he already knows the time and ni values. Since the tag will use a different n each time, the adversary cannot determine whether other n values belong to the same user. Similarly, since the n value is constantly changing, the adversary observing LS cannot use ωi to determine which ωs belong to the same user. Thus, no additional information can be obtained from T S or LS from ωi , ni . Another attack has the adversary after manually determining the identity associated with ωi , ni , trying to determine if a future ωj , nj belongs to the same user. This is useful if the adversary controls the reader deployed outside an sensitive location like a clinic. Since the adversary cannot always be physically present to determine a user’s identity, this attack allows the user to determine if the same user has visited that location again in the future. However, since knowing the ni and nj cannot be linked together because the ct value is incremented and hashed with a secret s known only the tag, the resulting ωi and ωj cannot be linked together. Finally, we consider the scenario where the adversary controls multiple RFID readers. Controlling multiple readers does not give the adversary any additional advantage, since a tag does not have to authenticate the RFID reader before transmission. The tag will always generate a different ω, n tuple to any reader that queries it. D. Protocol discussion Our protocol uses the counter ct that automatically incre￾ments each time the tag is queried. This feature allows an adversary, using his own reader, to query the tag simply to increment the ct value. However, this behavior only degrades the user’s performance, and does not help the adversary learn anything about the user. A rational adversary will not launch this type of attack. Our choice of ω in the protocol is h(ID, n). Given an adversary, a possible alternative is to set ω as h(ID, t). This will have the same properties as h(ID, n) since the time value t will only occur once and never repeat. Using h(ID, t) will also give better query performance, since the user can directly determine the appropriate ω and query the LS, instead of doing a binary search on T S to determine n. The reason we do not use h(ID, t) is that different readers may have a slightly different clock skew. Thus, honest readers may issue the same t 58