Proxy device for enhanced privacy in an RFID system

RELATED APPLICATIONS(s)

p-0002The present application claims the priority of U.S. Provisional Patent Application Ser. No. 60/591,981, filed Jul. 29, 2004 and entitled “High-Power Proxies for Enhancing RFID Privacy,” the disclosure of which is incorporated by reference herein.

p-0003The present application is also related to U.S. patent application Ser. No. 10/782,309, filed Feb. 19, 2004 and entitled “Low-Complexity Cryptographic Techniques For Use With Radio Frequency Identification Devices,” U.S. patent application Ser. No. 10/673,540, filed Sep. 29, 2003 and entitled “Method And Apparatus For Selective Blocking Of Radio Frequency Identification Devices,” and U.S. patent application Ser. No. 10/915,189, filed Aug. 10, 2004 and entitled “Radio Frequency Identification System With Privacy Policy Implementation Based On Device Classification,” which are commonly assigned herewith and incorporated by reference herein.

FIELD OF THE INVENTION

p-0004The present invention relates generally to systems comprising radio frequency identification (RFID) tags or other types of RFID devices, and more particularly to techniques for enhancing user privacy in such systems.

BACKGROUND OF THE INVENTION

p-0005A conventional RFID tag typically comprises an integrated circuit transceiver capable of transmitting a unique serial number or other identifying information to a nearby reader in response to a query from the reader. Many RFID tags are “passive” in that they do not include a battery or other power source, but instead obtain the power necessary to operate from the query signal itself.

p-0006Ongoing RFID tag development efforts have led to significant cost and size reductions, which should result in a rapid proliferation of RFID tags into many new areas of use. For example, RFID tags are expected to replace printed barcodes in consumer product applications. The Electronic Product Code (EPC) tag is a form of RFID device that is emerging as a successor to the printed barcode. EPC tags are an evolving standard under development by an organization called EPCglobal, a joint venture between the UCC and EAN, the organizations that oversee barcode standards in the U.S. and Europe, respectively. An EPC is the form of identifier that an individual EPC tag emits as prescribed by the EPCglobal standard. An EPC includes not just the information contained in a conventional printed barcode, namely the manufacturer and type of a particular product, but also a unique serial number. Additional details can be found in the current version of the EPCglobal standard document, “EPC™ Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz,” Version 1.0.8, 2005.

p-0007The unique serial number of an EPC tag associated with an object can serve as a pointer to a database entry containing a detailed history of the object. Thanks to the features of automated scanning and unique identification, RFID systems promise fine-grained tracking of inventory on an unprecedented scale.

p-0008Unfortunately, such capabilities also introduce a strong potential for various forms of privacy infringement, such as invasive physical tracking and inventorying of individuals. Similar threats are posed to the privacy of corporate data.

p-0009Conventional approaches, such as the use of “kill” control codes (e.g., identification numbers or PINs) to deactivate tags or the use of Faraday cages to shield tags from readers, fail to protect user privacy in a manner which retains the full benefits of the tags in a variety of environments. Other approaches involve the use of sophisticated cryptographic functionality that is incompatible with the limited computation and memory resources of EPC tags and other simple RFID devices.

p-0010Illustrative embodiments of the inventions disclosed in the above-cited U.S. patent application Ser. Nos. 10/782,309, 10/673,540 and 10/915,189 address the above-noted problems of conventional practice through techniques referred to as minimalist cryptography, selective blocking and soft blocking, respectively. Despite the considerable advantages provided by these techniques, a need remains for further improvements in the form of additional techniques capable of preserving user privacy in RFID device applications.

SUMMARY OF THE INVENTION

p-0011The present invention in accordance with one aspect thereof provides techniques for enhancing user privacy in an RFID system. The RFID system generally includes a plurality of RFID devices and at least one reader which communicates with one or more of the RFID devices. The system further includes at least one proxy device. The proxy device acquires information characterizing at least a given one of the RFID devices, controls the given RFID device so as to at least partially prevent the given RFID device from being read by the reader, and communicates with the reader in a manner which simulates the given RFID device. This advantageously allows the proxy device to implement privacy policies of arbitrary sophistication on behalf of the given RFID device. The proxy device subsequently releases control of the given RFID device so as to permit the given RFID device to again be read by the reader.

p-0012In an illustrative embodiment of the invention, the information characterizing the given RFID device comprises at least an identifier of that device. The proxy device may acquire the identifier by, for example, reading the given RFID device in substantially the same manner that the reader would read the given RFID device. Alternatively, the proxy device may acquire the identifier from the reader, or it may be provided by the given RFID device upon authentication of the proxy device to the given RFID device.

p-0013The given RFID device may be controlled by relabeling it with a new identifier. Such relabeling may therefore involve, for example, altering its current identifier as stored therein. More particularly, the identifier may be altered by replacing it with a pseudonym generated by the proxy device. The proxy device could assign different pseudonyms for different timeslots to the given RFID device. Such pseudonyms could be generated uniformly at random by the proxy device, or as symmetric-key ciphertexts based on a master key held by the proxy device, or using other techniques.

