Sage Journals: Discover world-class research

Abstract

EPCglobal network is used to share product data between trading partners, which was proposed by EPCglobal. Object Name Service (ONS) in EPCglobal framework raises two critical security risks: the authenticity of IP addresses for Physical Markup Language (PML) servers and the privacy of Electronic Product Codes (EPCs). Existing work considers either the IP address authentication or the EPC privacy. In addition, that work mainly relies on cryptographic tools, in which key distribution is not a trivial task and also causes a large amount of computation overhead. In this paper, we make the first attempt to solve those two security risks together without relying cryptography. We propose a scheme, namely, APP (authenticate ONS and protect EPC privacy), to guarantee the authenticity of IP addresses for PML servers as well as EPC privacy and to maintain ultralightweight computation cost. Moreover, we give formal definition of the authenticity and the privacy in ONS context. The security achievements are strictly analyzed and proved. The extensive analysis results justify the applicability of the proposed scheme.

1. Introduction

EPCglobal is a typical network framework for the Internet of Things (IoT), machine to Machine (M2M), and RFID networks. It has been envisioned as a key method to recognize, locate, and trace EPC-enabled physical objects (e.g., RFIDs or sensors). Moreover, it is used to facilitate supply chain management, food trace back, logistics, and so forth.

Concretely, EPCglobal relies on Object Name Service (ONS) to map Electronic Product Code (EPC) to an IP address of a server. The server, called Physical Markup Language (PML) server in EPCglobal, provides detailed product information of the EPC. To do so, an EPC tag reader obtains EPCs from tags and submits the EPCs to ONS. Based on the received EPCs, ONS returns the IP address of the corresponding server. Generally speaking, the architecture of ONS consists of distributed server systems and can support iteratively query for scalability and flexibility.

ONS architecture raises two security concerns: one is the authenticity of returning results. If the returning results are fake, the product information will be detoured to a forged server with garbage information. The other is the privacy of EPC. If EPC is revealed by ONS server, the user's privacy may be damaged. For example, a user looks up an EPC for a bottle of medical tablets that is privacy sensitive. Unfortunately, above security risks have not been largely recognized, and rare works exist to address both risks at the same time.

Currently, a few works use some similar methods for DNS security [1], rely on Public Key Infrastructure (PKI) [2], or depend on P2P architecture [3]. Those solutions experience many difficulties: The schemes relying on cryptography usually induce extensive computation overhead. The key distribution and management issues raise many deployment hurdles. The assumption of existing PKI is unrealistic in the current situation. Some solutions such as P2P solution require the migration of underlying network architecture. In addition, all schemes can only solve either of the aforementioned security concerns and not both. Moreover, as smartphones start to equip RFID reader function, the EPC reader will become portable. To save the power consumption of such hand-held devices, ultralightweight solutions are desired.

In this paper, we propose an ultralightweight solution to authenticate the ONS record and protect the user's privacy without cryptography. In addition, we strictly prove its security strength in terms of authenticity and privacy. Moreover, we adapt a formal and rigorous method to state, present, and analyze the security goals. That is, we formulate the definition of authenticity and privacy in EPCglobal. We formally prove the achievement of proposed scheme with respect to authenticity and privacy strength. All presentations strictly follow the formal expressions for better clarity and rigorous generality.

The contributions of the paper are listed as follows. (1)

We make the first attempt to propose an ultralightweight scheme in terms of computation overhead without cryptography to solve both aforementioned problems in one solution.

(2)

We make the first attempt to strictly define authenticity and privacy in EPCglobal and provide formal proofs for the achievement of security goals.

(3)

We propose a general scheme to represent all possible solutions for the problem.

The rest of the paper is organized as follows. Section 2 gives an overview on relevant prior work. In Section 3 we discuss the basic assumption and models used throughout the paper. Section 4 provides the detailed description of our proposed models and analysis. Finally, Section 5 concludes the paper.

2. Related Work

The security in ONS starts to attract more and more attention. Fabian and Günther [4] reviewed the security challenges of the EPCglobal network. Sun et al. [2] proposed a lightweight Public Key Infrastructure (LPKI) for trustworthy ONS. They proposed to use a new encryption encode or decode strategy of EPC and improved the reliability of the certificate authority by a new multiple customer relation model. Fabian [3] and Fabian and Günther [5] proposed to use structured P2P systems with distributed hash tables (DHT) to replace ONS architecture. They found that the strength of privacy protection slightly increased by using DHT compared to DNS, but strong protection still relied on secure key distribution mechanisms. Rosenkranz et al. [1] compared two mechanisms to improve the trust level of ONS, DNSSEC and DNSCurve. DNSSEC enables integrity and authenticity; DNSCurve additionally enables confidentiality and higher availability. Their security goals are different from our paper, and ONS security cannot be achieved by DNS security enhancement with optimal performance. Schapranow et al. [6] proposed to protect the privacy of querying parties. Their module can smoothly integrate into existing network infrastructures without major efforts. Kurkovsky et al. [7] proposed to use wearable tags embedded in badges or clothing for employee's tracking at the workplace. It may hurt the privacy of employee after continuous authentication. This kind of privacy problem of RFID has been discussed in many papers [8–11]. Shi et al. [12] proposed SecDS, a secure EPC discovery service system in EPCglobal network. They developed a secure and efficient search engine (SecDS) based on EPC Discovery Services (EPCDS) for EPCglobal network. Their work is independent of ours.

3. Problem Formulation

3.1. Network Model

There exist two major entities in ONS context: requester (denoted as ℛ) and ONS server (denoted as 𝒮). The requester reads RFID tag to obtain EPC and submits it to ONS server. The ONS server subsequently returns the IP address of the server who can provide detailed product information on that EPC. The requester then consults the server with returned IP address so as to fetch the detailed product information.

