25

Trapdoor-based Mutual Authentication Scheme without Cryptographic Primitives in RFID Tags Hwaseong Lee 1∗ Eun Young Choi 2 Su-Mi Lee 2 Dong Hoon Lee1 Center for Information Security Technologies (CIST), Korea University, Seoul, Korea 1 email{hwaseong,donghlee}@korea.ac.kr 2 email{bluecey,smlee}@cist.korea.ac.kr

Abstract Radio Frequency IDentification(RFID) systems are being used in many applications such as the supply chain. The widespread usage of tags creates new threats of security and privacy in RFID systems. Many schemes have been proposed to provide security and privacy, based on basic cryptographic primitives such as hash function and encryption algorithm. However, it may be a burden on a resource-constrained tag. As considering the requirements on a tag, we propose a lightweight mutual authentication scheme based on trapdoor one-way property and challenge/reaponse approach. Even though the proposed scheme does not perform cryptograhic primitives, it guarantees security and privacy provided by the authentication schemes using cryptographic primitives. We expect this mutual authentication scheme to activate RFID systems in various applications.

1

Introduction

An amount of research has been recently achieved on RFID systems which have an automatic identification characteristic. Basically, RFID systems consist of RFID tag, RFID reader, and database(s). RFID tag is attached to customer items and RFID reader broadcasts an RF signal to know information of the items through (mutual) authentication with RFID tag. RFID tag, smart-label, is recognized as a replacement for optical bar code in sense of economical and efficient inventory management [7] and expected to be used in more various applications : for example, inventory control, automobile identification, livestock, and access control to building, etc [16]. ∗ This research was supported by the Seoul R&BD Program(10665), Korea.

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

This pervasive deployment creates a potential threat to security and privacy such as counterfeit of RFID tag and violation of customer privacy. It is because the unique ID of RFID tag allows an adversary to track the moving history of the RFID tag or copy it into a bogus tag and an adversary can easily eavesdrop communication via public channel. A natural solution to security vulnerability for RFID systems is to perform the basic cryptographic primitives, specially hash function, in order to support cryptographic characteristics and authentication [12, 3, 10, 11]. However, we must keep in mind the scare computation/storage capability of RFID tag. The cost of manufacturing a RFID tag has to be below 50 cents [15] (RFID Journal expects the price of a single RFID tag to be 5 cents by 2007 [14]). It means that it is infeasible to implement a basic cryptographic primitive, requiring thousands of logic gates, in RFID tag. Practically, hash function is out of the capability of weak RFID tag, even if the number of logic gates for hash function becomes less and less. Hence, it will be difficult to perform the expensive cryptographic primitives in RFID systems. Generally, an authentication scheme is designed based on cryptographic primitives, in order to use cryptographic characteristics such as one-way property and randomness and confidentiality and so on. These characteristics are useful in authentication via public channel. For authentication, two parties must check them to share same secret or information via public channel. Even though hash values or encoded values are exchanged via public channel, an adversary cannot know original values, usually secret information. Namely, there is no secret information leakage. A few lightweight authentication schemes suitable for RFID systems have been proposed in [16, 6, 8, 9, 1, 6]. The motivation of these schemes is the resource limitation of RFID tag so that the schemes did not use cryptographic primitives. However, the schemes are weak against some attacks or insecure under a practical assumption. Even if cryptographic primitives are not used for an authentication

scheme in RFID systems, it is critical that the authentication scheme identically support security and privacy defined in the authentication schemes using the expensive cryptographic primitives. Our aim is to design an authentication scheme satisfying cryptographic characteristics without using cryptographic primitives in a low-power RFID tag. Instead of hash-based or encryption-based authentication, we introduce trapdoorbased authentication using challenge and response approach. Trapdoor-based authentication is achieved by satisfying trapdoor one-way property, even though it does not perform actual cryptographic primitives. A property is trapdoor one-way property if it has one-way property but it can be easily inverted with the knowledge of trapdoor. This property satisfies cryptographic characteristics explained above. Hence, the proposed scheme is strong against diverse attacks and has no assumption. Related Works. The necessity of lightweight operation in a low-power RFID tag has been insisted through many researches [16, 6, 8, 9, 1, 6]. Vajda and Buttyan proposed a lightweight authentication scheme in which a secure matrix is stored on RFID tag in advance and used for authentication (the matrix consists of s-bit primes) [16]. This scheme is also challenge-response type authentication like the proposed scheme but deriving response requires exhaustive search by integer division in side of RFID tag. Although this scheme does not use cryptographic primitives, it is unable to be called lightweight authentication scheme since it makes RFID tag compute multiple division operations in order to derive response. Karthilkeyan and Nesterenko proposed an authentication scheme by computing multiplication of a matrix [9]. It has the limitation such as synchronization between RFID reader and RFID tag in order to update key material. Juels proposed a lightweight scheme based on rotation by RFID tag through many pseudonyms [6]. When it is practically applied into RFID systems, it may not guarantee security, since this scheme is secure under limited eavesdropping of communication between RFID reader and RFID tag. Duc et al. presented a lightweight authentication scheme suitable for EPCglobal Class 1 Gen-2 tags [4]. This scheme uses CRC code instead of hash values but requires session-key synchronization which can be difficult in unreliable channel such as RFID systems. Juels and Weis proposed HB+ scheme in which authentication is achieved through q times responses about a single challenge [8]. RFID tag intentionally inserts noise in response and is authenticated by a reader if the error bound of responses is less than pre-defined noisy probability. However, an adversary can know the secret of RFID tag through man-in-the-middle attack and replay attack, under the assumption she can check whether modified response is accepted by a reader or not. To improve security of [8],

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

