Probabilistic Recursive Cryptanalysis of Ultralightweight Mutual Authentication Protocols for Passive RFID Systems

Abstract

Security and privacy are the fundamental concerns of RFID systems. Several ultralightweight mutual authentication protocols have been proposed to ensure the security of RFID systems in cost effective manner. These protocols usually involve simple bitwise logical operations such as XOR, AND, OR and some special purpose ultralightweight primitives. In this paper, we identify the vulnerabilities of the two recently proposed ultralightweight mutual authentication protocols: SASI and Yeh. et al. We have used Recursive Linear Cryptanalysis (RLC) for security analysis of SASI protocol, which requires only two authentication sessions to reveal concealed secret ID of the tags. For Yeh et al. protocol, we have proposed an active Quasi-Linear attack, which requires approximately 213 authentication sessions to disclose the tag’s secret ID.