Discussion

7

Defining Strong Privacy for RFID

ARI JUELS

RSA Security

and

STEPHEN A. WEIS

Google

In this work, we consider privacy in Radio Frequency IDentification (RFID) systems. Our contribu-

tion is twofold: (i) We propose a simple, formal definition of strong privacy useful for basic analysis

of RFID systems, as well as a different (weaker) definition applicable to multiverifier systems;

(ii) We apply our definition to reveal vulnerabilities in several proposed privacy-enhancing RFID

protocols; and (iii) We formally analyze and suggest improvements to hash-locks, one of the first

privacy-enhancing RFID protocols in the literature.

Categories and Subject Descriptors: D.4.6 [Security and Protection]: Authentication; F.1.1 [Models of Computation]: Bounded-Action Devices

General Terms: Security, Theory

Additional Key Words and Phrases: RFID, privacy, security, EPC, proximity cards

ACM Reference Format: Juels, A and Weis, S. A. 2009. Defining strong privacy for RFID. ACM Trans. Info. Syst. Sec. 13, 1,

Article 7 (October 2009), 23 pages.

DOI = 10.1145/1609956.1609963 http://doi.acm.org/10.1145/1609956.1609963

1. INTRODUCTION

Radio Frequency IDentification (RFID) systems offer improved efficiency in inventory control, logistics, and supply chain management. As such, they are of great interest to enterprises dependent on efficient supply chains, particularly large retailers and consumer product manufacturers. The long-term goal of these organizations is to integrate RFID on the retail level. Without proper protection, widespread adoption of retail RFID could raise privacy concerns for everyday consumers.

Authors’ addresses: A. Juels, RSA Laboratories, 11 Cambridge Center, Cambridge, MA 02142;

email: [email protected]; S. A. Weis, Google, 345 Spear Street, San Francisco, CA, 94105; email:

[email protected].

Permission to make digital or hard copies of part or all 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 show this notice on the first page or initial screen of a display along

with the full citation. Copyrights for components of this work owned by others than ACM must be

honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers,

to redistribute to lists, or to use any component of this work in other works requires prior specific

permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn

Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or [email protected]. C© 2009 ACM 1094-9224/2009/10-ART7 $10.00 DOI 10.1145/1609956.1609963 http://doi.acm.org/10.1145/1609956.1609963

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Publication date: October 2009.

7:2 • A. Juels and S. A. Weis

Briefly, RFID systems consist of two main components: tags and readers. Tags are radio transponders attached to physical objects. Radio transceivers, or readers, query these tags for some (potentially unique) identifying information about objects which tags are attached to. Although readers may be treated as an intermediary to a independent backend database, for simplicity, we will treat a reader and a backend database as a single entity.

Historically, tags have been expensive, bulky devices used for tagging ob- jects like shipping containers, munitions, automobile parts, or even live cat- tle. The high value of such objects justifies relatively expensive RFID de- vices that may perform complex computations, store ample data, and initiate their own communications. Since people do not typically carry cattle or ship- ping containers around with them, individual privacy is not an issue in these applications.

Concerns about privacy and security do arise, however, in new consumer applications of RFID. RFID technology is present in proximity cards or “prox cards” for physical access control, automobile keys, and in a variety of contact- less payment systems. Many—if not the majority—consumers in industrialized countries today make regular use of such systems. One potential application will be electronic product code (EPC) tags. EPC tags will serve on consumer products as a successor to optical “UPC” bar codes.

In the case of EPC tags, private information might be read from tags attached to products like clothing, books, or prescription drugs. An insecure prox card payment system might leak information about the movements of its users. But even if the semantic meaning of information on tags is well protected, tags may still be recognizable between appearances, and thus subject to tracking. This could violate individual location privacy for consumers or could reveal strategic information about an enterprise or military supply chain.

Because of their intentionally simple design, EPC tags cannot support ex- pensive, traditional cryptography and security functions—not even basic ci- phers. Tight economic considerations suggest that this will remain the case for the foreseeable future. Next-generation EPC tags (such as the emerging, more expensive Class 2 type) and other RFID tags, though, may be capable of performing symmetric-key cryptography. While some of the RFID literature [Fishkin et al. 2004; Juels et al. 2003] addresses privacy in tags that cannot perform cryptography, we focus in this article on privacy in RFID systems where symmetric-key cryptographic operations are possible.

1.1 Privacy-Preserving RFID Protocols in the Literature

Fortunately, much attention has been devoted to RFID security and privacy in recent years. Juels [2006] offers a survey of much of the related literature in and Avoine [2006] maintains a current online bibliography. Rather than reviewing the literature here, we refer the reader to those sources. While many RFID security schemes have been proposed, there has been little formal analysis. Lacking formal security definitions, much existing work offers ad hoc notions of security.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:3

1.2 Previous RFID-Privacy Definitions

Our proposed definition is similar in flavor to those of Avoine [2005], who pro- poses very general and flexible definitions of RFID privacy. The aim of Avoine, however, is to capture a range of adversarial abilities, while we seek to charac- terize a very strong adversary with a relatively simple definition. Thus, we aim for specificity and simplicity over flexibility. For example, the Avoine definitions distinguish between adversarial eavesdropping on the reader-to-tag channel, that is, reader transmissions to tags, and the tag-to-reader channel, that is, tag transmissions to the reader. (In practice, the former is easier to eavesdrop on than the latter, as readers emit more power than tags.) In contrast, we simply assume the ability of an adversary to eavesdrop on both channels.

On the other hand, our model is more general than the Avoine models in one important respect: Ours characterizes the privacy of systems in which tags carry correlated secrets, as in the proposed system of Molnar, Soppera, and Wagner (MSW) [Molnar and Wagner 2004; Molnar et al. 2005]. This feature is lacking in the Avoine models.

Consider the following scheme. Suppose that x is a secret value; let h represent a hash function (modeled as a random oracle) and E represent a symmetric-key cipher in the ideal-cipher model. At time step t, tag 1 outputs (Ex [1, t], h(1, t, x)); tag 2 similarly outputs (Ex [2, t], h(2, t, x)). Tag 3 outputs (Ex [3, t], x ⊕ h(1, t, x) ⊕ h(2, t, x)). Any pair of tags may be seen to offer strong privacy: An adversary cannot distinguish among different outputs of a given tag. But clearly an adversary capable of obtaining the outputs of the three tags at a given time t can completely break the privacy of this system by recovering x. The Avoine definitions, however, permit adversarial interaction with only two tags. They would classify this system as providing strong privacy (Existential- UNT).

While this three-tag construction is slightly artificial, it actually reflects a feature in realistic RFID architectures. In the MSW system [Molnar et al. 2005], for example, tags contain overlapping sets of secret keys derived from a tree structure.

In other work, Juels [2004] presents what he calls a “minimalist” model for tag privacy and security. This model is targeted at low-cost tags that cannot perform symmetric-key cryptography. The accompanying formal privacy defi- nition may be regarded as a specialized narrowing of our definitions here. The Juels definition specifically assumes bounds on the number of queries that an adversary can make in mounting a man-in-the-middle attack. Thus, that defi- nition does not aim to capture RFID privacy in a strong sense. Similarly, Golle et al. [2004] define privacy is a sense specific to a cryptographic primitive they propose called “universal re-encryption” of which they mention RFID as a pos- sible application. Their definition excludes certain forms of active adversarial attack.

Organization

