{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T10:18:30Z","timestamp":1763201910273,"version":"3.41.0"},"reference-count":49,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2015,6,3]],"date-time":"2015-06-03T00:00:00Z","timestamp":1433289600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2015,6,3]]},"abstract":"<jats:p>Abstract<\/jats:p><jats:p>From contactless payments to remote car unlocking, many applications are vulnerable to relay attacks. Distance bounding protocols are the main practical countermeasure against these attacks. In this paper, we present a formal analysis of SKI, which recently emerged as the first family of lightweight and provably secure distance bounding protocols. More precisely, we explicate a general formalism for distance-bounding protocols, which lead to this practical and provably secure class of protocols (and it could lead to others). We prove that SKI and its variants are provably secure, even under the real-life setting of noisy communications, against the main types of relay attacks: distance-fraud and generalised versions of mafia- and terrorist-fraud. To attain resistance to terrorist-fraud, we reinforce the idea of using secret sharing, combined with the new notion of a leakage scheme. In view of resistance to generalised mafia-frauds (and terrorist-frauds), we present the notion of circular-keying for pseudorandom functions (PRFs); this notion models the employment of a PRF, with possible linear reuse of the key. We also identify the need of PRF masking to fix common mistakes in existing security proofs\/claims. Finally, we enhance our design to guarantee resistance to terrorist-fraud in the presence of noise.<\/jats:p>","DOI":"10.3233\/jcs-140518","type":"journal-article","created":{"date-parts":[[2015,7,1]],"date-time":"2015-07-01T15:53:12Z","timestamp":1435765992000},"page":"229-257","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":32,"title":["Practical and provably secure distance-bounding"],"prefix":"10.1177","volume":"23","author":[{"given":"Ioana","family":"Boureanu","sequence":"first","affiliation":[{"name":"Akamai Technology Limited, London, UK. E-mail:\u00a0"}]},{"given":"Aikaterini","family":"Mitrokotsa","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Gothenburg, Sweden. E-mail:\u00a0"}]},{"given":"Serge","family":"Vaudenay","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), Lausanne, Switzerland. E-mail:\u00a0"}]}],"member":"179","published-online":{"date-parts":[[2015,6,3]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-2010-0408"},{"key":"ref002","doi-asserted-by":"crossref","unstructured":"[2]G.\u00a0Avoine, C.\u00a0Lauradoux and B.\u00a0Martin, How secret-sharing can defeat terrorist fraud, in: Proceedings of the 4th ACM Conference on Wireless Network Security \u2013 WiSec\u201911, June 2011, Hamburg, Germany, ACM Press, 2011.","DOI":"10.1145\/1998412.1998437"},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"[3]G.\u00a0Avoine and A.\u00a0Tchamkerten, An efficient distance bounding RFID authentication protocol: balancing false-acceptance rate and memory requirement, in: Proceedings of Information Security, Lecture Notes in Computer Science, Vol.\u00a05735, Springer, 2009, pp.\u00a0250\u2013261.","DOI":"10.1007\/978-3-642-04474-8_21"},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"[4]A.\u00a0Bay, I.C.\u00a0Boureanu, A.\u00a0Mitrokotsa, I.D.\u00a0Spulber and S.\u00a0Vaudenay, The Bussard\u2013Bagga and other distance-bounding protocols under attacks, in: The 88th China International Conference on Information Security and Cryptology (Inscrypt 2012), 2012.","DOI":"10.1007\/978-3-642-38519-3_23"},{"key":"ref005","doi-asserted-by":"crossref","unstructured":"[5]M.\u00a0Bellare and P.\u00a0Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in: Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS\u201993, ACM, New York, NY, USA, 1993, pp.\u00a062\u201373.","DOI":"10.1145\/168588.168596"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"[6]T.\u00a0Beth and Y.\u00a0Desmedt, Identification tokens or: solving the chess grandmaster problem, in: Proceedings of CRYPTO 1990, Lecture Notes in Computer Science, Springer, 1991, pp.\u00a0169\u2013176.","DOI":"10.1007\/3-540-38424-3_12"},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"[7]I.\u00a0Boureanu, A.\u00a0Mitrokotsa and S.\u00a0Vaudenay, On the pseudorandom function assumption in (secure) distance-bounding protocols, in: Progress in Cryptology \u2013 LATINCRYPT 2012, A.\u00a0Hevia and G.\u00a0Neven, eds, Lecture Notes in Computer Science, Springer, 2012, pp.\u00a0100\u2013120.","DOI":"10.1007\/978-3-642-33481-8_6"},{"key":"ref008","first-page":"465","volume":"2013","author":"Boureanu I.","year":"2013","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"[9]I.\u00a0Boureanu, A.\u00a0Mitrokotsa and S.\u00a0Vaudenay, Practical and provably secure distance-bounding, in: The 16th Information Security Conference (ISC 2013), Lecture Notes in Computer Science, Springer, 2013, to appear.","DOI":"10.1007\/978-3-662-43933-3_4"},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"[10]I.\u00a0Boureanu, A.\u00a0Mitrokotsa and S.\u00a0Vaudenay, Secure & lightweight distance-bounding, in: Proceedings of LIGHTSEC 2013, Lecture Notes in Computer Science, Vol.\u00a08162, Springer, 2013, pp.\u00a097\u2013113.","DOI":"10.1007\/978-3-642-40392-7_8"},{"key":"ref011","doi-asserted-by":"crossref","unstructured":"[11]I.\u00a0Boureanu, A.\u00a0Mitrokotsa and S.\u00a0Vaudenay, Towards secure distance bounding, in: The 20th Anniversary Annual Fast Software Encryption (FSE 2013), Lecture Notes in Computer Science, Springer, 2013.","DOI":"10.1007\/978-3-662-43933-3_4"},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"[12]S.\u00a0Brands and D.\u00a0Chaum, Distance-bounding protocols (extended abstract), in: EUROCRYPT, 1993, pp.\u00a0344\u2013359.","DOI":"10.1007\/3-540-48285-7_30"},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"[13]L.\u00a0Bussard and W.\u00a0Bagga, Distance-bounding proof of knowledge to avoid real-time attacks, in: Security and Privacy in the Age of Ubiquitous Computing, IFIP TC11 20th International Conference on Information Security (SEC 2005), May 30\u2013June 1, 2005, Springer, Chiba, Japan, pp.\u00a0223\u2013238, 2005.","DOI":"10.1007\/0-387-25660-1_15"},{"key":"ref014","unstructured":"[14]L.\u00a0Bussard and W.\u00a0Bagga, Distance-bounding proof of knowledge protocols to avoid terrorist fraud attacks, Technical Report RR-04-109, Institute EURECOM, May 2004."},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"[15]N.\u00a0Chandran, V.\u00a0Goyal, R.\u00a0Moriarty and R.\u00a0Ostrovsky, Position based cryptography, in: Proceedings Advances in Cryptology \u2013 CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, 16\u201320 August 2009, S.\u00a0Halevi, ed. Lecture Notes in Computer Science, Vol.\u00a05677, Springer, pp.\u00a0391\u2013407, 2009.","DOI":"10.1007\/978-3-642-03356-8_23"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"ref017","unstructured":"[17]C.\u00a0Cremers, K.B.\u00a0Rasmussen and S.\u00a0\u010capkun, Distance hijacking attacks on distance bounding protocols, Cryptology ePrint Archive, Report 2011\/129, 2011, available at: http:\/\/eprint.iacr.org\/."},{"key":"ref018","doi-asserted-by":"crossref","unstructured":"[18]C.\u00a0Cremers, K.B.\u00a0Rasmussen and S.\u00a0\u010capkun, Distance hijacking attacks on distance bounding protocols, in: IEEE Symposium on Security and Privacy, 2012, pp.\u00a0113\u2013127.","DOI":"10.1109\/SP.2012.17"},{"key":"ref019","unstructured":"[19]Y.\u00a0Desmedt, Major security problems with the \u201cUnforgeable\u201d (Feige)\u2013Fiat\u2013Shamir proofs of identity and how to overcome them, in: Proceedings of the 6th Worldwide Congress on Computer and Communications Security and Protection \u2013 SecuriCom\u201988, 15\u201317 March 1988, Paris, France, 1988, pp.\u00a0147\u2013159, SEDEP."},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"[20]C.\u00a0Dimitrakakis, A.\u00a0Mitrokotsa and S.\u00a0Vaudenay, Expected loss bounds for authentication in constrained channels, in: Proceedings of INFOCOM 2012, Orlando, FL, USA, March 2012, IEEE Press, 2012, pp.\u00a0478\u2013485.","DOI":"10.1109\/INFCOM.2012.6195788"},{"key":"ref021","unstructured":"[21]S.\u00a0Drimer and S.J.\u00a0Murdoch, Keep your enemies close: distance bounding against smartcard relay attacks, in: Proceedings of 16th USENIX Security Symposium, USENIX Association, Berkeley, CA, USA, 2007, pp.\u00a07:1\u20137:16."},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"[22]U.\u00a0D\u00fcrholz, M.\u00a0Fischlin, M.\u00a0Kasper and C.\u00a0Onete, A formal approach to distance bounding RFID protocols, in: Proceedings of the 14th Information Security Conference ISC 2011, Lecture Notes in Computer Science, Springer, 2011, pp.\u00a047\u201362.","DOI":"10.1007\/978-3-642-24861-0_4"},{"key":"ref023","doi-asserted-by":"crossref","unstructured":"[23]M.\u00a0Fischlin and C.\u00a0Onete, Subtle kinks in distance-bounding: an analysis of prominent protocols, in: Proceedings of WISEC 2013, ACM, 2013, pp.\u00a0195\u2013206.","DOI":"10.1145\/2462096.2462128"},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"[24]M.\u00a0Fischlin and C.\u00a0Onete, Terrorism in distance bounding: modelling terrorist-fraud resistance, in: Proceedings of ACNS 2013, Lecture Notes in Computer Science, Springer, 2013, pp.\u00a0414\u2013431.","DOI":"10.1007\/978-3-642-38980-1_26"},{"key":"ref025","unstructured":"[25]Ford, Safe and secureSecuriCode\u2122\u00a0keyless entry, 2011, available at: http:\/\/www.ford.com\/technology\/."},{"key":"ref026","unstructured":"[26]A.\u00a0Francillon, B.\u00a0Danev and S.\u00a0\u010capkun, Relay attacks on passive keyless entry and start systems in modern cars, in: Proceedings of the 18th Annual Network & Distributed System Security Symposium (NDSS\u201911), San Diego, CA, USA, 2011."},{"key":"ref027","unstructured":"[27]O.\u00a0Goldreich, Foundations of Cryptography, Vol.\u00a01, Cambridge Univ. Press, New York, NY, USA, 2006."},{"key":"ref028","unstructured":"[28]G.P.\u00a0Hancke, Distance bounding for RFID: effectiveness of terrorist fraud, in: Proceedings of IEEE RFID-TA, IEEE, 2012."},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"[29]G.P.\u00a0Hancke and M.G.\u00a0Kuhn, An RFID distance bounding protocol, in: SECURECOMM, ACM, 2005, pp.\u00a067\u201373.","DOI":"10.1109\/SECURECOMM.2005.56"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2009.06.001"},{"key":"ref031","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"ref032","doi-asserted-by":"crossref","unstructured":"[32]G.\u00a0Kapoor, W.\u00a0Zhou and S.\u00a0Piramuthu, Distance bounding protocol for multiple RFID tag authentication, in: Proceedings of the 2008 IEEE\/IFIP International Conference on Embedded and Ubiquitous Computing, Vol. 02 \u2013 EUC\u201908, Shanghai, China, December 2008, C.Z.\u00a0Xu and M.\u00a0Guo, eds, IEEE Computer Society, 2008, pp.\u00a0115\u2013120.","DOI":"10.1109\/EUC.2008.48"},{"key":"ref033","doi-asserted-by":"crossref","unstructured":"[33]C.H.\u00a0Kim and G.\u00a0Avoine, RFID distance bounding protocol with mixed challenges to prevent relay attacks, in: Proceedings of the 8th International Conference on Cryptology and Networks Security (CANS 2009), Lecture Notes in Computer Science, Vol.\u00a05888, Springer, 2009, pp.\u00a0119\u2013131.","DOI":"10.1007\/978-3-642-10433-6_9"},{"key":"ref034","doi-asserted-by":"crossref","unstructured":"[34]C.H.\u00a0Kim, G.\u00a0Avoine, F.\u00a0Koeune, F.\u00a0Standaert and O.\u00a0Pereira, The swiss-knife RFID distance bounding protocol, in: International Conference on Information Security and Cryptology \u2013 ICISC, December 2008, Lecture Notes in Computer Science, Springer, 2008.","DOI":"10.1007\/978-3-642-00730-9_7"},{"key":"ref035","doi-asserted-by":"publisher","DOI":"10.1002\/wcm.590"},{"key":"ref036","doi-asserted-by":"crossref","unstructured":"[36]J.\u00a0Munilla and A.\u00a0Peinado, Security analysis of Tu and Piramuthu\u2019s protocol, in: New Technologies, Mobility and Security\u00a0\u2013 NTMS\u201908, Tangier, Morocco, November 2008, IEEE Computer Society, 2008, pp.\u00a01\u20135.","DOI":"10.1109\/NTMS.2008.ECP.88"},{"key":"ref037","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2010.01.002"},{"key":"ref038","unstructured":"[38]K.B.\u00a0Rasmussen and S.\u00a0\u010capkun, Realization of RF distance bounding, in: Proceedings of the 19th USENIX Conference on Security, USENIX Security\u201910, USENIX Association, Berkeley, CA, USA, 2010, p.\u00a025."},{"key":"ref039","doi-asserted-by":"crossref","unstructured":"[39]J.\u00a0Reid, J.M.\u00a0Gonzalez Nieto, T.\u00a0Tang and B.\u00a0Senadji, Detecting relay attacks with timing-based protocols, in: ASIACCS\u201907: Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, ACM, 2007, pp.\u00a0204\u2013213.","DOI":"10.1145\/1229285.1229314"},{"key":"ref040","unstructured":"[40]A.\u00a0Schuster and J.\u00a0Nicholson, An Introduction to the Theory of Optics, 3rd edn, Edward Arnold, London, 1924."},{"key":"ref041","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"ref042","unstructured":"[42]V.\u00a0Shoup, Sequences of games: a tool for taming complexity in security proofs, Manuscript, 2006."},{"key":"ref043","doi-asserted-by":"crossref","unstructured":"[43]D.\u00a0Singel\u00e9e and B.\u00a0Preneel, Distance bounding in noisy environments, in: Proceedings of the European Workshop on Security and Privacy in Ad-Hoc and Sensor Networks (ESAS), Lecture Notes in Computer Science, Vol.\u00a04572, Springer, 2007, pp.\u00a0101\u2013115.","DOI":"10.1007\/978-3-540-73275-4_8"},{"key":"ref044","doi-asserted-by":"crossref","unstructured":"[44]B.\u00a0Toiruul, K.O.\u00a0Lee and J.M.\u00a0Kim, SLAP \u2013 a secure but light authentication protocol for RFID based on modular exponentiation, in: International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies, November 2007, 2007, pp.\u00a029\u201334.","DOI":"10.1109\/UBICOMM.2007.39"},{"key":"ref045","doi-asserted-by":"crossref","unstructured":"[45]R.\u00a0Trujillo-Rasua, B.\u00a0Martin and G.\u00a0Avoine, The Poulidor distance-bounding protocol, in: RFIDSec 2010, 2010, pp.\u00a0239\u2013257.","DOI":"10.1007\/978-3-642-16822-2_19"},{"key":"ref046","unstructured":"[46]Y.J.\u00a0Tu and S.\u00a0Piramuthu, RFID distance bounding protocols, in: Proceedings of the First International EURASIP Workshop on RFID Technology, 2007."},{"key":"ref047","doi-asserted-by":"crossref","unstructured":"[47]S.\u00a0Vaudenay, On privacy models for RFID, in: Proceedings on Advances in Cryptology, ASIACRYPT\u201907, Springer, New York, NY, USA, 2007, pp.\u00a068\u201387.","DOI":"10.1007\/978-3-540-76900-2_5"},{"key":"ref048","doi-asserted-by":"crossref","unstructured":"[48]S.\u00a0Vaudenay, On modeling terrorist frauds, in: Proceedings of PROVSEC 2013, Lecture Notes in Computer Science, Vol.\u00a08209, Springer, 2013, pp.\u00a01\u201320.","DOI":"10.1007\/978-3-642-41227-1_1"},{"key":"ref049","doi-asserted-by":"crossref","unstructured":"[49]A.\u00a0Yang, Y.\u00a0Zhuang and D.S.\u00a0Wong, An efficient single-slow-phase mutually authenticated RFID distance bounding protocol with tag privacy, in: Proceedings of the 14th International Conference on Information and Communications Security, ICICS\u201912, Springer, Heidelberg, 2012, pp.\u00a0285\u2013292.","DOI":"10.1007\/978-3-642-34129-8_25"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-140518","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-140518","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-140518","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T23:49:09Z","timestamp":1748476149000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-140518"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,3]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6,3]]}},"alternative-id":["10.3233\/JCS-140518"],"URL":"https:\/\/doi.org\/10.3233\/jcs-140518","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"type":"print","value":"0926-227X"},{"type":"electronic","value":"1875-8924"}],"subject":[],"published":{"date-parts":[[2015,6,3]]}}}