# A Secure Distance-Bounding Protocol with Mutual Authentication

Authors: Weiwei Liu; Hua Guo; Yangguang Tian
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Distance-bounding protocol is a useful primitive in resisting distance-based attacks. Currently, most of the existing distance-bounding protocols usually do not take the reuse of nonces in designing the protocols into consideration. However, there have been some literature studies showing that nonce repetition may lead to the leakage of the shared key between protocol participants. Aikaterini et al. introduced a countermeasure that could serve as a supplementary in most distance-bounding systems allowing nonce repetition. However, their proposal only holds against passive attackers. In this paper, we introduce an active attack model and show that their countermeasure is insecure under the proposed active attack model. We also discover that all existing distance-bounding protocols with mutual authentication are vulnerable to distance-based attacks if a short nonce is applied under the proposed active model. To address this security concern, we propose a new distance-bounding protocol with mutual authentication to prevent distance-based attacks under the active adversary model. A detailed security analysis is presented for the proposed distance-bounding protocol with mutual authentication.


---

## Body

## 1. Introduction

With the rapid development of information technology like 5G, more and more people enjoy the convenience brought by various location-based services provided by service providers. Distance-based attacks enable dishonest users to cheat on their real locations and thus may cause serious economic losses to the merchants. Distance-bounding protocols play a significant role in resisting distance-based attacks since they enable one entity to decide an upper bound on the distance of the other entity contacting with him/her. Distance-bounding protocol is first proposed to preclude relay attack (mafia fraud attack) which is essentially one type of man-in-the-middle attacks by measuring the round-trip times of messages exchanged between the prover and the verifier. The relay attack could be further derived into two variants: one is a distance fraud attack, and the other is a terrorist fraud attack. The distance fraud and terrorist fraud attacks are mainly incurred by the unreasonable design of distance-bounding protocols. Unfortunately, distance-bounding protocol, which is the only primitive that we employ to achieve both identity and distance verification, will be still used in many different security applications in the long future.The idea of measuring round-trip time to estimate the distance between parties was first proposed by Brands and Chaum in 1993 [1]. However, due to the randomness of response bit in the rapid-bit exchange (RBE) phase, the first distance-bounding protocol achieves neither distance fraud nor terrorist fraud resistance. Furthermore, there have been many controversies about the usage of computing-expensive operations to be an exact public-key-based signature in their design. Since the most likely applications—RFID—tags are often equipped with limited computing capability, Hancke and Kuhn proposed a new distance-bounding protocol which is more compatible with RFID applications by eliminating computing-expensive operations in the slow phase [2]. They used a pseudorandom function which takes two nonces and a secret key as inputs to generate a 2n bit sequence regarded as a response in the RBE phase. This provides certain assurance for reducing the success probability of a dishonest prover in launching distance fraud attacks. However, their construction can resist distance fraud attacks. What is more, it has been known that prestrategy attacks will help a mafia fraud attacker obtain an extra advantage in cheating the verification distance. There are a few works trying to improve Hancke and Kuhn’s distance-bounding protocols so as to reduce the success probability of potential adversaries in launching relay attacks at the RBE phase, such as [3–5]. While some variants of Hancke and Kuhn’s protocol try to combat terrorist fraud attack by using a secret key as a seed for generating the response set at the slow phase based on an assumption that the (dishonest prover) adversary cannot send all the computed information to another adversary [6–8], however, the improved protocols still suffer from a new attack named key-learning attack where an adversary can recover the secret key bit by bit when repeating nonces. There are also some recent works focusing on protecting the prover’s privacy from dishonest verifiers [9–11]. A recent work by Aikaterini et al. [12] makes a formal analysis about the relationship between the security of the secret key and the length of nonces used. Avoine et al. proposed another method to resist the terrorist fraud attack in which secret sharing technique [13] is employed. Capkun et al. gave rise to the first distance-bounding protocol for mutual authentication [14]; nevertheless, their protocol is based on the assumption that the prover has to be equipped with considerable computing capability. This does not scale well as RFID tag usually has limited storage and computation resource. To tackle this problem, Yum et al. proposed a new system based on Hancke and Kuhn’s construction by only using a direction bit to control a user (who is involved in the protocol) to act as either a verifier or prover probabilistically [15]. Subsequently, Avonie et al. pointed out that distance-bounding protocol for mutual authentication [15] had been overestimated and presented a generic solution for converting all previous distance-bounding protocols for unilateral authentication to mutual authentication [16].


