Protecting Rfid Communications In Supply Chains

Protecting RFID Communications in Supply Chains Yingjiu Li

Xuhua Ding

School of Information Systems Singapore Management University 80 Stamford Road, Singapore 178902

School of Information Systems Singapore Management University 80 Stamford Road, Singapore 178902

[email protected]

[email protected]

ABSTRACT Recent years have seen much growing attention on RFID security. However, little work has been performed to address the security issues in the context of supply chain management, which is exactly the major field for RFID applications. Existing RFID solutions cannot be applied directly in this field because of a set of special RFID security requirements to be addressed for supply chain management. The major contribution of this paper is to identify the unique set of security requirements in supply chains and to propose a practical design of RFID communication protocols that satisfy the security requirements.

Categories and Subject Descriptors H.4.2 [Information Systems Applications]: Types of Systems— Logistics

Keywords Supply chain, RFID, information security

1.

INTRODUCTION

Motivation Adopting RFID technology is an emerging trend in supply chain management. In fact, one of the major motivations for developing RFID techniques is to improve the efficiency in supply chain management due to its strong and expanding market. As forecasted by Frost & Sullivan, the total worldwide supply chain management market is expected to grow by 11.2 percent per year, reaching $9,668.7 million in 20101 . Several major retail chains including Albertsons, Target, and WalMart have requested all their suppliers to adopt RFID; meanwhile, the Department of Defense in the United States has ordered that all shipments to its armed forces be equipped with RFID tags. With RFID technology, product information can be efficiently collected, tracked, shared, and managed in a real time manner. This helps reduce the overall cost of supply 1 Supply Chain Management: Strengthening the Weakest Link! By Sathyajit Rao. In Frost & Sullivan, http://www.frost.com/prod/servlet/market-insighttop.pag?docid=10709461

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ASIACCS’07, March 20-22, 2007, Singapore. Copyright 2007 ACM 1-59593-574-6/07/0003 ...$5.00.

234

chain management and benefits all involved parties. RFID tags are thus considered as the 21st century replacement for the Universal Product Code bar codes developed in 1970s. Like a double-edged sword, RFID technology has also triggered significant security concerns. For example, an industry espionage may eavesdrop wireless RFID communications to collect inventory information; tag spoofing/cloning may cause significant loss to supply chain partners. As RFID enabled supply chains will likely soon become ubiquitous, it is crucial to mitigate the security concerns in a cost-effective manner without downgrading the efficiency of supply chain management due to the deployment of RFID technology. In this paper, we focus on how to protect RFID communications in supply chain environments. Our work is complementary to the rigorous efforts that have been made in RFID related cryptography and security research [7, 18], including tag killing, tag blocking, storing encrypted information in tags, using tag passwords or pseudonyms, distance-sensitive tag reading, and policy making. The previous work primarily investigates the privacy issues related to individual customers or the security issues related to a single reader-tag channel. Little work has been conducted to address the security issues in supply chain applications, which however represent the major driving force behind the commercial deployment of RFID technology. As indicated below, supply chain applications impose a different set of security requirements and thus deserve a new treatment to protect RFID communications. Previous work The security and privacy concerns posed by RFID technology can be roughly classified into corporate data security, which primarily affects corporations and organizations inside supply chains, and personal privacy, which primarily affects individual customers outside supply chains [7]. Typical existing schemes include: (i) tag killing [20], in which tags of sold items are disabled or removed at the point-of-sale, (ii) tag blocking [11], in which a blocker tag creates an radio frequency environment that prevents unauthorized scanning of consumer items, (iii) encryption [9, 8, 1], in which the information stored in tags is encrypted in a dynamic manner, (iv) using passwords [22], in which a tag responses to a reader only if it receives the right password, (v) using pseudonyms [9], in which each tag is associated with a set of pseudonyms and cycles through them each time it is read, (vi) distance-sensitive tag reading [5], in which the tag changes its behavior according to the distance to its reader, and (vii) policy making [6], in which guiding principles for RFID system creation and deployment are stipulated. The privacy and security aspects of RFID systems have also been investigated in the context of libraries [17], banknotes [10, 8], and recent theoretical development [20, 4, 16, 12, 2, 24, 19] . Most of these schemes focus on addressing the privacy concerns related to individual customers or the security concerns related to single reader-tag channel. Little attention has been paid to ad-

dressing the corporate data security issues within a supply chain domain. In the design of practical solutions for secure RFID communications in supply chains, special cares are needed to take into account supply chain structure information, interactions between supply chain partners, and supply chain visibility etc. For instance, in supply chain applications, one cannot assume that an RFID tag shares a secret key with all RFID readers as the tagged item (or pallet) is processed by readers belonging to different partners following the material flow. Because of this, existing RFID solutions cannot be applied directly to address the corporate data security issues in supply chain scenarios. Our contribution We extend the previous efforts by considering the entire information process in supply chain management. Our contributions are mainly twofold. First, we spell out four security requirements in applying RFID tags in supply chains: authoritative access, authenticity of tags, unlinkability and supply chain visibility. Note that though some of them inherit their security notions from generalized RFID applications, they show new implications under the supply chain context. Second, we propose a holistic RFID framework including RFID read and write protocols. Our scheme is practical and meets all the aforementioned challenges. Paper organization The rest of this paper is organized as follows. In Section 2, we briefly describe the technical background for RFID enabled supply chains and identify the security challenges. In Section 3, we propose our protocols for secure supply chain RFID communications. In Section 4, we analyze the security and performance issues on our proposed system. Finally, Section 5 concludes this paper.

