Practical & Provably Secure Distance-Bounding

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. At FSE 2013, we presented SKI as the first family of provably secure distance bounding protocols. At LIGHTSEC 2013, we presented the best attacks against SKI. In this paper, we present the security proofs. More precisely, we explicate a general formalism for distance-bounding protocols. Then, we prove that SKI and its variants is provably secure, even under the real-life setting of noisy communications, against the main types of relay attacks: distance-fraud and generalized versions of mafia- and terrorist-fraud. For this, we reinforce the idea of using secret sharing, combined with the new notion of a leakage scheme. In view of resistance to 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 use PRF masking to fix common mistakes in existing security proofs/claims.