p-0014In other embodiments, the identifier may be altered by the given RFID device responsive to input received from the proxy device. For example, the given RFID device may generate a new identifier responsive to an update command received from the proxy device. More specifically, the given RFID device may generate the new identifier as a pseudonym determined using a counter maintained in the given RFID device. As another example, the pseudonym may be generated in the proxy device at least in part as a function of input information obtained from the given RFID device. In such an arrangement, the pseudonym may be accepted by the given RFID device only upon confirmation by the given RFID device that the pseudonym was generated using the input information.

p-0015As indicated above, a proxy device can implement privacy policies of arbitrary sophistication that would otherwise be difficult or highly impractical to implement in conventional RFID systems. For example, policies involving robust cryptographic authentication algorithms, release of RFID device information only when the RFID device is in particular geographic locations, or release of RFID device information for an RFID device not actually carried by a corresponding user, can be easily implemented using a proxy device configured in accordance with the present invention.

p-0016These and other features and advantages of the present invention will become more readily apparent from the accompanying drawings and the following detailed description.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idrefs="DRAWINGS">FIG. 1</figref> is a simplified block diagram of an exemplary RFID system in which the present invention is implemented in one embodiment.

<figref idrefs="DRAWINGS">FIG. 2</figref> illustrates one possible implementation of a proxy device of the <figref idrefs="DRAWINGS">FIG. 1</figref> system.

<figref idrefs="DRAWINGS">FIG. 3</figref> is a flow diagram showing the operation of a proxy device of the <figref idrefs="DRAWINGS">FIG. 1</figref> system in an illustrative embodiment of the invention.

DETAILED DESCRIPTION

p-0020The present invention will be described herein with reference to an exemplary RFID system in which multiple RFID devices communicate with an RFID device reader. It is to be appreciated, however, that the invention is not restricted to use in this or any other particular RFID system configuration.

p-0021The term “RFID device” as used herein is intended to include an RFID tag or any other type of device configurable for transmission of device-identifying information via radio frequency communications. Although the following description will refer primarily to EPC tags, it is to be understood that the techniques disclosed are applicable to other types of RFID tags, and more generally applicable to other types of RFID devices. Also, the terms “radio frequency” or “RF” as used herein are not intended to be restricted to any particular frequency range, but are instead intended to be construed more generally so as to encompass any contiguous or non-contiguous arrangement of one or more signal frequencies suitable for supporting wireless communication between at least one device and at least one reader.

p-0022As described in the above-cited U.S. patent application Ser. No. 10/915,189, a given RFID device in an illustrative embodiment of the invention may have one or more of a number of different classifications. For example, the given RFID device may be classified as one of public, private, blocker, unblocker, etc. The classification of the given RFID device may be dynamic, that is, it can vary over time. Also, it is possible for a given RFID device to have multiple classifications at the same time, depending upon the particular set of classifications in use. The present invention, however, does not require the use of these or any other RFID device classification techniques.

p-0023The device-identifying information associated with a given RFID device may be an EPC, a serial number or any other type of identifier. It should be noted that not every identifier in a given set of unique identifiers need have a corresponding realized device.

p-0024The term “identifier” as used herein is intended to include a pseudonym of the type described in the above-cited U.S. patent application Ser. No. 10/782,309. In addition, an identifier is intended to include any information suitable for providing an indication of a classification of a particular RFID device.

p-0025The term “reader” as used herein is intended to include any type of device capable of interacting with an RFID tag or other device so as to receive device-identifying information therefrom.

h-00071. Example of an RFID System

p-0026<figref idrefs="DRAWINGS">FIG. 1</figref> shows an RFID system <b>100</b> in which the present invention is implemented. The system <b>100</b> includes a number N of RFID tags <b>102</b>, more particularly denoted by their associated tag identifiers T₁, T₂, . . . T_N, and an RFID reader <b>104</b>. The tags <b>102</b> may comprise EPCglobal Class-1 Generation-2 UHF tags or other types of EPC tags, or more generally other types of RFID devices. The reader <b>104</b> communicates with the tags <b>102</b> and receives identifying information therefrom, in the form of one or more transmitted identifiers. The reader <b>104</b> is coupled via a network <b>106</b> to servers denoted <b>108</b>, <b>110</b>.

p-0027The system <b>100</b> further comprises a proxy device <b>120</b>. The proxy device <b>120</b>, an example of which is referred to herein as an RFID enhancer proxy (REP), communicates with one or more of the RFID tags <b>102</b> and with the reader <b>104</b>. Although shown in <figref idrefs="DRAWINGS">FIG. 1</figref> as communicating with only tag T_N, the proxy device <b>120</b> can more generally be configured to communicate with any desired grouping of one or more of the tags in system <b>100</b>. The operation of the proxy device <b>120</b> will be further described below in conjunction with <figref idrefs="DRAWINGS">FIGS. 2 and 3</figref>. Generally, proxy device <b>120</b> acquires identifiers or other information characterizing at least a given one of the RFID tags <b>102</b>, and controls the given tag so as to at least partially prevent that tag from being read by the reader. As will be noted elsewhere herein, the term “controls” in this context is intended to be construed broadly, so as to encompass a wide variety of arrangements in which the proxy device interferes with the normal operation of the tag. While controlling the given tag, the proxy device itself communicates with the reader, in a manner that simulates the presence of the given tag but enforces a desired privacy policy. The proxy device subsequently releases control of the given tag, thereby permitting the tag to be read by the reader in a normal manner.