2.

BACKGROUND

A typical RFID enabled supply chain is illustrated in Figure 1. In this figure, supply chain partners A and B are connected via the Internet. To reduce the cost of RFID tags, bulky data about product details is stored in backend databases and accessible through the Internet. Only minimum amount of information such as product IDs and light-weight security primitives is stored in RFID tags. The RFID tags are attached to containers, pallets, and/or items. On the arrival of a material flow, a supply chain partner uses RFID readers to collect product information from RFID tags via a wireless communication channel. The collected information is then sent to the so-called savant computers for further interpretation and process. Meanwhile, a supply chain information flow can take place between supply chain partners through Internet connections. Supply chain partner A

Savant computers

Supply chain partner B

Internet connection

RFID readers

Savant computers

RFID readers

Material flow RFID tags

RFID tags

Figure 1: RFID enabled supply chain RFID Tag An RFID tag is a wireless transmitter attached to an object. A tag usually consists of a tiny microchip, to store data

235

and perform logical operations, and a coiled antenna, to communicate with RFID readers via radio frequency signals through nonconducting material. RFID tags can store a 64-bit or more unique code. Typical RFID coding schemes include the Electronic Product Code (EPC) that is developed in MIT Auto-ID center [20] for unique identification of all physical objects. The EPC code in a tag indicates the owner, type, and serial number of the item to which the tag is attached. The code serves as a pointer which can be used to obtain more detailed information about the item from the Internet. Based on its capability for write operations, RFID tags can be read-only, write-once read-many, or fully rewritable. Low-cost passive RFID tags are of primary interests in RFID-based system applications. Unfortunately, due to their miserable computation resource, it is infeasible to incorporate into such tags any public key primitives, even standard symmetric key encryption/decryption algorithms (e.g., AES). To secure RFID communications, various light-weight security protocols have been designed, where mostly hash functions and XOR operations are involved. In this paper, we consider fully rewritable passive RFID tags. RFID Reader An RFID reader is used to read and write tag data via wireless interactions, and to connect with back-end data processing systems via wired connections. Compared with tags, the costs of readers are less restrictive. RFID readers can be equipped with more internal storage and processing power. Various anticollision methods (e.g., binary tree walking and Aloha scheme) are developed to support effective and efficient communications between multiple readers and multiple tags at the same time [20]. There are two communication channels between readers and tags. The reader-to-tag channel, a.k.a. forward channel, is broadcast based and delivers strong signals which can be captured from a long distance, perhaps 100 meters. On the other hand, the tag-to-reader channel, a.k.a. backward channel, is a much weaker one which can only be received within short ranges, for example, several meters for low-cost passive tags. Data Processing Sub-System A data processing sub-system consists of (i) a network of savant computers that collect data from distributed RFID readers, (ii) back-end databases that contain detailed information about the tagged items (e.g., product information, tracking log, and key management data), and (iii) management and control components that facilitate information flow and supply chain applications. Due to extreme scarcity of RFID tags’ computation resource, typical data processing sub-system such as the Savant System [20] shifts most of the load from tags to readers and servant computers. Supply Chain Structure While Figure 1 illustrates a sectional view of two interacting partners within an exemplary supply chain system, a panoramic view on supply chains may have four different structures: third-party logistics (3PL), vendor managed inventory (VMI), collaborative planning, forecasting, and replenishment (CPFR), and supply network (SN). These structures are defined based on the collaboration relationships among supply chain partners. In brief, 3PL enables companies to concentrate on their core competencies and outsource shipping to other parties. In VMI, the vendors take over the replenishment planning tasks for their trading partners. CPFR is a collaborative arrangement of multiple parties for real-time sharing of demand and supply data. SN is similar to CPFR, however with more complex collaborative processes and more ad hoc information flows. For each supply chain structure, a different set of data objects (e.g., inventory management, product information, order management, production management, service and support, and supply chain plan) are required to be shared among supply chain partners. The reader is referred to [13] for more details about information sharing in different supply chain

structures.

3.

2.1

In this section, we propose a secure RFID communication framework in a supply chain environment.

Security Requirements for RFID Applications in Supply Chains

