The Study on Secure RFID Authentication and Access Control

1. Introduction

In recent years, Radio Frequency Identification (RFID) technology is rapid progress and has been widely used in daily life. RFID systems consist of three components: radio frequency (RF) tags, RF readers and a back-end database server. A passive RFID tag is a microchip capable of transmitting a static identifier or serial number for a short distance. Readers query tags for their contents by broadcasting an RF signal. Tags respond with resident data, such as a unique serial number. Tag data may be read automatically without line of sight. RFID systems have many applications in supply chain managements, inventory control, anti-counterfeiting, ticketing systems, healthcare and smart home developments.

However, it may bring up some privacy threats. Anyone can easily access tagged items and collect data without line of sight that personal privacy under threat. The most concerned issues are the tracking and the location privacy. Based on the characteristic of outstanding traceability, the history of the tag’s location might be identified as a tag’s information is intercepted and collected by the attacker in different location. For instance, the unique tag’s EPC data can be used to trace a person or an object carrying a tag in time and space. The collected information can be merged and linked in order to generate a person’s profile. It will be a serious problem as RFID tags are widely used.

Without privacy protection, a person with carried RFID tags can be tracked and profiled by unauthorized people. The unique information of the items may be indicated that a customer carrying those tags is subject to track from unauthorized readers.

Ideal RFID systems used in product lifecycle should satisfy high confidentiality, anonymity, integrity and high availability (Gao et al., 2004; Pisarsky, 2004). The product life cycle is a procedure that the product from manufacture to be recycled. This procedure from the perspective of commerce can be divided into five stages(Figure 1): (1)&(2) are the stage of “production to retail store” (business-to-business), (3) is the stage of “retail store to customer” (business-to-customer), (4) is the stage of “individual sales” (customer-to-customer), (5)&(6) are the stage of “after-sales service”, and (7) is the stage of “recycling” (reverse logistics). Since a tag is embedded in the product, security risks such as privacy threats may be occurred in each stage of the product life cycle.

Figure 1.

The product life cycle.

To our desirable point, researchers need to pay more effort to develop object identication throughout the life cycle with guaranteeing the corporate and personal privacy, illegal tracking, unauthorized profiling, impersonating, cloning, and illegal reading/writing. This article is not purpose of an exhaustive literature survey but summarizes some aspects of RFID authentication and access control in the proposed studies.

2. Basic RFID tags

In most RFID systems, tags automatically emit their unique serial numbers upon reader interrogation without alerting their users. The challenge in providing security for RFID tags is such kinds of low-cost device unable to perform basic cryptographic operations. Basic RFID tags just have a little rewritable memory, even have no programmable-supported computing capability. At best, such RFID tags may include security functions supporting keyed reads and keyed writes which essentially just like PIN-controlled data accesses. In this section, we show how privacy and authentication may be considerably improved in low-cost RFID tags with only a small enhancement of their capabilities.

2.1. Killing and sleeping

The “kill command” method is a straightforward approach to make a tag no longer functional. This approach proposed by the AutoID Center is indeed for tags to be killed upon purchase of the tagged product. A tag can be killed by sending it a special “kill command” with a short PIN (Sarma et al., 2002; Weis et al., 2003). As the tag receives the “kill” command, its state changes into the inoperative state. Kill the tag technique is to restrict the use of a tag by removing its identity. As shown in Fig. 2, the killed tag has no way to change back to the inventoried state. It cannot be identified for more detailed information again. For example, purchased goods would be killed at checkout clerks such that no one would contain active RFID tags for protecting the consumer privacy. This solution is simple and effective but the tag can not be reused. Clearly, the tag’s lifecycle is end and it cannot be applied for after-sale purposes.

Figure 2.

The state changing of the tag in killing approach