In Section 2, we present our formal definition for strong RFID privacy. In Sec- tion 3, we examine several different privacy-preserving RFID systems proposed

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:4 • A. Juels and S. A. Weis

in the literature. We show how each of these systems falls short of our strong def- inition of privacy; we demonstrate practical attacks that undermine important privacy characteristics. Section 4 briefly examines a privacy-preserving RFID idea called hash-locks that meets our definitional requirements. We prove that one variant meets our privacy definition and propose a simple improvement that achieves privacy in a broader sense. We conclude in Section 5.

2. FORMAL PRIVACY DEFINITION

In this section, we give a formal definition of privacy in RFID systems that can model a variety of security protocols and attacks. We regard a system as comprising a single reader R and a set of n tags T1, . . . , Tn. Each party is a probabilistic interactive Turing machine with an independent source of ran- domness and unlimited internal storage. Tags and readers are modeled as ideal functionalities, similar to entities in Canetti’s Universal Composability paradigm [Canetti]. Functionalities have a well-defined interface, may receive messages, and may respond with messages of their own.

We do not use the term oracle to describe tags and readers, since it sometimes implies a deterministic function where inputs always have the same output. In our model, tags and readers may maintain internal state, are randomized, and may adaptively change their output. We also want to avoid confusion when we later use oracle in the context of the random oracle model.

2.1 Tag Functionalities

Each tag functionality Ti stores an internal secret key and a session identifier sid. A tag can be assigned a new key via a SETKEY message. A tag responds to a SETKEY message by disgorging its current key. The caller may then send an arbitrary new key to replace the prior key. A tag SID can be set to a new value sid via the message (TAGINIT, sid ). TAGINIT messages delete information associated with an existing sid. In other words, a tag may be involved in only one protocol session at a time.

A tag may respond to a protocol message or challenge, denoted c j , with a response r j . The tag functionality interface is illustrated in Figure 1. We explain it further in the following text.

2.2 Reader Functionality

The reader R is initialized with private key material. For the purposes of this model, this key material is immutable and internal to the reader. Tag data may be thought of as residing in a backend database containing records of the tags owned by a particular reader. The reader functionality initializes a new session upon receipt of a message of the form READERINIT. When receiving a READERINIT message, R generates a fresh session identifier, sid, and the first challenge of an interactive challenge-response protocol, c0.

For each READERINIT received, the reader creates a new internal entry of the form (sid, “open,” c0). Any responses containing sid are appended to that entry, as well as subsequent challenges, or any other auxiliary data. This entry is marked as “closed” and becomes read-only when the reader ultimately accepts

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:5

Fig. 1. Illustration of the tag functionality interface.

Fig. 2. Illustration of the reader functionality interface.

or rejects a session. The interface to a reader functionality R is illustrated in Figure 2; further explanation will follow.

2.3 Functionality Interaction

The sid values generated by passing READERINIT messages to R may be passed as a TAGINIT message to some T . Once a tag is initialized with a sid, it can respond to challenge c j with response r j . This response can be a function of the key, sid, the j − 1 previous challenge-response pairs, and locally generated randomness. The tag may internally log both the latest received c j and the response r j . This protocol log and any other data except key are deleted by a tag upon receipt of a TAGINIT message. Thus, a tag’s responses can only depend on that particular session.

Similarly, reader functionality R responds to messages of the form (sid, r j ) by first searching for a (sid, “open”, c0, r0, . . . , c j ) session entry, if any exists. At this point, R performs a verification step by computing a function over its entire internal state, including all open and closed sessions and any internal key material. R can output an “accept” or “reject” and mark the session entry as (sid, “closed”, c0, r0, . . . , c j , r j ). Alternatively, R can compute the next challenge c j +1 and append it to the corresponding session entry.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:6 • A. Juels and S. A. Weis

2.4 Parameterized Adversaries

An adversary A can issue its own SETKEY, TAGINIT, READERINIT, challenge, and response messages. We parameterize the number of READERINIT messages sent by A with r, the number of computational steps1 it performs by s, and the number of TAGINIT messages sent by t. We do not parameterize the number of explicit challenge and response messages an adversary may issue because it will be determined by the number of TAGINIT and READERINIT messages. That is, communication costs are entirely determined by r and t.

Nor do we parameterize the number of SETKEY messages sent by A. An ad- versary able to issue SETKEY messages essentially models both the ability to corrupt a tag, since adversaries obtain its internal tag keys, and to manufacture arbitrary tags, since adversaries can then set tag’s key to an arbitrary value. For this reason, we will consider any tag that receives a SETKEY message from the adversary as “corrupted.” We assume an adversary is able to send as many SETKEY messages as it likes (within its computational step bound s), at any time, to any set of at most n − 2 tags. The rationale for this n − 2 bound will be explained in the following section.

2.5 Privacy Experiment

We now present a privacy experiment reminiscent of the classic indistinguisha- bility under chosen-plaintext attack (IND-CPA) and under chosen-ciphertext attack (IND-CCA) cryptosystem security experiments. The idea is that an RFID protocol may be considered private for some parameter values if no adversary has a significant advantage in this experiment. The goal of the adversary in this experiment is to distinguish between two different tags within the limits of its computational power and functionality-call bounds.

That is why at least two tags need to be uncorrupted. In the first phase of this experiment, an adversary A will be able to issue any messages and perform any computation within its parameter bounds. The adversary A controls the communication channel between R and each Ti , and may obtain or corrupt any sid, c j , or r j values at will.

The adversary selects two uncorrupted tags as challenge candidates. These challenge candidates are removed from the pool of tags at large. One of these challenge candidates is then randomly selected and presented to A (effectively as a tag oracle). A may then issue any messages and perform any computation it likes within its parameter bounds, except issuing a SETKEY command to the tag oracle. (For most protocols, that would make the experiment trivial, although later we briefly explore variants allowing corruption of challenge candidates.)

All key material is generated using a randomized function GEN(1k ) → (key0, . . . , keyn). This function is considered part of the overall RFID system and thus privacy depends on its characteristics. This function is computable by an adversary. Obviously, its output in the experiment is kept secret from A.

We denote our privacy experiment for an RFID system by ExpprivA,S [k, n, r, s, t]. Here, S = (GEN, R, {Ti }), where {Ti } contains n tags. We let k be a security

1We are using “computational steps” in the context of a traditional RAM model of computation.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:7

Fig. 3. The parameterized privacy experiment for the RFID system (GEN, R, {Ti }).

parameter. Adversary A with parameters r, s, and t is denoted by A[r, s, t], where r, s and t are respective parameters for reader initializations, computa- tion steps, and tag initializations. We detail our experiment in Figure 3.

2.6 Privacy Definition

A protocol run within an RFID system S =(GEN,R, {Ti }) is defined to be private if no adversary A[r, s, t] has a nonnegligible advantage in successfully guessing b in the experiment in Figure 3.

We now define the notion of (r, s, t)-privacy for RFID systems. The variables r, s, and t can be functions of system parameters like k, if desired, as we shall see in our analyses. We use the notation poly (k) to represent any polynomial function of k.

Definition 2.1 (RFID (r, s, t)-Privacy). A protocol initiated by R in an RFID system S = (GEN,R, {T1, . . . , Tn}) with security parameter k is (r,s,t)-private if:

∀A[r, s, t] Pr [ ExpprivA,S [k, n, r, s, t] succeeds in guessing b.

] ≤ 1

2 + 1/poly (k).

2.7 Implications of (r,s,t)-Privacy