Common security requirements of RFID tags include untraceability, confidentiality, etc, as discussed in existing RFID literatures. Nonetheless, applying RFID tags in supply chain environments introduces a unique set of parameters. Therefore, some of the generalized RFID security properties are bestowed with new implications. Moreover, supply chain applications also bring in their unique security challenges. In the following, we list those security requirements under the supply chain context. • AUTHORITATIVE ACCESS : It means that the RFID tags in a shipment to partner Pi are only accessible by authorized readers of partners Pi . In other words, only legitimate readers are allowed to identify and update the tags. Note that Pi−1 has the ability to read the tags as well since Pi−1 is the deliverer of the shipment to Pi . • AUTHENTICITY OF TAGS : It means that in a supply chain link from Pi−1 to Pi , only legitimate RFID tags delivered by Pi−1 will be accepted by Pi ’s readers. This is crucial for a supply chain partner since it ensures that only the expected flows are accepted and processed accordingly. • U NLINKABILITY: For a partner in a supply chain, a rogue RFID reader may interrogate a tag in its inbound material flow and another tag in its outbound material flow. Unlinability ensures that it is infeasible for the rogue reader to determine by observing both responses whether both its interrogations are upon the same tag. Note that unlinkability is a weaker variant of untraceability, which is an important requirement for RFID-based applications due to the fact that RFID tags can be probed unwittingly from a distance. In its traditional sense, untraceability requires that (i) an unauthorized reader cannot obtain a valid tag’s identity from its reply, and (ii) an unauthorized reader cannot link any two replies to the same tag; that is, it cannot distinguish between any two replies from the same tag (probed at different times) and any two replies from two different tags. However, in a supply chain environment, the global structure of the supply chain is of more security concerns. A correlation of inbound flow and outbound flow reveals critical information of a supply chain, whereas tracking tags within an isolated flow poses little threat since no personal privacy is involved2 . • S UPPLY C HAIN V ISIBILITY: It has twofold implications: (1)The manager of the supply chain is able to track the RFID tags; (2) At any phase of the material flow, the manager of the supply chain is able to open RFID tags and identify the last partner who has processed them. It is a critical common requirement to enable visibility in supply chain management. The most attractive feature of RFID techniques in supply chain is its enhancement on supply chain visibility. It allows companies to track and monitor the progress of material flow without inefficient bar code scanning. Any secure RFID protocol in supply chains must maintain supply chain visibility. 2

Note that the unlinkability is required within supply chains while the untraceability should be enforced outside of supply chains (after customers buy tagged products).

236

OUR SOLUTION

3.1

System Model

We consider a supply chain consisting of N partners, denoted by P1 , P2 , · · · , PN . Each partner is independently managed by her own organization. They may or may not trust each other. A partner or a collusion of some of them, may attempt to mount attacks on the RFID system in order to achieve certain malicious goals. A material flow of items is equipped with RFID tags. It originates from P1 and is shipped along the supply chain in the sequence of P1 , P2 , · · · , Pi , Pi+1 , · · · , PN . When the flow arrives at Pi , Pi is required to read and update all RFID tags. We assume that every partner has limited knowledge of her local neighborhood in the whole supply chain. Namely, for all 1 ≤ i < N , partner Pi is aware of her subsequent peer Pi+1 and for all 1 < i ≤ N , Pi is aware of her preceding peer Pi−1 . Nonetheless, we do not assume, nor require that a partner has the global information of the entire supply chain. We do not consider physical attacks to legitimate readers, tags, or tag-item attachment. Existing technical or management solutions to thwart such attacks [21] are essentially complementary to our solution. While we do not exclude the possibility that RFID readers and/or tagged items can be in the possession of some attackers, we assume that the attackers cannot access the stored secrets by breaking into RFID readers or tags, though they can probe, monitor, replay, or analyze the wireless communications between readers and tags. We also assume that attackers cannot detach RFID tags from their attached items without physically destroying the functionality of tags and items. We do not address possible denial of service to legitimate readers (as in most RFID security and privacy papers3 ). Such attacks can be easily detected by legitimate readers. Since the sources of such attacks must be situated in an area physically close to the victim readers, detected attacks can be thwarted by inspecting the area and removing the attack sources.

3.2

System Setup

For every partner Pi , let Sigi (m) denote a public key signature generated by Pi on message m, and Enci (m) denote a public key encryption under Pi ’s public key on message m. (Note that Pi may have different public key pairs for signatures and encryption.) Let l be the maximum length of RFID tags’ serial numbers. For ∀ i > 1, Pi selects a secret key ki ∈R {0, 1}l and sends Enci−1 (ki , Sigi (ki )) to its upstream partner Pi−1 . In this way, Pi securely sends his secret key ki to Pi−1 with non-repudiation. Pi−1 accepts the key if the signature is verified true under Pi ’s signature public key. Moreover, a strong collision resistant hash function H(·) : {0, 1}∗ → {0, 1}l is selected for all partners. H(·) digests an any-bit long binary string into an l-bit long binary string. RFID Tag Initialization P1 is responsible for RFID tag initialization. The data pertaining to an RFID tag includes a serial number and an access key: • Tag Serial Number (C): A globally unique number that serves as the identity of the tag. • Access Key (K): A l-bit secret key shared with the assigned RFID readers. 3 Some RFID solutions such as blocker tags [11] actually utilize the denial of service to protect consumer’s privacy, preventing RFID tags from being read by any (rogue) readers beyond the point-ofsale.