Another kind of solution is using the “sleeping” mechanism. As the reader sends a “sleep” command to the tag, the tag will temporarily inactive. The sleeping tag can be waked as the tag receives PIN from the reader. The state changing of the tag is shown in Fig. 3. The tag’s state can be switched between inventoried and sleep. For controlling the tag’s access, the tag’s owner has to manage the PINs of all tags on purchased good. Unfortunately, passwords may be overheard or collected by spoofing a tag. This approach also pose other problems: a set of tags use a single generic PIN which can be easily defeated, but each tag use a unique PIN which could be uniquely identified by the adversary.

Figure 3.

The state changing of the tag in sleeping approach

2.2. Renaming approach

The solutions of relabeling or re-encrypting the tag’s serial number were proposed for minimal security requirements. This approach takes into account the natural computational limitations of RFID tags, it involves no computational operations but only relatively little storage. The relabelled or re-encrypted serial number is overwritten to the tag at checkout for protecting the consumer’s privacy. This is possible for current generation tags and would prevent the unauthorized compilation of bibliographic directories. However, even if the relabelled or re-encrypted identifier emitted by an RFID tag has no intrinsic meaning, it can still be tracked since the relabelled or re-encrypted identifier is just a static meta-identifier. Therefore, point-to-point tracking is possible if the meta-identifier is not changed over time. For this reason, this approach does not solve the problem of privacy.

2.2.1. Relabeling

Sarma et al. (2003) proposed an idea to protect the tracking problem (Sarma et al., 2003). As a customer purchases goods, the reader sends a “delete” command at the point of sale such that the tags’ unique serial number is erased. Only the product code information of the tag is retained for later use. The state changing of the tag is shown in Fig. 4. However, the tracing problem is still existed to distinguish individual by a fixed group RFID-tagged products. For example, someone is a fan of a particular brand will always take the brand’s shoes, watch and bag such that tracking is still possible by associating these kinds of particular tag types with holder identities.

Figure 4.

Sarma’s idea for erasing the tag’s unique identifier

Inoue & Yasuura (2003) proposed another relabling approach to offer users the identifier’s controllability for protecting privacy (Inoue & Yasuura, 2003; Inoue et al., 2002). Each tag has a read-only memory (ROM) and an electrically-erasable programmable read-only memory (EEPROM). These two memories are used exclusively. The state changing of the tag is shown in Fig. 5. A unique and permanent identity is stored in the tag’s ROM by the producer. As the tag remains on ROM mode, the permanent identity can be read. The tag can provide unlimited identification with ROM mode for total management at its production, distribution, and sale stage. For purchased goods, the owner can set a private and temporary identity in EEPROM. As switching to EEPROM mode, the tag cannot operate the permanent object identification. Even the temporary identity can be read by anyone, no one can recognize the tag since the information about the object in the network is distributed accompanying the permanent identity on the ROM as a key. Therefore, the adversary has nothing to do with the temporary identity. The object can be identified only by the owner. Moreover, the tag can be switched to ROM mode again by certificating the owner or restricting the change only via contacted communication. This approach remains the permanent identity for life cycle of the object. As the object is discarded, the scrap merchant can make the tag to be switched to ROM mode to operate the permanent object identification and utilize it for recycling. However, the temporary identity is unique and cannot avoid the point-to-point tracing problem since it could be uniquely identified by the adversary.

Figure 5.

Inoue’s double mode tag

Kinosita et al. (2003) proposed another approach to rewrite the tag (Kinosita et al., 2003). As a customer purchases the product on checkout, the reader rewrites a new random number to the tag. Fig. 6 shows the state changing of the tag. However, the random identifier is unique and cannot avoid the point-to-point tracing problem since it could be uniquely identified by the adversary.

Figure 6.

Kinosita’s approach to rewrite the tag

2.2.2. Re-encryption