p-0028<figref idrefs="DRAWINGS">FIG. 2</figref> shows one possible implementation of the proxy device <b>120</b> of the <figref idrefs="DRAWINGS">FIG. 1</figref> system. The proxy device <b>120</b> in this implementation includes a processing block <b>200</b>, comprising a processor <b>202</b> coupled to a memory <b>204</b>, an RF transceiver <b>210</b>, and an antenna <b>212</b>. One or more of these elements may be implemented in whole or in part as a conventional microprocessor, digital signal processor, application-specific integrated circuit (ASIC) or other type of circuitry, as well as portions or combinations of such circuitry elements. Software programs for controlling the operation of the proxy device <b>120</b> may be stored in the memory <b>204</b> and executed by the processor <b>202</b>.

p-0029<figref idrefs="DRAWINGS">FIG. 3</figref> shows a flow diagram <b>300</b> which outlines the operation of proxy device <b>120</b> in the illustrative embodiment.

p-0030In step <b>302</b>, the proxy device <b>120</b> acquires tag information, such as an EPC or other tag identifier, for at least one tag. For example, the proxy device <b>120</b> may acquire such information by communicating with a particular tag, such as tag T_Nas shown in <figref idrefs="DRAWINGS">FIG. 1</figref>. Alternatively, such information may be communicated to the proxy device through other channels.

p-0031In step <b>304</b>, the proxy device controls the tag so as to prevent the tag from being read by the reader <b>104</b>, and possibly any additional readers of the system. As will be described in greater detail below, this step may involve, for example, the proxy device temporarily altering the tag identifier or otherwise preventing the tag from communicating in its normal mode of operation with the reader(s). It should be noted that this step may be implemented such that the reader is prevented from reading only a portion of the full readable information contained in the tag. Such an arrangement is an example of one in which a tag is controlled so as to “at least partially prevent” that tag from being read by a reader. Another example may include an arrangement in which the proxy device intercepts reader queries to protected tags, using an approach referred to herein as “block-and-simulate.” These and other arrangements are considered to be within the broad scope of the terms “controls” or “controlling” as applied to a given tag or other RFID device.

p-0032In step <b>306</b>, the proxy device <b>120</b> simulates the tag in interaction with the reader(s). This advantageously allows implementation of arbitrary privacy policies on behalf of the proxy user. The proxy device in the illustrative embodiment is assumed to have significantly more processing power than a typical tag, and therefore can implement sophisticated privacy policies involving, for example, cryptographic authentication functionality, on behalf of one or more tags owned by an associated user.

p-0033In step <b>308</b>, the proxy device <b>120</b> releases the tag so as to permit the tag to resume its normal operation.

p-0034More detailed examples of the operation of proxy device <b>120</b> will be described in the REP description of Section 2 below.

p-0035It should be noted that the proxy device <b>120</b> need not take on a particular physical form, and can instead be implemented as any type of processing device, including, for example, a mobile telephone, a personal digital assistant (PDA), a mobile email device, a portable computer, a hardware-based authentication token such as an RSA SecurID® token commercially available from RSA Security Inc. of Bedford, Mass., U.S.A., or any other type of processing device. Such processing devices can be readily configured to operate as proxy devices in accordance with the invention.

p-0036The proxy device <b>120</b> in this illustrative embodiment communicates with the tags <b>102</b> and the reader <b>104</b> using the same RF communication protocols used for conventional tag-to-reader and reader-to-tag communication. It is to be appreciated, however, that the proxy device can be configured to support a wide variety of other types of protocols, in any combination. For example, the proxy device may include wireless network interface capability, using protocols such as IEEE 802.11, Bluetooth, GSM, UMTS, etc. The proxy device may therefore provide a bridge between system <b>100</b> and external wireless networks not shown.

p-0037A given RFID tag <b>102</b> in system <b>100</b> generally includes circuitry comprising memory, processing logic and an RF transceiver. These elements may be configured in a manner similar to that used in conventional RFID tags.

p-0038One or more of the tags <b>102</b> may each comprise a so-called “blocker tag” configured with an ability to block the operation of a singulation algorithm utilized by the reader <b>104</b> in order to provide enhanced privacy for a user of the tag, as described in the above-cited U.S. patent application Ser. No. 10/673,540. The present invention, however, does not require the use of such blocker tags.

p-0039One or more of the tags <b>102</b> may also or alternatively implement minimalist cryptography, soft blocking, or other techniques described in the above-cited U.S. patent application Ser. Nos. 10/782,309 and 10/915,189. Again, the present invention does not require the use of such techniques.

p-0040The network <b>106</b> may represent a global computer network such as the Internet, a wide area network (WAN), a local area network (LAN), a satellite network, a telephone or cable network, or various portions or combinations of these and other types of networks. The servers <b>108</b>, <b>110</b> may be conventional processor-based information processing devices of a type conventionally utilized in conjunction with RFID readers in an RFID system.

p-0041The particular number N of tags <b>102</b> in the system <b>100</b> is purely arbitrary, and the system can be configured to support any desired number of tags. Also, although only a single reader <b>104</b> is shown in the figure for simplicity and clarity of illustration, the system will typically include multiple readers. Furthermore, it should be noted that a given reader need not be connected to a network, and may instead operate as a stand-alone device, or may be only intermittently connected to the network. Also, a given reader can be directly connected to a server or other system element, rather than connected thereto over a network as illustrated in the example system <b>100</b>.

