On Selecting the Nonce Length in Distance-Bounding Protocols

Distance-bounding protocols form a family of challenge-response authentication protocols that have been introduced to thwart relay attacks. They enable a verifier to authenticate and to establish an upper bound on the physical distance to an untrusted prover. We provide a detailed security analysis of a family of such protocols. More precisely, we show that the secret key shared between the verifier and the prover can be leaked after a number of nonce repetitions. The leakage probability, while exponentially decreasing with the nonce length, is only weakly dependent on the key length. Our main contribution is a high probability bound on the number of sessions required for the attacker to discover the secret, and an experimental analysis of the attack under noisy conditions. Both of these show that the attack's success probability mainly depends on the length of the used nonces rather than the length of the shared secret key. The theoretical bound could be used by practitioners to appropriately select their security parameters. While longer nonces can guard against this type of attack, we provide a possible countermeasure which successfully combats these attacks even when short nonces are used.