Instead of storing both C and K, a pseudonym α, which is an XOR result of C and K, i.e., α = C ⊕K, is stored in the tag. The format of the content of RFID tag is the following: Tag Pseudonym (α) Table 1: The Format of RFID Tags P1 initializes an RFID tag as follows. She first determines the tag serial number, c, according to the item which this tag is supposed to attach to. She then assigns k2 as the access key, Finally, she writes c ⊕ k2 into the tag. Database Initialization Each Pi maintains a database Di in her local storage. Each tuple in the database corresponds to a tag. Di contains all RFID information with respect to the said shipment. Specifically, Di has the following structure, where n is the number of tags for the current shipment: • Tag Serial Number (C) : the same as defined in last paragraph. • Tag Secret Mask (R): a secret random number used for tag authentication. • Tag Response (T ): the response (to be) received from the corresponding RFID tag. • Pointer: An octet string containing an address where the business information relevant to the tag is stored. An alternative approach is to store information in this field directly. Obviously, it trades the storage cost for communication efficiency. • Status (S): a binary bit. ’s=1’ means that the corresponding RFID tag has been processed; otherwise, ’s=0’. Throughout the paper, we call an entry is unmarked if its status is not set as 1. For convenience, the j-th entry in the database, (cj , rj , tj , pj , sj ), is denoted by dj . Di is represented by {d1 , d2 , · · · , dn }. Initially, Di is empty. To process the incoming material flow, Pi , 1 < i ≤ N , either receives or downloads all serial numbers and pointers of Di−1 from Pi−1 through a secure communication channel. Pi sets all sj = 0, 1 ≤ j ≤ n. All other fields are initially empty. Note that Pi and Pi−1 share a secret key ki . Therefore, a secure communication channel is easily established in a standard fashion. Since P1 is the originator of the supply chain, she initializes her D1 after setting up RFID tags described previously.

3.3

RFID Read/Write Protocol

RFID tags are read and written by RFID readers under each partner’s management. The read and write operations of RFID readers need the support from the back-end servant computers. Since the communications between readers and servant computers can be easily protected by standard encryption and authentication techniques, we do not discuss its relevant security issues in this paper. We show below how an RFID reader of partner Pi interacts with an RFID tag using Read/Write protocols (see illustrations in Figure 2). Without loss of generality, let the tag’s serial number be c, access key be k and its stored value be α. Read Protocol The ultimate goal of Read protocol for Pi ’s reader is to extract a tag’s serial number and retrieve its corresponding record from the database. In practice, an RFID reader usually interacts with multiple RFID tags in a batch. We leave the discussion of batch process

237

in Section 4. Our Read protocol described below only shows the interaction between one tag and a reader. Step 1: Reader → Tag: The reader selects a non-zero nonce r ∈R {0, 1}l and sends it to the tag. Step 2: Tag → Reader: If r = 0, Abort. Otherwise, the tag computes t = H(r ⊕ α) and sends t back to the reader as the response. Step 3: Identification by Reader: The reader executes Algorithm 1 to identify the engaged tag. Algorithm 1 RFID Identification Input:database Di = {d1 , d2 , · · · , dn }, tag’s reply t, nonce r, key ki Procedure: 1: for every entry dj = (cj , rj , tj , pj , sj ) in Di , 1 ≤ j ≤ n do 2: if sj = 0 then 3: rj ← r 4: tj ← H(cj ⊕ rj ⊕ ki ) 5: end if 6: end for 7: Search an entry dz ∈ {di |si = 0}, such that tz = t. 8: if dz is found then 9: sz ← 1 and the tag in read is accepted. 10: else 11: Abort, the identification of the tag fails. 12: end if

Note that if the tag is a legitimate one, its access key k is the same as Pi ’s key ki , i.e. k = ki . The basic idea of Algorithm 1 in Step 3 is similar to a dictionary attack on a password file with salts. Using the nonce r, the reader computes all possible responses for all unmarked tags in the database Di . Then, the reader searches t from her computation results. If no match is found, the reader aborts the transaction since it is unable to identify this tag. Otherwise, the reader retrieves from the database Di the entry (c, m, t, p, s) and sets s = 1. From the pointer in this record, Pi is able to locate relevant information with respect to this RFID tag. Write Protocol The write process is to update a tag’s access key so that it can be accessed securely by the authorized readers of the next partner Pi+1 . Moreover, it helps to resist tracing attacks. In essence, the reader of Pi writes ki+1 to an RFID tag. The protocol is as follows: Step 1: Reader → Tag The reader computes a = ki ⊕ ki+1 and b = H(a ⊕ c ⊕ ki ). It sends (a, b) to the tag. Step 2: Verification by Tag On receiving (a, b) from the reader, the tag authenticates the reader by checking whether b = H(a⊕α). If so, it updates α by computing α = a ⊕ α; Otherwise, the tag rejects the write command. In the write command, b is essentially an authenticator for a. It passes the tag’s verification provided that the reader has the knowledge of both the tag’s serial number c and it access key k. Note that a tag’s content α is never released to any reader. Therefore, to update a tag, the reader must successfully identify the tag.

4.

ANALYSIS

In this section, we analyze our scheme with respect to the security requirements posed by supply chain management as discussed in Section 2.

4.1

Authoritative Access to RFID tags

Ideally, RFID applications would allow an RFID tag to authenticate a reader which attempts to read or write it. Since RFID read protocol is time-critical especially in batch process mode, the standard shared-key based authentication protocols cost undesirable delay. In our solution shown in Section 3, the tag responses

