7 From Relay Attacks to Distance-Bounding Protocols
119
response faster than expected or sending a correct response early, e.g., if the verifier
sends a challenge followed by some framing bits and expects the provers to start
calculating the response only once the entire message, including the stop frame bit,
is received but instead the prover can send the correct response immediately after
the challenge bit is received.
7.3 Canonical Distance-Bounding Protocols
In this section, we describe and discuss two protocols that can be considered
the cornerstones of distance-bounding schemes. The Brands-Chaum protocol is
the earliest distance-bounding protocol ever published, and is based on Beth and
Desmedt’s [83] idea that roundtrip times (RTTs) can detect mafia fraud. The
Hancke-Kuhn protocol resurrected research interest in distance-bounding protocols,
and was specifically designed for contactless devices.
7.3.1 General Structure
General Setup Distance-bounding schemes can use either symmetric- or publickey cryptography. In the symmetric-key scenario, the prover and verifier share a
secret key K. For public-key primitives, the prover stores a private/public key-pair
(sk i , pk i ), for which the verifier only holds the public key. Each verifier is assumed
to possess a clock able to measure roundtrip times (RTTs) with a fine-grained
resolution (ideally, less than a nanosecond). In the protocol, the verifier uses the
clock to measure RTT values for several so-called time-critical rounds.
General 3-Phase Structure The general structure of distance-bounding protocols
follows these three phases (each consisting of zero, one, or multiple rounds
of communication): session set-up, proximity checking, and verification. During
session set-up, the prover and verifier exchange session-specific data and possibly
pre-compute some values that will be used during the next stage. During proximity
checking, the parties execute n fast phases of communication: the verifier generally
starts the clock at the beginning of each round, and stops it at the end. The responses
r i sent by the prover, and the round-trip time (RTT) of each round are stored by
the verifier. Finally, during verification, the verifier performs some cryptographic
operations, may exchange some more messages with the prover, and it compares
the measured RTT values of the proximity-checking phase with a threshold. At the
end of this phase, the verifier must output an authentication bit, which is typically
1 if the prover is assumed to be legitimate and within a correct distance, and 0
otherwise.
119
response faster than expected or sending a correct response early, e.g., if the verifier
sends a challenge followed by some framing bits and expects the provers to start
calculating the response only once the entire message, including the stop frame bit,
is received but instead the prover can send the correct response immediately after
the challenge bit is received.
7.3 Canonical Distance-Bounding Protocols
In this section, we describe and discuss two protocols that can be considered
the cornerstones of distance-bounding schemes. The Brands-Chaum protocol is
the earliest distance-bounding protocol ever published, and is based on Beth and
Desmedt’s [83] idea that roundtrip times (RTTs) can detect mafia fraud. The
Hancke-Kuhn protocol resurrected research interest in distance-bounding protocols,
and was specifically designed for contactless devices.
7.3.1 General Structure
General Setup Distance-bounding schemes can use either symmetric- or publickey cryptography. In the symmetric-key scenario, the prover and verifier share a
secret key K. For public-key primitives, the prover stores a private/public key-pair
(sk i , pk i ), for which the verifier only holds the public key. Each verifier is assumed
to possess a clock able to measure roundtrip times (RTTs) with a fine-grained
resolution (ideally, less than a nanosecond). In the protocol, the verifier uses the
clock to measure RTT values for several so-called time-critical rounds.
General 3-Phase Structure The general structure of distance-bounding protocols
follows these three phases (each consisting of zero, one, or multiple rounds
of communication): session set-up, proximity checking, and verification. During
session set-up, the prover and verifier exchange session-specific data and possibly
pre-compute some values that will be used during the next stage. During proximity
checking, the parties execute n fast phases of communication: the verifier generally
starts the clock at the beginning of each round, and stops it at the end. The responses
r i sent by the prover, and the round-trip time (RTT) of each round are stored by
the verifier. Finally, during verification, the verifier performs some cryptographic
operations, may exchange some more messages with the prover, and it compares
the measured RTT values of the proximity-checking phase with a threshold. At the
end of this phase, the verifier must output an authentication bit, which is typically
1 if the prover is assumed to be legitimate and within a correct distance, and 0
otherwise.