Although the architecture of ONS is very similar to DNS, we observe that there still exists a major distinction between ONS and DNS: the content on the server returned by ONS for a given EPC is usually fixed and shorter than that in the server returned by DNS as it is the information for a product. The content on the server returned by DNS may be changed frequently as it is the information for a web site.

3.2. Attack Model and Trust Model

We only consider adversaries at ONS servers as the paper concentrates on the authenticity of returned records (IP addresses) and EPC privacy. The adversary is denoted as 𝒜. We point out following possible attacks.

Definition 1 (ONS pollution attack ( $𝒜_{poll}$ )).

ONS server returns a fake IP address upon being requested for an EPC. The PML server at the fake IP address provides forged product information. In shorthand,

\begin{matrix} ℛ ⟶ 𝒮 : {e p c}, \\ 𝒮 ⟶ ℛ : {i p_{e p c} | (e p c, i p_{e p c}) \notin {M A P}_{a u t h}}, \end{matrix}

(1)

where

e p c

is the requested EPC;

i p_{e p c}

is the IP address of PML server for that

e p c

;

{M A P}_{a u t h}

is an imaginary authenticated list containing correct

(e p c, i p_{e p c})

pairs.

Definition 2 (ONS leakage attack ( $𝒜_{leak}$ )).

ONS server reveals the pair of submitted EPC and requester's IP address to other third parties who are interested in them. In shorthand,

\begin{matrix} 𝒮 ⟶ * : {e p c, i p_{r}}, \end{matrix}

(2)

where * means public;

e p c

is the requested EPC;

i p_{r}

is the requester's IP address.

Definition 3 (ONS inference attack ( $𝒜_{infr}$ )).

ONS server deduces the activities related to submitted EPCs and reveals those activities and requester's IP address to other third parities who are interested in them. In shorthand,

\begin{matrix} 𝒮 ⟶ * : {a c t, i p_{r}}, \end{matrix}

(3)

where * means public;

a c t

is an activity.

ONS server is untrustworthy as we assume adversaries at ONS server are interested in the user's privacy and intend to break the authenticity. Requester must be trustworthy, as it is a prerequisite requirement for further discussion; otherwise, the discussion is meaningless and no solution exists.

3.3. Security Definition and Design Goal

Informally speaking, the authenticity is guaranteed if adversaries cannot fool the requester to believe a fake IP address. More specifically, we formally state the definitions as follows.

Definition 4 (perfect authenticity of mapping IP address ( ${A u t h}_{prft}$ )).

In shorthand, it is

\begin{array}{l} Pr {ℛ believes (e p c, i p) \in {M A P}_{a u t h} | ℛ ⟶ 𝒮 : {e p c}, \\ 𝒮 ⟶ ℛ : {i p | (e p c, i p) \notin {M A P}_{a u t h}}} = 0, \end{array}

(4)

where

Pr {A | B}

denotes the probability that A happens after event B happens. It is perfect authenticity to defend against

𝒜_{poll}

Definition 5 (computational authenticity of mapping IP address ( ${A u t h}_{cmpt}$ )).

For any probabilistic polynomial turing machine (PPTM) adversary 𝒜, given any $e p c$ , it is computationally infeasible to find $ip$ such that $(e p c, i p) \notin R$ , but let ℛ believe it is correct. In shorthand,

\begin{array}{l} Pr {ℛ believes (e p c, i p) \in {M A P}_{a u t h} | ℛ ⟶ 𝒮 : {e p c}, \\ 𝒮 ⟶ ℛ : {i p | (e p c, i p) \notin {M A P}_{a u t h}}} < n e g l (z), \end{array}

(5)

where

n e g l (z)

is a negligible function with security parameter z;

Pr {A | B}

denotes the probability that A happens after event B happens. It is computational authenticity to defend against

𝒜_{poll}

Definition 6.

Authentication attacking experiment on scheme Π defending against adversary 𝒜- ${E x p A u t h}_{𝒜, Π} (z)$ , is defined as follows. (1)

Scheme Π is executed with security parameter z in the presence of adversary 𝒜.

(2)

ℛ sends $e p c$ to 𝒮; 𝒜 at 𝒮 finds $i p$ , where $(e p c, i p) \notin {M A P}_{a u t h}$ , and sends $i p$ to ℛ. ℛ believes $i p$ is a correct $i p$ , then outputs 1, otherwise, outputs 0.

(3)

If and only if ℛ outputs 1, the experiment outputs 1.

Definition 7.

Scheme Π guarantees perfect (computational) authenticity in the presence of any (PPTM) adversary 𝒜 (denoted as ${A u t h}_{Π, 𝒜} = 1$ ), if and only if for any (PPTM) adversary 𝒜 and scheme Π, the probability that the output of authentication attacking experiment equals 1 satisfies

\begin{matrix} Pr [{E x p A u t h}_{𝒜, Π} (z) = 1] = 0 (\leq n e g l (z)), \end{matrix}

(6)

where

n e g l (z)

is a negligible function with parameter z. (In the above equation, the contents in parentheses are corresponding and present simultaneously.)

The EPC privacy defending against $𝒜_{leak}$ is guaranteed if and only if adversaries cannot know the requested $e p c$ as $i p_{r}$ is always known by adversaries at 𝒮. In this situation, $e p c$ should be either encrypted or transformed.

The EPC privacy defending against $𝒜_{infr}$ is guaranteed, if and only if adversaries cannot deduce requester's activities after viewing requested $e p c$ serials. Note that, it is impossible to hide $e p c$ from 𝒮 as $e p c$ must be known by 𝒮 to return corresponding $i p$ . Thus, the privacy requirement is to disturb the requester's activities in $e p c$ serials. More specifically, we formally state the definitions for EPC privacy as follows:

Definition 8 (user activity).

It is a behavior related to certain products that are attached with requested EPCs, denoted as $A C T = {A_{1}, A_{2}, \dots, A_{m}}$ , where $A_{i} (i = 1, \dots, m)$ is an activity.

Definition 9 (seduce).

It links an activity to a serial of EPCs, called $S E Q_{e p c}$ . Suppose $S E Q_{e p c} (t) = {{E P C}_{i + 1}, \dots, {E P C}_{i + t}}$ , where ${E P C}_{i + 1}, \dots, {E P C}_{i + t}$ are t EPCs, $0 \leq i \leq n - t$ , $1 \leq t \leq n$ , and $| E P C | = n$ , $| S E Q_{e p c} (t) | = t$ . $S E Q_{e p c} (t)$ can deduce that activity $A_{j} (j = 1, \dots, m)$ happens; This deduction is represented as $(S E Q_{e p c} (t), A_{j}) \in {M A P}_{p r v c}$ , where ${M A P}_{p r v c}$ is a privacy deduction relation set mapping a serial of $EPCs$ to an activity.

Definition 10 (perfect privacy).

Simply speaking, adversaries cannot link to anyone in $ACT$ after viewing $S E Q_{e p c} (t)$ . In shorthand, the perfect privacy is

\begin{array}{l} Pr {(S E Q_{e p c} (t), *) \in {M A P}_{p r v c} | \\ ℛ ⟶ 𝒮 : S E Q_{e p c} (t) = {{E P C}_{i + 1}, \dots, {E P C}_{i + t}}} = 0, \end{array}

(7)

where

Pr {A | B}

denotes the probability that A happens after event B happens.

Computational privacy can be defined similarly like computational authenticity.

Definition 11.

Privacy attacking experiment on scheme Π defending against adversary 𝒜- ${E x p P r v c}_{𝒜, Π} (z)$ , which is defined as follows (1)

Scheme Π is executed with security parameter z in the presence of adversary 𝒜.

(2)

ℛ sends $S E Q_{e p c} (t)$ s to 𝒮. If 𝒜 finds $A_{j} \in A C T$ , such that $(S E Q_{e p c} (t), A_{j}) \in {M A P}_{p r v c}$ , 𝒜 outputs 1, otherwise, outputs 0.

(3)

If and only if 𝒜 outputs 1, the experiment outputs 1.

Definition 12.

Scheme Π guarantees perfect (computational) privacy in presence of any (PPTM) adversary 𝒜 (denoted as ${P r v c}_{Π, 𝒜} = 1$ ), if and only if for any (PPTM) adversary 𝒜 and scheme Π, the probability that the output of perfect (computational) privacy attacking experiment equals 1 satisfies

\begin{matrix} Pr [{E x p P r v c}_{𝒜, Π} (z) = 1] = 0 (\leq n e g l (z)), \end{matrix}

(8)

where

n e g l (z)

is a negligible function with parameter z. (In the above equation, the contents in parentheses are corresponding and present simultaneously.)

Therefore, the design goal is to propose a scheme Π satisfying

\begin{matrix} {P r v c}_{Π, 𝒜} = 1, {A u t h}_{Π, 𝒜} = 1, \end{matrix}

(9)

and especially with ultralightweight computation without cryptography.

4. Proposed Schemes

4.1. Basic Schemes

Before we propose our advanced scheme, we review some basic schemes to illustrate our motivations.

(1) Protect Authenticity via Digital Signature. The straightforward method to protect authenticity of EPC is relying on the digital signature. Suppose there exists Trusted Third Party (TTP). TTP signs the signatures for each pair of $(e p c, i p)$ with its private key $S K_{t t p}$ . The public key of TTP $P K_{t t p}$ is predeployed at ℛ. The authenticity of EPC can be achieved by following method:

\begin{matrix} ℛ ⟶ 𝒮 : {e p c}, \\ 𝒮 ⟶ ℛ : {i p, C e r t = S i g n ((e p c, i p), S K_{t t p})}, \\ ℛ : V r f y ((e p c, i p), C e r t, P K_{t t p}) \overset{?}{=} 1, \end{matrix}

(10)

where

C e r t

is a certificate or a signature from TTP for

(e p c, i p)

;

S i g n (\cdot, \cdot)

is a digital signature function;

S K_{t t p}

is the secret key of TTP;

V e f y (\cdot, \cdot, \cdot)

is a signature verification function;

P K_{t t p}

is the public key of TTP.

This method requires TTP to sign a large number of signatures previously and deploy them to 𝒮. It is not scalable and flexible when the number of EPCs is large.

(2) Protect Authenticity via PKI Online. If there exists PKI, the certificate for public key can be fetched, and the signature of TTP can be generated on-line. The authenticity of EPC can be achieved by the following method:

\begin{matrix} ℛ ⟶ 𝒮 : {e p c}, \\ 𝒮 ⟶ TTP : {(e p c, i p)}, \\ T T P ⟶ 𝒮 : {C e r t = S i g n ((e p c, i p), S K_{t t p})}, \\ 𝒮 ⟶ ℛ : {i p, C e r t}, \\ ℛ : V r f y ((e p c, i p), C e r t, P K_{t t p}) \overset{?}{=} 1 . \end{matrix}

(11)

This method requires that TTP exists and signs signatures on-line. It may be scalable when the number of EPCs is large, but more delay and communication overhead are induced.