### 1.1. Our Contributions

Aikaterini et al. proposed a novel research result that the security of certain distance-bounding protocols [9, 12, 17, 18] depends on the length of nonces [12]. The authors also came up with a countermeasure to reduce the success probability of an adversary in launching an impersonation attack when the repetition of nonce occurs. However, we find that their protocol is only built on the passive attacker model. Analyzing their system in the active attacker model, we find that it performs no better than the Swiss-Knife protocol under our new active attack. What is more, besides those protocols [17–20] mentioned in [12], other protocols using the secret key [6–8, 21] as a seed to generate response information could be insecure under our attack when short nonces are used. Besides, the repetition of nonce could result in other distance-based attacks to previous distance-bounding protocols. Therefore, the security analysis should be different from the previous analysis which does not allow repetition of nonces. For instance, when short nonces are used, the distance-bounding protocols proposed in [15, 16] are suffering from distance fraud attacks. We present an enhanced protocol that can stop an adversary from launching an active attack. Security analysis of our improved protocol is also presented on a condition where repetition short nonces are used in designing the protocol.Paper Organization. The rest of the paper is organized as follows. We present Aikaterini et al.’s protocol and a practical attack against their protocol in Section 2. A novel distance-bounding protocol is presented in Section 3. A detailed security analysis regarding the protocol is presented in Section 4, and the paper is concluded in Section 5.


## 1.1. Our Contributions

Aikaterini et al. proposed a novel research result that the security of certain distance-bounding protocols [9, 12, 17, 18] depends on the length of nonces [12]. The authors also came up with a countermeasure to reduce the success probability of an adversary in launching an impersonation attack when the repetition of nonce occurs. However, we find that their protocol is only built on the passive attacker model. Analyzing their system in the active attacker model, we find that it performs no better than the Swiss-Knife protocol under our new active attack. What is more, besides those protocols [17–20] mentioned in [12], other protocols using the secret key [6–8, 21] as a seed to generate response information could be insecure under our attack when short nonces are used. Besides, the repetition of nonce could result in other distance-based attacks to previous distance-bounding protocols. Therefore, the security analysis should be different from the previous analysis which does not allow repetition of nonces. For instance, when short nonces are used, the distance-bounding protocols proposed in [15, 16] are suffering from distance fraud attacks. We present an enhanced protocol that can stop an adversary from launching an active attack. Security analysis of our improved protocol is also presented on a condition where repetition short nonces are used in designing the protocol.Paper Organization. The rest of the paper is organized as follows. We present Aikaterini et al.’s protocol and a practical attack against their protocol in Section 2. A novel distance-bounding protocol is presented in Section 3. A detailed security analysis regarding the protocol is presented in Section 4, and the paper is concluded in Section 5.


## 2. Aikaterini et al.’s Protocol for Repetition of Nonces

### 2.1. Overview of Their Protocol

