Sage Journals: Discover world-class research

Abstract

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.

Keywords

Distance-bounding authentication relay attacks provable security man-in-the-middle attacks

Get full access to this article

View all access options for this article.

References

[1]

Avoine,

Bingöl,

Kardas,

Lauradoux and

Martin, A framework for analyzing RFID distance bounding protocols, Journal of Computer Security 19(2) (2011), 289–317.

[2]

Avoine,

Lauradoux and

Martin, How secret-sharing can defeat terrorist fraud, in: Proceedings of the 4th ACM Conference on Wireless Network Security – WiSec’11, June 2011, Hamburg, Germany, ACM Press, 2011.

[3]

Avoine and

Tchamkerten, 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. 5735, Springer, 2009, pp. 250–261.

[4]

Bay,

I.C.

Boureanu,

Mitrokotsa,

I.-D.

Spulber and

Vaudenay, The Bussard–Bagga and other distance-bounding protocols under attacks, in: The 88th China International Conference on Information Security and Cryptology (Inscrypt 2012), 2012.

[5]

Bellare and

Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in: Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS’93, ACM, New York, NY, USA, 1993, pp. 62–73.

[6]

Beth and

Desmedt, Identification tokens or: solving the chess grandmaster problem, in: Proceedings of CRYPTO 1990, Lecture Notes in Computer Science, Springer, 1991, pp. 169–176.

[7]

Boureanu,

Mitrokotsa and

Vaudenay, On the pseudorandom function assumption in (secure) distance-bounding protocols, in: Progress in Cryptology – LATINCRYPT 2012,

Hevia and

Neven, eds, Lecture Notes in Computer Science, Springer, 2012, pp. 100–120.

[8]

Boureanu,

Mitrokotsa and

Vaudenay, Practical & provably secure distance-bounding, IACR Cryptology ePrint Archive 2013 (2013), 465.

[9]

Boureanu,

Mitrokotsa and

Vaudenay, Practical and provably secure distance-bounding, in: The 16th Information Security Conference (ISC 2013), Lecture Notes in Computer Science, Springer, 2013, to appear.

10.

[10]

Boureanu,

Mitrokotsa and

Vaudenay, Secure & lightweight distance-bounding, in: Proceedings of LIGHTSEC 2013, Lecture Notes in Computer Science, Vol. 8162, Springer, 2013, pp. 97–113.

11.

[11]

Boureanu,

Mitrokotsa and

Vaudenay, Towards secure distance bounding, in: The 20th Anniversary Annual Fast Software Encryption (FSE 2013), Lecture Notes in Computer Science, Springer, 2013.

12.

[12]

Brands and

Chaum, Distance-bounding protocols (extended abstract), in: EUROCRYPT, 1993, pp. 344–359.

13.

[13]

Bussard and

Bagga, 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–June 1, 2005, Springer, Chiba, Japan, pp. 223–238, 2005.

14.

[14]

Bussard and

Bagga, Distance-bounding proof of knowledge protocols to avoid terrorist fraud attacks, Technical Report RR-04-109, Institute EURECOM, May 2004.

15.

[15]

Chandran,

Goyal,

Moriarty and

Ostrovsky, Position based cryptography, in: Proceedings Advances in Cryptology – CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2009,

Halevi, ed., Lecture Notes in Computer Science, Vol. 5677, Springer, pp. 391–407, 2009.

16.

[16]

Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, The Annals of Mathematical Statistics 23(4) (1952), 493–507.

17.

[17]

Cremers,

K.B.

Rasmussen and

Čapkun, Distance hijacking attacks on distance bounding protocols, Cryptology ePrint Archive, Report 2011/129, 2011, available at: http://eprint.iacr.org/.

18.

[18]

Cremers,

K.B.

Rasmussen and

Čapkun, Distance hijacking attacks on distance bounding protocols, in: IEEE Symposium on Security and Privacy, 2012, pp. 113–127.

19.

[19]

Desmedt, Major security problems with the “Unforgeable” (Feige)–Fiat–Shamir proofs of identity and how to overcome them, in: Proceedings of the 6th Worldwide Congress on Computer and Communications Security and Protection – SecuriCom’88, 15–17 March 1988, Paris, France, 1988, pp. 147–159, SEDEP.

20.

[20]

Dimitrakakis,

Mitrokotsa and

Vaudenay, Expected loss bounds for authentication in constrained channels, in: Proceedings of INFOCOM 2012, Orlando, FL, USA, March 2012, IEEE Press, 2012, pp. 478–485.

21.

[21]

Drimer and

S.J.

Murdoch, Keep your enemies close: distance bounding against smartcard relay attacks, in: Proceedings of 16th USENIX Security Symposium, USENIX Association, Berkeley, CA, USA, 2007, pp. 7:1–7:16.

22.

[22]

Dürholz,

Fischlin,

Kasper and

