Open access peer-reviewed chapter

An Unconditionally Secure Lightweight RFID Authentication Protocol with Untraceability

By Hung-Yu Chien

Submitted: October 21st 2010Reviewed: May 6th 2011Published: July 20th 2011

DOI: 10.5772/17595

Downloaded: 1519

1. Introduction

Radio frequency identification (RFID) is a wireless technology that uses radio signals to identify objects automatically and remotely. The most popular tags are passive devices owing to their low cost. Nowadays, RFID devices are widely deployed in many applications, such as supply chain management, inventory control, contactless credit card and so on, due to the low-cost and convenience in identifying objects with non-line-of sight reading, However, there are many potential security threats around the tiny RFID tags attached to users. The carrying items or privacy information contained in these tags might be compromised. Furthermore, low-cost makes these tags very resource-limited, which makes it very challenging to design secure protocols for these tags.

From the point of end user’s side, a secure RFID system should provide the capability of location/content privacy protection, anonymity, untraceability and availability [2]. Several RFID lightweight authentication protocols like [4-10] have been developed, but not all of them satisfy all the security requirements. All the previously proposed protocols are designed to be computationally secure, i.e., the security depends on the hardness of solving mathematical problem. Recently, Alomair et al. [1] proposed an unconditionally secure lightweight RFID (UCS-RFID for short) protocol, and claimed that their protocol achieved unconditional secrecy and unconditionally integrity. The security of the UCS-RFID protocol depends on the freshness of the keys. However, the UCS-RFID protocol does not achieve backward untraceability, even though it does achieve forward untractability.

Forward and backward untraceability are important privacy properties for RFID authentication protocol [4]. Forward untraceability requires that even if the adversary reveals the internal state of a tag at time τ, the adversary still cannot know whether a transaction after time τ+ δ(for some δ> 0) involves the same tag or not, provided that the adversary does not eavesdrop on the tag continuously after time τ. Backward untraceability requires that even if the adversary reveals the internal state of a tag at time τ, the adversary is not able to tell whether a transaction before time τinvolves the same tag or not [3]. These two properties are important for the RFID systems that the equipped tags are low-cost and potentially prone to being captured and compromised.

RRFID reader
Tii-th RFID tag
SBack-end database
pA 2N-bit prime integer, where Nis …..
ZpThe finite integer ring with usual addition and multiplication modulo p
ZpoThe multiplicative group modulo p,Zpo contains all non-zero elements of Zp; that is, Zpo = Zp \{0}
n(m)ndenotes a 2N-bit random number which is drawn uniformly from the Zpo, mdenotes that it is used in the m-th session
nl(m)The left Nmost significant bits of n(m)
nr(m)The right Nleast significant bits of n(m)
Ki(m)The secret keys of the RFID tag Ti . They consist of five subkeys, i.e., Ki(m)=( ka(0)i , kb(0)i , kc(0)i , kd(0)i , ke(0)i )The superscript mdenotes the m-th run, and the subscript idenote the i–th tag Ti.
ka(0)iA subkey which is initially drawn independently and uniformly from Z2N
kb(0)iA subkey which is initially drawn uniformly from Zp
kc(0)iA subkey which is initially drawn independently and uniformly from Zpo
kd(0)iA subkey which is initially drawn independently and uniformly from Z2N
ke(0)iA subkey which is initially drawn independently and uniformly from Zpo that will be used for updating the secret keys to maintain certain properties

Table 1.

Notations or Symbols

In this book chapter, we first examine the USC-RFID protocol, and show that the USC-RFID protocol does not achieve backward untraceability. After that, we will extend the USC-RFID protocol to an enforced one with untraceability.


2. The UCS-RFID protocol

The UCS-RFID procotol [1] is a lightweight RFID authentication protocol and is the first RFID protocol providing unconditional security for low-cost tags. The UCS-RFID protocol has the merits that it does not require tags to support random number generation and it requires only one simple multiplication on tags. The security of this protocol mainly relies on the RFID reader’s capability to deliver random numbers to RFID tags in an authenticated and secure way.

The UCS-RFID protocol consists of four phases: the tag identification phase, the reader authentication phase, the tag authentication phase, and the key updating phase (see Fig. 1 for more details). For the convenience of describing the UCS-RFID protocol, we first introduce the notations or symbols shown in Table 1. Initially, each tag Tihas a secret key set Ki(0)shared with the back-end database. In the following, we describe the m-th run of the protocol.

Tag identification phase

  1. The reader Rsends a Hellomessage to the tag Ti.

  2. Tisends its message A(m) to R, and Rforwards this messageAi(m)to the back-end database S.

  3. Slooks up the database for the secret keyKi(m)corresponding to the messageAi(m). If the Ai(m)could be identified as a valid identifier, then Ssends back the tag’s secret keyKi(m)to R. Otherwise, the tag Tiis rejected.

Reader Authentication Phase

  1. Rgenerates a random numbern(m), computes B(m)n(m)+kb(m)imodpandC(m)n(m)×kc(m)imodp, and then sends these two messages (B(m), C(m)) to Ti.

  2. After receiving B(m) and C(m), Tiextractsn(m)(B(m)kb(m)i)modp, and then verifies its integrity via checking whether the equation (B(m)kb(m)i)×kc(m)iC(m)modpholds. If so, Ris authenticated; otherwise, the tag aborts the protocol.