Aikaterini et al.’s distance-bounding protocol: theoretically, the nonces used in designing distance-bounding protocols should never repeat. Due to practical application especially RFID tags that do use short nonces, we should consider the effects that repetition of nonces brings to the security of distance-bounding protocols. A detailed analysis of this is presented in [12]. They found that if short nonces are used, some previous protocols [17–20] are suffering from a key-learning attack where a passive adversary could learn the secret key bit by bit through the sessions where nonces are repeated. They proposed a countermeasure which can reduce the success probability of getting the secret key when short nonces are used. Their protocol is illustrated in Figure 1.Figure 1
Aikaterini et al.’s original protocol.Compared with protocols in [17–20], Aikaterini et al.’s protocol introduces another random number R. In the slow phase, a pseudorandom function f⋅ is used which takes a couple of random numbers Nv,Np and a constant number C as inputs to generate a 2n-length bit sets R0 and R1. A commitment on the secret key is generated through calculating y=k⊕hRR0,R1. The main idea is that a passive adversary has to wait until a repetition of Nv,Np,R occurs and then he can get some useful information about the secret key, and thus, the success probability of the adversary is reduced compared with the protocols [17–20] where the adversary only needs to wait until repetitions of Nv,Np.


### 2.2. Active Attack on Their Protocol

In the previous research, we all assume the verifier to be honest while the prover can be dishonest. It seems normal because it is the dishonest tags trying to cheat on their real location. After the research in [12], we can find a strong excuse to assume the verifier to be malicious, since he can find an easy way to acquire the secret key of a tag and imitate the tag ever after. The active adversary we use in this report is defined as follows.Definition 1.
The adversary is able to eavesdrop, modify, reroute, and insert messages during the execution of a cryptographic protocol. The adversary is able to obtain the value of any old session key. The adversary may start any number of parallel protocols. The adversary may be a legitimate protocol participant. The adversary does not have infinite computing ability.
Active attack byA on their protocol:(1)
A2 acts as a malicious verifier who sends a nonce Nv to an honest prover P. He records the responses Np,R,y and makes the challenge bits ci=0i=1n and stores the response bits rii=1n.(2)
A2 keeps sending Nv to P, until a repeat nonce Np is returned, and then in the RBE phase, A2 sends ci∗=1i=1n as challenge bits and records the corresponding response bits as ri∗i=1n.(3)
A2 recovers the secret key k of P through calculating k=y⊕hRa,b, where ai=ri,bi=ri∗i=1n.


### 2.3. Theoretical Analysis of the Active Attack

We follow the analysis in [12] by allowing the nonces N be either N=Np in Swiss-Knife protocol or N=Nv‖Np in protocols [17–20]. It is worth noting that, under an active attack, the security depends solely on the length of nonces used while has nothing to do with the length of the key, which confirms the research in [12]. What is more, under an active attack, the adversary can fix Nv that means if Np repeats, then N repeats. Let N1,…,Nt be a sequence of random numbers used in the 1,…,t session, respectively, where Ni=d,1≤i≤t. By controlling the challenge bits sent to the prover, the active adversary can recover the secret key when the first repeat of N appears. Assume the nonce space is d and let T be the event that the first repetition of N occurs, then the expected number of sessions ET could be expressed in the following equation:(1)ET=2⋅PrT=1+3⋅PrT=2+⋯+d+1⋅PrT=d+1,=∑i=2d+1i⋅PrT=i,where PrT=i denotes the probability that the first repetition happens in the ith session. Because there are only d nonces, therefore the first repetition will appear in the d+1 trials for sure. Let Ai be the event that there are no collisions in the previous i sessions. Let ai be the event that the collision appears in the isession for the first time. And PrT=i can be calculated in the following equation:(2)PrT=i=Prai|Ai−1PrAi−1.As forAj where 1≤j≤i−1, it can be calculated as follows:(3)PrAj=Praj¯|Aj−1PrAj−1=1−Praj|Aj−1PrAj−1.The probability ofPraj|Aj−1 means that, in the j session, the repetition of N appears for the first time:(4)Praj|Aj−1=j−1d.According to (1)–(4), the expected number of sessions ET could be expressed in the following equation:(5)ET=∑i=2d+1ii−1∏j=0i−21−jd.Thus, the expected number of sessions whenN=28,216, 224,232 can be calculated as in Table 1.Table 1
Expected number of sessions withd=28,216,224,232.
The length of nonces28216224232Number of sessions2032051328.2×104