Tag Serial Number (C) c1 .. . cn

Tag Secret Mask (R) r1 .. . rn

Tag Response (T ) t1 .. . tn

Pointer p1 .. . pn

Status s1 .. . sn

Table 2: The structural definition of database Di database

reader

Di: C,R,T,Pointer, Status

H(),

memory

tag



H(),





Access Key ki, ki+1 1) query: r t=H(r

2) reply: t


 )

Find c from Di Search Dk for a single record (c, r, t,p,s) such that t=H(r c ki) If not found, the tag is unidentified Otherwise update the tag in step 3) 3) update: a=ki

ki+1, b=H(a

c

ki)

Check if b = H(




a)

If no, the reader is unidentified Otherwise update



with




a

Figure 2: Protocol for RFID communications in supply chains to any query without explicit authentication. Nonetheless, only authorized readers are able to interpret the responses and extract their identities whereas a malicious reader obtains no meaningful information from its interrogation. With such an implicit authentication approach, we minimize RFID tags’ response time without compromising security. In Write protocol, our solution is similar to HMAC [3] which authenticates the source of the write command. We summarize the security with respect to authoritative access in the following statement. S TATEMENT 4.1. Consider an RFID tag delivered by partner Pi−1 to partner Pi . Only Pi ’s reader is able to read the tag’s serial number. Furthermore, only Pi ’s reader is able to write to this tag. (Proof Sketch) On any read challenge r, the tag responses with t = H(r ⊕ α). Since α = k ⊕ c, therefore t = H(r ⊕ k ⊕ c). It is straightforward to observe that only with knowledge k can a reader compute tag serial number c such that it satisfies t = H(r ⊕ k ⊕ c). Before delivering an RFID tag to Pi , Pi−1 has updated the tag’s access key with k = ki , where ki is Pi ’s secret key. Thus, Pi is able to locate c. Moreover, a secure hash function is one-way. Namely, no polynomial-time bounded entity is able to derive its pre-image r ⊕ α from t. Thus, an unauthorized reader is unable to acquire any significant information of the tag’s identity c. In the write command (a, b), b is in fact an authenticator of a, in the same manner as using HMAC, where c ⊕ k is the shared key

238

between Pi ’s reader and the tag. Due to the weak collision resistance of hash function H, only with the knowledge of c and k, can the reader compute b = H(a ⊕ c ⊕ k). It implies that the originator of (a, b) is in possession of the matching key ki . Therefore, only commands from the authorized reader can be accepted by the tag. 2 Note that Pi−1 can read/write a tag shipped to Pi as well, since ki is shared between Pi−1 and Pi . This imposes no risk since Pi−1 has processed all tags. Before the material flow arrives at Pi , Pi−1 is still involved. However, immediately after Pi updates RFID tags, Pi−1 ’s privilege to read/write becomes invalid.

4.2

Authenticity of Tags

The use of nonce in Read protocol is to thwart tag cloning attacks [7]. If no nonce is used in the protocol, it is vulnerable to cloning and replay attacks. A rogue reader can easily probe a valid tag, and then clones this tag by copying its received response to tags at her disposal. Note that a supply chain’s reader is unable to distinguish the original tag and a cloned malicious tag. Such failures cause financial losses. The authenticity of tags in our protocol is summarized in the following statement. S TATEMENT 4.2. Given a nonce r, it is computationally infeasible for an adversary, without the knowledge of ki , to find a pair of serial number c and valid response t, such that t = H(r ⊕ c ⊕ ki ).

(Proof Sketch) This is obvious, as providing (c, t) satisfying the hash equation without knowledge of ki is equivalent to the reverse of the hash function. In fact, the adversary is even unable to find (α, t) satisfying t = H(r⊕α). Thus, for a randomly chosen nonce, no faked tag will be accepted by the reader. 2 However, the use of nonce for tag authentication is at the cost of higher computation complexity on the reader’s side. In the worst case, the reader needs to conduct n hashing computations, O(n log n) sorting operations, and lognn! comparisons for reaching a tag. This complexity is naturally high even though all the necessary computations are executed by the reader (including the Savant computer). To reduce the complexity of authentication to a practical level without sacrificing much anti-cloning capability, a fresh nonce can be used for authenticating a batch of multiple tags, instead of a single tag. The total n tags are partitioned into m batches such that all the tagged items in the same batch share the same nonce and are processed concurrently. Different batches have their own unique fresh nonce. Such an approach conforms with supply chain practice where tagged items often arrived together and are processed in batches. For simplicity, we assume that each batch consists of n/m tags. Before the arrival of a batch of tagged items, the RFID reader will (i) update the unmarked records in its database with a fresh nonce r, i.e. to set tj = H(r ⊕ ki ⊕ cj ) for each unmarked tag cj , and (ii) sort the unmarked records according to the updated hash values. This process is called batch pre-processing, which happens before reader interacting with each tag in a batch. The batch preprocessing takes maximum n (minimum n/m) hashing computations and O(n log n) (minimum O(n/m log n/m)) sorting operations for processing the first batch (last batch) of tags. In section 4.5, we will illustrate that the time cost for batch pre-processing is sufficiently low even for an unrealistically large number n. Upon the arrival of a batch of tagged items, the RFID reader will (i) initiate Read protocol with the same nonce r for interrogating all tags in the batch in parallel, and (ii) verify each tag’s response against the unmarked records in its updated and sorted database. This process is called real-time searching. For simplicity, we assume that the binary search is used in the searching process4 . The complexity of authenticating each tag in this process is given below. S TATEMENT 4.3. To authenticate and read n tags processed in m batches, a legitimate reader on average needs to conduct log n! = O(log n) comparisons per tag. n (Proof Sketch) With the updated and sorted database, the reader will authenticates all n/m tags in the first batch by verifying each tag’s reply against the unmarked database records and marking the matched record. This requires log n + log(n − 1) + . . . + log(n − n/m + 1) comparisons in binary search. Similar to the first batch, it requires log(n − n/m) + log(n − n/m − 1) + . . . + log(n − 2n/m + 1) comparisons for the second batch (if any). In the end, the last batch demands log n/m + log(n/m − 1) + . . . + log 1 comparisons. Overall, the reader needs to conduct log n + log(n − 1) + . . . + log 1 = log n! comparisons. On average, it requires lognn! =