Onete, 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. 47–62.

23.

[23]

Fischlin and

Onete, Subtle kinks in distance-bounding: an analysis of prominent protocols, in: Proceedings of WISEC 2013, ACM, 2013, pp. 195–206.

24.

[24]

Fischlin and

Onete, Terrorism in distance bounding: modelling terrorist-fraud resistance, in: Proceedings of ACNS 2013, Lecture Notes in Computer Science, Springer, 2013, pp. 414–431.

25.

[25]Ford, Safe and secure SecuriCode™ keyless entry, 2011, available at: http://www.ford.com/technology/.

26.

[26]

Francillon,

Danev and

Čapkun, Relay attacks on passive keyless entry and start systems in modern cars, in: Proceedings of the 18th Annual Network & Distributed System Security Symposium (NDSS’11), San Diego, CA, USA, 2011.

27.

[27]

Goldreich, Foundations of Cryptography, Vol. 1, Cambridge Univ. Press, New York, NY, USA, 2006.

28.

[28]

G.P.

Hancke, Distance bounding for RFID: effectiveness of terrorist fraud, in: Proceedings of IEEE RFID-TA, IEEE, 2012.

29.

[29]

G.P.

Hancke and

M.G.

Kuhn, An RFID distance bounding protocol, in: SECURECOMM, ACM, 2005, pp. 67–73.

30.

[30]

G.P.

Hancke,

K.E.

Mayes and

Markantonakis, Confidence in smart token proximity: relay attacks revisited, Computers & Security 28(7) (2009), 404–408.

31.

[31]

Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58(301) (1963), 13–30.

32.

[32]

Kapoor,

Zhou and

Piramuthu, Distance bounding protocol for multiple RFID tag authentication, in: Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, Vol. 02 – EUC’08, Shanghai, China, December 2008,

C.-Z.

Xu and

Guo, eds, IEEE Computer Society, 2008, pp. 115–120.

33.

[33]

C.H.

Kim and

Avoine, 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. 5888, Springer, 2009, pp. 119–131.

34.

[34]

C.H.

Kim,

Avoine,

Koeune,

Standaert and

Pereira, The swiss-knife RFID distance bounding protocol, in: International Conference on Information Security and Cryptology – ICISC, December 2008, Lecture Notes in Computer Science, Springer, 2008.

35.

[35]

Munilla and

Peinado, Distance bounding protocols for RFID enhanced by using void-challenges and analysis in noisy channels, Wireless Communications and Mobile Computing 8 (2008), 1227–1232.

36.

[36]

Munilla and

Peinado, Security analysis of Tu and Piramuthu’s protocol, in: New Technologies, Mobility and Security – NTMS’08, Tangier, Morocco, November 2008, IEEE Computer Society, 2008, pp. 1–5.

37.

[37]

Munilla and

Peinado, Attacks on a distance bounding protocol, Computer Communications 33 (2010), 884–889.

38.

[38]

K.B.

Rasmussen and

Čapkun, Realization of RF distance bounding, in: Proceedings of the 19th USENIX Conference on Security, USENIX Security’10, USENIX Association, Berkeley, CA, USA, 2010, p. 25.

39.

[39]

Reid,

J.M.

Gonzalez Nieto,

Tang and

Senadji, Detecting relay attacks with timing-based protocols, in: ASIACCS’07: Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, ACM, 2007, pp. 204–213.

40.

[40]

Schuster and

Nicholson, An Introduction to the Theory of Optics, 3rd edn, Edward Arnold, London, 1924.

41.

[41]

Shamir, How to share a secret, Communications of the ACM 22 (1979), 612–613.

42.

[42]

Shoup, Sequences of games: a tool for taming complexity in security proofs, Manuscript, 2006.

43.

[43]

Singelée and

Preneel, 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. 4572, Springer, 2007, pp. 101–115.

44.

[44]

Toiruul,

K.O.

Lee and

J.M.

Kim, SLAP – 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. 29–34.

45.

[45]

Trujillo-Rasua,

Martin and

Avoine, The Poulidor distance-bounding protocol, in: RFIDSec 2010, 2010, pp. 239–257.

46.

[46]

Y.-J.

Tu and

Piramuthu, RFID distance bounding protocols, in: Proceedings of the First International EURASIP Workshop on RFID Technology, 2007.

47.

[47]

Vaudenay, On privacy models for RFID, in: Proceedings on Advances in Cryptology, ASIACRYPT’07, Springer, New York, NY, USA, 2007, pp. 68–87.

48.

[48]

Vaudenay, On modeling terrorist frauds, in: Proceedings of PROVSEC 2013, Lecture Notes in Computer Science, Vol. 8209, Springer, 2013, pp. 1–20.

49.

[49]

Yang,

Zhuang and

D.S.

Wong, 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’12, Springer, Heidelberg, 2012, pp. 285–292.