(3) Protect Privacy via TTP's Encryption and Online Decryption. For protecting the privacy of EPC, the straightforward method is via encryption. The database on pairs of ( $e p c$ , $i p$ ) at 𝒮 is encrypted by TTP's public key $P K_{t t p}$ . That is, 𝒮 possesses a list of $〈 E_{e p c}, E_{e p c i p} 〉$ , where $E_{e p c} = E n c r (e p c, P K_{t t p})$ ; $E_{e p c i p} = E n c r ((e p c, i p), P K_{t t p})$ ; $E n c r (\cdot, \cdot)$ is a public key encryption function. The EPC privacy can be achieved by the following method:

\begin{matrix} ℛ ⟶ 𝒮 : {E_{e p c} = E n c r (e p c, P K_{t t p})}, \\ 𝒮 ⟶ ℛ : {E_{e p c i p}}, \\ ℛ ⟶ T T P : {E_{e p c i p}}, \\ T T P ⟶ ℛ : {(e p c, i p)} . \end{matrix}

(12)

This method requires TTP to encrypt a large number of $e p c$ and $(e p c, i p)$ previously, deploy them to 𝒮, and decrypt $E_{e p c i p}$ on-line. It is not scalable and flexible when the number of EPCs is large. Besides, the EPC privacy protection can only defend against adversaries at 𝒮 but not on the links.

(4) Protect Authenticity via P2P Redundancy. If there does not exist PKI or TTP, the authenticity of EPC has to rely on redundancy information that can be provided from P2P network. The authenticity of EPC can be achieved by the following method:

\begin{matrix} ℛ ⟶ 𝒮_{i} : {e p c}, \\ 𝒮_{i} ⟶ ℛ : {i p_{i}, e p c}, \\ ℛ ⟶ 𝒮_{j} : {e p c}, \\ 𝒮_{j} ⟶ ℛ : {i p_{j}, e p c}, \\ ℛ : i p_{i} \overset{?}{=} i p_{j}, \end{matrix}

(13)

where

𝒮_{i}

𝒮_{j}

are any two 𝒮s in P2P network;

𝒮_{i}

and

𝒮_{j}

should not be colluded. The privacy protection cannot be achieved in this method.

With the above warmup, we next propose an advanced scheme to achieve the design goal. We list major notations used in the remainder of the paper in Table 1.

Table 1

Notation.

𝒜	Adversary
ℛ	Requester
𝒮	ONS server
$E P C I P_{k}$	A set of EPC and IP pairs with set size k
$E P C_{k}$	A set of EPCs with the set size k
$E P C I P_{a}$	A set of EPC and IP pairs with set size a
$E P C_{a}$	A set of EPCs with the set size a
$E P C_{b - a - 1}$	A set of EPCs with the set size $b - a - 1$
$\bar{e p c}$	Requested EPC
$\bar{i p}$	IP address corresponding to $\bar{e p c}$
$E P C_{b}$	A set of EPCs with the set size b
$I P_{b}$	A set of IP addresses with the set size b corresponding to $E P C_{b}$

4.2. Advanced Scheme: APP

We propose an advanced scheme APP (authenticate ONS and protect EPC privacy)—an ultralightweight scheme for both authenticity and privacy—as follows.

At ℛ the Following Happens

Step 1.

ℛ has been predeployed by an authenticated set of $(e p c, i p)$ pairs. Indeed, the set is a table with two fields— $e p c$ and $i p$ —denoted as $E P C I P_{k}$ . We have

\begin{matrix} \forall (e p c, i p) \in E P C I P_{k}, (e p c, i p) \in M A P_{a u t h}, | E P C I P_{k} | = k . \end{matrix}

(14)

All EPCs in

E P C I P_{k}

forms a set denoted as

E P C_{k}

. That is,

\begin{matrix} E P C_{k} = Ω_{e p c} (E P C I P_{k}), \end{matrix}

(15)

where Ω is projection operation for a field

e p c

in the table

E P C I P_{k}

Step 2.

Select $(e p c, i p)$ pairs from $E P C I P_{k}$ . The number of pairs is a, which form a testing set $E P C I P_{a}$ . That is,

\begin{matrix} E P C I P_{a} \subset E P C I P_{k}, | E P C I P_{a} | = a . \end{matrix}

(16)

Similarly, all EPCs in

E P C I P_{a}

forms a set, denoted as

{E P C}_{a}

. That is,

\begin{matrix} {E P C}_{a} = Ω_{e p c} (E P C I P_{a}), \end{matrix}

(17)

where Π is projection operation for a field

e p c

in the table

E P C I P_{a}

;

| {E P C}_{a} | = a

Step 3.

Suppose the requested EPC is $\bar{e p c}$ . ℛ randomly generates $b - a - 1$ distinct EPCs that are not in the set ${E P C}_{a}$ and do not equal $\bar{e p c}$ . It is called a set ${E P C}_{b - a - 1}$ . It mixes three sets, namely, ${E P C}_{a}$ , ${E P C}_{b - a - 1}$ , and ${\bar{e p c}}$ . The union set is ${E P C}_{b}$ . That is,

\begin{matrix} {E P C}_{b} = {E P C}_{a} \cup {E P C}_{b - a - 1} \cup {\bar{e p c}} = {e p c_{1}, \dots, e p c_{b}}, \\ | {E P C}_{b} | = b . \end{matrix}

(18)

Step 4.

ℛ sends the mixed set $E P C_{b}$ to 𝒮:

\begin{matrix} ℛ ⟶ 𝒮 : {e p c_{1}, \dots, e p c_{b}}; \end{matrix}

(19)

At 𝒮 the Following Happens

Step 5.

𝒮 searches its database and returns corresponding IP addresses to ℛ:

\begin{matrix} 𝒮 ⟶ ℛ : {i p_{1}, \dots, i p_{b}}; \end{matrix}

(20)

At ℛ the Following Happens

Step 6.

ℛ checks the correctness of IP addresses, namely $I P_{a} = {i p_{i 1}, \dots, i p_{i a}} \subset I P_{b}$ . That is, check whether

