On the optimal resistance against mafia and distance fraud in distance-bounding protocols

[en] Distance-bounding protocols are security protocols with a time measurement phase used to detect relay attacks, whose security is typically measured against mafia-fraud and distance-fraud attacks. A prominent subclass of distance-bounding protocols, known as lookup-based protocols, use simple lookup operations to diminish the impact of the computation time in the distance calculation. Independent results have found theoretical lower bounds [Formula presented] and [Formula presented], where n is the number of time measurement rounds, on the security of lookup-based protocols against mafia and distance-fraud attacks, respectively. However, it is still an open question whether there exists a protocol achieving both security bounds. This article closes this question in two ways. First, we prove that the two lower bounds are mutually exclusive, meaning that there does not exist a lookup-based protocol that provides optimal protection against both types of attacks. Second, we provide a lookup-based protocol that approximates those bounds by a small constant factor. Our experiments show that, restricted to a memory size that linearly grows with n, our protocol offers strictly better security than previous lookup-based protocols against both types of fraud.

Disciplines :

Computer science

Author, co-author :

GIL PONS, Reynaldo ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Mauw

MAUW, Sjouke ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

Trujillo-Rasua, Rolando; Universitat Rovira i Virgili, Tarragona, Spain

External co-authors :

yes

Language :

English

Title :

On the optimal resistance against mafia and distance fraud in distance-bounding protocols

Publication date :

October 2023

Journal title :

Computer Communications

ISSN :

0140-3664

Publisher :

Elsevier B.V.

Volume :

210

Pages :

69 - 78

Peer reviewed :

Peer Reviewed verified by ORBi

Funders :

European Commission
Fonds National de la Recherche Luxembourg
Ministerio de Ciencia e Innovación

Funding number :

AFR-PhD-14565947

Funding text :

This research is funded by the Luxembourg National Research Fund, Luxembourg , under the grant AFR-PhD-14565947 . Rolando Trujillo-Rasua is funded by a Ramon y Cajal grant from the Spanish Ministry of Science and Innovation and the European Union (REF: RYC2020-028954-I )

Available on ORBilu :

since 29 January 2024

Statistics

Number of views

107 (2 by Unilu)

Number of downloads

43 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

WoS citations^™

Bibliography

