24

Storage-Awareness: RFID Private Authentication based on Sparse Tree ∗ Weijia Wang, Yong Li, Lei Hu and Li Lu State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences {wwj, yli, hu, luli}@is.ac.cn Abstract As the growing use of Radio Frequency Identification (RFID) technology to enhance ubiquitous computing environments, the privacy protection problem becomes a crucial issue. The objective of private authentication for RFID systems is to allow valid readers explicitly authenticate their dominated tags without leaking tags’ private information. To achieve strong privacy, recently, Lu et al. propose a Strong and lightweight RFID Private Authentication protocol (SPA), which enables dynamic key-updating mechanism for balanced tree based authentication approaches. However, due to its balanced tree structure, SPA is still susceptible to compromising attacks. In this paper, we propose a Storage-Aware Private Authentication protocol (SAPA). This scheme employs the sparse tree structure, and treats the path of each tag in the tree as an independent secret. As a result, SAPA enjoys perfect privacy and largely reduces the space for storing key sequence on the side of the tag, while keeping the key search complexity on the side of the reader still be logarithmic.

1 Introduction Radio Frequency Identification (RFID) is a technology for automated identification of objects in a contactless manner. RFID systems are made up of small and inexpensive transponders (tags) inserted into the objects, of readers which communicate with tags using radio frequencies, and usually of a back-end database which contains information on the tag. Tags, which have the ability to store data and derive their power from the signal of an interrogating reader, are small microchips designed for wireless data transmission in response to interrogation by an RFID reader. Readers are often regarded as a simple conduit to back-end database; and it is generally assumed that the connection between reader and back-end database is a secure link. Thus, in this context, our focus is put on the communication link between tags and reader. ∗ Supported

by NSFC(60573053).

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

The advantages of using RFID technology is growing tremendously and is gaining much attention, which is seen by an increase in its deployment, such as object tracking and monitoring, supply-chain management, and personalized information services. However, these low-cost tags provide no access control and tamper resistance to sensitive information and hence pose new risks to security and privacy. For example, without privacy protection, any RFID reader can identify a consumer’s ID via the emitted serial number from the tag. As a result, a buyer can be tracked and profiled by unauthorized marketers. Therefore, a secure RFID system must meet two requirements, which also are the objective of private authentication. On one hand, a valid reader must successfully identify the valid tags; on the other hand, misbehaving readers should not be able to retrieve private information from these tags. Related work. To address the above privacy protection issue in RFID system, many efforts have been made to achieve efficient private authentication. One method is to employ encryptions in RFID authentication. Each tag shares a unique key with the RFID reader and sends an encrypted authentication message to the reader. Instead of identifying the tag directly, the reader hereby searches all keys that it holds to recover the authentication message and identify the tag. Weis et al. [12] first advanced the general approach of key search for RFID-tag identification. They proposed a hash function based authentication scheme, HashLock, to avoid tags being tracked. In this approach, each tag shares a secret key k with the reader. The reader sends a random number r as the authentication request. To respond to the reader, the tag generates a hash value on the inputs of r and k. The reader then computes h(k, r) with all stored keys until it finds a key to recover r, thereby identifies the tag. The search complexity of HashLock is linear to n, where n is the number of tags in the system. In practice, if the set of tags {Ti }ni=1 is large, then key search can be prohibitively costly. Most subsequent approaches in the literature are aimed at reducing the cost of key search. In [7], these approaches are classified into three types. Tree based approaches: ([10, 9, 4, 8]) Molnar et al. [10]

