MEED: A Memory-efficient Distance Bounding Protocol with Error Detection

Radio Frequency Identification (RFID) systems suffer from different security and privacy problems, among which relay attacks are a hot topic recently. A relay attack is a form of man-in-the-middle (MITM) attack where the adversary manipulates the communication by only relaying the verbatim messages between two parties. The main countermeasure against relay attacks is the use of distance bounding protocols measuring the round-trip time between the reader and the tag, more precisely, it uses bit exchanges for a series of rapid challenge-response rounds in RFID systems. In 2005, Hancke and Kuhn first introduced distance bounding protocol into RFID systems, after that, many schemes have been proposed based on this protocol. However, most schemes tend to a more complex design to decrease adversary's success probability. In this paper, we propose a novel distance bounding protocol named MEED, using only 2n bits of memory, which, to our best knowledge, is equal to Hancke and Kuhn's protocol and less than any existing protocols. In addition, by using our protocol, the tag is able to detect adversary's malicious queries. We also make a comparison with typical previous distance bounding protocols in both memory and mafia fraud success probability.