Bringer et al. proposed HB++ scheme [1]. It has limitation in terms of implementation because permutation function must keep distribution of scalar products as well as satisfies low computational complexity. Our contribution is to propose a novel lightweight mutual authentication scheme in a low-power RFID tag by introducing the concept of trapdoor one-way property into RFID systems. • Lightweight operation : both a low-power RFID tag and a reader perform only bitwise operation, which is more lightweight than traditional cryptographic primitives. • Strong against attacks : the proposed scheme is secure against passive attacks, the probability of succeeding in active attacks is negligible, and the damage due to tag-compromising attack does not affect the other tags. Besides, it does not require synchronization for mutual authentication since key materials or a tag ID need not be updated for mutual authentication. • Trapdoor one-way property : communication via public channel does not help an adversary know secret information of RFID tag. Only parties knowing trapdoor can derive response corresponding to a specific challenge. Organization. The rest of the paper is organized as follows. Section 2 describes notations used in this paper. Section 3 explains system model and security requirements. We propose a mutual authentication scheme in Section 4. We analyze its security and performance in Section 5. Finally, we conclude our paper in Section 6.

2 Notation For concreteness and simpler presentation, we use notations as below. c is challenge a reader sends to a tag r is response to challenge T rap is trapdoor containing information to derive response Blind is a blinding factor used to cover a tag ID R is a random number for singulation K is a key shared between reader-tag M1 is a binary matrix commonly shared between reader-tag M2 is a binary matrix separately shared between reader-tag N is the number of rows in M1 M [i] is an element of i-th row in any matrix M M [i][j] is a j-th bit on i-th row in any matrix M |bits| is the length of bits
is the concatenation operation −→ is sending a message from left party to right one

3 3.1

System Model and Security Requirements RFID Systems

RFID Systems consist of RFID tag, RFID reader, and back-end database. RFID Tag. Each RFID tag(hereafter a tag) has its unique ID(UID) which is a 96-bit number in EPC Code [5]. A tag is divided into passive tag and active tag according to the source of energy. Generally, a tag is comprised of antenna and IC chip which are used for communication with RFID reader and data storage/logical operation, respectively. RFID Reader. RFID Reader(hereafter a reader) transmits a RF signal to tags, receives information from tags, and sends it to back-end database. In addition, a reader has an ability to read and write data to the tags. Back-End Database. Back-end database(hereafter database) is a secure data-processing server that can store and manage information of tags such as ID, product information, reader location, and so on. Moreover, database can resolve the ID of a tag which responds to a reader’s query. Usually, the communication between a reader and a tag is considered to be weak to eavesdrop while the communication between a reader and database is assumed to be conducted over secure channel. On occasion, a reader is a proxy of database so that database stores all secret information and can establish a value required for authentication. For a simple explanation, we think a reader plays a role of database together. If tag reading does not exceed 1 second, each tag can transmit almost 500 bits [12]. Since a tag is a very low-cost device, it is considered that a tag cannot afford to use the standard cryptographic primitives such as MAC, encryption, and digital signature [16]. Therefore, we will not use cryptographic primitives in a tag. Moreover, it is too expensive to support tamper-resistant in a tag. It means an adversary can obtain the internal data in a tag through physical attacks.

3.2

Attack Models

The ultimate goal of an adversary is divided into the following. The first is to know tag ID even though an adversary does not have a secret which is shared between database and a legitimate tag and used in process of authentication. The second is to produce a correct response to a challenge even though she is not a legitimate tag. In other words, she wants to be authenticated by a reader(ultimately database), whether she impersonates a legitimate tag to a reader and participates in authentication protocol or not. Below, we can classify attack models achieving such goals. Passive Attack. It is classified into a passive attack if an adversary can just eavesdrop and collect the exchanged

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

