# ICRP: Internet-Friendly Cryptographic Relay-Detection Protocol
## 4 Protocol
### Distance-Bounding Protocols  
To the best of our knowledge, the strongest example of countermeasure to relay attacks using time measurements are the distance-bounding protocols, also known as proximity checks. They have been massively studied [26] in the context of Radio Frequency IDentification (RFID), and they are implemented in some contactless smartcards, e.g., Mifare Plus [28] and Mifare DESfire [29]. Given that the signal propagation cannot be faster than the speed of light, a verifier considers that there is no relaying adversary if the RTTs between the verifier and the prover are below a given upper bound. A well-known relay attack is the mafia fraud introduced by [PERSON], [PERSON] and [PERSON] in 1987 [30], and applied to the Fiat-Shamir Zero-Knowledge Argument of Knowledge [31]. This protocol is based on the complexity of the quadratic residuosity problem and allows an interactive authentication of a prover \(\mathcal{P}\) to a verifier \(\mathcal{V}\). The attack name comes from [PERSON]'s claim that the Fiat-Shamir protocol remains secure even in a scenario where the prover is a mafia-owned store, which is contradicted by [30]. The mafia fraud actually allows the attacker to get authenticated by simply relaying the exchange between the genuine prover and the verifying device. Such an attack especially makes sense in contactless authentication that needs the prover (card, transit pass, or else) to be in the proximity of the verifying device. [PERSON] and [PERSON] introduced in 1994 [22] a countermeasure to this fraud. They indeed added to the Fiat-Shamir protocol a feature to bound the distance from which is standing the genuine prover and to dismiss the authentication if it concludes that the prover is standing further than a given distance. This countermeasure is a so-called distance-bounding protocol, and it uses a series of rapid bit-exchanges to measure the round trip time between the prover and the verifier, and so the distance, using the speed of light as an upper bound. We illustrate the protocol of [PERSON] and [PERSON] in Figure 10. In this protocol, \(\mathcal{P}\) proves to \(\mathcal{V}\) that he knows \(x\) such that \(x^{2}=X\) mod \(n\) in three steps:  
* _Initialization_: \(\mathcal{P}\) picks \(k\) nonces \(r_{i}\), computes their squares \(R_{i}=r_{i}^{2}\mod n\), then picks \(k\) random bits \(c_{i}^{\mathcal{P}}\). He then sends the \(R_{i}\)'s and a commitment (typically a hash) of the \(c_{i}^{\mathcal{P}}\)s. The prover \(\mathcal{V}\) then also computes \(k\) random bits \(c_{i}^{\mathcal{V}}\). * _Fast bit-exchange_: for \(i=1\ldots k\), \(\mathcal{V}\) creates a timestamp \(t_{i}\), sends \(c_{i}^{\mathcal{V}}\), receives the responses \(c_{i}^{\mathcal{P}}\) and immediately creates another timestamp \(t_{i}^{\prime}\), and stores \((t_{i}^{\prime}-t_{i})\). * _Verification_: \(\mathcal{P}\) computes all the \(c_{i}=c_{i}^{\mathcal{P}}\oplus c_{i}^{\mathcal{V}}\), \(z_{i}=r_{i}x^{c_{i}}\) mod \(n\) and sends \(z_{i}\) to \(\mathcal{V}\). The latter checks (i) if the committed \(c_{i}^{\mathcal{P}}\)s in the initialization phase are the same as those he received in the fast bit-exchange phase (typically by recomputing the \(\text{commit}(c^{\mathcal{P}})\), (ii) computes the \(c_{i}\) similarly, (iii) checks if \(z_{i}^{2}\) is equal to \(R_{i}X^{c_{i}}\) and (iv) checks if \(\max(\left\{t_{i}^{\prime}-t_{i}\right\})\) is below a given upper bound. [PERSON] and [PERSON]'s seminal work paved the way for many other distance-bounding protocols. One could for example cite [PERSON] and [PERSON]'s protocol [23] that uses only symmetric-key cryptography. Although describing the body of literature related to distance-bounding protocols is out of the scope of this article, interested readers will find a complete analysis of distance-bounding protocols in [26].