Open access

An Unconditionally Secure Lightweight RFID Authentication Protocol with Untraceability

Written By

Hung-Yu Chien

Submitted: October 21st, 2010 Published: July 20th, 2011

DOI: 10.5772/17595

Chapter metrics overview

1,821 Chapter Downloads

View Full Metrics

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 N is …..
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)n denotes a 2N-bit random number which is drawn uniformly from the Zpo, m denotes that it is used in the m-th session
nl(m)The left N most significant bits of n(m)
nr(m)The right N least 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 m denotes the m-th run, and the subscript i denote 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 Ti has 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 R sends a Hello message to the tag Ti.

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

  3. S looks 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 S sends back the tag’s secret keyKi(m)to R. Otherwise, the tag Ti is rejected.

Reader Authentication Phase

  1. R generates a random numbern(m), computes B(m)n(m)+kb(m)imodp andC(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), Ti extractsn(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)modp holds. If so, R is authenticated; otherwise, the tag aborts the protocol.

Tag Authentication Phase

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

  2. After receiving the value, R verifies 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 Ti has been compromised and the internal secrets A(m)nl(m1)+ka(m)imod2N and 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)imodp and C=?n(m1)×kc(m1)imodp hold. 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 continuously after 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)imod2N contains 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)imod2N and 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)imod2N to 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.


  1. 1. AlomairB.ClarkA.CuellarJ.PoovendranR. 2010 Securing Low-Cost RFID Systems: an Unconditionally Secure Approach, 2010 Workshop on RFID Security- RFIDsec’10 Asia.
  2. 2. ChienH. Y.LaihC. S. 2009 ECC-Based Lightweight Authentication Protocol with Untraceability for Low-Cost RFID, Journal of Parallel and Distributed Computing. 69 10 848853 .
  3. 3. PhanR. C. W.WuJ.OuafiK. 2008 Privacy Analysis of Forward and Backward Untraceable RFID Authentication Schemes. Available from :
  4. 4. HenriciA. D.MaullerP. 2004 “Hash-based Enhancement of Location Privacy for Radio-Frequency Identification Devices using Varying Identifiers,” In the Proceedings of PerSec’04 at IEEE PerCom, 149153 .
  5. 5. KarthikeyanS.NesterenkoM. 2005 “RFID security without extensive cryptography,” Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks, 6367 .
  6. 6. MolnarD.WagnerD. 2004 “Privacy and security in library RFID: Issues, practices, and architectures,” Conference on Computer and Communications Security- CCS’04, 210219 .
  7. 7. OhkuboM.SuzkiK.KinoshitaS. 2003 ”Cryptographic Approach to ‘Privacy-Friendly’ Tags,” In RFID Privacy Workshop, 2003.
  8. 8. WeisS. A. 2003 “Security and Privacy in Radio-Frequency Identification Devices,” Masters Thesis MIT.
  9. 9. AvoineG.DysliE.OechslinP. 2005 “Reducing time complexity in RFID systems,” The 12th Annual Workshop on Selected Areas in Cryptography(SAC).
  10. 10. ChienH. Y. 2007 “SASI: A New Ultra-Lightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity”, IEEE Transactions on Dependable and Secure Computing 4(4), 337340 , October, 2007.

Written By

Hung-Yu Chien

Submitted: October 21st, 2010 Published: July 20th, 2011