## 2.1. Overview of Their Protocol

Aikaterini et al.’s distance-bounding protocol: theoretically, the nonces used in designing distance-bounding protocols should never repeat. Due to practical application especially RFID tags that do use short nonces, we should consider the effects that repetition of nonces brings to the security of distance-bounding protocols. A detailed analysis of this is presented in [12]. They found that if short nonces are used, some previous protocols [17–20] are suffering from a key-learning attack where a passive adversary could learn the secret key bit by bit through the sessions where nonces are repeated. They proposed a countermeasure which can reduce the success probability of getting the secret key when short nonces are used. Their protocol is illustrated in Figure 1.Figure 1
Aikaterini et al.’s original protocol.Compared with protocols in [17–20], Aikaterini et al.’s protocol introduces another random number R. In the slow phase, a pseudorandom function f⋅ is used which takes a couple of random numbers Nv,Np and a constant number C as inputs to generate a 2n-length bit sets R0 and R1. A commitment on the secret key is generated through calculating y=k⊕hRR0,R1. The main idea is that a passive adversary has to wait until a repetition of Nv,Np,R occurs and then he can get some useful information about the secret key, and thus, the success probability of the adversary is reduced compared with the protocols [17–20] where the adversary only needs to wait until repetitions of Nv,Np.


## 2.2. Active Attack on Their Protocol

In the previous research, we all assume the verifier to be honest while the prover can be dishonest. It seems normal because it is the dishonest tags trying to cheat on their real location. After the research in [12], we can find a strong excuse to assume the verifier to be malicious, since he can find an easy way to acquire the secret key of a tag and imitate the tag ever after. The active adversary we use in this report is defined as follows.Definition 1.
The adversary is able to eavesdrop, modify, reroute, and insert messages during the execution of a cryptographic protocol. The adversary is able to obtain the value of any old session key. The adversary may start any number of parallel protocols. The adversary may be a legitimate protocol participant. The adversary does not have infinite computing ability.
Active attack byA on their protocol:(1)
A2 acts as a malicious verifier who sends a nonce Nv to an honest prover P. He records the responses Np,R,y and makes the challenge bits ci=0i=1n and stores the response bits rii=1n.(2)
A2 keeps sending Nv to P, until a repeat nonce Np is returned, and then in the RBE phase, A2 sends ci∗=1i=1n as challenge bits and records the corresponding response bits as ri∗i=1n.(3)
A2 recovers the secret key k of P through calculating k=y⊕hRa,b, where ai=ri,bi=ri∗i=1n.


## 2.3. Theoretical Analysis of the Active Attack

We follow the analysis in [12] by allowing the nonces N be either N=Np in Swiss-Knife protocol or N=Nv‖Np in protocols [17–20]. It is worth noting that, under an active attack, the security depends solely on the length of nonces used while has nothing to do with the length of the key, which confirms the research in [12]. What is more, under an active attack, the adversary can fix Nv that means if Np repeats, then N repeats. Let N1,…,Nt be a sequence of random numbers used in the 1,…,t session, respectively, where Ni=d,1≤i≤t. By controlling the challenge bits sent to the prover, the active adversary can recover the secret key when the first repeat of N appears. Assume the nonce space is d and let T be the event that the first repetition of N occurs, then the expected number of sessions ET could be expressed in the following equation:(1)ET=2⋅PrT=1+3⋅PrT=2+⋯+d+1⋅PrT=d+1,=∑i=2d+1i⋅PrT=i,where PrT=i denotes the probability that the first repetition happens in the ith session. Because there are only d nonces, therefore the first repetition will appear in the d+1 trials for sure. Let Ai be the event that there are no collisions in the previous i sessions. Let ai be the event that the collision appears in the isession for the first time. And PrT=i can be calculated in the following equation:(2)PrT=i=Prai|Ai−1PrAi−1.As forAj where 1≤j≤i−1, it can be calculated as follows:(3)PrAj=Praj¯|Aj−1PrAj−1=1−Praj|Aj−1PrAj−1.The probability ofPraj|Aj−1 means that, in the j session, the repetition of N appears for the first time:(4)Praj|Aj−1=j−1d.According to (1)–(4), the expected number of sessions ET could be expressed in the following equation:(5)ET=∑i=2d+1ii−1∏j=0i−21−jd.Thus, the expected number of sessions whenN=28,216, 224,232 can be calculated as in Table 1.Table 1
Expected number of sessions withd=28,216,224,232.
The length of nonces28216224232Number of sessions2032051328.2×104