A few observations on our privacy definition are in order. Definition 2.1 requires that R not differ significantly in its acceptance rate across tags. Otherwise, A could just pick, for example, one tag that R accepts frequently and one that it accepts less frequently as its challenge candidates. R must essentially own all the tags in {Ti }, or at least treat them all equally. ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:8 • A. Juels and S. A. Weis

R also cannot be trivially history-dependent nor can its acceptance be influ- enced significantly by A. For example, an R that accepts each tag only a fixed number m times cannot be private in the face of an A able to make more than m + 1 READERINIT calls. Such an adversary could simply complete m legitimate queries to a tag Phase 1, and see if the reader accepts T ∗b in Phase 2. We discuss exactly this attack in Section 3.

Our definition treats protocol-level privacy issues only. In the real world, there are effectively many possible side channels. As Avoine and Oechslin [2005a] observe, for example, if tags emit a distinctive radio fingerprint, then no protocol-level countermeasures can prevent privacy infringement. And, of course, bearers of privacy-preserving RFID tags are vulnerable to tracking if they additionally carry wireless devices that lack privacy protections.

An important implication of Definition 2.1 is that the GEN function cannot output low-entropy or strongly correlated keys. Otherwise, A might have a significant advantage in guessing keys given the output from SETKEY calls. This illustrates how privacy by our definition depends on the entire RFID system (GEN, R, {Ti }). There are classes of R and GEN that simply cannot be private under this definition.

2.7.0.1 Remarks. (i) A superficial difference between the Avoine model and our own is that the target tags in the Avoine model are determined not by the adversary, but by a Challenger. This Challenger has unspecified function- ality, but presumably selects target tags uniformly at random. In an asymp- totic sense, adversarial and random selection of target tags are equivalent: Random selection will yield any desired pair of target tags with nonnegligible probability.

(ii) One may consider a variant of ExpprivA,S experiment with a stronger ad- versary A that is allowed to corrupt T ∗b in Phase 2 of the experiment, that is, removing the words “except T ∗b ” from experiment step (8c). In most schemes, this will trivially violate privacy. It is worthwhile, however, to consider this def- inition of forward (r,s,t)-privacy. In a scheme with forward privacy of this kind, corrupting a tag does not link it to its past output. (Forward privacy is a goal of the OSK/AO scheme that we analyze later in the text.) Forward privacy is strictly stronger than (r, s, t)-privacy as defined in Definition 2.1.

2.8 Cross-Reader (r,s,t)-Privacy

A limitation of our definition is that it models a world in which a reader R owns every tag, that is, a monolithic and closed system. While this model provides important insights into the privacy properties of an RFID system, different (weaker) definitions can be useful for analyzing real-world scenarios.

Consider an RFID system that contains two types of tags, type A and type B. The reader R recognizes, that is, accepts valid tags of type A. But it rejects all tags of type B. Our definition suggests that such a system can never be privacy preserving. An attacker can break the privacy of the system by distinguishing between type A and type B tags.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:9

In the real world, though, such scenarios frequently arise. There are many, independent RFID systems; people carry heterogeneous constellations of tags, such as SpeedPass tags, contactless credit cards, proximity cards, automobile immobilizer chips, and so forth. The very diversity of tag types leaks informa- tion. An unusual collection of tags could even be uniquely identifying. Thus, while our privacy definition is useful for characterizing privacy within a single RFID system, an extended or variant definition is needed to analyze multiver- ifier privacy—and capture its inherent limitations.

For this purpose, a different (weaker) privacy definition is useful. An at- tacker capable of mounting unrestricted man-in-the-middle attacks can deter- mine whether or not a given tag is recognized by a given reader R. Such an attacker can, of course, easily violate the privacy of an RFID-tag bearer by determining the presence of type A and type B tags on her person. For this reason—and also because man-in-the-middle attacks can be tricky to mount in RFID environments—we propose a variant of our privacy definition. This variant excludes man-in-the-middle attacks by means of a very simple restric-

tion on the adversary in ExpprivA,S [k, n, r, s, t]: When A emits a READERINIT call, the system first emits TAGINIT calls with random sids to all tags. We call the modified experiment Expcross-read-privA,S [k, n, r, s, t], and characterize a system in the obvious way as cross-reader (r, s, t)-private.

Cross-reader (r, s, t)-privacy is useful in analyzing an environment with mul- tiple, independent verifiers (RFID readers). We can model such a system as an environment with just one reader R; we simply assume type A and type B tags as described earlier. Again, type A tags are those that lie within the closed system for reader R, and type B tags are those in other, independent systems.

What is especially interesting about cross-reader (r, s, t)-privacy is its inter- section with tag authentication. As we show in the following text, in a system where R recognizes all tags, that is, all tags are of type A, the original Weis et al. [2003] hash-lock system is (r, s, t)-private and cross-reader (r, s, t)-private for polynomial r, s, t. In a system with tags of types A and B, however, the Weis et al. system is not cross-reader private. This is true because the system does not provide strong authentication for tags. Without mounting a man-in-the- middle attack, an adversary can simulate a target RFID tag and determine whether it is of type A or B, thereby undermining privacy. As we show, how- ever, by adding strong authentication to the Weis et al. system, we can confer cross-reader (r, s, t)-privacy for polynomial r, s, t in a multiverifier environment.

2.8.0.2 Remark. Even cross-reader privacy definition is unachievable when type A and type B tags may be distinguished outside the protocol layer. For example, if the two types operate at different frequencies, an attacker can dis- tinguish between them without reference to any valid reader. In such cases, the best privacy that can be hoped for is indistinguishability, that is, cross-reader privacy among tags of a given physical type.

3. ANALYSIS OF SEVERAL PROPOSED RFID SCHEMES

We now examine several RFID privacy schemes proposed in the literature: (1) That of Ohkubo, Suzuki, and Kinoshita (OSK) [2004] and a variant proposed

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:10 • A. Juels and S. A. Weis

by Avoine and Oechslin (AO) [2005b] (with a follow-up by Avoine, Dysli, and Oechslin [2005]); (2) That of Nohara, Inoue, Baba, and Yasuura (NIBY) [2005]; (3) The YA-TRAP scheme of Tsudik [2006b]; and (4) A recent zero-knowledge scheme of Engberg, Harning, and Jensen (EHJ) [2004].

In our analyses of OSK/AO and NIBY, we demonstrate an adversarial algo- rithm that shows that the algorithms do not achieve strong privacy according to our definition. We believe that this adversarial algorithm is practical and that it reveals a privacy vulnerability that has gone unnoticed in the literature. The vulnerability is similar in both OSK/AO and NIBY. It involves an adversary in- teracting with a target tag and modifying its state. The aim of the modification is to mark the target tag so that it is recognizable by the adversary at a later time. The mark takes the form of state that is invalid in the view of a legitimate RFID reader. The adversary effectively plants a timestamp in a tag that is too far in the future to be treated as valid by the reader.

We believe that this vulnerability in tags that do not accept reader input has been overlooked in the literature because it bypasses the natural intuitive view of privacy modeling. For example, in the OSK/AO system, tags do not accept input from a querying reader (apart from a trivial read command). The only state change in tags is the incrementing of an internal counter. Thus, these systems appear to reduce an adversary to strictly passive attacks. Our formal definition of privacy, however, highlights the fact that an adversary can in fact mount an active attack by aggressively changing the internal state of tags. Tags in OSK/AO and NIBY systems are counter based and output-only. We also examine two systems in which readers modify tag state by means of timestamps.