into m sets of records corresponding to m batches. The batch preprocessing and real-time searching can always be performed over m records for all batches. In this case, the batch pre-processing will n incur n/m hashing computations and O(n/m log n/m) sorting operations. The average complexity of authenticating each tag in real-time searching is reduced to m/n log(n/m)! = O(log n/m) matching operations. Balancing Security and Performance Though batch process reduces the reader’s cost, it opens a window for clone or replay attacks. To clone a tag that has not been read by the legitimate reader, the attacker can use his own reader and the intercepted nonce to probe the tag and replay the tag’s reply to the legitimate reader (while the corresponding tagged item can be removed, say, by the attacker). Note that it is not that meaningful to spoof those tags that have already been read, as the corresponding database records have been marked. Also note that the cloning attack is only effective within the targeted batch, as the nonces for other batches are different. Therefore, the parameter m can be chosen for balancing the efficiency of tag authentication and the resistance to tag cloning attacks. The smaller the parameter m, the fewer hash computations are needed while the longer the time window for batch authentication. Consequently, an attacker has more time to intercept/eavesdrop the nonce and to clone one or more tags in the said batch. In supply chain practice, the tagged items in the same batch usually arrive at their processing site at the same time. When the first tag starts to interact with a legitimate reader, all other tagged items in the same batch should be in a position close enough to the reader such that the cloning attack is not easy to launch. It is even more difficult for an attacker to remove a tagged item in this scenario. Without removing the tagged item, a cloning attack can be easily detected even if the attack is successfully launched; the detection can be performed based on the fact that the same tag will be read more than one time.

4.3

Unlinkability and Supply Chain Visibility

Unlinkability and supply chain visibility defined in Section 2 seem to contradict to each other. The key to solve the apparent dilemma is to differentiate two types of RFID readers: legitimate readers of supply chain partners and unauthorized readers of nonpartners (e.g., in industry espionage). While the supply chain partners are trusted and should be provided with supply chain visibility, unauthorized readers should be prevented from understanding any tag’s content and from tracking the movement of material flow. S TATEMENT 4.4. Given a response t1 from a tag prior to being processed by partner Pi and a response t2 from a tag after being process by Pi , it is infeasible for a rogue reader to determine whether t1 and t2 are from the same tag. In other words, the tags are unlinkable for unauthorized readers.

n O( log(n n e ) ) = O(log n + log − 1) = O(log n) com2n parisons per tag authentication. 2 We observe that in some supply chain applications, partner Pi may have prior knowledge of the range of serial numbers of a batch of tags in delivery. In those cases, database Di can be partitioned

(Proof Sketch) Note that the attack may choose the same nonce for both interrogations. Without loss of generality, let t1 = H(r ⊕ c1 ⊕ k) and t2 = H(r ⊕ c2 ⊕ k0 ), where k 6= k0 , and c1 , c2 are the serial numbers of the tags. The challenge for the adversary is to determine whether c1 = c2 . It is infeasible for the adversary to make a successful guess due to the following: t2 = H(r ⊕ c1 ⊕ (c1 ⊕ c2 ⊕ k0 )). Therefore, without the knowledge of k, k 0 , no reader is able to link two responses. 2 With Statement 4.4, we further have the following two Corollaries.

4 More efficient searching can be achieved using complex index structures [17].

C OROLLARY 4.5. Without knowledge of the access key, no reader is able to obtain a tag’s identity.

n+1/2 −n

239

