Distance bounding protocols details

[Papa Carder]

Overview of Distance Bounding Protocols​

Distance bounding protocols (DBPs) are cryptographic protocols designed to enable a verifier (V) to establish an upper bound on the physical distance to a prover (P). They achieve this by measuring the round-trip time (RTT) of signals, typically electromagnetic waves, between V and P, leveraging the fact that these signals travel at nearly the speed of light (c ≈ 3 × 10^8 m/s) and cannot exceed it. The core principle is to compute the distance as d ≤ (RTT / 2) × c, after subtracting any known processing delays at P. This provides a secure way to verify proximity, preventing adversaries from simulating closeness through relaying or other manipulations.

DBPs are particularly useful in scenarios where physical presence is critical for security, as they integrate timing measurements with cryptographic authentication to thwart distance-based frauds. They operate in half-duplex or full-duplex modes, often using minimal data exchanges (e.g., single bits) to minimize latency and ensure tight bounds.

History​

The concept of distance bounding originated in the early 1990s, with the seminal work by Stefan Brands and David Chaum in their 1994 paper "Distance-Bounding Protocols," presented at EUROCRYPT '93. This built on earlier ideas from Beth and Desmedt (1990) regarding relay attacks. Key advancements followed:

• 2003-2005: Protocols for secure positioning in wireless networks (Capkun, Buttyán, Hubaux) and RFID-specific designs (Hancke and Kuhn).
• 2010: Rasmussen and Capkun introduced analog-based processing for sub-nanosecond delays.
• 2015: Hussain et al. modified the 2010 protocol using polarization for efficiency.
• 2018: Formal verification frameworks without explicit time/location (Mauw et al.).
• Up to 2026: Developments include commercial integrations like MIFARE Proximity Check (introduced ~2017-2018) and ongoing refinements for Bluetooth and UWB in IoT/automotive systems. Recent work focuses on provable security and resistance to quantum threats, though major breakthroughs post-2018 are limited in public sources.

How They Work​

DBPs typically consist of three phases: initialization (setup and nonce exchange), rapid bit exchange (time-critical challenge-response), and verification/authentication.

1. Initialization: V and P exchange nonces and compute shared values using a secret key (e.g., pseudorandom functions).
2. Rapid Bit Exchange: V sends challenge bits (often single bits), P computes and responds immediately (e.g., via XOR or selection from precomputed sequences). RTT is measured for each exchange. Processing delays must be minimal (e.g., <1 ns for ~15 cm accuracy).
3. Verification: V checks responses for correctness and ensures RTT ≤ threshold (t_m), bounding distance as d ≤ c × t_m / 2.

Example Protocols

• Brands-Chaum (1994): Integrates with public-key identification; V sends challenges, P responds with signed bits. Vulnerable to distance hijacking.
• Hancke-Kuhn (2005) for RFID: Uses UWB pulses; precomputes two sequences (R0, R1) from shared key/nonce, selects based on challenge. Probability of attacker success: (3/4)^n for n bits.
• Rasmussen-Capkun (2010): Analog processing for ultra-low delays; modified in 2015 for polarization-based efficiency.
• TREAD (2010s): Terrorist-fraud resistant; analyzed to reveal mafia fraud vulnerabilities via relay.
• MIFARE Proximity Check: Commercial; uses ISO 14443; exchanges 8-byte challenges/responses with MAC verification; bounds via short intervals (e.g., 0.1-0.2 ms slack for ±15 km, but tighter in practice).

Protocols often use asynchronous logic or stable clocks to handle timing uncertainties like clock drift (e.g., 100 ppm error over 1 ms = ±15 m).

Types of Fraud Prevented​

DBPs primarily counter relay attacks (mafia fraud), where an adversary relays signals to fake proximity. Other prevented frauds:

• Distance Fraud: P claims to be farther but is closer (e.g., overclocking detection).
• Terrorist Fraud: P colludes with adversary but doesn't reveal secrets.
• Distance Hijacking: Honest P exploited to authenticate a distant intruder.

Applications in RFID/NFC/EMV​

In RFID/NFC systems (e.g., ISO 14443), DBPs prevent unauthorized access or payments by ensuring <10 cm proximity. For EMV contactless, they mitigate relay attacks in payments, integrating with cryptograms (e.g., ARQC) via timing bounds. Other uses: door access, vehicle tolls, military IFF, prisoner tracking, and sensor networks (anti-wormhole). Bluetooth/UWB variants secure IoT/automotive keyless entry.

Security Models and Verification​

Security models define DBPs as secure if claims of proximity imply causal event ordering: challenge → prover action → response. Causality-based verification (e.g., in Tamarin) equates time/location models to trace ordering, proving equivalence under properties like speed-of-light consistency. Analyzed protocols (e.g., 13 in Tamarin) reveal vulnerabilities like mafia fraud in TREAD. Considerations include noise, bit errors, and false acceptance/rejection probabilities.

For implementation, refer to standards like EMV Contactless Kernel for timing enforcements or academic prototypes for custom hardware.