Paper 2012/165

Key Updates for RFID Distance-Bounding Protocols: Achieving Narrow-Destructive Privacy

Cristina Onete


Distance-bounding protocols address man-in-the-middle (MITM) in authentication protocols: by measuring response times, verifiers ensure that the responses are not purely relayed. Durholz et al. [13] formalize the following attacks against distance-bounding protocols: (1) mafia fraud, where adversaries must authenticate to the verifier in the presence of honest provers; (2) terrorist fraud, where malicious provers help the adversary (in offline phases) to authenticate (however, the adversary shouldn't authenticate on its own); (3) distance fraud, where a malicious prover must convince the verifier that it is closer to it than in reality; (4) impersonation security, where the prover must authenticate to the verifier in the rounds where response times are not measured. A scenario where distance-bounding can be successfully deployed is RFID authentication, where the provers and RFID tags, and the verifiers are RFID readers. Security models and most distance-bounding schemes designed so far are static, i.e. the used secret key is never updated. The scenario considered by [13] features a single reader and a single tag. However, a crucial topic in RFID authentication is privacy, as formalized by Vaudenay [32]. Adversaries against privacy can corrupt tags and learn the secret keys; in this scenario, key updates ensure better privacy. In this paper we extend distance-bounding security to include key updates, and show a compiler that preserves mafia, distance, and impersonation security, and turns a narrow-weak private distance-bounding protocol into a narrow-destructive private distance-bounding protocol as in [32]. We discuss why it is much harder to attain terrorist fraud resistance, for both stateless and stateful scenarios. We optimize our compiler for cases where (i) the underlying distance-bounding protocol does not have reader authentication; (ii) impersonation security is achieved (by using a pseudorandom function) before the distance-bounding phase; or (iii) the prover ends by sending a MAC of the transcript. We also use our compiler on the enhanced construction in [13].

Note: Updated version/constructions. More efficient compiler.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
stateful distance boundingdenial of serviceprivacyRFID
Contact author(s)
cristina onete @ gmail com
2012-04-04: last of 2 revisions
2012-03-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Cristina Onete},
      title = {Key Updates for {RFID} Distance-Bounding Protocols: Achieving Narrow-Destructive Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2012/165},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.