Juels & Pappu’s (2003) proposed an approach based on re-encryption concept (Juels & Pappu, 2003). The public key cryptosystem is used in this scheme. The data of a banknote is arranged into optical and radio frequency areas. A unique serial number and a signature are printed on the banknote. The banknote serial number and signature are encrypted by the law-enforcement’s public key. The resulting ciphertexts are stored in the banknote’s tag. Clearly, the tag can be authenticated as the ciphertexts are decrypted by the law-enforcement for verifying the signature of serial number. For rendering multiple appearances of the tag unlinkable, these ciphertexts are re-encrypted with a new encryption factor by the law-enforcement’s public key after each access session. The encryption-operation requires high computational loading which is performed by the reader not the tag. The change in each appearance is designed for preventing the tracing problem. Fig. 7 shows the state changing of the tag. However, the ciphertexts keep constant (Ohkubo et. al, 2003) such that the tag still can be traced between twice re-encryptions. It means the tag must be rewritten often. This makes re-encryption approach unsuitable in practical. Basing on the re-encryption concept, a similar scheme proposed by Golle et al. (Golle P et al., 2004) known as universal re-encryption mechanism. It is essentially a special extension of the ElGamal cryptosystem (Elgamal T., 1985) in which re-encryption is possible without knowledge of public keys. However, this universal re-encryption mechanism has a practical drawback of requiring the role of agent to perform re-encryption.

Figure 7.

Juels & Pappu’s re-encryption approach

2.3. Distance measurement

Fishkin et al. proposed an approach to measure the distance between the reader and the tag (Fishkin et al., 2004). An adversary usually interrogates the tag in the far distance. Fishkin et al. observes and analyzes the energy of the received signal by the tag. The distance between the reader and the tag can be estimated by the signal-to-noise ratio. This distance information is used as a variable in a tiered authentication scheme, where the tag releases general or specific information to the reader according to the distance variable. Fig. 8 shows the state changing of the tag.

Figure 8.

Fishkin’s approach

2.4. Blocking & soft blocking

Juels et al’s (2003) proposed a mechanism to interfere with the readers' interrogation by a blocker tag (Juels et al., 2003). The blocker tag simulates all possible RFID tags to prevent the malicious identification of the target tag. This privacy protection scheme depends on adding a privacy bit to the tag. While inside a store, the tag’s privacy bit usually is set to 0, indicating public access to the tag’s identification. While during checkout, this privacy bit is changed to 1, denoting the tag is entering restricted access. Then the tag must interact with another tag known as the “blocker tag” (Juels et al., 2003). The blocker tag broadcasts radio signals to block/disrupt nearby RFID readers could work. It is accomplished through non-standard interaction with the anti-collision protocols employed in tag-reading session (Auto-ID Center, 2003; Sarma, 2001). The blocker tag will manipulate the query result of a normal tag by scrambling the bits of certain tags determined by their privacy bit (Juels & Brainard, 2004). The state changing of the tag is shown in Fig. 9. As the privacy bit is set to 0, the tag can be unrestricted scanned and the blocker tag doesn’t interrupt the reading of tag. As the privacy bit is set to 1, the tag is private with restricted access under the cover of blocker tag. Juels and Brainard proposed an enhancement mechanism called soft blocking (Juels & Brainard, 2004). The soft blocker tag transmits a policy statement to enforces and monitors the reader not violate the security policies. However, blocker tag is expensive (Cavoukian, 2004) and suffers from the heterogeneity of current RFID systems using different frequencies, air protocols, etc. The blocker tag and its variants have limited applicability.

Figure 9.

Blocking approach

3. Symmetric-key tags

Symmetric-key tags are considered as the type of security obtainable with a small amount of rewritable memory, but very limited computing capability. Such RFID tags may be expected to perform some basic computational operations, but not conventional cryptographic ones. Many approaches have been proposed to achieve private authentication in such RFID systems. The proposals usually include hash function, silent tree-walking, or other light cryptography-based approaches to prevent the unauthorized reading of RFID tags. Most researchers devoted to show that standard cryptographic functionality is not needed to achieve stronger security in RFID tags. Since the communication between the reader and the tag is using RF signals, which make an RFID system vulnerable to various attacks such as eavesdropping, traffic analysis, spoofing and denial of service. Within the scanning range, a malicious reader can perform bogus authentication with detected tags to retrieve sensitive information. The sensitive information may be disclosed and hence infringe on the user’s privacy. Traceability is another type of privacy violation, the relation between the user and the tag can be found will cause the tracing of the tag makes the tracing of the user possible (Avoine & Oechslin, 2005). The proliferation of RFID applications (Ni et al., 2003) raises an emerging requirement – protecting user privacy (Robinson & Beigl, 2003) in RFID authentications.