messages between a reader and a tag but cannot inject and modify an answer to a reader(or a tag)and have no ability to make a physical attack to a tag. For example, tracing through eavesdropping is included in this passive attack. Active Attack. We define an active attack as injecting/modifying/blocking answer as well as eavesdropping. In this attack it is possible to impersonate a tag. Still an active attack does not include a physical access to a tag. DoS attack or spoofing attack belongs to this attack. Tag-compromising Attack. We define a tagcompromising attack as an attack where an adversary captures a tag and obtains a secret information in the tag. It is important that a compromised tag does not affect non-compromised tag in security point of view. It is noted that this attack includes passive and active attacks. In general, if an adversary can launch active attack(tagcompromising attack), she is considered to have the ability enough to launch passive attack(active and passive attack).

3.3

Security Requirements

There are a few problems to be solved for secure RFID systems; in other words, we must block the goals of an adversary which were described in attack models. The first is to keep information on which tags a user holds. It means that tag information must not be revealed. It is important in terms of tag anonymity, privacy, and tracing, etc. The second is to prevent an adversary from being illegally authenticated because it can lead to counterfeit tag and then a great damage in RFID systems. We suggest two security requirements for secure RFID systems. Indistinguishability. If the probability of distinguishing the output of a tag and a random output is negligible, it will be called indistinguishability. It means that it is infeasible to know that the output is from a target tag. It is satisfied when there is no information leakage. It is a critical requirement to prevent the above first goal. Hardness of Correct Response. As soon as receiving the challenge from a reader, an adversary must correctly guess a tag’s answer and respond to the challenge in order to be illegally authenticated by the reader. If an adversary guesses the response of unspecific tag, she would be estimated to have the capability of correct response. Hence it must be hard that an adversary responds correctly, in order to fail to identify her as a correct object. It is a requirement to prevent the second goal explained above. A public key-based mechanism satisfies the above security requirements while public key-based mechanism generally requires a greater amount of computation overhead than a low-power tag can afford. Hence, it is necessary to satisfy

the above security requirements at lightweight computation.

4

Trapdoor-based Mutual Authentication Scheme

We propose lightweight mutual authentication scheme for RFID systems in this section. For authentication, a reader sends XORed trapdoor and a challenge to tags and only tags sharing a pre-stored secret can recover trapdoor and correctly respond to the challenge with trapdoor. The key idea for authentication is trapdoor one-way property using challenge/response approach and two matrices. In the proposed scheme, a challenge and a response are respectively considered a point in the range and a point in the domain. Accordingly, it is easy to derive the response of a given challenge with the knowledge of trapdoor while it is infeasible to derive the response without the knowledge of trapdoor. Accordingly, trapdoor is for legitimate tags in security point of view. Two matrices are embodied in each tag. The matrices play a role of secret information, which is able to minimize the damage on tag-compromising attack. The proposed scheme is divided into two phases as below.

4.1

System Setup

Three secrets are embodied on each tag before the tag is attached in an item : one key and two different matrices. The same key is pre-stored into each tag. Two matrices are as following : the first matrix M1 is identical to all the tags and the second M2 is different to separate tags. Let M1 and M2 be respectively a N × log2 N  binary matrix and a |R| × |ID|·2 |R| binary matrix, where N is the number of rows in M1 and R is a random number used in singulation. It is important that the values corresponding to each row must not be in order and overlapped.

4.2

Mutual Authentication using Trapdoor One-way Property

Step 1. (Singulation) Before authentication, every scheme must pass by singulation in order to wake up and identify a single tag in multiple tags [5]. Singulation consists of three flows : query phase and exchanging phase of random number R. A reader initiates query phase, and then a tag sends a random number R and a reader echoes R to a tag. The first flow in Fig. 1 represents singulation phase briefly. Note that R is a random number generated by a tag, not a reader (precisely, a pseudo random generator which is a basic component for a tag [5]). We use R in this round to XOR a tag’s ID in Step 3. It is reasonable to use R since all the protocols must send R for singulation. Reader ←→ Tag : Query, R

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

Database

K, M1, {M2}

Reader K † Trap, c

Query, R

Tag

K, M1, M2

r, ID †Blind

Figure 1. Overview of the Proposed Scheme