proposed a scheme in which a tag contains multiple keys instead of a single symmetric key. A virtual hierarchical tree structure is constructed by the reader to organize these keys. Every node in the tree, except the root, stores a unique key. Each tag is associated with a unique leaf node. Keys in the path from the root to the leaf node are hereby distributed to this tag. If the tree has a depth d and branching factor α, each tag contains d keys and the entire tree can support up to N = αd tags. A tag authenticates to a reader using each of its d keys. The reader can identify a tag by performing a breadth-first search in the key tree. In each hierarchy, the reader can narrow the search set within α keys. Thus, the reader only needs to search d · α keys for each tag’s authentication. Therefore, the key search complexity of identifying a given tag is improved from O(N ) to O(log N ). In [4], Dimitriou provided a more efficient scheme which performs the authentication via one message from the tag to the reader and no further interactions. However, the tree based approaches are often vulnerable to the Tag Compromising Attack. Because tags share keys with others in the tree structure and most tree based approaches are lack of key-updating mechanism, compromising one tag results in compromising secrets in other tags. To address this problem, Lu et al. [8] proposed a Strong and lightweight RFID Private Authentication protocol (SPA) , which enables dynamic key-updating approach for balanced tree based authentication approaches. Synchronization approaches: ([11, 6, 3]) Ohkubo et al. [11] employed counter and window technique to enhance the authentication security. But such scheme is vulnerable to Desynchronization Attack, in which an invalid reader can interrogate a tag many times so that the counter of this tag exceeds the window recorded in the valid reader. For this, in [6, 3], by allowing tags report the number of incomplete authentications or increasing tag’s counter only after successful mutual authentications, the authors proposed their respective protocols to mitigate the impact from desynchronization attacks. Those protocols, however, degrade the anonymity of tags. An attacker is still able to interrogate a given tag enough times so that the tag will be immediately recognized when replying unchanged responses. Time-space tradeoff approaches:([1, 5]) Avoine [1] converted the key search problem to an attempt of breaking a symmetric key. In [5], Hellman studied the key-breaking problem and claimed that to recover a symmetric key k from a ciphertext needs pre-computation and stores O(N 2/3 ) possible keys. Accordingly, the key search complexity is O(N 2/3 ) in key-breaking based approaches. Our contributions. Balanced tree based approaches are efficient, nevertheless, not secure due to the tight relationships among the adjoining tags in the tree. Although Lu et al.[8] attempts to address this problem by recursive key-

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

updating from bottom to top in the tree, the tight relationships among the adjoining tags is not essentially resolved since they still use the balanced tree structure. On the other hand, corresponding to balanced tree structure, especially in a large scale RFID system, a long sequence of keys should be stored, which can hardly be afforded for low-cost tags. In this paper, we propose a Storage-Aware Private Authentication protocol (SAPA). This scheme achieves an effective and efficient key-updating based on a sparse tree structure. In SAPA, for the first time, we treat the path of each tag in the sparse tree as an independent secret. Instead of the redundant keys in the non-leaf node [10, 8], such secret is stored in the tag and is updated by directly using a cryptographic hash function. As a result, SAPA enjoys perfect privacy. Furthermore, by our approach, the key search complexity on the side of the reader is still kept logarithmic, while the space for storing key sequence on the side of the tag is largely reduced.

2 SAPA Protocol 2.1

Prior Schemes Overview

The primitive tree based scheme [10] is static, in which the reader organizes and stores the keys for all tags by using a balanced tree. Each node of the tree stores a key. A sequence of keys assigned to each tag are in turn disposed on a unique path from the root to the leaf. The reader can identify a tag by performing a breadth-first search in the key tree. This algorithm for the tag identification is efficient, because the complexity of tree-based key search is logarithmic. However, due to using the static tree structure, each tag will share some keys with others, more or less, which leads to the leakage of parts of keys of innocent tags when some tags are compromised. For this, very recently, Lu et al. [8] proposed a dynamic key-updating scheme, SPA, which reduces the key relationship between compromised tags and uncompromised ones by recursively updating keys in the tree. In this solution, the whole protocol procedure consists of two stages: Identification and synchronous key-updating. For example, as shown in Fig.1, there are four tags T1 , T2 , T3 and T4 , and the reader R stores their keys with a balance binary tree, where all subtree state bits sli,j and sri,j are assumed to be zero in the beginning. Upon successfully identifying T1 , the reader R updates k2,1 , sets the bit sl1,1 to be 1, and then sends to tag T1 the synchronization updating information as a response. Similarly, when R finishes identifying T2 , it updates k2,2 and set sr1,1 as 1. And then R checks sl1,1 and sr1,1 . If both of them are 1, R updates k1,1 , stores the old t value in the temporary key k1,1 for the next identification l for T1 and in the end sets s0 as 1. Until now, one can easily conclude that the key updating algorithm from the leaf to

k0t ,k0 l r s0 s0 k1t,1,k1,1 s1l,1

k1,t2,k 1,2 s1r,1

s1l,2

k m1 k m2

001 010

k m3

110 s1l,1 1

s1r,2 s2l ,1

k2,1 T1

k2,2 T2

k2,3 T3

s0l 1

k2,4 T4