As the relationship is illustrated (Fig. 10) in Weis’s paper (Weis et al, 2003), the forward channel (reader-to-tag) is assumed to be easily monitored by an adversary since the signal broadcasted by the reader is strong enough, the backward channel (tag-to-reader) is relatively much weaker and may only be monitor by an adversary within the tag’s shorter operating range. The reader-to-tag (forward) channel and the tag-to-reader (backward) channel are assumed not secure, but eavesdroppers may only monitor the forward channel without detection.

Figure 10.

Forward vs. backward channels

In this section, we show how privacy and authentication may be considerably developed. It needs to take into account the natural computational limitations and the likely attack scenarios. The challenge in providing security for low-cost RFID tags is that they are computationally weak devices, unable to perform even basic symmetric-key cryptographic operations.

3.1. Non-indexed key-search approach

The general approach of key search for RFID-tag identification was proposed by Weis et al. (2003). Upon receiving a query from the reader, the tag first sends the hash value of its key with a random nonce. Without any index, the reader must compute for all keys until it identify the tag. As the tag responds with different values every time, the reader must exhaustively search until it finds the matched one. The scheme is not scalable for a huge number of tags since many computations must be performed at the back-end.(Rhee et al., 2005; Weis et al., 2003)

Weis et al. (2003) proposed two simple hash-based access control protocols, the hash-lock scheme and the randomized hash-lock scheme (Weis et al., 2003). Fig. 11 shows the randomized hash-lock scheme. Each tag has its initial $$I{D}_i$$ is issued by the back-end database server. As the reader tries to access the tag, the tag’s response is a hash value $$\alpha =h(I{D}_i||R)$$ generated by hashing the tag’s $$I{D}_i$$ concatenated with a random number$$R$$. If the reader is legal, it can ask the back-end database server to provide all tags’ identities. Then the reader performs a brute-force searching comparison between $$\alpha$$and $$h(I{D}_k||R)$$ to find the corresponding record. This scheme is not scalable since the reader’s computational loading is O(n).

Figure 11.

Weis‘s randomized access control scheme

The motivation of this scheme is to make the tag’s response message not predictable to prevent the tracing of individual. To randomizes tag responses instead of a invariable tag response in order to protect location privacy. However, the tag still can be traced as shown in the following use-case diagram (Fig. 12). An adversary can eavesdrop on the legal reader’s broadcasts $$I{D}_i$$ for collecting to its own database. As the target tag’s identity is collected, the adversary immediately realizes the tag had appeared on the location. In addition, the adversary may interrogate a tag to get its response message $$(R,\alpha )$$ for making a brute-force searching comparison between $$\alpha$$and $$h(I{D}_i||R)$$ to figure out which collected identity $$I{D}_i$$ is matched. Therefore, any collected identity can be traced.

Figure 12.

The attack on Weis’s randomized access control scheme

3.2. Indexed key-search approach

The major sticking point with the non-indexed key-search approach is that the reader’s computational loading is O(n). Under the practical consideration, it is not scalable since the process of key search can be prohibitively costly if the set of tags is large. For reducing the cost of key search, the tag’s first reply message must be the index for key-searching. As the reader has sent the right response being the “key”, then the tag reveals its identity. Unfortunately, the invariable index value will cause the tag traceable. (Chien, 2006; Huang, 2009; Weis et al., 2003)

3.2.1. Weis's hash-based access control scheme

Weis et al. (2003) proposed the hash-lock scheme (Weis et al., 2003), shown in Fig.13. Each tag has a hash value $$metaI{D}_i$$ of its $$Ke{y}_i$$ as it is issued by the back-end database server. The

