Distance Bounding

Correction: the notion of tainted refers to sessions and not to adversaries. There was a small typo. (Thanks to Bogdan)

The reading group of today has been driven by Bogdan and Marcel.

In the first part of the presentation, Bogdan talked about security definitions on distance bounding protocols. These definition best fit to RFID authentication, and they are designed as countermeasures against man-in-the-middle attacks: measuring elapsed time between sending challenges and receiving responses makes, in theory, these type of attacks unfeasible.

The verifiers are called Readers, and provers are RFID Tags.

Main threats that authentication protocols may face are:
1) Mafia fraud: adversary acts as the Reader when communicating  to the Tag.
2) Terrorist fraud: Tag leaks information to the adversary.
3) Distance fraud: Tag claims to be closer that it actually is.

Identification protocols are divided into disjoint rounds of two types:  time-critical and lazy phases. Having in total N_c critical phases. Time elapsed on critical phases is compared against some threshold t_max (this is usually done by the reader). Time measurement errors may occur, so T_max < t_max exceeding critical phases are allowed. Also E_max < N_c is the maximum of allowed erroneous critical transmissions. Depending on this parameters an identification protocol generates the verified output. In this way, the proposed model tight together security and channel reliability.

Security is game-based oriented. The communication model is designed as follows: each identification session is assigned a sid identifier, known only by the adversary. The shared key between Tag and Reader is static across sessions. The adversary learns whether or  not an authentication session succeeds. Also, simultaneously, and in different sessions, the adversary can
1) impersonate the tag (reader-adversary session),
2) impersonate the reader (tag-adversary session),
3) simply be honest but curious (tag-reader session).
The transcript of these possible interactions is also known by the adversary, and its winning advantage is parameterized by his running time and the number of (each type of) sessions it engages in.

In the paper they use the notion of tainted adversaries tainted sessions to define security. In the case of the mafia-fraud model, this formalizes the following: anytime the adversary crosses messages between critical phases of different sessions, he does not change the messages, and these crossings are made in order, (tainted phases). The adversary wins if he manages to force the Reader to accept, tainting at most T_max critical phases.

For the case of terrorist attacks, tainted phases model the case when A queries the Tag's help at some point during the time-critical phase in which A is engaged with the Reader. They make a distinction in how this help is provided. It is trivial if the information provided by the Tag allows the adversary to authenticate himself to the Reader in future sessions without further help from the Tag (e.g. leaking the key). The terrorist attack corresponds to the case when the Tag provides non-trivial help.  To achieve security against terrorist attacks they use simulators S with the  restriction that S only gets the transcript of A in an offline phase  (no communication between S and the Tag in the online phase). S will try to make the Reader accept in further sessions. The advantage of A is defined as p_A - p_S where p_A (p_S) is the probability that A (S) wins. If A, aided non-trivially by the Tag, suceeds, then p_A is significantly bigger than p_S,  or in other words, if the advantage of A is negligible and A suceeds, then the Tag aided A trivially.

In the last attack, distance fraud, the adversary must send his messages before he receives any Reader's communication. This notion is captured by A committing to his first answer (and only his first message: powerful adversary). A session is tainted if A sends out a non-committed message. He wins whenever the Reader accepts, assuming there are at most T_max tainted phases.

All the above are properties of time-critical phases. Impersonation resistance models the case when A try to impersonate a Tag only in lazy phases. A wins when the Reader accepts and A is not merely relaying messages (of possibly different sessions) between the  legitimate Tag and the Reader.

Under this security definitions, they claim that the above attacks are  independent of each other, although this is an informal result, and proofs are not provided in this version of the paper.

In the second part of the presentation, Marcel discussed the security against the four type of attacks in several protocols that make use of critical and lazy phases for authentication.

 Among other ideas, the Tag may use signatures (lazy phase), of the concatenated random bits interchanged in earliest critical-time phases. According to the  paper it is neither terrorist resistance, nor distance resistance. Also it is possible to interchange nonces (lazy phase) and use them as a seed of a PRF (on the shared secret key) to generate a string. Making use of repeteadly critical-time phases, the Reader checks that the Tag holds the same string as his. Again, according to the paper, this protocol is claimed to be neither impersonate resistance, nor terrorist resistance. The last protocol is similar to the previous one, but now the lazy phase generates two values, the output of the PRF is seen as an ephemeral key, used to encrypt the master key. The bits of the ephemeral key and the encrypted master key are hidden within a binary tree. The Reader's challenges sent out in time-critical phases determine what path must the Tag follow along the tree.