The YA-TRAP system is a new proposal by Tsudik that has not yet received formal security analysis. Tsudik already notes that the system does not with- stand the full range of possible active attacks. With these limitations in mind, Tsudik has designed YA-TRAP for settings in which RFID-tag information is batched, as in warehouses, rather than for consumer applications. Our analysis gives firmer shape to this design aim. We show a privacy limitation in which, as in OSK/AO, a tag may be marked by being invalidated. More interestingly, an extension of this attack can mark a tag with a unique timestamp that may be indirectly read by an adversary. Our analysis confirms Tsudik’s view of the circumscribed settings for which YA-TRAP is appropriate.

The EHJ system is particularly interesting because it is under commercial development, with privacy being emphasized as its distinguishing feature. The vulnerability we highlight in the EHJ system is of a different nature than the others. In that system, an adversary can intercept a flow in the authentication protocol between a tag Ti and the reader, and interrupt the associated session. By resuming the session at a later time using the intercepted flow, the adversary can uniquely identify Ti .

There is one common thread across all of the vulnerabilities we explore. As our formal definition shows, even a single bit of information—namely whether a tag functions or malfunctions—has an important bearing on RFID-system privacy.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:11

3.1 OSK/AO Schemes

OSK [2004] propose a simple scheme for privacy-preserving tag identification in the face of active attacks; the OSK scheme also provides forward security. Suppose that tag i is initialized with secret xi ; let h1 and h2 be independent one- way functions (most conveniently modeled as random oracles). When queried, the tag updates its secret key by applying h1. The tag outputs IDi,t = h2(h(t)1 (xi )).

Readers in the OSK scheme share secrets with tags. On input IDi,t , a reader determines i by brute-force search. OSK propose a fixed upper bound m on the number of time steps over which tags operate. (After m time steps, presumably a tag yields no output or random output while it awaits reinitialization or retire- ment.) OSK propose that readers precompute a giant table T = {[IDi,t , (i, t)]}, where 1 ≤ i ≤ n and 1 ≤ t ≤ m. When structured appropriately, T can support rapid look-up of a tag identifier. Kinoshita et al. [2005] have implemented the OSK protocol in an active RFID tag.

AO [Avoine and Oechslin 2005b; Avoine et al. 2005] propose use of Hellman tables as a special form of precomputation on T . Hellman [1980] originally studied the problem of breaking symmetric keys. He considered the resource requirements of an attacker seeking to recover secret key k from a ciphertext C = ek (M ) on a predetermined message M . Of course, the attacker might simply perform a brute-force key search, investing computational effort O(n), where n is the size of the full key space. Or she might precompute and store a table of size O(n) consisting of C = {Ci = eki (M )}ki ∈K , and simply look up C in the table; this is what OSK originally proposed.

Hellman, however, identified a useful time-space trade-off. An attacker can pre-compute a table of size O(N 2/3), now known as a Hellman table, that per- mits successful key search with computational effort only O(N 2/3). Loosely speaking, the idea is to group sequences of ciphertexts in C into determin- istically traversable chains of size O(N 2/3). Within the Hellman table are stored only the first and last elements of these chains. Starting with a ci- phertext C, the attacker can traverse the induced chain until she locates the last element. By consulting the Hellman table, she can then determine the first element in the chain; on traversing the chain from this point, she can determine ki .

AO cleverly observed that the problem of symmetric-key search for readers in privacy-preserving RFID systems is nearly identical with that of breaking keys. For a reader to determine which tag it is communicating with, the reader can crack the ciphertext Ci to determine ki and thus Ti . AO apply a variant of the Hellman technique to the OSK system, yielding a scheme with considerably more practical look-up costs. (They in fact propose use of a variant called rain- bow chains put forth by Oechslin [2003].) Rather than constructing a simple look-up table T , a reader can make use of a Hellman table T̃ . The AO approach can thus render the original OSK more practical.2

2Note, however, that because a Hellman table T̃ requires precomputation over a fixed number of entries, it is unclear how to modify the table to accommodate new entries. Insertion of new entries

into a simple table T is more straightforward.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:12 • A. Juels and S. A. Weis

Fig. 4. Adversarial algorithm for OSK/AO.

3.1.0.3 Privacy Vulnerability in OSK/AO. Avoine analyzes the OSK (and, by extension, the AO) scheme for tag identification, and concludes that it affords the strongest form of privacy [Avoine 2005]. As we now explain, however, OSK is in fact vulnerable to an attack that undermines strong privacy in the system.3

Very simply, an adversary can exploit the upper bound m on the number of tag time steps accommodated in the look-up table T or T̃ . The adversary queries a tag until its counter value exceeds m. In essence, it mounts a denial- of-service attack against the tag: The adversary exhausts the supply of valid output values stored in the tag.

This strategy depends on the ability of the adversary to obtain a single bit of information from a reader, namely whether or not it recognizes the output of a given tag as valid. For most natural RFID tag applications, such information will be easily obtainable. For example, a proximity card either opens or fails to open a door, a payment card is either accepted or rejected by a point-of-sale device, and so forth. The adversarial algorithm in Figure 4 demonstrates that OSK/AO does not achieve (r, s, t)-privacy for t > m and r ≥ 1 (and s > m). Indeed, for these parameters, ExpprivA,S [n, k, r, s, t] = 1.

A simple modification of the adversarial algorithm in Figure 4 allows an ad- versary to distinguish among multiple tags by desynchronizing them in differ- ent degrees. The adversary queries Ti a total of qi times to mark it; the adversary lets qi be unique for each tag. On later sighting a target tag T , the adversary queries T a total of m times. Let r1, r2, . . . , rm be the resulting outputs. The adversary feeds these outputs to the reader in reverse order rm, rm−1, . . . until the reader accepts some rk . The adversary concludes that the counter value for the tag q = m− k. Assuming that no normal reading has taken place during the interval of time between the marking and the sighting of the tag, the adversary concludes that if q = qi , the sighted tag is Ti . Note that it the adversary staggers qi values sufficiently, this strategy works even when some limited amount of normal reading has effected changes in tag counter values.

The adversarial algorithm we describe here would appear to be feasible in a practical setting. Avoine and Oechslin [2005b] propose m =1,024 as an example parameter for a practically realizable AO system. As EPC tags (Class 1 Gen 2) have a theoretical read rate of up to 1,000 per second [Alien Technology 2005], the adversarial algorithm we describe could well be feasible in many systems. In the original OSK system, which is less efficient than the AO variant, m would have to be considerably smaller to permit practical deployment, and the vulnerability we describe more easily exploitable.

3The vulnerability we demonstrate appears to exist even within the Avoine privacy model. The

analysis in Avoine [2005] may simply represent an oversight.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:13

3.1.0.4 Remarks. (i) The adversarial strategy we describe for OSK/AO here induces desynchronization between tags and the reader. It is tempting to try to evade this problem with a protocol modification in which the reader rejects input from a Ti if the current tag counter qi differs by more than d from the previous counter perceived by the reader. This does not solve the privacy prob- lem; however, it is equivalent to setting m = d . Moreover, if d is small, then the system becomes vulnerable to denial-of-service attacks. Another possible countermeasure is simply to cause tags to stop yielding output after the mth

query. Again, this creates a vulnerability to denial-of-service attacks. In a natural setting, the adversary might not always have access to fresh

