A novel mutual authentication scheme based on quadratic residues for RFID systems

In 2004, Ari Juels proposed a Yoking-Proofs protocol for RFID systems. Their aim is to permit a pair of tags to generate a proof which is verifiable off-line by a trusted entity even when the readers are potentially untrusted. However, we found that their protocol does not possess the anonymity property but also suffers from both known-plaintext attack and replay attack. Wong et al. [Kirk H.M. Wong, Patrick C.L. Hui, Allan C.K. Chan, Cryptography and authentication on RFID passive tags for apparel products, Computer in Industry 57 (2005) 342–349] proposed an authentication scheme for RFID passive tags, attempting to be a standard for apparel products. Yet, to our review, their protocol suffers from guessing parameter attack and replay attack. Moreover, both of the schemes have the common weakness: the backend server must use brute search for each tag’s authentication. In this paper, we first describe the weaknesses in the two above-mentioned protocols. Then, we propose a novel efficient scheme which not only achieve the mutual authentication between the server and the tag but also can satisfy all the security requirements needed in an RFID system.