Abstract
In this paper, we show that many formal and informal security results on distance-bounding (DB) protocols are incorrect/ incomplete. We identify that this inadequacy stems from the fact that the pseudorandom function (PRF) assumption alone, invoked in many security claims, is insufficient. To this end, we identify two distinct shortcomings of invoking the PRF assumption alone: one leads to distance-fraud attacks, whilst the other opens for man-in-the-middle (MiM) attacks. First, we describe –in a more unitary, formal fashion– why assuming that a family of functions classically used inside DB protocols is solely a PRF is unsatisfactory and what generic security flaws this leads to. Then, we present concrete constructions that disprove the PRF-based claimed security of several DB protocols in the literature; this is achieved by using some PRF programming techniques. Whilst our examples may be considered contrived, the overall message is clear: the PRF assumption should be strengthened in order to attain security against distance-fraud and MiM attacks in distance-bounding protocols!
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Security Parameter
- Secret Sharing Scheme
- Impersonation Attack
- Pseudorandom Function
- Cryptology ePrint Archive
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Avoine, G., Lauradoux, C., Martin, B.: How Secret-sharing can Defeat Terrorist Fraud. In: Proceedings of the 4th ACM Conference on Wireless Network Security – WiSec 2011, Hamburg, Germany. ACM, ACM Press (June 2011)
Avoine, G., Tchamkerten, A.: An Efficient Distance Bounding RFID Authentication Protocol: Balancing False-Acceptance Rate and Memory Requirement. In: Samarati, P., Yung, M., Martinelli, F., Ardagna, C.A. (eds.) ISC 2009. LNCS, vol. 5735, pp. 250–261. Springer, Heidelberg (2009)
Brands, S., Chaum, D.: Distance Bounding Protocols (Extended Abstract). In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 344–359. Springer, Heidelberg (1994)
Cremers, C., Rasmussen, K.B., Čapkun, S.: Distance hijacking attacks on distance bounding protocols. Cryptology ePrint Archive, Report 2011/129 (2011), http://eprint.iacr.org/
Drimer, S., Murdoch, S.J.: Keep your enemies close: distance bounding against smartcard relay attacks. In: Proceedings of the 16th USENIX Security Symposium on USENIX Security Symposium, pp. 7:1–7:16. USENIX Association, Berkeley (2007)
Dürholz, U., Fischlin, M., Kasper, M., Onete, C.: A Formal Approach to Distance-Bounding RFID Protocols. In: Lai, X., Zhou, J., Li, H. (eds.) ISC 2011. LNCS, vol. 7001, pp. 47–62. Springer, Heidelberg (2011)
Fischlin, M., Onete, C.: Provably secure distance-bounding: an analysis of prominent protocols. Cryptology ePrint Archive, Report 2012/128 (2012)
Ford. Safe and Secure SecuriCode TM Keyless Entry (2011), http://www.ford.com/technology/
Hancke, G.P., Kuhn, M.G.: An RFID Distance Bounding Protocol. In: Proceedings of SECURECOMM, pp. 67–73 (2005)
Kapoor, G., Zhou, W., Piramuthu, S.: Distance Bounding Protocol for Multiple RFID Tag Authentication. In: Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2008, vol. 02, pp. 115–120. IEEE, IEEE Computer Society, Shanghai, China (2008)
Kim, C.H., Avoine, G.: RFID Distance Bounding Protocol with Mixed Challenges to Prevent Relay Attacks. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 119–133. Springer, Heidelberg (2009)
Kim, C.H., Avoine, G., Koeune, F., Standaert, F.-X., Pereira, O.: The Swiss-Knife RFID Distance Bounding Protocol. In: Lee, P.J., Cheon, J.H. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 98–115. Springer, Heidelberg (2009)
Nielsen, J.B.: A Threshold Pseudorandom Function Construction and Its Applications. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 401–416. Springer, Heidelberg (2002)
Reid, J., Gonzalez Nieto, J.M., Tang, T., Senadji, B.: Detecting Relay Attacks with Timing-based Protocols. In: Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, ASIACCS 2007, pp. 204–213. ACM, Singapore (March 2007)
Shoup, V.: Sequences of Games: a Tool for Taming Complexity in Security Proofs (2006) (manuscript)
Tu, Y.-J., Piramuthu, S.: RFID Distance Bounding Protocols. In: Proceedings of the First International EURASIP Workshop on RFID Technology (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boureanu, I., Mitrokotsa, A., Vaudenay, S. (2012). On the Pseudorandom Function Assumption in (Secure) Distance-Bounding Protocols. In: Hevia, A., Neven, G. (eds) Progress in Cryptology – LATINCRYPT 2012. LATINCRYPT 2012. Lecture Notes in Computer Science, vol 7533. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33481-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-33481-8_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33480-1
Online ISBN: 978-3-642-33481-8
eBook Packages: Computer ScienceComputer Science (R0)