Figure 13.

Weis’s hash-based access control scheme

reader can only get this hash value $$metaI{D}_i$$ as it tries to access the tag. If the reader is legal, it can ask the back-end database server to retrieve the corresponding$$Ke{y}_i$$. After the tag receives the correct $$Ke{y}_i$$ from the reader, the tag’s information can be accessed by the reader. Unfortunately, the scheme not offers location privacy since the tag can be uniquely identified by its hash value. Another drawback is that the plain key is sent over the forward channel which can be eavesdropped in the RF-signal range.

In this scheme,the tag can be traced as shown in the following use-case diagram (Fig. 14). The adversary can eavesdrop on the legal reader’s broadcasts $$Ke{y}_i$$ for collecting to its own database. As the target tag’s key is collected, the adversary realizes the tag had appeared on the location. Moreover, the adversary may interrogate a tag to get its response message $$metaI{D}_i$$ for making a comparison between $$metaI{D}_i$$and $$h(Ke{y}_i)$$ to figure out which collected $$Ke{y}_i$$ is matched. Since a tag’s response message is an invariable$$metaI{D}_i$$, it can be treated as an identifier, for the adversary to trace individuals. This scheme supports data privacy but can not protect location privacy of the tag since the invariable hash value is used in each time.

Figure 14.

The attack on Weis’s hash-based access control scheme

3.2.2. Chien’s hash-based access control scheme

Chien (2006) proposed another hash-based access control scheme (Chien, 2006), shown in Fig. 15. The back-end database server’s master secret key is$$K_{svr}$$, and each tag’s unique key is $$Ke{y}_i=h(K_{svr}||I{D}_i)$$ Each tag has a hash value $$metaI{D}_i$$ of its $$Ke{y}_i$$ as it is issued by the back-end database server. As the reader tries to access the tag, it can get this hash value $$metaI{D}_i$$ and the current$$date$$. If the reader is legal, it can ask the back-end database server to retrieve the corresponding $$I{D}_i$$ for generating the right$$Ke{y}_i$$. Then the reader generates a hash value $$h(Ke{y}_i\oplus date)$$ by the tag’s $$Ke{y}_i$$ and the received current$$date$$. After the tag receives the correct hash value $$h(Ke{y}_i\oplus date)$$ from the reader, the tag’s information can be accessed by the reader.

Figure 15.

Chien’s hash-based access control scheme

Figure 16.

The attack on Chien’s hash-based access control scheme

Fig. 16 shows the use-case diagram of this scheme’s weaknesses. The adversary can eavesdrop on the legal reader’s broadcasts $$Res{p}_i$$ for collecting to its own database. As the target tag’s response is collected on the same day, the adversary realizes the tag had appeared on the location. Moreover, the adversary may interrogate a tag to get its response message ($$metaI{D}_i$$,$$date$$). Since a tag’s response message has an invariable$$metaI{D}_i$$, it can be treated as an identifier for the adversary to trace individuals.

3.3. Synchronization approach

The general idea is to change the tag’s identifier after each access session. By refreshing both of the tag’s identifier and the corresponding back-end database record in each session, the identifier cannot be employed for tracking purposes. The adversary can only eavesdrop or intercept a single, unreliable message exchange, it seems to provide the tag with location privacy. The literature explores several variants of this principle. Ohkubo, Suzuki, and Kinoshita (OSK) propose the conceptually simplest approach. Henrici and Müller propose to resolve the synchronization problem. Dimitriou proposes a scheme that eliminates the issue of desynchronization entirely. (Avoine & Oechslin, 2005; Dimitriou, 2005; Henrici & Muller, 2004; Joaquin et al., 2011; Juels, 2004; Lee et al., 2005, 2006; Ohkubo et al., 2003; Osaka et al., 2006)

3.3.1. Henrici & Muller’s hash-based ID variation scheme

