A practical quadratic residues based scheme for authentication and privacy in mobile RFID systems

In this paper we propose a novel approach to authentication and privacy in mobile RFID systems based on quadratic residues and in conformance to EPC Class-1 Gen-2 specifications. Recently, Chen et al. (2008) and Yeh et al. (2011) have both proposed authentication schemes for RFID systems based on quadratic residues. However, these schemes are not suitable for implementation on low-cost passive RFID tags as they require the implementation of hash functions on the tags. Consequently, both of these current methods do not conform to the EPC Class-1 Gen-2 standard for passive RFID tags which from a security perspective requires tags to only implement cyclic redundancy checks (CRC)and pseudo-random number generators (PRNG) leaving about 2.5k to 5k gates available for any other security operations. Further, due to secure channel assumptions both schemes are not suited for mobile/wireless reader applications. We present the collaborative authentication scheme suitable for mobile/wireless reader RFID Systems where the security of the server-reader channel cannot be guaranteed. Our schemes achieves authentication of the tag, reader and back-end server in the RFID system and protects the privacy of the communication without the need for tags to implement expensive hash functions. Our scheme is the first quadratic residues based scheme to achieve compliance to EPC Class-1 Gen-2 specifications. Through detailed security analysis we show that the collaborative authentication scheme achieves the required security properties of tag anonymity, reader anonymity, reader privacy, tag untraceability and forward secrecy. In addition, it is resistant to replay, impersonation and desynchronisation attacks. We also show through Strand space analysis that the proposed approach achieves the required properties of agreement, originality and secrecy between the tag and the server.