A Salient Missing Link in RFID Security Protocols

As a result of their low production costs and tiny size, RFID tags are considered as the replacement technology for bar codes and other means of traditional identification tools which traditionally find many applications in manufacturing, supply chain management, and inventory control. A typical RFID system consists of mainly three components: tags, one or more readers, and a back-end server. On top of this hardware, a set of networking rules including the authentication (or identification) protocols reside.

RFID technology raises significant privacy issues regarding the traceability concerns. While a person could be traced by tracking his/her mobile phone through a carrier, such a method is no more useful once the phone is turned off. However, this is not the case for someone carrying an RFID gadget. First of all, most users are not aware that they are carrying RFID tags. In fact, even if they know it, tags could not be turned off in general and worse, it automatically responds to queries via radio signals. Therefore, in RFID systems, the attack scenarios and accompanying countermeasures are quite different than the typical wired or wireless systems.

Although public key cryptography has the necessary primitives to solve this sort of problems in various networks, it is not trivial to implement these primitives in networks having constraint devices such as RFID tags without breaking the cost boundaries. In fact, it is a challenging task to design authentication protocols for low-cost RFID tags resisting all of the known attacks and threats and at the same time fulfill the so-called RFID tag specifications. Therefore, solving this delicate task has recently aroused the interest of the security community, and many authentication protocols have been proposed for RFID security. Unfortunately, most of these, like [1‐11], failed to address the requirements to a satisfactory extent partially because of not having a common adversary and system definitions.

In this study, our goal is to point out a salient missing link in RFID security protocols, namely, the back-end server (or the database) role and potential pitfalls or side channels in RFID system realization. In side channel analysis, an attacker utilizes some legitimate function queries in order to collect the corresponding responses of a cryptographic system while it is functioning in a normal mode. If those responses reveal some unwanted information about the secrecy or privacy, this leakage is called side channel information and these responses are called side channels. In this respect, careless deployments of "secure" RFID authentication protocols are not exceptions and subject to side channel attacks.

Focusing on lightweight RFID security protocols, we examine the server responses for several RFID tags and realize that if the database querying is performed through a static process, the RFID system is subject to a timing attack that could easily jeopardize the system's untraceability criteria. Supporting analysis and experiments of this observation are presented with the following outline. In Section 2, after giving a brief update on related work, we describe the basic authentication protocol (BAP) as a building block used in describing our attack model. BAP will further be a basis for various RFID authentication protocols that are vulnerable to the attack. In Section 3, we present our attack model and give probability of its success in terms of the system parameters. Section 4 investigates security of some RFID protocols against the proposed attack. In Section 5, we propose solutions to fix the security flaw. Finally, we conclude in Section 6.

Timing attacks provide an attacker with secrets maintained in a security system by measuring the time it takes the system to respond to various queries. For instance, Kocher [30] designed a timing attack to recover secret keys used for RSA decryption. In addition, Brumley and Boneh presented a timing attack on unprotected OpenSSL implementations and showed that such attack was practical, that is, an attacker could measure the response-time variances of a secure Web server and could derive that servers RSA private key [31]. With a similar approach, since in different steps of the RFID protocols, tags, and the server execute different processes, if time taken to execute these steps differs based on the input of tags' state or responses, an attacker can attempt to mount a timing attack to distinguish the tags by analyzing the time variances corresponding to their input. So, with precise measurements of the time difference, an attacker can easily trace the tags and break the untraceability property of the protocol.

Intuitively, a protocol satisfies untraceability if an adversary is not able to recognize a previously observed tag [32]. Untraceability issue has been treated formally in different security models, notably driven by Avoine in [33], by Vaudenay in [13], by Van Le et al. in [34], by Juels and Weis in [12], and by Deursen et al. in [35]. The Juels-Weis model characterizes a very strong adversary with a relatively simple definition and according to this model untraceability is defined in terms of privacy experiments by which an adversary could distinguish two different tags within the limits of its computational power and functionality-call bounds. Throughout this text, we adopt the terms and notions of [12] to our needs. In this privacy model, two of the available functions for an adversary are ReaderInit and TagInit. When receiving a ReaderInit message, initializes a new session and returns the first challenge of an interactive challenge-response protocol. On the other side, by receiving TagInit message a tag is involved in the corresponding protocol session and it may respond to a protocol message or challenge. For an RFID system , the privacy experiment, , consists of the following two phases:

(1)Learning Phase. in this phase, according to Juels-Weis privacy model [12], an adversary might initiate a communication with the reader (ReaderInit) or a tag (TagInit). Also, has the ability to modify, insert, or delete messages that agree with the corresponding protocol's procedures. In other words, controls the communication channel between and each and may make any ReaderInit or TagInit calls in any interleaved order without exceeding its parameter bounds.

(2)Challenge Phase. in this phase, the adversary selects two tag candidates and and tests these with the identifers and , respectively. Depending on a randomly chosen bit , is given a challenger identifier from the set . That is, is given access to one of these tags randomly, called . The adversary might again interact with the reader and the tags. Eventually, at some point, decides to terminate the experiment and returns the bit as its guess for the value of . The success of in guessing is equivalent to its success of breaking the untraceability, and is quantified as 's advantage in distinguishing the tag's identity compared to random selection. This is expressed formally as:

where is the security parameter (i.e., the bit length of the unknown secret ). An RFID system, , achieves untraceability if for some negligible function .

It is equivalent to say that an attack is successful in tracing the tags if the adversary has a nonnegligible advantage in guessing the selected tag. As an illustrative example, assume that the probability of a correct guess is (i.e., ). In this case, is zero. Thus, the adversary, , does not have any advantage in guessing .

Definition 4.

Let denote the attacker's precision in distinguishing elapsed time of the reader responses and expressed in terms of seconds, that is, timing resolution.

In our attack model, we suppose the examined protocol is based on SLAS BAP which we call SBAP and for the privacy experiments, the adversary can follow the steps below.

In the learning phase, two tags and are randomly selected and then the adversary observes successful authenticated protocols between the reader and the tags and notes respective elapsed time of the reader responses as and .

Learning Phase

Notice that in our attack, always provides an answer. Thus in the challenge phase, if , he makes a random guess for the selected tag . On the other hand, if , the adversary only observes a successful authentication between the legitimate reader and the selected tag and records time duration between the second and the third message flow, call it . If , the challenge tag is ; otherwise the selected tag is .

Challenge Phase

Lemma 1.

Suppose in exhaustive search of database for each item , cryptographic operations are evaluated and each operation can be carried out in seconds. Let denote the maximum index difference of two candidate elements and of the query sequence , related to the tags and , respectively, such that the adversary cannot distinguish the tags by using the above attack. It is equivalent to say that

Then we can express .

Proof.

If , then the cannot realize time difference, and so does not have a nonnegligible advantage in distinguishing the tags. We know that , so must be satisfied to give a negligible advantage to the adversary. Hence the maximum index difference can be expressed as

Definition 5.

For privacy experiment , suppose and are selected and , denote the respective candidates in the exhaustive search process. Then the discrete random variable , describing the probability of being , that is, can sense the time difference, is defined as below

Proposition 1.

If denotes number of tags in the database, then for any selected tags and , the 's advantage by considering the described attack is expressed as

Proof.

Success probability of the attack depends on . If , that is, , the adversary has zero advantage since he could just as well have flipped a coin to make the guess, which would have given him the same probability of correct guessing. On the other hand if , he can recognize the time difference of the reader responses and makes a correct guess for the privacy experiment with maximum advantage. Therefore, the correct guess probability can be expressed as

The marginal probabilities of is derived as follows:

Notice that and . Thus, if we replace these values together with those given in (7) in (6), we obtain

From (1) we obtain

In Figure 2, advantage of the adversary for different and values is shown. Note that as , becomes closer to , which is the maximum advantage.

Remark 1.

Since , . Therefore, for , advantage of an adversary can be approximated as

In order to illustrate the realization of the presented attack, we consider a real life scenario in a library, where tags are used to identify books and the protocol is an SBAP.

Example 1.

We consider an SBAP RFID scheme installed in a public library to substitute bar codes on the books. Suppose the library has got about 1 million of books, , and we assume that there are about 100000 candidates between and as the candidates related to some books and , respectively, in the database, that is, . Besides, we suppose that timing resolution of an adversary who attempts to apply the proposed attack is one millisecond and also to identify a single tag the server needs a single cryptographic operation which is performed in one microsecond. Thus, , , and .

