A new implementation methodology for a secure distance bounding protocol

Vom Fachbereich

Mohammad Reza Sohizadeh Abyaneh

Jingxian Zhou

Xifan Zheng

Location (or distance) information of a device plays a significant role in current location-based systems. How to determine the location of a device or verify the location claims made by a device is challenging, as devices are untrusted and may have an incentive to claim a false location. In secure localization and positioning system, the trusted verifier(s) interact with the untrusted prover to determine its location or validate its location claim. In this thesis, we mainly focus on one of the prominent areas of such systems: distance bounding. Distance (upper) bounding (DUB) allows a verifier to verify whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location-based services. This thesis has two main contributions. The first is that we consider the dual problem of distance lower bounding (DLB), where the prover proves it is outside a distance bound from the verifier. We motivate this problem through a number of application scenarios and model security against distance fraud (DF), Man-in-the-Middle (MiM), and collusion fraud (CF) attacks. We prove impossibility of security against these attacks without making physical assumptions. We propose approaches to the construction of secure protocols under reasonable physical assumptions and give detailed design of a DLB protocol with security analysis using our proposed model. This is the first treatment of the DLB problem in the untrusted prover setting with a number of applications, raising new research directions and opportunities in location based services. We discuss our results and propose directions for future research. One of the main assumptions which DUB protocols rely on is that the time that the prover spends in receiving the challenge, processing, and sending the response is negligible compared to the propagation time of the signal between the prover and verifier. This strict requirement poses difficulties on the implementation of DUB protocols and limits the possible development of applications for distance bounding as well. The second contribution in this thesis is that we design a novel one-round DUB protocol that uses one-way transmission time to estimate the distance instead of round-trip time, so that the assumption of negligible processing time is not required any longer. In order to prove the security, we formalize the notion of time in a distributed environment with adversarial users. In this model, time is implemented by a trusted party broadcasting unpredictable timestamps at a high frequency. We show that the timestamp is proved to be fresh and unpredictable. We then extend the time model to formalize DUB protocols and define corresponding attacks. Finally, we prove the security of our proposed distance bounding protocol and discuss potential issues when implementing such protocol. Besides these two main contributions, we also have the following two contributions: (1) we identify and analyze a new attack: false rejection attack, which poses serious threat to proximity-based authentications that uses distance bounding protocol for proximity evaluation; (2) We investigate the feasibility of replay attack in context-based proximity authentication using real-world data.

Kevin Bogner, Dave Singelée, Aysajan Abidin

This paper introduces an entanglement-based Quantum Distance Bounding (QDB) protocol, whose security derived from Bell’s inequality violation. This protocol leverages the non-locality of quantum entanglement to enhance the integrity and security of quantum channels, providing device-independent assurances. We present both the theoretical framework and a practical implementation scenario using Qiskit. This study lays the groundwork for rigorous future analyses and the refinement of QDB protocols.

Ioana Boureanu, Serge Vaudenay B

Abstract. Provably secure distance-bounding is a rising subject, yet an unsettled one; indeed, very few distance-bounding protocols, with formal security proofs, have been proposed. In fact, so far only two protocols, namely SKI (by Boureanu et al.) and FO (by Fischlin and Onete), offer all-encompassing security guaranties, i.e., resistance to distance-fraud, mafia-fraud, and terrorist-fraud. Matters like security, alongside with soundness, or added tolerance to noise do not always coexist in the (new) distance-bounding designs. Moreover, as we will show in this paper, efficiency and simultaneous protection against all frauds seem to be rather conflicting matters, leading to proposed solutions which were/are sub-optimal. In fact, in this recent quest for provable security, efficiency has been left in the shadow. Notably, the tradeoffs between the security and efficiency have not been studied. In this paper, we will address these limitations, setting the “security vs. efficiency ” record straight. Concretely, by combining ideas from SKI and FO, we propose symmetric protocols that are efficient, noise-tolerant and—at the same time—provably secure against all known frauds. Indeed, our new distance-bounding solutions outperform the two aforementioned provably secure distance-bounding protocols. For instance, with a noise level of 5%, we obtain the same level of security as those of the pre-existent protocols, but we reduce the number of rounds needed from 181 to 54. 1