Passive Attacks on a Class of Authentication Protocols for RFID

Mutual authentication mechanisms can be used in RFID systems to preserve the confidentiality of the RFID tags. Hiding the unique IDs of the tags is critical to prevent unauthorized tag tracking. In this paper, the authors analyze two mutual authentication protocols called M2AP and EMAP, recently proposed by Peris-Lopez et. al. They show that a passive adversary eavesdropping on the open wireless medium, can extract the unique ID of the RFID tag by collecting an expected O(log2 L) challenge-response exchange messages between the tag and the reader, where L is the length of the tag's unique ID.