MAP: Towards Authentication for Multiple Tags

Abstract

The prevalence of Radio Frequency Identification (RFID) technology requires Privacy-Preserving Authentication (PPA) protocols to prevent privacy leakage during authentication. Existing PPA protocols employ the per-tag authentication, in which the reader has to sequentially authenticate the tags within the detecting region. Such a processing pattern becomes a bottleneck in current RFID enabled systems, especially for those batch-type processing applications. In this paper, we propose an efficient authentication protocol, which leverages the collaboration among multiple tags for accelerating the authentication speed. We also find that the collision, usually being considered as a negative factor, is helpful media to enable collaborative authentication among tags. Our protocol, termed as Multiple-tags privacy-preserving Authentication Protocol (MAP), authenticates a batch of tags concurrently with strong privacy and high efficiency. The analytical and simulation results show that the efficiency of MAP is better than O( $\log N$ ) and asymptotically approaches O(1).

1. Introduction

RFID technology has been involved in many daily applications [1]. RFID tags can be embedded in passports, ID cards, credit cards, and logistical labels to perform remote identification, as well as facilitate applications such as device-free activity monitoring [2] and fast inventory [3]. RFID tags usually contain or relate to sensitive information of the tag owners or carriers. If the sensitive information on a tag is exposed, the privacy of the tag holder will be jeopardized. Recently, Privacy-Preserving Authentication (PPA) protocols [4–6] are proposed to enable authentication for tags without leaking private information. Generally, each tag shares some secrets with the reader. During authentication, the reader interrogates a tag with a nonce. The tag responds with a message computed with the shared secrets and the nonce to authenticate itself to the reader. Upon this response, the reader searches in the backend database to find a match record for the tag and determine the validity of the tag. If the tag is legitimate, the reader emits a message to authenticate itself to the tag. Utilizing cryptographic functions and nonces, PPA protocols can strengthen privacy protection.

Most PPA approaches are designed for the per-tag scenario, where a reader can only authenticate one tag at each time. Due to cost concern, an RFID tag is usually designed to be extremely resource limited, even with less power than in sensor-based data collection applications [7]. Thus, the tag cannot afford complex cryptographic functions, such as asymmetric cryptographic functions. Thus, current RFID tags usually adopt relatively low-cost cryptographic algorithms, for example, the lightweight hash functions [8] or HB protocols [9], to perform the authentication. However, it is proven that a large system with strong indistinguishable privacy and constant complexity requires public key cryptography in [10], where the indistinguishable privacy (ind-privacy) means that none can link a tag and its behavior without learning its internal states. The proof also implies that the authentication complexity of PPA protocols is at least $O(N)$ if utilizing symmetric cryptographic functions to achieve strong privacy, where N is the number of tags in the system. As a result, existing PPA protocols, although achieving $O(\log N)$ or even $O(1)$ complexity, have the penalty of privacy degrading.

The above dilemma motivates us to change the perspective of enhancing privacy and improving efficiency for PPA protocols. Before presenting our protocol, we report the following important observations.

• (a)

Essentially, batch-type authentication pattern is more suitable for current RFID applications. Many RFID applications have urgent requirements for batch processing. For example, in port logistics applications, items are usually arranged in containers. The customs authorities need to check or even real-timely monitor the cargos to avoid hiding of dangerous goods. It would be impractical and time consuming to open the containers and authenticate the goods one by one. What is more, the tags on goods may have sensitive business information unwilling to be leaked. These needs also arise when express companies deliver valuable goods, where privacy leakage may cause reputation defamation of the customers. If batch-type PPA protocols are available, the urgent needs of efficient and private authentication can be satisfied.

(b)

When facing multiple tags, an RFID reader needs an anticollision process for communicating and dealing with each individual tag. Although being efficient, existing anticollision approaches cannot meet the requirement of privacy protection. Thus, the anticollision process should be performed anonymously. The result of the anonymized anticollision process, however, is helpless to the authentication process. Simply combining these two processes is inefficient for real RFID systems. In addition, a large number of operations are redundant for processing multiple tags if employing PPA protocols with the per-tag pattern, which also incurs a time waste, as will be shown in Section 3.1.

(c)

To resist the tracking attack, it is an intuitive way to employ multiple tags for confusing the attackers, as will be shown in Section 6.1. But we cannot fully utilize this feature if adopting the per-tag authentication pattern. If we can allow multiple tags to collaboratively protect themselves in PPA authentication, their privacy can be enhanced.

With the above observations, we introduce the concept of tag collaboration to RFID systems. A group of tags can cooperate to obtain better privacy protection. Furthermore, the collaboration can improve the efficiency of RFID authentication. We thereby propose a protocol to allow a batch of tags to collaboratively authenticate themselves to the reader. The protocol also meets the urgent need from real RFID applications. Our protocol, termed as Multiple tags privacy-preserving Authentication Protocol (MAP), has three major merits.

• (1)

MAP allows multiple tags to perform collaborative authentication. Particularly, we leverage the collision, which is commonly considered as a negative impact on RFID authentication, to perform collaboration. The collaboration accelerates the authentication process and hides each individual tag in the group.

(2)

MAP can effectively defend against compromising attack, in which an adversary tries to distinguish uncompromised tags based on the secret information obtained from compromised tags and provide strong privacy for multiple tags. We define a notion of m-strong-ind-privacy, as a refinement of ind-privacy, to evaluate the privacy strength of multiple tags' authentication. We prove that MAP can provide m-strong-ind-privacy. With this feature, the possibility that adversaries successfully break the indistinguishable privacy of tags is mitigated to be negligible. Therefore, our scheme provides strong privacy protection for practical RFID applications.

(3)

MAP also provides security and privacy protection in terms of confidentiality, cloning resistance, tracking resistance, timing-based attack resistance, and forward secrecy.

(4)

We present the theoretical upper bound, lower bound, and mean time cost of MAP's authentication efficiency. The results show that the authentication efficiency of MAP is better than $O(\log N)$ , which is the upper bound of most PPA approaches. In particular, the efficiency asymptotically approaches to $O(1)$ as the size of the tag set enlarges.

The rest of this paper is organized as follows. We discuss the related works in Section 2. In Section 3, we present our observations and motivations in authenticating multiple tags. We present the details in the design of MAP in Section 4. In Section 5, we discuss the performance of MAP. In Section 6, we present the security and privacy analysis. In Section 7, we provide some possible variants and improvements. At last, we conclude the work.

2. Related Works

2.1. Existing PPA Protocols and Their Limitations

Recently, Privacy-Preserving Authentication (PPA) protocols [4–6] are proposed to protect private information for RFID users. Those approaches aim to provide authentication for tags without leaking their private information, for example, the IDs stored in tags.

Early PPA protocols organize tags (or keys of the tags) in a linear structure [11, 12]. The linear structure results in $O(N)$ search efficiency, where N is the number of tags in the system. In large-scale systems that usually have millions of tags, however, $O(N)$ is insufficient to meet the need of fast processing. In [13], the authors employ a time-space tradeoff to provide $O(N^{2/3})$ search efficiency [14], but their work is still inefficient for large-scale systems. Later, a number of synchronization protocols are proposed to utilize precomputed records to accelerate the search procedure. In [15–17], the reader synchronizes with tags for fast authentication. Although the synchronization approaches can provide $O(1)$ search efficiency, they are vulnerable to desynchronization attacks. In such attacks, an adversary keeps interrogating a tag until the counter of the tag goes beyond a predefined threshold. In this case, the protocol would be improperly broken and the tag can be either unacceptable by legitimate readers or trackable to attackers. In [18], the authors propose a protocol which combines the synchronization method with exhaustive search. Such a combination can achieve efficient authentication with high privacy protection when the protocol utilizes synchronization method but suffers from $O(N)$ search efficiency when the synchronization method is not applicable.