\begin{matrix} (e p c_{i j}, i p_{i j}) \in E P C I P_{a}, (j = 1, \dots, a) \end{matrix}

(21)

are satisfied.

Step 7.

If all IP addresses in $I P_{a}$ are correct, ℛ believes the returning result of $\bar{i p}$ . That is, it records IP address for $\bar{e p c}$ , denoted as $\bar{i p}$ .

4.2.1. Extension

(1) The above can be conducted by ℛ for more rounds. If in all rounds $\bar{i p}$ believes the returning results, the final result will be believed. That is, suppose round number is r; the $\bar{e p c}$ is mixed in the final round. In first $r - 1$ rounds, the $\bar{e p c}$ is a dummy. Only if ℛ believes 𝒮 in first i, $1 \leq i \leq r - 1$ rounds, ℛ continues the next round (namely, $i + 1$ round).

(2) $E P C I P_{k}$ may be updated by adding item $(\bar{e p c}, \bar{i p})$ . That is,

\begin{matrix} E P C I P_{k} ⟸ E P C I P_{k} \cup {(\bar{e p c}, \bar{i p})} . \end{matrix}

(22)

The updating can further be extended to batch

v (1 \leq v \leq b - a)

items that are randomly selected from

E P C_{b - a - 1}

(3) The verification for IP address can be extended to the verification of EPC information. In case the IP address corresponding to certain EPC is changed, the verification can be migrated to EPC information. The table $E P C I P_{k}$ can be extended to table $E P C I N F O_{k}$ accordingly as the information for designated EPC is usually constant. $E P C I N F O_{k}$ is used for authenticating returned IP address. Most processes in above seven steps maintain unchanged, except that the fields in table are changed, and the verification will be delayed upon requesting PML server.

(4) The parameters a, b in scheme APP can be extended to adaptive tuning according to the observation on the trustworthiness of ONS server. If accumulative trustworthiness is over a threshold value, the security parameter a, b can be changed to smaller ones for better performance (with respect to communication overhead).

4.2.2. Discussion

(1) As an EPC is short (no more than 96 bits), it does not obviously damage communication performance when submitting multiple EPCs. Similarly, an IP address is short (no more than 128 bits), and it does not obviously damage communication performance when returning multiple IP addresses.

(2) The above discussion is independent to buffered ONS architecture. If buffered ONS is available, ℛ does not need to explicitly request 𝒮, instead of requesting the buffered ONS. It thus can defend against poisonous ONS buffers. Indeed, buffered ONS records can be looked upon as an imaginary ONS server.

(3) It is better to let authenticated set ${E P C}_{a}$ be different in the requests for a given ONS server 𝒮. We let $k ≫ a$ . It does not induce much overhead as the storage of ${E P C}_{k}$ is lightweight even though k is large. That is, the length of one record in ${E P C}_{k}$ is no more than $96 + 128 = 224$ bits; thus, the total length for ${E P C}_{k}$ with k records is $224 * k$ bits.

Algorithms proposed for APP scheme are as in Algorithms 1–3.

Algorithm 1: APP-1 algorithm.

Require: $E P C I P_{k}, \bar{e p c}, 𝒮$

Ensure: $E P C_{b}$

$E P C I P_{a} \Leftarrow R a n d o m S e l e c t (E P C I P_{k})$

$E P C_{a} \Leftarrow T a b l e P r o j e c t (E P C I P_{k}, e p c)$

$\bar{e p c} \Leftarrow R e a d T a g ()$

$E P C_{b - a - 1} \Leftarrow R a n d o m G e n e r a t e E P C ()$

$E P C_{b} \Leftarrow E P C_{a} \cup {\bar{e p c}} \cup E P C_{b - a - 1}$

$S e n d (E P C_{b}, 𝒮)$

Algorithm 2: APP-2 algorithm.

Require: $E P C_{b}, ℛ$

Ensure: $\bar{i p}$

$R e c e i v e (E P C_{b}, ℛ)$

$S e n d (I P_{b}, ℛ)$

Algorithm 3: APP-3 algorithm.

Require: $I P_{b}, 𝒮$

Ensure: $\bar{i p}$

$R e c e i v e (I P_{b}, 𝒮)$

$I P_{a} \Leftarrow G e t I P (I P_{b})$

$C O R R E C T \Leftarrow C h e c k (I P_{a})$

if $(C O R R E C T)$ then

$A c c e p t ({(\bar{e p c}, \bar{i p})}) / /$ go ahead

else

$A b a n d o n (\bar{i p})$

end if

Analysis

Proposition 13.

The authenticity strength of APP with one round is $1 - (a! (b - a)! / b!)$ .

Proof.

If and only if adversaries correctly answer the testing set ${E P C}_{a}$ in ${E P C}_{b}$ , requesters will accept the returning results. As $| {E P C}_{a} | = a$ and $| {E P C}_{a} | = b$ , the probability that adversaries correctly guess the location of $E P C_{a}$ in $E P C_{b}$ is thus $(a! (b - a)!) / b!$ . That is the probability that adversaries can cheat requesters to believe a fake returning IP address. Thus, the authenticity strength of APP with one round is $1 - (a! (b - a)!) / b!$ .

Proposition 14.

The authenticity strength of APP with r rounds is $1 - (a! (b - a)! / b!)^{r}$ .

Proof.

The probability that adversaries can cheat requesters in all r rounds is the probability of a successful guess in all r times, which is $(a! (b - a)! / b!)^{r}$ . Thus, the authenticity strength is $1 - (a! (b - a)! / b!)^{r}$ .

Proposition 15.

The privacy strength of APP with one round is $1 / b$ .

Proof.

