Scalability issues in Privacy-Compliant RFID protocols

Like all growing technologies, radio frequency identification brings along its share of security-related problems. Such problems are impersonation of tags, denial of service attacks, leakage or theft of information, malicious traceability, etc. to name a few. To carry out her attack, an adversary can try to penetrate into the back-end database, to tamper with some tags, or she can try to eavesdrop or even modify the information exchanged between the tags and the readers. The latter approach is the one we focus on in this chapter: We address the conception of tag–reader protocols that avoid malicious traceability. Finding such a protocol is far from being an easy task, due to the weak resources available on tags. Indeed, we consider that tags are not able to use public-key cryptography. With such an assumption, protocols that resist to malicious traceability do not scale well, and so cannot be used in most of the current applications. In what follows, we recall the basic knowledges about RFID protocols and malicious traceability. Then, we present protocols that scale well but which are not secure. We so exhibit common design-related mistakes one can encounter when analyzing RFID protocols. Next, we introduce protocols based on the well-known challenge–response scheme. We explain why they are secure, but also why they do not scale well. In the last part of this chapter, we present techniques that have been suggested to reduce the computation complexity of challenge–response-based protocols.