An optimal probabilistic solution for information confinement, privacy, and security in RFID systems

In this paper, we provide the following contributions to enhance the security of RFID based systems. First, we assume that among multiple servers storing the information related to the tags some of them can be compromised. For this new threat scenario, we devise a technique to make RFID identification server dependent, providing a different unique secret key shared by a tag and a server. The solution proposed requires the tag to store just a single key, thus fitting the constraints on tag's memory. Second, we provide a probabilistic tag identification scheme that requires the server to perform just bitwise operations and simple list manipulation primitives, thus speeding up the identification process. The tag identification protocol assures privacy, security and resilience to DoS attacks thanks to its stateless nature. Moreover, we extend the tag identification protocol to achieve mutual authentication and resilience to replay attacks. The proposed identification protocol, unlike other probabilistic protocols, never rejects a legitimate tag. Furthermore, the identification protocol requires the reader to access the local database (DB) of tags' keys O(n) timeswhere n is the number of tags in the systemwhile it has been shown in the literature that a privacy preserving identification protocol requires a reader to access Θ(n) times this DB. In this sense, our protocol is optimal. Finally, the three features suggested in this paper, namely, reader-dependent key management, tag identification, and mutual authentication, can be independently adopted to build alternative solutions.