tags, that is, tags whose counters are equal to 0. A simple modification of the adversarial algorithm in Figure 4, however, can still distinguish between tags. By querying a target tag a sufficient number of times, the adversary can mark it. For example, suppose that m = 1,024, and suppose that prior to the testing phase of our definition experiment, Ti and T j have each been queried qi and q j times, where qi , q j ∈U [0, 1, 2, . . . , 50]. Then, the adversary merely has to submit 51 queries to Ti to mark it such that it may be distinguished from T j in the guessing Phase 2.

One possible countermeasure to such attacks is throttling, that is, deliberate slowing of the rate of tag response. A rather different privacy model for tags would be needed to accommodate the effect of this countermeasure, however [Juels 2004].

(ii) MSW carries a similar vulnerability in principle, as tags can support only a pre-determined number of queries, as observed by Molnar et al. [2005]. Under realistic parameterization, however, a privacy-infringing attack would require an infeasibly large number of queries. In a practical sense, therefore, MSW is not vulnerable.

3.2 Unlinkable ID-Matching Scheme

At the 2005 Workshop on Privacy in the Electronic Society, Nohara, Inoue, Baba, and Yasuura (NIBY) [Nohara et al. 2005] proposed a scheme similar in flavor to MSW. Their basic protocol permits leaves of potentially nonuniform depth within a tree T of maximum depth d . A tag is presumed to output random values when depth-first-search queries exceed the depth of its corresponding leaf.

An adversary can undermine strong privacy in this scheme in much the same manner as OSK/AO; nonuniformity in the NIBY scheme, however, renders it more vulnerable. In particular, for a given tag Ti , an adversary can learn the depth di of the corresponding leaf in the identifier tree with overwhelming probability using the following algorithm:

Algorithm Probe(d , Ti ).

(1) Send d queries to Ti (send d TAGINITs).; let Z e = {z (i)e }de=1 denote the sequence of d outputs yielded by the eth query, for 1 ≤ e ≤ d .

(2) For every e, 1 ≤ e ≤ d , replace z (d )e , z (d −1)e , . . . , z (e)e with random values. (3) Feed Z e, Z e−1, . . . to R until R accepts some Z e′ . (4) Output e′.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:14 • A. Juels and S. A. Weis

Fig. 5. Adversarial algorithm for NIBY.

Suppose that the probability that two leaves in the tree T differ in depth is non- negligible. With use of the Probe algorithm as a subroutine, we can construct an adversarial algorithm that breaks (r, s, t)-privacy in NIBY for r, t > 3d (and s > 2d ). This algorithm is depicted in Figure 5.

A reader can ostensibly detect this type of attack. In practice, however, the natural noisiness of RFID systems might make such detection difficult.

The authors analyze the security of a restricted case of their scheme in which all leaves are presumed to have equal depth. The adversarial algorithm we describe here is not applicable in that case. Our analysis, therefore, suggests that use of a uniform tree for NIBY is essential to privacy.

3.3 YA-TRAP: Yet Another Trivial RFID Authentication Protocol

Tsudik [2006b] describes an RFID authentication protocol that he calls YA- TRAP (yet another trivial RFID authentication protocol). As discussed earlier, Tsudik aims this protocol at environments in which tag information is processed in batches, rather than for more fine-grained applications like access control and tagging of individual consumer items. Tsudik [2006a] has not yet formally analyzed the security properties of YA-TRAP; such analysis is forthcoming. In the meantime, our investigation here confirms the importance of confining YA-TRAP to the limited settings for which it is designed.

In YA-TRAP, the reader shares a unique key xi with tag Ti . A tag Ti also stores an internal timestamp pi namely the time at which it was last interrogated by a reader.4 To interrogate a tag, a reader transmits the current time pR. The tag compares pR with pi . If pR is stale with respect to pi , that is, pR ≤ p, then the tag outputs a random response. Otherwise, the tag outputs R = Hxi [ pR], where Hxi represents an HMAC computed with secret key xi ; the tag also sets pi ← pR, i.e., updates its timestamp.5 To validate the response of a tag, a reader checks whether R = Hx j [ pR] for any secret key x j in its database. If so, the reader accepts the tag, otherwise it rejects it.

We consider two adversarial strategies against the YA-TRAP protocol. The first is based on denial of service. An adversary queries a tag with pmax to mark it, where pmax is some time in the far future. The tag sets its internal time value pi ← pmax, and outputs random values in response to all future queries. Thus, a reader rejects the tag in all future sessions, permitting the adversary

4The original article uses t to denote timestamps. We replace this with p to avoid confusion with the security parameter in the (r, s, t) privacy definition. 5The premise is that HMAC output is indistinguishable from a random distribution, so successful

or failed tag responses are indistinguishable to an adversary. While this premise is not true of

HMAC in general, it may be achieved with an appropriate underlying hash function.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:15

Fig. 6. Adversarial DoS algorithm for YA-TRAP.

to distinguish the tag from one that is unmarked. We outline this adversarial strategy in Figure 6.

As the adversarial algorithm in Figure 6 demonstrates, the YA-TRAP pro- tocol does not achieve (r, s, t) = (1, O(k), 2)-privacy. It is worth noting that the Phase 1 portion of the attack does not involve R and can be mounted by an ad- versary with access to Ti alone. The Phase 2 portion does not require a man-in- the-middle setting. A real-life adversary could wait until R tries to legitimately query T ∗b , and then eavesdrop, that is, play a purely passive role.

Building on this first strategy, we arrive at a second and more potent adver- sarial strategy that allows an adversary to mark a tag uniquely—not simply to invalidate it. To mark a tag Ti in this way, the adversary selects a future time ui . The adversary queries tag Ti with it, causing pi ← ui . The time ui serves as a uniquely individuating mark for tag Ti . Starting at any time prior to ui , an attacker can test whether a given, unidentified tag T is in fact Ti . The process involves two stages.

(1) Probing T . The adversary selects two slightly spaced times ubeforei and u after i

such that ubeforei ≤ ui < u after i . The adversary then queries the tag T with

ubeforei and u after i , obtaining responses rbefore and rafter.

(2) Testing the results. The adversary interacts with R at time ubeforei and u after i

and replays responses rbefore and rafter. If the reader accepts rbefore and rejects rafter, then T = Ti with negligible error.

Note that this strategy does not require an active man in the middle. A can interact with the tag and the reader at separate times. This adversarial algo- rithm can be extended, of course, to mark multiple tags uniquely. In the real world, an attacker could identify an individual on the basis of a single marked tag Ti —regardless of how many other tags the consumer is carrying.

In the setting for which YA-TRAP was designed, where a reader batches tag information exclusively for processing by a backend system that does not reveal information to an adversary about the results of its identification of tags, YA-TRAP is not subject to the attacks we describe.

3.3.0.5 Remark. If the granularity of time in the system is small, then it may be difficult for A to interact with R at exactly time ubeforei or u

after i . To

increase its likelihood of success, A can query the tag at multiple times around ubeforei and u

after i , that is, harvest a staggered set of responses from the target tag.

By querying each of n tags, an adversary can set the time value of Ti to a unique time value p2i . These time values are interleaved among a set of marker values of the form p2i−1 such that p1 > p2 > . . . > p2n−1 > p2n > p2n+1.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:16 • A. Juels and S. A. Weis