s1r,1 1

KH

s0r

1

s1l, 2

0 s2r,1 1 s2l , 2 1 s2r , 2

0 0

k r2

k r1

T1

s1r, 2 1 s2l , 4 1 s2r , 4

0

kr3

T2

T3

Figure 1. The balanced tree of SPA Figure 2. The sparse tree of SAPA the root is recursive, so here we no longer make a further description. Refer to [8] for more details. In fact, both ideas of the two schemes above make use of the balanced tree structure to improve the search speed at the cost of the storage of secrets held by each tag. For example, let us consider the case that there are n = 220 tags and each key is 64 bit, as a result each tags should store 20 × 64 = 1280 bit keys, which will be a hard job for some tags lack of memory resources. On the other hand, although the key-updating mechanism in Lu et al.’s scheme, to a certain extent, reduces the key relationship as a whole, local key relationships, especially between the tags whose last keys are brother leaf nodes (we refer to them as brother tag, for simplicity), are still kept relatively static. Therefore the compromise of some tag still imperil the privacy of its brother tag seriously even if the aforementioned updating tactic is employed. To address the two problems above, we propose our solution SAPA.

2.2

Basic Idea of SAPA

In SAPA, we make use of a sparse tree structure, instead of a balanced tree, to organize all tags’s keys. In the tree, none of non-leaf nodes (except the root) stores keys, and each path from the root to the leaf, as an independent secret, is held by the corresponding tags and is updated by using cryptographic hash function in the key-updating stage. As a result, with logarithmic search complexity, our scheme enjoys both low key-storage cost and perfect privacy on the side of tags. In the following , we present the description of our scheme which consists of four components: initialization, identification, key-updating and maintenance.

2.3

Initialization

It is assumed that there are n tags Ti , 1 ≤ i ≤ n, and a reader R in the RFID system. The reader R stores and organizes keys of all tags by using a sparse tree, called key tree S. Let α denote the branching factor of the key tree and

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

R

Ti Request, r1 − −−−−−−−−−−− →

Identification.

r2 , W ←−−−−−−−−−−−−

Computing W .

Computing ∆ and key-Updating.

∆ − −−−−−−−−−−− →

Checking ∆ then updating keys.

Figure 3. The identification of SAPA .

d denote the depth of the tree. To present our scheme more clearly, we only described the scheme in terms of a binary tree, but nothing restricts the sparse-tree-based scheme to binary trees. Hence α = 2 in the following. The secrets held by each tag is a key triple (kh , km , kr ), where kh and kr are corresponding to the root and the leaf node in the key tree S, respectively; km represents the path from the root to the leaf, of which each bit denote which subtree the path will pass through (i.e. 0 refer to left subtree and 1 does right one) in each level of the tree S. Each non-leaf node is assigned with two state bit sl and sr , which are used to denote whether its left or right subtree exists. In the initialization, the tree S is empty. When the n tags {T1 , T2 , ..., Tn } are enrolled into the system, the reader R first builds a root for the tree S and assigns to it a number KH chosen at random. Next, R generates n 1 n binary {(Km , Kr1 ), ..., (Km , Krn )} randomly. For each bii i nary (Km , Kr ), R inserts a branch (or path) in the tree from the root, level by level, in turn according to each bit i of Km , assigns Kri to the leaf node of the branch, and i then distributes (KH , Km , Kri ) to tag Ti as its key triple i i i (kh , km , kr ). In the end, the reader R finishes assigning the n tags to n branches in a sparse binary tree S. For simplicity of exposition, we consider a simple and trivial case, where there are only tree tags T1 , T2 and T3 and a sparse binary tree of three levels are used to manage them, as illustrated in Fig.2.

2.4

Identification

Let h denote a cryptographic hash function: {0, 1}∗ → {0, 1}lr , where lr be a security parameter in the system. The authentication procedure between the reader R and a tag Ti comprises three rounds, as illustrated in Fig.3. In the first round, R starts the protocol by sending a “Request” and a nonce r1 to tag Ti . In the second round, upon request, Ti generates a nonce r2 and computes a sequence of hash chains i W ={h(khi , r1 , r2 ), h(h(khi , r1 , r2 ), km [1]), ..., i h(h(h(...h(khi , r1 , r2 )), km [l]), kri )}, i i [j] denotes the j-th bit in the binary string km and where km i l is the size of km . Upon receipt of the authentication information from Ti , R begins to identify Ti with the help of key tree S. By using KH stored in the root, the reader R first verify the first item h(khi , r1 , r2 ) in the authentication sequence. If it is valid, R invokes a recursive algorithm to identify the following hash chains level by level in terms of the subtree state bit of non-leaf nodes until the leaf node. For the example in Fig.2, the reader R authenticates tag T1 . Let M = h(kh1 , r1 , r2 ), and the authenticators sequence from T1 can be shown as follows

