Data Synchronization in Privacy-Preserving RFID Authentication Schemes

Massively deploying RFID systems, while preserving people’s privacy and data integrity, is a major security challenge of the coming years. This is why research related to privacy-preserving authentication is growing, including design of schemes, cryptanalysis and security models. In nearly all such schemes secret key cryptography is used, since RFID tags are extremely constrained in time and space, and untraceability is achieved by updating some data at each authentication. Unfortunately, none of them entirely resists to denial of service attacks, those in which the enemy forces updating of the tag and/or the reader by sending fake messages. Moreover, literature lacks a clear and formal way of comparing schemes w.r.t. this kind of attack. In this paper, we introduce a new characterization, called synchronizability. This allows us to, first, establish a relevant model; second, evaluate existing schemes in this model and point out their deficiencies; third, present a new scheme with all desired features.