p-0042A typical RFID reader is generally only able to communicate with a single RFID tag at a time. In effect, however, the reader may be viewed as broadcasting a query to all of the tags <b>102</b> at once. If more than one tag responds to a query by the reader, the reader detects a collision and executes a singulation algorithm which allows the reader to communicate with the conflicting tags one at a time.

p-0043Conventional RFID tag systems may operate at a frequency of, for example, either 13.56 MHz or 915 MHz, and may utilize, for example, ALOHA-type singulation algorithms or tree-walking singulation algorithms. Other frequencies, such as 125 kHz and 2.45 GHz, are also used, and employ similar singulation algorithms. Such singulation algorithms are known in the art, and will therefore not be further described herein. The invention can be utilized with a reader incorporating one of these known singulation algorithms, or a reader incorporating another type of singulation algorithm, or any other type of reader, including a reader that does not singulate tags. Thus, it is to be appreciated that the invention does not require the use of singulation.

p-0044As indicated above, one particular embodiment of a proxy device such as device <b>102</b> is referred to herein as a REP. In Section 2 below, the operation of the REP is described in further detail. The REP and its associated functionality as described herein should not be viewed as requirements of the invention, but are instead presented by way of example. Numerous alternative proxy device configurations will be apparent to those skilled in the art from the teachings provided herein.

h-00082. RFID Enhancer Proxy (REP)

p-0045As indicated previously, the REP is an example of what is more generally referred to herein as a proxy device. Briefly stated, a REP assumes the identities of tags and simulates them by proxy. By merit of its greater computing power, the REP can enforce more sophisticated privacy policies than those available in tags. As a side benefit, it can also provide more flexible and reliable communications in RFID systems.

p-0046An important advantage of the REP of this embodiment is that it is a trusted device, and therefore is not vulnerable to attacks involving malicious exchange of data between RFID tags. Vulnerability to such an attack is a significant drawback associated with the conventional personal re-encryption devices disclosed in P. Golle et al., “Universal re-encryption for mixnets,” T. Okamoto, editor, RSA Conference-Cryptographers' Track (CT-RSA), pp. 163-178, Springer-Verlag, 2004.

p-0047The REP assumes the identities of RFID tags under its control. In particular, it loads their identifying information and then simulates the tags in the presence of one or more readers in order to enforce a privacy policy on behalf of the REP owner. Suitable privacy policies may include, for example, a requirement for the reader and the REP to participate in an authentication protocol more sophisticated than that which an ordinary tag implements. When a given tag is no longer to be simulated by a REP, the tag may reassume its identity and operate in a conventional manner.

p-0048For consumer applications, it will often be desirable for the REP to continually rewrite the identifiers transmitted by tags under its control. The REP may, for example, write ciphertexts or random pseudonyms to tags. Such an approach is similar to approaches described in the above-cited P. Golle et al. reference, and in A. Juels et al., “Squealing Euros: Privacy protection in RFID-enabled banknotes,” Financial Cryptography '03, pp. 103-121, Springer-Verlag, 2003, LNCS No. 2742. These references propose re-encryption of ciphertexts on tag identifiers by computationally powerful and potentially untrusted external computing devices. In contrast to these proposals for tag re-encryption, however, we consider the REP as a trusted personal device. This advantageously removes the need for a reliance on public-key cryptography, as will be described in greater detail below.

p-0049The REP in the illustrative embodiment performs the following operations:

p-00501. Tag Acquisition. By way of example, when the owner of a REP and RFID tag wishes the REP to simulate the tag, the REP acquires all of the necessary tag information and places the tag in a state permitting the REP to act as its proxy. The main technical challenge occurs when the tag has associated secrets, like PINs for access control or “killing” that must be transferred securely.

p-00512. Tag Relabeling. The REP changes the identifiers on tags in its control so as to prevent surveillance of these tags. Relabeling introduces various integrity problems, particularly the need to prevent adversarial re-writing of tags. This illustrative embodiment uses a simple technique for preventing an adversary from swapping the identities of two different tags, e.g., swapping the identifiers on two medications with differing dosages. As previously indicated, the personal re-encryption device of the above-cited Golle et al. reference is vulnerable to this type of attack. The approach described in the above-cited A. Juels et al. reference uses special physical prevention mechanisms to address this type of attack. The technique of this illustrative embodiment, which involves random input from the tag in the creation of pseudonyms, works even when tags do not have access-control features. As one possible alternative, tags could instead be put in a “sleep” mode, as will be described in Section 2.5 below.

p-00523. Tag Simulation. The REP simulates tags in interaction with readers. The REP may also simulate spurious tags to prevent leakage of information about the number of tags carried by its owner. As a REP is assumed to be a powerful device, it can enforce any privacy policy desired by its owner. A wide variety of suitable privacy policies would be readily apparent to those skilled in the art, and accordingly are not described in detail herein. Examples include robust public-key based authentication schemes.

p-00534. Tag Release. When the owner of a REP wishes it no longer to simulate a tag, the REP releases its control and reconfigures the tag to a normal mode of operation.