Step 2. (Tag Authenticates Reader) First, a reader selects rows on M1 and can establish a tag’s response r in advance. Second, a reader can establish challenge c from response r with trapdoor one-way function Punc() and trapdoor containing information to help derive response r from challenge c. Third, a reader sends K ⊕ T, c to a tag. Fourth, a tag can recover T rap and authenticate a reader with checksum. Below, more details are explained in order. Reader −→ Tag : K ⊕ T rap, c = P unc(A) 1. Reader establishes r in advance. Response r is a N ×1 binary matrix. Reader selects randomly the N4 elements from M1 as taking complement into account. A is a N4 × log2 N  binary matrix and consists of the selected elements like A = A[1]
A[2]
...
A[ N4 ]. The other N4 elements are the complements of the selected N4 elements (message length to transmit is reduced by using complement). In total, N2 elements are selected on M1 without no overlap. The N −bit r is set to 1 at rows which correspond to rows of the selected elements in M1 and 0 at remaining rows. Namely, response r represents the index on selected elements in M1 . 2. Reader establishes c and T rap. P unc() intentionally punctures a bit per element on A as considering a tag to derive r as like Algorithm 1. T rap holds information for recovery : punctured position on challenge c and indirect bit information recovering puncture position. 3. Reader covers T rap with a key. A reader cover T rap with a pre-stored key and transmits XORed T rap and c to a tag. It is important that T rap has a relation with c. It is explained below. 4. Tag recovers T rap and authenticates reader. A tag can recover T rap with a pre-stored key K. It is possible for a tag to authenticate a reader with the relation between c and T rap. Namely, c and T rap play a role of message and checksum, respectively. If an adversary randomly selects T rap
, T rap
may not satisfy

01 : 02 : 03 : 04 : 05 : 06 : 07 : 08 : 09 : 10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : 22 :

Algorithm 1. Establishing Challenge and Trapdoor Input: A := A[1]
A[2]
...
A[ N4 ] Output: Challenge, Trapdoor length := log2 N  for i := 1 to N4 A[i] := A[i] for j := 0 to (length - 1) if (A[i][j] = 1) then A[i][j] := 0 else A[i][j] := 1 element := A[i] element := A[i] row := (element / length) + 1 col := element (mod length) row := element / length + 1 col := element (mod length) bit[i] := M1 [row][col] bit[i] := M1 [row][col] if (bit[i] = bit[i]) delete a j-th bit on A[i] T rap[i] := j || bit[i] c[i] := A[i] break Return c, T rap

the relation. Therefore, this scheme is secure against DoS attack since a tag will respond only if checksum is correct. Step 3. (Reader Authenticates Tag) First, a tag derives response r with T rap. Second, a tag establishes blinding factor Blind and sends r and blinded ID to a reader. Third, a reader authenticates a tag by checking r. Below we explain how to derive r and share Blind. Tag −→ Reader : r, ID ⊕ Blind 1. Tag derives r from c with T rap. A tag can find where the punctured positions on c are and also know what the bits of punctured positions are by using T rap. Hence, a tag can derive r which is used when a reader authenticates the tag. 2. Reader blinds ID. As explained before, singulation precedes an authentication scheme in order to wake a tag and confirm the tag. We use R in singulation and the second binary matrix M2 to establish a Blind. First, we compute Index = R ⊕ K by using only |R| bits on K. Second, as if r signifies the index of selected rows on M1 , Index becomes the index of rows

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

to be selected on M2 . We concatenate the elements corresponding on the index and use it as Blind. Therefore blinded ID on each tag is separate and changed every time because of a separate M2 on each tag and a random number R. 3. Reader authenticates tag. A reader authenticates a tag by checking whether an expected response r is equal to a received response r. The overview of authentication is like Fig. 1.

4.3

Example on the Proposed Scheme

Due to the limited page, we omit an example on the proposed scheme. Refer to a full paper where the proposed scheme is easily described [17].

5

Analysis

5.1

Security Analysis

We discuss security of the proposed scheme. Assume that an adversary can launch passive attack, active attack, and tag-compromising attack as explained in 3.2. Furthermore, an adversary tries to know a tag ID and/or want a reader to regard her as a legitimate tag. Therefore, authentication scheme in RFID systems should be able to protect an adversary from achieving the goal of attacks. Below, we summarize security briefly due to limited pages. 1. Secure against Passive Attack. In the proposed scheme an adversary launching passive attack such as tracking cannot succeed in both goals since the proposed scheme supports randomness and any information on a tag is never revealed through eavesdropping. 2. A Negligible Probability against Active Attack. Even though an adversary under active attack tries such as spoofing to be illegally authenticated, she succeeds with a negligible probability which is about as much as she guesses ID or collision occurs. To achieve it, she must correctly guess response r corresponding to challenge c. The advantage she can get is negligible because there is trapdoor one-way property between challenge/response. 3. Minimized Damage against Tag-compromising Attack. In fact, it is very important to minimize the damage due to tag-compromising attack since it is infeasible to expect no damage under tag-compromising attack. In the proposed scheme the damage under tag-compromising attack affects just the compromised tag itself. It is because each tag uses separate matrix shared with database.