## 3. A Novel Distance-Bounding Protocol with Mutual Authentication

The primary cause of active attacks in [12] is the lack of verifier authentication. Therefore, distance-bounding protocols for mutual authentication could be a potential solution to active attacks. However, as we can see in type II attack, mutual authentication in the slow phase cannot stop an active adversary from launching an active attack because the key information the active adversary wants to gain is in the RBE phase. This means we have to implement mutual authentication in the RBE phase. Currently, there are two distance-bounding protocols achieving mutual authentication in the RBE phase [15, 16]. However, further analysis shows that if we take repetition of nonces into consideration, both protocols proposed in [15, 16] are suffering from distance fraud attacks when short nonces are used. Since all the challenge bits and response bits are generated in the slow phase, when the nonces repeat, a dishonest prover would have known the challenge bits that would be sent, and thus, he can make an advanced reply. Therefore, we design our distance-bounding protocol with mutual authentication with both fixed and random challenge messages in the RBE phase. In order to avoid confusion, the explanations of the notations used in our protocols are presented in Table 2 and our improved protocol is presented in Figure 2.Table 2
Notations used in designing our protocol.
NotationsExplanationskSymmetric secret keyfk⋅Pseudorandom functionR,Np,NvRandom numbersCV,CP,R0,R1,R0′BitsciChallenge bit in theith roundriResponse bit in theith roundFigure 2
Our improved protocol with mutual authentication.


## 4. Security Analysis

In this section, we provide a detailed analysis for our proposed protocol against distance fraud, mafia fraud, and terrorist fraud attacks. We first define some notations that will be used in this section.Letλi denote the adversary success probability in the ith round of the RBE phaseLetci and ri be the fixed challenge bit from the prover and response bit from the verifier while ci′ and ri′ be the adversary’s guessing challenge and response bits, respectively, in the ith round of the RBE phaseLetci∗ and ri∗ be the random challenge bit from the verifier and response bit from the prover while ci∗′ and ri∗′ be the guessing challenge and response bits from an adversary in the ith round of the RBE phase


### 4.1. Active Attack and Passive Attack

We first evaluate the success probability of an active adversary on our improved protocol since the adversary has no knowledge of the secret keyk. When the adversary receives the fixed challenge bit ci from the prover P in one single round, he has to guess about the response ri. As for the random challenge bit ci∗, according to our active attack model, before he meets a repetition of N, he will keep sending ci∗=0 as the random challenge. Therefore, the success probability of the active adversary in one single round is Prλi=Prλi|ri=ri′=1/2. Therefore, the success probability of the active adversary in n rounds is 1/2n.


### 4.2. Distance Fraud Attack

In distance fraud attack, a dishonest prover tries to make the verifier believe that he is closer than he really is by providing advanced responses. Let us consider a single round in the RBE phase. Since a dishonest prover has all the knowledge aboutCV‖CP‖R0‖R1, he can always give a correct ci. However, he cannot determine the challenge bit ci∗ from the verifier. When Ri0′=Ri1′, he can give a success response while when Ri0′≠Ri1′ he has to choose Ri0′ or Ri1′ as an advance response. Therefore, the success probability Prλi of the dishonest user in each round can be expressed as(6)Prλi=Prλi|ci∗=ci∗′Prci∗=ci∗′+Prλi|ci∗≠ci∗′⋅Prci∗≠ci∗′=Prλi|ci∗=ci∗′Prci∗=ci∗′+Prλi|Ri0′=Ri1′,⋅Prci∗≠ci∗′+Prλi|Ri0′≠Ri1′Prci∗≠ci∗′−Prλi|ci∗=ci∗′∧Ri0′=Ri1′Prci∗=ci∗′∧Ri0′=Ri1′=58.Therefore, the success probability of a dishonest prover in launching a distance fraud attack isPrλ=5/8n.


