IEEE RFID 2010 Privacy Protection for RFID-based Tracking Systems Chiu C.Tan Qun Li Lei Xie Department of Computer Science Department of Computer Science State Key Laboratory of College of William and Mary College of William and Mary Novel Software Technology cct@cs.wm.edu liqun@cs.wm.edu Nanjing University xielei@dislab.nju.edu.cn Abstract-RFID technology is increasingly being deployed in to the database.A user wanting to know for instance who was ubiquitous computing environments for object tracking and at a meeting in Office 1 at 1:00 pm can query the database localization.Existing tracking architecture usually assumes the to determine the IDs of the tags,and thus the identity of the use of a trusted server which is invulnerable to compromise by internal and external adversaries.However,maintaining such meeting participants. a trusted server is unlikely in the real world.In this paper, The potential for abuse of such a powerful tracking system we consider the problem of adding privacy protection to object is apparent.The straightforward approach is to limit the access tracking systems built upon passive RFID tags,without relying to the database data using passwords.Each user is associated on a trusted server assumption.Our protocol continues to protect user privacy in the event of partial compromise of a server. with a list of RFID tags they are authorized to access,and must supply the correct password when querying the database. I.INTRODUCTION For example,a user with ID=101 running a query "Select location From database Where ID=101 and Time=time"must The low cost and rugged design of RFID tags make them first supply the appropriate permissions for his tag before suitable to be attached to everyday objects such as key chains the location information is released.More advance techniques and coffee mugs.With every object embedded with its own such as role-based access control [3],[4].and Hippocratic RFID tag,ubiquitous computing concepts like object tracking databases [5],can also be used to protect the database. and localization or location based services can be realized [1]. This type of solutions have a common requirement.A 2],allowing many new applications to be developed upon this trusted database is needed to maintain and enforce the infrastructure.At the same time,widespread RFID deployment privacy policy.Without a database that is invulnerable to creates privacy risks for everyone,not just a few willing early compromise by criminal hackers or disgruntled employees, adopters,thus the need for privacy protection becomes critical. and always managed by competent system administrators, Wired connection we cannot protect user privacy.We believe that maintaining such a trusted server is difficult in practice.Even three letter government agencies with strong emphasis on security have Database Comidor office r been vulnerable to database breaches or mistakes [6].[7].[8]. 0 In this paper,we consider the problem of how to build Radio range Office 2 1 a tracking system that does not rely on a trusted database Comridor 2 to protect user privacy.Our solution divides up the database 8- operations into separate servers such that we can tolerate ΣRFID reader Otfice 3 the compromise of any one of the databases.Our protocols O RFID tag 8- are designed to take into account the computationally weak (attached toa person or thing Office 4 capabilities of an RFID tag,and allow a user to efficiently query the database for answers. Fig.1. Typical RFID tracking system We make the following contributions in this paper.We propose a technique to divide a database query,originally Fig.I shows an environment where RFID tags are attached intended to a single database,into multiple databases such to people and objects.Each RFID tag has an associated unique that if only one of the database is compromised,the user's ID which represents that tag in the system.A network of privacy is protected.We also consider how to detect,but not RFID readers are deployed in the building,with each reader prevent,adversary disruption attacks such as the data deletion associated with a specific location,such as "Office 1"or and manipulation. "Corridor 2".The readers are connected to a database server The rest of the paper is as follows.We formulate our prob- via a wired network.A reader will periodically broadcast a lem and adversary model in Section II.Section III introduces query,and all the RFID tags within the vicinity will respond two strawman protocols to motivate our solutions.Sections IV to that reader.The reader will then forward these tag responses presents our protocol against different types of adversaries. 978-1-4244-5743-4/10/$26.00©20101EEE 53Privacy Protection for RFID-based Tracking Systems Chiu C. Tan Department of Computer Science College of William and Mary cct@cs.wm.edu Qun Li Department of Computer Science College of William and Mary liqun@cs.wm.edu Lei Xie State Key Laboratory of Novel Software Technology Nanjing University xielei@dislab.nju.edu.cn Abstract—RFID technology is increasingly being deployed in ubiquitous computing environments for object tracking and localization. Existing tracking architecture usually assumes the use of a trusted server which is invulnerable to compromise by internal and external adversaries. However, maintaining such a trusted server is unlikely in the real world. In this paper, we consider the problem of adding privacy protection to object tracking systems built upon passive RFID tags, without relying on a trusted server assumption. Our protocol continues to protect user privacy in the event of partial compromise of a server. I. INTRODUCTION The low cost and rugged design of RFID tags make them suitable to be attached to everyday objects such as key chains and coffee mugs. With every object embedded with its own RFID tag, ubiquitous computing concepts like object tracking and localization or location based services can be realized [1], [2], allowing many new applications to be developed upon this infrastructure. At the same time, widespread RFID deployment creates privacy risks for everyone, not just a few willing early adopters, thus the need for privacy protection becomes critical. Database RFID reader RFID tag (attached to a person or thing) Office 1 Office 2 Office 3 Office 4 Corridor 1 Corridor 2 Wired connection Radio range Fig. 1. Typical RFID tracking system Fig. 1 shows an environment where RFID tags are attached to people and objects. Each RFID tag has an associated unique ID which represents that tag in the system. A network of RFID readers are deployed in the building, with each reader associated with a specific location, such as “Office 1” or “Corridor 2”. The readers are connected to a database server via a wired network. A reader will periodically broadcast a query, and all the RFID tags within the vicinity will respond to that reader. The reader will then forward these tag responses to the database. A user wanting to know for instance who was at a meeting in Office 1 at 1:00 pm can query the database to determine the IDs of the tags, and thus the identity of the meeting participants. The potential for abuse of such a powerful tracking system is apparent. The straightforward approach is to limit the access to the database data using passwords. Each user is associated with a list of RFID tags they are authorized to access, and must supply the correct password when querying the database. For example, a user with ID=101 running a query “Select location From database Where ID=101 and Time=time” must first supply the appropriate permissions for his tag before the location information is released. More advance techniques such as role-based access control [3], [4], and Hippocratic databases [5], can also be used to protect the database. This type of solutions have a common requirement. A trusted database is needed to maintain and enforce the privacy policy. Without a database that is invulnerable to compromise by criminal hackers or disgruntled employees, and always managed by competent system administrators, we cannot protect user privacy. We believe that maintaining such a trusted server is difficult in practice. Even three letter government agencies with strong emphasis on security have been vulnerable to database breaches or mistakes [6], [7], [8]. In this paper, we consider the problem of how to build a tracking system that does not rely on a trusted database to protect user privacy. Our solution divides up the database operations into separate servers such that we can tolerate the compromise of any one of the databases. Our protocols are designed to take into account the computationally weak capabilities of an RFID tag, and allow a user to efficiently query the database for answers. We make the following contributions in this paper. We propose a technique to divide a database query, originally intended to a single database, into multiple databases such that if only one of the database is compromised, the user’s privacy is protected. We also consider how to detect, but not prevent, adversary disruption attacks such as the data deletion and manipulation. The rest of the paper is as follows. We formulate our prob￾lem and adversary model in Section II. Section III introduces two strawman protocols to motivate our solutions. Sections IV presents our protocol against different types of adversaries. IEEE RFID 2010 978-1-4244-5743-4/10/$26.00 ©2010 IEEE 53