Henrici & Muller (2004) proposed a hash-based ID variation scheme (Henrici & Muller, 2004), shown in Fig. 17. A tag with initial$$I{D}_i$$, transaction number $$TI{D}_i$$ and last successful

Figure 17.

Henrici & Muller’s hash-based ID variation scheme

transaction number $$LS{T}_i$$ are issued by the back-end database server. As the tag is queried, the tag’s transaction number $$TI{D}_i$$ is increased progressively and the message ($$\beta =h(I{D}_i)$$,$$\gamma =h(TI{D}_i\oplus I{D}_i)$$ ,$$\Delta TI{D}_{\text{i}}=TI{D}_{\text{i}}\text{-}LS{T}_{\text{i}}$$) is responded to the reader. If the reader is legal, it can ask the back-end database server to use $$\beta =h(I{D}_i)$$ identifying the tag. Then the back-end database server’s response is the hash value $$\alpha =h(R\oplus TI{D}_i\oplus I{D}_i)$$ generated by the transaction number$$TI{D}_i$$, tag’s identity$$I{D}_i$$, and a random number$$R$$. After the tag receives the correct hash value $$\alpha$$ from the reader, the tag’s information can be accessed by the reader.

In this scheme, the tag updates its $$I{D}_i$$ after each successful access. It seems to make the tag’s response message $$\beta =h(I{D}_i)$$ not predictable to prevent the tracing of individual. However, the design of identity variation not really guarantees the location privacy. Fig. 18 shows the use-case diagram of this scheme’s weaknesses. The adversary may interrogate a tag to get its response message $$\beta =h(I{D}_i)$$ and $$\Delta TI{D}_{\text{i}}=TI{D}_{\text{i}}\text{-}LS{T}_{\text{i}}$$ for collecting to its own database. If$$\Delta TI{D}_i\ge 2$$, it means the last transaction is not successful and the tag’s identity $$I{D}_i$$ is not updated. As the target tag’s hash value $$\beta =h(I{D}_i)$$ once again collected, the adversary immediately realizes the target tag appeared.

Figure 18.

The attack on Henrici & Muller’s hash-based ID variation scheme

3.3.2. LCAP scheme

Lee et al. (2005) proposed a low-cost RFID authentication protocol (LCAP) (Lee et al., 2005), shown in Fig.19. A tag with initial $$I{D}_i$$ is issued by the back-end database server. The back-end database server always maintains a previous-session record and a current-session record for a tag. Each record has the fields (HaID_i, ID_i, TD_i). HaID_i value is the hash value of ID_i used for identifying or addressing the tag. TD_i is used to link the previous-session record and the current-session record each other in order to synchronize the tag and the database in case of incompletion of the current session. As the reader tries to query the tag with a random number$$R$$, the tag emits a hash value $$\beta =h(I{D}_i)$$and the left-half hash value$${\alpha }_L=f_L(h(I{D}_i\left|\right|R))$$. If the reader is legal, it can ask the back-end database server to use $$\beta =h(I{D}_i)$$ identifying the tag. Then the back-end database server’s response is the right-half hash value$${\alpha }_R=f_R(h(I{D}_i\left|\right|R))$$. After the tag receives the correct right-half hash value $${\alpha }_R$$ from the reader,the tag’s information can be accessed by the reader.

Figure 19.

LCAP scheme

In this scheme, the tag’s identity $$I{D}_i$$ is refreshed simultaneously by the tag and the back-end database server after each successful access. It seems to make the tag’s response message $$\beta =h(I{D}_i)$$ not predictable to prevent the tracing of individual. However, the design of “dynamic” identity not really guarantees the location privacy. Fig. 20 shows the use-case diagram of this scheme’s weaknesses. Gildas Avoine and Philippe Oechslim had described an attack based on refreshment avoidance (Lee et al., 2005). In the attack, an adversary always makes a tag unable to refresh its identity and hence can trace the tag. For example, the adversary interrogates all tags with the same number R to get the response message $$\beta =h(I{D}_i)$$ and the left-half hash value $${\alpha }_L=f_L(h(I{D}_i\left|\right|R))$$ for collecting to its own database. As the target tag’s hash value $$\beta =h(I{D}_i)$$ once again collected, the adversary immediately realizes the target tag appeared.