5.2

Efficiency Analysis

We analyze efficiency in terms of memory space, operation, and communication overhead in a tag. 1. Memory Cost. Normally, logic gates to be used for security are from 250 to 3000 in a tag [13]. In the proposed scheme, a tag has to store one key and two binary matrices. A tag need not store the implementation of a low-cost cryptographic primitives which can be constructed with 6 to 13 K gates [2]. It results in the usage of less memory than previous scheme. 2. Computation Cost. The proposed scheme requires a lightweight bitwise operation both in a tag and a reader. It reduces the burden on database in process of searching a tag ID as well as on a tag to operate. 3. Communication Cost. Communication cost can be afforded in a tag. If the bit length of R and the number of rows on M1 and the bit length of each row on M1 and the length of ID are respectively 16, 128, 7, and 128, the length of message in Step 2 is in total 320 bits(= 128 + 192) and the length of message in step 3 is 256 bits(= 128 + 128). A tag can afford it when considering a transmit rate in Section 3. By using complement rows, communication overhead is reduced as keeping strong security. We expect the proposed scheme to be practically used in a current RFID tag. Further, it is likely to advance the feasible usage of RFID tag.

6

Conclusion

We defined attack models and security requirements for RFID systems. As taking the requirements into account, we proposed a lightweight mutual authentication, based on trapdoor one-way property. The security of the proposed scheme was proven under pre-defined attack models. It means the proposed scheme to guarantee the security of schemes performing cryptographic primitives, although it does not perform cryptographic primitives and uses only lightweight operation. Further, the proposed scheme can be practically applied into current RFID systems because of lightweight property of the proposed scheme.

References [1] J. Bringer, H. Chabanne, E. Dottax. HB++ : a Lightweight Authentication Protocol Secure agsint Some Attacks. eprint 2005. [2] CRYPTOREC reports, published 2002

Third International Workshop on Security Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2007) 0-7695-2863-5/07 $25.00 © 2007

[3] E. Y. Choi, S. M. Lee, and D. Hoon Lee. Efficient RFID Authentication Protocol for Ubiquitous Computing Environment. EUC workshop 2005, pp. 945-954, 2005. [4] D. N. Duc, J. Park, H. Lee, and K. Kim. Enhancing Security of EPCglobal Gen-2 RFID Tag against Traceability and Cloning. SCIS06, 2006. [5] EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID, EPCglobal Inc., 2005. [6] A. Juels. Minimalist Cryptography for Low-Cost RFID Tags. SCN04, pp. 149-164, 2004. [7] A. Juels. RFID Security and Privacy:A Research Survey. IEEE Journal on Selected Areas in Communications, Vol. 24, NO. 2, pp. 381-394, 2006. [8] A. Juels and S. A. Weis. Authenticating Pervasive Devices with Human Protocols. Crypto05, pp. 293-308, 2005. [9] S. Karthikeyan and M. Nesterenko. RFID Security without Extensive Cryptography. SASN05, pp. 63-67, 2005. [10] J. Kang and D. Nyang. RFID Authentication Protocol with Strong Resistance Against Traceability and Denial of Service Attacks. ESAS05, pp. 164175, 2005. [11] D. Molnar, A. Soppera, D. Wagner. A scalable, delegatable, pseudonym protocol enabling ownership transfer of RFID tags. EASA05, pp. 1-16, 2005. [12] M. Ohkubo, K. Suzuki, and S. Kinoshita. A Cryptographic Approach to Privacy- Friendly tag. RFID Privacy 2003 Workshop, 2003. [13] P. Peris-Lopez, J. C. Hernandez-Castro, J. Estevez-Tapiador, A. Ribagorda. M2 AP: A Minimalist Mutual-Authentication Protocol for Lowcost RFID Tags. UIC06, pp. 912-923, 2006. [14] RFID Journal, http://www.rfidjournal.com/. [15] S. Sarma, S. Weis and D. Engels. Radio-frequency identification : Security risks and challenges. CryptoBytes 6, 2003. [16] I. Vajda and L. Butydan. Lightweight authentication protocols for low-cost RFID tags. Workshop on Security in Ubiquitous Computing, 2003. [17] http://protocol.korea.ac.kr/˜ puzzle /paper/trapdoorRFID.pdf