If and only if adversaries correctly guesses the location of $\bar{e p c}$ in ${E P C}_{b}$ , the privacy will be broken. As ${E P C}_{b - a - 1}$ is randomly generated, the linkages between serial EPCs are blurred. That is, $(S E Q_{e p c} (t), A_{j}) \in {M A P}_{p r v c}$ . As $| {E P C}_{b} | = b$ , and the privacy strength of one round of APP is $1 / b$ .

Proposition 16.

The privacy strength of APP with r rounds is $1 / (b * r)$ .

Proof.

Straightforward.

Claim 1. Scheme APP is ultralightweight.

Proof.

The computation overhead for authenticity protection is merely the verification of string comparison; no cryptographic computation is induced. Besides, no computation overhead for privacy protection is induced. The induced communications are $b - 1$ times. As the length of EPCs is no more than 96 bits, and IP address is no more than 128 bits, the total induced extra communication overhead is less than $224 * (b - 1)$ bits.

If the elements in testing set are recurrent, the security will be damaged. k is also a security parameter influencing the authenticity and privacy strength. For simplicity and security, let $k ≫ a$ . Otherwise, the following analysis proofs the influence of parameter k in scheme APP.

Proposition 17.

The probability that ${E P C}_{a}$ is recurrent in two subsequent rounds of selection of ${E P C}_{a}$ at the requestors is $1 / C (a, k) = (a! (k - a)!) / k!$ , where $C (a, k)$ is the combination counts for selecting a elements from k elements.

Proof.

View the selection of ${E P C}_{a}$ as an event with probability $1 / C (a, k)$ . Suppose ${E P C}_{a}$ is the set of the first round selection; the recurrence of ${E P C}_{a}$ in the next round is thus $1 / C (a, k)$ .

Proposition 18.

The probability that x items in ${E P C}_{a}$ are recurrent in two subsequent rounds of ${E P C}_{a}$ selection is $1 / (C (x, a) * C (a - x, k - a))$ .

Proof.

Suppose ${E P C}_{a}$ is the set of the first round selection; the recurrence of x items in ${E P C}_{a}$ in the next round is $1 / (C (x, a) * C (a - x, k - a))$ .

Proposition 19.

The probability that x items in ${E P C}_{a}$ are recurrent in any y rounds of ${E P C}_{a}$ selection is $1 / (C (x, a) * C (a - x, k - y a))$ .

Proof.

Suppose ${E P C}_{a}$ is the set of the first round selection; the probability that the recurrence of x items in ${E P C}_{a}$ in any y rounds is $1 / (C (x, a) * C (a - x, k - y a))$ .

Lemma 20.

Any required strength for authenticity and privacy can be achieved by APP scheme via selecting a proper security parameter (i.e., APP is sufficient for the authenticity and privacy).

Proof.

Suppose the authentication and privacy strength requirements are $(α, β)$ . The decision of security parameters for one round of scheme APP is as follows. (1)

Select b such that $1 / b < β$ .

(2)

Select a such that $(a! (b - a)!) / b! < α$ .

(3)

Select $k ≫ a$ .

Proposition 21.

APP scheme can guarantee the authenticity and privacy (i.e., ${P r v c}_{A P P, 𝒜} = 1$ , ${A u t h}_{A P P, 𝒜} = 1$ ).

Proof.

According to the Lemma, a security parameter (denoted as z in the definition of authenticity and privacy) can be selected for scheme APP to guarantee the required strength for authenticity and privacy.

4.3. A General Scheme

We finally propose a general scheme to unify all possible schemes to protect authenticity and privacy in ONS context to defend against adversaries in ONS server and channels. The attacks such as ONS pollution attack, ONS leakage attack, and ONS deduction attack can be mitigated.

(1) ${e p c}^{'} \Leftarrow$ Hide $(p r i k 1_{r}, e p c)$ : it is a computation function at ℛ. ℛ transforms requested $e p c$ to another form ${e p c}^{'}$ by using $p r i k 1_{r}$ . $p r i k 1_{r}$ is the key privately possessed by ℛ.