{M, h(M, 0), h(h(M, 0), 0), h(h(h(M, 0), 0), 1), h(h(h(h(M, 0), 0), 1), kr1 )}. After successfully verifying M with h(KH , r1 , r2 ), R computes h(h(KH , r1 , r2 ), 0) (if sl0 = 1) and h(h(KH , r1 , r2 ), 1) (if sr0 = 1), and then compares them with the received h(M, 0). It is clear that the former is equal to h(M, 0), which means that the tag is belonging to the left subtree of the root, thereby R continues to verify the next hash chain by checking sl1,1 and sr1,1 . The rest identification procedure may be deduced by analogy until R extends the path (001) of T1 from the root to the leaf. Finally, R finishes authenticating the whole hash chain sequence by verifying the last hash chain with the leaf node kr1 . Note that if both subtree state bit are zero or both the comparisons between the hash chain from the target tag and the reader’s own computation result fail at corresponding level in the tree, the identification procedure of the tag fail and stop.

2.5

Key-Updating

In the following, we introduce the key-updating algorithm, which are invoked by the reader after the aforementioned identification step, as shown in Fig.3. It is assumed that the target tag is Ti , and the reader R has obtained its corresponding branch from the root to the leaf in the

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

key tree S by the identification procedure. For generating new keys, R still makes use of the hash function h. i Let khi , km , kri be the old key held by Ti , which also are in the form of a branch in S mastered by the reader. The i  reader computes a new key from the old key as km =  i i , kri , r1 , r2 , 1), kri = h(kri , km , r1 , r2 , 2). Next, the h(km reader invokes the branch-deletion algorithm to erase the i branch corresponding to km from the tree S and inserts a i  in S by applying the branchnew one corresponding to km  insert algorithm. Finally it stores kri in the leaf node of the new branch. Upon finishing the key-updating, R sends a i synchronization message ∆ = h(km , kri , r2 , r1 , 3) to Ti , as shown in Fig.3. Having received these messages, Ti first i verifies whether or not ∆ = h(km , kri , r2 , r1 , 3). If yes, Ti updates its keys according to the synchronization message, that is, it computes new keys just as the reader does above. In the end, both the tag Ti and the reader R will share a new i  i secret triple {khi , km , kr }. As for the updating of KH shared by all tags, we can implement it easily by employing the similar method as in [8].

2.6

Maintenance

Compared with the scheme provide by Lu et al. [8], it is much easier for the system to withdraw or add tags in our scheme. For withdrawing a tag, the system calls the branchdeletion algorithm to delete the corresponding branch from the key tree. For adding a new one, the system chooses a new secret triple randomly, assigns it to the new tag and then invokes the branch-insert algorithm to add a corresponding new branch from the root.

3 Security Analysis In this section, we focus on the formal analysis of the privacy of SAPA under compromising attack. The informal analyses of our scheme on the security requirements mentioned in [4] are similar to those of SPA in [8].

3.1

Model and Definition

Compromising attack is a serious active attack, in which by compromising some tags’ keys, attackers attempt to trace the uncompromised ones. In the following, we make use of a attack model to formalize the ability of adversary. The model in this paper is mainly based on Avoine’s attack model [2], in which the attackers and the RFID system are abstracted into two participants: the Adversary A and the Challenger C. Attacking-defending between the attackers and the RFID system is like a game between A and C. Any attack on a given R or T can be represented as A’s calling on one of its oracle as follows:

Query(T, m1 , m3 ): A sends a request m1 to T . Subsequently, A receives a response from T . A then sends the message m3 to T . Send(R, m2 ): A sends a message m2 to R and receives R’s response. Execution(T, R): A acts as a man in the middle and executes an instance of P with T and R, respectively. A then modifies the received response message from one side and relays it to another side. Reveal(T ): After accessing this oracle of T , A compromises T , which means A obtains T ’s keys. Note that A can distinguish any given tag T from other tags if it can obtain T ’s keys. Based on these oracles, the detailed procedure of a game between A and C is demonstrated by following steps. 1. A interacts with C by asking the above four oracles in polynomial times. 2. A tells C that the guess begins. C chooses two uncompromised tags T0 and T1 . 3. For two tags T0 and T1 chosen by C, A accesses the oracles (except the Reveal oracle) of T0 and T1 . For T0 and T1 , let OT0 and OT1 denote the sets of accessed oracles, respectively. 4. C selects a bit uniformly at random, and then provides the oracles of the corresponding tag Tb (if b = 0, Tb = T0 , otherwise, Tb = T1 ) to A. For simplicity, we denote Tb as T . A then accesses T ’s oracles (except the Reveal oracle). Let OT denote the set of accessed oracles of T . 5. Based on the results from OT0 , OT1 and OT , A outputs a bit b . If b = b, we say A succeeds; otherwise, A loses. In the model, we assume that A can access the oracles of OT0 , OT1 and OT in polynomial times. Since T0 and T1 are randomly chosen from uncompromised tags, if A can not guess successfully with the probability which is non-negligibly higher than 1/2, it means that the RFID system is compromising resistance.

Proof. In the proof, we use the random oracle model (ROM) [14], in which hash functions are used as black box by attackers for whom they are indistinguishable from perfectly random functions. Let A be an adversary attacking SAPA by asking at most qh queries to the hash oracle, qE queries to the Execution oracle, qS queries to the Send oracle, and qQ queries to the Query oracle. For simplicity, we assume that all tags held by challenger C (the RFID system) except T0 and T1 have been compromised by the adversary A. This means that the first keys kh ’s of T0 and T1 , which is same for all tags, has been obtained by A, and the second keys km ’s of them used in each authenticating procedure also can be inferred by verifying the hash chain. We incrementally define a sequence of games starting at the real game G0 and ending up at the game G4 in which the advantage of the adversary is zero. We define Succi as the event that A guesses b hidden in C correctly in game Gi , and then use the Shoup’s lemma [13] to bound their probabilities. Furthermore, we assume that when the game below aborts or stops with no answer for b hidden in the oracles from A, we guess a random bit for b, in which the success probability of the adversary is straightforwardly 1/2. Game G0 : This game represents the real attack game, where all the instances of C modeled as oracles are available to the adversary. By definition, we have

3.2

It also simulates all the authentication instances, as the real system would do, for Query, Send and Executivequeries. For this simulation, we can find that the game is perfectly indistinguishable from the real attacks. Game G2 : In this game, C cancels games in which some collision appears:

Security Proof

Based on the above model, we formally show our scheme SAPA satisfies compromising resistance by the following theorem. Theorem 1. Let qE , qS and qQ denote the number of queries to Execution, Send and Query oracles, respectively, and let qh be the number of queries to the random oracle h. Then, (qE + qS + qQ )2 + qh2 2 · 2 lr qS + qQ + qE + qh + 2 lr

cr AdvSAP A (qE , qS , qQ ) ≤

where lr is the security parameter in the RFID system.

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

cr AdvSAP A (A) = 2 · P r[Succ0 ] − 1.

(1)

Game G1 : In this game, C simulates the hash oracles (h, but also additional hash function h :{0, 1}∗ → {0, 1}lr that will appear in the Game G4 ) by maintaining hash lists Λ as follows. • For a hash-query h(q) (resp. h (q)), such that a record (q, t) appears in Λh (resp. Λh
), the answer is t. Otherwise one chooses a random element t ∈ {0, 1}lr , answers with it, and adds the record (q, t) to Λh (resp. Λh
).

• collisions on the partial transcripts((r1 ,·)(r2 ,·)). Note that transcripts involve at least one honesty party, and thus one of r1 or r2 is truly uniformly distributed. • collisions on the output of h. Since both probabilities are bounded by the birthday q2 (q +q +q )2 paradox: P r[coll2 ] ≤ E 2·2Slr Q + 2·2hlr , we can get the following lemma.

Lemma 1. |P r[Succ2 ] − P r[Succ1 ]| <

2 (qE +qS +qQ )2 +qh . 2·2lr

Game G3 : In this game, we modify the simulation of the oracles by changing the authentication message from tags into {r2 , kh , rm , h(r1 , r2 , kh , km , kr )}, where rm is the random number selected by the oracles. Since there is no occurrence of collisions and the adversary A has obtained the first key kh , it is clear that the success possibility of A in the game is exactly the one in the previous. Game G4 : In this game, C uses the its private oracles h , instead h, to generate the authentication messages and synchronization ones. The two games G4 and G3 are perfectly indistinguishable unless A queries the hash functions h on {r1 , r2 , kh , km , kr } or {km , kr , r2 , r1 , 3}. So, the lemma follows from the fact that probability of the occurrence of q +q +q +q the above two queries is at most S Q2lr E h . Lemma 2. |P r[Succ4 ] − P r[Succ3 ]| <

qS +qQ +qE +qh . 2lr

Thus far, since no information on the bit b hidden by in C is leaked to the adversary, we have P r[Succ4 ] = 1/2. Combining with the previous lemmas, one gets the result on compromising resistance in Theorem 1.

4 Conclusions and Future Work In this paper, we propose a RFID private authentication scheme, SAPA, to provide perfect privacy and low storagecost for tags. To keep the pseudo-randomness and one-way properties of the cryptographic hash function and the sparse degree of the key tree, we suggest to use MD5 or SHA-1 as the hash function h in practice. For reducing the number of computation rounds of tags, it is preferential to set the branching factor of the key tree α = 16 and encrypt four bits of the second key of the secret with the hash function each time. In a large scale RFID system, where are 220 tags or more, the search complexity of the reader will be 4 times as the one in the scheme of [8], and the complexities of computations and communications of each tag will be nearly same as the ones of the scheme [8]. However, it is well known that the reader in the RFID system is assumed to be powerful, so it is justified to use our scheme to win an overall improvement on privacy and save tag’s storage at the cost of acceptable increases in the search complexity of the reader. Certainly, especially for some small scale RFID systems, to limit the depth of the sparse key tree (i.e. to reduce the computation and communication cost in the tag side) to a certain degree, we can consider to reduce the length of the second key in the secret triple and only use parts of hash function’s output, which will introduce some additional key-updating synchronization mechanism between tags and the reader for treating potential hash collisions. It will be an interesting challenge in the future work.

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

References [1] G. Avoine, E. Dysli, P. Oechslin, “Reducing Time Complexity in RFID Systems,” in Proceedings of SAC, 2005. [2] G. Avoine, “Adversarial Model for Radio Frequency Identification,” in Cryptology ePrint Archive, 2005. [3] T. Dimitriou, “A Lightweight RFID Protocol to Protect Against Traceability and Cloning Attacks,” in Proceedings of SecureComm, 2005. [4] T. Dimitriou, “A Secure and Efficient RFID Protocol that Could make Big Brother (partially) Obsolete,” in Proceedings of IEEE PerCom, 2006. [5] M. Hellman, “A Cryptanalytic Time-Memory Tradeoff,” in IEEE Transactions on Information Theory, 1980. [6] A. Juels, “Minimalist cryptography for low-cost RFID tags,” in Proceedings of SCN, 2004. [7] A. Juels, “RFID Security and Privacy: a Research Survey,” in IEEE Journal on Selected Areas in Communications, 2006. [8] L. Lu, J. Han, L. Hu, Y. Liu, and L. M. Ni, “Dynamic Key-Updating: Privacy-Preserving Authentication for RFID Systems,” in Proceedings of IEEE PerCom, 2007. [9] D. Molnar, A. Soppera, D. Wagner, “A Scalable, Delegatable Pseudonym Protocol Enabling Ownership Transfer of RFID Tags,” in Proceedings of SAC, 2005. [10] D. Molnar, D. Wagner, “Privacy and Security in Library RFID: Issues, Practices, and Structures,” in Proceedings of ACM CCS, 2004 [11] M. Ohkubo, K. Suzuki, S. Kinoshita, “Efficient hashchain based RFID privacy protection scheme,” in Proceedings of Ubicomp, Workshop Privacy, 2004. [12] S. Weis, S. Sarma, R. Rivest, D. Engels, “Security and privacy aspects of low-cost radio frequency identification systems” in Proceedings of SPC, 2003. [13] V. Shoup, “OAEP Reconsidered,” in Proceedings of Cryptology, 2001. [14] M. Bellare, P. Rogaway, “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols,” in Proceedings of ACM CCS, 1993.