p-0054It should be noted that blocker tags as described in the above-cited U.S. patent application Ser. Nos. 10/673,540 and 10/915,189 can serve as alternatives to REPs for consumer privacy protection. REPs, however, have a number of features that make them an attractive alternative to blocker tags. For example, if a conventional tag temporarily exits the broadcast range of a blocker tag, the former is subject to complete compromise. By contrast, a conventional tag under the control of a REP will merely go without an identity change during this period. As another example, blocker tags are typically most effective as a standard implemented on both tags and readers, while a REP requires only tag-based support, and can be compatible with any type of reader. However, it is to be appreciated that a blocker tag may be configured to implement REP functionality as described herein, and a REP may be configured to implement blocker tag functionality.

p-0055A REP in this illustrative embodiment thus functions as a proxy for one or more RFID tags. As such, it is able to simulate these tags and therefore enforce privacy policies of arbitrary sophistication. Additionally, and quite importantly for many applications, a REP, which is assumed to be a device having significant computation and memory resources, can serve as a much more reliable interface for transmitting RFID data than an RFID tag. Stated more generally, a REP can serve as a more trustworthy conduit for RFID data than the tags it controls. This can be particularly valuable in, e.g., environments in which there are physical impediments to RFID scanning. Metals and liquids can both interfere with RFID scanning, for instance; manufacturers have already confronted challenges in scanning such items as cans of drinking soda. The REP alleviates such problems.

p-0056The above-listed operations of the REP, namely, tag acquisition, tag relabeling, tag simulation and tag release, will now be described in greater detail. It should be understood that this particular set of operations, and the details thereof as outlined below, are merely illustrative examples associated with one particular embodiment of a proxy device in accordance with the invention. Other embodiments may implement only a subset of these operations, use additional or alternative operations, and so on.

h-00092.1 Tag Acquisition

p-0057Acquisition of a tag by a REP involves transfer of a complete set of tag data, which typically comprises at least the tag identifier. For tags that simply broadcast identifiers and other public information, this is a straightforward matter in that the REP need merely scan the tag. Where it becomes more complicated is when a tag has associated secrets, particularly PINs required to implement secure tag operations such as writing and “killing.” The transfer of these data may take place, for example, in the following ways:

p-00581. The tag data may be transferred directly to the REP from a trusted higher powered device such as a reader. In all cases, care should be taken of course to protect the privacy and integrity of data during this transfer. At checkout from a shop, for example, private data associated with the tags on purchased products might be communicated by the checkout register directly to the REP via, e.g., a Bluetooth link. In a supply chain, before shipment to a supply-chain partner, a pallet of tagged items might itself be tagged with a REP. The REP is programmed with private data about the tags in its pallet from a reader. This data transfer may take place using the RFID data transport or another physical layer such as Bluetooth, ZigBee, or IrDA.

p-00592. The tag data may be released by the tag on suitable out-of-band authentication of the REP to the tag, or this data transfer may take place in an environment with adequate compensating controls. There are several channels by which the RFID reader might authenticate itself to the tag as a trusted device. If tags bear printed keys, then optical scanning of these keys might serve this function. A more convenient alternative might be release of tag data upon physical contact or proximity between the REP and the tag in accordance with the “resurrecting duckling” paradigm of F. Stajano et al., “The resurrecting duckling: Security issues for ad-hoc wireless networks,” 7th International Workshop on Security Protocols, pp. 172-194, Springer-Verlag, 1999, LNCS No. 1796. Indeed, researchers have demonstrated methods by which tags may be able to ascertain roughly whether a reader is in close proximity. See, for example, K. P. Fishkin et al., “Some methods for privacy in RFID communication,” 1st European Workshop on Security in Ad-Hoc and Sensor Networks (ESAS 2004), pp. 42-53, 2004.

h-00102.2 Tag Relabeling

p-0060As explained above, relabeling of tags by the REP protects against privacy compromise that may result through direct tag scanning. One way to accomplish this is to have the REP re-encrypt a public-key ciphertext carried by a tag, using re-encryption techniques such as those described in the above-cited P. Golle et al. reference. This illustrative embodiment, however, in which the REP serves as a proxy, permits a simpler approach involving the assignment of changing pseudonyms to tags. In particular, for timeslot t, the REP can assign a k-bit pseudonym p_t,ito tag i. Time here would be maintained by the REP alone, assuming it is infeasible for simple tags to keep time. This pseudonym may be generated uniformly at random by the REP and stored in a table in association with the tag identity. Alternatively, it could be computed as a k-bit symmetric-key ciphertext based on a master key a held by the REP. For example, the pseudonym could be computed as p_t,i=E_σ[t,i].

p-0061The approach of re-encryption or more generally, relabeling of tags, however, introduces a serious security problem, that of data integrity. Because tags in the illustrative embodiment are assumed to be computationally too weak to authenticate re-writing entities, it is hard to enforce write-control permissions on tags that preclude adversarial tampering. This means that an attacker can corrupt tag data.

p-0062Writing of tag data is typically a PIN-protected process in RFID tags. This mitigates the risk of malicious corruption of tag data, but does not eliminate it. An adversary can potentially intercept REP-to-tag communications and thus learn the write PIN for the tag. Alternatively, if attacking at sufficiently close range, the adversary can hijack a write session between the REP and tag. However, provided that k is sufficiently large, i.e., pseudonyms are long enough, an attacker has very little chance of being able to forge a pseudonym.