Instead of just being able to identify a tag among two challenges Ti and T j like in the (r, s, t)-privacy experiment, an adversary will now be able to uniquely identify some T ∗ from any of these n possibilities. To do so, an adversary A sends READERINIT messages to have R repeatedly query T ∗. A legitimate R’s time value will increase monotonically. To identify T ∗, A will wait for the first time value t∗ that T ∗ is accepted. If p2i−1 < t∗ < p2i+1, then A will identify T ∗ as Ti .

This attack could even identify a particular tag from a set of heterogeneous unknown T ∗ tags. In the real world, this could identify an individual carry- ing a tag marked with a specific time value t∗, regardless of how many other heterogeneous RFID systems are present.

3.4 A Zero-Knowledge RFID Protocol

Engberg, Harning, and Jensen [2004] (EHJ) have proposed a privacy-preserving RFID protocol that they call zero-knowledge device authentication. (The pro- tocol, as they note, is not zero-knowledge in the received sense of the term.) Media reports suggest that this protocol is serving as the basis of a commercial offering by a company called RFIDSec [Kahn 2005]. As we show, their protocol does not provide strong privacy according to our definition.

The authors do not fully explain a core aspect of their system. Their authen- tication protocol involves reader-side initiation, but they do not indicate how a reader is to determine which tag it is communicating with (and thus which key to use). Therefore, we assume that the number of tags in the vicinity of the reader is small, such that it can try all keys in attempting to communicate with a tag. We also gloss over the question of how a reader singulates a tag, as this has little bearing on our analysis.

The protocol involves two passes. To use the notation of EHJ, DT is a times- tamp, and RSK is a random nonce selected by the reader. The value SSDK is a tag-specific secret key. We let ⊕ denote the XOR operation: (1) R → T : [DT, (RSK ⊕ h(DT ⊕ SSDK)), h(RSK ⊕ SSDK)] (2) T → R: h(RSK ⊕ SSDK ⊕ DT). A tag stores the timestamp DT ′ that it received in the last successful protocol execution. When it receives a new authentication message based on some DT, it only responds if the message is valid (with respect to SSDK) and if DT > DT ′. Otherwise, the tag outputs no response.

3.4.0.6 Privacy Vulnerability in EHJ. A privacy vulnerability in this sys- tem lies in the way that a tag decides whether or not to respond to a first-flow message. The first flow of the protocol is meant to permit the reader to authen- ticate to the tag. This flow, however, is keyed according to the tag with which the reader communicates. Suppose that adversary intercepts and stores a first flow message M directed to Ti . If the adversary transmits M to Ti (while M is still fresh), then Ti will output a response. Any other tag will disregard M .

Verification of DT > DT ′ is meant to serve against replay attacks. It is easy to see, however, that this protocol features causes a tag to reveal 1 bit of information, namely whether or not DT ′ is fresh in the view of the tag. As

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:17

Fig. 7. Adversarial algorithm for EHJ.

we show, an attacker can exploit this information to undermine the privacy protection of the system.

Suppose that we execute our privacy experiment with two tags, T0 and T1. In Phase 1, the attacker causes the reader to authenticate to T0 at time DT0; the attacker further causes the reader to issue an authentication message M to the tag again at time DT0 ′ > DT0, but intercepts this message (i.e., stores it and does not allow it to reach T0). Finally, the attacker causes the reader to issue an authentication message to T1 and T1 at time DT1, where DT1 > DT′0.

At this point, observe that message M carries a timestamp that is fresh with respect to the stored timestamp DT0 in T0, but stale with respect to the stored timestamp DT1 in T1. Thus, in the second phase of our experiment now, the attacker merely has to transmit M to tag T ∗b . If the tag accepts the message and transmits a response, the attacker concludes that b = 0; otherwise, the tag ignores M , and the attacker concludes that b = 1.

In Figure 7, we specify an adversarial algorithm that shows that EHJ is not (r, s, t)-private for any r ≥ 1 and t ≥ 2. Of course, an adversary can ex- tend this strategy to discriminate easily among multiple tags, T0, T1, . . ., Tn−1. The adversary need simply harvest first-flow messages M0, . . . Mn−1 for each of the tags. To identify a given tag, the adversary tests each of its harvested messages.

One might think that if a tag does not respond to a read request that no privacy issue arises. This idea is misleading for two reasons. First of all, the absence of a tag can be conspicuous. For example, if the tag is a disabled prox- imity card, the fact of an individual being unable to enter a building is an easily observable event. More importantly, though, in the EHJ scheme, a tag must provide some indication of its existence at the outset. If it does not, then the reader cannot determine that it should initiate the first flow. Any practical embodiment of EHJ therefore would probably need at a minimum to involve a liveness signal from tags.

3.4.0.7 Vulnerability in EHJ with Shared Keys. Even if SSDK is shared across tags (which would make the protocol more scalable), a privacy-infringing attack is still possible. In particular, the adversary causes the reader to set timestamps DT0 and DT2 in tags Ti and T j , respectively, by causing two authen- tication sessions to run to completion. The adversary also causes the reader to output a first-flow message M at time DT1, where DT0 < DT1 < DT2. The message M will then be fresh with respect to Ti , but stale with respect to T j , permitting the adversary to distinguish between them. This adversarial strat- egy too can be extended in an obvious manner to distinguish among multiple tags.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:18 • A. Juels and S. A. Weis

3.4.0.8 Repairing EHJ. The EHJ protocol can easily be modified to alle- viate the privacy vulnerability we present here. Rather than ignoring an au- thentication message with a stale timestamp, a tag can output a random or pseudorandom response (computationally indistinguishable from a legitimate one). In the absence of a carefully specified protocol, however, we do not make any formal claims about the security of this variant. Indeed, the inevitable pres- ence of clock skew and the naturally slow response times of RFID tags make timestamp-based protocols like this one tricky to analyze.

One might think that tag silence confers privacy protection by concealing the presence of RFID tags on a given person or in a given environment. We note, however, that tag silence probably confers minimal privacy protection. Even if a tag does not reply to a reader query, its presence is still likely to be detectable through simple power analysis of reflected RF reader emissions. Recent work by Oren and Shamir [O’Connor 2006] suggests the potency of such attacks. Logical-layer silence does not necessarily imply RF silence.

3.5 Summary of Minimum Bounds for Privacy Breaks

This table summarizes the minimum bounds necessary to break privacy in the schemes discussed in this article. Definitions of the security parameters r, s, and t appear in Section 2.4.

Scheme r s t Note OSK/AO 1 m m m is the maximum times a tag may operate NIBY 3d 2d 3d d is the depth of the tree used in NIBY YA-TRAP 1 O(k) 2 k is the security parameter EHJ 1 O(1) 2

4. APPENDIX: HASH-LOCKS

Weis, Sarma, Rivest, and Engels [2003] (WSRE) first advanced the general approach of key search for RFID-tag identification. They proposed two basic schemes dubbed hash-locks and randomized hash-locks. We now show that de- terministic hash-locks are not private by our definition. We will show, however, that randomized hash locks are (r, s, t)-private for any r, s, and t polynomial in k. We propose a new improved randomized hash-lock that is both private and resistant to replay attacks, and also satisfies our cross-reader privacy definition.

4.1 Deterministic Hash-Locks

Hash-locks are an access control mechanism designed for efficiency. The gen- eral idea is as follows. A tag normally resides in a locked state in which it only responds to reader queries with a temporary metaID, rather than some perma- nent identifier. This metaID is the hash of some random nonce selected by R and programmed into the tag. R stores both the metaID and its preimage for its later interaction with the tag.

