Robust, Anonymous RFID Authentication with Constant Key-Lookup
A considerable number of anonymous RFID authentication schemes have been proposed. However, current proposals either do not provide robust security guarantees, or suffer from scalability issues when the number of tags issued by the system is very large. In this paper, we focus on approaches that reconcile these important requirements. In particular, we seek to reduce the complexity of identifying tags by the back-end server in anonymous RFID authentication protocols---what we term the key-lookup problem. We propose a compiler that transforms a generic RFID authentication protocol (supporting anonymity) into one that achieves the same guarantees with constant key-lookup cost even when the number of tags is very large (billions of tags and beyond). This approach uses a lightweight one-way trapdoor function and produces protocols that are suitable for deployment into current tag architectures. We then explore the issue of minimal assumptions required, and show that one-way trapdoor functions are necessary to achieve highly scalable, robustly secure solutions. We then relax the requirement of unlinkable anonymity, and consider scalable solutions that are provably secure and for which the loss of privacy is minimal.
Provably Secure Grouping-proofs for RFID tags
We investigate an application of RFIDs referred to in the literature as the group scanning problem, in which several tags are ``simultaneously'' scanned by a reader. The security context of this application was first discussed by Ari Juels, who presented a protocol that allows pairs of RFID tags to provide evidence of having been simultaneous scanned---a yoking proof. Our goal is to study group scanning proofs in strong adversarial models. We describe a security model for RFID group scanning proofs, and consider versions of the problem that require privacy (anonymity) of the grouped tags, and/ or forward-security properties. Our security model is based on the Universal Composability framework and supports reusability (through modularity of security guarantees). We also introduce novel protocols that realize the security models, focusing on efficient solutions based on off-the-shelf components, such as highly optimized pseudo-random function designs that require fewer than 2000 Gate-Equivalents.