p-0063More serious is the possibility of a swapping attack, in which an adversary exchanges the ciphertexts p_t,iand p_t,jbetween two tags i and j. This can have very serious consequences. It suffices to consider the possibility of an attacker exchanging ciphertexts associated with two medications or two spare aircraft parts. Conventional techniques involving re-encryption of ciphertexts, such as those described in the above-cited P. Golle et al. reference, have been unable to address this attack, and have indeed left its resolution as an open problem.

p-0064In the case where the PIN associated with a tag is locked, i.e., not subject to alteration, the PIN itself can serve as a kind of authenticator for the tag. Authentication techniques of this type are disclosed in U.S. patent application Ser. No. 11/191,633, filed Jul. 28, 2005 and entitled “Methods and Apparatus for RFID Device Authentication,” which is incorporated by reference herein. Thus, a PIN can be used as a mechanism to defend against swapping attacks, in that if a tag is discovered to carry a pseudonym that does not match its PIN, then it may be presumed that a swapping attack has occurred.

p-0065There are a number of problems associated with the use of PINs to defend against swapping attacks. First, a frequently-used PIN is subject to compromise, and a compromised PIN is effectively a kind of static identifier. An attacker capable of testing the correctness of a PIN can use it to track a tag. Of course, if a PIN is not used to authenticate the operation of identifier-writing, but only to test periodically for swapping, then the risk of PIN compromise is diminished. A second, more serious problem is the basic one of PIN management. We have already noted that tag acquisition may need to involve out-of-band transfer of tag secrets. In general, management of tag PINs is like the general problem of key management in data-security systems. It is conceptually simple, but operationally difficult. Hence, it seems very likely that consumers will carry RFID tags that do not have associated PINs, or will not know the associated PINs of their tags.

p-0066The illustrative embodiment of the invention provides a simple defense against identifier swapping that works even when write access to tags is universal. The idea is for a tag i to participate itself in the generation of a given pseudonym p_t,i. In principle, if the tag itself could perform symmetric-key encryption under an appropriate cipher E, then the data-integrity problem would be solved. The tag would not need to have its pseudonyms updated by the REP. Cryptography of this kind, however, as we have explained, is well beyond the reach of low-cost tag capabilities.

p-0067Tags can, however, generate a certain amount of randomness. Consider a protocol in which a tag generates a new pseudonym p_t,ifor a counter t maintained in the tag. If it receives an “update” command from the REP, along with a valid write key, the tag transmits p_t,ito the reader and adopts p_t,ias its new pseudonym. In order to prevent desynchronization due to an interrupted session, a tag might await a final acknowledgment from the reader before effecting the update. This approach would render swapping attacks infeasible, as the REP, and thus an adversary, would be unable to dictate tag pseudonyms.

p-0068In practice, tags are capable of generating only a limited number of random bits in the course of a given session. Moreover, much of the randomness that a tag generates is already allocated to other protocol requirements. A tag may therefore be unable to generate a full-length random pseudonym in each session.

p-0069Even partial generation of a pseudonym by a tag, however, can help alleviate the risk of swapping attacks. For example, a tag might emit a random nonce r of length k′&lt;k before accepting the writing of a new pseudonym. The tag then only accepts a new pseudonym if it “matches” this nonce, e.g., if the last bits of the pseudonym are equal to r. As an alternative, a tag might simply “declare” the last bits of its pseudonym to be r and accept only the other bits from the reader. In other words, a tag can participate partially in the generation of its pseudonyms. An adversary attempting to swap pseudonyms, then, will be unable to do so unless it can locate a pair of tags simultaneously emitting the same nonces.

p-0070The probability of successful attack by an adversary, then, is a function of the number of tags N managed by a REP, the number of timeslots s available to the adversary for its attack, and the bit-length k′. Consider, for instance, a pallet carrying some 100 tags relabeled every minute, and seeking protection against attacks lasting up to one day (1440 minutes), and employing tags that generate 32-bit nonces. The probability that a given tag shares a random pseudonym with any of the 99 others may be crudely bounded above by 99/2³². Thus the probability of a successful swapping attack in this case is easily seen to be less than (1−(1−99/2³²))×1440&lt;0.000034.

p-0071Even if an attacker cannot successfully initiate a swapping attack, corruption of tag data has a second effect, namely, denial of service. If an attacker is able to implant a pseudonym in a tag, the tag effectively becomes desynchronized with the REP, in that the REP no longer recognizes the tag's pseudonym. If the REP were consequently to halt rotation of new pseudonyms into a tag, a breach of privacy could result, since the tag identifier would remain static. A REP might alert a user to unexpected desynchronization events of this kind by emitting a warning tone, for instance. Alternatively, a REP might continue to relabel tags even if it does not know their true underlying identifiers. The REP can, of course, simply generate temporary identifiers for tags it does not recognize. This might have an undesirable spillover effect if a REP relabels tags that do not belong to its owner.

p-0072A secondary effect of a corruption attack is that the REP cannot properly release tags. If it does not recognize their pseudonyms, it cannot manage them properly. Thus, one of two approaches might be needed for tag restoration: (1) If the REP possesses PINs for the tags in its control, it can try to match tags to PINs via exhaustive search, or (2) Manual intervention on the part of the user might be necessary, e.g., the user might have to key in a printed product code from items that the REP has “lost.” Given the current, and probably persistent imperfections in RFID, we expect some level of back-up identifier recovery and manual intervention to occur regularly. Since denial-of-service attacks would likely be a rarity, anyway, they would probably constitute little more than a nuisance in the system.

