120
G. Avoine et al.
Fig. 7.3 The Hancke and Kuhn protocol between a prover P and a verifier V . The notation ||
describes string concatenation
7.3.2 The Hancke-Kuhn Protocol
The protocol presented by Hancke and Kuhn [254] in 2005 performs symmetrickey distance bounding. It relies on a pseudorandom function (PRF), which takes
two inputs, a key and a message, and outputs a string of fixed length (in our case,
2n). Figure 7.3 depicts this protocol for a prover P and a verifier V . At session setup, P and V exchange nonces. 1 The two parties then use the PRF to map the key
K and the concatenation of the two nonces to a bit-string of length 2 · n. This value
is divided into a left and a right register of length n each, which we denote R 0 and
R 1 respectively. During proximity-checking, in each of the n subsequent fast rounds,
the challenger chooses a bit c i at random, and the prover is expected to respond with
the i-th bit from either the left response register (if c i = 0) or from the right one. We
denote these bits R 0
i and R 1
i respectively. For each round, the RTT is measured. At
the end of the protocol, during verification, the prover is authenticated if, and only
if, all the responses provided by the prover were correct, and if all the measured
RTT values are under the t max bound.
Design Intuition As long as the key K is unknown to an attacker, the PRF
guarantees the security-crux herein: two independent response strings. Indeed, a
man-in-the-middle attacker can relay the exact nonces used by an honest prover and
1 In an early version of this protocol, only V sent a nonce; P did not. That version of the protocol
is insecure against worst-case attackers; thus we choose to present a later version here.
G. Avoine et al.
Fig. 7.3 The Hancke and Kuhn protocol between a prover P and a verifier V . The notation ||
describes string concatenation
7.3.2 The Hancke-Kuhn Protocol
The protocol presented by Hancke and Kuhn [254] in 2005 performs symmetrickey distance bounding. It relies on a pseudorandom function (PRF), which takes
two inputs, a key and a message, and outputs a string of fixed length (in our case,
2n). Figure 7.3 depicts this protocol for a prover P and a verifier V . At session setup, P and V exchange nonces. 1 The two parties then use the PRF to map the key
K and the concatenation of the two nonces to a bit-string of length 2 · n. This value
is divided into a left and a right register of length n each, which we denote R 0 and
R 1 respectively. During proximity-checking, in each of the n subsequent fast rounds,
the challenger chooses a bit c i at random, and the prover is expected to respond with
the i-th bit from either the left response register (if c i = 0) or from the right one. We
denote these bits R 0
i and R 1
i respectively. For each round, the RTT is measured. At
the end of the protocol, during verification, the prover is authenticated if, and only
if, all the responses provided by the prover were correct, and if all the measured
RTT values are under the t max bound.
Design Intuition As long as the key K is unknown to an attacker, the PRF
guarantees the security-crux herein: two independent response strings. Indeed, a
man-in-the-middle attacker can relay the exact nonces used by an honest prover and
1 In an early version of this protocol, only V sent a nonce; P did not. That version of the protocol
is insecure against worst-case attackers; thus we choose to present a later version here.