A Prover-Anonymous and Terrorist-Fraud Resistant Distance Bounding Protocol

Xavier Bultel, Sébastian Gambs, David Gérault, Pascal Lafourcade, Cristina Onete, Jean-Marc Robert

Contactless communications have become omnipresent in our daily lives, from simple access cards to electronic passports. Such systems are particularly vulnerable to relay attacks, in which an adversary relays the messages from a prover to a verifier. Distance-bounding protocols were introduced to counter such attacks. Lately, there has been a very active research trend on improving the security of these protocols, but also on ensuring strong privacy properties with respect to active adversaries and malicious verifiers.

In particular, a difficult threat to address is the terrorist fraud, in which a far-away prover cooperates with a nearby accomplice to fool a verifier. The usual defence against this attack is to make it impossible for the accomplice to succeed unless the prover provides him with enough information to recover his secret key and impersonate him later on. However, the mere existence of a long-term secret key is problematic with respect to privacy.

In this paper, we propose a novel approach in which the prover who wants to help his accomplice to authenticate does not leak his secret key but a reusable session key along with a group signature on it. This allows the adversary to impersonate him even without knowing his signature key. Based on this approach, we give the first distance-bounding protocol, called SPADE, integrating anonymity, revocability and provable resistance to standard threat models.

Estimating the distance (or, typically, a bound of the distance) of two nodes (devices) leveraging RF communication in the presence of adversaries has received extensive attention in the literature. A class of attacks, termed “terrorist fraud attacks”, are perpetrated by a remote malicious “prover” and its accomplice, a device that is close(r) to the “verifier” (to be misled that the prover is not as far as it actually is). The approach to thwart a terrorist fraud relies on the assumption that the malicious prover would not be willing to leak private information to its accomplice (e.g., its private, signing key). Of course, if it did so willingly, the attack would be easily successful. Along these lines, this paper works on the same approach while adding anonymous authentication: a “session key” is signed with a “group signature” and an alternative mechanism (that could make the verifier provide anyone with ‘enough information’ the session key) is added to deter the malicious prover from leaking information.

The reviewing process appreciated the novelty of the proposed scheme and the solid technical treatment of the problem at hand. At the same time, it brought forth a number of discussion or, possibly, debate, points. For example: under what conditions can the protocol defend against an accomplice that obtained cryptographically transformed information (granted, not a private key)? What is the spectrum of protection one can consider and how meaningful is it in this context to do so based on probabilities? What is a use-case or real-world scenario that could best fit the protocol elaborated in this paper? In the end, the consensus within the TPC was that this combination of technically solid work and the stimulating questions it raises, would make the paper a good contribution to the program.