p-0073One way to achieve privacy protection of REP-to-tag communications is to have the tag generate a random value R and send it on the tag-to-REP channel. The REP can then protect transmission of a message on the REP-to-tag channel, which is typically higher power than the tag-to-REP channel, as the REP can then transmit the write PIN XORed with R. Techniques such as these can in principle prevent compromise of write PINs for tags via long-range eavesdropping, and thus reduce the overall threat of data corruption. They do not, however, address the problems of short-range eavesdropping and hijacking.

p-0074A stronger approach to data integrity is possible using, for example, the minimalist cryptography of the above-cited U.S. patent Ser. No. 10/782,309 to establish shared secrets between tags and the REP. On top of this might be layered a lightweight message authentication code (MAC). Such a combination of techniques could be used to permit the REP and tag to authenticate new pseudonyms.

h-00112.3 Tag Simulation

p-0075Once the REP has acquired a tag, it can, of course, simulate it as desired in the presence of an RFID reader. As explained above, this has the benefit of making tag reading more reliable. The REP, which is assumed to have greater processor and memory resources than a tag, can transmit information to a reader more reliably than a tag. The REP might essentially enforce the kind of data filtering envisioned in the soft blocking approach described in the above-cited U.S. patent Ser. No. 10/915,189. Soft blocking, however, is implemented in an illustrative embodiment using, e.g., a universal set of policy conventions. A REP, by contrast to such an embodiment, can achieve a wholly personalized set of privacy policies. Additionally, a REP can enforce these policies in the presence of any reader, even a malicious one.

p-0076The following are two examples of REP capabilities that are not provided in conventional approaches.

p-00771. Geographical conditioning. A REP may make decisions about whether to release information based on its geographical location. For example, a REP might release information about a pallet's RFID tags only when the pallet arrives at its destination. There is a variety of channels by which the REP might determine whether or not it is present at its destination, e.g., (1) a built-in GPS unit; (2) authenticated transmissions from readers; or (3) an authenticated notification from another protocol such as Bluetooth.

p-00782. Object simulation. To deceive attackers, a REP may simulate RFID tags associated with objects that the user does not possess. For example, a consumer can “carry” information about an object by simulating it. When the owner of a refrigerator wants to purchase a new handle of the correct type, or the owner of a stereo system wants to know which speakers are appropriate for her home theater system, she can simulate the associated RFID tags in order to acquire, carry, and convey this information conveniently. As another example, the owner of an expensive watch might program her REP to simulate the RFID tag of that watch when she is present in upscale shops (so as to improve her level of customer service), but to mask her expensive watch (or simulate a cheap one) when she is walking the streets.

p-0079There are numerous other scenarios in which a REP can enforce privacy policies. For example, jewelry retailers typically perform nightly inventories of their stock, given the high value of individual items. One can imagine that they would find RFID-tagging of their stock useful in this process. Such tagging, however, would make it possible for a competitor to scan a jewelry case quickly and in secrecy, and thereby learn the rate of stock turnover. A REP might simulate non-existent jewels to render this more difficult. This approach would, similarly, be very useful in military environments.

p-0080Finally, we note that a REP can transmit tag information to devices other than RFID readers. A REP might, for instance, transmit tag data via IEEE 802.11 or other similar protocol, thereby serving as a bridge between an RFID system and other wireless systems.

h-00122.4 Tag Release

p-0081When a REP releases an RFID tag, it typically restores the tag's original identity. This process is straightforward if the REP has unrestricted write access to the tag. The technique described in Section 2.2 above for preventing swapping attacks introduces a problem here, however, as its aim is precisely to restrict the identifiers that may be written to a tag. We propose, therefore, that on release of a tag, the randomly assigned portion of its identifier be retained, and that the rest of its identifier be restored to its original state. For example, the identifier on an EPC tag may be viewed as comprising two segments, namely, a first segment identifying the manufacturer and type of a particular product, and a second segment in the form of a unique serial number. During the period in which a tag is simulated by a REP, the first segment can be effaced or otherwise overwritten by the REP, while the second segment, or a portion thereof, is generated at random by the tag. When the tag is released, the randomness in the second segment is retained, while the first segment is restored. Effectively, then, a tag gets a new serial number at the time it is released.

p-0082This change in the second segment could be problematic in some cases. For example, if a user has a warranty associated with an item that is referenced by its initial serial number, the user would like to retain that serial number. We note, however, that the REP can help provide serial-number translation as desired. For example, if a carton of milk has had its serial number changed through relabeling, the REP can transfer the old serial number to a “smart” refrigerator when a consumer puts the milk away.

p-0083In the case where a tag has an associated PIN, of course, the PIN may be used to place the tag in a special state in which its serial number may be completely rewritten. Alternatively, physical mechanisms like reader proximity, such as that described in the above-cited K. P. Fishkin et al. reference, might be used to trigger tag restoration of its original state.