### 4.3. Mafia Fraud Attack

In mafia fraud attack, both the verifier and prover are honest. An adversary tries to launch a mafia fraud attack between the verifier and prover by acting as the prover with the verifier and verifier with the prover. We say the adversary succeeds if she is successfully authenticated by either the verifier or prover. Therefore, we divide the attack into the following two situations, and the success probabilitiesPrλ1 and Prλ2 are calculated, respectively.The adversary first acts as the prover communicating with the verifier and then acts as the verifier using the information got from the verifier and communicates with the proverThe adversary first acts as the verifier communicating with the prover and then acts as the prover using the information got from the prover and communicates with the verifier


#### 4.3.1. Case I

In this case, the adversary possesses no knowledge aboutCV‖CP‖R0‖R1‖R0′‖R1′. Therefore, in one single round, he has to guess the values of ci and ri∗, and the success probability Prλi in one single round can be expressed as follows: Prλi=Prλi|ci=ci′∧ri∗=ri∗′⋅Prci=ci′∧ri∗=ri∗′=1/4. Therefore, the success probability of the adversary under Case I in n rounds is 1/4n.


#### 4.3.2. Case II

In this case, the adversary has to guess the response bitri to the prover and ci∗ that a verifier might ask later in one single round, and thus, the success probability in one single Prλi round can be expressed as follows: Prλi=Prλi|ri=ri′∧ci∗=ci∗′⋅Prri=ri′∧ci∗=ci∗′+Prλi|ri=ri′∧ci∗≠ci∗′⋅Prri=ri′∧ci∗≠ci∗′=3/8.Therefore, the success probability of the adversary under Case II inn rounds is 3/8n.


### 4.4. Terrorist Fraud Attack

In terrorist fraud attack, a dishonest prover collaborates with an adversary trying to cheat on his real location. It is worth noticing that the dishonest prover should provide as much information as possible on the condition that that information will not reveal his secret key. Therefore, we first evaluate that information in our protocol that could be given to an adversary by a dishonest prover which is presented in Table3.Table 3
Information that could be accessed by an adversary in terrorist fraud attack.
Different casesInformationCase ICP‖R0‖R1‖R0′‖R1′Case IICV‖R0‖R1‖R0′‖R1′Case IIICV‖CP‖R0‖R1‖R0′‖R1′Case IVCV‖CP‖R0‖R1‖R0′‖R1′Case VCV‖CP‖R0‖R1‖R0′‖R1′Case VICV‖CP‖R0‖R1‖R0′‖R0Further analysis shows that the adversary can recoverCP and then he can calculate the secret key held by the dishonest user which contradicts the definition of terrorist fraud attack. Therefore, we only need to analyze Cases II to VII, and the corresponding success probabilities are presented in Table 4.Table 4
The success probability of the adversary under different cases.
Different casesSuccess probabilityCase IIPrλ=1/2nCase IIIPrλ=3/4n−1Case IVPrλ=3/4n−1Case VPrλ=3/4nCase VIPrλ=3/4nTherefore, the success probability of the dishonest prover and adversary in launching a terrorist fraud attack is3/4n−1.


### 4.5. Comparison with Existing Distance-Bounding Protocols