Purpose: the privacy of $e p c$ is protected via ${e p c}^{'}$ . That is, on viewing of ${e p c}^{'}$ , the $e p c$ can be correctly guessed with a low probability (namely, a predefined threshold value). Or it is computationally infeasible to compute $e p c$ from ${e p c}^{'}$ .

(2) Request $({e p c}^{'}, t a g_{r} = f ({e p c}^{'}, k 2_{r}), ℛ, 𝒮)$ : it is a communication function at ℛ. ℛ sends ${e p c}^{'}$ and $t a g_{r}$ to 𝒮. $k 2_{r}$ is a private key or a secrete key shared between ℛ and 𝒮. That is, $k 2_{r} = {p r i k 2_{r} ∥ k 2_{r s}}$ . f is a (trapdoor) one-way function with second preimage resistance.

Purpose: for adversaries in communication channels, the authenticity of ${e p c}^{'}$ is protected. That is, it is computationally infeasible to find another ${e p c}^{''} \neq {e p c}^{'}$ , such that $t a g_{r} = f ({e p c}^{''}, *)$ , where * is any string. For authenticated channels, $t a g_{r}$ can be omitted. For adversaries in communication channels and at 𝒮, the privacy of $e p c$ is protected (already explained in the first step).

(3) ${0 ∥ 1} \Leftarrow$ Verify $(𝒮, {e p c}^{'}, t a g_{r}, k 2_{s})$ : it is a computation function at 𝒮. 𝒮 verifies the authenticity of ${e p c}^{'}$ via $t a g_{r}$ . The verification needs $k 2_{s}$ that is a public key corresponding to $p r i k 2_{r}$ or a secrete key sharing with ℛ. That is, $k 2_{s} = {p u b k 2_{r} ∥ k 2_{r s}}$ . If and only if the result is $1$ , 𝒮 continues; otherwise, 𝒮 terminates.

Purpose: 𝒮 authenticates received ${e p c}^{'}$ . For authenticated channels, this step can be omitted.

(4) ${i p}^{'} \Leftarrow$ Find $(𝒮, {e p c}^{'})$ : it is a computation function at 𝒮. 𝒮 finds the corresponding ${i p}^{'}$ of ${e p c}^{'}$ . ${e p c}^{'}$ and ${i p}^{'}$ cannot be unknown with respect to 𝒮.

Purpose: 𝒮 searches ${i p}^{'}$ according to ${e p c}^{'}$ .

(5) Response $({i p}^{'}, t a g_{s} = f ({e p c}^{'}, k 3_{s}), 𝒮, ℛ)$ : It is a communication function at 𝒮. 𝒮 returns ${i p}^{'}$ and $t a g_{s}$ to ℛ. $k 3_{s}$ is a private key or a secrete key shared with ℛ. That is, $k 3_{s} = {p r i k 1_{s} ∥ k 3_{r s}}$ . f is a (trapdoor) one-way function with second preimage resistance.

Purpose: For adversaries in communication channels and at ℛ, the privacy of $i p$ is protected via ${i p}^{'}$ . That is, on viewing of ${i p}^{'}$ , the $ip$ can be correctly guessed with a low probability (namely, a predefined threshold value). Or it is computationally infeasible to compute $i p$ from ${i p}^{'}$ .

For adversaries in communication channels, the authenticity of ${i p}^{'}$ is protected. That is, it is computationally infeasible to find another ${i p}^{''} \neq {i p}^{'}$ , such that $t a g_{s} = f ({i p}^{''}, *)$ , where * is any string.

For authenticated channels, $ta g_{s}$ can be omitted.

(6) ${0 ∥ 1} \Leftarrow$ Verify $(ℛ, {i p}^{'}, t a g_{s}, k 3_{r})$ : it is a computation function at ℛ. ℛ verifies the authenticity of ${i p}^{'}$ via $t a g_{s}$ . The verification needs $k 3_{r}$ that is a public key corresponding to $p r i k 1_{s}$ or a secrete key sharing with ℛ. That is, $k 3_{r} = {p u b k 1_{s} ∥ k 3_{r s}}$ . If and only if result is Y, 𝒮 continues; otherwise, 𝒮 terminates.

Purpose: ℛ authenticates received ${i p}^{'}$ . For authenticated channels, this step can be omitted.

(7) $i p \Leftarrow$ Recover $(p r i k 3_{r}, {i p}^{'})$ : it is a computation function at ℛ. $i p$ is the corresponding IP address for $e p c$ . Only ℛ can recover $i p$ from ${i p}^{'}$ as only ℛ possesses $p r i k 3_{r}$ . $p r i k 3_{r}$ could be equal to $p r i k 1_{r}$ .

Purpose: ℛ obtains final inquired result $i p$ corresponding to $e p c$ .

Next, to simplify the discussion and concentrate on adversaries only at 𝒮, we propose a simplified general scheme to unify all possible schemes to protect authenticity and privacy in ONS context to defend against only adversaries in ONS server. The attacks such as ONS pollution attack, ONS leakage attack, and ONS deduction attack can be mitigated.

(1) ${e p c}^{'} \Leftarrow$ Hide $(p r i k 1_{r}, e p c)$ . It is a computation function at ℛ. ℛ hides requested $e p c$ into another form ${e p c}^{'}$ by using $p r i k 1_{r}$ . $p r i k 1_{r}$ is the key privately possessed by ℛ.

(2) Request $({e p c}^{'}, ℛ, 𝒮)$ . it is a communication function at ℛ. ℛ sends ${e p c}^{'}$ to 𝒮.

(3) ${i p}^{'} \Leftarrow$ Find $(𝒮, {e p c}^{'})$ : it is a computation function at 𝒮. 𝒮 finds the corresponding ${i p}^{'}$ of ${e p c}^{'}$ .

(4) Response $({i p}^{'}, 𝒮, ℛ)$ : it is a communication function at 𝒮. 𝒮 returns ${i p}^{'}$ to ℛ.

(5) $i p \Leftarrow$ Recover $(p r i k 2_{r}, {i p}^{'})$ : it is a computation function at ℛ. $i p$ is the corresponding IP address for $e p c$ . Only ℛ can recover $i p$ from ${i p}^{'}$ as only ℛ possesses $p r i k 2_{r}$ . $p r i k 2_{r}$ could be equal to $p r i k 1_{r}$ .

Figure 1 illustrates the processes in general scheme.

Figure 1

A general scheme to protect authenticity and privacy defending against adversaries at 𝒮.

Proposition 22.

The APP scheme is an illustration of the simplified general scheme.

Proof (straightforward).

We list the elements in scheme APP corresponding to the elements in the simplified general scheme as follows: $e p c = \bar{e p c}$ , ${e p c}^{'} = {E P C}_{b}$ , $i p = \bar{i p}$ , ${i p}^{'} = I P_{b}$ , and $p r i k 1_{r} = p r i k 2_{r} = N U L L$ .

Proposition 23.

APP is the necessary condition for authenticity and privacy protection without any cryptographic computation and TTP.

Proof (sketch).

As there does not exist TTP, the authenticity and privacy have to be achieved by ℛ and 𝒮 themselves. As there do not exist cryptographic operations, $p r i v 1_{r} = p r i k 2_{r} = N U L L$ . As 𝒮 must know $e p c$ to return $i p$ , adversaries at 𝒮 can reveal $i p$ . As $i p$ cannot be encrypted, the privacy can be achieved only by requiring multiple EPCs. As there does not exist TTP to judge the authenticity of returning $I P_{b}$ , an authenticated set ${E P C}_{a}$ is required as a self-judgement criteria. That is, ${E P C}_{a} \subset {E P C}_{k}$ is required to be possessed by ℛ.

5. Conclusions

In this paper, we proposed an ultralightweight scheme to authenticate requested IP address of EPC and to protect the user's privacy in EPCglobal network without relying on any cryptographic computation or TTP. We also proposed relevant algorithms and a general scheme that can unify all possible schemes. Moreover, the security of the scheme in terms of authenticity and privacy was strictly proved, and the performance was extensively analyzed. Both justified the applicability of the proposed scheme.

Footnotes

Acknowledgments

Wei Ren's research was financially supported by the National Natural Science Foundation of China (61170217), the Open Research Fund from the Shandong Provincial Key Laboratory of Computer Network (SDKLCN-2011-01), Fundamental Research Funds for the Central Universities (CUG110109), and Wuhan Planning Project of Science and Technology (2013010501010144). Yi Ren's research was sponsored in part by the Aim for the Top University Project of the National Chiao Tung University and the Ministry of Education, Taiwan.

References

Rosenkranz

Dreyer

Schmitz

Schoenborn

Sakal

Pohl

Comparison of dnssec and dnscurve securing the object name service (ons) of the epc architecture framework

Proceedings of the European Workshop on Smart Objects: Systems, Technologies and Applications (RFID Sys Tech '10)

June 2010

1 6

Sun

Zhao

Xiao

Lightweight public key infrastructure and service relation model for designing a trustworthy ONS

Proceedings of the 8th IEEE/ACIS International Conference on Computer and Information Science (ICIS '09)

June 2009

295 300

2-s2.0-70350736316

10.1109/ICIS.2009.93

Fabian

Implementing secure P2P-ons

Proceedings of IEEE International Conference on Communications (ICC '09)

June 2009

1 5

Fabian

Günther

Security challenges of the epcglobal network

Communications of the ACM 2009 52 7 121 125

Fabian

Günther

Distributed ons and its impact on privacy

Proceedings of IEEE International Conference on Communications (ICC '07)

June 2007

1223 1228

Schapranow

M. P.

Zeier

Leupold

Schubotz

Securing EPCglobal object name service—privacy enhancements for anti-counterfeiting

Proceedings of the 2nd International Conference on Intelligent Systems, Modelling and Simulation (ISMS '11)

January 2011

332 337

2-s2.0-79953741279

10.1109/ISMS.2011.57

Kurkovsky

Syta

Casano

Continuous RFID-enabled authentication: privacy implications

IEEE Technology and Society Magazine 2011 30 3 34 41

Langheinrich

A survey of RFID privacy approaches

Personal and Ubiquitous Computing 2009 13 6 413 421

2-s2.0-67650674080

10.1007/s00779-008-0213-4

Deng

R. H.

RFID privacy: relation between two notions, minimal condition, and efficient construction

Proceedings of the 16th ACM Conference on Computer and Communications Security (CCS '09)

November 2009

54 65

2-s2.0-74049095938

10.1145/1653662.1653670

10.

Juels

Weis

S. A.

Defining strong privacy for RFID

ACM Transactions on Information and System Security 2009 13 1, article 7

2-s2.0-72449181354

10.1145/1609956.1609963

11.

Deng

Lai

On two RFID privacy notions and their relations

ACM Transactions on Information and System Security 2008 14 4, article 30

12.

Shi

Sim

Deng

Secds: a secure epc discovery service system in epcglobal network

Proceedings of the 2nd ACM conference on Data and Application Security and Privacy (CODASPY '12)

2012

New York, NY, USA

267 274

APP: An Ultralightweight Scheme to Authenticate ONS and Protect EPC Privacy without Cryptography in EPCglobal Networks

Abstract

1. Introduction

2. Related Work

3. Problem Formulation

3.1. Network Model

3.2. Attack Model and Trust Model

Definition 1 (ONS pollution attack ( 𝒜 poll )).

Definition 2 (ONS leakage attack ( 𝒜 leak )).

Definition 3 (ONS inference attack ( 𝒜 infr )).

3.3. Security Definition and Design Goal

Definition 4 (perfect authenticity of mapping IP address ( A u t h prft )).

Definition 5 (computational authenticity of mapping IP address ( A u t h cmpt )).

Definition 6.

Definition 7.

Definition 8 (user activity).

Definition 9 (seduce).

Definition 10 (perfect privacy).

Definition 11.

Definition 12.

4. Proposed Schemes

4.1. Basic Schemes

4.2. Advanced Scheme: APP

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

Step 6.

Step 7.

4.2.1. Extension

4.2.2. Discussion

Algorithm 1: APP-1 algorithm.

Algorithm 2: APP-2 algorithm.

Algorithm 3: APP-3 algorithm.

Proposition 13.

Proof.

Proposition 14.

Proof.

Proposition 15.

Proof.

Proposition 16.

Proof.

Proof.

Proposition 17.

Proof.

Proposition 18.

Proof.

Proposition 19.

Proof.

Lemma 20.

Proof.

Proposition 21.

Proof.

4.3. A General Scheme

Proposition 22.

Proof (straightforward).

Proposition 23.

Proof (sketch).

5. Conclusions

Footnotes

Acknowledgments

References

Definition 1 (ONS pollution attack ( $𝒜_{poll}$ )).

Definition 2 (ONS leakage attack ( $𝒜_{leak}$ )).

Definition 3 (ONS inference attack ( $𝒜_{infr}$ )).

Definition 4 (perfect authenticity of mapping IP address ( ${A u t h}_{prft}$ )).

Definition 5 (computational authenticity of mapping IP address ( ${A u t h}_{cmpt}$ )).