Figure 20.

The attack on LCAP

3.4. Tree-based approach

In the tree-based approach, each tag is not just assigned with a single key but associated with a unique leaf node. In fact, a sequence of keys from the root to the leaf node are defined for the associated tag. The tag’s authentication response is performed by the sequence of keys such that it can be identified by the reader using a breadth-first search in the key tree. Based on the logarithmic complexity of tree-based key search, the tree-based identification is efficient to support a large scale system. (Bringer et al., 2008; Dimitriou, 2006; Lu et al., 2007; Molnar & Wagner, 2004; Molnar et al., 2005; Wang et al., 2007; Yeh et al., 2008)

3.4.1. Dimitriou’s tree-based tag identification scheme

Dimitriou (2006) proposed a tree-based tag identification scheme (Dimitriou, 2006). Each edge is defined with a secret value$$Ke{y}_i$$. $$Ke{y}_i$$in the path from the root to the leaf node are hereby distributed to this tag. If the tree depth is$$d$$, each tag contains $$d$$ keys. Fig. 21 shows a binary key tree with eight tags. For example, $$T_4$$has keys$$k_4^1$$, $$k_4^2$$and$$k_4^3$$.

Figure 21.

A binary key tree with eight tags

Figure 22.

Dimitriou’s tree-based tag identification scheme

The procedure of Dimitriou’s tree-based tag identification scheme is shown in Fig. 22. As the reader tries to query the tag with a random number$$N_R$$, the tag generates a random number $$N_T$$ and computes the message ($$f^1$$,$$f^2$$ , …,$$f^d$$) by all its keys. The back-end database server has to find out the keys in the trees from the root to the leaf node for identifying the tag. If the path exists, the back-end database server regards the tag as a valid tag.

In this scheme, tag searching using the idea of the tree walking algorithm is efficient for the reader. However, it may not be afforded for low-cost tags without enough computing capability to generate the responses by the sequence of keys in a transaction.

3.4.2. Wang et al.’s tree-based authentication scheme

Wang et al.’s (2007) proposed a Storage-Aware Private Authentication protocol (SAPA) (Wang et al, 2007). This scheme uses a sparse tree structure to organize keys of all tags. In the tree, only the root and the leaf node store a key. Each tag $$T_i$$ is arranged to a leaf node and has a key triple ($$k_h$$,$$k_m$$ ,$$k_r$$).$$k_h$$, is the key assigned to the root. $$k_r$$is the key assigned to the leaf node. $$k_m$$represents the path from the root to the leaf node which is expressed in 0 and 1. For example fig.23 shows a sparse binary tree of three levels, the key triple ($$k_h$$, $$k_m^2$$and$$k_r^2$$) is assigned to$$T_2$$.

Figure 23.

A sparse binary tree of three levels

The procedure of Wang et al.’s tree-based authentication scheme is shown in Fig. 24. As the reader tries to query the tag with a random number$$r_1$$, the tag generates a random number $$r_2$$ and computes a sequence of hash chains ($$M_0$$,$$M_1$$ , …,$$M_l$$ ,$$M_i$$). Then the back-end database server first verifies the message $$M_0$$ to authenticate the tag. After, the back-end database server performs a recursive algorithm to identify the tag through the path.

Figure 24.

Wang et al.’s tree-based authentication scheme