We compare our proposed distance-bounding protocol with some popular existing protocols and the result is presented in Table5. It can be seen from the result that our proposed protocol is the first protocol that is secure under the active adversary model as well as achieves mutual authentication. For space limitation, we use “M” to represent mafia fraud attack, “T” to represent terrorist fraud attack, “MA” to represent mutual authentication, “NR” to represent nonce repetition, and “SA” to represent secure under active adversary model.Table 5
Performance of existing distance-bounding protocols.
ProtocolsMTMNRSA[1]√××××[2]√××××[14]√×√××[15]√√√××[16]√√√××[12]√√√√×Ours√√√√√


## 4.1. Active Attack and Passive Attack

We first evaluate the success probability of an active adversary on our improved protocol since the adversary has no knowledge of the secret keyk. When the adversary receives the fixed challenge bit ci from the prover P in one single round, he has to guess about the response ri. As for the random challenge bit ci∗, according to our active attack model, before he meets a repetition of N, he will keep sending ci∗=0 as the random challenge. Therefore, the success probability of the active adversary in one single round is Prλi=Prλi|ri=ri′=1/2. Therefore, the success probability of the active adversary in n rounds is 1/2n.


## 4.2. Distance Fraud Attack

In distance fraud attack, a dishonest prover tries to make the verifier believe that he is closer than he really is by providing advanced responses. Let us consider a single round in the RBE phase. Since a dishonest prover has all the knowledge aboutCV‖CP‖R0‖R1, he can always give a correct ci. However, he cannot determine the challenge bit ci∗ from the verifier. When Ri0′=Ri1′, he can give a success response while when Ri0′≠Ri1′ he has to choose Ri0′ or Ri1′ as an advance response. Therefore, the success probability Prλi of the dishonest user in each round can be expressed as(6)Prλi=Prλi|ci∗=ci∗′Prci∗=ci∗′+Prλi|ci∗≠ci∗′⋅Prci∗≠ci∗′=Prλi|ci∗=ci∗′Prci∗=ci∗′+Prλi|Ri0′=Ri1′,⋅Prci∗≠ci∗′+Prλi|Ri0′≠Ri1′Prci∗≠ci∗′−Prλi|ci∗=ci∗′∧Ri0′=Ri1′Prci∗=ci∗′∧Ri0′=Ri1′=58.Therefore, the success probability of a dishonest prover in launching a distance fraud attack isPrλ=5/8n.


## 4.3. Mafia Fraud Attack

In mafia fraud attack, both the verifier and prover are honest. An adversary tries to launch a mafia fraud attack between the verifier and prover by acting as the prover with the verifier and verifier with the prover. We say the adversary succeeds if she is successfully authenticated by either the verifier or prover. Therefore, we divide the attack into the following two situations, and the success probabilitiesPrλ1 and Prλ2 are calculated, respectively.The adversary first acts as the prover communicating with the verifier and then acts as the verifier using the information got from the verifier and communicates with the proverThe adversary first acts as the verifier communicating with the prover and then acts as the prover using the information got from the prover and communicates with the verifier


### 4.3.1. Case I

In this case, the adversary possesses no knowledge aboutCV‖CP‖R0‖R1‖R0′‖R1′. Therefore, in one single round, he has to guess the values of ci and ri∗, and the success probability Prλi in one single round can be expressed as follows: Prλi=Prλi|ci=ci′∧ri∗=ri∗′⋅Prci=ci′∧ri∗=ri∗′=1/4. Therefore, the success probability of the adversary under Case I in n rounds is 1/4n.


### 4.3.2. Case II

In this case, the adversary has to guess the response bitri to the prover and ci∗ that a verifier might ask later in one single round, and thus, the success probability in one single Prλi round can be expressed as follows: Prλi=Prλi|ri=ri′∧ci∗=ci∗′⋅Prri=ri′∧ci∗=ci∗′+Prλi|ri=ri′∧ci∗≠ci∗′⋅Prri=ri′∧ci∗≠ci∗′=3/8.Therefore, the success probability of the adversary under Case II inn rounds is 3/8n.


## 4.3.1. Case I

