Mobile and Ubiquitous Systems: Computing, Networking, and Services. 10th International Conference, MOBIQUITOUS 2013, Tokyo, Japan, December 2-4, 2013, Revised Selected Papers

Research Article

Complexity of Distance Fraud Attacks in Graph-Based Distance Bounding

Download
359 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-11569-6_23,
        author={Rolando Trujillo-Rasua},
        title={Complexity of Distance Fraud Attacks in Graph-Based Distance Bounding},
        proceedings={Mobile and Ubiquitous Systems: Computing, Networking, and Services. 10th International Conference, MOBIQUITOUS 2013, Tokyo, Japan, December 2-4, 2013,  Revised Selected Papers},
        proceedings_a={MOBIQUITOUS},
        year={2014},
        month={12},
        keywords={Security Relay attack Distance bounding Most frequent sequence Graph NP-complete NP-hard},
        doi={10.1007/978-3-319-11569-6_23}
    }
    
  • Rolando Trujillo-Rasua
    Year: 2014
    Complexity of Distance Fraud Attacks in Graph-Based Distance Bounding
    MOBIQUITOUS
    Springer
    DOI: 10.1007/978-3-319-11569-6_23
Rolando Trujillo-Rasua1,*
  • 1: University of Luxembourg, SnT
*Contact email: rolando.trujillo@uni.lu

Abstract

             (DB) emerged as a countermeasure to the so-called , which affects several technologies such as RFID, NFC, Bluetooth, and Ad-hoc networks. A prominent family of DB protocols are those based on graphs, which were introduced in 2010 to resist both mafia and distance frauds. The security analysis in terms of distance fraud is performed by considering an adversary that, given a vertex labeled graph  and a vertex , is able to find the most frequent -long sequence in  starting from  (MFS problem). However, to the best of our knowledge, it is still an open question whether the distance fraud security can be computed considering the aforementioned adversarial model. Our first contribution is a proof that the MFS problem is NP-Hard even when the graph is constrained to meet the requirements of a graph-based DB protocol. Although this result does not invalidate the model, it does suggest that a  adversary is perhaps being considered (, in practice, graph-based DB protocols might resist distance fraud better than the security model suggests.) Our second contribution is an algorithm addressing the distance fraud security of the tree-based approach due to Avoine and Tchamkerten. The novel algorithm improves the computational complexity  of the naive approach to  where  is the number of rounds.