(Proof Sketch) It is trivial. Otherwise, the reader can link two tags, which contradicts with Statement 4.4. 2 C OROLLARY 4.6. Without knowledge of the access key, no reader is able to determine whether two tags belong to the same material flow, i.e., using the same access key. (Proof Sketch) It can be proved in the same manner as for Statement 4.4. 2 C AVEAT We highlight that unlinkability in supply chain context is different from in the traditional context, which requires no linkage between any two read operations. It is obvious that our protocol does not provide unlinkability of the latter notion, which is a stronger than the first one. We argue that it is not a security compromise, since the latter notion is usually demanded when user personal privacy is under threat, which is not applicable for supply chains. In supply chain systems, it is of more importance to protect the privacy of the supply chain structure. Therefore, we consider implementing the stronger unlinkability as an unnecessary cost for supply chain systems. While rogue readers are prevented from tracking tags across supply chain links, authorized reader are allowed to do so as required by supply chain visibility. To achieve this objective, a simple solution is to involve a trusted authority, called as supply chain visibility authority (VA). It resides in the data processing sub-system and is responsible for tracking the movement of material flow, implementing access control, and handling tracking-related queries (among other essential services). During the setup phase, each partner Pi , 1 ≤ i ≤ n − 1, sends (ki+1 , Sigi+1 (ki+1 )) to VA so that VA’s RFID readers have all the access keys. With possession of all access keys, VA’s authoritative readers are able to identify an RFID tag at any stage in its material flow. Note that once VA successfully identifies a tag with an access key, it also identifies the current partner processing the tags since only this partner has the corresponding access key. In addition, whenever a batch of tagged items have been successfully processed at a supply chain partner’s site, typical tracking information related to this batch including the tag serial numbers, pointers, statuses, time, and location are reported to VA, which processes the information and makes it available for authorized parties to query. Therefore, VA is able to maintain supply chain visibility by interrogating RFID tags and checking its database.

4.4

Eavesdropper and Insider Attacks

Previous discussions only consider the interrogation of a rogue reader upon RFID tags. Now, we consider whether the proposed RFID Read and Write protocols are subject to eavesdropping attacks. A passive adversary is able to sniff all the communications between a reader and RFID tags provided she is equipped with a capable antenna. Although a partner may enforce the physical security of its premise so that no sniffer is within its radio range, an analysis of the protocols is still desirable. For Read protocol, an eavesdropper has less advantage than a rogue reader which interrogate the tag by itself, since the nonce used in the protocol is simply a random number with no secret information. Therefore, Read protocol is secure against eavesdroppers. For Write protocol5 , an eavesdropper within Pi ’s vicinity obtains a = ki ⊕ ki+1 and a number of authenticators of a for individual tags. We observe that a is exactly a one-time pad encryption [15] 5

Note that the tag initialization by P1 should be executed in a physically secure environment so that no rogue readers and eavesdroppers are unable to mount attacks.

240

of ki+1 or ki . Without the knowledge of either one of the key, the adversary is unable to acquire even one bit information of the other key. Therefore, Write protocol is secure against external eavesdroppers. Unfortunately, under the supply chain context, we have to consider malicious partners, which could be Pi−1 with the knowledge of ki . If Pi−1 eavesdrops Write protocol executions at Pi ’s site, it can easily derive the new access key ki+1 . Consequently, Pi−1 can impersonate Pi+1 to read or write those tags that have been updated by Pi . Further, Pi−1 is able to steal all access keys in downstream supply chain by repeating such attacks. Alternatively, a dishonest partner’s reader may interrogate all tags and figures out the access key by exhaustively guessing all tags’ serial numbers. This is one of those notorious insider attacks. We argue that Pi−1 gains little from this attack under certain circumstances. First, Pi−1 has already read those tags successfully at her site; there is no value for her to read them again. Second, Pi−1 is a legitimate supply chain partner; in some supply chain settings all partners are entitled to know the structure of the entire chain. Therefore, tracking tags along the material flow does not provide additional knowledge to Pi−1 under certain circumstances. In cases that every partner is only allowed to know her upstream and downstream peers, the aforementioned insider attack should be prevented. An approach is to introduce a trust third party (TTP) which helps to establish a secret shared key between the current partner and tags. In specific, each tag has a unique secret key shared with the TTP. This key is used as a seed to generate session keys between the tag and a partner with the help of TTP. Obviously, it is not efficient. We leave as an open question how to design efficient protocols secure against insider attacks.

4.5

Performance Analysis

A wide adoption of RFID technology in supply chains demands Read/Write protocol not only to be secure, but to be efficient and practical. We analyze our proposed protocols by evaluating its storage cost and computation cost. An RFID tag in our system only stores α = c ⊕ k, which has the same size of its serial number. Since a tag at least has a permanent storage for its serial number, our protocol does not incur extra cost. Note that a tag still needs other memory space for computation and communication. Since our computation only includes XOR operation and hash functions, the required memory space is rather limited. The computation load of tags in our protocols is also remarkably light-weight. A tag needs only one hash function and one XOR operation both for Read and Write protocols. In Read protocol, the RFID reader takes much of the computation load, whereby it locates the tag’s information by exhaustive search. We argue that a reader may comprise a full-fledged computer with sufficient memory storage and computing power. We estimate the time cost for the reader’s pre-processing and real-time searching as follows. In our estimation, we suppose that the length of the tag’s serial number is 128-bit, i.e., l = 128. According to [14], it takes a hash function, e.g. SHA-1, 210 CPU cycles of a Pentium CPU to digest a 128bit message. Based on the experiments conducted in [23], we roughly estimate that it costs about 40 CPU cycles per sort operation for merge-sort or quick-sort algorithms, though the actual data varies with many factors including CPU cache, compiler, memory etc. Consider a material flow with n tags in one or multiple batches. It requires at maximum 40 log n CPU cycles to search a tag, and 210n + 40n log n cycles to prepare the database for each batch. To be conservative, we estimate the time cost in the case where a 1-GHz Pentium machine is used in