Besides the linear organization, tags can be organized in a virtual tree-based structure [19, 20]. In a tree-based approach, each tag is attached to a leaf node. Each node in the tree keeps a random key. A tag holds the keys on the path from the root to the corresponding leaf node. During an authentication, the reader sends a query and the tag generates ciphers using its keys. Upon the ciphers, the reader performs a Depth-First-Search (DFS) in the key tree for locating a path with correct keys that can successfully match those ciphers, and hence authenticating the tag. In this way, the reader can authenticate a tag with an $O(\log N)$ search efficiency, where N is the number of tags. Tree-based protocols are efficient, but they suffer from the compromising attack. In tree-based approaches, compromising attack is the most serious threat because the tags share keys with each other. The adversary can recognize an uncompromised tag via some of the keys obtained from compromised tags. For example, in a binary tree-based system with 2²⁰ tags, compromising 20 tags can achieve a nearly 95.5% probability of successfully tracking a tag [21]. Many protocols are proposed to resist compromising attack by utilizing key-updating mechanism [21] or balancing the tradeoff between time, space, and privacy [22]. Those protocols, although mitigating the affect of compromising attacks, still cannot provide strong ind-privacy [23] with less than O(N) complexity. In [9], a protocol employing lightweight HB protocol instead of cryptographic hash function is proposed to achieve efficient authentication. This design, based on tree architecture, also suffers from compromising attack.

Existing PPA protocols are designed for authenticating a single tag at a time, which is suitable for per-tag scenario. The per-tag pattern, however, can hardly provide high efficiency and privacy simultaneously, which implies a need of adopting public key cryptography [10]. Unfortunately, the adoption of public key cryptography is prohibitively expensive for most tags due to the capability and resource limitations. Some researchers suggest weaker privacy models for per-tag authentication [23, 24].

Recently, some works emerged dealing with multiple tags' identification and thus are related to this work [25–28]. Yang et al. [25] propose to aggregate the responses from a batch of tags on corresponding readers, and then the aggregated responses enable probabilistic verification for the batch of tags. Bianchi [26] extends this approach and employs Bloom Filter to achieve a more general framework. These two works focuses on the reader-to-server process procedure, while our approach focus on the searching process for authenticating tags with privacy concern. Zheng and Li [27] propose a fast tag searching protocol which is efficient and scalable for multiple tags. However, this work focuses on tag identification other than authentication. Sheng and Tan [28] study the group authentication problem with heterogeneous RFID network. In this work, more advanced computational RFID tags are introduced helping regular tags to be authenticated to the reader.

2.2. Existing Anticollision Algorithms and Limitations

On the other hand, many anticollision algorithms, such as [29–32], have been proposed to arbitrate collisions of multiple tags. There are two major categories of anticollision algorithms, framed-slot-based approaches (also known as ALOHA-based approaches), and tree-based approaches. In an ALOHA-based approach, a reader first sends query command claiming how many slots in a detecting frame. Then each tag randomly selects a slot and transmits the ID within the chosen slot. In some slots, a collision may inevitably happen. The reader will repeatedly launch the detecting process until every tag can be identified without collisions. The tree-based anticollision protocols allow the reader to actively declare a filter. According to the filter, a set of tags are required to report their IDs in a slot, and others keep silent. In this way, the reader can decode responses and identify tags. In [29], historical information obtained from the last identification process is used in current identification process to decrease collisions. In [30, 31], a counter facilitates tags to evade collisions. The tags with a counter 0 respond the query and choose a value, for example, 0 or 1, for their counters in the next round if they collide. In [32], the authors propose a method for multiple readers to interrogate tags with near-optimal number of time slots.

Being effective in collision arbitration, the above designs, however, are unsuitable for protecting privacy, since the IDs are all in plain text during the anticollision process. Although the authors in [33] propose a pseudo-identifier to enable private anticollision, the pseudo IDs cannot help the reader to know the real ID of the tags. Thus the reader has to conduct another search procedure for locating the tags and getting their keys needed for authentication.

3. Observations and Motivation

3.1. Observations on Redundancy and Possible Treatments

In real RFID applications, it is common that a batch of tags is within the detecting region of a reader. The reader employs an anticollision process to distinguish those tags and then communicates with each of them for performing PPA authentication. Indeed, the combination of anticollision and authentication is inefficient.

Firstly, current PPA protocols are mainly designed for per-tag scenarios, where the searching process for different tags' keys contains many redundant computation and comparison operations. We demonstrate this fact via an example of a typical tree-based authentication protocol [20]. The keys are arranged in a key tree, as illustrated in Figure 1. The protocol is performed as shown in Figure 2. In Figure 1, $T_1$ 's keys are ( $k_{1,\mathrm{0}}$ , $k_{2,\mathrm{1}}$ , $k_{3,\mathrm{2}}$ ). $N_R$ and $N_T$ are two nonces, $r=N_R||N_T$ is their conjunction, and $F_{k_{\mathrm{1,0}}}(r)$ , $F_{k_{\mathrm{2,1}}}(r)$ , and $F_{k_{\mathrm{3,2}}}(r)$ are three hash values computed by using r and the three keys ( $k_{\mathrm{1,0}}$ , $k_{\mathrm{2,1}}$ , $k_{\mathrm{3,2}}$ ) of $T_1$ , respectively. The hash value with the inputs of r and tag $T_i$ 's jth level key $k_j^i$ is $F_{k_j^i}^{}(r)$ . The reader then checks the hash values at level j to determine the jth branch that the tag lies in. Continuing this process, the reader can eventually identify and authenticate a tag. For the example in Figure 1, the reader will travel along the path root → $M_1$ → $M_2$ → $T_1$ to reach the leaf node $T_1$ . In this way, the reader can authenticate a tag with $O(\log N)$ efficiency.

Figure 1

Tree-based architecture.

Figure 2

Typical tree-based protocol.

In Figure 1, if $T_1$ and $T_2$ are both in the batch, the reader has to check ( $k_{\mathrm{1,0}}$ , $k_{\mathrm{2,1}}$ , $k_{\mathrm{3,2}}$ ) to authenticate $T_1$ and check ( $k_{\mathrm{1,0}}$ , $k_{\mathrm{2,1}}$ , $k_{\mathrm{3,3}}$ ) for $T_2$ . The checking for $k_{\mathrm{1,0}}$ and $k_{\mathrm{2,1}}$ is redundant. Previous works pay little attentions to the redundant operations in PPA authentication, because they mainly focus on the interaction between the individual tag and reader in the per-tag's authentication. If those redundant operations are well arranged, a nontrivial improvement on the authentication efficiency can be achieved in the batch-type process.

Secondly, the anticollision and authentication processes are generally conducted separately. In the existing works, the result of anticollision cannot be reused by the authentication process. Since existing anticollision mechanisms are designed without considering privacy protection, if a tag uses its real identifier in the anticollision process, the privacy will be broken. To meet the need of privacy, a tag can only use anonymized ID, for example, a pseudo-identifier, in the anticollision process. Nevertheless, the reader cannot leverage anonymized ID to locate the tag in the database in the PPA authentication process. If the anticollision information is generated and utilized without privacy leakage, the authentication process can be accelerated by reusing the result of anticollision.

3.2. Motivation

Based on above observations, our motivation is to enable the collaboration of multiple tags to concurrently achieve privacy-preserving collision arbitration and fast authentication.