In this scheme, both the tag and the back-end database server update key triple ($$k_h$$,$$k_m\text{'}$$ ,$$k_r\text{'}$$) for each successful authentication. It may cause a collision for the new path $$k_m\text{'}$$ assigned to the tag. The asynchronous attack may happen as the adversary blocks $$\Delta$$ sent back to the tag. These drawbacks cause the scheme impractical.

3.5. Chen et al.’s indefinite-indexed approach

Chen et al. (2011) proposed the indefinite-indexed access control scheme (Chen et al., 2011), shown in Fig.25. As a tag is issued by the back-end database server, the$$inde{x}_i$$, $$Ke{y}_i$$and a square matrix $$\omega$$ are stored in the tag. The tag’s serial number $$inde{x}_i$$ is specified as a pair of values $$(x_i,y_i)$$ which can also be regarded as a coordinate. For the purpose of keeping the tag’s location private, the serial number cannot be emitted directly. Infinite possibilities exist to select two un-parallel lines crossed on the coordinate. If the tag is allowed to freely determine the two un-parallel lines, it means $$inde{x}_i$$ can be represented randomly. The first line can be determined by the tag’s serial number $$(x_i,y_i)$$ and any point$$(x_1,y_1)$$. Then the second point $$(x_2,y_2)$$ can be randomly selected on this line. Later, the other two points $$(x_3,y_3)$$ and $$(x_4,y_4)$$ can also be determined similarly. The values of these four coordinates will be re-arranged into a matrix $$\pi$$ and performs the matrix product $$\pi \cdot \omega$$ as the response for the reader. Therefore, only the back-end database server holds the inverse matrix of $$\omega$$ can obtain the matrix $$\pi$$ and figure out the tag’s serial number.

Figure 25.

Chen’s indefinite-indexed access control scheme

The motivation of this scheme is to make the tag’s response message not predictable to prevent the tracing of individual. In other word, the tag’s response message in each access cannot be recognized it is emitted by the same tag. In this scheme, the tag’s serial number is regarded as a coordinate. Infinite possibilities exist to select two un-parallel lines crossed on the coordinate. Therefore, the tag’s serial number can be represented differently in each access and not useful to identify the tag. Moreover, the other messages emitted between the tag and the reader are also randomized and not useful to trace the tag. Therefore, the tag’s location privacy can be guaranteed. In addition, this scheme also guarantees mutual authentication and resists the man-in-the-middle attack, the spoofed reader attack, and the spoofed tag attack.

4. Conclusions

Modern RFID systems are creating a new era of ubiquitous information society. It allows almost everything to be uniquely numbered by embedding a RFID tag. Then the process automation efficiency and usability could be improved (Chang, 2005; Garfinkel et al., 2005). It allows objects to be scanned and identified without the need for visual or physical contact. However, due to the powerful tracking capability of RFID tag, it poses a potentially widespread threat to consumer privacy (McCullagh, 2003). In the world of RFID tags widespread deployment, anyone with an RFID reader can potentially discover individuals’ informational preferences without their permission.

Without access control, anyone can read the information stored on current generation RFID tags. The static unique identifiers stored on tags can be traced for linking the tagged items to the individuals who carry the item. Therefore, security and privacy in RFID systems are an important aspect that needs particular attention. Current researches in RFID technology not just concentrate on the identification scheme. Secure and efficient authentication and access control mechanisms have received much attention in the proposed researches. This article examines the main privacy concerns: information leakage of a tag, traceability of the person and impersonation of a tag. The impersonation problem is always the first one to be analyzed and solved in each scheme. Otherwise, the adversary can collect the information sent by the tag and the adversary can try a spoofing or replay attack to impersonate a target tag. For further consideration, the disclosure of information arising during a transmission of data possibly reveals various personal details without awareness of the holder. Most of the proposed schemes were well designed to prevent the problem of tag’s information leakage. However, most of the proposed schemes can not really avoid the problem of traceability. The adversary may try to distinguish whether the response is transmitted by the target tag or not. Once a link is established between the response and the target tag, the adversary can monitor the person’s location. For those schemes analyzed in this article, state diagram and use-case diagram are used to figure out the schemes’ weaknesses. Through this way, the security requirements in RFID applications can be clearly understood to know which mechanism actually brings which feature. We expect it is more beneficial those researchers as just devoting to the RFID security studies.