R may unlock a tag by sending it the preimage of its metaID. The tag verifies that this value hashes to the metaID. Alternatively, the tag need not use a hash function at all. It can instead be locked with some secret metaKey. The tag is programmed with a (metaID, metaKey) pair when locked, and unlocked with

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:19

the metaKey. The hash-function-based scheme may be justified, however, if the hardware cost of implementing a hash function is less than EEPROM costs of metaKey storage or if the metaID needs to be assigned in the clear.

Using the notation of this article, the session identifier sid will play the role of the metaID. Let h : {0, 1}∗ → {0, 1}2k be a random oracle. Hash-locks work as follows.

Setup: (1) GEN outputs a uniformly chosen vector of k-bit keys (key1, . . . , keyn). (2) R is initialized with GEN’s output. (3) Each Ti is initialized by a SETKEY call with a unique keyi . (4) R makes a TAGINIT call to each Ti with sid = h(nonce) for a random

k-bit nonce. (5) R stores each (sid, nonce) pair internally.

System execution: (6) R’s challenge c0 to a tag T is empty. (7) T ’s response r0 = sid . (8) R’s challenge c1 = nonce. (9) If h(c1) = sid , then T ’s r1 is some identifier determined by key.

(10) Otherwise T ’s r1 is empty.

Clearly, this protocol is not private by our definition, since a tag’s response r0 is always its current sid. Or A can simply eavesdrop on the protocol between T ∗b and R to obtain some identifier. Thus, deterministic hash-locks are not (r, s, t)- private for any nontrivial (r, s, t) values. In fact, any protocol where tags respond deterministically is necessarily not private by our definition.

4.2 Randomized Hash-Locks

In contrast, WRSE’s randomized hash-lock scheme is a mechanism for private tag identification that is in fact (r, s, t)-private in the random oracle model. We present a short proof of this fact. Letting h : {0, 1}∗ → {0, 1}2k be a random oracle, randomized hash-locks work as follows:

Setup: (1) GEN outputs a uniformly chosen vector of k-bit keys (key1, . . . , keyn). (2) R is initialized with GEN’s output. (3) Each Ti is initialized by a SETKEY call with a unique keyi . (4) Tags do not store any session state or sid.

System execution: (5) R’s challenges c0 are empty. (6) T ’s response r0 = (nonce, h(nonce||key)), for a random k-bit nonce. (7) R searches for keyi among GEN’s output such that r0 contains

h(nonce||keyi ). (8) R accepts if such a keyi exists and rejects otherwise.

A simple illustration is given in Figure 8.

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:20 • A. Juels and S. A. Weis

Fig. 8. Illustration of the randomized hash-lock protocol.

THEOREM 4.1 (RANDOMIZED HASH-LOCK PRIVACY). Randomized hash-locks are (r, s, t)-private in the random oracle model, for any polynomially bounded A, that is, any r, s, t polynomial in k.

4.2.0.9 Proof. We specify a simulator Sim for T ∗b in the privacy experi- ment Exppriv. Sim does not possess knowledge of the value of b or any keys ki . A’s interaction with Sim will be computationally indistinguishable from an interaction with T ∗b . Thus, we demonstrate that A gains no knowledge from its interaction with T ∗b in the real RFID system S.

Recall that A selects two challenge tags Ti and T j from the population of uncorrupted tags. Let L be the full list of pairs {(nonce, h(nonce ‖ key))} output by Ti and T j during the learning phase of the experiment. Let H() represent the random oracle for h() in our system.

During the challenge phase, Sim simulates the result of a TAGINIT call to T ∗b by generating a random nonce/hash pair (n, y ) and appending it to a list L′

(empty at the beginning of the challenge change). In addition to any valid tag pair, R accepts any pair in L′.

In order for A to distinguish between the simulated challenge phase and a real challenge phase, A must determine that some pair (n, y ) ∈ L′ is invalid for both Ti and T j . As a necessary condition for this determination, A must identify a pair (n, z) that is valid for Ti or T j , but such that z = y . (In other words, A must rule out (n, y ) as a valid pair in order to determine that Sim is present.) Consequently, one of the following three conditions must occur at some point in the course of the experiment.

(i) There is a nonce value n such that (n, y ) ∈ L′ and (n, z) ∈ L for some pair ( y , z): Since A may make at most t calls to tags, we have |L′|, |L| ≤ t. As nonces are random k-bit values, and thus the space of nonces is 2k , it follows that this condition occurs with probability at most t2/2k .

(ii) A submits to H() a query of the form n ‖ ki or n ‖ k j : Given that H() is a random oracle, its outputs reveal no information about secret keys. Hence, the probability that A can successfully submit a query of the form n ‖ ki or n ‖ k j is at most 2s/2k , and thus negligible.

(iii) For a pair (n, y ) ∈ L′, A submits and R accepts a pair (n, z), where z = y : Barring Condition 1 and Condition 2, and given that H() is a random oracle, A can submit a pair (n, z) ∈ L, L′ only by guessing z by brute force. The probability of this event is at most r/2k .

Thus, A can distinguish Sim from T ∗b with probability at most (r + 2s + t2)/2k , which is negligible for polynomially bounded A. ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:21

4.3 Improved Randomized Hash-Locks

Since r0 does not depend on any reader input, tag outputs are vulnerable to replay. Consequently, as explained in Section 2.8, the WRSE system does not provide privacy in a multiverifier model. In particular, it does not provide cross- reader (r, s, t)-privacy.

Fortunately, this is an easily addressable flaw. Instead of sending an empty c0, R can instead send c0 = nonceR, where nonceR is generated uniformly at random. (Alternatively, sid could contain this nonce value.) A tag will generate its own nonce nonceT and send the value r0 = (nonceT , h(nonceR||nonceT ||key)). The reader R will then search for a key among GEN’s output that would generate r0.

Adversaries cannot replay a previously used r0 to a R, since with high proba- bility, it will not match the nonceR value generated by R for that session. Unlike the OSK/AO or NIBY protocol, the tag does not store internal state based on nonceR. Thus, there is no counter or timestamp that can be manipulated by an adversary. Unlike EHJ, the tag always yields an output value.

We do not formally analyze this variant protocol here.

5. CONCLUSION: FURTHER RESEARCH DIRECTIONS

We have proposed new privacy definitions strong enough to capture highly stringent application-level design requirements for RFID systems in the real world. We believe that the relative simplicity of these definitions is useful for the design and analysis of privacy-preserving RFID protocols. In this article, we have examined several published systems that fail to fulfill our privacy definition. In so doing, we believe that we have highlighted potential design flaws.

That said, our proposed privacy definitions are just a starting point. They certainly do not capture the full spectrum of real-world needs. Stronger def- initions, which could perhaps model side-channel attacks as well as weaker privacy definitions, like cross-reader privacy, both could be useful in RFID pro- tocol design. With this in mind, we propose two important areas for further work.

5.1 Stronger Definitions

In one sense, even our definition of strong privacy is not strong enough, as it does not capture the effects of side information. Side-channel attacks are pertinent to newly emerging protocol proposals. For example, in independent and contemporaneous work, Burmester et al. [2006] propose a new protocol called O-TRAP that is similar in flavor to hash locks. They propose a definition of privacy and security in the Universal Composability framework and prove that O-TRAP fulfills their definition. We believe that O-TRAP is also provably secure with respect to our definition of strong privacy.