We still employ the example in Figure 1 to explain our strategy. Consider two tags $T_2$ and $T_3$ . If simultaneously queried by a single reader with a timestamp r, they will emit messages for the reader's verification, as defined in the PPA protocols. These messages are computed using the r and their keys. According to the collision resistance property of cryptographic hash functions, the keys in different branches will produce different outputs. Thus, the two hash values will be different at some bits. We call those bits as different collision bits and their positions as collision positions. Indeed, these collisions provide us a possible way to privately differentiate tags.

In fact, a legitimate reader knows the keys of all tags; that is, it knows the keys at each branch in the key tree. This fact allows us to leverage precomputed results to accelerate the authentication. In Figure 1, with these known parameters, R can compute the possible hash values of $T_2$ and $T_3$ at level 1 in advance. Then R can compare these two hash values to obtain the possible positions of collision bits. R can just query the first collision bit to check if there is a difference. If a collision is detected at a virtual node in the binary key tree, each of its branches contains at least one tag in the detecting region. Figure 3 illustrates an example for $T_2$ and $T_3$ . At level $x-1$ , R pre-computes hash values $h(k_x^2,r_y)=10110$ and $h(k_x^3,r_y)=10000$ , where $h(k_x^j,r_y)$ is computed with $T_j$ 's xth key and the timestamp $r_y$ for this current sessionas inputs. The two hash values differ at the 3rd bit, then R sends out a query ( $r_y$ , 1, 3), where 1 denotes a value for collision bit at level $x-2$ denoting node $M_1$ , and 3 is the collision position of level x. Upon the query, $T_2$ and $T_3$ compute responses, where (10110)₃ = 1, (10000)₃ = 0, and ${(v)}_u$ is the uth bit in v. Then $T_3$ responds “1” at time slot 0 and $T_2$ responds “1” at time slot 1. In this way, ONE bit transmission is adequate in each time slot for tag's response. At level x, R receives the responses and chooses a branch, which is related to slot 1 in this example. R also pre-computes and sends out the message to continue the depth-first-search. With this message, R moves to the node related to $T_2$ at next level and $T_3$ enters the “holding” status, in which $T_3$ will keep silent until its turn for any action. In this way, tags collaboratively conduct the anticollision. R can verify a tag's unique information when it moves to the leaf level to complete the authentication for this tag. Note that, even if a collision happens due to the existence of multiple tags in a slot, R can still conduct the anticollision process because R only requires the information that whether a branch contains tag instead of recovering individual responses from tags.

Figure 3

Anticollision with one bit.

Based on the above analysis, we find that combining private anticollision and authentication processes is feasible. In particular, the length of each tag's response message to the reader can be minimized to one bit.

4. MAP Design

4.1. Overview

The MAP has four components: system initialization, tags authentication, updating, and system maintenance.

MAP also initializes a virtual tree to organize keys for tags. Except the root, each virtual node in the tree contains a key. Each leaf node is assigned to a tag. Hence, the depth of the tree is $O(\log N)$ , where N is the total number of tags in the system. The reader maintains the key tree and keeps it secret.

To enable concurrent authentication for multiple tags, the authentication of MAP contains two phases, anticollision of multiple tags and authentication of individual tags. During the former phase, tags return one-bit responses to the reader. If more than one branch replies, the reader splits the entire tree (or a branch of the tree) into two subtrees (or subbranches). The reader then informs the tags on one subtree (or subbranch) to continue performing the MAP protocol, and the tags on the other subtrees (or subbranches) to hold.

For each subtree (or sub branch), the reader recursively executes the MAP protocol. When arriving at a leaf node in the virtual tree, MAP launches its authentication component, in which the reader mutually authenticates a tag.

After a successful mutual authentication between the reader and a tag, the keys of the tag will be updated and hence synchronized at both the tag and the reader. When updating the keys, MAP employs a cryptographic hash function with the current key and two random nonces as inputs to generate a new key.

In addition, MAP provides maintenance function to deal with tags' joining and leaving. Utilizing this component, the expired tags can also be renewed.

4.2. System Initialization

MAP employs a sparse tree, denoted as S, to initialize and maintain the keys for all tags. We use δ and d to denote the branching factor (2 for binary tree) and depth of S, respectively. For the simplicity of explanation, we choose the branching factor of 2. As shown in Figure 1, assuming there are N tags $\{T_i\}$ , $1\le i\le N$ , and a reader R, in the RFID system, the reader R assigns N tags to N leaf nodes in S. In the key tree, each virtual node except the root contains a secret key. As a result, each tag has d keys, which form a path from the root of the responding leaf node in S. Initially, each key is randomly generated. The cryptographic hash function used by R and all tags is $h(·)$ . A counter $c_p$ is stored in each tag, recording the anticollision sequence of the tag. Each tag $T_i$ also has a timestamp timestamp _i .

When initializing a tag $T_i$ , R first dispatches d keys to $T_i$ and sets the $c_p$ of $T_i$ to 0. R also sets the value of an internal counter $c_0$ = 0. The counters denote the “holding” sequence for later remounting. The keys are corresponding to a path from the root of S to the tag. For example, in Figure 1, the keys stored in tag $T_1$ are $k_{\mathrm{1,0}}$ , $k_{\mathrm{2,1}}$ , and $k_{\mathrm{3,2}}$ . We denote the secret keys of $T_i$ as ( $k_1^i,k_2^i,\dots ,k_d^i$ ). We define $k_x^i$ as the xth key of $T_i$ , corresponding to the depth x.  R then sets the timestamp _i of $T_i$ to the current time.

4.3. Tags Authentication

The tags authentication of MAP is different from existing protocols. This component has two phases: anticollision of multiple tags and authentication of individual tags, as illustrated in Algorithm 1. On the reader side, the corresponding authentication is recursively executed on the key tree, as performing a depth-first-search (DFS). This is supported by the remount subcomponent.

Algorithm 1: Tags authentication in MAP.

//Anti-collision sub-component.

// At non-leaf depth $x-1$ :

R randomly selects a branch, sends ( $r_y$ , $P_C$ , $V_C^{\prime }$ , $c_y$ );

R records ( $c_y,\hspace{0.17em}x-1$ ), $c_y$ ++;

Tags which match $V_C^{\prime }$ choose time slot ${\left(h\left(k_x^i,r_y\right)\right)}_{P_C}$

Tags not match wait and record $c_y$ in $c_p$ ;

Go to depth x;

// Authentication sub-component plus updating.

if $x=d$  // At leaf level:

  R sends a timestamp $R_1$ to $T_i$ ;

   $T_i$ checks $R_1$ and delay $t_{\max }$ /( $threshold-R_1+1$ );

   then replies ( $R_2$ , I), where $I=h(1,\hspace{0.17em}{k}_d^i,\hspace{0.17em}{R}_1,\hspace{0.17em}{R}_2)$ ;

  R computes a hash value for $T_i$ to check I;

  if match

    R accepts $T_i$ , and sends $M=h(2,\hspace{0.17em}{k}_d^i,\hspace{0.17em}{R}_1,\hspace{0.17em}{R}_2)$ ;

    R updates $k_d^i$ to $h(3,\hspace{0.17em}{k}_d^i,\hspace{0.17em}{R}_1,\hspace{0.17em}{R}_2)$ ; // update R

  else if not match

    R sends M as a random number; // if match

   $T_i$ gets M and computes a value to check M;

  if M matches the computed value by $T_i$

     $T_i$ accepts R;

     $T_i$ updates $k_d^i$ to $h(3,\hspace{0.17em}{k}_d^i,\hspace{0.17em}{R}_1,\hspace{0.17em}{R}_2)$ ; // update $T_i$

  // Remount

  R chooses the max $c_{y^{\prime }}$ stored, as $c_{\max }$ in ( $c_{y^{\prime }}$ , $po{s}_{y^{\prime }}$ );

  While exists such $c_{\max }$

    R sends to tags ( $c_{\max }$ , $r_{y^{\prime }}$ , $P_C$ );

     $T_j$ with $c_{\max }$ chooses slot $(h(k_{x^{\prime }+\mathrm{1}}^j,r_{y^{\prime }}){)}_{P_C}$ ;

    R deletes the pair stored related to $c_{\max }$ ;

    R continues to tags-authentication at

    depth $x^{\prime }+1$ in the sub-tree which roots at $po{s}_{y^{\prime }}$ ;