p-0084An important logistical question is how the REP is to determine when to release a tag. This process may in many cases be controlled by the user or performed automatically based on external environmental cues, e.g., when a user's home network informs the REP that the user has entered her home. Experiments described in the above-cited K. P. Fishkin et al. reference suggest that as tags enter the limit of range of a reading device, their response rate degrades. Based on such information, a REP might be able to detect the removal of a tag from its vicinity and restore its initial state automatically. To achieve early detection of impending tag departure from its read radius, a REP might periodically reduce its power level. The opposite is alternatively possible. For example, release of a tag might be effected by bringing the REP into close proximity or actual physical contact with the tag. This latter case has a useful feature, in that physical proximity is effectively a kind of authentication, and might serve as the basis for full restoration of a tag identifier, thereby bypassing the problem of serial-number-changes discussed above. For library books and similar items, this could be especially useful.

h-00132.5 Putting Tags to Sleep

p-0085In other embodiments, a REP can put tags to sleep while it is simulating them, and then wake them for identity re-implantation, thereby obviating the need for tag relabeling. Such a “sleep” capability is not supported by the EPC Class-1 Generation-2 standard, but could in principle be incorporated into inexpensive tags. The process of waking, however, can be a problematic one. For logical access control, sleep/wake commands should be keyed with PINs so as to prevent malicious alteration of tag behavior. A problem which arises is that unless a tag identifies itself, a reader (or REP) cannot know which waking key to transmit; a sleeping tag cannot, of course, identify itself. Trial-and-error transmission of PINs to tags would be possible, but cumbersome. Alternatively, it is possible for a REP to broadcast a waking PIN to all tags in its vicinity, but given the likely movement of tags in and out of the field of control of the REP over the course of time, this approach seems impractical for consumer applications. This is particularly the case if a REP wishes to transfer control of a tag to a different device, in that the secondary device must be able to identify the tag of which it is taking control.

p-0086Putting tags to sleep might present a more feasible approach to access control if waking involves some form of physical access control. For example, it would be possible to touch an appropriately-configured RFID device to a tag in order to wake it. We expect, however, that it would be cumbersome for consumers to have to engage in a fine-grained physical process to control the state of their tags.

p-0087In supply chains, where rigorous logistical controls are available, sleep/wake patterns may be more manageable. In such settings it may make sense for a REP to put tags to sleep while simulating them.

h-00142.6 REPs and the EPCglobal Standard

p-0088The basic REP approach of this illustrative embodiment works effectively with Class-1 Generation-2 EPC tags in commercial settings, particularly if such tags have writeable identifiers. Many memory technologies such as EEPROM impose limitations on the number of times memory cells may be rewritten, but some thousands of rewrite operations should be supportable. PIN management would also be essential to prevent swapping attacks, as EPC tags do not support tag-generated randomness in identifiers. Alternatively, the above-noted “block-and-simulate” approach would be workable here.

p-0089Unlike the application of REPs to provide personal privacy, REPs in commercial settings would typically manage a limited population of tags. The goal in this situation may be to transport a container of items from one trusted environment such as a factory to another such as a distribution center. This transportation of goods has been a major source of loss for manufacturers and retailers alike.

p-0090Using a REP to manage the tags avoids the need to build a new data communications infrastructure among supply chain participants. The key distribution problem is reduced to the authentication of a reader to the REP. REPs by their virtue of relaxed cost constraints could be capable of public-key cryptography. Issuance of digital certificates to REPs and readers would eliminate the need for a new secret-key distribution infrastructure. Upon arrival of a pallet at its destination, the reader and REP would perform public-key-based mutual authentication using their digital certificates. On completion of the protocol, the reader would issue a special command causing the REP to unconceal and relabel all the tags in the pallet with their true identities. Thus, REPs can provide significant advantages in applications involving EPCglobal-enabled supply chains.

p-0091The present invention in the illustrative embodiments described above provides devices that can serve as a proxy for RFID tags, simulating such tags to readers, in a manner that enhances user privacy while also maintaining the benefits of tags. The proxy devices of the illustrative embodiments can enforce privacy policies of arbitrary sophistication, taking factors like time and location into account. Proxy devices can efficaciously protect the privacy of consumers and the sensitive information contained in industrial RFID systems, and can withstand attacks against the integrity of tag identifiers, e.g., swapping attacks. In addition to restricting information access where appropriate, a proxy device can also facilitate communications within a given RFID system, and can serve as a bridge between the given RFID system and other types of wireless systems.

p-0092It is to be appreciated that the particular configuration, elements and operating parameters of the illustrative embodiments are not requirements of the invention, and should not be construed as limiting the scope of the invention in any way.

p-0093For example, the system elements and their configuration as shown in <figref idrefs="DRAWINGS">FIGS. 1 and 2</figref> may be varied in alternative embodiments. Similarly, the particular protocol steps in the diagram of <figref idrefs="DRAWINGS">FIG. 3</figref> can be varied in alternative embodiments. Those skilled in the art can make these and other modifications in the described embodiments in a straightforward manner.

p-0094In addition, although described in the context of EPC tags and associated kill and access PINs, the techniques of the present invention may be implemented in systems which utilize a wide variety of other types of RFID devices and associated control codes. Such control codes may be associated with tag functions other than kill and access.

p-0095Furthermore, the various simplifying assumptions made above in the course of describing the illustrative embodiments should also be viewed as exemplary rather than as requirements or limitations of the invention. In alternative embodiments, one or more of these assumptions need not apply.

p-0096These and numerous other alternative embodiments within the scope of the appended claims will be readily apparent to those skilled in the art.