Time Measurement threatens privacy-friendly RFID authentication protocols

Privacy is one of the most important security concerns in radio frequency identification. The publication of hundred RFID-based authentication protocols during the last decade raised the need of designing a dedicated privacy model. An important step has been done with the model of Vaudenay that combines early models into a unified and powerful one. In particular, this model addresses the case where an adversary is able to know whether or not the protocol execution succeeded. This modelizes the fact that the adversary may get information from a side channel about the termination of the protocol, e.g., she notices that the access is granted to the RFID-tag holder. We go one step forward in this paper and stress that the adversary may also have access to a side channel that leaks the computational time of the reader. This modelizes an adversary who measures how long it takes to grant the access. Although this channel could be seen as an implementation flaw, we consider that it is always risky to require the implementation to solve what the design should deal with. This new channel enables to demonstrate that many key-reference protocols are not as privacy-friendly as they claim to be, e.g., WSRE, OSK, C2, O-FRAP, O-FRAKE,... We then introduce the TIMEFUL oracle in the model of Vaudenay, which allows to analyze the resistance of the protocols to time-based attacks as soon as the design phase. Finally, we suggest some methods that make RFID-based authentication protocols immune to such attacks