Practical and provably secure distance-bounding

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

1. Introduction

Cryptography sees many applications in the world of smart-cards, from the more and more sophisticated NFC bankcards to the simpler RFID access cards. But the security protocols implied (e.g., protocols for ATM systems) are vulnerable to relay attacks or to more general forms of man-in-the-middle attacks. Relay attacks have already been mounted against bankcards [21]. In access control applications, it is not guaranteed that the card computing the responses to the reader’s challenges is indeed the one requiring access [30]. Similarly, car manufacturers use RFID protocols to unlock and even start their vehicles (see, e.g., [25]). However, these protocols may unfortunately be compromised by relaying [26]. The most interesting cryptographic solution to these threats seems to be based on distance-bounding [21].

In [12], Brands and Chaum introduced distance-bounding (DB) protocols, based on some original idea by Beth and Desmedt [6]. They are employed so that a prover may demonstrate his proximity to a verifier as well as authenticate this honest prover to the verifier.1

¹
In this paper, we consider authenticated distance-bounding. Namely: protocols where both participants use a pre-established secret.

In the literature covering such protocols, three main types of possible attacks have been distinguished. The first is distance-fraud, in which a prover tries to convince the verifier that he is closer than he really is. The second type of attack is mafia-fraud and involves three entities: an honest prover, an honest verifier, and an adversary. The adversary communicates with both the prover and the verifier and tries to demonstrate to the verifier that the prover is in the verifier’s proximity although the prover is in reality far away from the verifier. Finally, the third type of attack is denoted as terrorist-fraud.2

The terms “mafia-fraud” and “terrorist-fraud” were introduced in 1988 by Desmedt [19]. Although confusion-prone, these are the ones still used in the literature.

Here, the adversary has the same goal as in the mafia-fraud attack, but in this case the prover is dishonest and colludes with the adversary up to the non-disclosure of essential information, e.g., (parts of) secret keys, that may facilitate later impersonations of this prover.

Ad-hoc countermeasures protecting against one or several such attacks have sometimes been provided [1]. It has also been claimed [33] that DB protocols in their commonly known form cannot protect against all three frauds at a time. Unfortunately, these frauds have become even more dangerous through recent generalisations [18,22]. Nonetheless, DB protocols will most probably soon be implemented by car manufacturers or bank payment companies in their products, as platforms for such deployments arise [38]. In these contexts, security proofs and clear, solid security models become of paramount importance. However, unitary security models and respective compelling security proofs have not yet been formulated with respect to this class of protocols. In the following, we endeavour in overcoming this shortcoming, providing a comprehensive security model for distance-bounding protocols and constructing practical and provably secure protocols in the model herein.

More precisely, in this paper we provide a formal analysis, for SKI the first family of lightweight and provably secure distance bounding protocols3

The SKI protocols were first presented at FSE’13. The name “SKI” comes from the first names of the authors: Serge, Katerina, Ioana.

that was initially introduced in [10,11]. We give a detailed description of the employed formal communication model for distance-bounding protocols. We define formally what a distance-bounding protocol is and we provide formal definitions for the resistance of a distance bounding protocol against the main types of attacks: distance-fraud and generalised versions of mafia- and terrorist-fraud. Furthermore, we describe in detail SKI and its variants. We also provide a detailed design and security assessment that includes the formal proofs for SKI’s resistance against the main relay attacks. We should point out here that in papers [10,11] were SKI was initially introduced the definitions provided were informal while the security proofs were sketched.

2. Related work and state-of-the-art

2.1. Distance bounding – Informal and semi-formal approaches

In this section we provide details on the practical requirements (i.e. tolerance to noisy conditions) for secure distance bounding protocols, review the related work in distance bounding and finally discuss its connection to location based cryptography.

Tolerance to noise

Since distance-bounding protocols operate under time-critical constraints and with rapid-bit exchanges, they are likely to be subject to noise, i.e., to noisy communication channels. So, these protocols often tolerate a few faulty iterations, in such a way that honest executions would succeed with high probability. Of course, noisy, rapid-bit exchanges are a reality of applied cryptographic protocols. However, many research results on DB assume noiseless conditions [1,14,17,45]. In this paper, noise will be taken into consideration in our security assessments.

DB protocols and attacks amendments

Many DB protocols [32,34,39,46] consist of a data agreement phase or initialisation phase and a distance-bounding phase. The distance-bounding phase is time-critical and it normally imposes very fast computation, typically of less than a single clock cycle per round. (Light travels one meter within about three nanoseconds. So, every bit must be treated on the fly, upon arrival, with no delay, and there is no part for any time-consuming computation.) Nevertheless, even if the time-of-flight is critical, some DB protocols are not secure against terrorist-fraud: an attacker can find ingenious ways to collude with provers, defeating DB; an example of the sort is the terrorist-fraud, recently shown against the Bussard and Bagga [13,14]. Hancke and Kuhn [29], Munilla and Peinado [35], Kim and Avoine [33] and Reid et al. [39] proposed follow-ups of each others’ schemes, addressing either a better protection against terrorist-fraud or mafia-fraud, or a better suitability to practice, or a more formal description, etc. In general, attempts to construct secure distance-bounding protocols such as [34,43,46] have been proven flawed [36,37]. In fact, Kim et al. state [33] that there is no DB protocol, which has one-bit challenges/responses per iteration in the distance-bounding phase, resisting all three attacks (i.e., distance-, mafia-, and terrorist-frauds) with a significant probability. In [10,11, Table 1], the popular distance-bounding protocols and their vulnerabilities as best-known up to that point (2013) are reported. That table shows a dire situation, so the question of provable security against all frauds mounted has been standing prominently. Since, two (classes of) protocols (one class in [10] and one protocol in [24]) which are provably secure have been published.

Moreover, more general attacks have been recently described. In [18], Cremers et al. described distance-hijacking as an extension of distance-fraud, yet as an attack that is close to terrorist-fraud at the same time; the fraud involves one dishonest, far-away prover and several honest provers, without the latter colluding with the former. Impersonation (a type of man-in-the-middle) is presented in [22]. In the current work, our threat model also incorporates these latter, powerful attacks.

In [2], a targeted protocol-analysis is carried on the TDB protocol by Avoine et al. They especially address the protection against terrorist-fraud for the Hancke and Kuhn protocol, using secret sharing schemes. However, [2] does not state the sound, (necessary and) sufficient assumptions for combating terrorist-fraud. This will be amended and taken further in this paper; we generalise the underlying idea of using a secret sharing scheme [2] and introduce a taxonomy of security-enforcing conditions (some of which are linked to secret sharing).

Recently, Hancke [28] observed that terrorist-frauds could also be mounted, by simply abusing the aforementioned, noise-tolerance property required from DB. Basically, a malicious prover could help an adversary to answer most challenges and not leak to this adversary the secret key but only a noisy version of the secret key. Also, this leaked information is such that it does not give the adversary any significant advantage in later attacks onto the scheme, i.e., the coerced prover mounts a valid terrorist-fraud. Similar to TDB and the protocols herein, there is the recent protocol in [49]; however, unlike the protocols herein, the protocol in [49] does not resist these new terrorist-frauds in noisy conditions by Hancke [28]. As a matter of fact, all but two protocols allegedly resisting the classical terrorist-frauds as they were known before Hancke’s observation would now collapse under terrorist-frauds executed in this new scenario of Hancke’s (at least, cf. to [10,11, Table 1]). The protocols left standing in front of this attack are the SKI protocols [10,11] to be studied herein and the Fischlin–Onete protocol [24].

Position-based cryptography and distance bounding

Position-based cryptography (PBC) [15] becomes possible through secure positioning (SP), which involves a set of verifiers ensuring that a given prover is indeed at some claimed position. In other words, in PBC a verifier within the network not only estimates the distance to another device but is also helped by, e.g., trusted base-stations that offer position-data for coordinate-triangulation in his final decisions. In SP, this assistance by, e.g., base-stations can happen repeatedly, to defend against malicious behaviour. This is not the case in DB, where the verifier is on his own, with his much simpler measurements at hand. However, distance-bounding protocols could potentially be used as building blocks for SP.

The model needed to achieve PBC bears similarities with the one to follow, yet distance-bounding is a weaker requirement than secure positioning. DB informally implies one prover proving to one verifier only that the former is close enough to the latter, using the time-of-flight of their exchanges. Thus, while the “geometry” needed for achieving distance-bounding is much simpler, the notion of time is of greater importance for distance-bounding.

2.2. State-of-the-art: Towards provable DB security

DB formalisations

In [1], Avoine et al. give a complete but rather informal model for distance-bounding. Herein, we will refer to this line as to the ABKLM model. They define distance-bounding as the combination of authentication and distance-checking. They further carry on a tentative analysis of the Munilla–Peinado protocol [35]. As we will further discuss below, [1] does not clearly state the exact assumptions needed on the underlying primitives in order to achieve the alleged security.

So far, the most promising model for distance-bounding was presented recently by Dürholz et al. in [22]. We refer to it as the DFKO model. This model does not provide a clear communication model and its notions of time or distance are only implicit. It requires to specify protocols by explicitly distinguishing a lazy phase and a time-critical one. The DFKO model formalises the three classical types of frauds and an extra notion of impersonation fraud. The attackers are very specific, presented in terms of protocol session interleaving. Maybe due to this specificity or to their requirements which may be too strict, the model is too strong, fact admitted by its authors in [23]. In this model, certain insecurities (impersonation or terrorist-fraud) are hard-to-defend claims, leading to no convincing attack. Fischlin and Onete later proposed a secure protocol, proven secure in a new, clearer, game-based security model advanced at the same time. This recent protocol is discussed and compared with SKI in [48]; therein, it was observed that the resistance of [24] to terrorist fraud lowered the resistance to mafia fraud.

Security shortcomings in DB

Practical DB should also be attack-proof. But, from the above, one can conclude that provably secure DB is still in the making. When security is rarely attained/proved against one fraud, another resistance is diminished [48]. But, more seriously, some of the literature on distance-bounding uses either unsupported claims of the form “if f is a PRF, then this protocol is secure against…”. In fact, in the line of Boureanu et al. [7], it was proven, by the technique of PRF programming, that if PRFs exist, then these results are incorrect. When employed with some specific PRFs, the TDB [2] protocol, an enhancement of the Kim–Avoine protocol [22], Hancke and Kuhn’s [29] protocol, Avoine and Tchamkerten’s [3], Reid’s et al. [39] protocol, and the Swiss-Knife [34] protocol, they were all shown to be indeed vulnerable to distance-fraud and/or man-in-the-middle attacks. The DB security claims recently disproven by Boureanu et al. [7] seem to come from a mis-use of PRF techniques: replacing a PRF (in security arguments) by a random function at a place where the adversary has access to the PRF key or at a place where the PRF key is simultaneously used at other places in the protocol. In a parallel line, [34] proved that many existing distance-bounding protocols are also subject to mafia-fraud. And, in [4], it is revealed that public-key techniques do not necessarily protect against terrorist-fraud. Also therein, a family of protocols is exposed to generalised mafia-fraud attacks. Finally, Hancke [28] shows that noisy communications and tolerance to them must also be addressed in the security analysis. So, the technicalities of the model to be presented herein, to assure a solid provable security framework, are of utmost importance.