In this case, the adversary possesses no knowledge aboutCV‖CP‖R0‖R1‖R0′‖R1′. Therefore, in one single round, he has to guess the values of ci and ri∗, and the success probability Prλi in one single round can be expressed as follows: Prλi=Prλi|ci=ci′∧ri∗=ri∗′⋅Prci=ci′∧ri∗=ri∗′=1/4. Therefore, the success probability of the adversary under Case I in n rounds is 1/4n.


## 4.3.2. Case II

In this case, the adversary has to guess the response bitri to the prover and ci∗ that a verifier might ask later in one single round, and thus, the success probability in one single Prλi round can be expressed as follows: Prλi=Prλi|ri=ri′∧ci∗=ci∗′⋅Prri=ri′∧ci∗=ci∗′+Prλi|ri=ri′∧ci∗≠ci∗′⋅Prri=ri′∧ci∗≠ci∗′=3/8.Therefore, the success probability of the adversary under Case II inn rounds is 3/8n.


## 4.4. Terrorist Fraud Attack

In terrorist fraud attack, a dishonest prover collaborates with an adversary trying to cheat on his real location. It is worth noticing that the dishonest prover should provide as much information as possible on the condition that that information will not reveal his secret key. Therefore, we first evaluate that information in our protocol that could be given to an adversary by a dishonest prover which is presented in Table3.Table 3
Information that could be accessed by an adversary in terrorist fraud attack.
Different casesInformationCase ICP‖R0‖R1‖R0′‖R1′Case IICV‖R0‖R1‖R0′‖R1′Case IIICV‖CP‖R0‖R1‖R0′‖R1′Case IVCV‖CP‖R0‖R1‖R0′‖R1′Case VCV‖CP‖R0‖R1‖R0′‖R1′Case VICV‖CP‖R0‖R1‖R0′‖R0Further analysis shows that the adversary can recoverCP and then he can calculate the secret key held by the dishonest user which contradicts the definition of terrorist fraud attack. Therefore, we only need to analyze Cases II to VII, and the corresponding success probabilities are presented in Table 4.Table 4
The success probability of the adversary under different cases.
Different casesSuccess probabilityCase IIPrλ=1/2nCase IIIPrλ=3/4n−1Case IVPrλ=3/4n−1Case VPrλ=3/4nCase VIPrλ=3/4nTherefore, the success probability of the dishonest prover and adversary in launching a terrorist fraud attack is3/4n−1.


## 4.5. Comparison with Existing Distance-Bounding Protocols

We compare our proposed distance-bounding protocol with some popular existing protocols and the result is presented in Table5. It can be seen from the result that our proposed protocol is the first protocol that is secure under the active adversary model as well as achieves mutual authentication. For space limitation, we use “M” to represent mafia fraud attack, “T” to represent terrorist fraud attack, “MA” to represent mutual authentication, “NR” to represent nonce repetition, and “SA” to represent secure under active adversary model.Table 5
Performance of existing distance-bounding protocols.
ProtocolsMTMNRSA[1]√××××[2]√××××[14]√×√××[15]√√√××[16]√√√××[12]√√√√×Ours√√√√√


## 5. Conclusions

In this paper, we propose an active attack on the distance-bounding protocol proposed in [12] where an adversary can catch the secret key much more efficiently when short nonces are used. Theoretical analysis shows their protocol performs no better than the protocols [17–20] under our active attack. We propose an enhanced version of their protocol as a countermeasure to the active attack using the knowledge of mutual authentication. However, when previous distance bounding protocols allowing short nonces [15, 16] are applied into real-world applications, since all challenge bits in these protocols are fixed, therefore it will cause a distance fraud attack. Therefore, we set both fixed and random challenge bits in the RBE phase. Detailed security analysis is also presented which takes repetition of nonces into consideration. Through the length of the RBE phase be extended to 2n-length, our improved protocol shows a better result in resisting the key-learning attack as well as achieves mutual authentication.



---

*Source: 6644326-2021-06-01.xml*