the data processing system and n = 220 (which is much larger than the number of tags in most practical material flows). The required time for real-time searching is only about 800ns, which is negligible compared to the communication delay. Note that in practice the throughput for a high speed RFID reader is only around 100 tags per second. On the other hand, its pre-processing time per batch needs about 1.06s, including about 220ms for hashing computations and about 840ms for sorting the database. This cost is also negligible since the time gap between processing batches is usually in seconds or even minutes.

[15]

5.

[17]

CONCLUSION

In this paper, we study the security issues of using RFID tags in supply chain models. Under the supply chain context, we first identify a set of security requirements including authoritative access, authenticity of tags, unlinkability and supply chain visibility. An RFID system comprising both a read and a write protocol is proposed. Our analysis shows that the proposed solution satisfies the aforementioned security requirements with affordable computation and storage cost imposed on RFID tags. Our solution represents a valuable first step toward more advanced solutions for protecting RFID communications in supply chains.

6.

[14]

[16]

[18]

[19]

[20]

REFERENCES

[1] G. Ateniese, J. Camenisch, and B. de Medeiros. Untraceable rfid tags via insubvertible encryption. In ACM Conference on Computer and Communications Security, pages 92–101, 2005. [2] G. Avoine and P. Oechslin. Rfid traceability: A multilayer problem. In Financial Cryptography, pages 125–140, 2005. [3] M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. In Crypto’96, pages 1–15. [4] S. C. Bono, M. Green, A. Stubblefield, A. Juels, A. D. Rubin, and M. Szydlo. Security analysis of a cryptographically-enabled RFID device. In USENIX Security Symposium, pages 1–16, 2005. [5] K. P. Fishkin and S. Roy. Enhancing RFID privacy via antenna energy analysis. tech. memo IRS-TR-03-012, Intel Research Seattle, 2003. [6] S. Garfinkel. An RFID bill of rights. Technology Review, page 35, October 2002. [7] S. L. Garfinkel, A. Juels, and R. Pappu. RFID privacy: An overview of problems and proposed solutions. IEEE Security & Privacy, 3(3):34–43, 2005. [8] P. Golle, M. Jakobsson, A. Juels, and P. F. Syverson. Universal re-encryption for mixnets. In CT-RSA, pages 163–178, 2004. [9] A. Juels. Minimalist cryptography for low-cost RFID tags. In SCN, pages 149–164, 2004. [10] A. Juels and R. Pappu. Squealing Euros: Privacy protection in RFID-enabled banknotes. In Financial Cryptography, pages 103–121, 2003. [11] A. Juels, R. L. Rivest, and M. Szydlo. The blocker tag: selective blocking of RFID tags for consumer privacy. In ACM Conference on Computer and Communications Security, pages 103–111, 2003. [12] A. Juels, P. Syverson, and D. Bailey. High-power proxies for enhancing rfid privacy and utility. In Privacy Enhancing Technologies, pages 210–226, 2005. [13] E. Liu and A. Kumar. Leveraging information sharing to increase supply chain configurability. In Twenty-Fourth

241

[21]

[22]

[23]

[24]

International Conference on Information Systems, pages 523–537, 2003. D. Menasce. Security performance. IEEE Internet Computing, pages 84–87, May 2003. A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of applied cryptography. CRC Press, 1997. ISBN 0-8493-8523-7. D. Molnar, A. Soppera, and D. Wagner. A scalable, delegatable pseudonym protocol enabling ownership transfer of RFID tags. In Selected Areas in Cryptography, pages 276–290, 2005. D. Molnar and D. Wagner. Privacy and security in library RFID: issues, practices, and architectures. In ACM Conference on Computer and Communications Security, pages 210–219, 2004. M. Ohkubo, K. Suzuki, and S. Kinoshita. RFID privacy issues and technical challenges. ACM Communications, 48(9):66–71, 2005. M. R. Rieback, B. Crispo, and A. S. Tanenbaum. Rfid guardian: A battery-powered mobile device for rfid privacy management. In ACISP, pages 184–194, 2005. S. Sarma, S. Weis, and D. Engels. White paper: RFID systems, security and privacy implications. Technical Report MIT-AUTOID-WH-014, Auto-ID Center, MIT, November 2002. S. Weigart. Physical security devices for computer subsystems: A survey of attacks and defences. In Workshop on Cryptographic Hardware and Embedded Systems, pages 302–317, 2000. S. A. Weis, S. E. Sarma, R. L. Rivest, and D. W. Engels. Security and privacy aspects of low-cost radio frequency identification systems. In SPC, pages 201–212, 2003. L. Xiao, X. Zhang, and S. A. Kubricht. Improving memory performance of sorting algorithms. ACM Journal of Experimental Algorithmics, 5(3), 2000. X. Zhang and B. King. Integrity improvements to an rfid privacy protection protocol for anti-counterfeiting. In ISC, pages 474–481, 2005.