Tag Authentication Phase

  1. TicomputesD(m)=nl(m)kd(m)iand returns this value.

  2. After receiving the value, Rverifies whether the equation D(m)=?nl(m)kd(m)i

holds. If so, the tag is authenticated; Otherwise, the tag is rejected.

Key Updating Phase: After a successful mutual authentication between the tag and the reader, the secret key and the tag identifier are updated at the back-end database and the tag respectively as specified in Fig. 1. Fig. 1 depicts the protocol for the m-th run.

The above protocol cannot deter possible denial-of-service attacks (DOS attacks), and Alomair et al. had extended the above protocol to prevent DOS attacks and possible key exposure problem. Since these extensions are not relevant to our improvements, we will not discuss these parts for easy presentation, and interested readers are referred to [1] for details.

Figure 1.

The UCS-RFID protocol.

3. Extending the USC-RFID to untraceability

In Section 3.1, we examine the untraceability of the USC-RFID protocol, and then provide an improved scheme to enhance its untraceability.

3.1. Untraceability of the UCS-RFID protocol

Here we show that the UCS-RFID protocol does not provide backward untraceability as follows.

Suppose the tag Tihas been compromised and the internal secrets A(m)nl(m1)+ka(m)imod2Nand Ki(m)=(ka(m)i, kb(m)i, kc(m)i, kd(m)i,ke(m)i) are revealed at time τ. Let (A, B, C, D) be one eavesdropped message. Then we can tell whether the message (A, B, C, D) comes from the same tag or not as follows.

  1. Derive


  2. Derivekd(m1)i=Dnl(m1), nr(m1)=kd(m)ikd(m1)iandn(m1)=nl(m1)||nr(m1).

  3. Now we can derive the previous internal stateka(m1)i=nr(m1)ka(m)i, ke(m1)i=ke(m)i×(n(m1))-1modp, kb(m1)i=(kb(m)ike(m1)imodp)n(m1), kc(m1)i=(kc(m)i×(ke(m1)i)1modp)n(m1)andkd(m1)i=nr(m1)kd(m)i.

  4. Now we check whether the two equations B=?n(m1)+kb(m1)imodpand C=?n(m1)×kc(m1)imodphold. It is obvious that if the two equations hold, then the message (A, B, C, D) is the (A(m1),B(m1),C(m1),D(m1))from the compromised tag.

We can recursively apply the above steps to trace the messages from the same tag for i-th run, whereim1. That is, the USC-RFID protocol cannot provide backward untraceability.

Even though the USC-RFID protocol does not satisfy backward untraceability, it does provide forward untraceability. This is because, in forward untraceability, if the adversary reveals the internal state of a tag at time τ, it is required that the adversary does not eavesdrop on the tag continuouslyafter time τ. It is this break of eavesdropping that makes the USC-RFID satisfy forward untraceability.

3.2. Enhancing the untraceability

The key to find the link in our backward traceability is that the equation A(m)=nl(m1)+ka(m)imod2Ncontains only one unknown value nl(m1)when the adversary learn the internal state A(m)and Ki(m)=(ka(m)i, kb(m)i, kc(m)i, kd(m)i,ke(m)i); therefore, the adversary can derive nl(m1)=A(m)ka(m)imod2Nand the other values accordingly. We also notice that each of the other key updating equations in the key updating phase contains at least two unknown values. Therefore, we can amend the protocol by simply modifying this equation A(m)=nl(m1)+ka(m)imod2Nto contain two unknowns. One simple suggestion is thatA(m)=nl(m1)+ka(m1)imod2N. With this modification, the adversary should solve two unknowns in each equation to derive the secret even assume he has learned the current state (A(m),ka(m)i, kb(m)i, kc(m)i, kd(m)i,ke(m)i). It, therefore, cannot provide adversaries a unique and deterministic link to trace the tag.

4. Conclusion

In this book chapter, we have shown that the UCS-RFID protocol which is the first unconditionally secure mutual authentication protocol for RFID systems cannot satisfy backward untraceability, and we have proposed a simple amendment to enhance its backward untraceability. The unconditional secure RFID protocol is very promising approach for RFID security. In this book chapter, we have enhanced the first unconditional secure RFID protocol to satisfy untraceability. Our future work is to further analyze and improve the security of unconditional secure RFID protocols.

© 2011 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike-3.0 License, which permits use, distribution and reproduction for non-commercial purposes, provided the original is properly cited and derivative works building on this content are distributed under the same license.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Hung-Yu Chien (July 20th 2011). An Unconditionally Secure Lightweight RFID Authentication Protocol with Untraceability, Current Trends and Challenges in RFID, Cornel Turcu, IntechOpen, DOI: 10.5772/17595. Available from:

chapter statistics

1519total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Application of Monte Carlo Method for Determining the Interrogation Zone in Anticollision Radio Frequency Identification Systems

By Piotr Jankowski-Mihułowicz and Włodzimierz Kalita

Related Book

First chapter

Design of Low-Cost Probe-Fed Microstrip Antennas

By D. C. Nascimento and J. C. da S. Lacava

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us