4.3.1. Anticollision

The anticollision process starts from the root of the key tree. At each virtual node, the reader R conducts one round of communication with the tags in its detecting range. In the anticollision process, prior works usually require a tag to respond with the whole hash value computed using its key and ID. Instead, MAP requests the tag to reply with only ONE bit in each round of interaction, as illustrated in Figure 3. The requested bit is in the highest position of those bits that differ. Algorithm 1 illustrates the interactive communication. We use $P_C$ to denote the highest position of the possible collision bits and $V_C$ to denote the value of bit on this position. Since the outputs of cryptographic hash function in MAP are 64 bits long hash values, the length of $P_C$ can be 6 bits. The whole anticollision is executed in S as follows.

At each non leaf depth $x-\mathrm{1}$ , $1\le x\le d-1$ (for the root, $x=1$ ), R has two tasks: choosing the branch denoted by $V_C^{\prime }$ for the anticollision process at level $x-2$ , which is related to a node n at level $x-1$ , and pre-computing $P_C$ using the keys on n's branches at level x. The value of $V_C^{\prime }$ is computed using the branch keys at depth $x-1$ .

To choose a branch related at depth $x-1$ , R randomly chooses a collision value $V_C^{\prime }$ based on the tags' responses, where $V_C^{\prime }$ is computed using the branch keys at depth $x-1$ . To generate $P_C$ , R creates a timestamp $r_y$ , where y is an integer counter. R uses the keys of n's two children nodes to compute two hash values in the form of $h(k_x^i,r_y)$ . R then compares these two hash values and records the highest position of the possible collision bits as $P_C$ . R then sends a query, with four parameters, $r_y$ , $V_C^{\prime }$ , $P_C$ , and $c_y$ , where $c_y$ is a counter.

Upon receiving the query, a tag $T_i$ , which responded in depth $x-2$ , checks whether the timestamp is posterior to the one it holds. If yes, $T_i$ believes the query is a new request and checks if $V_C^{\prime }$ matches its last response. If yes, $T_i$ computes $V_C$ related to $P_C$ of level x and chooses the $V_C$ th time slot to respond with bit “1.” Otherwise, if not match, $T_i$ enters the “holding” status and stores $c_y$ in $c_p$ . If more than one branch replies, R also records the pair of $(c_y,n_y)$ , where $n_y$ denotes the sibling node related to the $V_C^{\prime }$ at level $x-1$ . If $T_i$ 's timestamp is larger than the one in the query, it randomly chooses a slot to respond with bit “1.”

The anticollision is an important part of authentication process, processing multiple tags at the same time. Based on this, MAP provides multiple tags style authentication, other than sequential authentication in which the authentication procedure for each tag does not overlap.

4.3.2. Authentication

When arriving at a leaf node, R starts the authentication subcomponent with $T_i$ . R and $T_i$ authenticate each other via this subcomponent. At this point, R has exploited the path from the root to the leaf node related to $T_i$ . The subcomponent includes four steps, as shown in Algorithm 1.

(1) R sends a query to $T_i$ with the timestamp $R_1$ .

(2) Upon this query, $T_i$ checks if $R_1$ is acceptable, and delay $t_{\max }/(\text{threshold}-R_1+1)$ , where $t_{\max }$ is a predefined maximum delay and threshold, is a predefined maximum counter value. The value of $t_{\max }$ and threshold can be initialized empirically and adjusted in real application. Then $T_i$ replies with a random nonce $R_2$ and a hash value $I=h(1,R_1,R_2,k_d^i)$ .

(3) R compares I to the hash value computed using corresponding key stored in the database. If the two hash values are identical, the reader accepts the tag as a legitimate one. Otherwise, R treats the tag as illegal. For a legal tag, the reader sends $M=h(2,R_1,R_2,k_d^i)$ as an authentication message and then launches the updating component on the reader side. For an illegal tag, the reader only sends a random bit string with the same length of $h(·)$ .

Note that the key in the leaf node may not match the corresponding tag's key. In this case, R has to search through the entire database to check if a matching key can be found. If such a key is found, the tag is accepted as legitimate. In this way, even a tag which is desynchronization attacked and thus has a big timestamp can also be authenticated. This can prevent attackers from distinguishing tags by whether they can be accepted.

(4) Upon M, $T_i$ computes the hash value based on the key stored in it. If they are matched, $T_i$ takes R as a legitimate one. $T_i$ then launches the updating on the tag side if R is legitimate.

A collision may happen when two tags choose an identical leaf node. At this time, there is more than one tag responding to the reader. Their signals will collide and cannot be correctly decoded. This can happen when a tag's random choices match the path of the other tag from root to leaf. The possibility is $2^{-d}$ where d is the depth of the key tree. While the possibility is negligible, we just take these collided messages as a random message and complete the routine processes of authentication and updating. As each tag has a unique leaf key which will be updated involving the random nonces during authentication, the possibility they collide again at the leaf node will still be negligible, we will process the colliding tags in the next round of entire tags-authentication process.

4.3.3. Remount

After authentication and updating of a tag, the whole tag authentication process is remounted for unprocessed tags according to their “holding” sequence in descending order. R finds out the max counter $c_{\max }$ in the $(c_{y^{\prime }},{pos}_{y^{\prime }})$ pairs stored in the reader, where $y^{\prime }$ is an integer. If there exists such a $c_{\max }$ , R computes $P_C$ for the branches of ${pos}_{y^{\prime }}$ and starts the anticollision subcomponent in the subtree rooted at ${pos}_{y^{\prime }}$ . To do this, the reader sends a recursive query command $recQuer{y}_{y^{\prime }}$ , with $c_{\max }$ , $P_C$ , and a new timestamp $r_{y^{\prime }}$ . Upon this query, each tag checks its internal counter $c_p$ . The tags that have a matched $c_{\max }$ respond with the corresponding $V_C$ . If no such a $c_{\max }$ exists, the reader terminates the current round of MAP and launches a new round. The reader iteratively performs the authentication process until all tags are processed or the number of rounds exceeds a predefined threshold threshold. In MAP, if there are some tags moving into the detecting region of R in current round, R will treat them as newly coming tags in the next round.

We illustrate the above process by using the example of authenticating $T_1$ , $T_2$ , and $T_3$ in Figure 1. Assume the reader chooses the left branch each time. Then there is no collision at depth 0, and the entire authentication procedure goes to the subtree rooted at the node related to $k_{\mathrm{1,0}}$ at depth 1. The $V_C$ values related to keys at depth 2 will collide. R moves down to the left branch related to $k_{2,0}$ and $k_{\mathrm{3,0}}$ . R puts $T_2$ and $T_1$ in a holding state at this point. R also records the anticollision sequence and the node related to $k_{\mathrm{2,1}}$ . As there is no more collision for $T_3$ , R completes the authentication of $T_3$ and goes back to the holding tags. R requests $V_C$ related to the keys at depth 3. The responses of $T_2$ and $T_1$ fall in different branches. Then R puts $T_2$ to holding state and authenticates $T_1$ . After that, the reader R authenticates $T_2$ .