2.3. Contributions

In the context of the shortcomings above, our main contribution is three-fold:

We present a formalism for distance-bounding, which includes a sound communication and adversarial model. In these latter models, we incorporate the notion of time-of-flight for distance-based communication.4

⁴
Since every send/receive action in our model is subject to a maximal transmission speed, there is no distinction between a lazy phase and a time-critical one as in the DFKO model [22,23].

We further formalise security against distance-fraud, man-in-the-middle (MiM) generalising mafia-frauds, and an enhanced version of terrorist-fraud that we call collusion-fraud. As practice dictates, our formalisations take noisy communications into account.

Mainly in the context of security against generalised mafia-frauds (when TF-resistance is also enforced), we introduce the concept of circular-keying security to extend the security of a pseudorandom function (PRF) f to its possible uses in maps of the form $y \mapsto L (x) + f_{x} (y)$ , for a secret key x and a transformation L. We also introduce a leakage scheme, to resist to collusion frauds, and a PRF masking technique to address distance-fraud issues. These formal mechanisms come to counteract mistakes like those in proofs based on PRF-constructions, errors of the kind exposed by Boureanu et al. in [7], and by Hancke in [28].

We analyse variants of the SKI protocol [10,11], leading us to a provably secure, practical class of distance-bounding protocols. On the way to this, we formalise the DB-driven requirements of the SKI protocols’ components. In addition to enjoying provable security, the SKI protocols offer competitive performance and practical security. Especially in terms of suitability to practice, SKI is one of the two DB protocols that resist terrorist-frauds in the presence of noise.

Note: The SKI contribution was first presented at FSE’13 [11] and then at LIGHTSEC’13 [10]. On these both occasions, the protocols were presented without details on a formal model and without their corresponding security proofs. For instance, to justify some security bounds on the classical DB threats, the authors used reasoning related to the best conceivable attacks, but no provable security argument was included. Recently, at ISC’13 [9], a partial security model for SKI and partially developed security proofs were included. In turn, this present article comes with the full, formal security model, full security proofs for all the SKI protocols, as well as all the details on the tight, provable bounds of SKI’s security. With respect to a somewhat similar manuscript [8], we add that the present article contains significant improvements and updates, both on the proofs and on the tightness of the security bounds. We put together and also complete all the pieces needed for the full picture of SKI and its provable security; in this way, this is also the first complete document to provide a recipe on how to design provably secure DB and/or how to (dis)prove the security of existing ones.

3. Model for distance-bounding protocols

We consider a multiparty setting where each participant U is modelled by a polynomially bounded interactive Turing machine (ITM), has a location ${loc}_{U}$ , and where communication messages from a location to another take some time, depending on the distance to travel. Some participants may be corrupted. Some are set up with a pre-shared key. All algorithms are bounded to probabilistic polynomial-time (ppt).

As aforementioned, we model a generic two-party communication protocol by the interactive system run by ITMs [27]; we now fix the notations.5

⁵
We use standard notations for ITMs. Namely, random coins are separated from other inputs by a semicolon or omitted for simplicity. Inputs consist of the initial input and the variable number of incoming messages.

Consider two honest participants P and V, each running a predefined algorithm denoting its side of the interaction to take place. Along standard lines, a general communication is formalised via an experiment, generically denoted

\exp = (P (x; r_{P}) \leftrightarrow V (y; r_{V}))

, where

r_{⟨ \cdot ⟩}

are the random coins of the participants and x is an input of P and y is the input of V. In some cases,

x = y

denoting a long-term shared secret. The experiment above can be “enlarged” with an adversary

A_{0}

who interferes in the communication, up to his abilities (which will be described below). This “enlargement” is hereby denoted as

(P (x; r_{P}) \leftrightarrow A_{0} (r_{A}) \leftrightarrow V (y; r_{V}))

. At the end of each experiment, participant V has an output, denoted,

{Out}_{V}

. The view of a participant on an experiment is the collection of all its initial inputs (including coins) and his incoming messages, i.e., the view of

A_{0}

above subsumes his “communication” with P and his “communication” with V. In the notation

(P (\dots) \leftrightarrow A (\dots) \leftrightarrow V (\dots))

, we may group several participants under the same symbolic name; e.g., we may group several (colluding) malicious participants encapsulated under a single

A

denomination.

Bound on the distance

To our modelling, we add a fixed integer constant $B$ denoting the distance-bound. It defines what it means to be “close-enough” to a verifier V. Hence, the output of a verifier is 1 if the responses authenticate the prover and his estimated6

⁶

This estimation is based on round-trip time, i.e., each response ought to be received before V has $2 B$ standby actions.

location is not further than

B

in the metric space.

3.1. The crux of the DB model

The crux of proving the security of DB protocols lies in Lemma 3.1, stated below.

Informal formulation of Lemma 3.1

By Lemma 3.1, we informally mean the following: if V sends a challenge c, then the answer r from a close-by participant $A$ is locally computed by $A$ itself. In other words, to compute r, the close-by $A$ cannot get any online, real-time help dependent on the challenge c, not from any far-away participant. This is logical: getting distant help dependent on c would mean that this challenge c travelled to that distant location, which in turn would mean failing the time/distance bound.

In more details, in computing such an answer, $A$ would use two parts: (1) its own view gathered up to the arrival of c inclusively; (2) possible material that $A$ may receive before $A$ sends r out; all such material must be independent from c and from all the messages sent to $A$ thereafter, even if it may come from far-away participants $B$ .

The use of Lemma 3.1

We will use this lemma every time when a too-long-distance has an implication on the data-flow. We believe such a clear-cut formalisation eases the proofs. For instance, in the DFKO model [22], the implicitness of timed communications requires an effective distinction between a lazy and a time-critical phase in the runs of the protocols, which may in turn hinder the construction of clear security proofs. The DFKO model also requires to define exhaustively which data flows are allowed (the tainted sessions) for each security notion.

Another way to go about this would have been to introduce a full model in which such a lemma holds; in fact, we do so in Appendix A. Or, yet another way would have been to simply state the text of the lemma and take it axiomatically. Instead, we took the approach of enunciating it formally and proving it.

Lemma 3.1.
Assume an experiment $B (z; r_{B}) \leftrightarrow A (u; r_{A}) \leftrightarrow V (y; r_{V})$ in which the verifier V plays a two-round protocol where he broadcasts a message c, then V receives a response r, and V accepts if r took at most time $2 B$ to arrive. In the experiment, $A$ is the set of all participants which are within a distance up to $B$ to V, and $B$ is the set of all other participants. For each user U, we consider his partial view ${View}_{U}$ which includes all his input until just before the time when U can see the broadcast message c. We say that a message by U is independent from c if it is computed by U before this time (equivalently: if it is the result of applying U on ${View}_{U}$ , or a prefix of it). There exists an algorithm $A$ and a list w of messages independent from c such that if V accepts, then $r = A ({View}_{A}, c, w)$ , where ${View}_{A}$ is the list of all ${View}_{A}$ , $A \in A$ .

w.r.t. the model in Appendix A

We first assume a single participant in $A$ . Figure 1 illustrates the communication flow. Let $(p; r_{A})$ be the partial view such that $r = A (p; r_{A})$ . Clearly, p can be written $p = (v, c, w)$ with $(v; r_{A}) = {View}_{A}$ and a list w of messages from $B$ participants. If w includes a message m not independent from c, there is time for c to arrive to $B$ , to compute m, sent it to $A$ , compute r and sent it to V. Due to the distance between $B$ and V, this is not the case. So, all messages in w are independent from c. This means that, in due time, $A$ cannot get any help from $B$ to answer to c.

Fig. 1.
Adversarial communication flow over time.

With several participants in $A$ , there is one $A \in A$ for which $r = A (v_{A}, c, w_{A}; r_{A})$ and messages in $w_{A}$ are either $A$ messages, and can be written the same (recursively), or $B$ messages which are independent from c.
3.2. Formal distance-bounding

When modelling distance-bounding protocols, we consider provers, denoted by P and verifiers, denoted by V. We let $A$ denote the adversary and $P^{*}$ generally denote dishonest provers. We assume that provers have no output and verifiers output one bit ${Out}_{V}$ denoting acceptance, i.e. ${Out}_{V} = 1$ , or rejection, i.e., ${Out}_{V} = 0$ (e.g., privileges are granted or not). We proceed with the definition of a DB protocol.

Definition 3.1 (Distance-bounding protocols).

A distance-bounding (DB) protocol is defined by a tuple $(Gen, P, V, B)$ , where: (1) $Gen$ is a randomised, key-generation algorithm such that $(x, y)$ is the output7

⁷
We denote this output as $(x, y) \leftarrow Gen (1^{s}; r_{k})$ . For all protocols in this paper, there is just one common input, i.e., we assume $x = y$ .

Gen (1^{s}; r_{k})

, where

r_{k}

are the random coins of

Gen

and s is a security parameter; (2)

P (x; r_{P})

is a ppt. ITM running the algorithm of the prover with input x and random input

r_{P}

; (3)

V (y; r_{V})

is a ppt. ITM running the algorithm of the verifier with input y, and random input

r_{V}

; (4)

B

is a distance-bound. They must be such that the following two facts hold:

Termination: $(\forall s)$ $(\forall R) (\forall r_{k}, r_{V}) (\forall {loc}_{V})$ if $(\cdot, y) \leftarrow Gen (1^{s}; r_{k})$ and $(R \leftrightarrow V (y; r_{V}))$ model the execution, it is the case that V halts in $Poly (s)$ computational steps, where R is any set of (unbounded) algorithms;8

⁸

In the above, only the termination of V is of interest, since it is only the verifier who has a meaningful output.

p-Completeness: $(\forall s)$ $(\forall {loc}_{V}, {loc}_{P} such that d ({loc}_{V}, {loc}_{P}) ⩽ B)$ we have $\underset{r_{k}, r_{P}, r_{V}}{Pr} [{Out}_{V} = 1 : \begin{matrix} (x, y) \leftarrow Gen (1^{s}; r_{k}) \\ P (x; r_{P}) \leftrightarrow V (y; r_{V}) \end{matrix}] ⩾ p .$

Throughout, “ $\underset{r}{Pr} [event : experiment]$ ” denotes the probability that an event takes place after the experiment has happened, taken on the set of random coins r underlying the experiment. The random variable associated to the event is defined via the experiment. Hence, we are not referring here to two events conditioning one another, but just to an experiment leading to the description of a random variable.

DB concurrency