Hancke, Gerhard P., Kuhn, Markus G., An RFID distance bounding protocol. Proc. First International Conference on Security and Privacy for Emerging Areas in Communications Networks, SecureComm-2005, 2005, IEEE Computer Society, Washington, DC, USA, 67–73.
Desmedt, Yvo, Goutier, Claude, Bengio, Samy, Special uses and abuses of the Fiat-Shamir passport protocol. CRYPTO’87 LNCS, vol. 293, 1988, Springer, 21–39.
Avoine, Gildas, Boureanu, Ioana, Gérault, David, Hancke, Gerhard P, Lafourcade, Pascal, Onete, Cristina, From relay attacks to distance-bounding protocols. Secur. Ubiquitous Comput. Syst. Sel. Top., 2021, 113–130.
EMVCo, E.M.V., Contactless specifications for payment systems. 2021 Book C-2, Kernel.
Thueringer, Peter, De Jong, Hans, Murray, Bruce, Neumann, Heike, Hubmer, Paul, Stern, Susanne, Decoupling of measuring the response time of a transponder and its authentication. 2018 US Patent 10,044,512.
Avoine, Gildas, Tchamkerten, Aslan, An efficient distance bounding RFID authentication protocol: Balancing false-acceptance rate and memory requirement. Proc. 12th International Conference on Information Security, ISC’09 LNCS, vol. 5735, 2009, Springer, 250–261.
Gürel, Ali Özhan, Arslan, Atakan, Akgün, Mete, Non-uniform stepping approach to RFID distance bounding problem. Proc. 5th International Workshop on Data Privacy Management, DPM’10, and 3rd International Conference on Autonomous Spontaneous Security, SETOP’10 LNCS, vol. 6514, 2011, Springer, 64–78.
Kardas, Süleyman, Kiraz, Mehmet Sabir, Bingöl, Muhammed Ali, Demirci, Hüseyin, A novel RFID distance bounding protocol based on physically unclonable functions. International Conference on Radio Frequency Identification: Security and Privacy Issues, 2012, Springer, 78–93.
Kim, Chong Hee, Avoine, Gildas, RFID distance bounding protocols with mixed challenges. IEEE Trans. Wirel. Commun. 10:5 (2011), 1618–1626.
Munilla, Jorge, Peinado, Alberto, Distance bounding protocols for RFID enhanced by using void-challenges and analysis in noisy channels. Wirel. Commun. Mob. Comput. 8:9 (2008), 1227–1232.
Sjouke Mauw, Jorge Toro-Pozo, Rolando Trujillo-Rasua, A class of precomputation-based distance-bounding protocols, in: Proc. 1st IEEE European Symposium on Security and Privacy, EuroS&P, Saarbrücken, Germany, 2016.
Trujillo-Rasua, Rolando, Complexity of distance fraud attacks in graph-based distance bounding. Proc. 10th International Conference on Mobile and Ubiquitous Systems: Computing, Networking, and Services, MOBIQUITOUS’13 LNCS, vol. 131, 2013, Springer, 289–302.
Trujillo-Rasua, Rolando, Martin, Benjamin, Avoine, Gildas, The poulidor distance-bounding protocol. Proc. 6th International Conference on Radio Frequency Identification: Security and Privacy Issues, RFIDSec’10 LNCS, vol. 6370, 2010, Springer, 239–257.
Yu-Ju Tu, Selwyn Piramuthu, RFID distance bounding protocols, in: Proc. First International EURASIP Workshop on RFID Technology, 2007, pp. 67–68.
Avoine, Gildas, Bingöl, Muhammed Ali, Kardas, Süleyman, Lauradoux, Cédric, Martin, Benjamin, A framework for analyzing RFID distance bounding protocols. J. Comput. Secur. 19:2 (2011), 289–317, 10.3233/JCS-2010-0408.
Avoine, Gildas, Bingöl, Muhammed Ali, Boureanu, Ioana, Capkun, Srdjan, Hancke, Gerhard P., Kardas, Süleyman, Kim, Chong Hee, Lauradoux, Cédric, Martin, Benjamin, Munilla, Jorge, Peinado, Alberto, Rasmussen, Kasper Bonne, Singelée, Dave, Tchamkerten, Aslan, Trujillo-Rasua, Rolando, Vaudenay, Serge, Security of distance-bounding: A survey. ACM Comput. Surv. 51:5 (2019), 94:1–94:33, 10.1145/3264628.
Brands, Stefan, Chaum, David, Distance-bounding protocols. Proc. Advances in Cryptology, EUROCRYPT’93 LNCS, vol. 765, 1994, Springer, 344–359.
Cremers, Cas, Rasmussen, Kasper B., Schmidt, Benedikt, Capkun, Srdjan, Distance hijacking attacks on distance bounding protocols. 2012 IEEE Symposium on Security and Privacy, 2012, 113–127, 10.1109/SP.2012.17.
Bengio, Samy, Brassard, Gilles, Desmedt, Yvo G., Goutier, Claude, Quisquater, Jean-Jacques, Secure implementation of identification systems. J. Cryptol. 4:3 (1991), 175–183.
Kim, Chong Hee, Avoine, Gildas, Koeune, François, Standaert, François-Xavier, Pereira, Olivier, The Swiss-Knife RFID distance bounding protocol. The 11th International Conference on Information Security and Cryptology, ICISC 2008 Lecture Notes in Computer Science, vol. 5461, 2008, Springer-Verlag, 98–115.
Ziv Kfir, Avishai Wool, Picking virtual pockets using relay attacks on contactless smartcard, in: First International Conference on Security and Privacy for Emerging Areas in Communications Networks, SecureComm-2005, 2005, pp. 47–58.
Lishoy Francis, Gerhard P. Hancke, Keith Mayes, Konstantinos Markantonakis, Practical NFC peer-to-peer relay attack using mobile phones, in: Radio Frequency Identification: Security and Privacy Issues - 6th International Workshop, RFIDSec 2010, Istanbul, Turkey, June 8-9, 2010, Revised Selected Papers, 2010, pp. 35–49.
Hancke, Gerhard P., Practical attacks on proximity identification systems (short paper). Proceedings of the 2006 IEEE Symposium on Security and Privacy, SP ’06, 2006, IEEE Computer Society, Washington, DC, USA 0-7695-2574-1, 328–333, 10.1109/SP.2006.30.
Aurélien Francillon, Boris Danev, Srdjan Capkun, Relay Attacks on Passive Keyless Entry and Start Systems in Modern Cars, in: Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, California, USA, 6th February - 9th February 2011, 2011.
Boureanu, Ioana, Mitrokotsa, Aikaterini, Vaudenay, Serge, Practical and provably secure distance-bounding. Desmedt, Yvo, (eds.) Information Security, 2015, Springer International Publishing, Cham 978-3-319-27659-5, 248–258.
Debant, Alexandre, Delaune, Stéphanie, Wiedling, Cyrille, So near and yet so far - symbolic verification of distance-bounding protocols. ACM Trans. Priv. Secur. 25:2 (2022), 11:1–11:39, 10.1145/3501402.
Avoine, Gildas, Floerkemeier, Christian, Martin, Benjamin, RFID distance bounding multistate enhancement. Proc. Progress in Cryptology, INDOCRYPT’09 LNCS, vol. 5922, 2009, Springer, 290–307.
Avoine, Gildas, Mauw, Sjouke, Trujillo-Rasua, Rolando, Comparing distance bounding protocols: A critical mission supported by decision theory. Comput. Commun. 67 (2015), 92–102.