4.4. Updating

After a successful mutual authentication between the tag and reader, the updating process follows, as illustrated in Algorithm 1. MAP only updates the leaf keys for multiple tags environments, where a leaf key is the key on the leaf node. There are two reasons. First, in our protocol the keys on nonleaf nodes are only used for navigation. Second, as analyzed in [22], updating keys for tags without changing the sharing relationship of keys among tags will not increase the difficulty for adversaries to successfully conduct compromising attacks. We also allow a tag to be renewed in the system maintenance component, as an updating method which also updates the tag's location and the corresponding keys in the virtual tree for better privacy.

R updates the keys for a tag after a successful authentication of the tag. At the corresponding leaf node, a new leaf key is generated as ${k_d^i}^{\prime }=h(3,R_1,R_2,k_d^i)$ for $T_i$ . $T_i$ updates its leaf key only after a successful authentication of R by checking M.

4.5. System Maintenance

Users may want to insert, renew, or withdraw their tags. The system maintenance component deals with these requests.

If a new tag joins in the system, R initializes it by assigning it to an empty leaf node and generates the necessary keys for it. If a tag is withdrawn, R simply deletes the information on corresponding nodes related to the tag from S.

We also allow a tag to be renewed for better security and privacy. The permission is controlled by the manager. When a tag is permitted to be renewed, it is first withdrawn by the reader. Then the reader treats the tag like a new one and inserts it into the system. After being renewed, the new keys and related path in the key tree have no relation with the old ones.

5. Performance Analysis

In this section, we analyze the performance of MAP, considering both communication and computation costs. We theoretically analyze the costs and give the corresponding upper bound, lower bound, and mean value. We also launch a simulation. Then we compare the performance of MAP with two combination solutions.

5.1. Theoretical Analysis

In MAP multiple tags are authenticated concurrently; thus, we care about the average time costs derived from costs for all tags divided by the number of tags. In Section 5, when we mention a cost for each tag, we are meaning such an average time cost for each tag.

There are cases when the tags to be authenticated cover the least branches. Then paths of these tags cover a full subtree and a single path from the root of this subtree to the root of system tree S, as $T_1$ and $T_2$ in Figure 4(a). In these cases, arbitrations and hash computations are shared by the most tags. Thus it is possible that both the communication and compute cost for each tag are the least in these cases.

Figure 4

The different sharing scenarios.

Contrarily, when the tags cover the most branches, respecting no path being shared, as $T_3$ itself in Figure 4(b), then it is possible that both communication and compute cost for each tag are the largest, as arbitrations and hash computes are shared by the least tags.

For theoretic comprehensibility, we consider time cost for transferring hash values in communication cost. For compute cost, we consider only cost for computing hash values at both reader end and tag end. For the overall cost considering overheads, we give a simulation result in Section 5.2.

When tags cover the least branches, the minimum communication and compute cost are computed as follows. Theoretically, they are the lower bound of MAP in terms of time cost. Indeed, both of them are in O(1) complexity:

$$\begin{array}{cc}& \text{Com}{\text{m}}_{\min }=t_{\text{auth}}+\mathrm{2}{t}_{\text{query}}+t_{\text{reply}}-\frac{\left(t_{\text{query}}+t_{\text{reply}}\right)}{N}\\ \approx t_{\text{auth}}+2t_{\text{query}}+t_{\text{reply}},\\ {\text{Comp}}_{\min }=\left(2-\frac{1}{N}\right)t_{t\mathrm{comp}}+\left(3-\frac{2}{N_A}\right)t_{r\mathrm{comp}}\\ \approx 2t_{t\mathrm{comp}}+3t_{r\mathrm{comp}},\end{array}$$

(1)

where the d is the height of the system tree S, N is the number of tags in the system, $N_A$ is the number of tags to be authenticated and $N_A=N$ in this case, $t_{\text{query}}$ is the time for a reader R to send out a query, $t_{\text{reply}}$ is the time for each tag on both branches to reply their related 1 bit $V_C$ values in the two time slots, $t_{\text{auth}}$ is the time for a tag to send the hash value of its leaf node, $t_{t\mathrm{comp}}$ is the time for a tag to compute a hash value, and $t_{r\mathrm{comp}}$ is the time for R to compute a hash value. Note that we suppose sending the request commands needs the same time as the $t_{\text{query}}$ .

When each tag covers the most branches, there is only one tag to be authenticated. Thus, we get the maximum costs. We denote the maximum communication and compute cost as ${\text{Comm}}_{\max }$ and ${\text{Comp}}_{\max }$ , respectively. The theoretical upper bound cost of MAP is given by

$$\begin{array}{cc}& {\text{Comm}}_{\max }=t_{\text{auth}}+d\times t_{\text{reply}}+\left(d+\mathrm{1}\right)t_{\text{query}},\\ {\text{Comp}}_{\max }=\left(d+1\right)t_{r\mathrm{comp}}+\left(2d+1\right)t_{r\mathrm{comp}},\end{array}$$

(2)

where d is the height of the system tree S. We can find that both the maximum costs have an $O(\log N)$ complexity.

When tags cover all branches, supposing the cover probability is unique, we get the mean communication and computing costs as follows:

$$\begin{array}{l}{\text{Comm}}_{\text{mean}}=t_{\text{auth}}+t_{\text{query}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\left(t_{\text{query}}+t_{\text{reply}}\right)\left(2+d-{\log }_2{N}_A-\frac{1}{N_A}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\approx t_{\text{auth}}+t_{\text{query}}+\left(t_{\text{query}}+t_{\text{reply}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \left(2+d-{\log }_2{N}_A\right),\\ {\text{Comp}}_{\text{mean}}=\left(2+d-{\log }_2{N}_A-\frac{1}{N_A}\right)t_{t\mathrm{comp}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+2\left(1+d-{\log }_2{N}_A-\frac{1}{N_A}\right)t_{r\mathrm{comp}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\approx \left(2+d-{\log }_2{N}_A\right)t_{t\mathrm{comp}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+2\left(1+d-{\log }_2{N}_A\right)t_{r\mathrm{comp}}.\end{array}$$

(3)

Both Comm_mean and Comp_mean are strict monotonic functions of $N_A$ . When $N_A$ is big enough, they approach the constant value of $O(1)$ .

Considering the minimum authentication cost, without anticollision or updating, for a single tag in traditional tree-based protocol, it will need to compute, transmit, and verify at least ${\log }_{\delta }N$ ciphers, where δ is the branching factor of the key tree. When the tag lies at the first-reach leaf, the cost is minimum with message length and computation times of about ${\log }_{\delta }N$ . When the tag lies at the last-reach leaf, the cost is maximum with the computation times enlarged to about $\delta \times {\log }_{\delta }N$ . The average computation cost is about $(1+\delta )/2\times {\log }_{\delta }N$ . Thus, MAP protocol outperforms the traditional tree-based protocol theoretically.

5.2. Simulation

We compared the average processing time of MAP to two simple combination solutions. Both the two solutions use the slot-count (Q) selection algorithm in EPC C1G2 UHF Air Interface Protocol Standard [31] for anticollision. The PPA protocols for these two solutions are the typical tree-based protocol [20] and RWP protocol [22] with O(1) complexity. In all protocols, both tag side and reader side employ SQUASH (SQUaring haSH), which is proposed by Shamir in [8], to compute hash values. SQUASH needs only several hundred gate equivalents (GEs) and is appropriate for low cost RFID tags. We consider the overall time cost including communication cost and search cost. The communication cost includes the cost for transmitting commands and data with overheads such as wait time, time out, frame sync, and preamble. Note that, compared to other kinds of wireless communication such as WiFi, the messages exchanged between the reader and tags are very short. Thus, the overheads are not negligible. All the command formats, data formats, and link timing follow the standard. In search cost, we consider compute cost for hash values by both reader and tags. We assume the reader can process 2²³ times 64 bits SQUASH in a second in average. For the tag, we assume it can process one time SQUASH in 67.75 us and 242 us. We make these two assumptions based on the link timing requirements specified in the standard.

In our simulation, the forward data rate is 40 Kbps and the backward data rate is 320 Kbps. We suppose that there are 2²⁰ tags in the system. We choose tags randomly and repeat the whole process 100 times for average results.

In Figure 5, we give the result for 1000 tags. The simulation result shows that MAP gains a better efficiency than typical tree-based protocol. The average time cost of tree-based protocols is about 2.2 times to 4.2 times that of MAP. The efficiency of MAP asymptotically approaches the RWP protocol with O(1) complexity as the size of the tag set approaches 1000. The simulation result is in accordance with the theoretical analysis. That is because in MAP computing and communication are shared between all tags. Moreover, during anticollision subcomponent tags respond with only 1 bit to save communication cost. That is why MAP outperforms typical tree-based protocol when tag size is small.

Figure 5

Comparison on performance for 1–1000 tags.

According to the performance result in [26], for 1000 tags in a system with 10⁵ tags at 40 Kbps forward rate, achieving 1% erroneous decision, the SEBA approach [25] needs 41 minutes, while the SEBA+ approach [26] needs about 4 minutes. Utilizing MAP, it takes about 1000 × 10^4.05 × 10⁻⁶ s = 11.22 s. which is less than SEBA and more than SEBA+. However, the result in [26] considers only the message transmission time, leaving out the nonnegligible computation time and the communication overheads such as wait time, time out, frame sync, and preamble. Moreover, MAP provides accurate authentication with no error probability. Thus, MAP is a good choice in performance for the authentication of multiple tags.

6. Security and Privacy Analysis

In this section, we analyze the security and privacy characters of MAP. Because our approach is tree based, we focus on resistance to compromising attack which has the most serious impact on conventional tree-based approaches [23]. We prove that MAP is m-strong-ind-private, showing that MAP satisfies strong privacy protection in multiple tags scenario. We also show the abilities of MAP in terms of confidentiality, cloning resistance, tracking resistance, timing-based attack resistance, and forward secrecy.

6.1. Compromising Attack

Compromising attack is the most effective way for crashing tree-based protocols. That is because tags organized in tree-based structures share keys with each other. When an adversary A compromises some tags and thus obtain their secret keys, A can deduce the secret keys of other tags. In conventional tree-based protocols, a legitimate reader splits a tag from other possible ones level by level and finally authenticates it on the leaf, using its keys on related levels. An adversary can also distinguish tags and further track them in this way with keys from the compromised tags. For detailed analysis, please refer to [14, 21].

Our analysis is based on the works in [10, 14, 18, 21, 23, 34]. The notion of strong ind-privacy defined in [23], which is equivalent to the destructive-privacy defined in [34], is very similar to the strong privacy provided by MAP, except that MAP focuses on privacy protection for multiple tags. The existing privacy models are designed for one-tag-one-reader authentication scheme and focus on distinguishability privacy between TWO tags only. They are not fit for the multiple tags scenario in MAP, where the reader cannot communicate to a tag before anticollision subcomponent.

We define a new model for multiple tags environments, including four oracles, Request(·, ·, ·), Send(·,·), Relay(·,·), and Compromise(·) to formulate the attacks to the tag sets and reader. Assume we have a tag set $N_S$ . Any attack on R or $N_S$ can be represented by calling on its oracles.

Request( $N_S,m_1,m_3$ ): A queries the tag set $N_S$ by a query message $m_1$ and receives the responses. Then A sends another message $m_3$ to $N_S$ , including the collision arbitration and R's authentication data.

Send(R, $m_2$ ): A sends a message $m_2$ , representing the tag set's reply and authentication messages, to R and receives a response.

Relay( $N_S$ , R): A relays the messages between $N_S$ and R. A can arbitrarily modify the messages from one side to another.

Compromise( $N_C$ ): A compromises tags in set $N_C$ and obtains their secret keys, where $N_C$ is a tag set A obtains. The compromised tags are broken and cannot be used any further.

The compromising attack on MAP, denoted by ${\text{CA}}_A^{\text{MAP}}[k_0,N_A]$ , is performed with the following steps.

Step 1.

The adversary A compromises $k_0$ tags and obtains their secret keys.

Step 2.

A chooses a target tag T that has not been compromised. A can query T or act as a man-in-the-middle between T and the reader R polynomial times. Note that A cannot compromise T. According to the secret keys A gains in Step 1, A can compute outputs of these keys and compare to them T's outputs. In this way A can determine which of T's keys equal to A's known keys.

Step 3.

The system gives a tag set $N_S$ with $N_O$ tags, including T. Then $N_S$ is divided into two subsets $N_{S,1}$ and $N_{S,2}$ . For the simplicity we assume each subset contains $N_A$ tags. Or else we can define the smaller set contains $N_A$ tags, which will not affect the result of analysis but complex the analysis process. A randomly picks a subset $N_{S,b}$ , where b = 0 or b = 1, and determines if T is in this subset. A can pick both subsets. If $N_{S,b}$ contains T, A can proceed tracking T by tracking $N_{S,b}$ , otherwise $N_{S,(\mathrm{1}-b)}$ . A can send queries to the tag set or act as a man-in-the-middle between the tag set and the reader R polynomial times, but cannot compromise those tags.

We denote

$$\begin{array}{cc}& P_{\text{MAP}}=P_r\left[{\text{CA}}_A^{\text{MAP}}\left[k_0,N_A\right]=1\right]\end{array}$$

(4)

as the possibility A definitely knows whether tag set $N_{S,b}$ includes T. A succeeds if A definitely knows which tag set includes T. Then the possibility that A succeeds is

$$\begin{array}{cc}& P_{\text{MAP}}=P_r\left[{\text{CA}}_A^{\text{MAP}}\left[k_0,N_A\right]=1\right]=1-{\left(1-P_0\right)}^2,\end{array}$$

(5)

where $P_0$ is the possibility that A succeeds in either subset in a system employing MAP.

Definition 1.

The advantage of adversary A in the compromising attack is defined as

$$\begin{array}{cc}& {\text{adv}}_A^{\text{MAP}}\left(k_0,N_A\right)=\left|\left(P_{\text{MAP}}+\frac{1}{2}\left(1-P_{\text{MAP}}\right)\right)-\frac{1}{2}\right|=\frac{P_{\text{MAP}}}{2},\end{array}$$

(6)

where the probability is the advantage of A correctly guess against randomly guess which subset T is in.

Definition 2 (M-strong $(\epsilon ,k_{\mathrm{0}},N_A)$ -ind-privacy).

An RFID protocol PRO is m-strong( $\epsilon ,k_0,N_A$ )-ind-private if when $N_A$ approaches N, the advantage ${\text{adv}}_A^{\text{PRO}}(k_0,N_A)$ is at most ε in polynomial time. Where $N_A<N$ , ε is an infinitesimal when N approaches infinity.

M-weak(ε, $k_{\mathrm{0}}$ , $N_A$ )-ind-privacy is defined the same as m-strong $(\epsilon ,k_0,N_A)$ -ind-privacy except that $k_{\mathrm{0}}$ = 0.

The above two privacy notions can be simply denoted as m-strong-ind-privacy (MSIP) and m-weak-ind-privacy (MWIP), where the letter “m” is the abbreviation of multiple tags. When $N_A$ = 1, the MSIP (MWIP) equals the strong-privacy (weak-privacy) in Juels's model [23] and the destructive-privacy (weak-privacy) in Vaudenay's model [34]. At this time, the case of a tag lying in a set is identical to the case of the target tag being a particular tag in traditional privacy model with two tags. Thus, our multiple tags privacy model is a generalized version of existing privacy models [23, 34]. On the contrary, the existing privacy models are special cases of multiple tags privacy where each tag set has only one tag. Then, we can define 8 different levels of privacy, by generalizing Vaudenay's model for multiple tags scenarios, as illustrated in Figure 6.

Figure 6

The privacy levels.

The above model is dedicated for classifying the privacy protection in multiple tags scenarios. Intuitively, it is easier for a tag to hide in a set than to behavior indistinguishably to another tag. Thus, the above model is a model weaker than the privacy models for one-reader-one-tag scenarios.

However, if the authentication protocol does not take this advantage, then the protocol cannot provide better privacy in scenarios with multiple tags than in one-reader-one-tag scenarios, no matter how many tags are there to be authenticated. For example, in the OSK [12] protocol, one desynchronized tag cannot be accepted by a legitimate reader. Thus, a desynchronized tag can still be distinguished in a tag set, saying nothing of hiding in the set. As a result, the OSK method cannot provide m-strong-ind-privacy or m-weak-ind-privacy.

In the tree for MAP, when A is not aware of all keys in both branches, A does not know the $P_C$ and has to randomly guess one for navigation and conduct the searching process. When the guess fails, A sends out a position that has no collisions. Then A cannot split the tags. Only when A knows all the keys in the branches related to T, A can send out the correct $P_C$ and proceed on tracking. That is the main reason why MAP performs better than traditional tree-based protocols in defending against compromising attacks. In fact, the MAP protocol is m-strong-ind-private as will be proven in the bellowing.

Theorem 3.

The MAP protocol is MSIP private.

Proof.

We perform the compromising attack with MAP protocol as follows.

We denote tags in $N_{S,b}$ by $T^{\prime }$ . We denote keys in T and $T^{\prime }$ with ( $ke{y}_0,ke{y}_1,\dots ,ke{y}_d$ ) and ( $ke{y}_0^{\prime },ke{y}_1^{\prime },\dots ,ke{y}_d^{\prime }$ ), respectively, where d is the depth of the tree. Considering at level x where $ke{y}_x$ is in a subtree, we use $K_x$ to denote the set of known keys by A in this subtree, and $k_x$ to denote the number of keys in $K_x$ . And $k_0$ is the number of tags compromised. There are three cases to be considered at level x.

Case 1. A does not succeed in previous $x-1$ levels, and there is exactly one key $ke{y}_x^{\prime }$ equal to $ke{y}_x$ . A definitely knows $N_{S,b}$ includes T. The possibility is

$$\begin{array}{cc}& P_r\left(C_x^1\right)=\prod _{j=0}^{\delta -1}\left(\frac{{\delta }^{x-1}{k}_x-j}{{\delta }^x-j}\right)\times \frac{k_x}{\delta }\times \frac{1}{{\delta }^x}\times {\left(1-\frac{1}{{\delta }^x}\right)}^{N_A-1}.\end{array}$$

(7)

Case 2. A does not succeed in previous $x-1$ levels, and there's no key $ke{y}_x^{\prime }$ equals to $ke{y}_x$ . A definitely knows that $N_{S,b}$ does not include T. The possibility is

$$\begin{array}{cc}& P_r\left(C_x^2\right)=\prod _{j=0}^{\delta -1}\left(\frac{{\delta }^{x-1}{k}_x-j}{{\delta }^x-j}\right)\times \frac{k_x}{\delta }\times {\left(1-\frac{1}{{\delta }^x}\right)}^{N_A}.\end{array}$$

(8)

Case 3. A does not succeed in previous $x-1$ levels, and more than one key $ke{y}_x^{\prime }$ equals $ke{y}_x$ . In this case, A fails at level x and should move to level $x+1$ . The possibility is

$$\begin{array}{cc}& P_r\left(C_x^3\right)=\prod _{j=0}^{\delta -1}\left(\frac{{\delta }^{x-1}{k}_x-j}{{\delta }^x-j}\right)\times \frac{k_x}{\delta }-P_r\left(C_x^1\right)-P_r\left(C_x^2\right).\end{array}$$

(9)

The overall probability of A definitely knows whether $N_{S,b}$ includes T is

$$\begin{array}{l}{P}_0=P_r\left(C_1^1\vee C_1^2\right)+\sum _{x=2}^d\left(P_r\left(C_x^1\vee C_x^2\right)\times \prod _{y=1}^{x-1}{P}_r\left(C_y^3\right)\right)\\ \hspace{1em}={\left(1-\frac{1}{\delta }\right)}^{N_A-1}\frac{k_1}{\delta }\prod _{j=0}^{\delta -1}\frac{k_1-j}{\delta -j}\\ \hspace{1em}\hspace{1em}+\sum _{x=2}^d(\phantom{\prod _{y=1}^{x-1}\left(P\left(ke{y}_y\right)\frac{k_y}{\delta }\left(1-{\left(1-\frac{1}{{\delta }^y}\right)}^{N_A-1}\right)\right)}{\left(1-\frac{1}{{\delta }^x}\right)}^{N_A-1}\frac{k_x}{\delta }P\left(ke{y}_x\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \prod _{y=1}^{x-1}\left(P\left(ke{y}_y\right)\frac{k_y}{\delta }\left(1-{\left(1-\frac{1}{{\delta }^y}\right)}^{N_A-1}\right)\right)),\end{array}$$

(10)

where

$$\begin{array}{cc}& P\left(ke{y}_x\right)=\prod _{j=0}^{\delta -1}\frac{\left({\delta }^{x-1}{k}_x-j\right)\left(\delta -j\right)}{{\left({\delta }^x-j\right)}^2},\\ k_1=\delta \left(1-{\left(1-\frac{1}{\delta }\right)}^{k_0}\right),\\ k_x=\delta \left(1-{\left(1-\frac{1}{\delta }\right)}^{g\left(k_x\right)}\right),\hspace{1em}\left(2\le x\le d\right),\\ g\left(k_x\right)=k_0\prod _{y=1}^{x-1}\frac{1}{k_y}.\end{array}$$

(11)

The possibility A succeeds in either subset is $P_0$ which is a monotonically decreasing function of $N_A$ , so is $P_{\text{MAP}}$ . The advantage of A is $P_{\text{MAP}}$ , which decreases exponentially to 0 as $N_A$ increases to be big enough.

Considering that $k_x\le \delta$ and $\delta \ge 2$ , we have the following derivations:

$$\begin{array}{l}{\left(1-\frac{1}{\delta }\right)}^{N_A-1}\frac{k_1}{\delta }\prod _{j=0}^{\delta -1}\frac{k_1-j}{\delta -j}\\ \hspace{1em}\hspace{1em}\le {\left(\frac{1}{2}\right)}^{N_A-1}\frac{k_1}{\delta }\frac{k_1}{\delta }\frac{k_1-1}{\delta -1}\\ \hspace{1em}\hspace{1em}\le {\left(\frac{1}{2}\right)}^{N_A-1},\\ \prod _{y=1}^{x-1}\left(P\left(ke{y}_y\right)\frac{k_y}{\delta }\left(1-{\left(1-\frac{1}{{\delta }^y}\right)}^{N_A-1}\right)\right)\\ \hspace{1em}\hspace{1em}<\prod _{y=1}^{x-1}\left(P\left(ke{y}_y\right)\times 1\times 1\right)\\ \hspace{1em}\hspace{1em}=\prod _{y=1}^{x-1}P\left(ke{y}_y\right).\end{array}$$

(12)

Then, we have the following deduction:

$$\begin{array}{l}{P}_0<{\left(\frac{1}{2}\right)}^{N_A-1}\\ \hspace{1em}\hspace{1em}+\sum _{x=2}^d\left({\left(1-\frac{1}{{\delta }^x}\right)}^{N_A-1}\frac{k_x}{\delta }P\left(ke{y}_x\right)\prod _{y=1}^{x-1}P\left(ke{y}_y\right)\right)\\ \hspace{1em}<{\left(\frac{1}{2}\right)}^{N_A-1}+\sum _{x=2}^d{\left(1-\frac{1}{{\delta }^x}\right)}^{N_A-1}\\ \hspace{1em}<{\left(\frac{1}{2}\right)}^{N_A-1}+d{\left(1-\frac{1}{{\delta }^2}\right)}^{N_A-1}.\end{array}$$

(13)

The right part of the inequality is a monotonically decreasing function of $N_A$ . For example, it can be deduced that $P_0<{(1/2)}^{N_A-1}+d{(3/4)}^{N_A-1}$ , when $\delta =2$ . Then, $P_0$ is an infinitesimal as $N_A$ approaches N, so is $P_{\text{MAP}}$ . According to Definition 2, MAP is m-strong-ind-private.

Assume a RFID system of 2²⁰ tags with $\delta =2$ and $d=20$ . Figure 7 demonstrates possibilities A successfully tracks a tag by compromising 200 tags, employing MAP or tree-based protocol such as [20].

Figure 7

Comparisons on defending against compromising attack.

We can find that for both protocols the possibilities that A succeeds reduces when $N_A$ increases. For MAP, the possibility reduce rapidly, while for traditional balance tree-based PPA it reduces slowly. For MAP protocol, when $N_A>8$ , $P_{\text{MAP}}<0.05$ , saying A can definitely distinguish and know which tag set includes T with low possibility even the set size is small. This is an acceptable result as environments with at least 8 tags are common. Moreover, the successful tracking probability asymptotically approaches to 0 as the size of the tag set to be authenticated arises. For tree-based protocol, A always has a successful possibility larger than 0.8 with tag set size smaller than 200.

6.2. Confidentiality

In MAP, all information from a tag is sent as the value of a cryptographic hash function or a part of such a hash value. According to the preimage resistance property of cryptographic hash functions, the adversary cannot know the origin information.

6.3. Cloning Resistance

In cloning attack, an adversary records responses from a tag and replay them to fool legitimate readers. In MAP, the $V_C$ values are only used for navigation and each tag uses its unique leaf key for the final authentication. The tag generates the hash values of the leaf key with a timestamp from R and a nonce from the tag as inputs. Both the timestamp and the nonce are the session tokens of the conversation. Therefore, authentication messages from a given tag will change in different conversations due to the different session tokens. The navigation bits can be replayed; however, they cannot help to fool R because the adversary does not know the authentication message at the leaf node. The replayed messages cannot be acceptable by legitimate readers according to the protocol.

6.4. Tracking Resistance

In Section 6.1, we focus on tags' path keys and present that MAP can resist compromising attack in scenarios with multiple tags. For any leaf key, it uniquely belongs to an individual tag. The adversary A never knows a tag's leaf key unless compromising it. When performing authentication subcomponent, a tag computes a hash value with its leaf key and the session tokens. This authentication message varies each time, and A cannot link the messages to a tag without knowing its leaf key.

MAP resists against compromising attack in multiple tags scenarios. However, when a batch only has a few tags, $P_{\text{MAP}}$ is not negligible. According to the results shown in Figure 7, when the number of tags is larger than 8, the probability of multiple tags exposing to attackers will not exceed 0.05, which is acceptable for most RFID applications. Therefore, we recommend to select MAP when the number of tags is larger than 8, otherwise choosing time consuming per-tag authentication to prevent the tracking attack.

An adversary A may launch the Denial of Service (DoS) attack between a legitimate reader and tags. In this attack A firstly exhausts the timestamp in a tag. Then A can relay the tag's response to a legitimate reader to see if the tag is accepted and further track the tag by observing the result. This attack is not feasible to MAP because desynchronized tags can also be accepted employing MAP, as presented in Section 4.3.2. Besides, we recommend the system to thwart the response speed of the tags which are under attack. Then, a counter with an acceptable bit length is enough to avoid the timestamps of the tags run over a predefined threshold.

6.5. Timing-Based Attack Resistance

An adversary may time the processing cost of a tag to identify the status of this tag and further distinguish it from other tags [35]. This kind of attack is a new general attack which can even break the privacy of proven private RFID authentication protocols. MAP can defend against such attack. The reason is that the authentication process for each tag in MAP corresponds to the same procedure. From root to leaf, each branch selection corresponds to no sequential computation of tags. Instead, the tags do concurrent computation at each level. In this way, the observable behavior of each tag is hard to distinguish. The problem in traversing the traditional binary tree, which causes different searching cost, does not happen in MAP. On the other hand, the thwart method used in MAP does not raise rapid increase in the response. Thus, the thwarted tag's behavior is hard to distinguish, especially when the tag set is large and the predefined threshold is big enough.

6.6. Forward Secrecy

An adversary A can record the messages sent by R or tags. And A can compromise tags to obtain their current keys. Forward secrecy requires that the information in previous messages will never be revealed. In MAP, the leaf keys are updated after each successful authentication. The forward secrecy is thereby guaranteed. For the nonleaf keys, they are not used for data transfer but only for navigation. In addition, they will be updated when a tag is renewed. Thus, MAP does not update the nonleaf keys at each authentication and such a process does not damage the forward secrecy.

7. Possible Variants and Improvements

The storage requirement of MAP for a system larger than 2¹⁶ tags may be larger than 1 k bits. This cost is practical for nowadays RFID tags. For ultra-low storage, path keys can be computed employing SQUASH with the unique leaf key and identifier of the tag as inputs. This would decrease the storage requirement to $O(1)$ but double the average computation time. It can be easily deduced that the performance of MAP is still better than the tree-based protocol in large-scale systems.

MAP focuses on the interaction between tags and reader, as well as reader-server side search accelerating. On the other hand, the SEBA [25, 26] like protocols focuses on the reader-to-server communication, as well as the server side probabilistic verification. Thus, a possible future work is to combine and gain profit from both of the two styles of multiple tags protocols.

8. Conclusions and Future Work

In this work we propose a Multiple tags privacy-preserving Authentication Protocol, MAP, to authenticate multiple tags concurrently. By enabling anticollision functionality in authentication process, MAP eliminates the redundant efforts wasted in anticollision processes and authenticating tags. Tags in MAP respond concurrently with 1 bit to conduct the authentication for better privacy. MAP is m-strong-ind-private, which is a variant of ind-privacy we define for multiple tags scenarios. MAP can effectively mitigate the impact of compromising attack, in multiple tags scenarios, to an acceptable extent. Employing MAP, the successful tracking probability of adversaries for tag set larger than 8 is below 0.05 and will deduce rapidly to 0 as the size of the tag set enlarges. The efficiency of MAP is better than $O(\log N)$ and asymptotically approaches $O(1)$ as the number of tags in the tag set to be authenticated increases, as proven in theoretical analysis and shown in the simulation. The proposed protocol in our work, MAP, is dedicated for authenticating multiple tags. One prospective direction may be building protocols for both single tag and multiple tags to provide high efficiency and strong privacy at the same time.