In the light of given information, it is obvious that identification process will be faster than those of 's. Moreover, by using (3) we obtain . Because , the adversary can easily distinguish these two tags by comparing the elapsed time between 2nd and 3rd rounds of the protocols for each tag.

In this section, we examine some RFID privacy schemes proposed in the literature: Those of Song and Mitchell (SM) [5], a challenge/response-based protocol by [3], the scheme of Duc et al. [22], and the model proposed by Ohkubo et al. (OSK) [2]. In our analysis, we do not consider whether or not these protocols have been cryptanalyzed previously by some different type attacks like denial of service, tag impersonation, replay attacks, or others; rather we focus on realization of our attack for these schemes. The common point of these models is that how the candidates are chosen from database in the search process is not defined exactly, and this makes them vulnerable against our attack. In the following parts, we assume that the system relies on a single computer which takes seconds to carry out a cryptographic operation, that is, , the number of tags in the system, , is 2²⁰ and seconds (i.e., ≈ 1 ms), unless otherwise is stated. Furthermore, below we only give the three message flows of the protocol since these parts interest us. Update of the secrets and other details can be found in the corresponding study.

Before giving our countermeasure against the proposed attack, we want to elaborate on some other obvious but not efficient techniques that remedy the security flaw.

With consideration of the previous parts, intuitively one can provide security against the proposed timing attack by realizing the condition that the server response time variation for different tags is negligible, in other words, the server responds with an equal time and this is same for all tags. This condition can be achieved by using look-up tables as mentioned in [19] or artificially padding the delay in reader responses for all tags as reported in [14]. For the lookup-table model the server stores all possible answers of tags that are precomputed previously. Thus, in authentication phase the server avoids to make an exhaustive search, and instead responds in constant-time. Note that although this solution fixes the problem, constructing such a scheme with satisfying security and implementation requirements is impractical. In fact, if such a system exists, then clearly the use of exhaustive search in tag identification would be abandoned. On the other hand, inserting an artificial delay at the server side, determined by the worst case time, definitely eradicates the security flaw. However, this is clearly undesirable, because it reduces the efficiency of the overall system.

Our timing analysis and the experimental results of the previous section exploit the use of an SLAS RFID scheme which uses a static exhaustive search process on server authentication. However, if a dynamic search process is employed the described timing analysis would fail in measuring the running time differences for different tag searches. In this respect, the simplest countermeasure to avoid such attacks would be simply changing the starting point of the exhaustive search process. We formulate this countermeasure as follows.

Countermeasure 1

Let an RFID system implements an SLAS scheme, having the same query sequence for all of its search items such as for some positive integer . Choosing nonidentical random query sequences for all search items gives the desired protection for the described attacks.

Although Countermeasure 1 gives a wide range of selection having different implementation complexities, naturally, the simplest countermeasures come from setting minimal differences between query sequences. Observe that query sequences can also be seen as permutations on items where is the number tags. Thus, composing the query sequences with the following constant cyclic permutation gives nonidentical shifted query sequences:

In other words, for all search items we have the following general terms for the corresponding query sequences

In fact, this modification corresponds to random selection of the starting point of the exhaustive search process. Since we use different query sequences for different tag searches, for any selected two tags the index difference will also be different. Therefore, timing attacks would fail in measuring the time differences.

It is shown that exhaustive search process is crucial in RFID authentication protocols. Although the protocol might satisfy the necessary security requirements of the RFID system specifications, careless deployments of database search mechanisms could jeopardize the security of the whole system. Therefore, it should not be left to user's choice and has to be described precisely in the system specifications. We believe our attempt would point out this salient missing link in RFID security protocols and address the potential pitfalls or side channels in realizations.

In order to support our observation through a careful analysis we give the minimum index difference of two selected tags in database such that the attacker succeeds. In addition, the success probability of the proposed attack model is derived in terms of the number of tags in the system, number of cryptographic operations carried out by the server, the computational power of the server, and the sensitivity of the attacker in timing.

As a countermeasure for the timing attack, we propose a dynamic search process which would fail in measuring the running time differences for different tag searches. We claim that choosing nonidentical random query sequences for all search items gives the desired protection for the described attacks.