O-TRAP, however, is not secure according to a variant of our definition in which the reader functionality outputs timing information. The reader (or back- end server) in the O-TRAP protocol performs a single table look-up in the op- timistic case where a tag is synchronized with a reader; otherwise, it performs

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

7:22 • A. Juels and S. A. Weis

a search of the full key space for the system. If an adversary can distinguish between these two cases based on timing—which seems a serious, practical threat—she can mark tags by desynchronizing them, much as we do in the attacks we describe previously for OSK/AO and NIBY. (The reader in O-TRAP could process tags in uniform time, but then the system would be no more efficient than brute-force key search, like the improved hash-lock scheme we proposed earlier.) Thus, a small extension of our model in which the reader outputs information about computation time can shed critical light on protocol design. Modeling other forms of side information may prove equally valuable.

5.2 Weaker Definitions

On the other hand, some aspects of our definitions (even the cross-reader one) may actually be too strong. For RFID tags capable of only symmetric-key cryp- tography, we believe that our definition may require the reader to perform brute-force search to identify tags—at least in cases of desynchronization. Such a system scales poorly. Obviously public-key cryptography would alleviate this burden, but is impractical for the vast majority of RFID devices. (Indeed, many classes of RFID tags will be incapable of executing even standard symmetric- key protocols for some years.) While the cryptographic literature often aims at increasingly strong definitions and protocols, we emphasize like Juels [2006] that a fertile and essential area of investigation is definitions and protocols for RFID privacy that are weaker, but more practical and useful.

ACKNOWLEDGMENTS

Thanks to Gildas Avoine, Burt Kaliski, Shingo Kinoshita, Miyako Ohkubo, Koutarou Suzuki, and Gene Tsudik for their very helpful comments on this work.

REFERENCES

ALIEN TECHNOLOGY. 2005. Alien Technology Corporation achieves another step toward pervasive,

economic RFID with announcement of 12.9 cent RFID labels. Alien Technology Press release.

http://www.alientechnology.com.

AVOINE, G. 2005. Adversarial model for radio frequency identification. Cryptology ePrint Archive.

Report 2005/049. http://eprint.iacr.org

AVOINE, G. 2006. Security and privacy in RFID systems. http://lasecwww.ep.ch/figavoine/rfid/.

AVOINE, G., DYSLI, E., AND OECHSLIN, P. 2005. Reducing time complexity in RFID systems. In

Proceedings of the 12th Annual Workshop on Selected Areas in Cryptography (SAC’05). Springer- Verlag, Berlin.

AVOINE, G. AND OECHSLIN, P. 2005a. RFID traceability: A multilayer problem. In Proceedings of the 9th International Conference on Financial Cryptography and Data Security (FC’05). Springer- Verlag, Berlin, 125–140.

AVOINE, G. AND OECHSLIN, P. 2005b. A scalable and provably secure hash based RFID protocol. In

Proceedings of the 2nd IEEE International Workshop on Pervasive Computing and Communica- tion Security (PerSec’05). IEEE, Los Alamitos, CA, 110–114.

BURMESTER, M., VAN LE, T., AND DE MEDEIROS, B. 2006. Provably secure ubiquitous systems: Uni-

versally composable RFID authentication protocols. http://eprint.iacr.org/2006/131.pdf.

CANETTI, R. Universally composable security: A new paradigm for cryptographic protocols. IACR

ePrint Report 2000/067. http://eprint.iacr.org/2000/067

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.

Defining Strong Privacy for RFID • 7:23

ENGBERG, S., HARNING, M., AND JENSEN, C. 2004. Zero-knowledge device authentication: Privacy

and security enhanced RFID preserving business value and consumer convenience. In Proceed- ings of the 2nd Annual Conference on Privacy, Security, and Trust. IEEE, Los Alamitos, CA.

FISHKIN, K. P., ROY, S., AND JIANG, B. 2004. Some methods for privacy in RFID communication. In

Proceedings of the 1st European Workshop on Security in Ad-Hoc and Sensor Networks (ESAS’04). Springer, Berlin.

GOLLE, P., JAKOBSSON, M., JUELS, A., AND SYVERSON, P. 2004. Universal re-encryption for mixnets. In

Proceedings of the Cryptographers’ Track RSA Conference (CT-RSA). Springer, Berlin, 163–178. HELLMAN, M. 1980. A cryptanalytic time-memory tradeoff. IEEE Trans. Inf. Theor. 26, 401–406. JUELS, A. 2004. Minimalist cryptography for low-cost RFID tags. In Proceedings of the 4th Inter-

national Conference on Security in Communication Networks (SCN’04). Springer-Verlag, Berlin, 149–164.

JUELS, A. 2006. RFID security and privacy: A research survey. IEEE J. Sel. Areas Comm. 24, 2. JUELS, A., RIVEST, R., AND SZYDLO, M. 2003. The blocker tag: Selective blocking of RFID tags for

consumer privacy. In Proceedings of the 8th ACM Conference on Computer and Communications Security. ACM, New York, 103–111.

KAHN, F. 2005. Can zero-knowledge tags protect privacy? RFID J. http://www.rfidjournal. com/article/articleview/1891/1/1/.

KINOSHITA, A., OHKUBO, M., HOSHINO, F., MOROHASHI, G., SHIONOIRI, O., AND KANAI, A. 2005. Privacy

enhanced active RFID tag. In Proceedings of the International Workshop on Exploiting Context Histories in Smart Environments. Springer-Verlag, Berlin.

MOLNAR, D., SOPPERA, A., AND WAGNER, D. 2005. A scalable, delegatable pseudonym protocol en-

abling ownership transfer of RFID tags. In Proceedings of the 12th Annual Workshop on Selected Areas in Cryptography (SAC’05). Springer-Verlag, Berlin.

MOLNAR, D. AND WAGNER, D. 2004. Privacy and security in library RFID: Issues, practices, and

architectures. In Proceedings of the ACM Conference on Communications and Computer Security. ACM, New York, 210–219.

NOHARA, Y., INOUE, S., BABA, K., AND YASUURA, H. 2005. Quantitative evaluation of unlinkable ID

matching schemes. In Proceedings of the Workshop on Privacy in the Electronic Society (WPES’05). ACM, New York.

O’CONNOR, M. 2006. EPC tags subject to phone attacks. RFID J. http://www1.rfidjournal. com/article/articleview/2167/1/1.

OECHSLIN, P. 2003. Making a faster cryptanalytic time-memory trade-off. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques. Springer- Verlag, Berlin, 617–630.

OHKUBO, M., SUZUKI, K., AND KINOSHITA, S. 2004. Efficient hash-chain-based RFID privacy protec-

tion scheme. In Proceedings of the International Conference on Ubiquitous Computing. Springer- Verlag, Berlin.

TSUDIK, G. 2006a. Personal communication.

TSUDIK, G. 2006b. YA-TRAP: Yet another trivial RFID authentication protocol. In Proceedings of the 4th Annual Conference on Pervasive Computing and Communications (PerCom’06). IEEE, Los Alamitos, CA.

WEIS, S., SARMA, S., RIVEST, R., AND ENGELS, D. 2003. Security and privacy aspects of low-cost radio

frequency identification systems. In Proceedings of the International Conference on Security in Pervasive Computing (SPC’03). Springer-Verlag, Berlin, 454–469.

Received April 2007; revised November 2008; accepted January 2009

ACM Transactions on Information and System Security, Vol. 13, No. 1, Article 7, Pubication date: October 2009.