Our model implicitly assumes concurrency involving participants not sharing the secret inputs amongst them. In security definitions, these extra participants are implicitly universally quantified. When several provers using the same input x appear in experiments, they will be explicitly mentioned. I.e., several instances of the same participant at different location and/or time.

3.3. DB threats

The security requirements of DB protocols, i.e., the resistance to the different DB threats, are formalised in the definitions to follow. The parameters used therein, α, β, γ, $γ^{'}$ are real numbers in the interval $[0, 1]$ .

3.3.1. (Generalised) distance-fraud

Definition 3.2 (α-resistance to distance-fraud).

$(\forall s)$ $(\forall P^{*})$ $(\forall {loc}_{V} such that d ({loc}_{V}, {loc}_{P^{*}}) > B)$ $(\forall r_{k})$ , we have $\underset{r_{V}}{Pr} [{Out}_{V} = 1 : \begin{matrix} (x, y) \leftarrow G e n (1^{s}; r_{k}) \\ P^{*} (x) \leftrightarrow V (y; r_{V}) \end{matrix}] ⩽ α,$ where $P^{*}$ is any (unbounded) dishonest prover. In a concurrent setting, we implicitly allow a polynomially bounded number of honest $P (x^{'})$ and $V (y^{'})$ close to $V (y)$ with independent $(x^{'}, y^{'})$ .

Informal explanation of Definition 3.2. The above definition states, in our modelling, the notion of resisting to distance-fraud: i.e., a participant $P^{*}$ that is situated somewhere beyond the distance-bound should not succeed in making the verifier accept but with a very low probability hereby denoted by α.

Relation with other formalisms. In a 2-party setting, the above definition corresponds to the one of the ABKLM model [1]. When α is negligible, our security notion becomes equivalent to the one in the DFKO model [22].

Relation with distance hijacking [18]. Due to our concurrent setting, Definition 3.2 captures the notion of distance hijacking in [18], i.e., an experiment in which a dishonest far-away prover $P^{*}$ may use several provers to get authenticated as one, honest P that is close to the verifier.

3.3.2. (Generalised) mafia-fraud

Definition 3.3 (β-resistance to MiM).

$(\forall s) (\forall m, ℓ, z)$ polynomially bounded, $(\forall A_{1}, A_{2})$ polynomially bounded, for all locations such that $d ({loc}_{P_{j}}, {loc}_{V}) > B$ , where $j \in {m + 1, \dots, ℓ}$ , we have $Pr [{Out}_{V} = 1 : \begin{matrix} (x, y) \leftarrow G e n (1^{s}) \\ P_{1} (x), \dots, P_{m} (x) \leftrightarrow A_{1} \leftrightarrow V_{1} (y), \dots, V_{z} (y) \\ P_{m + 1} (x), \dots, P_{ℓ} (x) \leftrightarrow A_{2} ({View}_{A_{1}}) \leftrightarrow V (y) \end{matrix}] ⩽ β$ over all random coins, where ${View}_{A_{1}}$ is the final view of $A_{1}$ . In a concurrent setting, we implicitly allow a polynomially bounded number of $P (x^{'})$ , $P^{*} (x^{'})$ , and $V (y^{'})$ with independent $(x^{'}, y^{'})$ , anywhere.

Informal explanation of Definition 3.3. In man-in-the-middle (MiM) attacks or generalised mafia-frauds as above, we consider that during a learning phase, the attacker interacts, in parallel, with $m ⩾ 0$ provers and $z ⩾ 0$ verifiers. Then – in the attack phase – the adversary tries to win in an experiment in front of a verifier which is far-away from $ℓ - m ⩾ 0$ provers. (Using the notation $A_{1}$ for the learning phase and $A_{2}$ for the attack phase is just to show that the adversarial behaviours in these phases might be different. As the reader can notice, the attacker $A_{2}$ shares the view/knowledge of $A_{1}$ .)

By the learning phase, Definition 3.3 models practical threats. For instance, an attacker would have cloned several tags and would make them interact with several readers with which they are registered. From such a multi-party communication, the attacker can get potentially more benefits, in a shorter period of time. Of course, an attacker can in fact set up this learning phase as he pleases, to increase his gains. So, we can even imagine that he places prover-tags close to verifier-readers, even if being an active adversary between two neighbouring P and V is technically more challenging than interfering between two far-away parties. E.g., in this scenario, the adversary could interfere with the initial frequency synchronisation phase so that the $P \leftrightarrow A$ and $A \leftrightarrow V$ channels would become different (e.g., using different frequency bands) and P and V would not even be aware of the existence of the other channel.

In any case, note that the learning phase is not obligatory in our setting (m and z can be 0). Indeed, we further consider mafia-frauds as a specialisation of the above, where no learning phase is present. But, if and when a non-trivial learning phase is present, it renders a stronger threat model and proven resistance to such attacks entails better security.

Relations with mafia-fraud and other frauds

The classical notion of mafia-fraud (the one from the ABKLM model [1]) corresponds to $m = z = 0$ (i.e., no learning phase), and $ℓ = 1$ .

The classical notion of impersonation for identification schemes corresponds to $ℓ = m$ (i.e., there is no prover in the attack phase).

Relation with other formalisms

The DFKO model [22] of mafia-fraud already includes the above general extension since concurrent settings are implicit in the DFKO model.

Non-narrow attackers

We will now describe a special type of (MiM) attackers, following a notion introduced in [47]. Thereby, a (MiM) attacker is non-narrow if he can learn the bit that the verifier outputs. A way in which this can be trivially formalised is by adding a return channel to the communication, here denoting that the verifier V sends ${Out}_{V}$ as a final message, just before V halts. In real life this is the case, e.g., there is a LED on a door turning green denoting “access-granted” and turning red otherwise.

It is pertinent to formalise such an attacker: intruders learn obviously more information by looking also at whether the run was successful or not. Indeed, in the generalised MF presented in [4], it is this sort of return channel that facilitates the attacks. To avoid defining a new class of attacks (as done in the literature [47]), we define this as a property of the protocol.

Definition 3.4 (Non-narrow MiM).

A distance-bounding protocol is called non-narrow if it terminates by V sending ${Out}_{V}$ to P as his final message.

3.3.3. (Generalised) terrorist-fraud

Definition 3.5 ( $(γ, γ^{'})$ -resistance to collusion-fraud).

$(\forall s)$ $(\forall P^{*})$ $(\forall {loc}_{V_{0}} such that d ({loc}_{V_{0}}, {loc}_{P^{*}}) > B)$ $(\forall A^{CF} ppt)$ such that $Pr [{Out}_{V_{0}} = 1 : \begin{matrix} (x, y) \leftarrow Gen (1^{s}) \\ P^{*} (x) \leftrightarrow A^{CF} \leftrightarrow V_{0} (y) \end{matrix}] ⩾ γ$ over all random coins, there exists a (kind of)9

⁹
Definition 3.3 defines MiM attacks as using an honest $P (x)$ . Here, we deviate a bit by introducing $P^{*} (x)$ as well.

MiM attack

m, ℓ, z, A_{1}, A_{2}, P_{i}, P_{j}, V_{i^{'}}

using P and

P^{*}

in the learning phase, such that

Pr [{Out}_{V} = 1 : \begin{matrix} (x, y) \leftarrow Gen (1^{s}) \\ P_{1}^{(*)} (x), \dots, P_{m}^{(*)} (x) \leftrightarrow A_{1} \leftrightarrow V_{1} (y), \dots, V_{z} (y) \\ P_{m + 1} (x), \dots, P_{ℓ} (x) \leftrightarrow A_{2} ({View}_{A_{1}}) \leftrightarrow V (y) \end{matrix}] ⩾ γ^{'},

where

P^{*}

is any (unbounded) dishonest prover and

P^{(*)}

runs either P or

P^{*}

. Following the MiM requirements,

d ({loc}_{P_{j}}, {loc}_{V}) > B

, for all

j \in {m + 1, ℓ}

. In a concurrent setting, we implicitly allow a polynomially bounded number of

P (x^{'})

P^{*} (x^{'})

, and

V (y^{'})

with independent

(x^{'}, y^{'})

, but no honest participant close to

V_{0}

Informal explanation of Definition 3.5. Definition 3.5 expresses the following. Consider a prover $P^{*}$ , situated far-away from $V_{0}$ , who can help an adversary $A^{CF}$ located closer to $V_{0}$ pass a distance-bounding protocol. Then, a malicious adversary denoted as $(A_{1}, A_{2})$ could run a successful MiM attack,10

¹⁰

In practice, $A^{MiM}$ and $A^{CF}$ represent the same adversarial party; we simply differentiate to show that different algorithms/attack-strategies may be involved.

“playing” with possibly multiple instances of

P^{*} (x)

in the learning phase. In other words, a dishonest prover

P^{*}

cannot successfully collude with

A^{CF}

without leaking some private information.

Note that collusion frauds are non-falsifiable. However, this is inherent to terrorist frauds.

Relation with terrorist-fraud. Collusion-frauds are more general than terrorist-frauds. The classical notion of terrorist-fraud corresponds to a specialised case of Definition 3.5: the one where $m = z = ℓ = 1$ and $A_{1}$ runs just $A^{CF}$ in the learning phase. Put simply, in the classical terrorist-fraud, $A^{CF}$ gets information to directly impersonate the prover, whereas in Definition 3.5 we formalise the means to get this information via a learning phase.

Relation with other formalisms. In the ABKLM or DFKO models, only the specialised case of collusion frauds mentioned above, i.e., the traditional terrorist-fraud, is considered. In the DFKO model [22], the formalisation of terrorist-fraud further considers $p_{A} = Pr [{Out}_{V_{0}} = 1]$ , and $p_{S} = Pr [{Out}_{V} = 1 | {Out}_{V_{0}} = 1]$ . Following some results from [23], a protocol resists to terrorist-fraud if for every $A^{CF}$ there is a $A_{2}$ such that $p_{A} ⩽ p_{S}$ . However, we think that illustrating some $A^{CF}$ such that $p_{A}$ is negligible but for no $A_{2}$ we would have $p_{A} ⩽ p_{S}$ [23] is not a strong enough argument for insecurity. It rather shows that the definition from [22] is too strong. In our approach, we decided to characterise resistance herein through a pair of probabilities $(γ, γ^{'})$ .

Fig. 2.
The SKI schema of distance-bounding protocols.
4. Practical and secure distance-bounding protocols
4.1. SKI: Description and completeness

At a high level, the protocol schema SKI is presented in Fig. 2. We use the parameters $(s, q, n, k, t, t^{'})$ , where s is the security parameter. The SKI protocols are built using a PRF (pseudorandom function), denoted ${(f_{x})}_{x \in GF {(q)}^{s}}$ , with q being a small power of prime. In the concrete examples in the main body of the paper, we employ $q = 2$ , i.e., x, a are simply bitstrings as it is most practical. In the DB phase, n rounds are used, with $n \in Ω (s)$ . Then, SKI uses the value $f_{x} (N_{P}, N_{V}, L) \in GF {(q)}^{t^{'} n}$ , with nonces $N_{P}, N_{V} \in {0, 1}^{k}$ and a mask $M \in GF {(q)}^{t^{'} n}$ , where $k \in Ω (s)$ . In the main proposal, $t^{'} = 2$ is used, i.e., to keep the lightweight character. The element $a = (a_{1}, \dots, a_{n})$ with $a_{i} \in GF {(q)}^{t^{'}}$ is established by V in the initialisation phase, and it is sent encrypted as $M : = a + f_{x} (N_{P}, N_{V}, L)$ , with $M \in GF {(q)}^{t^{'} n}$ , where + denotes the $GF (q)$ -vector addition. Similarly, V selects a random linear transformation L from a set11

¹¹
The $L$ set will be later introduced as a leakage scheme; its purpose is to leak $L (x)$ in the case of a collusion-fraud/terrorist-fraud.

$L$ which is specified by the SKI protocol instance and the parties compute $x^{'} = L (x)$ . Further, $c = (c_{1}, \dots, c_{n})$ is the challenge-vector with $c_{i} \in {1, \dots, t}$ , $r_{i} : = F (c_{i}, a_{i}, x_{i}^{'})$ is the ith response to the ith challenge $c_{i}$ , with $i \in {1, \dots, n}$ , $r_{i} \in GF (q)$ and F as specified below.12
¹²
This will be called the F-scheme and it will incorporate requirements towards (generalised) DF-, TF- and MF-resistance.

In other concrete proposals, $t = 3$ , or $t = 2$ for the lighter version, are used. The protocol ends with a message ${Out}_{V}$ denoting the output of the verifier (i.e., the success/failure of the protocol), to capture the notion of MiM attackers on a non-narrow protocol.

SKI instances

We first depict ${SKI}_{pro}$ through Fig. 3.

Fig. 3.
The ${SKI}_{pro}$ distance-bounding protocol ( $q = 2$ , $t = 3$ , $t' = 2$ ).

In fact, in Boureanu et al. [10,11], several variants of SKI were proposed. We now concentrate on two variants of SKI:
${SKI}_{pro}$ with $q = 2$ , $t^{'} = 2$ , $t = 3$ , with the response-function $F (1, a_{i}, x_{i}^{'}) = {(a_{i})}_{1}, F (2, a_{i}, x_{i}^{'}) = {(a_{i})}_{2}, F (3, a_{i}, x_{i}^{'}) = x_{i}^{'} + {(a_{i})}_{1} + {(a_{i})}_{2},$ where ${(a_{i})}_{j}$ denotes the jth bit of $a_{i}$ , with the transforms $L_{μ}$ defined each from a vector $μ \in GF {(q)}^{s}$ by $L_{μ} (x) = (μ \cdot x, \dots, μ \cdot x)$ i.e., n repetitions of the same bit $μ \cdot x$ , the dot product of μ and x over $GF (2)$ .

${SKI}_{lite}$ with $q = 2$ , $t^{'} = 2$ , $t = 2$ , with the response-function $F (1, a_{i}, x_{i}^{'}) = {(a_{i})}_{1}, F (2, a_{i}, x_{i}^{'}) = {(a_{i})}_{2},$ with the transform-set $L = {\emptyset}$ .
Namely, note that ${SKI}_{lite}$ never uses the $c_{i} = 3$ challenge, i.e., it never uses the part $x^{'}$ having to do directly with the secret key x in the DB responses. Each ${SKI}_{pro}$ session uses a transform $L_{μ}$ on x such that on $x^{'}$ all coordinates are set to the scalar product between μ and x. Since ${SKI}_{lite}$ never uses $x^{'}$ , $L$ can be left empty.

We note that both instances are efficient. Indeed, we could precompute the table of $F (\cdot, a_{i}, x_{i}^{'})$ and just do a table lookup to compute $r_{i}$ from $c_{i}$ . For ${SKI}_{pro}$ , this can be done with a circuit of only 7 NAND gates and depth 4. For ${SKI}_{lite}$ , 3 NAND gates and a depth of 2 are enough. The heavy computation lies in the $f_{x}$ evaluation which occurs in a phase which is not time-critical. In practice, any reasonable PRF suffices as it can satisfy the circular-keying condition to be stated below.

However, in our design, we need the reuse of x for protection against terrorist-fraud and/or collusion-fraud. Along these lines, the ${SKI}_{lite}$ protocols do not assume circular-keying security (as defined below), but the ${SKI}_{pro}$ do.

In Appendix B, we consider other variants of SKI with different F-schemes (using, e.g., two-bit responses) which we still deem very practical.

SKI completeness (in noisy communications)

We would like to investigate the suitability of the selected parameters. More precisely, we verify for which parameters, SKI is in line with Definition 3.1, i.e., it definitely terminates, but the completeness bound can be “tuned”.

Each $(c_{i}, r_{i})$ exchange is time-critical, so it is subject to errors. To address this, we introduce the probability $p_{noise}$ of one response being erroneous (à la Hancke–Kuhn [29]). Then, the SKI protocol specifies that the verifier accepts only if the number of correct answers is at least τ, where τ is an extra parameter. The probability that at least τ responses out of n are correct is clearly given by: $B (n, τ, 1 - p_{noise}) = \sum_{i = τ}^{n} (\begin{matrix} n \\ i \end{matrix}) {(1 - p_{noise})}^{i} p_{noise}^{n - i} .$

It is natural to choose τ (and other parameters) such that we operate with correct DB protocols, cf. with Definition 3.1. I.e., the protocol is complete: honest communications succeed with high probability.
Lemma 4.1.
Let $ε > 0$ . For $τ ⩽ (1 - p_{noise} - ε) n$ , the SKI protocols are $(1 - e^{- 2 ε^{2} n})$ -complete.
Proof.
Due to the Chernoff–Hoeffding bound [16,31], $τ ⩽ (1 - p_{noise} - ε) n$ implies $B (n, τ, 1 - p_{noise}) ⩾ 1 - e^{- 2 ε^{2} n}$ . According to Definition 3.1, this makes the SKI protocols $(1 - e^{- 2 ε^{2} n})$ -complete. □

In practice, we may use a constant $p_{noise}$ (i.e., hard-coded in the protocol implementation). This also entails employing τ as some parameter which is linear in terms of n. A detailed analysis of the optimal selection of this threshold τ is provided in [20].
4.2. SKI: Security-driven design and security assessment
In this subsection, we discuss the design choices that we made in order to render the instances of SKI provably secure.

PRF masking

Importantly, SKI applies a random mask M on the output of $f_{x}$ to fix the problems raised in Boureanu et al. [7]. We call this PRF masking.

We introduce PRF masking to protect against the class of attacks in [7]. I.e., Without PRF masking, M is not used (or equivalently, M is always set to 0). Then we could construct [7] a PRF such that, e.g., for all x and $N_{V}$ , the value of $f_{x} (x, N_{V}, L)$ is such that $F (c_{i}, a_{i}, x_{i}^{'})$ does not depend on $c_{i}$ . In this way, a malicious prover could set, e.g., $N_{P} = x$ and predict the answer $F (c_{i}, a_{i}, x_{i}^{'})$ without having received the challenge $c_{i}$ . Hence, he could mount a successful distance-fraud. By having the verifier decide a (thus, by masking the value of the PRF-instance $f_{x} (x, N_{V}, L)$ ), SKI enforces that the distribution of a cannot be influenced by a malicious prover.

F-scheme

In our way to prove security, we need some notions related to the response-function F; these characterise the concept of F-scheme. At the same time, these concepts give the sufficient conditions to protect against all three frauds possible against the concrete SKI instances to follow. Such a characterisation is different from the approach in Avoine et al. [2], where a response-function based on secret sharing is proposed for the protection against terrorist-fraud only, but no formal justification was given to that end; also, the relation between the other frauds and the response-function was not addressed therein. Thus, we stress that using a secret sharing scheme in computing the responses may be too strong and/or insufficient to characterise the protection against frauds mounted onto DB protocols, and we amend this with Definitions 4.1 and 4.3.

Definition 4.1 (F-scheme).

Let $t, t^{'} ⩾ 2$ . The response-function $F : {1, \dots, t} \times GF {(q)}^{t^{'}} \times GF (q) \to GF (q)$ gives an F-scheme, which is characterised as follows.
We say that the F-scheme is linear if for all challenges $c_{i}$ in their domain, the $F (c_{i}, \cdot, \cdot)$ function is a linear form over the $GF (q)$ -vector space $GF {(q)}^{t^{'}} \times GF (q)$ which is non-degenerate in the $a_{i}$ component.

We say the F-scheme is pairwise uniform if $(\forall I ⊊ {1, \dots, t}, # I ⩽ 2) (H (x_{i}^{'} | F {(c_{i}, a_{i}, x_{i}^{'})}_{c_{i} \in I}) = H (x_{i}^{'})),$ where $(a_{i}, x_{i}^{'}) \in_{U} GF {(q)}^{t^{'}} \times GF (q)$ , $# S$ denotes the cardinality of a set S, and H denotes the Shannon entropy.

We say the F-scheme is t-leaking if there exists a polynomial time algorithm E such that for all $(a_{i}, x_{i}^{'}) \in GF {(q)}^{t^{'}} \times GF (q)$ , we have $E (F (1, a_{i}, x_{i}^{'}), \dots, F (t, a_{i}, x_{i}^{'})) = x_{i}^{'}$ .

Let $F_{a_{i}, x_{i}^{'}}$ denote $F (\cdot, a_{i}, x_{i}^{'})$ . We say that the F-scheme is σ-bounded if for any $x_{i}^{'} \in GF (q)$ , we have $E_{a_{i}} (max_{y} (# (F_{a_{i}, x_{i}^{'}}^{- 1} (y)))) ⩽ σ$ , where $x^{'} \in GF (q)$ and the expected-value is $E$ taken over $a_{i} \in GF {(q)}^{t^{'}}$ .

Informal explanation of Definition 4.1. The pairwise uniformity and the t-leaking property of the F-scheme say that knowing the complete table of the response-function F for a given $c_{i}$ leaks $x_{i}^{'}$ , yet knowing only up to 2 entries challenge-response in this table discloses no information about $x_{i}^{'}$ .

The σ-boundedness of the schemes says that the expected value (taken on the choice of the subsecrets $a_{i}$ ) of the largest preimage of the map $c_{i} \mapsto F (c_{i}, a_{i}, x_{i}^{'})$ is bounded by a constant σ. In simple words, it says that it should be hard to invert the response function.

We have $\frac{t}{q} ⩽ σ ⩽ t$ due to the pigeonhole principle, since $\sum_{y} # (F_{a_{i}, x_{i}^{'}}^{- 1} (y)) = t$ . Furthermore, $σ ⩾ 1$ .

In relation with the definitions of the F-schemes above, we now prove the following lemma.

Lemma 4.2.
The F-scheme used in ${SKI}_{pro}$ is linear, pairwise uniform, $\frac{9}{4}$ -bounded, and t-leaking. The F-scheme used in ${SKI}_{lite}$ is linear, pairwise uniform, $\frac{3}{2}$ -bounded, but not t-leaking.

This lemma extends to Lemma B.1 given and proven in Appendix B.

Leakage scheme

We can consider several sets $L$ of transformations to be used in the PRF-instance, of the SKI initialisation phase. The idea of the set $L$ is that, when leaking some noisy versions of $L (x)$ for some random $L \in L$ , the adversary can reconstruct x without noise.

More formally, we introduce the following notion.
Definition 4.2 (Leakage scheme).

Let $L$ be a set of linear functions from $GF {(q)}^{s}$ to $GF {(q)}^{n}$ . Given $x \in GF {(q)}^{s}$ and a ppt algorithm $e (x, L; r_{e})$ , we define an oracle $O_{L, x, e}$ producing a random pair $(L, e (x, L))$ with $L \in_{U} L$ . We say that $L$ is a $(T, u, p)$ -leakage scheme if there exists an oracle ppt algorithm $A^{⟨ \cdot ⟩}$ limited to u queries, such that for all $x \in GF {(q)}^{s}$ , for all ppt e, $Pr [A^{O_{L, x, e}} = x | E] ⩾ p$ , where E is the event that all queries return a value such that $d_{H} (e (x, L), L (x)) < T$ , where $d_{H}$ denotes the Hamming distance.

Informal explanation of Definition 4.2. Intuitively, this means that based on r values of L and a noisy $L (x)$ , we can decode and return x.

We define $L_{classic} = {L}$ , with only one transformation: the identity function L, i.e., $L (x) = x$ . Unfortunately, this is not sufficient to add protection against collusion fraud due to Hancke [28]: given a constant θ, a malicious prover could select a vector e of Hamming weight $n - τ + θ$ and provide the full table of all $c_{i} \mapsto F (c_{i}, a_{i}, x_{i})$ functions, only that some entries in the table had been changed. Namely, for each $i \in {1, \dots, n}$ with $e_{i} = 1$ , the dishonest prover flips $F (c_{i}, a_{i}, x_{i})$ in this leaked table. Then, we would have $γ = {(1 - \frac{1}{t})}^{θ}$ , but this helped attacker can only reconstruct $x + e$ . Using multiple coerced provers $P^{*}$ will not reveal anything more, if the function $g (x)$ giving e is deterministic (i.e., then, several runs would have no randomised, adaptive choices of $g (x)$ , coming from $P^{*}$ ’s). Depending on such functions g, and since $n - τ$ is linear, recovering x takes exponential time. So, the value of $x + g (x)$ is not enough to run a MiM attack since we need x to evaluate $f_{x}$ .

We consider the leakage scheme $L_{bit}$ of ${SKI}_{pro}$ , consisting of all $L_{μ}$ transforms, where $L_{μ}$ is defined from a vector $μ \in GF {(q)}^{s}$ by $L_{μ} (x) = (μ \cdot x, \dots, μ \cdot x) .$

The following lemma is trivial.

Lemma 4.3.
$L_{classic}$ is a $(1, 1, 1)$ -leakage scheme.
Lemma 4.4.
For all constant $u > s$ , $L_{bit}$ is a $(\frac{n}{2}, u, 1 - q^{s - u})$ -leakage scheme.
Proof.
$A$ calls the oracle u times, then – by computing the majority – $A$ deduces $μ \cdot x$ whenever the Hamming distance to $L_{μ} (x)$ of the returned vector is lower than $\frac{n}{2}$ , for each of the obtained μ. After collecting u samples μ, they span the entire $GF (q^{s})$ vector space except with probability bounded by $q^{s - u}$ . Then, we deduce x by solving a linear system. □

Circular-keying security

On our way to prove the security of the SKI protocols, we need and hereby introduce the notion of security against circular-keying. This notion of security will help protect against MiM, in the context in which the key x is used in the response-function to protect against TF. To attain provable security against MiM attackers, we take secure circular-keying as an extra assumption to the PRF ${(f_{x})}_{x \in GF {(q)}^{s}}$ to handle the reuse of a fixed x outside of a PRF instance $f_{x}$ . Definition 4.3 (Circular-keying).

Let s be some security parameter, let b be a bit, let $q ⩾ 2$ , let $m \in Poly (s)$ , and let $x, \bar{x} \in GF {(q)}^{s}$ be two row-vectors. Let ${(f_{x})}_{x \in GF {(q)}^{s}}$ be a family of (keyed) functions, e.g., $f_{x} : {0, 1}^{*} \to GF {(q)}^{m}$ . For an input y, the output $f_{x} (y)$ can be represented as a row-vector in $GF {(q)}^{m}$ .

We define an oracle $O_{f_{x}, \bar{x}}$ such that upon a query of form $(y_{i}, A_{i}, B_{i})$ , with $A_{i} \in GF {(q)}^{s}$ , $B_{i} \in GF {(q)}^{m}$ , it answers $(A_{i} \cdot \bar{x}) + (B_{i} \cdot f_{x} (y_{i}))$ . The game ${Circ}_{f_{x}, \bar{x}}$ of circular-keying with an adversary $A$ is described as follows: we set $b_{f_{x}, \bar{x}} : = A^{O_{f_{x}, \bar{x}}}$ , where the queries $(y_{i}, A_{i}, B_{i})$ from $A$ must follow the restriction that $(\forall c_{1}, \dots, c_{k} \in GF (q)) (# {y_{i}; c_{i} \neq 0} = 1, \sum_{j = 1}^{k} c_{j} B_{j} = 0 ⟹ \sum_{j = 1}^{k} c_{j} A_{j} = 0) .$ We say that the family of functions ${(f_{x})}_{x \in GF {(q)}^{s}}$ is an $(ε, C, Q)$ -circular-PRF if for any ppt adversary $A$ making Q queries and having complexity C, it is the case that $Pr [b_{f_{x}, x} = b_{f^{*}, \bar{x}}] ⩽ \frac{1}{2} + ε$ , where the probability is taken over the random coins of $A$ and over the random selection of $x, \bar{x} \in GF {(q)}^{s}$ and the random function $f^{*}$ .
The condition on the queries means that for any set of queries with the same value $y_{i}$ , any linear combination making $B_{j}$ vanish makes $A_{j}$ vanish at the same time. (Otherwise, we would trivially extract some information about $\bar{x}$ by linear combinations.)

We note that it is possible to create secure circular-keying in the random oracle model (ROM) [5]. This is a “sanity check” for our circular-keying notion. Indeed, any “reasonable” PRF should satisfy this constraint. Only special constructions would not. E.g., the ones based on PRF programming from [7].

Lemma 4.5.
Let $f_{x} (y) = H (x, y)$ , where H is a random oracle, $x \in {0, 1}^{s}$ , and $y \in {0, 1}^{*}$ . Then, f is a $(T 2^{- s}, T, Q)$ -circular PRF for any T and Q.
Proof.
Let $(y, A_{i}, B_{i})$ , $i \in 1, \dots, k$ , be some queries to $O_{f_{x}, \bar{x}}$ that share the same y, made by some $A$ , making no query to H. We define the matrices $A = {(A_{1} \dots A_{k})}^{T}$ and $B = {(B_{1} \dots B_{k})}^{T}$ . Thus, $A$ learns $A \bar{x} + B H (x, y)$ . Now, w.l.o.g., assume that $A$ multiplies $A \bar{x} + B H (x, y)$ to the left by a conveniently chosen, invertible matrix P, i.e., such that $P B = {(I_{p} 0)}^{T}$ where $I_{p}$ is the identity matrix of rank p of B and 0 is a zero matrix block.

By taking $c = c^{'} P$ with $c^{'} = (0, \dots, 0, 1, 0 \dots, 0)$ , where 1 appears at some position j for any $j > p$ , we have that $c B = 0$ . Then, by circular keying, we have that $c A = 0$ . Thus, all rows from positions beyond p, i.e., $p + 1, p + 2, \dots$ “downwards” inside the matrix $PA$ , are filled with zeroes. Thus, $A$ learns $A^{'} \bar{x} + H (x, y)$ , where $A^{'}$ is the “upper-part” of PA, i.e., above the pth row. We have shown that $A$ is equivalent to an adversary learning $A^{'} \bar{x} + H (x, y)$ for some random matrix $A^{'}$ . So, we can replace $H (x, y)$ by something random and the advantage of the adversary $A$ in this game would not change.

Now, in the random oracle model, $A$ also queries H. We consider the hybrids of $A$ in which the first queries to H are simulated and the hybrid stops before making the next query to H (there are up to T hybrids). We apply the previous argument to the hybrids to show that they cannot query H with x, except by guessing it with probability $2^{- s}$ . □

We proceed with inspecting the rest of the security requirements on these protocols.
Theorem 4.1.
The SKI protocols are secure distance-bounding protocols, i.e.:
A. If the F-scheme is linear and σ-bounded, if ${(f_{x})}_{x \in GF {(q)}^{n}}$ is a $(ε, n N, C)$ -circular PRF, then the SKI protocols offer α-resistance to distance-fraud, with $α = B (n, τ, \frac{σ}{t}) + ε$ , for attacks limited to complexity C and N participants. So, we need $\frac{τ}{n} > \frac{σ}{t}$ for security.

B. If the F-scheme is linear and pairwise uniform, if ${(f_{x})}_{x \in GF {(q)}^{n}}$ is a $(ε, n (ℓ + z + 1), C)$ -circular PRF, if $L$ is a set of linear mappings, the SKI protocols are β-resilient against (non-narrow) MiM attackers with parameters ℓ and z and a complexity bounded by C, $β = B (n, τ, \frac{1}{t} + \frac{t - 1}{t} \times \frac{1}{q}) + 2^{- k} (\frac{ℓ (ℓ - 1)}{2} + \frac{z (z + 1)}{2}) + ε$ . So, we need $\frac{τ}{n} > \frac{1}{t} + \frac{t - 1}{t} \times \frac{1}{q}$ for security.

B $^{^{'}}$ . If the F-scheme is linear and pairwise uniform, if ${(f_{x})}_{x \in GF {(q)}^{n}}$ is a $(ε, n (ℓ + z + 1), C)$ -PRF, if the function $F (c_{i}, a_{i}, \cdot)$ is constant for each $c_{i}, a_{i}$ , the SKI protocols are β-resilient against (non-narrow) MiM attackers with parameters ℓ and z and a complexity bounded by C, $β = B (n, τ, \frac{1}{t} + \frac{t - 1}{t} \times \frac{1}{q}) + 2^{- k} (\frac{ℓ (ℓ - 1)}{2} + \frac{z (z + 1)}{2}) + ε$ . So, we need $\frac{τ}{n} > \frac{1}{t} + \frac{t - 1}{t} \times \frac{1}{q}$ for security.

C. If the F-scheme is t-leaking, if $L$ is a $(T, u, p)$ -leakage scheme, for all $θ \in] 0, 1 [$ , the SKI protocols offer $(γ, γ^{'})$ -resistance to collusion-fraud, for $γ ⩾ B {(T, T + τ - n, \frac{t - 1}{t})}^{1 - θ}$ , $γ^{- 1}$ is polynomially bounded, and $γ^{'} = {(1 - B {(T, T + τ - n, \frac{t - 1}{t})}^{θ})}^{u} p$ . So, we need $\frac{τ}{n} > 1 - \frac{T}{t n}$ for security.

The proof of Theorem 4.1.B′ is similar (and simplified) as the one of Theorem 4.1.B. So, we prove the A, B and C parts only.

In the noiseless case (i.e., with $p_{noise} = 0$ ), we can work with $τ = n$ . Interestingly, we can then use $L = L_{classic}$ and still have resistance to collusion fraud, with $γ ⩾ {(\frac{t - 1}{t})}^{1 - θ}$ and $γ^{'} = 1 - {(\frac{t - 1}{t})}^{θ}$ .
Proof of Theorem 4.1.A.
For each key $x^{'}$ which is different from x and for which there is a $P (x^{'})$ close to V (so, there is no $P^{*} (x^{'})$ anywhere, due to the distance-fraud model), we apply the circular-PRF reduction. (Details as for why we can apply this reduction will appear in the proof of Theorem 4.1.B.) We are losing a probability up to ε in this reduction.

We recall that if the F-scheme is linear, then $F (c_{i}, a_{i}, x_{i}^{'})$ must be non-degenerate in $a_{i}$ . So, answers $r_{i}$ coming from $P (x^{'})$ instead of $P^{*} (x)$ are correct with probability $\frac{1}{t}$ , since $a_{i}$ is random, after the circular-PRF reduction.

If $r_{i}$ now comes from $P^{*}$ , due to Lemma 3.1, $r_{i}$ must be a function independent from $c_{i}$ . I.e., $P^{*}$ must have $F (c_{i}, a_{i}, x_{i}^{'})$ ready, before $c_{i}$ arrives from V. So, for any secret x and a, the probability to get one response right is given by $p_{i} = \underset{c_{i} \in {1, \dots, t}}{Pr} [r_{i} = F (c_{i}, a_{i}, x_{i}^{'})]$ .

Thanks to PRF masking, the distribution of the $a_{i}$ ’s is uniform. Namely, $P^{*}$ cannot influence their distribution by selecting $N_{P}$ maliciously.

To establish the probabilities $p_{i}$ , consider the partitions $I_{j}$ , $j \in {1, \dots, t}$ as follows: for $i \in I_{j}$ , the largest preimage of $F_{a_{i}, x_{i}^{'}} : c_{i} \mapsto F (c_{i}, a_{i}, x_{i}^{'})$ has size j, i.e., $max_{y} (# (F_{a_{i}, x_{i}^{'}}^{- 1} (y)) = j$ . Then, we are looking at the probability $P_{j} (x_{i}^{'}) : = \underset{a_{i}}{Pr} [max_{y} (# (F_{a_{i}, x_{i}^{'}}^{- 1} (y))) = j],$ where $# (S)$ denotes the cardinality of a set S. Given $x^{'}$ fixed, each iteration has a probability to succeed equal to $\frac{P_{1}}{t} + \frac{2 P_{2}}{t} + \dots + \frac{t P_{t}}{t} = \frac{σ}{t} .$ So, the probability to win the experiment is bounded by $p = B (n, τ, \frac{σ}{t})$ . □

Tightness

The above result is tight as the following attack shows. It is thus the best distance fraud. We consider a malicious (far-away) prover who follows normally the initialisation phase. For the distance bounding phase, he anticipates the challenge $c_{i}$ and sends the response $r_{i}$ in advance so that it arrives on time. The response is chosen such that $# F_{a_{i}, x_{i}^{'}}^{- 1} (r_{i})$ is maximal. So, the probability that the verifier accepts is $B (n, τ, \frac{σ}{t})$ , which is negligibly close to α.
Proof of Theorem 4.1.B.
In the next, $P (\dots)$ and $V (\dots)$ respectively denote the algorithm/(part of the) protocol of a generic prover P and that of a generic verifier V, out of the ℓ provers and $z + 1$ verifiers in this attack-game, run on specific parameters to be specified in-line. We herein denote V in the MiM-resistance definition as $V_{z + 1}$ .

We use the game-reduction methodology [42] to prove this lemma. Let ${Game}_{0}$ be the non-narrow MiM attack-game described in Definition 3.3 played by $A$ against the honest parties in a SKI protocol.

Below we consider a prover $P_{j}$ and a verifier $V_{k}$ in an experiment, $j \in {1, \dots, ℓ}$ , $k \in {1, \dots, z + 1}$ . Let $(N_{P, j}, {\bar{M}}_{j}, {\bar{L}}_{j}, {\bar{N}}_{V, j})$ be the values of the nonces $(N_{P}, N_{V})$ , of the mask M, and of the transformation L that the prover $P_{j}$ generates or sees respectively, and $({\bar{N}}_{P, k}, M_{k}, L_{k}, N_{V, k})$ be the values of the nonces $(N_{P}, N_{V})$ , mask M, and transformation L that a verifier $V_{k}$ generates or sees at his turn, $j \in {1, \dots, ℓ}$ , $k \in {1, \dots, z + 1}$ .

We apply a reduction by failure-event to prove that the game ${Game}_{0}$ is indistinguishable to the adversary $A$ from a game ${Game}_{1}$ where no repetitions on $N_{P, j}$ or on $N_{V, k}$ happen for $j \in {1, \dots, ℓ}$ , $k \in {1, \dots, z + 1}$ , i.e., there is no collision on the nonces generated by the provers and there is no collision on the nonces of the verifiers.

Assume that F is the event that at least a collision as above happens, i.e., $F \equiv (\underset{0 < i < j ⩽ ℓ}{⋁} (N_{P, i} = N_{P, j})) \lor (\underset{0 < i^{'} < j^{'} ⩽ z + 1}{⋁} (N_{V, i^{'}} = N_{V, j^{'}})) .$ We want to have that, from the point of view of the adversary $A$ , ${Game}_{0} \land \neg F \Leftrightarrow {Game}_{1} \land \neg F \Leftrightarrow {Game}_{1}$ . But, $∥ Pr [A wins in {Game}_{0}] - Pr [A wins in {Game}_{1}] ∥ ⩽ Pr [F] .$ Then, $Pr [F] ⩽ 2^{- k} (\frac{ℓ (ℓ - 1)}{2} + \frac{z (z + 1)}{2})$ .

Since the F-scheme is linear, we can write $F (c_{i}, a_{i}, x_{i}^{'}) = u_{i} (c_{i}) x_{i}^{'} + (v_{i} (c_{i}) \cdot a_{i})$ where $u_{i} (c_{i}) \in GF (q), v_{i} (c_{i}) \in GF {(q)}^{t^{'}}$ . Note that, in terms of i, the $(v_{i} (1), \dots, v_{i} (t))$ ’s span independent linear spaces. In ${Game}_{1}$ , each $(N_{P}, N_{V}, L, i)$ tuple can be invoked only twice (with a prover and a verifier) by the adversary. The pairwise uniformity of the F-scheme implies that $y v_{i} (c_{i}) + y^{'} v_{i} (c_{i}^{'}) = 0$ implies $y u_{i} (c_{i}) + y^{'} u_{i} (c_{i}^{'}) = 0$ for all $c_{i}, c_{i}^{'} \in {1, \dots, t}$ and all $y, y^{'} \in GF (q)$ . So, we deduce that the condition to apply the circular-keying reduction is fulfilled. We can thus apply the circular-PRF reduction and reduce to ${Game}_{2}$ , where $F (c_{i}, f_{x} {(N_{P}, N_{V}, L)}_{i}, x_{i}^{'})$ is replaced by $u_{i} (c_{i}) {\tilde{x}}_{i} + (v_{i} (c_{i}) \cdot f^{*} {(N_{P}, N_{V}, L)}_{i})$ , where $f^{*}$ is a random function. This reduction has a probability loss of up to ε.

From here, we use a simple bridging step to say that the adversary $A$ has virtually no advantage over ${Game}_{2}$ and a game ${Game}_{3}$ , where the vector $a = f^{*} (N_{P}, N_{V}, L)$ is selected at random; we recall that this is the case since there is no repetition on $N_{P}$ and $f^{*}$ is a random function. The $(N_{P}, N_{V}, L)$ triplet used by V in the attack phase can be used by only one $P_{j}$ , in the attack phase as well, where $j \in {m + 1, \dots, ℓ}$ . We can simulate all other P’s and V’s based on a (simulated) random a. This reduces to an adversary making no use of the learning phase and using only $P_{j}$ and V in the attack phase.

So, the probability p of $A$ of succeeding in ${Game}_{3}$ is the probability that at least τ rounds have a correct $r_{i}$ . Due to Lemma 3.1, $r_{i}$ must be computed by $A$ (and not $P_{j}$ ). Getting $r_{i}$ correct for $c_{i}$ can thus be attained in two distinct ways: (1) in the event $e 1$ of guessing $c_{i}^{'} = c_{i}$ and sending it beforehand to $P_{j}$ and getting the correct response $r_{i}$ , or (2) in the event $e 2$ of simply guessing the correct answer $r_{i}$ (for a challenge $c_{i}^{'} \neq c_{i}$ ). So, $p = B (n, τ, Pr [e 1] + Pr [e 2]) = B (n, τ, \frac{1}{t} + \frac{t - 1}{t} \times \frac{1}{q})$ . □

Tightness

The above result is tight as the following attack shows. It is thus the best MiM attack. We consider an adversary who first relays the messages between the (far away) prover and the verifier during the initialisation phase. Then, he simulates a distance bounding phase with the prover to learn some $c_{i} \mapsto r_{i}$ relations. During the distance bounding phase with the verifier, either the challenge matches the learnt $c_{i}$ , in which case he can answer $r_{i}$ and pass with probability 1, or the challenge is different, in which case he can answer randomly and pass with probability $\frac{1}{q}$ . The overall probability to pass one round is $\frac{1}{t} + (1 - \frac{1}{t}) \frac{1}{q}$ . So, the probability that the verifier accepts is $B (n, τ, \frac{1}{t} + (1 - \frac{1}{t}) \frac{1}{q})$ , which is negligibly close to β.
Proof of Theorem 4.1.C.
Assume as per the requirement for resistance to collusion-fraud that there is an experiment $\exp^{CF} = (P^{*} (x) ⟷ A^{CF} (r_{CF}) ⟷ V_{0} (y; r_{V_{0}}))$ , with $P^{*}$ a coerced prover who is far away from $V_{0}$ and that $\underset{r_{V_{0}}, r_{CF}}{Pr} [{Out}_{V_{0}} = 1] = γ$ . Given some random $c_{1}, \dots, c_{n}$ from the verifier, we define the random variable ${View}_{i}$ as being the view of $A^{CF}$ before receiving $c_{i}$ from V, and the random variable $w_{i}$ being all the information that $A^{CF}$ has received from $P^{*}$ before the time when sending out $r_{i}$ would become critical (i.e., before it would be too late to send $r_{i}$ on to $V_{0}$ ). This answer $r_{i}$ done by $A^{CF}$ is formalised in Lemma 3.1. So, $r_{i} : = A^{CF} ({View}_{i} ∥ c_{i} ∥ w_{i})$ .

Let $C_{i}$ be the set of all possible $c_{i}$ ’s on which the functions $A^{CF} ({View}_{i} ∥ \cdot ∥ w_{i})$ and $F (\cdot, a_{i}, x_{i}^{'})$ match (i.e., $A^{CF}$ answers correctly to the challenge $c_{i}$ at round i). Let S be the set of i’s such that $c_{i} \in C_{i}$ (i.e., $A^{CF}$ answers correctly at round i). Finally, let R be the set of i’s such that $# C_{i} = t$ (i.e., $A^{CF}$ answers correctly at round i whatever the challenge). I.e., $C_{i} = {c \in {1, \dots, t} ∣ A^{CF} ({View}_{i} ∥ c ∥ w_{i}) = F (c, a_{i}, x_{i}^{'})}$ , $S = {i \in {1, \dots, n} ∣ c_{i} \in C_{i}}$ , and $R = {i \in {1, \dots, n} ∣ # C_{i} = t}$ . The adversary $A$ succeeds in $\exp^{CF}$ if $# S ⩾ τ$ , i.e., if he can pass at least τ rounds, for the challenges that $V_{0}$ will fix in those rounds.

For terrorist-fraud resistance, we would also like that – in the second, MiM experiment – the adversary $A_{2}$ can answer τ rounds (or more), no matter what the challenge, i.e., in this way, $A$ could extract x and the TF would be invalid. In other words, we would like that $# R$ is large, i.e. $# R > n - T$ so that we can decode.

So, if we were to pick a set of challenges such that $# S ⩾ τ$ and $# R ⩽ n - T$ , we should select a good challenge (from no more than $t - 1$ existing out of t), for at least $T + τ - n$ rounds out of T. In other words, $Pr [# S ⩾ τ, # R ⩽ n - T] ⩽ B (T, T + τ - n, \frac{t - 1}{t})$ . But, by the hypothesis, $Pr [# S ⩾ τ] ⩾ γ$ . So, we deduce immediately that $Pr [# R ⩽ n - T | # S ⩾ τ] ⩽ γ^{- 1} B (T, T + τ - n, \frac{t - 1}{t})$ . Therefore, $Pr [# R > n - T | # S ⩾ τ] ⩾ 1 - γ^{- 1} B (T, T + τ - n, \frac{t - 1}{t})$ .

We use $m = ℓ = z = O (γ^{- 1} r)$ (i.e., $A_{2}$ will directly impersonate P to V after $A_{1}$ ran m times the collusion fraud, with $P^{*}$ and V). We define $A_{2}$ such that, for each execution of the collusion fraud with $P^{*}$ and V, it gets ${View}_{i}$ , $w_{i}$ . For each i, $A_{2}$ computes the table $c \mapsto A^{CF} ({View}_{i} ∥ c ∥ w_{i})$ and apply the t-leaking function E of the F-scheme on this table to obtain $y_{i} = E (c \mapsto A^{CF} ({View}_{i} ∥ c ∥ w_{i}))$ . For each $i \in R$ , the table matches the one of $c \mapsto F (c, a_{i}, x_{i}^{'})$ with $x^{'} = L (x)$ , and we have $y_{i} = x_{i}^{'}$ . So, $A_{2}$ computes a vector y. If V accepts the proof, then y coincides with $L (x)$ on at least $n - T + 1$ positions, with a probability of at least $ρ : = 1 - γ^{- 1} B (T, T + τ - n, \frac{t - 1}{t})$ . That is, after $O (γ^{- 1})$ runs, $A_{2}$ implements an oracle which produces a random $L \in L$ and a y which has a Hamming distance to $L (x)$ up to $T - 1$ .

By applying the leakage scheme decoder e on this oracle, with u samples, it can fully recover x, with probability at least $ρ^{u} p$ : just obtain a list of possible values for x and isolate the good one based on the collected information. Then, by taking $γ = B {(T, T + τ - n, \frac{t - 1}{t})}^{1 - θ}$ and $γ^{'} = {(1 - B {(T, T + τ - n, \frac{t - 1}{t})}^{θ})}^{u} p$ , we obtain our result. □

Tightness

For our ${SKI}_{pro}$ construction using $T = \frac{n}{2}$ , the above result is tight as the following attack shows. It is thus the best collusion fraud. We assume there is a function g mapping the secret x and the leak function $L_{μ}$ to a vector $e = g (x, L_{μ})$ with Hamming weight $\frac{n}{2}$ . We consider a malicious prover who selects some challenges $c_{i}^{*}$ at random. He runs the initialisation phase normally. Then, he sends to the adversary a table $c_{i} \mapsto r_{i}$ for each round i. For i such that $e_{i} = 0$ , he gives the full table $c_{i} \mapsto F (c_{i}, a_{i}, x_{i}^{'})$ . For i such that $e_{1} = 1$ , he gives the table, except for $c_{i} = c_{i}^{*}$ , for which the correct response is flipped. The adversary uses the table to answer to each round. Due to the leakage property, the adversary learns $L_{μ} (x) + e$ which is a vector with Hamming weight $\frac{n}{2}$ , which leaks no information about $L_{μ} (x)$ . We can show more formally that this does not leak any usable information about x.

During the collusion fraud, the adversary passes each round such that $e_{i} = 0$ . When $e_{i} = 1$ , the probability to pass is $1 - \frac{1}{t}$ , i.e. the probability that the challenge is not $c_{i}^{*}$ . So, the overall probability to pass the protocol is $γ = B (\frac{n}{2}, τ - \frac{n}{2}, 1 - \frac{1}{t})$ , without leaking any usable information. Our result indicates that this is the largest γ we can achieve.

Thus, under the circumstances where protection against terrorist-fraud and/or collusion-fraud13
¹³
It is clear that these ${SKI}_{lite}$ protocols do not protect against terrorist-fraud (given the F-scheme used inside them).

is not of primary importance, one can use the proposed ${SKI}_{lite}$ protocols, the security of which does not rely on the assumption of circular-keying security.

Following Lemma 4.2 and Theorem 4.1, it is clear that the probabilities α and β to succeed respectively in a distance-fraud and MiM, against the SKI protocols are based on:

${SKI}_{pro}$ ${SKI}_{lite}$

α: $B (n, τ, \frac{3}{4})$ $B (n, τ, \frac{3}{4})$

β: $B (n, τ, \frac{2}{3})$ $B (n, τ, \frac{3}{4})$

SKI’s parameters

Let $ε > 0$ . Remember (from page 242, Lemma 4.1) that the SKI protocols are $(1 - e^{- 2 ε^{2} n})$ -complete if τ is at most $(1 - p_{noise} - ε) n$ .

According to the data in the table above, we must take $1 - p_{noise} - ε ⩾ \frac{τ}{n} ⩾ \frac{3}{4} + ε$ to make the above instances of SKI secure, with a failure probability bounded β by $e^{- 2 ε^{2} n}$ (by the Chernoff–Hoeffding bound [16,31]).

By changing the F-scheme, we can decrease the value $\frac{3}{4}$ in α. For instance, using the Shamir secret sharing [41], we reduce it to $\frac{5}{8}$ , as shown in Appendix B.

If we require TF-resistance (as per Theorem 4.1.C), we also get a constraint of $\frac{τ}{n} > \frac{5}{6} + \frac{ε}{2}$ , similarly.
5. Summarising SKI’s contributions

The contributions of the SKI families of protocols is two-fold: provable security and efficiency.

Provable security

As we discussed in Section 2.1, most distance-bounding protocols, new or old, do not enjoy formal security proofs. On the contrary, most have been proven vulnerable to various attacks (see [10,11, Table 1]). The only two, recent protocols which amend this and come with a formal security model and adjacent security protocol are the SKI family here, and the Fischlin–Onete (FO) protocol [24]. Moreover, in this paper, we also discuss the tightness of our security proofs.

The two formalisms are different; the FO model is game-based, the current one being based on simpler experiments run by interactive Turing-machines. Throughout the paper, for each formulated definition where it was pertinent, we discussed the link with the FO model. We remind that the FO recent protocol is discussed and compared with SKI in [48]; therein, it was observed, e.g., that the resistance of [24] to terrorist fraud lowered the resistance to mafia fraud.

Efficiency

The SKI protocol is generally more efficient than the FO protocol. To see this, one has to set acceptable levels for the noise (e.g., 5%) and completeness (e.g., 99%), look at the necessary number of rounds to obtain different levels of resistance to the different frauds (i.e., see what n, implies which α, β, γ, etc.). By doing so, one can see that, e.g., SKI offers the double of MiM-resistance (e.g., $2^{- 20}$ as opposed to $2^{- 10}$ ) for the same number of rounds (e.g., 120). The more in-depth matter of protocol efficiency is however not the focus of this paper.

6. Conclusions

In this paper, we have specified distance-bounding protocols and their security requirements, i.e., resistance to (generalised) distance-fraud, man-in-the-middle, terrorist-fraud attacks, in a general formalism for modelling location-driven security protocols developed herein. We also proposed the formal proofs for a provably secure class of practical protocols for distance-bounding, by identifying the requirements on the building blocks (i.e., the F-scheme, the leakage scheme, PRF masking, and the circular-keying security). Thus, these protocols are practical, efficient and provably secure against all frauds and their generalisations, even in noisy conditions. As a by-product, we introduced (at least) a new security notion, i.e., circular-keying for pseudorandom functions (PRFs); this models the employment of a PRF, with possible linear reuse of the key.

	${SKI}_{pro}$	${SKI}_{lite}$
α:	$B (n, τ, \frac{3}{4})$	$B (n, τ, \frac{3}{4})$
β:	$B (n, τ, \frac{2}{3})$	$B (n, τ, \frac{3}{4})$

Footnotes

A communication model

We introduce a model for distance-bounding protocols. We first specify the main ideas at a high-level and then, in Section A.2, we formalise our communication and our threat model.

SKI variants

Our F-scheme can be instantiated to produce different SKI protocols, some arguably more practical/secure than others. In the main body of this paper, we presented a version that is in-line with the existing literature in the field, i.e., one-bit responses and a set of values for challenges of small cardinality, e.g., 3. Irrespective of this alignment with the state-of-the-art, the practicality of today’s RFID/NFC cards goes beyond one-bit responses [44]. Moreover, pre-computation tables can be used.

As formalised above, to attain security, the idea behind such an F-scheme is that it should be a secret sharing scheme in which the response to the $t > 2$ challenges in round i reveals the component $x_{i}$ of the secret, but the answers to only 2 of these challenges (e.g., one from the prover and another indirectly leaked by the verifier, e.g., within a non-narrow MiM attack) do not reveal $x_{i}$ . Namely, we will consider two generic such response-functions in which the ith response ( $1 ⩽ i ⩽ n$ ) is produced as follows: $F_{shamir} (c_{i}, a_{i}, x_{i}) = x_{i} + {(a_{i})}_{1} {\bar{c}}_{i} + {(a_{i})}_{2} {\bar{c}}_{i}^{2} + \dots + {(a_{i})}_{t - 1} {\bar{c}}_{i}^{t - 1},$ where $x_{i} \in GF (q)$ , $q ⩾ 4$ , $c_{i} \in {1, \dots, t}$ is mapped to ${\bar{c}}_{i} \in GF {(q)}^{*}$ by an arbitrary injective mapping, ${(a_{i})}_{j} \in GF (q), j \in {1, \dots, t - 1}$ ; $F_{xor} (c_{i}, a_{i}, x_{i}) = x_{i} 1_{c_{i} = t} + {(a_{i})}_{1} 1_{c_{i} \in {t, 1}} + \dots + {(a_{i})}_{t - 1} 1_{c_{i} \in {t, t - 1}},$ where $c_{i} \in {1, \dots, t}$ , $x_{i} \in GF (q)$ , $q ⩾ 2$ , ${(a_{i})}_{j} \in GF (q)$ , $j \in {1, \dots, t - 1}$ , and $1_{R}$ is 1 if R is true and 0 otherwise.

Note that the function $F_{xor}$ has been invoked in the main body of this paper to define ${SKI}_{pro}$ and ${SKI}_{lite}$ . We give two more variants of it, ${SKI}_{shamir}$ and ${SKI}_{4}$ .

In our numerical studies, we actually look at three specific F-schemes dictated by the functions above, giving three specific SKI protocols as follows:

In relation with the definitions of the F-schemes and protocols above, we prove the following lemma.

Following Lemma B.1 and Theorem 4.1, it is clear that the probabilities α and β to succeed respectively in distance-frauds and in MiMs, against the SKI protocols are:

	${SKI}_{shamir}$	${SKI}_{pro}$	${SKI}_{4}$	${SKI}_{lite}$
α:	$B (n, τ, \frac{5}{8})$	$B (n, τ, \frac{3}{4})$	$B (n, τ, \frac{3}{4})$	$B (n, τ, \frac{3}{4})$
β:	$B (n, τ, \frac{1}{2})$	$B (n, τ, \frac{2}{3})$	$B (n, τ, \frac{5}{8})$	$B (n, τ, \frac{3}{4})$

References

1.
[1]G. Avoine, M. Bingöl, S. Kardas, C. Lauradoux and B. Martin, A framework for analyzing RFID distance bounding protocols, Journal of Computer Security 19(2) (2011), 289–317.

2.
[2]G. Avoine, C. Lauradoux and B. 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.
[3]G. Avoine and A. 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.
[4]A. Bay, I.C. Boureanu, A. Mitrokotsa, I.-D. Spulber and S. 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.
[5]M. Bellare and P. 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.
[6]T. Beth and Y. 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.
[7]I. Boureanu, A. Mitrokotsa and S. Vaudenay, On the pseudorandom function assumption in (secure) distance-bounding protocols, in: Progress in Cryptology – LATINCRYPT 2012, A. Hevia and G. Neven, eds, Lecture Notes in Computer Science, Springer, 2012, pp. 100–120.

8.
[8]I. Boureanu, A. Mitrokotsa and S. Vaudenay, Practical & provably secure distance-bounding, IACR Cryptology ePrint Archive 2013 (2013), 465.

9.
[9]I. Boureanu, A. Mitrokotsa and S. 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]I. Boureanu, A. Mitrokotsa and S. Vaudenay, Secure & lightweight distance-bounding, in: Proceedings of LIGHTSEC 2013, Lecture Notes in Computer Science, Vol. 8162, Springer, 2013, pp. 97–113.

11.
[11]I. Boureanu, A. Mitrokotsa and S. Vaudenay, Towards secure distance bounding, in: The 20th Anniversary Annual Fast Software Encryption (FSE 2013), Lecture Notes in Computer Science, Springer, 2013.

12.
[12]S. Brands and D. Chaum, Distance-bounding protocols (extended abstract), in: EUROCRYPT, 1993, pp. 344–359.

13.
[13]L. Bussard and W. 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]L. Bussard and W. Bagga, Distance-bounding proof of knowledge protocols to avoid terrorist fraud attacks, Technical Report RR-04-109, Institute EURECOM, May 2004.

15.
[15]N. Chandran, V. Goyal, R. Moriarty and R. Ostrovsky, Position based cryptography, in: Proceedings Advances in Cryptology – CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2009, S. Halevi, ed., Lecture Notes in Computer Science, Vol. 5677, Springer, pp. 391–407, 2009.

16.
[16]H. 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]C. Cremers, K.B. Rasmussen and S. Čapkun, Distance hijacking attacks on distance bounding protocols, Cryptology ePrint Archive, Report 2011/129, 2011, available at: http://eprint.iacr.org/.

18.
[18]C. Cremers, K.B. Rasmussen and S. Čapkun, Distance hijacking attacks on distance bounding protocols, in: IEEE Symposium on Security and Privacy, 2012, pp. 113–127.

19.
[19]Y. 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]C. Dimitrakakis, A. Mitrokotsa and S. 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]S. 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]U. Dürholz, M. Fischlin, M. Kasper and C. 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]M. Fischlin and C. Onete, Subtle kinks in distance-bounding: an analysis of prominent protocols, in: Proceedings of WISEC 2013, ACM, 2013, pp. 195–206.

24.
[24]M. Fischlin and C. 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]A. Francillon, B. Danev and S. Č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]O. 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 K. Markantonakis, Confidence in smart token proximity: relay attacks revisited, Computers & Security 28(7) (2009), 404–408.

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

32.
[32]G. Kapoor, W. Zhou and S. 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 M. Guo, eds, IEEE Computer Society, 2008, pp. 115–120.

33.
[33]C.H. Kim and G. 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, G. Avoine, F. Koeune, F. Standaert and O. 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]J. Munilla and A. 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]J. Munilla and A. 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]J. Munilla and A. Peinado, Attacks on a distance bounding protocol, Computer Communications 33 (2010), 884–889.

38.
[38]K.B. Rasmussen and S. Č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]J. Reid, J.M. Gonzalez Nieto, T. Tang and B. 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]A. Schuster and J. Nicholson, An Introduction to the Theory of Optics, 3rd edn, Edward Arnold, London, 1924.

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

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

43.
[43]D. Singelée and B. 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]B. 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]R. Trujillo-Rasua, B. Martin and G. Avoine, The Poulidor distance-bounding protocol, in: RFIDSec 2010, 2010, pp. 239–257.

46.
[46]Y.-J. Tu and S. Piramuthu, RFID distance bounding protocols, in: Proceedings of the First International EURASIP Workshop on RFID Technology, 2007.

47.
[47]S. 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]S. Vaudenay, On modeling terrorist frauds, in: Proceedings of PROVSEC 2013, Lecture Notes in Computer Science, Vol. 8209, Springer, 2013, pp. 1–20.

49.
[49]A. Yang, Y. 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.

Practical and provably secure distance-bounding

Abstract

Keywords

1. Introduction

1 In this paper, we consider authenticated distance-bounding. Namely: protocols where both participants use a pre-established secret.

2.1. Distance bounding – Informal and semi-formal approaches

Tolerance to noise

DB protocols and attacks amendments

Position-based cryptography and distance bounding

2.2. State-of-the-art: Towards provable DB security

DB formalisations

Security shortcomings in DB

2.3. Contributions

4 Since every send/receive action in our model is subject to a maximal transmission speed, there is no distinction between a lazy phase and a time-critical one as in the DFKO model [22,23].

5 We use standard notations for ITMs. Namely, random coins are separated from other inputs by a semicolon or omitted for simplicity. Inputs consist of the initial input and the variable number of incoming messages.

Bound on the distance

Informal formulation of Lemma 3.1

The use of Lemma 3.1

w.r.t. the model in Appendix A

Definition 3.1 (Distance-bounding protocols).

7 We denote this output as ( x , y ) ← Gen ( 1 s ; r k ) . For all protocols in this paper, there is just one common input, i.e., we assume x = y .

DB concurrency

3.3.1. (Generalised) distance-fraud

Definition 3.2 (α-resistance to distance-fraud).

3.3.2. (Generalised) mafia-fraud

Definition 3.3 (β-resistance to MiM).

Relations with mafia-fraud and other frauds

Relation with other formalisms

Non-narrow attackers

Definition 3.4 (Non-narrow MiM).

3.3.3. (Generalised) terrorist-fraud

Definition 3.5 ( ( γ , γ ′ ) -resistance to collusion-fraud).

9 Definition 3.3 defines MiM attacks as using an honest P ( x ) . Here, we deviate a bit by introducing P ∗ ( x ) as well.

4.1. SKI: Description and completeness

11 The L set will be later introduced as a leakage scheme; its purpose is to leak L ( x ) in the case of a collusion-fraud/terrorist-fraud.

SKI instances

SKI completeness (in noisy communications)

PRF masking

F-scheme

Definition 4.1 (F-scheme).

Leakage scheme

Circular-keying security

Tightness

Tightness

Tightness

SKI’s parameters

Provable security

Efficiency

6. Conclusions

Footnotes

A communication model

SKI variants

References

¹
In this paper, we consider authenticated distance-bounding. Namely: protocols where both participants use a pre-established secret.

⁴
Since every send/receive action in our model is subject to a maximal transmission speed, there is no distinction between a lazy phase and a time-critical one as in the DFKO model [22,23].

⁵
We use standard notations for ITMs. Namely, random coins are separated from other inputs by a semicolon or omitted for simplicity. Inputs consist of the initial input and the variable number of incoming messages.

⁷
We denote this output as $(x, y) \leftarrow Gen (1^{s}; r_{k})$ . For all protocols in this paper, there is just one common input, i.e., we assume $x = y$ .

Definition 3.5 ( $(γ, γ^{'})$ -resistance to collusion-fraud).

⁹
Definition 3.3 defines MiM attacks as using an honest $P (x)$ . Here, we deviate a bit by introducing $P^{*} (x)$ as well.

¹¹
The $L$ set will be later introduced as a leakage scheme; its purpose is to leak $L (x)$ in the case of a collusion-fraud/terrorist-fraud.