Security, Privacy and Efficiency in RFID SystemsbyEhsan VahediB.Sc., Electrical Engineering, K. N. T. University of Technology, Iran, 2004M.Sc., Electrical and Computer Engineering, University of Tehran, Iran, 2008A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)September 2013c? Ehsan Vahedi, 2013AbstractRadio frequency identification (RFID) is a ubiquitous wireless technology that allows ob-jects to be identified automatically. Using the RFID technology can simplify many ap-plications and provide many benefits but meanwhile, the security and privacy of RFIDsystems should be taken into account. In this thesis, we have two goals. The first one is toimprove the security and privacy in RFID systems. Our second goal is to provide accurateanalytical models for the most important tag singulation schemes. We use these analyticalmodels to evaluate and compare the efficiency of the tag singulation schemes.First, we study the blocking attack in RFID systems and develop an analytical modelfor it. Using this analytical model, we propose two probabilistic blocker tag detection(P-BTD) algorithms for RFID systems that operate based on the binary tree walking andALOHA techniques.Then, we study the security and privacy of some recently introduced light-weight au-thentication protocols, and discuss their advantages and drawbacks. Based on this analysisand considering the hardware limitations of RFID tags, we propose a new authenticationprotocol that improves the security and privacy in RFID systems.By taking advantage of the analytical model we proposed for the ALOHA-based P-BTDalgorithm, we develop an accurate tag estimate method. Using the proposed method, wecan estimate the number of tags in RFID systems accurately, and design more efficientALOHA-based tag singulation mechanisms.Next, we study the EPC Gen-2 protocol and its tag singulation mechanism. We modeliiAbstractthe EPC Gen-2 protocol as an absorbing Markov chain. Using the model proposed, wederive accurate analytical expressions for the expected number of queries and the expectednumber of transmitted bits needed to identify all tags in the RFID system.Finally, we study the use of the CDMA technique for RFID systems. We model theCDMA-based tag singulation procedure as an absorbing Markov chain, and derive accurateanalytical expressions for the expected number of queries and the amount of transmitteddata needed to identify all tags in the system. Using the analytical models developed, wecompare the performance of the CDMA-based and the EPC Gen-2 tag singulation schemes.iiiPrefaceHereby, I declare that I am the first author and the principal contributor of this thesis. Ihave also benefited from the valuable comments and advice of Dr. Rabab K. Ward, Dr.Ian F. Blake, Dr. Vahid Shah-Mansouri and Dr. Vincent W.S. Wong.The following publications describe the work completed in this thesis. In some cases,the conference papers contain materials overlapping with the journal papers.Journal Papers Accepted/Published? Ehsan Vahedi and Vincent W.S. Wong and Ian F. Blake and R. K. Ward, ?Proba-bilistic Analysis and Correction of Chen?s Tag Estimate Method,? IEEE Trans. onAutomation Sciences and Engineering, vol. 8, no. 3, pp. 659-663, July 2011.? Ehsan Vahedi and Vahid Shah-Mansouri and Vincent W.S. Wong and Ian F. Blakeand Rabab K. Ward, ?Probabilistic Analysis of Blocking Attack in RFID Systems,?IEEE Trans. on Information Forensics and Security, vol. 6, no. 3, pp. 803-817,September 2011.? Ehsan Vahedi and Rabab K. Ward and Vahid Shah-Mansouri and Vincent W.S.Wong and Ian F. Blake, ?On Securing RFIDs Against Blocking Attacks,? IEEEMMTC Letter, vol. 2, no. 6, pp. 16-18, December 2011.ivPreface? Ehsan Vahedi and Rabab K. Ward and Ian F. Blake, ?Performance Analysis ofRFID Protocols: CDMA vs. the Standard EPC Gen2,? IEEE Trans. on AutomationSciences and Engineering, Accepted, August 2013.Book Chapter? Ehsan Vahedi and Vincent W.S. Wong and Ian F. Blake, ?An overview of cryptog-raphy,? Advanced Security and Privacy for RFID Technologies, IGI Global, Chapter6, pp. 70-100, March 2013.Conference Papers Published? Ehsan Vahedi and Vahid Shah-Mansouri and Vincent W.S. Wong and Ian F. Blake,?A Probabilistic Approach for Detecting Blocking Attack in RFID Systems,? IEEEICC?10, Cape Town, South Africa, May 2010.? Ehsan Vahedi and Rabab K. Ward and Ian F. Blake, ?Security Analysis and Com-plexity Comparison of Some Recent Lightweight RFID Protocols,? CISIS?11, LNCS6694 (Springer-Heidelberg), Malaga, Spain, June 2011.? Ehsan Vahedi and Rabab. K. Ward and Ian F. Blake, ?Analytical Modelling ofRFID Generation-2 Protocol Using Absorbing Markov Chain Theorem,? IEEE Globe-com?12, Anaheim, USA, December 2012.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Radio Frequency Identification (RFID) . . . . . . . . . . . . . . . . . . . . 21.2 Security and Privacy in RFID Systems . . . . . . . . . . . . . . . . . . . . 51.3 Tag Singulation Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.1 Tree-based Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 ALOHA-based Techniques . . . . . . . . . . . . . . . . . . . . . . . 101.3.3 CDMA-based Techniques . . . . . . . . . . . . . . . . . . . . . . . 121.4 Contributions and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 15viTable of Contents1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 Probabilistic Analysis of Blocking Attack in RFID Systems . . . . . . 222.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . . . . 262.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 342.3 Probabilistic Blocker Tag Detection (P-BTD) Algorithm . . . . . . . . . . 452.3.1 Binary Tree Walking-based RFID Systems . . . . . . . . . . . . . . 452.3.2 ALOHA-based RFID Systems . . . . . . . . . . . . . . . . . . . . . 482.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502.4.1 Binary Tree Walking-based RFID Systems . . . . . . . . . . . . . . 502.4.2 ALOHA-based RFID Systems . . . . . . . . . . . . . . . . . . . . . 562.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 Toward a Light-weight Authentication Protocol for RFID Systems . . 643.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.2.1 EPC Class-1 Gen-2 RFID Protocol . . . . . . . . . . . . . . . . . . 663.2.2 Henrici-Mu?ller RFID Protocol . . . . . . . . . . . . . . . . . . . . 683.2.3 Lim et al. RFID Protocols . . . . . . . . . . . . . . . . . . . . . . 703.2.4 Tan et al. RFID Protocol . . . . . . . . . . . . . . . . . . . . . . . 733.2.5 Sun et al. Gen-2+ RFID Protocol . . . . . . . . . . . . . . . . . . 753.3 Security and Privacy Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 773.3.1 EPC Class-1 Gen-2 RFID Protocol . . . . . . . . . . . . . . . . . . 793.3.2 Henrici-Mu?ller RFID Protocol . . . . . . . . . . . . . . . . . . . . 803.3.3 Lim et al. RFID Protocols . . . . . . . . . . . . . . . . . . . . . . 81viiTable of Contents3.3.4 Tan et al. RFID Protocol . . . . . . . . . . . . . . . . . . . . . . . 843.3.5 Sun et al. Gen-2+ RFID Protocol . . . . . . . . . . . . . . . . . . 853.4 The New Light-weight Authentication Protocol . . . . . . . . . . . . . . . 863.4.1 Why the SQUASH Method? . . . . . . . . . . . . . . . . . . . . . 873.4.2 Reduced Version of the SQUASH . . . . . . . . . . . . . . . . . . . 893.4.3 The Proposed Protocol . . . . . . . . . . . . . . . . . . . . . . . . 923.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 994 Probabilistic Tag Estimation Method . . . . . . . . . . . . . . . . . . . . 1034.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1034.2 Probabilistic Model Proposed by Chen . . . . . . . . . . . . . . . . . . . . 1054.3 Correct Probabilistic Model of the ALOHA Systems . . . . . . . . . . . . 1084.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1124.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155 Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175.2 The Standard Q-algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 1205.3 The Model Proposed by Wang et al. [1] . . . . . . . . . . . . . . . . . . . 1225.4 The New Analytical Framework . . . . . . . . . . . . . . . . . . . . . . . . 1265.4.1 Expected Number of Required Queries . . . . . . . . . . . . . . . . 1295.4.2 Expected Number of Transmitted Bits . . . . . . . . . . . . . . . . 1335.4.3 Generalizing the SMC Model for Variable c . . . . . . . . . . . . . 1375.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1405.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147viiiTable of Contents6 Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2 . . 1516.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1516.2 CDMA-based Tag Identification . . . . . . . . . . . . . . . . . . . . . . . 1546.2.1 Tag Identification Procedure . . . . . . . . . . . . . . . . . . . . . 1546.2.2 Proposed Absorbing Markov Chain Model . . . . . . . . . . . . . . 1566.2.3 Expected Number of Required Queries . . . . . . . . . . . . . . . . 1626.2.4 Expected Number of Transmitted Chips . . . . . . . . . . . . . . . 1656.3 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 1656.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1687 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 1727.1 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1727.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 175Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178ixList of Tables3.1 Security comparison of the proposed protocol and the light-weight authen-tication schemes explained in Section 3.2. . . . . . . . . . . . . . . . . . . . 993.2 Complexity comparison of the proposed protocol and the light-weight au-thentication schemes explained in Section 3.2. . . . . . . . . . . . . . . . . 1004.1 Correct values of the estimated n (number of tags) for the algorithm in [2](L = 10) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114xList of Figures2.1 Binary tree walking mechanism for tag singulation. . . . . . . . . . . . . . 282.2 The empty, single and collided sections of a time frame in our analyticalmodel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.3 Two-dimensional representation of the events and decision making criterionfor tree-based RFID systems. . . . . . . . . . . . . . . . . . . . . . . . . . 452.4 Two-dimensional representation of the events and decision making criterionfor ALOHA-based RFID systems. . . . . . . . . . . . . . . . . . . . . . . 492.5 Probability of false alarm by P-BTD algorithm in a 16-bit RFID system. . 522.6 The effect of changing the number of fake tags on the probability of observingcollision in an RFID system with L = 16, N = 5, 000, b = 000000111110100,and h = 1, 000. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532.7 Average of the last detected ID before detecting the presence of a blockerversus number of fake tags F . (L = 16, N = 5, 000 and h = 1, 000) . . . . 542.8 Average of the last detected ID before detecting the presence of a blockerversus number of real tags N . (L = 16, F = 5, 000 and h = 1, 000) . . . . 552.9 Average of the last interrogated serial number versus inaccurate values of F(?5% error) in the P-BTD and threshold-based algorithms for binary treewalking RFID systems. (L = 16, N = 5, 000 and h = 1, 000) . . . . . . . . 56xiList of Figures2.10 Average of the last interrogated serial number versus inaccurate values of N(?5% error) in the P-BTD and threshold-based algorithms for binary treewalking RFID systems. (L = 16, F = 5, 000 and h = 1, 000) . . . . . . . . 572.11 The probability of false alarm by P-BTD algorithm in an ALOHA-basedRFID system. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582.12 Average number of the required queries for different values of p in the P-BTDand threshold-based algorithms. (N = 500, h = 1 and T = 21) . . . . . . . 592.13 Average number of the required queries for different values of N in theP-BTD and threshold-based algorithms. (p = 0.7, h = 1 and T = 21) . . . 602.14 Average number of the required queries with inaccurate values of p (?0.05error) in the P-BTD and threshold-based algorithms. (N = 500, h = 1 andT = 21) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612.15 Average number of the required queries with inaccurate values of N (?5%error) in the P-BTD and threshold-based algorithms. (p = 0.7, h = 1 andT = 21) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.1 The standard EPC Gen-2 protocol [3, 4]. . . . . . . . . . . . . . . . . . . . 673.2 The RFID protocol proposed by Henrici and Mu?ller [5]. . . . . . . . . . . . 693.3 The challenge-response trigger protocol proposed by Lim et al. [6]. . . . . . 713.4 The forward rolling trigger protocol proposed by Lim et al. [6]. . . . . . . . 723.5 The server-less protocol proposed by Tan et al. [7]. . . . . . . . . . . . . . 743.6 The Gen-2+ protocol proposed by Sun et al. [4]. . . . . . . . . . . . . . . . 763.7 The proposed light-weight authentication protocol for RFID communications. 934.1 The empty, single and collided sections of a time frame in the analyticalmodel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109xiiList of Figures4.2 A posteriori probability distributions using Eq. (4.5) from [2], Eq. (4.18),and the actual probabilities for a simulated RFID system. . . . . . . . . . 1135.1 The adaptive Q-algorithm used by EPC Gen-2 [3]. . . . . . . . . . . . . . . 1225.2 Our proposed SMC model. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1275.3 Generalized form of the SMC model for variable c. . . . . . . . . . . . . . . 1395.4 The expected number of required queries q for detecting all the tags vs. thenumber of tags in the system (c = 0.2). . . . . . . . . . . . . . . . . . . . . 1405.5 Difference between the q calculated using the FMC and SMC models andthe qsim obtained from the simulated RFID system (c = 0.2). . . . . . . . . 1415.6 The expected number of transmitted bits TB needed for detecting all tagsvs. the number of tags in the system (c = 0.2). . . . . . . . . . . . . . . . . 1425.7 Difference between the TB calculated using the FMC and SMC models andthe TBsim obtained from the simulated RFID system (c = 0.2). . . . . . . 1435.8 The expected number of required queries q for detecting all the tags vs. thenumber of tags in the system (c = 0.4). . . . . . . . . . . . . . . . . . . . . 1455.9 Difference between the q calculated using the FMC and SMC models andthe qsim obtained from the simulated RFID system (c = 0.4). . . . . . . . . 1465.10 The expected number of transmitted bits TB needed for detecting all thetags vs. the number of tags in the system (c = 0.4). . . . . . . . . . . . . . 1475.11 Difference between the TB calculated using the FMC and SMC models andthe TBsim obtained from the simulated RFID system (c = 0.4). . . . . . . 1485.12 The expected number of required queries q for detecting all the tags vs. thenumber of tags in the system with the variable c shown by Eq. (5.39). . . 149xiiiList of Figures5.13 The expected number of transmitted bits TB needed for detecting all thetags vs. the number of tags in the system with the variable c shown byEq. (5.39). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1506.1 The CDMA technique, the bit and the chip concepts we used for RFIDsystems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1566.2 Our Proposed Markov chain model for the CDMA system. . . . . . . . . . 1576.3 The expected number of required queries q? for detecting all tags vs. thenumber of tags in the system for both the EPC protocol (c = 0.2) and theCDMA-based tag identification scheme (l = 16, 31, 64). . . . . . . . . . . . 1666.4 The total transmitted data TD for detecting all tags vs. the number of tagsin the system for both the EPC protocol (c = 0.2) and the CDMA-basedtag identification scheme (TDEPC = TB, TDCDMA = TC, and l = 16, 31, 64).1676.5 The total transmitted data TD for detecting all tags vs. the number of tagsin the system for both the EPC protocol (c = 0.4) and the CDMA-basedtag identification scheme (l = 16, 31, 64). . . . . . . . . . . . . . . . . . . . 1696.6 The total transmitted data TD for detecting all tags vs. the number of tagsin the system for both the EPC protocol (c = 0.4) and the CDMA-basedtag identification scheme (TDEPC = TB, TDCDMA = TC, and l = 16, 31, 64).170xivList of AbbreviationsACK AcknowledgmentAES Advanced Encryption StandardCDMA Code Division Multiple AccessCRC Cyclic Redundancy CheckDFSA Dynamic Framed Slotted ALOHADMV Department of Motor VehiclesDoS Denial of ServiceDS Direct SequenceECC Elliptic Curve CryptographyEPC Electronic Product CodeETC Electronic Toll CollectionFH Frequency HoppingFMC First Markov Chain (Model)FSA Framed Slotted ALOHAHF High FrequencyHM Hybrid ModulationID Identification (Number)ISO International Organization for StandardizationLF Low FrequencyxvList of AbbreviationsMAC Medium Access ControlNS Non-SecretPA Pure ALOHAP-BTD Probabilistic Blocker Tag DetectionPN Pseudo-NoisePRNG Pseudo-Random Number GeneratorRFID Radio Frequency IdentificationRN16 Random Number (16-bit)SHA Secure Hash AlgorithmSMC Second Markov Chain (Model)SQUASH Square HashTH Time HoppingUHF Ultra High FrequencyZK Zero KnowledgexviAcknowledgmentsFirst and foremost, I would like to offer my sincerest gratitude to my supervisors, Dr.Rabab K. Ward and Dr. Ian F. Blake, for their invaluable advice, insightful guidance, andcontinuous patience. They have improved the quality of my research, analytical thinkingand presentation skills by their constructive comments, from the early stages of my researchuntil the very end. They have supported me and encouraged me throughout my PhD study.Honestly without them, this research would not be possible. I would like to thank themfor their invaluable consideration and understanding of the conditions and problems thatI was involved with as a new international student. Even in my personal life and duringthe hardest days, they have always been there by my side when I needed them and helpedme with their invaluable advice. Briefly speaking, they have truly been more than PhDsupervisors to me, and I will owe them for the rest of my life.I would like to express my gratitude to Dr. Vincent Wong for his technical commentsand advice, Dr. Robert Schober and Dr. Mehrdad Fatourechi for their invaluable helpand support, and Dr. Vahid Shah-Mansouri for his constructive suggestions and guidancethrough out my research. I would also like to thank the members of my doctoral committeefor their invaluable time and suggestions.I am also thankful to my friends, especially Armaghan Eshaghi, Vahid Shah-Mansouri,Keivan Ronasi and Sardar Malekmohammadi for their always being supportive and ac-countable. I also want to thank Ahmad, Anahita, Hamidreza, Fahimeh, Peyman, Morteza,Sergio, Mohammad, Negar, Lino, Mani, Sima, Man Hon, Ali, Hamid, Di, Saloome, Babak,xviiAcknowledgmentsHamed, Ehsan, Tanaya, Arian, Simon, Pedram and all my other friends that definitely Icannot name them all here.I would like to show my respect and express my gratitude to Dr. Mohsen Shiva andDr. Caro Lucas, former faculty members of the University of Tehran and my previousmentors who are not among us anymore. Both my academic and personal life have greatlybenefited by my scientific collaboration with Dr. Shiva and Dr. Lucas, and most of all, bytheir invaluable friendship. I will miss them for sure in the days and years to come.Lastly, and most importantly, I feel indebted to my great family, my father Ahmad, mymother Roya, and my brothers Pouyan and Hossein for their everlasting love, support, andprotectiveness not only in the past four years but also throughout my entire life. I wouldalso like to thank Mina Irani, Mahmoud, Rosa and Reza Riazi, and Abbas Tavakkoli foralways being encouraging and supportive.I am really grateful for the opportunities I was given in Canada and appreciate thehospitality and generosity of the Canadian society. This work was supported by the NaturalSciences and Engineering Research Council (NSERC) of Canada.xviiiDedicationWith love, to my mom and dad,and in memories of Dr. Mohsen Shiva... .xixChapter 1IntroductionRadio frequency identification (RFID) is a ubiquitous wireless technology which allowsobjects to be identified automatically. This technology is expected to play an importantrole in various applications such as labeling products and supply chain management, objecttracking, patients? monitoring in health care facilities and e-passports [8, 9, 10, 11]. Thereare also many other potential applications such as smart refrigerators that can recognizeexpired food packages and smart microwaves that know how long to cook a certain fooditem [12].An RFID system consists of several RFID tags and at least one RFID reader. An RFIDtag is a small electronic device with an antenna and has a unique serial identification (ID)number. An RFID reader is an electronic device which transmits and receives the radiofrequency waves used to communicate with the tags.Using RFID tags can simplify many applications and provide many benefits but at thesame time, privacy of the customers should be taken into account to prevent unwantedissues which may arise from using the new technology. Many customers are currentlyreluctant to use RFID embedded products because of the privacy issues. On the other hand,the manufacturing costs of RFID tags should be kept as low as possible (below 5-10 centsfor many applications), that itself imposes strict limitations on the hardware architectureof RFID tags. As a result, RFID tags have very limited computational capabilities andmemory, and they cannot calculate sophisticated cryptographic functions. Therefore, itis crucial to develop some strategies and protocols to improve the security and privacy of1Chapter 1. IntroductionRFID systems without imposing too much computational costs to the tags. In this thesis,we study the vulnerability issues of current RFID protocols, and try to improve the securityand privacy of communication between the tags and the reader(s) in RFID systems.One of the key aspects of every RFID system is the tag identification procedure. Findingan efficient, fast and reliable tag identification procedure has recently been the focal pointof many research programs. As a result, many tag identification techniques have beenproposed in recent years. However, the standard EPC Generation-2 protocol has stillkept its dominance over other techniques and it is widely used by industry. Although theEPC Generation-2 protocol is very efficient and literally has been accepted as the mostefficient tag identification protocol, to the best of our knowledge, no accurate analyticalmodel had been provided for it before [84]. Therefore, the only possible way to evaluatethe EPC Generation-2 protocol for different applications and to compare it with otherproposed tag identification techniques was simulating the whole RFID system, which is verytime-consuming and more importantly, only provides approximate values for the evaluatedfactors. In this thesis, we propose an accurate analytical framework for the standardEPC Generation-2 protocol. Using this analytical model, the performance of the the EPCGeneration-2 protocol can be evaluated accurately and compared with other proposed tagidentification techniques. In the next subsections, we introduce RFID systems, discusstheir security and privacy issues, explain the most popular tag identification techniques,and describe the directions of our work.1.1 Radio Frequency Identification (RFID)An RFID system consists of some objects with tags and at least one reader. Each tag is asmall electronic device with an antenna and has a unique serial identification (ID) number.An RFID tag transmits its ID (or sometimes only a portion of it) over the wireless channel2Chapter 1. Introductionin response to an interrogation or a query message from a reader. Commercial applicationsof RFID include inventory checking, supply chain management, labeling products for rapidcheckout at the counter, contactless credit cards and e-passports. In addition, there aremany other potential applications such as smart refrigerators and smart microwaves [12]. Inboth the popular press and academic circles, RFID technology has seen a swirl of attentionin recent years. One important reason for this is the effort of large organizations, such asWal-Mart, U.S. Department of Motor Vehicle (DMV), Procter and Gamble, Gillette, andthe U.S. Department of Defense, to deploy RFID as a tool for automated oversight of theirsupply chains [12, 13, 14, 15, 16].Advocates of RFID technology describe it as a successor to the optical barcode printedon consumer products, with two important advantages; unique identification and automa-tion capabilities. A barcode indicates the type of object on which it is printed, whilean RFID tag goes a step further. It emits a unique ID that distinguishes among manymillions of identically manufactured objects. The unique identifiers in RFID tags can actas pointers to a database entries containing complete transaction histories for individualitems. Moreover, being optically scanned, barcodes need direct line-of-sight contact withreaders, and thus they need careful physical positioning of scanned objects. Except inthe most rigorously controlled environments, barcode scanning requires human interven-tion. In contrast, RFID tags are readable without needing direct line-of-sight and precisepositioning. RFID readers can scan tags at rates of hundreds per second [12].The main form of a barcode-type RFID device is known as an electronic product code(EPC) tag. An organization known as EPCglobal Inc. oversees the development of thestandards for these tags [8]. EPC tags cost approximately 5 U.S. cents apiece in largequantities at present. In the quest for low cost, however, EPC tags adhere to a minimalistdesign [12]. They carry little data in the form of on-board memory. The unique ID of3Chapter 1. Introductionan EPC tag, known as an EPC code, includes information similar to that in an ordinarybarcode, but serves also as a pointer to database records for the tag. Today, an EPC codecan be up to 96 bits in length [3]. Database entries for tags, however, can have effectivelyan unlimited size.RFID tags can be categorized into passive, semi-passive and active tags [8, 12]. Passivetags do not have an on-board power source and use backscatter modulation. In other words,their transmission power is derived from the signal of the interrogating reader. Passive tagscan operate in different frequency bands. Low frequency (LF) tags operate in the 124-135kHz band and have the nominal read range of up to 0.5 m. Animal identification is oneof the widely used applications of LF tags. High frequency (HF) tags, operating at 13.56MHz, have ranges up to a meter but typically in the order of tens of centimeters. HF tagsare widely used in contactless credit cards and library tags nowadays. Ultra high frequency(UHF) tags, which operate at either 860-960 MHz (and sometimes 2.45 GHz), have a rangein the order of 10 m. Some RFID tags, on the other hand, contain batteries. There aretwo such types; semi-passive tags, whose batteries power their circuitry when interrogated,and active tags, whose batteries power their circuitry as well as their transmission. Activetags can initiate the communication with the reader, and have read ranges of 100 m ormore. Naturally, they are more expensive compared to passive tags and cost about $20 ormore [12].Different standards have been suggested so far for RFID systems such as the ISO 14443,ISO 15693, ISO 18000, ISO 18092, EPC Class-1 HF, EPC Class-0 UHF, EPC Class-1Generation-2 UHF and NFCIP-1/ECMA 340 [8, 12]. For HF and UHF RFID systems,however, the most well-known standards are the ones introduced by the EPCglobal Inc.,known as the EPC Class-1 HF and the EPC Class-1 Generation-2 UHF (briefly EPC Gen-2), respectively [17]. The EPC Class-1 HF and EPC Class-1 Gen-2 UHF have dominated4Chapter 1. Introductionthe other standards developed for passive HF and UHF tags and are widely used by industrynowadays. We study these two standards in more detail in Chapter 5.1.2 Security and Privacy in RFID SystemsUsing RFID tags can simplify many applications and provide many benefits but at thesame time, the privacy of customers should be taken into account to prevent undesirableissues which may arise from using the new technology. Many customers are reluctant touse RFID embedded products because of the privacy issues. Some users are concernedthat while carrying items (e.g., clothes, medicine, currency) embedded with RFID tags,they can be tracked by nearby readers. In that case, consumer privacy may be violated.In addition to tracking individuals, RFID tags may also be used to extract unauthorizedcritical and personal information [12]. Moreover, RFID tags may be used by some maliciousorganizations and dealers to sell fake RFID embedded items and forge them as valuablereal items [12, 18]. Denial of service is another type of problem which can be caused byattackers to interrupt an RFID-based system [19, 20]. Moreover, some specific applicationsdemand special considerations if the RFID technology is supposed to be used for them.As an example, Molnar and Wagner discussed the issues which should be considered forRFID-based libraries [21]. Juels and Pappu explained the security issues for using RFIDtechnology in RFID-enabled banknotes [22]. Xiao et al. discussed the security concernsthat need to be noted in RFID-based telemedicine systems [23]. Some noticeable worksare also devoted to the security issues of RFID-based e-passports include [9, 24, 25].In order to cope with the security issues of RFID systems, various schemes have beenproposed. These solutions can be divided into two general groups; the group of solutionsthat use cryptography to provide the required security and privacy, and the group of solu-tions that use approaches other than cryptography. The cryptographic solutions for RFID5Chapter 1. Introductionsecurity and privacy issues can themselves be divided into two main groups; light-weightauthentication protocols and complex cryptographic protocols. Most RFID researchersbelieve that the industry needs simple and low cost RFID tags (below 5 cents per item)with limited number of logical gates. Many approaches have been suggested which havebeen designed based on the light-weight authentication to address the security and privacyissues of RFID systems while keeping the computational cost and the manufacturing priceof RFID tags as low as possible [4, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38]. On theother hand, some other researchers believe that it is possible (or at least feasible) to usemore complex cryptographic protocols in future RFID tags. They suggest the use of pub-lic key solutions such as elliptic curve cryptography (ECC) [39, 40, 41, 42] and advancedencryption standard (AES) [43] to address the security issues of RFID systems. The pub-lic key cryptography refers to a cryptographic system requiring two separate keys, one ofwhich is secret and the other one is public. Although the secret and public keys are differ-ent, they are mathematically linked. The public key is used to encrypt the plain-text, andthe secret one is used to decrypt the cipher-text. Few approaches also exist which cannotbe fitted into the cryptographic solutions. For instance, Holcomb et al. suggested to takeadvantage of the power-up static random access memory (SRAM) state as an identifyingfingerprinting tool to solve the security problems of RFID tags [44]. Some researchersalso proposed to use blocking, jamming and physical solutions for the RFID security andprivacy issues [20, 45, 46, 47].1.3 Tag Singulation TechniquesIn an RFID system with a reader and several tags, the reader and the tags share the samewireless channel. Therefore, tag-to-tag collision can occur when multiple tags transmit sig-nals simultaneously to the reader. This prevents the reader from successfully identifying6Chapter 1. Introductionany tag. Thus, the reader and the tags need to use a technique that enables the readerto communicate with the conflicting tags one at a time. Such a technique, known as thesingulation technique, enables the reader to talk to each tag singly. Various tag singulationtechniques have been proposed in [48, 49, 50, 51, 52, 53, 54, 55, 56, 56, 57, 58, 59, 60,61, 62, 63, 64, 65, 66, 67] to prevent tag-to-tag collisions. An efficient tag singulationscheme has also been standardized recently by the EPCglobal Inc. [3]. Although manytechniques have been proposed to prevent tag-to-tag collisions, most of these techniquescan be categorized into three main classes; the tree-based, ALOHA-based and code divisionmultiple access (CDMA)-based tag singulation techniques. The tree-based techniques pro-vide a deterministic way to identify all tags in the system while the ALOHA-based andthe CDMA-based techniques are probabilistic. In the following subsections, we introducethese three classes in more detail.1.3.1 Tree-based TechniquesThe tree-based singulation techniques have been suggested by many researchers for UHFpassive tags [8, 14, 45, 57, 59]. This class of singulation techniques use a deterministicapproach to identify the tags in an RFID system. We have two forms of tree-based singu-lation techniques; the binary tree walking and the query tree techniques. Among the abovetwo techniques, the binary tree walking has played a more important role compared to thequery tree technique in RFID applications. It was also proposed as the main anti-collisionstrategy used in the EPC Class-0 UHF standard. The EPC Class-0 UHF standard wasdeveloped by the Auto ID lab at MIT for passive tags operating in the 915 MHz band.In the binary tree walking tag singulation, the reader divides the tags present at itsreading range into two groups based on their IDs. The reader further divides each of thesetwo groups into two smaller groups and continues this procedure until each group only7Chapter 1. Introductioncontains a single tag. This dividing process is continued in a group until all the tags inthat group are identified by the reader. After finding all tags in a group, the reader repeatsthis procedure for the other group and the whole tree walking process continues until alltags in the system are successfully identified by the reader. Binary tree walking can beillustrated as a process of creating and searching a tree where a node in the tree represents areader?s query. When a reader queries the tags in its vicinity using a tree-based technique,three scenarios may happen. If only one tag replies to the reader?s query, the reader cansuccessfully identify that tag. This is called a singly replied query. If more than one tagreplies to the reader?s query, collision happens and the reader cannot identify the replyingtags. This is called a collided query. In the third scenario, called the idle query, no tagreplies to the reader?s query. In the binary tree walking method, a tree is constructedwhen the singulation process is done. A leaf node in the tree corresponds to either a singlyreplied or an idle query, and an intermediate node represents a collided query. In binarytree walking, the reader transmits a query to the tags containing the prefixes of the tagIDs. Every tag within the reading range of the reader compares the prefix in the reader?squery with its ID and transmits its ID to the reader if the ID has the same prefix as the onesent by the reader. In this technique, all tags in a queried group transmit their IDs whilethe rest of the tags remain silent and wait for the next query of the reader. The contentof a query is the ID of each group. The reader repeats dividing the tags into two smallergroups until it detects a single tag and receives its ID. In this technique, the searchingtree is formed based on the tag IDs. When a collision occurs, the reader makes the prefixsent to the tags one bit longer by concatenating it with 0 and 1, and repeats the queryagain with the concatenated prefix. For example, assume that the reader queries with the00101101 prefix and a collision happens. This means that at least two tags exist that havethe 00101101 prefix in their IDs. The reader concatenates a 0 to the prefix and queries8Chapter 1. Introductionthe tags with the prefix 001011010 again. This procedure continues until all tags in thesystem are identified successfully by the reader. If an idle query happens, it means thereis no tag in the system with the prefix 00101101, and the reader checks the other groupwhich has a different prefix.The query tree singulation technique, on the other hand, uses a different trick to solvethe collision problem. It takes advantage of random binary sequences generated by collidingtags for the splitting procedure. In this technique, each tag has a counter initialized to 0at the beginning of the singulation procedure. The tag transmits its ID when the counteris 0, and remains silent when the counter is 1. Therefore, all tags transmit their IDsconcurrently at the beginning of the singulation procedure. The reader then transmits afeedback to inform the tags whether or not a collision has happened. According to thereader?s feedback, all the tags change their counter values. If a collision has happened,the tags which were involved in the collision (i.e., their counter value were 0 at the timeof collision) randomly select new binary values for their counters. On the other hand,the tags which were not involved in the collision (i.e., their counter value was 1 whencollision happened) change their counter value to 0. When the reader?s feedback indicatesno collision, all tags toggle their counter values. The tags which have been successfullyidentified by the reader during the previous queries become silent and do not transmit anysignal until the ongoing singulation procedure is terminated. The reader has a counter aswell, which is used to terminate the singulation procedure. It initializes the counter valueto 0 at the beginning of the singulation procedure. After each query, if a tag collisionhappens, the reader adds 1 to its counter value, otherwise, it decreases its counter value by1. When the counter value becomes negative (<0) the reader terminates the singulationprocedure.Although the query tree method is very similar to the binary tree walking technique9Chapter 1. Introductionin terms of the efficiency of identifying the tag IDs in the system, the binary tree walkingmethod has been the dominant singulation technique in the class of tree-based singulationtechniques. It has also been suggested as the anti-collision technique by the EPC Class-0standard. Therefore, we are more concerned about the binary tree walking technique andstudy it in more detail in Chapter 2.1.3.2 ALOHA-based TechniquesIn RFID literature, ALOHA-based tag singulation techniques are also known as the proba-bilistic anti-collision schemes. The reason is that when the reader queries the tags presentin its vicinity, each tag ID can be successfully detected by a probability less than one.In the ALOHA-based protocols, the communication channel is divided into time intervalscalled frames, and each frame consists of a number of time slots [8]. The duration of eachtime slot is equal to the time needed for transmitting a tag ID [68]. At the beginning ofthe singulation procedure, the reader sends a query message containing the length of theframe (or equivalently, the number of time slots in that frame) available to all tags in thesystem and waits for them to reply and send their tag IDs during these time slots. Eachtag randomly selects a time slot, and transmits its ID during that slot. When all tagstransmit their IDs, three scenario may happen for each time slot in the frame. If a timeslot is not selected by any tag, it is called an empty slot and contains no information. Thereader can successfully read the content (tag ID) of a time slot if one and only one tagselects that slot. This kind of time slot is called a singly occupied slot. Finally, if a timeslot is selected by more than one tag, it is called a collided time slot and its informationcannot be used by the reader. After each query, the tags that were successfully identifiedbecome silent, and the tags which were involved in collisions continue to select a time slotat random and send their IDs during the next queries. This singulation technique is called10Chapter 1. Introductionframed slotted ALOHA[53]. Framed slotted ALOHA has been used as the main singulationtechnique for the LF RFID systems. A special form of the framed slotted ALOHA has alsobeen suggested by the EPC Class-1 HF and the EPC Class-1 Gen-2 UHF standards.The performance of ALOHA-based protocols is highly affected by the frame size. If thenumber of unidentified tags in the system is much larger than the number of available timeslots in a frame, too many collisions happen and very few tag IDs are detected. On theother hand, if the number of available time slots in a frame is much larger than the numberof unidentified tags, too many time slots are wasted and the efficiency of the ALOHA-basedsingulation technique decreases. Therefore, it is very important to choose the number ofavailable time slots in each frame wisely if we want to increase the efficiency of ALOHA-based protocols. To do this, a new class of ALOHA-based techniques have been proposed inwhich the length of the frames can be dynamically changed by the reader [69, 70, 71]. Thesetechniques are referred to as dynamic framed slotted ALOHA. In dynamic framed slottedALOHA, the reader changes the number of time slots dynamically based on the numberof empty, single and collided time slots in the previous query. The reader decreases thenumber of time slots if too many slots remained empty in the previous query, and increasesthe number of time slots in the frame if too many collisions happened in the previous query.Different methods have been suggested for optimizing the frame length and adjustingthe number of time slots in each query. Most of the dynamic framed slotted ALOHAschemes operate based on estimating the number of tags in the RFID systems [2, 70, 72,73, 74, 75]. Recently, a new adaptive dynamic framed slotted ALOHA technique has alsobeen proposed and standardized by the EPCglobal Inc. for the EPC Class-1 HF and theEPC Class-1 Gen-2 UHF RFID systems [1, 3, 76]. This new technique has dominated otherALOHA-based tag singulation techniques and it is widely used by industry for differentRFID applications. In this tag singulation method, the reader changes the number of time11Chapter 1. Introductionslots at each query based on an adaptive algorithm called the Q-algorithm. In the firstquery, the reader provides 16 time slots to the tags (numbered from 0 to 15) and asksthem to choose one of these 16 time slots at random. After doing so, only the tags thathave chosen the 0 time slot are allowed to transmit their IDs and the rest of the tags areforced to remain silent and wait for the next query. If only one tag chooses the 0 timeslot, the reader can successfully read its ID, but if more than one tag choose the 0 timeslot, a collision happens and the reader cannot read the transmitted tag IDs. Based onthe status of the 0 time slot (which can be empty, singly occupied or collided), the Q-algorithm decides whether to increase or decrease the frame length for the next query orto keep it unchanged. In this method, the number of time slots can be changed from 0 to215 ? 1 (32768 time slots in total) by the Q-algorithm based on the status of the 0 timeslot. The reader continues sending queries and reading the content of the first time slotuntil it successfully identifies all the tags in the system. We will study the dynamic framedslotted ALOHA technique suggested by the EPC Class-1 HF and the EPC Class-1 Gen-2UHF standards in more detail in Chapter 5. We also show how this method outperformsother singulation techniques in terms of the number of queries and the total number oftransmitted bits needed to identify all tags in the system.1.3.3 CDMA-based TechniquesThe origins of CDMA are in military and navigation systems. Techniques developed tocounteract intentional jamming and eavesdropping have also proved suitable for multi-usercommunication systems [77]. Recently, some researchers have suggested to replace thecurrent dynamic framed slotted ALOHA technique used by the EPC Class-1 HF and theEPC Class-1 Gen-2 UHF standards with the CDMA technique [56, 60, 61, 62, 63, 64,65, 66, 67]. In CDMA-based RFID systems, each tag is assigned a unique code sequence12Chapter 1. Introductioncalled the spreading code (or a pool of spreading codes to choose from). Each tag usesthis spreading code to encode its tag ID. The ratio of the transmitted bandwidth to theinformation bandwidth is called the processing gain of the CDMA system. By knowingall the spreading codes, the reader decodes the received information and recovers thetransmitted tag ID. This is possible since the cross-correlations between the spreadingcodes are zero or very small. Since the bandwidth of the spreading codes are chosen tobe much larger than the information-bearing signal, the CDMA process enlarges (spreads)the spectrum of the transmitted signal. Therefore, the CDMA technique is also known asa spread spectrum multiple access (SSMA) technique [78].There are a number of modulation techniques that can be used to generate the spreadspectrum signals. The most important techniques are? Direct sequence CDMA (DS-CDMA): In this technique, the infirmation-bearing sig-nal is directly multiplied by a high chip rate spreading code.? Frequency hopping CDMA (FH-CDMA): In this technique, the carrier frequency ofthe infirmation-bearing signal is rapidly changed according to the spreading code.? Time hopping CDMA (TH-CDMA): In this technique, the information-bearing signalis not transmitted continuously, instead, the signal is transmitted in short burstswhere the times of the bursts are decided by the spreading code.? Hybrid modulation CDMA (HM-CDMA): If two or more of the above mentionedspread spectrum techniques are used together to modulate the spread signal, it iscalled the hybrid modulation spread spectrum technique [77].Since passive RFID tags are very limited in hardware structure, it is not easy to imple-ment FH-CDMA or TH-CDMA capabilities on them without increasing the total manufac-turing costs. Therefore, among the above mentioned modulation techniques, DS-CDMA13Chapter 1. Introductionhas been suggested the most for RFID systems [56, 60, 62, 63, 65, 66].The CDMA technique provides several useful features for RFID systems such as? Multiple access capability : Assuming that multiple tags transmits their IDs usingthe CDMA technique at the same time, the reader is still capable of distinguishingbetween the tags and recovering their IDs correctly if the spreading codes used bythe transmitting tags have sufficiently low cross-correlation with each other. Thereader correlates the received signal with the spreading codes used by the tags in thesystem one by one to de-spread and recover their signals [77].? Protecting against multi-path interference: In the real RFID applications, there mightbe more than one path between the transmitting tag and the reader (for examplein a large warehouse with thousands of RFID embedded merchandises). Therefore,multiple copies of the transmitted signal might be received by the reader due toreflections and refractions. The received signals have different amplitudes, phases,delays and arrival angles. Adding these signals by the reader can be constructiveat some frequencies and destructive at some other frequencies, which results in adispersed signal in the time domain. The CDMA technique can decrease the issuesthat arise from multi-path interferences and improve the performance of the system[77, 78].? Increasing the privacy : Using the CDMA technique, the transmitted signals can bede-spread and the tag IDs can be read only if the spreading codes are known. Thisfeature increases the privacy of the RFID system by preventing random eavesdroppersand illegitimate readers from identifying the tags in the system [77].? Interference reduction: Assuming that there exists a narrow-band interfering signalin the environment, the cross-correlation of the spreading codes with the narrow-14Chapter 1. Introductionband interference in the reader spreads the power of the interference, which resultsin reducing the interfering power in the information band-width, and makes it easierfor the reader to recover the tag IDs [77].Among the above mentioned advantages of using the CDMA technique, its multipleaccess capability is the most desired one for RFID systems. Using this idea, it has beensuggested to provide several spreading codes for the tags in an RFID system. The tagsuse these codes to spread (encode) their IDs, and then send their coded IDs to the reader.Using the CDMA technique, multiple tags can be simultaneously read in each query andthus the number of collisions is reduced.Although using the CDMA technique can reduce the number of collisions and increasethe number of identified tags at each query, the assumption that it speeds-up the wholetag identification procedure may not necessarily be true. In Chapter 6, we will study theuse of the CDMA technique for RFID systems in more detail and investigate the efficiencyof the tag identification procedure using the CDMA technique.1.4 Contributions and ResultsThis thesis aims to cover two important and challenging aspects of RFID systems. Thefirst area is the security and privacy in RFID systems, and the second one is the efficiencyof RFID protocols. In the first half of the thesis, we focus on security and privacy issuesof RFID systems. In the second half of the thesis, we focus on analytical modeling andperformance evaluation of the state of the art tag singulation schemes. Chapters 2 and3 address the security and privacy in RFID systems, and Chapters 4 to 6 address theanalytical modeling and performance evaluation of the main tag identification schemes.The contributions of this thesis are as follows.15Chapter 1. Introduction? We first study the blocking attack against RFID systems operating based on thebinary tree walking tag singulation mechanism. Using blocker tags was originallysuggested as a solution for the privacy issues of RFID systems. A blocker tag cansimulate all or a portion of the tag IDs in the system and avoid undesired interroga-tions. However, it was revealed later that blocker tags can also be used by maliciousattackers to interrupt or mislead the normal operation of RFID systems in largechain stores and warehouses. This attack, called the blocking attack, is very hard todetect automatically in large RFID systems with thousands of tags. We mathemat-ically model the blocker attack for RFID systems that operate based on the binarytree walking singulation mechanism. Using the developed analytical framework, wepropose a probabilistic blocker tag detection (P-BTD) algorithm to detect the pres-ence of an attacker in RFID systems operating based on the binary tree walkingmechanism. The proposed P-BTD algorithm can detect the existence of a blockertag using the information extracted from the interrogations performed by the reader.Simulation results show that the proposed algorithm has a better performance thanthe threshold-based detection algorithm in terms of the number of required interro-gations. We also study the blocking attack against RFID systems operating basedon the ALOHA tag singulation mechanism. Same as RFID systems which use thebinary tree walking for tag singulation, ALOHA-based RFID systems are also vulner-able to the blocking attack. An attacker may disrupt ALOHA-based RFID systemsby sending fake IDs to the randomly selected time slots in each frame. The blockercauses the reader to detect some fake tags by sending some fake IDs to the slotswhich would have remained empty in a normal (unattacked) system. Moreover, theblocking attack reduces the efficiency of the tag identification procedure in ALOHA-based RFID systems drastically. Based on the above, we need to find an efficient way16Chapter 1. Introductionto make sure that there is no attacker in the system and to prevent the reader frombeing involved in a loop of endless (or useless) interrogations. We mathematicallymodel the ALOHA-based RFID systems and find the probabilities that the readerobserves a specific frame structure in the presence and absence of a blocker tag. Usingthe analytical framework developed, we propose a probabilistic blocker tag detection(P-BTD) algorithm for ALOHA-based RFID systems. Simulation results show thatour proposed algorithm has a better performance compared to the threshold-baseddetection algorithm in terms of the number of required interrogations. This work hasbeen published in [20, 79, 80].? We consider the use of light-weight authentication protocols for increasing the se-curity and privacy of RFID systems. Using the light-weight authentication has theadvantage of keeping the computational demand and the price of RFID tags very lowwhile increasing the security and privacy in RFID systems. For this reason, light-weight authentication protocols have been of interest to both industry and academia.We perform the security analysis of the standard EPC Gen-2 protocol. We also per-form the security analysis of five other light-weight authentication protocols proposedin [4, 5, 6, 7], and show how they can be broken by some simple tricks. We then pro-pose a new light-weight authentication protocol that takes the hardware limitationsand the manufacturing costs of RFID tags into consideration. The security of theproposed protocol and its complexity are compared with [4, 5, 6, 7]. We show thatour proposed method improves the level of security and privacy by paying attentionto the vulnerabilities of the protocols proposed in [4, 5, 6, 7]. Part of this work hasbeen published in [81] and the rest has been submitted to [82].? We propose a new probabilistic tag estimation method for ALOHA-based RFID sys-tems. For many RFID applications, we need to know or calculate the number of tags17Chapter 1. Introductionpresent in the RFID system at any time. Many tag estimation methods have beenproposed to calculate the number of tags in the system. In [2], a probabilistic tagestimation method was proposed for ALOHA-based RFID systems. In this method,the reader estimates the number of remaining tags in the RFID system after eachinterrogation based on a posteriori probability, and uses this estimated number todetermine the number of required time slots for the next interrogation. This ap-proach can improve the performance of the ALOHA-based anti-collision algorithms.However, there exists a mathematical error in the probabilistic modeling of the prob-lem. We address this problem and provide the correct probabilistic model and thecorrect tag estimation method for ALOHA-based RFID systems. This work has beenpublished in [83].? We investigate the standard EPC Gen-2 protocol and model it as an absorbingMarkov chain. We formulate the proposed model and derive the expected num-ber of queries required by the EPC Gen-2 protocol to identify all tags in an RFIDsystem. We also derive the expected number of transmitted bits for the EPC Gen-2protocol. These formulae allow us to provide a measure of the speed of the EPCGen-2 protocol in identifying all tags in the system and the amount of data thatshould be transferred during this process. Moreover, the proposed model enables usto compare the performance of the EPC Gen-2 protocol with other schemes usingthe accurate formulation provided. Extensive simulations validate and confirm theaccuracy of our proposed analytical model. Without this model, one has to run simu-lations and average the results to obtain the expected number of required queries andthe expected number of transmitted bits. Using the analytical formulation providedby this model, there is no need to rely on simulations for studying the behavior of theEPC Gen-2 protocol, i.e., we are able to calculate the number of required queries and18Chapter 1. Introductionthe number of transmitted bits directly. Our proposed analytical model is also usefulin studying and comparing other RFID protocols, and in deploying better protocolsfor RFID systems. Part of this work has been published in [84] and the rest has beensubmitted to [85].? We investigate the CDMA-based RFID systems and model them as an absorbingMarkov chain. Recently, some researchers have suggested to replace the dynamicframed slotted ALOHA technique used in the standard EPC Gen-2 protocol with theCDMA technique to reduce the number of collisions that happen and to improve thetag identification procedure. We model the CDMA-based tag identification process asan absorbing Markov chain, and derive the analytical formulae for the average numberof queries required and the total transmitted data needed to identify all tags in anRFID system using the CDMA technique. Taking advantage of the proposed Markovchain and the one we proposed before for the standard EPC Gen-2 protocol, wecompare the two tag identification protocols and show that the standard EPC Gen-2protocol outperforms the CDMA-based scheme in terms of the total transmitted dataand the average time needed to identify all tags in the system. This work has beensubmitted to [86].1.5 Thesis OrganizationThe rest of the thesis is organized as follows. In Chapter 2, we study the blocking attack inRFID systems that operate based on the binary tree walking tag singulation mechanism.We develop an analytical model for the blocking attack against the binary tree walking tagsingulation mechanism. Using this analytical model, we propose a probabilistic blocker tagdetection algorithm (P-BTD) to detect the presence of an attacker in this type of RFID19Chapter 1. Introductionsystems. In the next step, we focus on RFID systems that operate based on the ALOHA tagsingulation mechanism and study the blocking attack against this type of RFID systems.We develop an analytical model for the blocking attack against the ALOHA tag singulationmechanism. Using this analytical model, we propose a probabilistic blocker tag detectionalgorithm (P-BTD) to detect the presence of an attacker in ALOHA-based RFID systems.In Chapter 3, we investigate the security and privacy issues of the standard EPC Gen-2 protocol, and study the use of light-weight authentication protocols for increasing thesecurity and privacy in RFID systems. After investigating the EPC Gen-2 protocol, weperform a security analysis of five light-weight authentication protocols suggested in [4, 5,6, 7] and show their vulnerabilities. Using this security analysis, we propose a new light-weight authentication protocol which improves the level of the security and privacy inRFID systems and at the same time considers and complies with the hardware limitationsof passive RFID tags. In Chapter 4, we study the probabilistic tag estimation methodproposed in [2] for ALOHA-based RFID systems. In this method, the reader estimatesthe number of RFID tags in the system after each interrogation based on a posterioriprobability and uses this estimated number to determine the number of required time slotsfor the next interrogation. We show that there exists an analytical error in the probabilisticmodeling of [2]. We address this problem and provide the correct probabilistic model andthe correct tag estimation method for ALOHA-based RFID systems. In Chapter 5, westudy the Q-algorithm and the tag singulation protocol used in the EPC Gen-2 standard.We model the tag singulation protocol used in the EPC Gen-2 standard as an absorbingMarkov chain. Using this Markov model, we derive the analytical formulas for the expectednumber of queries and the expected number of transmitted bits needed to identify all tags inan RFID system. Extensive simulations validate and confirm the accuracy of our proposedanalytical model. In Chapter 6, we study the use of the CDMA technique for RFID20Chapter 1. Introductionsystems. The CDMA technique has been suggested by many researchers in recent years toincrease the efficiency of the tag singulation procedure. We model the CDMA-based tagsingulation protocol as an absorbing Markov chain. Based on this Markov model, we derivethe analytical formulae for the expected number of queries and the total transmitted dataneeded to identify all tags in a CDMA-based RFID system. Using the analytical formulaein Chapters 5 and 6, we compare the efficiency of the EPC Gen-2 and the CDMA-basedtag singulation protocols, and show that using the CDMA technique does not necessarilyimprove the efficiency of the tag singulation process. Finally, Chapter 7 contains discussionof the main results, conclusions, and suggesting future research directions. Each of themain chapters in this thesis is self-contained and included in separate journal articles orconference papers. The notations are defined separately for each chapter. A review of therelated work is given for each chapter accordingly.21Chapter 2Probabilistic Analysis of BlockingAttack in RFID Systems2.1 IntroductionFor pervasive deployment of RFID systems, one issue which causes the public concernis privacy. Some customers are concerned about being tracked by other readers whencarrying items (such as clothes, medicine or currency) embedded with RFID tags. In addi-tion to tracking individuals, RFID tags may also be used to extract personal informationsuch as the type of clothes somebody wears, the specific brands that an individual is in-terested in, or some medical information about the patient carrying an RFID-embeddedcontainer of medicine [12]. RFID tags may also be used by some malicious organizationsor dealers that sell illegally copied items (embedded with fake RFID tags) and forge themas valuable items [12, 18]. Denial of service is another type of problem which can becaused by attackers whose aim is to disrupt an RFID-based system [19, 45, 79]. Moreover,some specific RFID applications demand specific considerations. As an example, Molnarand Wagner discussed the issues that should be considered for RFID-based libraries [21].Juels and Pappu explained the security issues concerning the use of RFID technology inRFID-enabled banknotes [22]. Xiao et al. discussed the security concerns of RFID-basedtelemedicine systems [23]. Ma et al. studied the security issues of RFID-based toll sys-tems [15]. Some noticeable work has also been devoted to security issues of RFID-based22Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemse-passports [9, 24, 25].In order to cope with security issues in RFID systems, various schemes have beenproposed. These solutions can be divided into two general groups. The first group usesblocking, jamming and physical solutions to increase the security and privacy of RFIDsystems [45, 46, 47]. The other group uses cryptography to provide the security andprivacy in RFID systems. Cryptographic solutions for RFID systems can themselves bedivided into two main groups, light-weight and complex cryptographic solutions. MostRFID researchers believe that the industry needs simple and low cost RFID tags (below 5cents per item) with limited number of logical gates. For this case, many approaches thatare based on the light-weight cryptographic solutions and protocols have been suggested[30, 31, 32, 33, 34, 35, 36, 37, 38]. Light-weight cryptographic solutions have the advantageof keeping the computational demand and the price of RFID tags low. On the other hand,some researchers believe that it is possible to use more complex cryptographic protocolsin future RFID tags. They suggest the use of public key solutions such as elliptic curvecryptography (ECC) [39, 40, 41, 42] and the advanced encryption standard (AES) [43].A few approaches that cannot be categorized into these two main groups have also beenproposed. For instance, Holcomb et al. have suggested the employment of the power-upstatic random access memory (SRAM) state as an identifying fingerprinting tool to solvethe security problems of RFID tags [44].Among the different solutions suggested for RFID security issues, one approach relieson the use of a blocker tag. A blocker tag is a cheap passive RFID device that can simulatemany ordinary RFID tags simultaneously. When carried by a consumer, a blocker tagthus ?blocks? RFID readers [45]. This approach has attracted much attention from bothindustrial and academic communities because of its simplicity and ease of implementation.This makes it an appropriate and inexpensive candidate for many future RFID applications.23Chapter 2. Probabilistic Analysis of Blocking Attack in RFID SystemsIn the blocker solution, when a blocker tag receives a query message from a reader, it canreply with some fake IDs to prevent the reader from successfully identifying the neighboringreal tags by keeping the reader busy. This approach addresses the case where the tags arenot removed from the sold items. When the customer goes to the checkout counter andpays for the merchandises, he/she receives a bag with a blocker tag inside it. Wheninterrogated by a reader, this blocker tag generates and broadcasts fake serial numbers inresponse. The customer puts all the purchased items along with the blocker tag in a bagand leaves the store. On his/her way to home, the customer cannot be tracked successfullyby any reader because of the blocker tag. Moreover, when the customer arrives home andbrings the purchased items out of the bag, the originally attached RFID tags can be usedagain. For example, the customer can put a pack of food equipped with an RFID tag inan intelligent microwave and the microwave starts cooking the contained material basedon the instructions kept by the tag [12]. A blocker tag is very similar to ordinary tags, andtherefore, its price is acceptable (almost the same as ordinary tags) [19, 45]. This makesthe blocker tag an ideal candidate and an economic solution for addressing the securityconcerns of many RFID applications.The blocker tag approach, however, can itself introduce a different type of threat tothe system. A malicious attacker can launch a blocking attack in a store or warehouseby placing a blocker tag inside that store. In this case, the blocker tag generates andbroadcasts numerous serial numbers so as to mislead the legitimate reader and force thesystem to be engaged in time consuming and useless interrogation sequences. On the otherhand, blocker tags are inexpensive, easy to implement, and they can solve the tracking andimpersonation problems in passive RFID tags effectively. Briefly, the blocker tag solutioncould have played a significant role, probably as the best possible solution for many RFIDapplications, if the RFID users were not worried about the blocking attack. To detect the24Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsblocker tag attack, an approach based on a pre-determined threshold can be used [45]. Thisapproach, however, is computationally demanding (time-consuming) and could hinder theefficiency of the system. The motivation of our work is to design a lower layer algorithmthat can detect the presence of blocker tags in passive RFID systems in a timely manner.The contributions of this chapter are as follows:? We mathematically analyze the interrogation process of RFID systems which use thebinary tree walking or ALOHA singulation mechanisms.? To investigate the behavior of an RFID system in the presence of a blocker tag, wemathematically model the blocker attack problem using the information extractedfrom the queries performed by the reader.? We propose a probabilistic blocker tag detection (P-BTD) algorithm to detect thepresence of blocker tags in RFID systems.? We determine the probability of false alarm for the P-BTD algorithm via simulations.The simulation results also show that our proposed P-BTD algorithm has better per-formance than the threshold-based detection algorithm in terms of having a shortertime (or needing fewer queries) to detect the presence of a blocker tag.The rest of this chapter is organized as follows: In Section 2.2, we present the systemmodel and problem formulation for RFID systems that operate based on the binary treewalking and ALOHA singulation mechanisms. In Section 2.3, we propose two P-BTD algo-rithms for detecting the presence of blocker tags in binary tree walking and ALOHA-basedRFID systems. The performance comparison between our proposed P-BTD algorithmsand the thresholding algorithms suggested in [45] is presented in Section 2.4. The chapteris summarized in Section 2.5.25Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems2.2 System Model and Problem FormulationIn Section 2.2.1, we explain the system models for RFID systems that operate based onthe binary tree walking and ALOHA tag singulation mechanisms. We also explain theblocking attack in binary tree walking and ALOHA tag singulation mechanisms. In thenext step, we provide two probabilistic models for the binary tree walking and ALOHAsingulation mechanisms in Section 2.3.2.2.1 System ModelBecause of the shared nature of the wireless channel in RFID systems, an RFID readercannot communicate with more than a single tag at a time. If more than one tag respondsto a query by the reader (for example, in Walmart?s automated checkout gate), the readerdetects a ?collision? and will not be able to read the tag IDs transmitted by the tagsaccurately. Thus, the reader and the tags need to engage in a protocol that enables thereader to communicate with the nearby tags one at a time. Such a protocol is called asingulation protocol, and enables the reader to talk to each tag singly (one by one) [45].Most of these singulation protocols can generally be classified into tree-based or ALOHA-based algorithms [48]. The tree-based methods, such as the binary tree walking and thequery tree mechanisms, continuously divide a set of tags into two subsets until each subsethas only one tag [45, 49, 51, 67, 87, 88]. Then, each tag ID can be obtained successfully bythe reader. In the ALOHA-based mechanisms such as the dynamic frame-slotted ALOHA,the reader assigns a frame to all tags in the system. The frame consists of a limited numberof time slots. Each tag chooses one time slot at random and transmits its information inthat time slot [1, 53, 55, 57, 69, 73, 89, 90, 91, 92].In Sections 2.2.1.1 and 2.2.1.2, we explain the system models for the binary tree walkingand the ALOHA singulation mechanisms. The blocking attack is then discussed in Section26Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems2.2.1.3.2.2.1.1 Binary Tree Walking-based RFID SystemsThe binary tree walking technique uses a tree to represent the existing tags in an RFIDsystem. In this representation, each leaf of the tree has a unique ID. These IDs show thepossible serial numbers which can be used by the tags in the RFID system. Each existingtag has its own ID which corresponds to a leaf in the binary tree. The number of the tagspresent in the system is less than or equal to the number of leaves in the binary tree. Inother words, each tag in the system corresponds to a leaf in the binary tree but some ofthe leaves may not correspond to any tag in the system. The output of the binary treewalking algorithm yields a list of the IDs of the tags existing in the system. The tree has(L + 1) levels starting from level 0 and ending at level L, assuming that the ID of eachtag is represented by a binary number of length L bits. The node at level 0 corresponds tothe root node and does not have an address. The nodes located in levels 1 to (L? 1) arecalled the interrogation nodes. Any interrogation node at level l, where l ? {1, . . . , L? 1},can be uniquely identified by a binary prefix b whereb = b1b2 . . . bl. (2.1)Fig. 2.1 shows the binary tree corresponding to a system with four-bit IDs (i.e., L = 4).In this figure, the interrogation nodes at level l = 2 are identified using the prefixes b = 00,b = 01, b = 10 and b = 11. In the binary tree walking algorithm, the reader initiatesthe interrogations at the root of the tree. At a given interrogation node at level l withprefix b, the reader queries all the tags that correspond to the leaves of the subtree rootedat the node with prefix b. All other tags should remain silent during this phase. Thequeried tags reply to the reader by announcing the (l + 1)th bit in their serial numbers.27Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems000000 0 0 0 0 0 011 111000 111111111100000001001000110100010101100111100010011010101111001101111011110Level1234RealFake RealFake FakeFake Real RealRealFakeFigure 2.1: Binary tree walking mechanism for tag singulation.The subtree rooted at the node with prefix b is composed of two subtrees, the left andright subtrees. In response to an interrogation, at a node with prefix b, each tag broadcastsbit 0 if it lies in the left subtree and bit 1 if it lies in the right subtree. Considering thismechanism, two cases may arise. The first case is when both the left and right subtrees ofthe interrogation node have tags present. In this case, the reader observes a collision sincethe tags in the left and right subtrees transmit simultaneously. When a collision happens,the reader first moves to the child node with prefix b1b2b3 . . . bl0, i.e. the left hand side ofthe subtree. Starting from the child node with prefix b1b2b3 . . . bl0, the reader continuesits interrogation until every leaf in that subtree is covered. Then, the reader moves to thechild node with prefix b1b2b3 . . . bl1 on the right hand side of the node b to continue itsinterrogations. The second case arises when all the tags at node b reply with only a singlebit bl+1 (0 or 1), which means that they all lie in the same subtree. In that case, the readermoves to the node with prefix b1b2b3 . . . blbl+1 and ignores the other subtree. When thealgorithm reaches a leaf, the corresponding tag transmits its L-bit serial number. At the28Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsend of this procedure, the output of the binary tree walking algorithm is a list of the serialnumbers of all tags within the reader?s range [45].2.2.1.2 ALOHA-based RFID SystemsIn recent years, different mechanisms for ALOHA-based tag singulation have been sug-gested [1, 53, 55, 57, 69, 73, 89, 90, 91, 92]. In the ALOHA-based tag singulation mech-anisms, the reader interrogates all the tags and orders them to transmit their IDs in apredefined number of time slots, called a frame. At the beginning of a frame, the readersends a query message containing the frame size to the tags. Each tag randomly chooses atime slot in the frame and transmits its ID in that time slot. If a specific time slot is chosenby only one tag, then the transmission of this tag is successful and the reader is able toread its information. If more than one tag chooses a certain time slot, a collision occursand the reader is then not able to read the content of this time slot. A time slot is calledempty if no tag transmits in that slot. In the ALOHA-based singulation mechanism, thereader interrogates the tags and reads the content of the time slots having one ID (singletime slots). The reader continues this procedure repeatedly until it identifies all the exist-ing tags in the system. In each interrogation, previously identified tags are instructed toremain silent, meaning that if a tag successfully transmits its ID in one interrogation, itwill not send its ID in the next interrogations.In the ALOHA model, the reader is responsible for determining the number of requiredtime slots in each frame. If the number of time slots (in a frame) is too small compared tothe number of tags, then many collisions happen and the reader will not be able to readthe content of these collided time slots. On the other hand, if the number of time slotsis much larger than the number of tags, then the reader observes many empty time slots.This means that the communication resources are not efficiently used and the reader iswasting part of its resources. The ideal case happens when the number of assigned time29Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsslots is equal to the number of tags in the system [93]. However, the reader might notknow the number of tags and it needs to approximate this value. Different techniques havebeen introduced so far to achieve this goal and to optimize the number of required timeslots [1, 3, 53, 55, 73, 89, 90, 91, 93]. For example, Kodialam et al. have proposed that thereader estimates the number of RFID tags in the system using the number of empty timeslots in each frame and then adjusts the length of the next frame based on this estimation[93].2.2.1.3 Blocking AttackBlocker tags have originally been suggested for the purpose of protecting the privacy ofusers and preventing unauthorized readers from successfully interrogating the nearby tags.It was first designed and introduced by Juels et al. based on the binary tree walkingsingulation technique, but it is mentioned in the paper that this idea can be extended forthe ALOHA-based singulation techniques as well [45]. For RFID systems that use thebinary tree walking mechanism, the malicious blocker chooses some leaves in the binarytree at random and replies to the reader if these leaves are interrogated as explained inSection 2.2.1.1. If the leaf chosen by the blocker represents a tag which really exists inthe system, the blocker?s response does not affect the final number of detected tags by thereader. However, if the chosen leaf was originally an empty leaf, the blocker?s responsecauses the reader to assume that the leaf belongs to a real existing tag. We refer to thistag as a fake tag. For RFID systems which operate based on the ALOHA mechanism,the malicious blocker chooses some time slots at random and transmits some fake IDs inthose time slots as explained in Section 2.2.1.2. If an attacked time slot represents a real(existing) tag, the reader observes collision in that time slot and cannot read the ID ofthe real tag. If the attacked time slot does not correspond to a real tag, it is consideredas a single time slot and the reader considers its content (the fake ID) as the ID of a real30Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsexisting tag. In other words, we assume that the blocker attack does not affect collidedtime slots in a frame, but it can change an empty slot to a single slot or change a singleslot to a collided slot.It should be noted that the blocking attack is not limited to the RFID systems thatuse the blocker approach for privacy protection. Any passive RFID system that usesa singulation mechanism is also vulnerable to this attack. In other words, the blockerattack is a MAC-layer denial of service (DoS) threat that aims to prevent the readerfrom successfully interrogating the RFID tags in the system. A blocker tag can be placedin a store or warehouse by malicious attackers so as to sabotage or adversely affect theoperation of the legitimate reader. We can assume two types of blocker tags. A universalblocker tag can simulate all possible RFID tag IDs while a partial or selective blockertag can only simulate a selective range of IDs (e.g., the set of serial numbers assigned to aparticular manufacturer) [45]. Such blocker tags can be used to disrupt business operationsby shielding merchandises from the inventory control mechanism and delaying the wholeprocedure by forcing the reader to start a long sequence of useless interrogations. Theuniversal blocker attack can be detected easily using some simple algorithms, however, itis not that easy to detect the presence of a selective blocker tag in an RFID system [45].To the best of our knowledge, the main approach for detecting the presence of a blockertag is based on the use of a pre-determined threshold [45]. In this approach, the readerstops its interrogation process after completing a predefined number of interrogations, orafter detecting a specific number of tags. For instance, the reader can be programmed insuch a way that it stops interrogation after detecting (T + 1) tags, where T is the numberof existing RFID tags in the system (if it is known) or it can be a certain predefined largenumber (if the actual number of existing tags is not known). The purpose of this chapteris to develop a more efficient way for detecting the presence of a malicious blocker tag in31Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsa shorter period of time.Many large companies, such as Wal-Mart and Procter and Gamble, currently use RFIDtags to improve inventory accuracy, on-shelf availability and monitoring purposes. For in-stance, it has been estimated that only in the United States, Wal-Mart tags approximately250 million men?s jeans annually. The apparel items are tagged at the point of manufac-turing, and they are read as they arrive at the loading docks, when they move from thewarehouses to the sales floor, and on the shelves [94]. These tags are read frequently duringworking hours. Using this technique, the number of jeans and other items are checked overtime to prevent the theft of items from the shelves. Moreover, the on-shelf monitoringsystem is notified if for instance, a specific size or model of an apparel is near to beingsold out or is in high demand. This way, the store is able to keep the balance betweenconsumer demand and the number of items on shelves. The following example shows theimportance of developing an efficient blocker tag detection method. Assume that a branchof Wal-Mart orders 2500 jeans of different styles and different sizes. These jeans are tagged,stored in the warehouse, and moved to the sales floor as the previous items are being sold.An attacker can put a blocker tag in the warehouse to disrupt the inventory mechanism.If the universal attack is used in an RFID system which works based on the binary treewalking, the reader can easily detect this attack after finding a series of successive IDs(500 for instance), or after finding an unexpected ID in the system (some IDs may bereserved in the system [3, 45], or may belong to other goods or other manufacturers). Thisdetection is even easier if the ALOHA technique is employed by the universal blocker. Theattacker sends information in all the ongoing time slots, changing the empty slots to singleslots and the single slots to collided ones. In this case, the reader can be programmedso that it announces the presence of an attacker if it does not observe any empty slotafter checking a pre-defined number of frames. The bottom line for detecting the univer-32Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemssal attack is counting the number of identified tags in the system and comparing it to apre-defined threshold. However, the story is different for a selective attack. In the aboveexample, the reader can detect the presence of a selective blocker only after identifying atleast 2501 IDs in the singulation procedure (thresholding method). These 2501 IDs are notnecessarily successive, therefore, it takes a long time for the reader to detect the 2501 IDsbefore terminating the singulation process. Moreover, some attackers may try to misleadthe on-shelf inventory mechanism of a store. As an example, a malicious user can put aselective blocker among the apparels of the sales floor to convince the reader that there areenough jeans of a specific size on the shelf, to steal some items or to prevent the systemfrom keeping the balance between the demand and the jeans required on the shelf. Thistype of attack is harder to detect, comparing to the universal blocking attack, and thestore should be notified as soon as possible. Based on the above, large organizations andsuppliers are vulnerable to blocking attacks, and they are in need of more efficient methodsfor detecting selective blocking attacks.For different RFID applications, we may face two different scenarios. In the first sce-nario, accurate information about the number of existing RFID tags is not known. Forexample, RFID tags can be used to count the number of persons attending a conferenceor to have an estimate of the number of attendants in different sessions. In these types ofapplications, we do not know the exact number of RFID tags in the system. If a blockertag is used by an attacker to corrupt this system, to the best of our knowledge, there isno efficient approach to make the reader capable of detecting the presence of the blockertag. If we do not have any initial information about the RFID system and the attackmodel, it is not possible to design an efficient algorithm to detect the blocker attack inthe system. In that case, we can only rely on some predefined thresholds and use them toinstruct the reader to stop interrogation when the number of detected tags or the number33Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsof interrogations exceeds the predefined thresholds.In the second type of RFID applications, the reader has some initial information aboutthe system. Assume a warehouse or a large store where, for example, the reader knows apriori how many bottles of wine (equipped with RFID tags) exist in the system (at thebeginning). When a customer buys some bottles of wine, the number of purchased bottlesis subtracted from the total number of bottles in the system. Therefore, the reader hasalways the updated information about the number of items equipped with RFID tags in thesystem. Another example is a library which uses RFID technology. Here, the exact numberof books in the library is known to the RFID reader. If somebody borrows some books,then by moving through the RFID gate, the reader subtracts the number of detected booksfrom the total available books in the library [21]. In these types of applications, the readerhas initial information about the number of RFID items in the system. The question hereis, how can we use a priori information to find an efficient way to reduce the vulnerabilityof RFID systems against the blocker attack? In this chapter, we answer this question andpropose an efficient probabilistic approach to detect the existence of a blocker tag in thesystem.2.2.2 Problem FormulationThe use of a pre-determined threshold to detect the presence of a malicious blocker tagin the system can be very time consuming. This is because the reader is obliged to con-tinue searching for new serial numbers until a predefined number of interrogations (or apredefined number of detected tags) is accomplished. To provide a faster and more effi-cient blocker tag detection method, first we need to find a reliable analytical model for theblocking attack. In Section 2.2.2.1 and 2.2.2.2, we derive two probabilistic models for thebinary tree walking and ALOHA tag singulation mechanisms.34Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems2.2.2.1 Binary Tree Walking-based RFID SystemsWe consider an RFID system in which there are N real (actual) tags. Let B denote theevent that a blocker tag is present and let B? denote the event that a blocker tag is notpresent. If a blocker tag is present, it can generate F different fake IDs when queriedby the reader. Assume that the reader uses the binary tree walking algorithm for tagsingulation. The total number of levels is L. We use b = b1b2 . . . bl to denote the prefixof the interrogation node. Based on the number of bits in b, the corresponding level l canbe determined accordingly. Let N(b) and E(b) denote the number of detected tags (bothreal and fake) and the number of empty positions in the left hand side of the interrogationnode with prefix b, respectively. The reader updates the values of N(b) and E(b) aftereach interrogation. For example, assume that the reader reaches the node with prefixb = 10 in Fig. 2.1 but it has not interrogated the node b = 10 yet. Thus, the readerwould have observed N(b) = 4 (for RFID tags with IDs 0001, 0010, 0100, and 0101) sofar, and E(b) = 4 (for empty positions 0000, 0011, 0110, and 0111) from its previousinterrogations. When the reader queries a node with prefix b, it observes one of the threepossible responses which we denote by the set r = {0, 1, c}. The value of 0 or 1 correspondsto receiving bit 0 or 1, respectively. The value of c corresponds to a collision. For example,at the interrogation node with prefix b = 10 in Fig. 2.1, the reader observes a collisionbecause there exist three tags with 1000, 1001 and 1011 IDs under this interrogation node.Given N(b), E(b), and the presence of a blocker tag (i.e., event B), the probability ofobserving r = 0 at the interrogation node with prefix b is the probability that there is atleast one tag in the 0 branch of the subtree rooted at node with prefix b and there is no35Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemstag in the 1 branch of this subtree. This probability can be written asPB(r = 0 | N(b), E(b)) =2L?(l+1)?i=1((2L?(l+1)i) i?1?j=0([N + F ?N(b)? j]+2L ?N(b)? E(b)? j)?2(L?l)?1?m=i(1? [N + F ?N(b)? i]+2L ?N(b)? E(b)?m)?? , (2.2)where [x]+ = max{x, 0},?i?1j=0([N+F?N(b)?j]+2L?N(b)?E(b)?j)is the probability that i leaves in the 0branch of the interrogation node b are occupied,?2(L?l)?1m=i(1? [N+F?N(b)?i]+2L?N(b)?E(b)?m)is theprobability that the remaining(2? (2L?(l+1))? i)leaves in the 0 and 1 branches of theinterrogation node are empty, and(2L?(l+1)i)is the number of ways which we can choosei leaves out of the (2L?(l+1)) leaves in the zero branch. We used the [x]+ operator toguarantee that the number of occupied leaves cannot be more than the number of tags inthe system.The probability of observing r = 1 at the interrogation node with prefix b in thepresence of a blocker is the probability that there is no tag in the left hand side (leftbranch) of the subtree rooted at b and there is at least one tag in the right hand side (rightbranch) of this subtree. This probability is equal to the probability of observing r = 0.Thus,PB(r = 1 | N(b), E(b)) = PB(r = 0 | N(b), E(b)). (2.3)A collision may also occur at an interrogation node with prefix b if there are tags in bothof the left and right hand sides of the subtree rooted at node b. This probability can be36Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemswritten asPB(r = c | N(b), E(b)) = 1? PB(r = 0 | N(b), E(b))? PB(r = 1 | N(b), E(b))= 1? 2PB(r = 0 | N(b), E(b)). (2.4)Given there is a blocker tag, the probability of having N(b) and E(b) at the interroga-tion node with prefix b isPB(N(b) = n,E(b) = e) =(n+ en) n?1?i=0(N + F ? i2L ? i) e?1?j=0(1? N + F ? n2L ? n? j). (2.5)In (2.5), the first product term is the probability that N(b) specified positions are occupiedin the (N(b) + E(b)) possible positions. The second product term is the probability thatthe remaining E(b) positions are empty.Given there is a blocker tag, the probability that the reader receives a response r atnode b , and observes N(b) detected tags and E(b) empty positions isPB(r,N(b), E(b)) = PB(r | N(b), E(b))? PB(N(b), E(b)). (2.6)Based on the probabilities in (2.2) and (2.5), the unconditional probability in (2.6) can bedetermined. Similarly, given that there is no blocker tag in the system, we can define theprobabilities PB?(r | N(b), E(b)), PB?(N(b), E(b)), and PB?(r,N(b), E(b)). We can obtainthe corresponding values by substituting F = 0 (i.e., no fake tag in the system) into37Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems(2.2)-(2.6). Thus, we havePB?(r = 0 | N(b), E(b)) =2L?(l+1)?i=1((2L?(l+1)i) i?1?j=0([N ?N(b)? j]+2L ?N(b)? E(b)? j)?2(L?l)?1?m=i(1? [N ?N(b)? i]+2L ?N(b)? E(b)?m)?? , (2.7)PB?(r = 1 | N(b), E(b)) = PB?(r = 0 | N(b), E(b)), (2.8)PB?(N(b) = n,E(b) = e) =(n+ en) n?1?i=0(N ? i2L ? i) e?1?j=0(1? N ? n2L ? n? j), (2.9)andPB?(r,N(b), E(b)) = PB?(r | N(b), E(b))? PB?(N(b), E(b)). (2.10)From (2.7) and (2.9), the unconditional probability in (2.10) can be determined.At each interrogation node with prefix b, we call the tuple (r,N(b), E(b)) observedby a reader as an event. For example, in Fig. 2.1, the event observed at node b = 10 is(r = c,N(b) = 4, E(b) = 4). Based on the observed event, the probabilities in (2.6) and(2.10) can be determined.2.2.2.2 ALOHA-based RFID SystemsSame as RFID systems which use the binary tree walking as the singulation mechanism,RFID systems which use the ALOHA singulation mechanism are also vulnerable to blockingattacks. An attacker may disrupt these systems by sending fake IDs to the randomlyselected time slots in each frame. The blocker causes the reader to detect fake tags by38Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems. . .e e e ss s c c c. . . . . .ek sk ckfFirst subframe Second subframe Third subframeFigure 2.2: The empty, single and collided sections of a time frame in our analytical model.sending fake IDs to the slots which would have remained empty in a normal system.Moreover, the blocking attack causes some of the singly occupied time slots to be observedas collided slots. Using this approach, the attacker can reduce the efficiency of the tagidentification procedure drastically. Based on the above, we need to find an efficient wayto make sure that there is no attacker in the system and prevent the reader from beinginvolved in a loop of endless (or useless) interrogations. In order to do that, we analyticallymodel the ALOHA tag singulation mechanism and find the probabilities that the readerobserves a specific frame structure in presence and absence of a blocker tag. Then basedon these probabilities, we decide whether the blocker exists or not.For a query frame with length f in an ALOHA-based RFID system, let ke denotethe number of empty slots, ks denote the number of slots with single transmission andkc denote the number of collided slots. We denote the probability of observing ke emptyslots, ks single slots, and kc collided slots in the absence and presence of an attacker withPB?(ke, ks, kc) and PB(ke, ks, kc), respectively. Consider a frame structure which has threesubframes as in Fig. 2.2. The first subframe has ke empty slots, the second subframehas ks single slots, and the last subframe consists of kc collided slots. We first find theprobability of observing such a frame and then use this probability to find PB?(ke, ks, kc)and PB(ke, ks, kc).In the formulation, the frame length is denoted by f while N represents the number of39Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsreal tags in the system. First, the probability of observing ke empty slots at the beginningof the frame is considered. This probability is denoted by PB?,1(ke) and is equal toPB?,1(ke) =(1? kef)N. (2.11)In the next step, the probability of observing ks single time slots in the second subframeconditioned to observing ke empty slots in the previous step is obtained. This probabilityis denoted by PB?,2(ks | ke)PB?,2(ks | ke) =(Nks)(ksks + kc)ks (1? ksks + kc)(N?ks)?(ks?i=0(?1)i(ksi)(1? iks)ks), (2.12)where the first three terms represent the probability that ks tags out of N tags choose ksslots in the second subframe and the remaining tags choose the last subframe. The lastterm in (2.12) is the probability that the ks tags which have chosen the second subframeare assigned to the ks slots with no slot empty. In other words, each of the ks slots onlyaccommodates one and only one of the ks tags. This is a well-known problem in theclassical urn model and the probability is provided in [95]. The last term in (2.12) can besimplified asks?i=0(?1)i(ksi)(1? iks)ks= ks!kkss. (2.13)40Chapter 2. Probabilistic Analysis of Blocking Attack in RFID SystemsBased on the above, PB?,2(ks | ke) can be written asPB?,2(ks | ke) =(Nks)(ksks + kc)ks (1? ksks + kc)(N?ks) ks!kkss(2.14)=(Nks)(k(N?ks)c(ks + kc)N)ks!.Now, we need to calculate the probability of observing kc collisions in the last subframeconditional on observing ke empty and ks single time slots in the previous steps. Thisprobability is denoted by PB?,3(kc | ke, ks). Since (N ? ks) tags and kc slots have left, thisis the probability that (N ? ks) tags are distributed in these slots in such a way that allslots have collisions. For PB?,3(kc | ke, ks), it is not that simple to calculate the probabilityof observing kc collisions conditional on ke and ks directly. Let gN?ks(kc, 2) denote thenumber of possible ways of assigning (N ? ks) tags to kc slots while each slot contains atleast 2 tags. Then, we havePB?,3(kc | ks, ke) =gN?ks(kc, 2)k(N?ks)c, (2.15)in which k(N?ks)c is the total number of ways we can assign (N ? ks) tags to the remainingkc time slots. The work by Riordan [96] proved two closed form recursive expressions usingthe classical urn model for gn(m, s). We use one of the expressions which isgn(m, s) =m?k=0(?1)k(mk)n!(s? 1)!k(n? sk + k)!gn?sk+k(m? k, s? 1) (2.16)and 0 ? gn(m, s) < ?. Using (2.16), we can find the exact number of acceptable eventsin (2.15) by replacing n with (N ? ks), m with kc, and s with 2 for our problem. We can41Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemssimplify (2.16) by replacing s with 2 and writegn(m, 2) =m?k=0(?1)k(mk)n!(n? k)!gn?k(m? k, 1) (2.17)in whichgn?k(m? k, 1) = p0(n? k,m? k) (m? k)(n?k) , (2.18)and p0(n ? k,m ? k) is the probability that we have (n ? k) tags and (m ? k) time slotsand all the slots contain at least one tag. From [95], p0(n? k,m? k) can be expressed asp0(n? k,m? k) =m?k?v=0(?1)v(m? kv)(1? vm? k)(n?k). (2.19)Replacing (2.18) and (2.19) in (2.17), we havegn(m, 2) =m?k=0m?k?v=0(?1)(k+v)(mk)(m? kv)n!(n? k)!(m? k ? v)(n?k) , (2.20)which gives us an explicit expression for gn(m, 2). Using (2.11), (2.14), (2.15) and (2.20),PB?(ke, ks, kc) can be written asPB?(ke, ks, kc) =(f !ke! ks! kc!)PB?,1(ke) PB?,2(ks | ke) PB?,3(kc | ks, ke). (2.21)In (2.21),(f !ke! ks! kc!)shows the number of ways the three mentioned subframes in Fig. 2.2can be scrambled and mixed with each other and make a random structure of ke emptyslots, ks single slots and kc collided slots.Now, we determine the probability of observing ke empty, ks single and kc collided timeslots in the presence of a blocker. To accomplish this task, we need to model the blocking42Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsattack. We assume that an attacker exists in the RFID system and leaves each time slotintact (not blocked) with probability p while it blocks each time slot with probability(1 ? p), and p can be varied between 0 and 1. Considering this model, the probability ofobserving ke empty slots, ks single slots and kc collided slots in presence of a blocker iswritten asPB(ke, ks, kc) =(f !ke!ks!kc!)PB,1(ke)[ks?i=0PB,2(ks | ke, i) PB,3(kc | ke, ks, i)]. (2.22)Here, PB,1(ke), PB,2(ks | ke, i), and PB,3(kc | ke, ks, i) are calculated using (2.23), (2.24) and(2.26), respectively. For PB,1(ke), we havePB,1(ke) =(1? kef)Npke , (2.23)in which(1? kef)Ngives the probability that none of the N tags are assigned to the firstke time slots and at the same time, the attacker does not block these ke time slots inFig. 2.2. For PB,2(ks | ke, i) we havePB,2(ks | ke, i) =(Nks ? i)(ksks + kc)(ks?i)(1? ksks + kc)N?(ks?i)p(ks?i) (2.24)? (ks ? i)!(ks ? i)(ks?i)(1? p)i(ksi)(ks ? iks)(ks?i),in which( Nks?i)is the number of ways we can choose (ks ? i) tags out of the total N tagsfor the single subframe,(ksks+kc)(ks?i) (1? ksks+kc)N?(ks?i)gives the probability that (ks? i)tags are assigned to the single subframe and the remaining (N ? (ks ? i)) tags are assignedto the collision subframe, p(ks?i) is the probability that none of the (ks? i) time slots in thesingle subframe are blocked by the attacker, (ks?i)!(ks?i)(ks?i) is the probability that all the (ks?i)time slots are occupied by only one of the (ks ? i) tags, (1? p)i gives the probability that43Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsthe i remaining time slots in the single subframe are all blocked by the attacker,(ksi)is thenumber of ways we can choose i attacked slots out of ks time slots in the single subframe,and(ks?iks)(ks?i)gives the probability that (ks ? i) tags are assigned to the (ks ? i) slotsout of the whole ks time slots in the single subframe. Based on the above, (2.24) can besimplified asPB,2(ks | ke, i) =(Nks ? i)(ksi)(k(N?ks+i)c(ks + kc)N)(ks ? i)!p(ks?i)(1? p)i. (2.25)For the PB,3(kc | ke, ks, i) part, we havePB,3(kc | ke, ks, i) =?????????????????0 , kc > N ? ks + ikc!kkcc(1? p)kc , kc = N ? ks + i?kc?1j=0gN?ks+i?j(kc?j,2)(kc?j)(N?ks+i?j)(kcj)(N?ks+ij)(j!jj)(jkc)j?(kc?jkc)(N?ks+i?j)(1? p)j , otherwise(2.26)where gN?ks+i?j(kc ? j, 2) is the number of ways we can assign (N ? ks + i ? j) tags to(kc? j) time slots and each slot contains at least two tags,(kcj)is the number of ways thatwe can choose j slots out of kc for being blocked by the attacker,(N?ks+ij)is the numberof ways we can choose j tags out of (N ? ks + i) to occupy these attacked time slots,(j!jj)is the probability that all the j attacked time slots are occupied using exactly j tags,(jkc)j (kc?jkc)(N?ks+i?j)is the probability that j tags are assigned to j number of the kctime slots and the remaining (N ? ks + i? j) tags are assigned to the remaining (kc ? j)time slots, and finally (1? p)j is the probability that these j time slots are blocked by theattacker.44Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsq0 11No BlockerRegionBlockerRegion))(),(,(bEbNrPB))(),(,( bEbNrPBFigure 2.3: Two-dimensional representation of the events and decision making criterion fortree-based RFID systems.2.3 Probabilistic Blocker Tag Detection (P-BTD)AlgorithmIn this section, we use the analytical models developed in Sections 2.2.2.1 and 2.2.2.2 andpropose two probabilistic blocker tag detection algorithms for RFID systems that operatebased on the binary tree walking and ALOHA tag singulation mechanisms.2.3.1 Binary Tree Walking-based RFID SystemsAfter finding the PB(r,N(b), E(b)) and PB?(r,N(b), E(b)) probabilities in Section 2.2.2.1,we can use them to decide whether there exists a blocker in the system or not. In order todo that, consider the two-dimensional space in Fig. 2.3, where the x-axis and y-axis denotePB(r,N(b), E(b)) and PB?(r,N(b), E(b)), respectively. Each point (or circle) in this space45Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemscorresponds to a feasible event and its location corresponds to the conditional probabilitiesin (2.6) and (2.10). Two regions can be defined on the two-dimensional space. The firstregion is the blocker region and the second one is the no blocker region. A blocker tag(or attack) is announced if the observed event resides in the blocker region of the two-dimensional space. The blocker and no blocker regions are separated using a line with theangle ? = 45 degree as depicted in Fig. 2.3. Thus, a reader will declare that a blocker tagexists in the system ifPB(r,N(b), E(b)) > PB?(r,N(b), E(b)). (2.27)Algorithm 2.1 denotes the P-BTD procedure for determining the existence of a blockertag in RFID systems which operate based on the binary tree walking mechanism. Theinput parameters of the P-BTD algorithm are the total number of levels L, the thresholdT , the number of real tags N , the number of fake tags F , and the step size h. The step sizeh is a positive integer which tells the reader after how many interrogations it should decideabout the existence of the blocker tag. The algorithm begins interrogation at the root ofthe tree. In line 2, Nl and El are auxiliary variables used to keep track of the number oftags and empty slots detected and they are used to update N(b) and E(b). In line 3, thereader sends a query to all the tags in the system and waits for their responses. Based onthe responses from the tags, the reader will set the response r to 0, 1 or c. After that,the interrogation node b (i.e., the subtree) for the next interrogation is set accordingly.After every h interrogations, the reader decides about the existence of a blocker (line 9).Here, MOD shows the reminder of dividing counter by h. In lines 10 and 11, the requiredprobabilities are determined from (2.6) and (2.10), based on the observed event. If equation(2.27) is satisfied, the reader announces the existence of a blocker tag and terminates theinterrogation procedure (lines 12-13). Otherwise, the algorithm continues as follows.46Chapter 2. Probabilistic Analysis of Blocking Attack in RFID SystemsAlgorithm 2.1 P-BTD algorithm for binary tree walking-based RFID systems1: Input L, T, h,N, F2: Nl := 0, El := 03: Interrogate all tags and set r4: Move to the next interrogation node and set b5: Set N(b) := Nl, E(b) := El6: counter := 07: while N(b) + E(b) ? 2L8: Interrogate at node with prefix b and set r9: if MOD(counter, h) = 010: Compute PB(r,N(b), E(b)) from Eq. (2.6)11: Compute PB?(r,N(b), E(b)) from Eq. (2.10)12: if PB(r,N(b), E(b)) > PB?(r,N(b), E(b))13: Return: Blocker exists14: end if15: end if16: if r ? {0, 1} and l = L? 117: Nl := Nl + 118: else if r = c and l = L? 119: Nl := Nl + 220: end if21: if Nl > T22: Return: Blocker exists23: end if24: El := decimal(b)? 2L?l ?Nl25: Move to the next interrogation node and set b26: counter := counter + 127: Set N(b) := Nl, E(b) := El28: end whileIn lines 16-20, the algorithm updates the total number of tags detected in the system.The algorithm checks if the interrogation node is at level (L ? 1) or not. Observing aresponse r equals to either 0 or 1 at level (L ? 1) means that there exists only one tagin the two positions under that interrogation node. Therefore, Nl is incremented by 1.On the other hand, observing a collision at level (L? 1) means that both positions underthe interrogation node are occupied. Therefore, Nl is incremented by 2. In line 21, thealgorithm also compares Nl and T . If the estimation of the number of real RFID tags N47Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsis accurate, then T is set to (N + 1). Otherwise, we set T to a large value. In both cases,T is greater than N in Algorithm 2.1. In line 21, if Nl > T (i.e., the reader has detectedmore tags than the threshold T ), then the reader declares that a blocker exists and stopsinterrogation. If none of the two conditions in lines 12 and 21 holds, then the reader doesnot have enough evidence to conclude that there exists a blocker in the system. In line 24,the algorithm calculates El based on the values of Nl and b, where the function decimal(b)converts the binary prefix b to a decimal value. After that, the algorithm moves to thenext interrogation node and goes back to line 7. The algorithm stops by either announcingthat a blocker exists or by checking all subsequent interrogation nodes in the binary tree.If an attacker wants to disrupt an RFID system severely, it needs to block a largenumber of tags in the system. In other words, the larger the number of tags it blocks, themore severe is the attack. For example, we may expect that a harmful attacker needs toattack at least 20% of the total possible IDs to interrupt the interrogation procedure ofthe legitimate reader severely. In a 16-bit system, this means that the attacker needs toblock at least 13000 IDs to make a severe problem for the legitimate reader.2.3.2 ALOHA-based RFID SystemsOur approach for designing the P-BTD algorithm for ALOHA-based RFID systems isexactly the same as that of Section 2.3.1. First, we calculate PB(ke, ks, kc) and PB?(ke, ks, kc)using Eq. (2.21) and (2.22). Then, we divide the two dimensional space of the eventsobserved by the reader into two regions as shown in Fig. 2.4, the blocker region and theno blocker region. Now we need an algorithm which helps the reader to detect a blockerin the system using the information obtained from the previous queries. This procedure isexplained in Algorithm 2.2. The reader needs the initial values of N , p, T , and h. Here,T is a predefined threshold which can be adjusted by the user to determine the maximum48Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsq0 11No BlockerRegionBlockerRegion),,(cseBkkkP),,( cseB kkkPFigure 2.4: Two-dimensional representation of the events and decision making criterion forALOHA-based RFID systems.number of acceptable interrogations, h is the step size and N and p were defined previously.Using these values, the reader starts interrogating the tags and updates the values of Nafter each interrogation. The reader computes the values of PB?(ke, ks, kc) and PB(ke, ks, kc)after each h interrogations and compares them. If the value of PB(ke, ks, kc) is greater thanPB?(ke, ks, kc), then it announces that there exists an attacker in the system and terminatesthe interrogation procedure, otherwise, it updates the values of Query, N , ke, ks, kc andFlag, and continues its work. At each interrogation, the reader checks three conditionsand if any of them does not hold, it terminates the interrogation immediately. The firstcondition, (N > 0), guarantees that the number of detected tags is not bigger than thetotal number of RFID tags in the system. The second condition, (Query < T ), guaranteesthat the number of performed interrogations is less than a predefined threshold. Finally,(Flag = 0) guarantees that no blocker has been detected in the system so far. In line 15,MOD is used to show the reminder of dividing Query by h.49Chapter 2. Probabilistic Analysis of Blocking Attack in RFID SystemsAlgorithm 2.2 P-BTD algorithm for ALOHA-based RFID systems1: Input N, p, T, h2: Flag := 03: Query := 04: ke := 0, ks := 0, kc := 05: while (N > 0) and (Flag = 0)6: f := N7: Interrogate all tags8: Query := Query + 19: if Query > T10: Return: Blocker exists11: Flag := 112: end if13: update ke, ks, kc14: N := N ? ks15: if MOD(Query, h) = 016: Compute PB?(ke, ks, kc) from Eq. (2.21)17: Compute PB(ke, ks, kc) from Eq. (2.22)18: if PB(ke, ks, kc) > PB?(ke, ks, kc)19: Return: Blocker exists20: Flag := 121: end if22: end if23: end while2.4 Performance EvaluationThis section presents the results of the simulation experiments we carried to evaluatethe performance of our proposed P-BTD algorithms. We also present the performancecomparisons between the proposed P-BTD algorithms and the threshold-based detectionmethod [45]. All simulations are performed in the MAPLE environment.2.4.1 Binary Tree Walking-based RFID SystemsIn this part, we investigate the performance of the P-BTD algorithm when the interrogationprocess is based on the binary tree walking singulation. First, we consider the probability of50Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systemsdetection error. There are two types of detection errors for the proposed P-BTD algorithm.The first one is the error of missing the presence of a blocker. This happens when thereexists a blocker in the system but the algorithm does not detect it. This probability is zerodue to the fact that even if the probabilistic approach (i.e., line 12 in Algorithm 2.1) cannotdetect a blocker, the threshold in line 21 of Algorithm 2.1 would detect it. Therefore, if ablocker exists, the algorithm detects its presence with probability one. The second erroris false alarm. This happens when the algorithm declares that there is a blocker in thesystem but that is not the case. We find the probability of false alarm via simulations.We consider an RFID system with 16-bit tag IDs (i.e, L = 16). In Algorithm 2.1, weset the input parameters as follows: L = 16, T = N + 1, h = 1, 000 and F = 1, 000, whereN is the number of existing real tags, h is the step size and F is the number of fake tagsgenerated by the blocker. N is varied from 1,000 to 5,000 with steps of 1,000. Fig. 2.5shows the probability of false alarm. Simulation results show that the probability of falsealarm decreases as the number of existing real tags N increases. When N = 5, 000, theprobability of false alarm is almost zero. This is because as N gets larger than F , thesystem becomes less sensitive to a blocker tag.Next, we investigate the effects of changing the parameter F on the behavior of thesystem. In this experiment, L = 16, N = 5, 000, and h = 1, 000. We vary the number offake tags F between 1,000 and 5,000. For different values of F , Fig. 2.6 shows the proba-bility of observing a collision at the interrogation node with prefix b = 000000111110100,given N(b) and E(b). Here, N(b) shows the number of tags detected by the reader up tonode b in the binary tree. The number of empty leaves detected by the reader up to nodeb = 000000111110100 is given by E(b). Fig. 2.6 shows that when the number of fake tagsF increases, the distance between the two peaks related to the system with and withoutan attacker also increases. As this distance increases, the level of uncertainty in the de-51Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems1,000 2,000 3,000 4,000 5,000012345x 10?4NProbabilityoffalsealarmFigure 2.5: Probability of false alarm by P-BTD algorithm in a 16-bit RFID system.cision decreases. This makes it easier for the algorithm to decide about the existence ofan attacker. In other words, if the attacker reduces the number of fake tags it introduces,the two peaks in Fig. 2.6 merge and this increases the level of uncertainty. On the otherhand, the attacker needs to block a large number of IDs in order to prevent the reader fromidentifying the real tags efficiently [45]. This makes it easier for the algorithm to detect thepresence of the attacker. Although Fig. 2.6 is plotted for the collision event (i.e., r = c),we obtain similar results for the cases of receiving 0 (r = 0) or 1 (r = 1) by the reader.We now compare the performance of the P-BTD algorithm with the threshold-baseddetection method [45] for a 16-bit RFID system. First, we set N = 5,000, h =1,000 andvary the number of fake tags F from 1,000 to 5,000. This procedure is repeated 1,000times. Each time Algorithm 2.1 announces that a blocker exists, we save the binary IDnumber of the last detected tag before the algorithm makes this decision. At the end ofthe simulation, the saved IDs are averaged to form the average of the last detected ID. The52Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems0 50 100 150 20000.010.020.030.040.050.06N(b)P(r=c|N(b),E(b))F=10000 50 100 150 20000.010.020.030.040.050.06N(b)P(r=c|N(b),E(b))F=20000 50 100 150 20000.010.020.030.040.050.06N(b)P(r=c|N(b),E(b))F=40000 50 100 150 20000.010.020.030.040.050.06N(b)F=5000Without BlockerWith BlockerWithout BlockerWith BlockerWithout BlockerWith BlockerWithout BlockerWith BlockerFigure 2.6: The effect of changing the number of fake tags on the probability of observingcollision in an RFID system with L = 16, N = 5, 000, b = 000000111110100, and h =1, 000.performance metric of the system is taken as the average of the last detected ID numbersbefore the algorithm declares a blocker exists. The reason this average is considered as anindicator of how fast the algorithm can detect the presence of a blocker tag is as follows: Asmall value for the last detected ID implies that the algorithm is able to detect a blockerwith a few number of interrogations. In other words, the reader needs to perform moreinterrogations to find a tag whose ID value is large. Each interrogation takes a specificamount of time to accomplish, thus if fewer tags were interrogated, then less time is spentby the reader to make its decision. For ease of understanding, we convert the ID numbersfrom binary to a decimal format.Fig. 2.7 shows the results of the last interrogated ID numbers averaged over 1,000iterations (N = 5,000) for the threshold-based detection algorithm [45] and our proposed53Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems1000 2000 3000 4000 50000123456x 104FAverageofthelastinterrogatedserialnumber Threshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.7: Average of the last detected ID before detecting the presence of a blocker versusnumber of fake tags F . (L = 16, N = 5, 000 and h = 1, 000)P-BTD algorithm. Simulation results show that our proposed algorithm can detect thepresence of a blocker at least 6 times faster than the threshold-based detection protocol [45]for different values of F . From Fig. 2.7, it can also be concluded that the detection speed ofour proposed algorithm does not depend on F (for values of F greater than 2,000). Next,we present the simulation results when the number of existing tags N is varied. Again,the performance metric is the average of the last detected ID numbers. The number offake tags F is set to 5,000. N is varied from 1,000 to 5,000 with steps of 1,000. Thesimulation results in Fig. 2.8 show that our proposed P-BTD algorithm is able to detectthe blocker in the system faster (2.5 to 6.5 times) than the threshold-based method andwith fewer interrogations. As can be inferred from Fig. 2.8, the threshold-based detectionalgorithm is sensitive to the number of real tags and its detection capability degrades asN increases. Our P-BTD algorithm outperforms the threshold-based algorithm in termsof detection time. Moreover, the performance of our proposed P-BTD algorithm does notdepend on the the number of existing tags in the system. This can add to the value of54Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems1000 2000 3000 4000 500000.511.522.533.54 x 104NAverageofthelastinterrogatedserialnumber Threshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.8: Average of the last detected ID before detecting the presence of a blocker versusnumber of real tags N . (L = 16, F = 5, 000 and h = 1, 000)our proposed algorithm because in practical cases, the algorithm should be able to workefficiently irrespective of the value of N .So far, we have assumed that we know the accurate values of N and F in the binarytree walking-based P-BTD algorithm. Now, we assume that the reader does not knowthe accurate values of these parameters and find the sensitivity of the P-BTD method tothese values. In order to do that, we consider the cases where the P-BTD algorithm usesinaccurate values of N and F . Fig. 2.9 shows the average of the last detected IDs when theP-BTD algorithm uses inaccurate values of F with ?5% error in the binary tree walkingsystem. Here, we assume N = 5, 000 and h = 1, 000. As can be inferred from Fig. 2.9,the P-BTD algorithm is capable of detecting a blocker tag faster (1.6 to 2.5 times) thanthe threshold-based method even when the reader uses inaccurate values of F (with ?5%error).Fig. 2.10 shows the average of the last detected IDs when the P-BTD algorithm usesan inaccurate value of N (with ?5% error) in the binary tree walking system. Even in this55Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems1000 2000 3000 4000 50000123456 x 104FAverageofthelastinterrogatedserialnumber Threshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.9: Average of the last interrogated serial number versus inaccurate values of F(?5% error) in the P-BTD and threshold-based algorithms for binary tree walking RFIDsystems. (L = 16, N = 5, 000 and h = 1, 000)case, the P-BTD algorithm is capable of detecting a blocker tag faster (1.1 to 1.8 times)than the threshold-based method.2.4.2 ALOHA-based RFID SystemsFor the ALOHA-based systems, we first investigate the performance of the P-BTD methodin terms of the probability of false alarm. Fig. 2.11 shows the probability of false alarm fordifferent values of N . We assume that (1?p) is the probability of blocking any time slot bythe blocker. We assume p = 1 for the case that a blocker does not exist and p = 0.7 for thecase that a blocker exists. We vary N from 100 to 500 and repeat the experiment 10,000times for each value of N . Then, we count the number of times the P-BTD algorithmannounces the existence of a blocker in the system, when such a blocker does not exist. Aswe can conclude from the figure, the probability of false alarm increases as N increases.56Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems1000 2000 3000 4000 500000.511.522.533.54 x 104NAverageofthelastinterrogatedserialnumberThreshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.10: Average of the last interrogated serial number versus inaccurate values of N(?5% error) in the P-BTD and threshold-based algorithms for binary tree walking RFIDsystems. (L = 16, F = 5, 000 and h = 1, 000)The probability of false alarm is zero for the threshold-based detection algorithm. Theaverage number of queries required to detect the presence of a blocker versus p is shownin Fig. 2.12. From this figure, we understand that the threshold-based algorithm is moredependent on the value of p than the P-BTD algorithm in terms of the average numberof queries. Moreover, the P-BTD algorithm is capable of detecting the blocker faster (1.5to 2.5 times) than the threshold-based method. This difference becomes more obvious inthe region where p changes between 0.9 and 0.99. By increasing the value of p, the systembehaves more similarly to a normal system (without a blocker). Therefore, more queriesare needed to detect the blocker in the system. The average number of queries required fordetecting the blocker versus N is shown in Fig. 2.13. As can be inferred from this figure,the P-BTD algorithm is able to detect the existence of an attacker using few queries (lessthan 3 queries) for different values of N while the threshold-based algorithm, on average,57Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems100 200 300 400 500012345678 x 10?4NProbabilityoffalsealarmFigure 2.11: The probability of false alarm by P-BTD algorithm in an ALOHA-basedRFID system.detects the attacker close to the 6th query.So far, we have assumed that the values of N and p are known in the ALOHA-basedP-BTD algorithm. Now, we assume that the reader does not know the accurate values ofthese parameters and find the sensitivity of the P-BTD method to these values. In orderto do that, we consider the cases where the P-BTD algorithm uses inaccurate values of Nand p. Fig. 2.14 shows the average number of the required queries for inaccurate valuesof p in an ALOHA-based RFID system with N = 500. To model the error, we run thealgorithm twice, using two inaccurate values of p. The error of p in the first run is -0.05and the error in the second run is +0.05. Fig. 2.14 shows the average of the results forboth cases. As can be observed, the P-BTD algorithm is capable of detecting the blockertag faster (1.1 to 1.8 times) than the threshold-based method, even when the reader doesnot choose the right value for p. Fig. 2.15 shows the average number of required querieswhen the reader chooses an inaccurate value for N and p is equal to 0.7. Here, we assumethe reader has ?5% error in choosing the right value of N . This situation can be ignored58Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.9902468101214pAverageNumberoftheRequiredQueriesThreshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.12: Average number of the required queries for different values of p in the P-BTDand threshold-based algorithms. (N = 500, h = 1 and T = 21)in our P-BTD method because this algorithm is designed for applications where the initialvalue of N is known a priori and the changes of N over time can be tracked by the reader.As can be inferred from Fig. 2.15, the threshold-based algorithm is not capable of detectingthe presence of the blocker if it does not have the correct value of N . Here, the algorithmterminates only after it reaches a predefined number of queries (21 in the simulations)by announcing that there exists a blocker in the system and stopping the interrogationprocedure. On the other hand, the P-BTD algorithm is still capable of detecting theblocker tag but the number of required queries increases with N .2.5 SummaryIn this chapter, we studied the use of a blocker tag as a malicious tool to attack RFID sys-tems. We modeled the blocker attack analytically for RFID systems whose interrogation59Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems100 150 200 250 300 350 400 450 50001234567NAverageNumberoftheRequiredQueriesThreshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.13: Average number of the required queries for different values of N in the P-BTDand threshold-based algorithms. (p = 0.7, h = 1 and T = 21)processes are based on the binary tree walking or the ALOHA singulation mechanisms. Us-ing these analytical models, we proposed two probabilistic blocker tag detection (P-BTD)algorithms. These algorithms use probabilistic approaches for detecting the presence of ablocker tag in RFID systems. The first algorithm is designed for RFID systems based onthe binary tree walking concept and the second one is for ALOHA-based RFID systems. Inthe binary tree walking P-BTD algorithm, the RFID reader uses the information extractedfrom the previous interrogations along with the observation at the current interrogationnode to make a decision about the existence of a blocker. In the ALOHA-based P-BTDalgorithm, the reader uses the information obtained from each interrogation and updatesthe number of empty, single and collided time slots in the frame. Using this information,the reader calculates the probability of observing each frame structure in the presence andabsence of a blocker and makes its decision based on these probabilities. In order to use theproposed P-BTD algorithms in simple readers with limited computational capabilities, all60Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9012345678pAverageNumberoftheRequiredQueriesThreshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.14: Average number of the required queries with inaccurate values of p (?0.05error) in the P-BTD and threshold-based algorithms. (N = 500, h = 1 and T = 21)the probabilities can be calculated once and saved in a look up table (LUT). Basic readerscan use this LUT to prevent the calculations required for the P-BTD algorithms.We showed via simulations that the probabilities of false alarm are very low, in the orderof 10?4, for both the proposed binary tree walking and ALOHA-based P-BTD algorithms.It was also shown that the probability of missing the presence of a blocker tag in the systemis zero for the proposed P-BTD algorithms. Based on the simulation results, the proposedP-BTD algorithms expedite the blocker detection procedure by reducing the number ofrequired interrogations. Our proposed P-BTD algorithms have better performance thanthe threshold-based method because they use the probabilistic model of the blocker attackand continuously update the information about the system. The threshold-based method,on the other hand, relies on counting the number of RFID tags only and ignores otheruseful information such as the probabilistic behavior of the blocker attack. Sensitivity ofthe proposed P-BTD algorithms to inaccurate values of the input parameters was also61Chapter 2. Probabilistic Analysis of Blocking Attack in RFID Systems100 150 200 250 300 350 400 450 5000510152025NAverageNumberoftheRequiredQueriesThreshold?based Detection AlgorithmP?BTD AlgorithmFigure 2.15: Average number of the required queries with inaccurate values of N (?5%error) in the P-BTD and threshold-based algorithms. (p = 0.7, h = 1 and T = 21)studied and it was shown through simulations that the proposed P-BTD algorithms candetect the presence of a blocker tag faster than the threshold-based method, even if thereader does not know the accurate values of N , F or p.In order to design the P-BTD algorithms, we assumed that the reader may not haveonline access to a central database for checking the validity of the detected tag IDs. This isa reasonable assumption for many applications and readers. As explained in the exampleof the wine warehouse in Section 2.2.1.3, the reader may not know the ID of each tagat the beginning, but it knows how many bottles of wine have been transferred to thewarehouse. At this stage, the reader only knows the number of tags present in the systembut does not know their IDs. The reader (or the central database) will know the IDs afterfinishing the singulation procedure. Moreover, having online access to a central databasecan be a strong assumption for many applications [7]. Based on the above, we designedthe P-BTD algorithms so that they do not rely on any previous knowledge of the tag IDs.62Chapter 2. Probabilistic Analysis of Blocking Attack in RFID SystemsHowever, if the reader has online access to a central database and knows the IDs of thetags present in the system, then one line can be added to the proposed P-BTD algorithms(as an additional constraint) for checking the validity of each detected tag ID, withoutlosing the generality of the proposed P-BTD algorithm.Finally, the proposed analytical models for the binary tree walking and ALOHA sin-gulation mechanisms were used to design probabilistic blocker tag detection algorithms inthis study, however, these analytical models can also be used for many other purposes suchas estimating the number of tags in an environment or improving the performance of RFIDsystems.63Chapter 3Toward a Light-weightAuthentication Protocol for RFIDSystems3.1 IntroductionRFID systems are vulnerable to security and privacy threats. Tracking customers, extract-ing personal information and selling illegally copied items are only few samples of theseissues. To cope with security and privacy issues in RFID systems, various schemes havebeen proposed. These solutions can be divided into two general groups. The first groupuses blocking, jamming and physical solutions for RFID security [45, 46, 47]. The othergroup uses cryptographic concepts and security protocols. Cryptographic solutions forRFID security issues can themselves be divided into two main groups, light-weight authen-tication protocols and complex cryptographic solutions. Some researchers believe that itis possible to use complex cryptographic protocols in future RFID tags. They believe themanufacturing costs of implementing cryptographic functions in RFID tags will decreasegradually and future RFID tags will have more computational power. Therefore, theysuggest using public key solutions such as elliptic curve cryptography (ECC) [39, 42] andthe advanced encryption standard (AES) [43]. Most RFID researchers, on the other hand,64Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsbelieve that the industry needs simple and low cost RFID tags (below 5 cents per item)with limited number of logical gates [12, 97]. For this case, many approaches that are basedon light-weight authentication protocols have been suggested [4, 5, 6, 7, 30, 32, 35, 37].Light-weight authentication protocols have the advantage of keeping the computationaldemand and the price of RFID tags very low. For this reason, light-weight authenticationprotocols have been of interest to both industry and academia. In this work, we performthe security analysis of the EPC Gen-2 protocol as one of the major standards of commu-nication between the tags and the reader in passive RFID systems. We also perform thesecurity analysis of five other light-weight RFID protocols proposed in [4, 5, 6, 7], and showthat they are vulnerable to some security attacks. We then propose a new light-weightauthentication protocol that takes the hardware limitations and the manufacturing costsof RFID tags into consideration. The main goal of the proposed light-weight authentica-tion protocol is to improve the security and reliability of communications between the tagsand the reader(s) in RFID systems. We show that our proposed authentication protocolimproves the level of security by solving the security issues of the protocols introduced in[4, 5, 6, 7]. Briefly, the contributions of this chapter are as follows:? We perform the security analysis of the standard EPC Gen-2 protocol, as well as thelight-weight authentication protocols proposed by Henrici and Mu?ller [5], Lim et al.[6], Tan et al. [7] and Sun et al. [4], and show how they are vulnerable to simpleattacks by malicious users.? Using what we learned from the security issues of the above mentioned protocols andtaking advantage of the SQUASH message authentication method [98], we propose anew light-weight authentication protocol that increases the security of communica-tions between the readers and the tags in RFID systems.? The computational cost and the complexity of the above mentioned protocols are65Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsdiscussed and compared.The rest of this chapter is organized as follows: Section 3.2 explains the standard EPCGen-2 protocol [3] along with five recently proposed light-weight authentication protocols[4, 5, 6, 7]. Section 3.3 summarizes the security drawbacks of the explained protocols andshows some simple tricks that can be used by attackers to affect the normal function ofthese protocols. In Section 3.4, we propose a new light-weight authentication protocol thatimproves the security and privacy of the RFID protocols studied in Section 3.2. Finally,the security of the proposed protocol and its computational costs are compared with thediscussed schemes in Section 3.5.3.2 Related Works3.2.1 EPC Class-1 Gen-2 RFID ProtocolThe EPCglobal class-1 generation-2 (briefly EPC Gen-2) protocol was approved as the ISO18000-6C standard in July 2006. This protocol was designed based on the specificationsand limitations of a standard class of passive RFID tags called the EPC Gen-2 tags. Atypical EPC Gen-2 tag contains a pseudorandom number generator (PRNG) and takesadvantage of a cyclic redundancy code (CRC-16) to protect the message integrity duringcommunication [3, 4]. An EPC Gen-2 tag gets its power from the reader, therefore, itscomputational power is limited. As a result, EPC Gen-2 tags cannot perform complexcomputations. In the EPC Gen-2 protocol, the communication process is performed asshown in Fig. 3.1:1. First, a request message is sent from the reader to the tag (in the form of ?Query?,?QueryAdj? or ?QueryRep? commands) to start the session [3, 4].66Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRequest(1)(2)(3)(4)RN16idACK (RN16)Req RN (RN16)handlecommand (handle)(5)(6)(7)Inventory StageAccess StageReader TagFigure 3.1: The standard EPC Gen-2 protocol [3, 4].2. The tag responds to the request message by generating a random 16-bit string, de-noted by RN16.3. The reader sends an acknowledge message, ACK(RN16), to the tag and waits forits response.4. After receiving the ACK(RN16), the tag sends its id in plain text to the reader andthe session is terminated.The above four steps are used for everyday RFID applications and called the ?inventorystage?. To modify all or part of the information stored in the tag, the reader can startanother stage, denoted as the ?access stage?, (steps 5 to 7 in Fig. 3.1). In order to startthe access session, the reader sends a Req RN(RN16) message (containing the previousRN16) to the tag and asks it for another random number. The tag checks if the previous67Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRN16 is correct and then replies with a ?handle? as explained in the EPC Gen-2 protocol.Finally, step (7) provides the appropriate memory access commands, such as ?Read?,?Write? and ?BlockWrite? [3, 4]. The reader needs to provide the same handle as the oneit received from the tag in step (6).The EPC Gen-2 protocol only relies on the capabilities of EPC Gen-2 tags (PRNG andCRC-16 circuitries) and does not need additional hardware equipments (which increase themanufacturing price of RFID tags). Moreover, the reader can query a tag as much as itwants without worrying about the denial of service (DoS) issue. In addition to the EPCGen-2 protocol, several light-weight authentication protocols have been proposed in recentyears. The main purpose of these light-weight authentication protocols is to improve thesecurity and privacy of the communications between the tags and the readers in RFIDsystems. In this section, we explain five recently proposed light-weight RFID protocols.We will explain how each of these protocols can be attacked by malicious users later inSection 3.3.3.2.2 Henrici-Mu?ller RFID ProtocolThe protocol proposed by Henrici and Mu?ller is a simple communication scheme designedfor RFID systems [5]. It relies on one-way hash functions and aims to prevent the trackingattack by changing the traceable data at each interrogation. A hash function is generallydefined as an algorithm or subroutine that maps large data sets of variable length to smallerdata sets of a fixed length. In Henrici-Mu?ller protocol, it is assumed that the singulationprocedure has been accomplished by the reader previously. Singulation is a method used byRFID readers to identify which tags are present in the system [20, 45]. The principles of thisprotocol are as follows: after the singulation phase, each tag contains its current identifierid, the current session number i, and the last successful session number i?. Similarly, the68Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRequestiidihidh D ),( ),( o)( , idirhr oo(1)(2)(3)if correct:ii ?*1+? ii*iii -=Dr Random Generate*iii +D=),( idrfid?ii ?*),( idrfid?Reader TagFigure 3.2: The RFID protocol proposed by Henrici and Mu?ller [5].database contains a list of all identifiers, session numbers and the last successful sessionnumbers for all the tags in the system. In addition to id, i and i?, the list contains thehashed value of id, denoted by h(id), for each tag in the system. In this scheme, both thereader and the tags are aware of the hash function h. At the very beginning, id and i areinitialized with random values and i? is equal to i. After initialization, the communicationprocess is performed as shown in Fig. 3.2 and consist of the following steps:1. First, a request message is sent from the reader to the tag to start the session.2. After receiving a request message from the reader, the tag increases the value of its iby one and calculates h(id), h(i ? id) and ?i = i? i?, and sends them to the readervia the insecure wireless channel. Here, ? is a ?suitable conjugation function? asmentioned in [5].3. The reader sends the above information to the database. The database calculatesthe hash functions for all the tags in the system and finds the tag whose id resultsin the received hash value h(id). The database extracts i? of the tag and calculates69Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsi (i = i? +?i) and i?. The database calculates h(i ? id) and checks whether or not itmatches the one sent by the tag. If the tag is confirmed by the database, a randomvalue r is generated. Then, r and h(r ? i ? id) are sent to the tag.4. Since the tag knows i and id and it receives r from the reader, it can calculateh(r ? i ? id) to make sure that it is communicating with the legitimate reader. If thisis the case, the tag calculates its new identifier using a predefined function of thereceived r like f(r, id), and updates the last successful session number i? which is setto i.It should be noted that in this protocol, an entry is not deleted from the database evenafter the third step, but a copy of the previous id and i? are kept until the next successfulsession. If the third step fails for any reason or the tag cannot receive the random value rcorrectly, the database can still identify the tag using the previous id and i.3.2.3 Lim et al. RFID ProtocolsHere, we explain two RFID protocols proposed by Lim et al. [6]. These protocols havebeen designed to improve the security of communication in RFID systems and to providea more reliable solution than [5]. The first protocol proposed by Lim et al. is namedthe ?challenge-response trigger? and uses a challenge-response mechanism to provide therequired security for RFID systems. After the singulation phase, each tag contains itscurrent id, and a copy of all the tag ids is kept in the database as well. The communicationprocess is performed as shown in Fig. 3.3:1. First, a request message is sent from the reader to the tag, along with a randomchallenge R to start the session.2. The tag generates a random challenge R? after receiving the request from the reader70Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRequest ,)( , RidgR o?)( Ridh ?o(1)(2)(3)Rididprev ?)( idfid ? ididprev ? )( idfid ?R Random GenerateR? Random Generateif correctReader TagFigure 3.3: The challenge-response trigger protocol proposed by Lim et al. [6].and sends it along with the g(id ? R) value to the reader. Again, ? is a ?suitableconjugation function? like XOR, and g is a one-way hash function [6]. The tag usesthe received R in its response g(id?R) to convince the reader that it is communicatingwith the legitimate tag, and not with an attacker.3. The reader forwards the information in step (2) to the database and the informationis checked there. If g(id ?R) is correct, the database calculates h(id ?R?) and sendsit to the tag via the reader. Like g, h is also a one-way hash function. The new id iscalculated using a function f which is known by both the tag and the database.It should be noted that in the challenge-response trigger protocol, an entry is not deletedfrom the database after the third step, but a copy of the previous id is kept until the nextsuccessful session. If the third step fails for any reason, the database can still identifythe tag using the previous id. After introducing the challenge-response trigger approach,another protocol was proposed by Lim et al. to improve the security of reader-tag com-munication in RFID systems. This scheme is named the ?forward rolling trigger? protocoland takes advantage of the Lamport?s one-time password authentication scheme [99]. In71Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsthis scheme, the tag only responds to a valid challenge from the reader, otherwise it sendsback some random value [6]. In the forward rolling trigger protocol, the reader stores achain of hash functions h(w), h2(w), h3(w),..., hmax(w), where h is a secure one-way hashfunction, w is a secret random seed, and max is the length of the chain. For each tag inRequest ,extidR , ?rep(1)(2)(3) ifiLi , )(idfid?1 +?iiididprev?R? Random Generate))(( and )0( *** iiii LLhii =>- -if),( iidgextid =ii ?*ii LL ?*elseend),( iidgextid =if),( Ridhrep ?=elserep Random Generateend),( Ridhrep ?=)(idfid?ididprev?Reader TagGenerate Random extidFigure 3.4: The forward rolling trigger protocol proposed by Lim et al. [6].the system, the last successful session (communication with the reader) is stored as i? andthe current session is indicated by i. The reader uses Li = hmax?i(w) to authenticate itselfto the tag. The values of i? and i are initialized to 0 at the beginning, and Li is initializedto hmax(w). The communication process is shown in Fig. 3.4 and has the following steps:1. The reader sends i and Li to the tag, along with the request message, to start a newsession with the tag.2. The tag checks whether (i?i?) is greater than 0 and hi?i?(Li) is equal to Li? . If these72Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemstwo conditions hold, it calculates extid = g(id, i), in which i is the current sessionnumber and id shows the identification of the tag. It also updates i? to be i, Li? tobe Li, generates a random challenge R?, and sends the extid and R? to the reader.The tag replies to the reader?s request with a meaningless random value instead ofextid if any of the two mentioned conditions does not hold.3. The reader forwards the received information to the database and if the receivedextid is correct, rep = h(id, R?) is calculated and sent to the tag via the reader.Otherwise, a meaningless random rep is generated and sent to the tag.4. After sending the rep to the tag, the current id is stored as the previous identificationidprev and the new id is calculated using f(id) in which f is a one-way function knownby the tag and the reader. At the tag side, idprev and id are updated only if thereceived rep is equal to h(id, R?).It should be noted that as in the previous three protocols, an entry is not deleted from thedatabase after the third step, but a copy of the previous id is kept until the next successfulsession. If the third step fails for any reason, the database can still identify the tag usingthe previous id.3.2.4 Tan et al. RFID ProtocolThe majority of recent RFID protocols such as the EPC Gen-2 standard and the protocolsproposed in [5] and [6] take advantage of a central database to store the RFID tag data. Inthese schemes, the reader queries the tags and sends the information to a central databaseusing a secure line. After authentication, the database returns the tag data to the reader.In [7], however, Tan et al. proposed a novel server-less authentication protocol that aimsto provide the same level of security as the previous protocols without needing a central73Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRequestjn(1)(2)(3) ii rn , mji trfh )),((jjiji idnntrfh ?)||||),(((4)Reader TagFigure 3.5: The server-less protocol proposed by Tan et al. [7].database. In this scheme, each reader has a unique identifier ri and each tag has a uniqueidentifier and a unique secret tj. For each tag, the secret tj is only known by the tag and acentral database. A one-way hash function h is known to all the tags and the readers. Letf(a, b) = h(a||b) in which || is the concatenation operation and a and b are the argumentsof f . Each reader ri is connected to the central database only once at the initializationstep and receives f(ri, t1) for the first tag, f(ri, t2) for the second tag, ..., and f(ri, tn)for the n-th tag in the system. It should be noted that the reader does not have accessto the secret tj of the j-th tag, but it knows the hash function f(ri, tj) [7]. Detail of theserver-less protocol is shown in Fig. 3.5 and it works as follows:1. The reader first sends a request message to the tag.2. The tag replies to the request from the tag by sending a random challenge nj.3. The reader sends its identifier ri along with a random challenge ni to the tag.4. The tag calculates h(f(ri, tj)) and sends its first m bits, denoted by h(f(ri, tj))m tothe reader. In addition to h(f(ri, tj))m, the tag calculates h(f(ri, tj)||ni||nj) ? idj74Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsand sends it back to the reader, where ? is the XOR operation.5. The reader checks its database and calculates the hash function of all of its entriesf(ri, tj), and looks for the candidates that match the first m bits of h(f(ri, tj))m.If there is a match, the reader uses the random challenges ni and nj to obtainh(f(ri, tj)||ni||nj), and then, calculates idj using an XOR operation.This protocol is easy to implement, inexpensive, and does not rely on the back-enddatabase concept. Moreover, it has been shown that this protocol can resist the DoS,cloning, replay and physical attacks [7]. However, it has some security issues which will beexplained in Section 3.3.3.2.5 Sun et al. Gen-2+ RFID ProtocolHere, we discuss the Gen-2+ protocol proposed by Sun et al. [4]. As mentioned in Sec-tion 3.2.1, the EPC Gen-2 protocol is inexpensive and easy to implement, however, it doesnot provide a secure protocol for communication between the legitimate readers and thetags. The id is sent in plain text to any reader who queries and sends an acknowledgemessage to the tag. This can jeopardize the privacy of the RFID technology consumers.Based on the above, Sun et al. modified the EPC Gen-2 protocol so as to provide mutualauthentication between the legitimate readers and the tags. The modified version of theEPC Gen-2 protocol is named the Gen-2+ protocol. It uses the PRNG and CRC-16 toolswhich are predicted in the EPC Gen-2 standard. Sun et al. assumed that each tag sharesan l-word-long random string, called ?key-pool?, with the back-end database. This stringis randomly generated by the back-end database and is written into the tag before deploy-ment [4]. A threshold t is also set in each tag to tolerate errors in the received bits andto boost the reading speed. Up to this point, no additional circuitry was needed by theGen-2+ protocol. However, Sun et al. assumed that it is possible to design and add an75Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRequest(1)(2)(3)(4)RN16 , checkidck?Req RN (RN16)handlecommand (handle)(5)(6)(7)Reader TagFigure 3.6: The Gen-2+ protocol proposed by Sun et al. [4].extra Hamming distance calculator to each EPC Gen-2 tag [4]. The Gen-2+ protocol isdepicted in Fig. 3.6 and works as follows:1. A request message in the form of Query, QueryAdj or QueryRep [3, 4] is sent fromthe reader to the tag.2. The tag generates a 16-bit random number RN16 using its PRNG circuitry andsends it to the tag. It also sends a check message that provides two bits of additionalinformation about the tag. In this scheme, the 16-bit RN16 is divided into two 8-bitbinary strings, called a and b. The check message is calculated by performing theXOR operation on the last two bits of a and b, i.e. a6? b6 and a7? b7, and it is usedto boost the process required for identifying the tag [4].76Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems3. The reader sends the RN16 (composed of a and b) and the check values to the back-end database. The database searches the key-pool to find the 16-bit key which ispointed out by a and b. This key is denoted by ck? and it is sent to the tag by thereader.4. The tag compares this ck? with its key ck to see if their Hamming distance is lessthan the threshold t. The tag accepts the reader as a legitimate reader and sends itsid if the mentioned Hamming distance is less than t, otherwise, it does not send itsid and waits for a new ck? from the reader which is close enough to ck.These four steps are usually enough for common RFID applications. However, steps (5)to (7) can be used by the reader as explained in Section 3.2.1, to modify all or part ofthe tag?s information or to access its memory [3, 4]. This protocol is very similar to theEPC Gen-2 protocol discussed in Section 3.2.1, except that the security of communicationsbetween the readers and the tags is increased in Gen-2+ by using an extra circuitry forcalculating the Hamming distance between two binary strings. There is also another costfor the increased security of the Gen-2+ protocol compared to the EPC Gen-2 protocol,and that is the high number of queries required to identify a communicating tag by alegitimate reader. It has been shown in [4] that approximately 15 queries are needed (onaverage) to identify a tag using the Gen-2+ protocol.3.3 Security and Privacy IssuesAlthough the protocols discussed in Section 3.2 are easy to implement and inexpensive,they are vulnerable to some attacks. We first define these attacks and then show how amalicious user can exploit them to interrupt each of the protocols discussed in Section 3.2.Below is a list of some simple and common attacks that can be carried against RFID77Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemssystems:? Tracking: under this attack, a malicious user who can passively eavesdrop on thecommunication between the tags and the readers or can actively interact with thetags, tries to trace a specific tag or to identify it among numerous tags, using theinformation sent by the tag over time.? De-synchronization: the main goal of this attack is to ruin the synchronization be-tween a legitimate reader and a tag, in order to prevent them from successfullycommunicating with each other. Moreover, this attack can be carried to prevent thereader from successfully updating the information (identification for instance) of atag after a successful communication.? Replay: under this attack, a malicious user eavesdrops on the communications be-tween a legitimate reader and a tag and saves the information sent by them. Theattacker uses this information later, i.e., it replays the saved information to commu-nicate with a legitimate reader or a real tag.? Denial of Service (DoS): the aim of this attack is not to obtain information about aspecific tag, but rather to ensure that a legitimate reader cannot communicate withthis tag any more. In order to launch this attack, the adversary needs to waste (use)some resources of the tag (or reader) which are necessary for their communication.? Impersonation: the objective of this attack is to obtain the information sent by atag and a legitimate reader during their communication. This information is thenused by a fake tag to convince the legitimate reader that it is communicating with aspecific real tag, and not a fake one.78Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems3.3.1 EPC Class-1 Gen-2 RFID ProtocolThe main advantage of the Gen-2 protocol is that it only relies on the capabilities of theEPC Gen-2 tags (PRNG and CRC-16 circuitries) and does not need additional hardwareequipments which increase the price of manufacturing RFID tags. Moreover, the readercan query a tag as much as it wants without worrying about the denial of service (DoS)issue. However, this protocol is vulnerable to some security threats. Using the abovedefinitions, some of the security drawbacks of the Gen-2 protocol are explained below:1. Revealing the information: any reader who can receive the RN16 message is ableto convince the tag to send its data in plain text by transmitting the ACK(RN16)message to the tag. Therefore, the Gen-2 protocol jeopardizes the costumers? privacyby revealing the information about their tag items.2. Tracking: it is possible to track a specific tag (and the costumer carrying that item)as the id is static and does not change over time. Therefore, any malicious readercan send the request message repeatedly and look for the tag that replies with theexpected id.3. Replay and Impersonation: any malicious reader can eavesdrop on the communica-tion between a real tag and a legitimate reader. This information can be stored ona fake tag and ?replayed? so as to mislead a legitimate reader or to ?impersonate?itself as the real one.4. De-synchronization: if a legitimate reader wants to obtain information about a tag,it sends the request message to the tag and this should be followed by the RN16reply from the tag. Now assume that an attacker sends another request message tothe tag after step (2). The attacker forces the tag to generate another RN16 thisway. The legitimate reader replies with the ACK(RN16) containing the previous79Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRN16 while the tag is expecting an ACK(RN16) containing the new RN16. Thisway, the attacker corrupts the synchronization between the tag and the legitimatereader. As a result, the tag does not reply to the received ACK(RN16) from thelegitimate reader and the communication fails.3.3.2 Henrici-Mu?ller RFID ProtocolThis protocol is simple, efficient, and can solve many security issues of RFID systems,however, it is vulnerable to some simple attacks that may jeopardize the privacy of RFIDusers. Below, we explain some of the security drawbacks of this protocol:1. Tracking (type I): In the Henrici-Mu?ller protocol, every time the tag receives a requestmessage, it increases the value of i by one, even if the session finally fails. However, i?is updated only if the session is successful and the reader is confirmed. Based on theabove, an attacker can interrogate a tag several times to abnormally increase i and?i. As can be seen in Fig. 3.2, ?i is sent to the reader in the second step. Therefore,an attacker is able to recognize its target by identifying and tracking the tag whichsends abnormally large values of ?i in response to requests by the attacker.2. Tracking (type II): An attacker can repeatedly send the request message to the nearbytags and looks for the h(id) in the received replies. The attacker can track a specifictag using its h(id) as it does not change over time. The tag remains vulnerable tothe tracking attack until a successful session is accomplished and its id is updated.3. De-synchronization (type I): After step (2) and before the legitimate reader sends rand h(r ? i ? id) to the tag, the attacker can send its own r? and h(r? ? i ? id) to thetag. The attacker does not know i and id separately but it knows h(i ? id) from thetag?s response in step (2). Therefore, the attacker can simply use the null element80Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems(r? = 0?) and send back the r? and h(r? ? i ? id) to the tag. As a result, the originalr and h(r ? i ? id) will not be accepted from the legitimate reader and it will bedesynchronized from the tag.4. De-synchronization (type II): In Henrici-Mu?ller protocol, when the legitimate readeris interrogating a tag, the attacker can interrogate this tag before the reader carriesout the third step. After receiving the request message from the attacker, the tagincreases i by one. Consequently, the hash value sent by the legitimate reader tothe tag is conceived as an incorrect response and will not be accepted (since the tagexpects to receive a hash value calculated from the newly increased i).5. Replay and impersonation: As mentioned before, a copy of the previous id is kept inthe database, so it is possible for the reader to communicate with a tag whose id hasnot been updated for any reason. Using this fact, an attacker can simply save andthen replay {h(id), h(i ? id),?i} to the legitimate reader to impersonate itself as thereal tag.3.3.3 Lim et al. RFID ProtocolsThe challenge-response trigger protocol proposed by Lim et al. can be attacked using somesimple tricks. Below, we explain some of the security drawbacks of this protocol:1. Replay and impersonation: for many RFID applications, it is a reasonable assumptionthat a tag may be captured and analyzed by an attacker. The attacker can interrogatethe captured tag for some values of R, and make a dictionary of these challenges andthe corresponding responses from the tag. The attacker can use this dictionary laterto masquerade and impersonate itself as the real tag for the legitimate reader.2. Tracking: the above mentioned dictionary can be used to track a specific tag. In81Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsorder to do that, the attacker would repeatedly send the request message and aknown challenge R to nearby tags, and look for the corresponding g(id, R) among thereceived responses (which is known from the dictionary). The tag remains vulnerableto the tracking attack in the challenge-response trigger protocol until a successfulsession is accomplished and its id is updated.3. De-synchronization: after sending the request message from the legitimate reader tothe tag in step (1) and before step (3), an attacker can repeat step (1) and sendanother request to force the tag to reset the random challenge R?. This new randomchallenge would be different from the previous one, which was sent to the legitimatereader. Therefore, the h(id ? R?) message which is made from the first challengewill not be accepted by the tag. The reader wrongly assumes that the id has beenupdated using the function f after sending h(id ?R?) in the third step.As in the case of the challenge-response trigger protocol, the forward rolling triggerprotocol has some security issues that may affect the privacy of RFID users. Below, weexplain some security drawbacks of this protocol:1. Limited number of sessions: for each tag, the total number of session requests thatcan be issued by the reader is limited to max, due to the fact that any i from the set{1, 2, 3, ...,max} can be used only once (for each tag). This limit applies to the casewhen the reader knows exactly which tag should be interrogated next. For example,assume that the reader has used i = 8 and L8 for tag A, and i = 3 and L3 for tagB, in its most recent interrogations with these tags. If the reader knows that it isgoing to interrogate tag A in the next session, any i from the set {9, 10, 11, ...,max}can be used to start the new session (as it had used i = 8 and L8 in the previoussession with tag A). For tag B, however, any i from the set {4, 5, 6, 7, 8, 9, ...,max}can be used if the reader knows it is going to interrogate tag B in the next session82Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems(as it had used i = 3 and L3 in the previous session with B). This is the best scenarioin which every i from the set {1, 2, 3, ...,max} can be used for each tag. However,the reader does not always know which tag is going to be interrogated in the nextsession. For example, in an RFID-based library, the reader should start the sessionfirst and wait for the RFID tag to answer and reveal its id [21]. For this type ofapplications, the reader has to increment i at each interrogation, therefore, the totalnumber of sessions for all tags (not each tag) is limited to max.2. DoS attack: the attacker may know the set of acceptable {i, Li} pairs (or a large pairof this set) from another RFID system or by tampering. In that case, the attackercan send i = max and Lmax to a tag and waste its previous pairs. This way, thetag loses its chance for communication with the legitimate reader in future sessionsbecause the condition (i? itag) > 0 is not satisfied anymore.3. De-synchronization: the (i ? itag) > 0 condition makes the protocol vulnerable toDoS attack as explained above. Moreover, the reader needs to be aware of the tagwhich is going to be interrogated next, and this is not a plausible assumption formany applications. On the other hand, if we remove the (i ? itag) > 0 condition,the protocol becomes vulnerable to de-synchronization and tracking attacks. Theattacker may listen to the communications between the tags and the reader in anotherRFID system, eavesdrop and save a valid (i, Li) pair, and use it for an RFID systemsomewhere else. For example, a legitimate reader may send a request along with anacceptable (i1, Li1) pair to a tag and the tag replies with {R?1, extid1 = g(id, i1)}. Atthis stage and before sending the rep message from the reader to the tag, an attackercan send another request with another acceptable (i2, Li2) pair to force the tag toreply with {R?2, extid2 = g(id, i2)} and this way, it ruins the synchronization betweenthe tag and the reader.83Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems4. Tracking: if we eliminate the (i ? itag) > 0 condition to prevent the DoS attack,an attacker can eavesdrop on the previous communications between the tag and thereader and use one of the previously used valid (i, Li) pairs to interrogate the tagagain. The tag replies with extid = g(id, i) and the attacker can track the tagby sending the request message repeatedly and tracking the tag which replies withextid = g(id, i). In other words, extid = g(id, i) is a static information and it can beused to track a tag before the third step (in which id is updated and extid = g(id, i)is changed).5. Impersonation: an attacker can eavesdrop on the communication between a legiti-mate reader and a tag, and extract a valid (i, Li) pair and its corresponding extid.Using the valid pair of (i, Li) and extid, and considering the fact that a copy of theprevious id and i? is kept by the reader until the next successful session, it is possiblefor the attacker to impersonate itself as a legitimate tag if the (i, Li) pair is usedagain by the reader (for interrogating other tags for instance).3.3.4 Tan et al. RFID ProtocolThis protocol is easy to implement, inexpensive, and does not rely on the database concept.Moreover, it has been shown that this protocol can resist the DoS, cloning, replay andphysical attacks [7]. However, it has some security issues which may be exploited by anattacker as shown below:1. De-synchronization: a malicious user can send a request message to the tag afterstep (3) and force it to generate a new challenge n?j. At this point, the reader waitsfor h(f(ri, tj))m and h(f(ri, tj)||ni||nj)? idj while the tag is expecting a new n?i andri as the third step. This way, the synchronization between the tag and the readeris corrupted and the session ends uselessly.84Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems2. Tracking: in step (4) of the explained scheme, h(f(ri, tj))m is a static form of datawhich can be used by malicious users to track the tag. Using this information,the attacker can find a specific tag among the other tags by repeatedly sending therequest message with a fixed ri and looks for the tag which replies with h(f(ri, tj))m.3. Impersonation: it is possible that an attacker captures a tag, repeatedly sends therequest message along with fixed values of ri and ni, and then stores the {h(f(ri, tj))m,h(f(ri, tj)||ni||nj)? idj} responses received for different values of nj. This procedureis then repeated by changing the value of ni. The attacker can make a table of theresponses for some values of ni and nj, and make a fake tag to impersonate it as areal one for a reader with ri.3.3.5 Sun et al. Gen-2+ RFID ProtocolThe Gen-2+ protocol is designed based on the capabilities of the standard EPC Gen-2RFID tags. Therefore, it does not require any modification in the hardware architectureof the tags. It is easy to implement and inexpensive. However, the Gen-2+ protocol hassome security problems as follow:1. Tracking: To obtain the id, an attacker needs to be able to provide an acceptable ck?and check for each RN16 it receives in step (2). It is proven in [4] that if an attackerrecords approximately 16,384 failed sessions between a reader and a tag and analysesthem, it may be able to track the tag using the additional information provided bythe check bits during the past 16,384 failed sessions. Moreover, a passive attackercan listen to the communication between the legitimate readers and the tags, andnotice the presence of a specific tag, as the id is sent in plain text in the Gen-2+protocol.85Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems2. Impersonation and replay: An attacker can eavesdrop on the communication betweena legitimate reader and a tag, and extract its id, RN16 and check. The attacker cansave this information on a fake tag. The fake tag then accepts any ck? it receives fromthe reader and sends its id in step (4) to impersonate itself. It should be noted thatthis attack is possible as long as the key-pool does not get updated by a legitimatereader.3. De-synchronization: An attacker can wait until a tag is interrogated by a legitimatereader and sends its RN16 and check in step (2). At this point and before thelegitimate reader calculates ck? and sends it to the tag, another request message canbe sent to the tag by the attacker. This way, the tag replies with another RN16 (orequivalently with another a and b) which points to a different location in the key-pool.As a result, the tag does not accept the ck? which was sent by the legitimate reader.In other words, the Gen-2+ protocol is vulnerable to de-synchronization attack.3.4 The New Light-weight Authentication ProtocolIn Section 3.2, we showed that none of the protocols proposed in [4, 5, 6, 7] are completelysecure, and explained how each of these protocols can be attacked. We also discussedabout the hardware limitations of RFID tags, and explained why sophisticated encryptionmethods are not appropriate for many RFID applications. After analysing the securitydrawbacks of the studied protocols and using what we learned from this study, we proposea new protocol in this section that provides a higher level of security for RFID communica-tion. In order to make the proposed protocol appropriate for real RFID applications, thelimitations of the hardware architecture and the cost of implementing RFID tags shouldbe taken into account as well. To address the hardware limitations of RFID tags, we take86Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsadvantage of the SQUASH message authentication method proposed by Shamir [98], anduse it as the method of hash function calculation in our proposed protocol. The SQUASHmethod not only provides an inexpensive way of calculating the hash functions needed forour protocol, but also improves the level of security in the proposed protocol, as we willexplain it later in Section 3.4.1.3.4.1 Why the SQUASH Method?Most of the recently proposed light-weight authentication protocols (including the proto-cols discussed in Section 3.2) use a one-way hash function h to provide the required secrecyfor the RFID protocols. However, there exist some strict limitations on the hardware ar-chitecture and the price of each manufactured tag that have rarely been considered andaddressed in recent works. It has been suggested that the price of each manufactured tagshould be less than 5 cents to be acceptable for the industry [12], and the final manufactur-ing price depends on the number of gates used in each tag. There are many hash functionsand security protocols that provide very high level of security, however, implementing thesefunctions on RFID tags increases the number of required gates and as a result, the price ofthe tags increases. As an example, the zero knowledge (ZK) interactive protocols are ableto prevent any leakage of information about the secret data, but they are too complicatedfor RFID tags [98]. In other words, we cannot expect sophisticated calculations from RFIDtags if we want to comply with the limitations on the architecture and the price of RFIDtags. Considering the above facts, many of the current hash functions and cryptographytools are not suitable for RFID tags. Therefore, we need to design (or use) an RFID spe-cific one-way hash function that takes the limitations of RFID systems into account andprovides the required security at the same time [100]. To address the hardware limitationsof RFID tags while providing the required security and privacy, some specifically designed87Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemshashing and encryption functions have been proposed in recent years. We can mentionHummingbird [101, 102, 103], GRAIN-128 [104], QUARK [105] and SQUASH-128 [98] assome of the best encryption schemes specifically designed for RFID tags.For RFID protocols, we need a one-way hash function h which can combine two piecesof information, the secret S and the non-secret NS information, and protect the secrecy ofS. This function must be able to hide S, but should not necessarily be a collision-resistantfunction since the discovery of a collision is not a security threat for challenge-responseRFID protocols. However, most of the standard hash functions, such as SHA-1, havebeen designed to resist collision attacks and prevent forgery of digitally signed documents.This is a very difficult requirement to satisfy and adds a lot of unnecessary complexityto the hardware implementation of the hash functions, making them too complicated forRFID tags. Finally, the hash function used for RFID applications should not depend onan internal source of random bits. Considering the above facts, Shamir proposed a newhash function, called SQUASH, which is ideal for challenge-response protocols in highlyconstrained devices like RFID tags [98]. The SQUASH function is completely deterministic,rather than probabilistic. Moreover, it can be easily implemented for different word sizesand does not need random bit generators. In addition to ease of implementation andhardware architecture, it has been proven that the SQUASH method is at least as secureas Rabin?s [106] public key encryption scheme, which has been investigated for more than30 years [98]. A reduced version of the SQUASH method, named SQUASH-128, has beensuggested in [98] for RFID applications. In SQUASH-128, the hash function has two 64-bit inputs (as S and NS), and generates a 32-bit hash value as the output. The publickey which is used in SQUASH-128 is n = 2128 ? 1. We take advantage of the SQUASH-128 method and use it as the hash function in our proposed light-weight authenticationprotocol.88Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems3.4.2 Reduced Version of the SQUASHConsidering the hardware and price limitations of RFID tags, Shamir modified the generalSQUASH scheme and designed an RFID-based hash function called SQUASH-128 [98]. Infact, the SQUASH-128 is a reduced version of the SQUASH method. For simplicity, we usethe word SQUASH to refer to the general SQUASH scheme in this chapter. The SQUASH-128 scheme does not need any source of randomness and there is no way a legitimate tagfails to convince a legitimate reader that it is authentic. The SQUASH-128 scheme iscapable of protecting privacy of the secret information S, even if the attacker has accessto h(S,NSi) for many known or chosen NSi. Below, we explain how the SQUASH andSQUASH-128 schemes can be implemented.Actually, the SQUASH method simplifies and speeds up the Rubin?s encryption scheme,and the SQUASH-128 is a modified and reduced version of the SQUASH scheme. The basicidea of SQUASH (and of course SQUASH-128) is to calculate a good approximation of theciphertext produced by Rabin?s encryption scheme, in a short window of bits (binarysequence representing the value that we want to calculate its hash). The SQUASH schemeworks based on the following equation:c ? m2 mod n (3.1)where m is the message to be encrypted (hashed), n is the key used for encryption and cis the ciphertext used for authentication. In the SQUASH method, a number of the formn = 2k ? 1 (called a Mersenne number) is used as the encryption key. This form of n canbe stored very compactly because its binary representation only uses k bits of 1?s. TheMersenne number of the form n = 2k ? 1 is not only easy to store, but also makes thecomputation of (3.1) pretty simple. Since 1 ? 2k mod n, we can only compute the double89Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemssized m2, and numerically add the lower half to the upper half of it to calculate (3.1). Moreprecisely, if n = 2k ? 1 andm2 = m2U ? 2k +m2L (3.2)where m2U indicates the higher half of m2 and m2L shows the lower half of m2, thenm2 ? (m2U +m2L) mod n. (3.3)For example, if m is equal to 5 (binary representation 101), then m2 is equal to 25 (binaryrepresentation 011001). Therefore, m2U = 011 and m2L = 001. Assuming that n = 7(k = 3), then 4 ? m2 mod n which can be calculated by adding 011 and 001 in the binaryform which results in 100.The tag does not really need to send all the bits of c to the reader to authenticate itself.It has been shown that only 32 bits of c is sufficient for this purpose if the attacker hasno prior information about the expected c [98]. Another useful point which can be used inimplementing the SQUASH scheme is that the tag can compute the successive bits of m2without storing all bits of the m sequence from the beginning of calculation. Instead, twostreams of bits can be convolved and generate the final m2 bit by bit. The tag calculatesbit j of m2L by summing all the products of mv ?mj?v for v = 0, 1, 2, ..., j and adding thecarry from the previous bit to this sum as below:m2j =j?v=0mv ?mj?v + rj?1 (3.4)where rj?1 shows the carry from the (j? 1)-th bit. To calculate bit j+ k in the upper halfof m2, the tag sums the product of mv ?mj+k?v for v = j +1, j +2, ..., k? 1 and adds the90Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemscarry from the previous bit to this sum as below:m2j+k =k?1?v=j+1mv ?mj+k?v + rj+k?1 (3.5)where rj+k?1 shows the carry from (j + k ? 1)-th bit [98]. In order to clarify the processrequired for calculating m2L and m2U , we consider the above mentioned example again(m = 5, k = 3, n = 7). Bits 0 to 2 of m2L is calculated using (3.4) as below:j = 0 ; m20 =0?v=0mv ?m?v ? (1 + r0) mod 2 (3.6)j = 1 ; m21 = r0 +1?v=0mv ?m1?v ? (0 + r1) mod 2 (3.7)j = 2 ; m22 = r1 +2?v=0mv ?m2?v ? (0 + r2) mod 2 (3.8)where r0 = 0, r1 = 0 and r2 = 1. Similarly, bits 3 to 4 are calculated using (3.5) as below:j + k = 3 ; m23 = r2 +2?v=1mv ?mj+k?v ? (1 + r3) mod 2 (3.9)j + k = 4 ; m24 = r3 +2?v=2mv ?mj+k?v ? (1 + r4) mod 2 (3.10)where r3 = 0 and r4 = 0. Therefore, m2L = 001, m2U = 011 and m2 = 011001. When the91Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemstag wants to calculate m2 mod n (where n = 2k ? 1), it needs to sum the upper half andthe lower half of m2. In order to do that, the j-th bit cj of c ? m2 mod n is calculated byadding bits j and j + k of m2, along with the carry bit.SQUASH-128 is exactly the same as SQUASH, except that it uses n = 2128?1 (k = 128)as the encryption key. It gets a 64-bit S (id for example) and a 64-bit NS (challenge forexample) and generates a 32-bit ciphertext. SQUASH-128 is more secure compared toRobin?s scheme, and no efficient attack on it is known [98]. The best attack on SQUASH-128 (if possible) would require exponential time and grows monotonically with the size ofn. Even finding the complete factorization of n = 2128?1 (if possible) does not necessarilymake the SQUASH-128 insecure in practice. In other words, even if an attacker canextract the arbitrary modular square roots mod n, it is not clear for him/her how to applythis operation when only a short window of bits in the middle of the Rabin ciphertextis available [98]. The security of the SQUASH-128 method and its robustness againstcommon attacks have been studied in more detail in [98]. More importantly, the SQUASH-128 can be implemented using approximately 1100 gates [98], which is almost one thirdof the gates required for Hummingbird (3220 gates) [101, 102, 103] and half of the gatesrequired for GRAIN-128 (2133 gates) [104] and QUARK (2296 gates) [105], while GRAIN-128, Hummingbird and QUARK are three of the smallest hardware oriented cryptographicschemes.3.4.3 The Proposed ProtocolIn this section, we propose a new RFID protocol which solves the security problems men-tioned in Section 3.2. This protocol is designed based on the challenge-response mechanismand uses the SQUASH-128 as the required one-way hash function. The principles of theproposed protocol is as follows: after the initialization phase, each tag contains its cur-92Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsRequestiidih D ),( o)( , * idirhr oo)( *irh o(1)(2)(3)(4)If correct:)(idfid ?ii ?*i Random Generate*iii -=Dr Random Generate*iii +D=If correct:)(idfid ?ii ?*Reader TagmaxtmaxtmaxtFigure 3.7: The proposed light-weight authentication protocol for RFID communications.rent identifier id, the current session number i and the last successful session number i?.Similarly, the database contains a list of all the identifiers and the last successful sessionnumbers for all the tags in the system. In this scheme, both the database and the tagsare aware of the hash function h. The communication process is shown in Fig. 3.7 andfollows the steps below:1. The reader sends a request message to the tag to start a new session. After sendingthe request message, the maximum time tmax that the reader waits for a valid replyby the tag is t. The reader resends the request message if a valid reply is not receivedin time t or if the received reply is not valid.2. The tag generates a random integer number for i and calculates ?i by subtractingthe last successful session number i? from i. It also calculates h(i ? id) and sends itto the reader along with ?i. Here, ? is a suitable conjugation function as in Sections93Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems3.2.2 and 3.2.3, and SQUASH-128 is used for h. The maximum time tmax that thetag waits for a valid reply by the reader is t.3. The reader forwards the information received in step (2) to the database, where i iscalculated using the received ?i and the stored i?. The database checks all of then entries and finds the tag whose id and i results in h(i ? id). It then generates arandom challenge r, calculates h(r ? i? ? id), and sends the r and h(r ? i? ? id) tothe tag via the reader. After sending the information in the third step, the readerwaits at most for t seconds to receive a valid reply by the tag. The reader resendsthe request message if a valid reply is not received in time t or if the received replyis not valid.4. The queried tag calculates h(r ? i? ? id) using the i? and id it knows and the challenger it has received from the reader, and compares it with the one sent by the reader.If they match, the tag changes its previous id using a function f which is known byboth the tags and the database. It then calculates h(r ? i?) and sends it to the readeras the acknowledgement of changing the old id.5. After receiving the h(r? i?), the database calculates the tag?s new id using the knownfunction f and updates its list. It also updates the last successful session i? with ias the final step.We assume that the tags are close enough to the reader and they receive enough energy(from the reader) to back-scatter. We also assume that we have ideal communicationsenvironment, meaning that if the reader sends a message to a tag or a tag sends a messageto the reader, the transmitted message is received correctly.To provide the required security of the communication between the tags and the reader,our proposed protocol takes advantage of two main algorithms. Algorithm 3.1 is used by94Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsAlgorithm 3.1 The sequence of procedures used by the reader in the proposed light-weightauthentication protocol.1: Input id and i? for all the tags in the system2: Input n and tmax3: Send a Request message4: for time = 0 : tmax5: Wait for {h(i ? id),?i}6: if {h(i ? id),?i} is received7: for j = 1 : n8: Calculate ij = ?ij + i?j9: if h(ij ? idj) = h(i ? id) (the received {h(i ? id),?i} is correct)10: Save j11: Generate random r12: Send r and h(i ? i?j ? idj) to the tag13: Break the loop (go to line 19)14: end if15: end for16: end if17: end for18: Go to line 319: for time = 0 : tmax20: Wait for {h(r ? i?)}21: if {h(r ? i?)} is received22: if h(r ? i?j ) = h(r ? i?) (the received {h(r ? i?)} is correct)23: idj ? f(idj)24: i?j ? ij25: Update the list26: Break the loop (go to line 31)27: end if28: end if29: end for30: Go to line 331: Terminate the algorithmthe reader and Algorithm 3.2 is used by the tags. In Algorithm 3.1, n indicates the totalnumber of tags present in the system, tmax shows the maximum waiting time, and index jrefers to the tag whose i and id satisfy the criterion examined by the database.Having explained our proposed protocol, we now consider the security threats men-tioned in Section 3.2 and show the security improvements offered by the new protocol. Wecan mention the following improvements compared with the Henrici-Mu?ller and Lim RFIDprotocols:1. Unlike the challenge-response trigger protocol, it is not possible for an attacker to95Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsAlgorithm 3.2 The sequence of procedures used by the tags in the proposed light-weightauthentication protocol.1: Wait for the Request message2: if the Request message is received3: Generate a random i4: Calculate ?i = i? i?5: Send {h(i ? id),?i} to the reader6: end if7: for time = 0 : tmax8: Wait for a message9: if the Request message is received10: Break the loop (go to line 3)11: else if the {r, h(r ? i?j ? idj)} message is received12: if h(r ? i?j ? idj) = h(r ? i? ? id) (the received {r, h(r ? i?j ? idj)} is correct)13: id? f(id)14: Send h(r ? i?) to the reader15: i? ? i16: Break the loop (go to line 21)17: end if18: end if19: end for20: Go to line 321: Terminate the algorithmmake a dictionary of the inputs and use it to interrogate the tags, impersonate themas the legitimate tags or to track an interrogated tag. The reason is that the readerdoes not use any challenge in step (1) of Fig. 3.7, and the response of the tag in step(2) is changed dynamically over time because of the random nature of i which makesit impossible for the attackers to track a static h(i ? id).2. Unlike the Henrici-Mu?ller protocol, the value of i does not increase over time butchanges randomly (it may increase or decrease) for each request message. Therefore,it is not possible for an attacker to abnormally increase the value of ?i and track thetarget tag using this large value.3. Unlike the Henrici-Mu?ller and the challenge-response trigger protocols, it is not pos-sible to track a tag based on the static information it sends. The reason is that ichanges randomly after each request message in step (1), therefore, each time the96Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsh(i ? id) and ?i are different from the previous time (after each interrogation).4. Unlike the Henrici-Mu?ller, the challenge-response trigger and the forward rollingschemes, it is not possible for an attacker to corrupt the synchronization betweenthe interrogated tag and the reader after step (1) and before step (3). The reasonis that in the third step, the reply from the reader depends on i?, not i nor thechallenge sent from the tag to the reader in step (2). For example, assume thatthe legitimate reader sends a request message to a tag and receives ?i1 = i1 ? i?,but before step (3), an attacker sends another request message to the tag as well.In this case, ?i2 = i2 ? i? is generated and sent by the tag but i? and id are notchanged. The legitimate reader finds the interrogated tag in its database list usingh(i1 ? id) and replies with r and h(r ? i? ? id). The response does not depend on i1 ori2 but only depends on i?. On the other hand, the attacker cannot send the correcth(r ? i? ? id) as it does not have access to i?. Therefore, the synchronization betweenthe tag and the reader is not affected by this attack. From another point of view,the attacker cannot de-synchronize the reader and the tag by sending a fake patternof the {h(i ? id),?i} to the reader in the second step. This is because of consideringthe tmax in the algorithm. After sending the request message in the first step, thereader waits for a maximum of tmax to receive a valid reply from the tag. If the readerreceives a valid {h(i ? id),?i}, it simply goes to the third step and sends back the{r, h(r ? i? ? id)}. However, if an attacker sends an invalid {h(i ? id),?i} before thelegitimate tag replies, the reader checks the received information and after findingthat the received {h(i ? id),?i} is invalid, it still waits for tmax seconds and givesthe legitimate tag the chance to send its valid {h(i ? id),?i} (Algorithm 3.1 line 4).The same mechanism is used to guarantee that the attacker cannot de-synchronizethe reader and the tag by sending a fake {r, h(r ? i? ? id)} to the tag in the third step97Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systems(Algorithm 3.2 line 7) or by sending a fake h(r ? i?) to the reader in the fourth step(Algorithm 3.1 line 19).5. Unlike the forward rolling trigger scheme, the number of sessions between the tagand the reader is not limited in the proposed protocol because this protocol onlyuses a simple one-way hash function and does not rely on Lamport?s authenticationmethod [99].6. Unlike the Henrici-Mu?ller scheme, the attacker cannot use the null element for thechallenge r in step (3) of the proposed protocol because the attacker cannot obtainthe value of h(i? ? id) from h(i ? id) in step (2).7. The proposed method is robust against the replay attack. An attacker can capture atag and interrogate it, but it can only obtain h(i ? id) and ?i. The attacker can usethis information to reply to a request message from the legitimate reader in step (2)of the proposed protocol, but it cannot impersonate itself to the reader as the readerwaits for the h(r ? i?) response from the attacker in step (4). On the other hand,the attacker cannot obtain any knowledge about i? by interrogating a captured tag.The attacker cannot send the correct h(r ? i?) to the reader and the reader does notupdate the identification of the tag in the database list. Therefore, the replay attackcannot affect the proposed protocol.8. In the proposed protocol, only the most recent and updated id is kept and theprevious id is deleted from the database list after receiving the h(r ? i?) messagein step (4). Therefore, attackers cannot eavesdrop on the communication betweena legitimate reader and a real tag to use it for misleading the reader. After eachsuccessful session, the id is updated and therefore, the information in step (2) ofFig. 3.7 will not be accepted anymore by the database.98Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsTable 3.1: Security comparison of the proposed protocol and the light-weight authentica-tion schemes explained in Section 3.2.Protocol\Attack Tracking De-synchronization Replay DoS ImpersonationStandard Gen-2 [4] No No No Yes NoHenrici-Mu?ller [5] No No No Yes NoChallenge-Response Trigger [6] No No Yes Yes NoForward Rolling Trigger [6] No No Yes No NoServer-less Method [7] No No Yes Yes NoGen-2+ [4] No No No Yes NoProposed method Yes Yes Yes Yes YesIn this chapter, we aimed to propose a new RFID protocol which solves the security andprivacy issues of the protocols introduced in [3, 4, 5, 6, 7], and to improve the reliabilityof the reader-tag communication in the RFID systems. We simply showed that unlikethe previously discussed schemes, our proposed protocol is not vulnerable to tracking, de-synchronization, replay, DoS and Impersonation attacks. Formal cryptographic analysisof the schemes introduced in [3, 4, 5, 6, 7] and the proposed protocol is beyond the scopeof this chapter, however, there exist many cryptographic frameworks that can be used toevaluate these protocols [107, 108, 109, 110].3.5 SummaryIn this section, we compare the security aspects of the proposed protocol with the standardGen-2 method [3] and the five light-weight authentication schemes [4, 5, 6, 7] explainedin Section 3.2. Besides the security aspects, the complexity and computational costs arecompared. We show that the proposed protocol does not impose too much computationaldemand on the RFID tag while significantly improving the security of RFID systems.Table 3.1 compares our proposed protocol with the schemes discussed in Section 3.2, andconfirms the robustness of the proposed protocol against the studied attacks. In this table,tracking, de-synchronization, replay, DoS, and impersonation are considered as common99Chapter 3. Toward a Light-weight Authentication Protocol for RFID SystemsTable 3.2: Complexity comparison of the proposed protocol and the light-weight authen-tication schemes explained in Section 3.2.Protocol ComplexityStandard Gen-2 [3] 2?Henrici-Mu?ller [5] 4?+2?Challenge-Response Trigger [6] 3?+?+2?Forward Rolling Trigger [6] 4?+?Server-less Method [7] 3?+?+4?Gen-2+ [4] 2?+?+?Proposed method 4?+?+3?RFID threats that may affect the light-weight authentication protocols. These attacksare defined in Section 3.2. For each attack, the word ?Yes? shows that the consideredprotocol is robust against that attack while ?No? means that the protocol is vulnerable tothat attack. As can be inferred from Table 3.1, the standard Gen-2 [3], Henrici-Mu?ller [5],challenge-response trigger [6], forward rolling trigger [6], server-less method [7], and Gen-2+ [4] protocols are all vulnerable to the tracking, de-synchronization, and impersonationattacks. The challenge-response trigger, forward rolling trigger and server-less schemes,however, can resist the replay attack, and DoS is a problem only for the forward rollingtrigger protocol. On the other hand, the proposed method can provide robustness againsttracking, de-synchronization, replay, DoS, and impersonation attacks.As explained before, the more computationally demanding a protocol is, the less at-tractive it is for real RFID applications. Therefore, the complexity and computationaldemand of the protocol should be considered as an important factor when designing anRFID communication scheme. The main bottleneck in designing RFID protocols is thelimitation in the computational ability of the tags and not the readers, as the readers cantake advantage of advanced processors. In this study, we only consider the computationsperformed by the tags and neglect the computational costs of the reader. Table 3.2 com-pares the computational costs for each of the six RFID schemes, as well as our proposedprotocol. In order to make a fair comparison of the complexity and computational costs,100Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemswe denote the computational cost of each hash function by ?, each random generation by?, each conjugation or concatenation function by ?, and each Hamming distance calcu-lation by ?. No matter which hash function is used, it would be a plausible assumptionthat ? has the most impact on the total computational costs among ?, ?, ? and ?. As anexample, it can be shown that each round of calculating ? using the Hummingbird schemeneeds 8 modulo 216 addition, 80 XOR and 80 S-box calculation. As another example, eachround of calculating ? using the SQUASH-128 scheme needs one modulo 2128?1 addition.It should be noted that among all the compared schemes, the proposed protocol is theonly one that takes advantage of the SQUASH-128 method. As a result, it imposes the low-est computational cost on the tags for hash calculation. In order to have a completely faircomparison, however, we consider the case where all the discussed protocols are assumed tohave used the SQUASH-128 method. This way, we assume that for each hash calculation,all the compared protocols have the same computational cost of ?. As can be inferred fromTable 3.2, the standard Gen-2 protocol has the lowest computation demands. Except forthe Gen-2 and Gen-2+ schemes, the other protocols need at least three hash computationsand the only scheme that needs an extra circuitry for calculating the Hamming distanceof two binary strings is Gen-2+. Finally, all the protocols except the standard Gen-2 andthe forward rolling trigger need to perform at least one conjugation or concatenation. Itcan be inferred from Table 3.2 that the proposed protocol does not impose a significantamount of computational costs on the tags. Having an extra simple circuitry (to calculatea hash function or a Hamming distance) seems to be a plausible and necessary assumptionfor increasing the security of communication between the tags and the readers, as discussedin [4, 5, 6, 7, 19, 22, 97]. Among the six schemes discussed in Sections 3.2.1 to 3.2.5 andthe one we proposed in Section 3.4.3, only the server-less protocol proposed by Tan et al.[7] does not depend on the direct access to a central database. Finally, it should be noted101Chapter 3. Toward a Light-weight Authentication Protocol for RFID Systemsthat except for the new proposed protocol, all the discussed protocols are vulnerable totracking, de-synchronization and impersonation attacks.In the proposed light-weight authentication protocol, we take advantage of the SQUASH-128 hash function. The main reasons that we choose SQUASH-128 are ease of implemen-tation (in terms of the number of required gates), suitability for RFID applications anddifficulty of breaking SQUASH-128. However, it should be noted that any other efficienthash function can be used in the proposed authentication protocol. The use of SQUASH-128 can also be beneficial to other studied protocols which use hash functions.We do not claim that the proposed protocol can resist all possible attacks and securitythreats, however, it was shown that the proposed protocol improves the security of com-munication between the readers and the tags in RFID systems, and solves many securityissues of the schemes proposed in [3, 4, 5, 6, 7].102Chapter 4Probabilistic Tag Estimation Method4.1 IntroductionAn RFID system consists of one (or more) reader(s) and a certain number of tags. Thereader communicates with the tags to retrieved their data. Due to the shared natureof the communication channel, packet collisions occur when multiple tags simultaneouslytransmit their data to the reader. Therefore, an efficient anti-collision protocol is of greatimportance to save the bandwidth and energy needed and to reduce the identification delaysin RFID systems. Many anti-collision protocols have been proposed to solve the collisionproblem in RFID systems. These protocols can be generalized into two main groups; thetree-based protocols and the ALOHA-based protocols. The tree-based protocols dividea set of tags into two subsets in each step until there is only one tag left. In ALOHA-based protocols, the tags transmit their data at random during the time frames previouslyassigned to all tags by the reader. The ALOHA technique has a series of variants such aspure ALOHA (PA), framed slotted ALOHA (FSA) and dynamic framed slotted ALOHA(DFSA). Among them, the DFSA technique is the most efficient one since it adjusts theframe size prior to each query [111]. For DFSA-based protocols, it has been shown thatthe maximum throughput is achieved when the frame size is equal to the number of tagsin the system [2, 93, 111, 112]. Therefore, we need to have an accurate tag estimatemethod to be able to design more efficient DFSA-based protocols. Estimating the numberof RFID tags (and accordingly the number of objects) in an area of interest is also one103Chapter 4. Probabilistic Tag Estimation Methodof the primary tasks in many applications, such as counting the number of conference orexhibition attendees with RFID badges [93], verifying the number of products with RFIDlabels in cargo shipping at the airport [113], etc. The problem of estimating the numberof RFID tags can be easily reduced to identifying the IDs of all RFID tags and countingthem. As mentioned before, there are a number of schemes proposed for solving the tagidentification problem and they can be directly borrowed to compute the exact number ofRFID tags when the size of the RFID system is small. Those solutions, however, becomeinfeasible when the RFID system scales up [114].It is not always necessary to know or count the exact number of tags in an RFID system.For many application scenarios, knowing the approximate number of tags in the systemis adequate. Moreover, since each tag ID is linked to a specific object or person, it is notalways allowed to use the tag IDs directly for counting the number of tags for securityand privacy reasons. For instance, the attendees of an exhibition may not wish to revealwhich of the service providers they were interested in when visiting the exhibition, or theattendees of a conference may not like to reveal the name of the sessions they attendedduring their visit [10]. Therefore, in many cases we need some alternative approaches toestimate the number of tags in an area of interest without directly reading all the tag IDs.In accordance with this need, a set of probabilistic counting schemes have been proposedto estimate the approximate number of tags in the RFID systems [2, 10, 72, 93, 115, 116].In [2], Chen proposed a novel tag estimation algorithm for the ALOHA-based anticol-lision protocols. In this approach, the reader estimates the number of remaining tags inthe RFID system after each interrogation based on a posteriori probability and uses thisestimated number to determine the number of required time slots for the next interroga-tion. This approach can improve the performance of the ALOHA-based RFID anticollisionalgorithms. However, there exists an error in the probabilistic modeling of the problem.104Chapter 4. Probabilistic Tag Estimation MethodIn this chapter, we take advantage of the probabilistic model we developed in Chapter 2and correct the tag estimation method proposed by Chen [2]. Briefly, the contributions ofthis chapter are as follows:? We first show that the probabilistic model proposed in [2] is incorrect. We thenpresent the correct probabilistic model.? Our proposed model is validated via simulation. We also compare the simulationresults with the model suggested in [2] and our proposed model. The results fromour probabilistic model closely match with the simulation results.? The consequences of using the model suggested in [2] are shown and the requiredcorrections are identified.The rest of this chapter is organized as follows: Section 4.2 summarizes the probabilisticmodel proposed in [2] and discusses its problem. The correct probabilistic model for theALOHA-based RFID systems is presented in Section 4.3. Some validating simulationresults and the corrections required for the probabilistic model proposed in [2] is providedin Section 4.4, followed by the summary in Section 4.5.4.2 Probabilistic Model Proposed by ChenIn this section, we summarize the probabilistic model proposed in [2]. In ALOHA-basedRFID systems, the time frame is divided into time slots. Each tag chooses one of thesetime slots randomly and transmits its ID in the reply message. In each time slot, threeevents may happen. If only one tag chooses a specific time slot and transmits its ID, thenthe transmission is successful. This time slot is called a single time slot. If more than onetag selects a specific time slot, then a packet collision will occur and the reader will not105Chapter 4. Probabilistic Tag Estimation Methodbe able to decode the received signal. This is called a collided time slot. Finally, if notag chooses a specific time slot, the reader will observe an empty time slot. If the readerchooses the number of slots in a frame to be much higher than the number of tags, thenthe channel capacity is wasted and the reader will observe multiple empty time slots. Onthe other hand, if the reader chooses the frame size to be much smaller than the numberof tags, then the chance of collision will increase. It has been proved that for optimalperformance, the number of time slots in a frame is equal to the number of tags in thesystem [2, 93, 111, 112].A probabilistic model for ALOHA-based RFID systems was proposed in [2]. In thatmodel, the reader first selects a predefined number of time slots (128) to be the frame size.It then transmits a query message. Each tag randomly chooses a time slot and sends itsreply in that time slot. After the first interrogation, the reader estimates the number of tagsn? in the system, based on the maximum a posteriori probability obtained from the numberof empty (E), single (S) and collided (C) time slots. Then, the reader selects the framesize to be equal to (n? ? S) and proceeds with the next interrogation. At the end of eachinterrogation, the values of n?, E, S and C are being updated. This procedure continuesuntil all the tags are identified in the system. In each interrogation, the summation of E,S and C is equal to L, which is the total number of time slots in the frame.In [2], Chen suggested to first calculate the probability of observing E empty, S singleand C collided time slots, P (E, S, C), and then find the n? which maximizes this probabilityfor each interrogation. He mentioned that in an RFID system containing n tags, the numberof tags allocated in a time slot is a binomial distribution with n Bernoulli experiments and1L as the occupied probability. The probability of finding r tags in a time slot is given by[2]B(r) =(nr)(1L)r (1? 1L)n?r, 0 ? r ? n . (4.1)106Chapter 4. Probabilistic Tag Estimation MethodThe probability of observing an empty slot, a single slot, and a collided slot can be obtainedrespectively as [2]pe = B(0) =(1? 1L)n, (4.2)ps = B(1) =nL(1? 1L)n?1, (4.3)pc = 1? pe ? ps. (4.4)In the next step, the probability of observing E empty, S single and C collided timeslots, P (E, S, C), was derived. In [2], the the problem was modeled as a multinomial dis-tribution with L repeated independent trials (choosing a time slot by a tag), where eachtrial can result in an empty, single or collision event. However, these events are not inde-pendent, that is, the probability of observing E empty time slots affects the probability ofobserving S single time slots, and these two probabilities affect the probability of observingC collisions. Based on the wrong assumption mentioned, P (E, S,C) was calculated in [2]asP (E, S, C) = L!E!S!C![(1? 1L)n]E[nL(1? 1L)n?1]S?[1?(1? 1L)n? nL(1? 1L)n?1]C.(4.5)After finding P (E, S,C), Chen?s algorithm finds n? which maximizes P (E, S,C). That isn? = argmaxn P (E, S, C). This n? is considered as the estimation of n, which is the numberof tags remained in the system. The algorithm proposed in [2] is shown in Algorithm 4.1.Although the approach proposed in [2] is rational, the results are inaccurate due to thementioned mistake in calculating P (E, S,C). Based on the above, a correct probabilistic107Chapter 4. Probabilistic Tag Estimation MethodAlgorithm 4.1 The anticollision algorithm used in [2]1: L := 1282: Initialize E, S and C (C 6= 0)3: counter := 04: while C 6= 05: Interrogate all tags6: counter := counter + 17: update E, S and C8: n? := argmaxn P (E,S,C)9: L := n?? S10: end whilemodel for ALOHA-based RFID systems is needed. By using the correct model and theapproach proposed in [2], the reader would be able to estimate the number of tags in thesystem accurately and assign an appropriate number of time slots in the frame for the nextinterrogation.4.3 Correct Probabilistic Model of the ALOHASystemsAs explained in Section 4.2, the formulation proposed in [2] is incorrect because it isassumed that the events of observing empty, single and collided time slots are independentfrom each other. This assumption is not valid and the mentioned events are dependent oneach other. In this section, we take advantage of the probabilistic model we developed inChapter 2 and present the correct derivation of the probability P (E, S,C).We need to model our system mathematically and find the probability of observing aspecific frame structure (E empty, S single and C collided time slots). We consider a framestructure which has E empty slots in its first section, S single slots in the second section,and C collided slots in the last section, as it is depicted in Fig. 4.1. In this figure, eachsmall circle in a time slot represents a single tag which has sent its ID in that time slot.Therefore, empty time slots are shown without any circle, single time slots are shown with108Chapter 4. Probabilistic Tag Estimation Method. . .. . . . . .E S CLFigure 4.1: The empty, single and collided sections of a time frame in the analytical model.one circle, and collided time slots are shown with multiple circles inside them.In the model, the frame length is equal to L, while n represents the number of remainingRFID tags in the system. First, the probability of observing E empty slots in the first partof the frame is considered. This probability is denoted by P1(E) and is equal toP1(E) =(1? EL)n, 0 ? E ? L . (4.6)In the next step, the probability of observing S single time slots in the second part ofthe frame conditioned to observing E empty slots in the previous step is considered. Thisprobability is denoted by P2(S | E)P2(S | E) =(nS)(SL? E)S (1? SL? E)(n?S)?(S?i=0(?1)i(Si)(1? iS)S),0 ? S ? min{L? E, n}(4.7)where( SL?E)S is the probability that S tags are assigned to the first S slots among thetotal remaining (L ? E) slots,(1? SL?E)(n?S) shows the probability that the remaining(n ? S) tags are assigned to the remaining (L ? E ? S) slots, and finally the summation?Si=0(?1)i(Si) (1? iS)S is the probability that the mentioned S tags are assigned to S slots,109Chapter 4. Probabilistic Tag Estimation Methodwith no basket empty, or in other words, each of the S slots only accommodates one and onlyone of the S tags (same as the classical urn model). The summation?Si=0(?1)i(Si) (1? iS)Scan be simplified asS?i=0(?1)i(Si)(1? iS)S= S!SS. (4.8)Based on the above, P2(S | E) can be written asP2(S | E) =(nS)(SL? E)S (1? SL? E)(n?S) S!SS=(nS)((L? E ? S)(n?S)(L? E)n)S! . (4.9)Now, we need to calculate the probability of observing C collisions in the last section ofthe frame conditioned to observing E empty and S single time slots in the previous steps.For P3(C | E, S), it is not that simple to calculate the probability of observing C collisionsconditioned to E and S directly. Therefore, we define a class of acceptable events whichrepresents different ways of distributing (n?S) tags in C slots such that each slot containsat least two tags. By defining the number of these acceptable events as gn?S(C, 2), we haveP3(C | E, S) =gn?S(C, 2)C(n?S), (4.10)in which C(n?S) is the total number of ways that we can assign (n?S) tags to the remainingC time slots. Now, the main problem is to determine gn?S(C, 2). Riordan [96] suggestedtwo closed form expressions for g?(m, s) using the classical urn model in which ?, m ands denote the number of balls, the number of urns, and the minimum number of balls ineach urn, respectively. The first closed form expression for g?(m, s) isg?(m, s) = mg??1(m, s) +m(?? 1s? 1)g??s(m? 1, s), (4.11)110Chapter 4. Probabilistic Tag Estimation Methodand the second one isg?(m, s) =m?k=0(?1)k(mk)?!(s? 1)!k(?? sk + k)!? g??sk+k(m? k, s? 1).(4.12)Using Eq. (4.11) and (4.12), we can find the exact number of acceptable events in Eq.(4.10) by replacing ? with (n ? S), m with C and s with 2 for our problem. The aboverecursive equations can be calculated in two different ways. In the first approach, we canonly use Eq. (4.11) and combine it with three simple logical constraints, as stated below:a) if (? 6= 0) and (m = 0), then g?(m, s) = 0 ;b) if (? < ms), then g?(m, s) = 0 ;c) if (m = 1) and (? 6= 0) and (? ? ms), then g?(m, s) = 1.Using this method, we can start from an initial point and find the exact value for g?(m, s)recursively. As the second approach, we can simplify Eq. (4.12) by replacing s with 2 andwriteg?(m, 2) =m?k=0(?1)k(mk)?!(?? k)!g??k(m? k, 1) (4.13)in whichg??k(m? k, 1) = p0(?? k,m? k) (m? k)(??k) , (4.14)and p0(? ? k,m? k) is the probability that we have (? ? k) tags and (m? k) time slotsand all the slots contain at least one tag. From [95], we have the mathematical expressionfor p0(?? k,m? k) asp0(?? k,m? k) =m?k?v=0(?1)v(m? kv)(1? vm? k)(??k). (4.15)111Chapter 4. Probabilistic Tag Estimation MethodBy substituting Eq. (4.14) and (4.15) into Eq. (4.13), we haveg?(m, 2) =m?k=0m?k?v=0(?1)(k+v)(mk)(m? kv)? ?!(?? k)!(m? k ? v)(??k) .(4.16)Based on the above, Eq. (4.10) can be written asP3(C | E, S) =C?k=0C?k?v=0(?1)(k+v)(Ck)(C ? kv)? (n? S)!(n? S ? k)!(C ? k ? v)(n?S?k)C(n?S).(4.17)Using Eq. (4.6), (4.9), (4.10) and (4.16) or (4.11), we can determine P (E, S, C), whichis the probability of observing E empty, S single and C collided slots asP (E, S,C) =(L!E! S! C!)P1(E) P2(S | E) P3(C | E, S) . (4.18)In Eq. (4.18),( L!E! S! C!)is the number of ways that the three mentioned sections in Fig. 4.1can be scrambled and mixed with each other and make a random structure of E empty,S single and C collided time slots. As it can be observed from Eq. (4.18), the probabilityP (E, S,C) is a product of three other probabilities which are related to each other. Thecorrect formula for calculating P (E, S, C) is Eq. (4.18), which is different from Eq. (4.5).4.4 Performance EvaluationIn this section, we show that Eq. (4.5) is not confirmed by simulations while Eq. (4.18)agrees with the simulation results. Based on the new formulation, some of the figures in[2] need to be changed. These corrections are also provided in this section.112Chapter 4. Probabilistic Tag Estimation Method0 5 10 15 20 25 30 35 40 45 5000.050.10.150.20.250.30.35Number of TagsP(E,S,C)Eq. (4.5)Eq. (4.18)SimulationL = 10, E = 4, S = 4, C = 2L = 10, E = 1, S = 3, C = 6L = 10, E = 3, S = 3, C = 4Figure 4.2: A posteriori probability distributions using Eq. (4.5) from [2], Eq. (4.18), andthe actual probabilities for a simulated RFID system.Fig. 4.2 shows the probability P (E, S,C) obtained using Eq. (4.5) which was proposedin [2], the correct formula shown in Eq. (4.18), and the actual probability obtained viasimulation. For the simulation, we used MATLAB and obtained the probability P (E, S,C),using 10,000 iterations. The probabilities are plotted for three cases, (L = 10, E = 4,S = 4, C = 2), (L = 10, E = 3, S = 3, C = 4) and (L = 10, E = 1, S = 3, C = 6). Theprobabilities obtained via simulation are then compared with the probabilities obtainedfrom Eq. (4.5) as well as the probabilities obtained from Eq. (4.18). As it can be inferredfrom Fig. 4.2, Eq. (4.5) does not match with the results obtained from simulating an RFIDsystem. The peaks obtained from Eq. (4.5) are lower than the simulated system and atsome points, these peaks occur with one unit shift to the right on n axis comparing to the113Chapter 4. Probabilistic Tag Estimation Methodsimulated system. On the other hand, the probabilities obtained from Eq. (4.18) matchwith the simulated system. The peaks of P (E, S, C) happen with the same heights andwithout any shift comparing to the simulated system.We can also conclude that Eq. (4.5) is incorrect from Fig. 4.2 without relying on thesimulated RFID system. If we observe P (E, S,C) plotted for (L = 10, E = 4, S = 4,C = 2) and obtained from Eq. (4.5) at point n = 5, we can notice a positive value whichis logically impossible. This probability should be equal to 0 because it is not possible toobserve E = 4, S = 4, C = 2 while we have only n = 5 tags in the system. Logically,P (E, S,C) should be equal to 0 for values of n less than 8.As another correction, a table was presented in [2] which showed the estimated numberof tags for an RFID system (TABLE I in [2]). In this table, the number of tags wereestimated based on a posteriori probability scheme for different values of S and C. Wechecked the values obtained from Eq. (4.18) with the values obtained from Eq. (4.5).Although the heights of the peaks for Eq. (4.18) and (4.5) are different, the values of nwhere the peaks happen are the same in some cases. However, in some other cases, thevalues of n where the peaks happen are different for Eq. (4.18) and (4.5). The correctvalues of estimated n are presented in Table 4.1. The numbers shown in bold red colorTable 4.1: Correct values of the estimated n (number of tags) for the algorithm in [2](L = 10)C0 1 2 3 4 5 6 7 8 9S1 2 3 4 5 6 7 8 9 10 112 4 5 6 7 8 9 10 11 12 -3 6 7 8 9 11 12 13 14 - -4 9 10 11 12 14 15 16 - - -5 12 13 14 16 17 19 - - - -6 15 17 18 20 21 - - - - -7 20 21 23 25 - - - - - -8 26 28 30 - - - - - - -9 35 38 - - - - - - - -10 50 - - - - - - - - -114Chapter 4. Probabilistic Tag Estimation Method(bold gray color in black and white print) are different from those calculated by Chen in [2]while the numbers in black color are the same for both Eq. (4.5) and (4.18) and therefore,they are the same as the values shown in [2].4.5 SummaryIn this chapter, we showed that the tag estimation proposed by Chen [2] is incorrect.Using the probabilistic model we developed for ALOHA-based RFID systems in Chap-ter 2, we corrected the probabilistic tag estimation method proposed in [2]. The modifiedprobabilistic model was verified via simulations and compared with the one proposed in[2]. Simulation results confirmed that our modified probabilistic tag estimation methodcompletely matches the results of real ALOHA-based RFID systems.An ideal ALOHA-based RFID system has been modeled in [2] and modified in thischapter, however, there exist some other technical aspects that can be targeted for futureworks and further contributions. For instance, in our modified probabilistic tag estimationmethod and the one proposed in [2], it has been assumed that the length of the E, Sand C time slots are all equal in ALOHA-based RFID systems, while the length of theseslots might be different in some specific types of ALOHA-based RFID protocols [90]. Asanother example, it has been assumed that the reader does not make any mistake indeciding whether a time slot is singly occupied or collided. However, this may not bealways true because of some technical issues. Some of the time slots which are interpretedas singly occupied can actually be collided slots [117, 118]. Moreover, it has been assumedthat if a tag transmits its data in a single slot, the reader will receive this data for sure.In other words, the probability of transmission error has been considered to be zero in theideal studied model. However, this may not be always true considering the noise and theinterference in wireless channels [118]. Finally, in the modified probabilistic tag estimation115Chapter 4. Probabilistic Tag Estimation Methodmethod and in [2], it has been assumed that the length of the frame (L) can be any integerfrom 1 to 128, however, many protocols have specific constraints on the length of the frame.For instance, the length of the frame in EPC Class-1 Gen-2 standard should be an integerof the form L = 2Q, where Q is an integer value between 0 and 15 [1, 3]. Finally, the fieldnulls effect and its role in losing the power of tags is another technical issue which can beconsidered in a non-ideal ALOHA-based RFID system [119].The modified tag estimation method relies on estimating the number of tags that max-imizes the probability of observing a combination of empty, single and collided slots bythe reader. Although this estimation adds some computational costs to the system, it isperformed in the reader (or database). Therefore, using the proposed method does notimpose any additional computation on the tags.116Chapter 5Analytical Modeling andPerformance Analysis of theEPCglobal Class-1 Generation-2Protocol5.1 IntroductionAn RFID reader is able to communicate with a single tag at a time, yet RFID systemsare prone to transmission collisions due to the shared nature of the wireless channel usedby tags. In order to solve the collision problem, the tree-walking and the ALOHA-basedanti-collision protocols have been proposed [20, 53, 55, 57, 58, 59]. Recently, a framed-slotted ALOHA-based anti-collision scheme has been standardized by EPCglobal [3]. Thisscheme is called the EPC Class-1 Generation-2 (briefly EPC Gen-2) protocol. The EPCGen-2 has been accepted as the main standard protocol for inventory checking, supplychain management and many other applications. Most RFID consumers currently use theEPC Gen-2 protocol [1]. Although the EPC Gen-2 protocol has been used as the mainstandard for supply chain management applications, there are only a few works that havestudied the performance of this protocol from the quantitative point of view [1, 68, 120].117Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolTo address this issue, Wang et al. studied the performance of the EPC Gen-2 protocoland modeled it as a Markov chain system [1]. This Markov chain interpretation of theEPC Gen-2 protocol offers a useful way for studying this protocol and helps researchersto better understand and improve it. Although this Markov chain model is useful inobtaining a quantitative performance analysis of the EPC Gen-2 protocol, it does notprovide an explicit analytical framework for the EPC Gen-2 protocol. In other words, weneed to run simulations and average the obtained results if we use the model suggested in[1] for studying the behavior of the EPC Gen-2 protocol. Moreover, the accuracy of thismodel decreases as the number of tags in the system increases. To solve the accuracy issue,we modify the model proposed in [1] and propose a new Markov chain model for the EPCGen-2 protocol. More importantly, we ?formulate? our proposed Markov chain model.Using our new model and the formulae derived, we are able to directly calculate how manyqueries are needed and how many bits are transmitted to identify all tags in a systemthat uses the EPC Gen-2 protocol, without needing any simulations. Such a performanceanalysis is helpful for RFID system deployment and in designing new algorithms to improvethe tag identification performance. Moreover, this chapter provides an analytical model forresearchers in the field to easily compare their proposed protocols with the standard EPCGen-2 protocol. Simulation results confirm that our Markov model accurately representsthe EPC Gen-2 protocol and is more accurate than the model proposed in [1]. The proposedanalytical model outperforms the Markov model in [1] for two reasons. First, the modelproposed in [1] uses an approximation of the EPC Gen-2 protocol while our analytical modeltakes advantage of the exact interpretation of the EPC Gen-2 protocol. Second, unlike theanalytical model in [1] which relies on simulations, our proposed model uses accurate andclosed form analytical formulae for calculating the expected number of queries and theexpected number of transmitted bits in an RFID system.118Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolThe contributions of this chapter are as follows:1. We study the EPC Gen-2 protocol and the Markov model proposed for it in [1].Then we modify this model and propose a more accurate Markov model for the EPCGen-2 protocol.2. The model proposed in [1] does not provide a closed form analytical formulation forthe number of queries and the number of transmitted bits needed to identify all tagsin the system. Instead, it relies on simulations and averaging to do so. To solvethis problem, we formulate our proposed Markov model completely and derive theaccurate analytical formulations for the number of required queries and the numberof transmitted bits in EPC Gen-2 protocol (as a function of the number of tags inthe system).3. We validate the accuracy of our proposed Markov model and the formulations wederived using simulations, and compare our Markov model with the one proposed in[1]. Simulation results confirm that our proposed Markov model accurately representsthe EPC Gen-2 protocol and is more accurate than the model proposed in [1].The rest of the chapter is organized as follows: Section 5.2 explains the Q-algorithmand the EPC Gen-2 protocol. Section 5.3 discusses the state of the art model proposedby Wang et al. to represent the EPC Gen-2 protocol [1]. In Section 5.4, we propose anew analytical model for the EPC Gen-2 protocol based on the absorbing Markov chainsystems and then we formulate this model. Performance evaluation and comparisons arepresented in Section 5.5 followed by conclusions in Section 5.6.119Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol5.2 The Standard Q-algorithmThe EPC Gen-2 protocol provides a standard communication mechanism for transferringand receiving data between RFID tags and the reader(s). It provides a wireless protocolincluding the physical layer and the medium access control (MAC) specifications for passiveUHF RFID tags that operate in the frequency range of 860 MHz to 960 MHz. Thisprotocol uses the dynamic framed-slotted ALOHA technique to identify the tags, and takesadvantage of an adaptive algorithm called the Q-algorithm to determine the number of timeslots required at each query. In the EPC Gen-2 protocol, the reader starts interrogatingthe tags present in its vicinity by sending a query command and a parameter called Q.Those tags that receive this query randomly choose a slot number (SN) between 0 and2Q ? 1. After this step, any tag whose SN is 0 generates a random 16-bit number calledRN16 and sends it back to the reader. Since each tag randomly chooses a time slot fromthe possible 2Q slots independently of the others, three scenarios may happen. In the firstscenario, called the idle transmission, no tag selects 0 for its SN and the reader receives noreply from the tags. In the second scenario, called the single transmission, only one tagselects 0 for its SN and sends its RN16 to the reader. The reader receives this RN16 andinforms all the tags that only the tag with this RN16 is allowed to use the wireless channeland to send its ID to the reader. As a result, this tag successfully sends its ID to the readerwhile all other tags remain silent. In the third scenario, called the collided transmission,more than one tag selects 0 for their SN. As a result, more than one tag sends RN16 tothe reader and therefore collision happens. If collision happens, the transmission fails [3].As can be inferred from the above, the Q parameter plays a significant role in the EPCGen-2 protocol. If Q is relatively large and the number of tags is small, the chance of idletransmission increases. On the other hand, if Q is relatively small while the number oftags in the system is large, the chance of collided transmission increases. Therefore, the Q120Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolparameter should be chosen wisely to reduce the chance of idle or collided transmissions.The EPC Gen-2 protocol uses the adaptive Q-algorithm to change the value of Q (andtherefore the number of available time slots) based on the responses the reader receivesfrom the tags. Fig. 5.1 shows how the adaptive Q-algorithm works. Here, Q is a parameterused by the EPC Gen-2 protocol to indicate the number of available time slots to the tagsand Qfp is the floating-point representation of Q. There is also another parameter c whichis used to adjust the rate of changing Q in the Q-algorithm. The value of Qfp is initializedto 4, and c can be selected from 0.1 to 0.5 by the system designer. An integrator typicallyuses small values of c when Q is large and large values of c when Q is small [3]. When aquery command is sent to the tags, the value of Qfp is rounded to the nearest integer andthis rounded value is assigned to Q. Then, the value of Q is sent to the tags along with thequery command. Each tag chooses a random SN according to the value of Q and repliesto the reader. If an idle transmission happens, the Q-algorithm decreases the value of Qfpby c, truncates the new Qfp to the nearest integer and adjusts the value of Q for the nextquery command accordingly. If a single transmission happens, the Q-algorithm does notchange the value of Qfp and uses the previous Q for the next query command. However, ifa collision happens, the Q-algorithm increases the value of Qfp by c and adjusts the new Qaccordingly for the next query command. It should be noted that the value of Q cannot beless than 0 or greater than 15. This procedure continues until all the tags in the system areidentified successfully by the reader. Using the above mechanism, the Q-algorithm changesthe number of time slots dynamically and controls the tag identifying process based on thenumber of tags in the system and their responses to the reader?s queries.121Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0.4=fpQ)(Query)(roundQQQ fp=Number of tagresponses),0max( cQQ fpfp -= ),15min( cQQ fpfp +=0+= fpfp QQ 0+= fpfp QQ0 > 11Figure 5.1: The adaptive Q-algorithm used by EPC Gen-2 [3].5.3 The Model Proposed by Wang et al. [1]In this section, we explain the model proposed by Wang et al. for analysing the performanceof the EPC Gen-2 protocol [1]. The EPC Gen-2 protocol is modeled as a Markov chainin [1]. We denote this model by the first Markov chain (FMC) model for the EPC Gen-2protocol. In this model, n shows the current number of unidentified tags in the system,N stands for the initial number of tags in the system, and Q is the parameter used bythe reader to inform the tags about the number of available time slots as explained inSection 5.2. In the FMC model, the pair of Q and n is shown by (Q,n) and it is called astate.In the FMC model, single transmissions are shown by S. After a single transmission,the system jumps from state (Q,n) to state (Q,n ? 1). This is exactly the same as whathappens in the actual Q-algorithm after a single transmission. If the system is in state(Q, 1) and a single transmission happens, it jumps to state (Q, 0) and remains there,meaning that the query process has finished successfully. However, the story is a littledifferent for the idle and collided transmissions. If an idle transmission happens, n is not122Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolchanged but Qfp is decreased by c in the actual Q-algorithm. This, on the other hand,may result in two different events. The Q parameter is decreased by 1 if the new Qfp iscloser to Q ? 1 than to Q. However, the Q parameter is not changed if Qfp is still closerto Q than to Q ? 1. In other words, the value of Q may or may not change after anidle transmission. On the other hand, there is no Qfp parameter in the FMC model andeverything is explained by Q and n. To reflect the effect of changing Qfp on Q, Wang et al.assume that after an idle transmission, the value of Q is decreased by 1 with probabilityPI1 or it is not changed with probability PI0, where I shows the idle transmission, 0 showsthat Q is not decreased and 1 indicates that Q is decreased by 1. We have the same storyfor collided transmissions. Again, a collided transmission may result in increasing the valueof Q by 1 if the new Qfp is closer to Q+1 than to Q, or it may result in the same value ofQ if the new Qfp is closer to Q than to Q + 1. However, in the FMC model it is assumedthat after a collided transmission, the value of Q is either increased by 1 with probabilityPC1 or it is not changed with probability PC0 [1].In the FMC model, the probability of single transmission PS(Q,n) is calculated asPS(Q,n) = n?(12Q)?(1? 12Q)n?1(5.1)and PI0(Q,n) and PI1(Q,n) are calculated asPI0(Q,n) = P0|I(Q,n)? PI(Q, n) (5.2)PI1(Q,n) = P1|I(Q,n)? PI(Q, n) (5.3)123Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolwhere PI(Q,n) is the probability of idle transmission and it is calculated as belowPI(Q,n) =(1? 12Q)n. (5.4)As can be seen, the P0|I(Q,n) and P1|I(Q,n) probabilities are also needed to calculatePI0(Q,n) and PI1(Q,n). In order to calculate P0|I(Q,n) and P1|I(Q, n), Wang et al. usethe following assumption: ?In long run, for each update triggered by an idle transmission,Q is decremented by 1 with probability c and is not changed with probability (1 ? c)? [1].Using this assumptionP0|I(Q,n) = 1? c (5.5)P1|I(Q,n) = c . (5.6)Similarly, PC0 and PC1 are calculated as belowPC0(Q,n) = P0|C(Q,n)? PC(Q,n) (5.7)PC1(Q,n) = P1|C(Q,n)? PC(Q,n) (5.8)where the probability of collided transmission PC(Q, n) is calculated as belowPC(Q,n) = 1? PS(Q,n)? PI(Q, n). (5.9)As in the idle scenario, P0|C(Q,n) and P1|C(Q,n) are needed to calculate PC0(Q,n) andPC1(Q,n). To calculate these probabilities, Wang et al. use the following assumption: ?Inlong run, for each update triggered by a collided transmission, Q is incremented by 1 with124Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolprobability c and is not changed with probability (1? c)? [1]. Using this assumptionP0|C(Q,n) = 1? c (5.10)P1|C(Q,n) = c . (5.11)Details on how Eq. (5.1) to (5.11) are derived can be found in [1].The FMC model provides a novel way of modeling the EPC Gen-2 protocol. Simulationresults show that this model can predict the behavior of the EPC Gen-2 protocol, andconfirm the usefulness of the FMC model. However, there exist two concerns which canbe noted here and solving these concerns will add to the value and usefulness of the FMCmodel. The first concern is the approximation used in this model. In the FMC model, theEPC Gen-2 protocol is modeled using the Q and n parameters but Q originally dependson Qfp, and Qfp is not reflected in the FMC model. As a result, the FMC model is alwaysan approximation of the EPC Gen-2 protocol. The second concern is the mathematicalformulation of the FMC model. While the Markov chain model proposed in [1] can predictthe behavior of the EPC Gen-2 protocol in real RFID systems very well, it does not providean explicit mathematical formulation for the number of queries needed to identify all tagsin the system (or similarly the time needed to identify all tags). This model also does notgive an explicit mathematical formulation for the total number of bits transmitted by alltags in the system. In other words, the FMC model can predict the behavior of the EPCGen-2 protocol using simulations, but it does not provide a mathematical formulation topredict the behavior of the protocol directly. This model depends on simulation results, andsimulations are always time consuming, especially when we want to study a typical RFIDsystem with thousands of tags. Moreover, we need to increase the number of repetitions125Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocoland averaging to increase the accuracy of the FMC model. We would be able to predictthe behavior of the EPC Gen-2 protocol directly and without needing the time consumingsimulations if we can provide explicit mathematical formulations for the proposed Markovchain model. Considering the above facts and concerns, we provide a more accurate anduseful analytical model for the EPC Gen-2 protocol.5.4 The New Analytical FrameworkThe idea of modeling the EPC Gen-2 protocol as a Markov chain system was first suggestedin [1]. We referred to this model as the first Markov chain (FMC) model for the EPC Gen-2protocol. In this section, we modify the FMC model and propose a new analytical modelfor the EPC Gen-2 protocol. We name our proposed analytical model the second Markovchain (SMC) model for the EPC Gen-2 protocol. Although we use the same approachas the one used in [1], our proposed SMC model has two main differences with the FMCmodel. First, the FMC model uses Q and n as the two parameters of the Markov chainsystem while in our SMC model, Qfp and n play the roles of the two key parameters inthe system as is now discussed. In the EPC Gen-2 protocol, Q originally depends on Qfp,but Qfp is not reflected in the FMC model [1]. In the FMC model, the Q parameter isalways an approximation of the actual Q in the Q-algorithm, and the behavior of the FMCmodel is always an approximation of the behavior of the EPC Gen-2 protocol. The effectsof this inaccuracy will be shown in more detail in Section 5.5. Our proposed SMC model,on the other hand, uses the Qfp parameter and thus, it can always provide an accuraterepresentation of the EPC Gen-2 protocol. The second difference is even more important.The FMC model does not provide any mathematical formulation for the average number ofqueries required (or equivalently, the average time needed) to identify all tags in the systemusing the EPC Gen-2 protocol. Instead, the FMC model relies on simulations to do so126Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolSSSSSSSSSSS S SSSS1T1+NTqT1+-NTq1+qTNc??????? -???? ???= 116qcQfp ?=01-NNncQfp ?=1( )[ ] cQ cfp ?-= 116( )[ ] cQ cfp ?-= 2162-N 1 0ICICICICC I C I C I C IC I C I C I C IFigure 5.2: Our proposed SMC model.and to predict the behavior of the EPC Gen-2 protocol. We, on the other hand, not onlypropose the accurate SMC model for the EPC Gen-2 protocol, but also mathematicallyformulate it using the absorbing Markov chain theorem. In other words, we do not need tosimulate the SMC model and average the simulation results to study the behavior of theEPC Gen-2 protocol. Instead, we can calculate all the required parameters directly usingthe mathematical formulation provided.The proposed SMC model is shown in Fig. 5.2 as a two dimensional absorbing Markovchain. In this model, n shows the current number of tags in the system, N stands for theinitial number of tags in the system, Qfp and c are as defined in Section 5.2. We also define127Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol? as[(16c)? 1]? N to save space in Fig. 5.2. Using Qfp and n as the parameters of ourMarkov chain, we have[(N + 1)?(16c)]states for each EPC Gen-2 RFID system with Ntags. These states are shown by Ti in Fig. 5.2 where i varies between 1 to[(16c)? (N + 1)].As can be seen in Fig. 5.2, n is decreased from left to right, and Qfp is increased from topto bottom. The EPC Gen-2 protocol starts from N tags in the system and eventually endsup to a state with 0 tags. In the actual Q-algorithm, three scenarios of single, idle andcollided transmissions may happen as explained in Section 5.2. In Fig. 5.2, single, idle andcollided transmissions are shown by S, I and C, respectively. After a single transmission,the system jumps from state (Qfp, n) to state (Qfp, n?1). If the system is in state (Qfp, 1)and a single transmission happens, it jumps to state (Qfp, 0) and remains there, meaningthat the query process has finished successfully. These states are called absorbing states.Our proposed model is an absorbing Markov model because the EPC Gen-2 protocol isfinally absorbed in one of the rightmost states (n = 0). If an idle transmission happens, nis not changed but Qfp is decreased by c, and the system jumps to the corresponding state.If a collision occurs, n is not changed but Qfp is increased by c, and the system jumps to thestate with the same n and the new Qfp. Using this model, the EPC Gen-2 protocol cannotstay in any of the states after a query command. This is exactly what actually happens inreal EPC Gen-2 protocol. This is one of the differences between our proposed SMC modeland the FMC model proposed in [1]. In the FMC model, each state can have two separatefeedback loops corresponding to idle and collided transmissions. Each feedback loop startsand ends at the same state. In other words, the system may remain in the same state afteran idle or collided transmission in the FMC model. However, in a real RFID system andin our proposed SMC model, it is not possible that the system remains in the same stateafter a query message.128Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol5.4.1 Expected Number of Required QueriesIn order to easily formulate the SMC model, we arrange the order and indices of Ti statessuch that we can divide them into two separate groups, called the transient states and theabsorbing states. In Fig. 5.2, the first N columns show the transient states, T1 to T( 16c )?N ,and the rightmost column shows the absorbing states, T( 16c )?N+1 to T( 16c )?(N+1). Using theSMC model, the probability of a single transmission is calculated asPS(Q,n) = n?(12Q)?(1? 12Q)n?1, (5.12)and the probability of idle and collided transmissions are calculated using Eq. (5.13) and(5.14)PI(Q, n) =(1? 12Q)n(5.13)PC(Q,n) = 1? PS(Q,n)? PI(Q,n) . (5.14)Now, we write the transition matrix of the Markov system shown in Fig. 5.2 as belowP =G H0 ITr.Tr.Abs.Abs.where P is the transition matrix, pi,j shows the probability of transition from state Ti tostate Tj, G is the matrix of transient states, H is the matrix of the absorbing states, 0 isthe zero matrix and I is the identity matrix. Using this notation and assuming that ? = 16cand ? =(16c)? N , the size of P, G, H, 0 and I matrices are (? + ?) ? (? + ?), ? ? ?,129Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol? ? ?, ?? ? and ?? ?, respectively. From the Markov chain theorem, we know that theprobability of the system being in the transient state Tj after x jumps and having startedfrom the transient state Ti is given by gxi,j, where gxi,j is the i, jth component of matrixGx. The following specifications of the G matrix are critical in providing an analyticalframework for the EPC Gen-2 protocol.Lemma 1: If the number of jumps (transitions) tends to infinity, then limx??Gx = 0.Proof: From each transient state Tj, it is possible to reach an absorbing state. Let sjbe the minimum number of steps needed to reach an absorbing state starting from Tj. Let?j be the probability that starting from Tj, the process does not reach an absorbing statein sj steps. Then, ?j < 1. Let smax be the largest of sj and ?max be the largest of ?j. Theprobability of not being absorbed in smax steps is always less than or equal to ?max, in 2smaxsteps is always less than or equal to ?2max, etc. Since ?max < 1, limx?? ?xmax = 0. Since theprobability of not being absorbed in n steps is monotone decreasing, limx??Gx = 0.Lemma 2: In the SMC model, (I ?G)?1 always exists, where I is the correspondingidentity matrix of the same size as G.Proof: We assume that there exists a matrix ? that results in (I ?G) ? ? = 0, thus? = G ? ?. By repeating the same procedure, we have ? = Gx ? ?. On the other hand,we have limx??Gx = 0 from the first lemma. Therefore, limx?? ? = limx??Gx ? ? = 0which is the only obvious solution for (I?G)? ? = 0. Thus, (I?G)?1 always exists.Now we can use these two lemmas to formulate our SMC model. Using the secondlemma, we can define a matrix M as belowM = (I?G)?1 . (5.15)130Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolWe also haveI?Gx+1 = (I?G)? (I+G+G2 +G3 + ...+Gx) . (5.16)Multiplying both sides by M, we haveM? (I?Gx+1) = (I?G)?1 ? (I?G)?(I+G+G2 +G3 + ...+Gx) . (5.17)From the first lemma we have limx??Gx = 0, so by letting x tend to infinity we haveM = (I+G+G2 +G3 + ...) (5.18)or equivalently,mi,j = g0i,j + g1i,j + g2i,j + ... . (5.19)Now let Ti and Tj be two transient states, and ?i,j(k) be a random variable which equals 1if the absorbing Markov chain of Fig. 5.2 reaches state j after exactly k jumps and startingfrom state i, and ?i,j(k) equals 0 otherwise. According to matrix G we havePr(?i,j(k) = 1) = gki,j (5.20)Pr(?i,j(k) = 0) = 1? gki,j (5.21)where gki,j is the i, jth entry of Gk. The expected number of times that the absorbingMarkov chain is in state Tj in the first k steps, given that it starts from state Ti is131Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolE{?i,j(0) + ?i,j(1) + ?i,j(2) + ...+ ?i,j(k)}= E{?i,j(0)}+ E{?i,j(1)}+ ...+ E{?i,j(k)}= g0i,j + g1i,j + g2i,j + ... + gki,j . (5.22)Letting k tend to infinity, we haveE{?i,j(0) + ?i,j(1) + ?i,j(2) + ...}= g0i,j + g1i,j + g2i,j + ... . (5.23)Finally from Eq. (5.19) and (5.23), we haveE{?i,j(0) + ?i,j(1) + ?i,j(2) + ...} = mi,j (5.24)where mi,j is the i, jth entry of matrix M defined in Eq. (5.15). Based on the above, if theEPC Gen-2 protocol starts from state i, the expected number of times that it visits state jbefore all the tags in the system are identified and the EPC Gen-2 protocol is terminatedcan be calculated using Eq. (5.24). We know that the EPC Gen-2 protocol always startswith Qfp equals to 4 [3]. Knowing this fact and using the SMC model shown in Fig. 5.2,we can simply conclude that the EPC Gen-2 protocol always starts from state T4?( 1c)?N+1.Therefore, we can calculate the expected number of queries in the EPC Gen-2 protocolgiven the number of tags at the beginning by calculating and adding the number of visitsto each of the transient states. In other words, the expected number of queries in the EPCGen-2 protocol is calculated by adding all entries of the (4?(1c)?N +1)th row in the M132Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolmatrix as belowq =( 16c )?N?j=1m(4?( 1c)?N+1),j (5.25)where q shows the average number of queries required to identify all of the N tags in thesystem.Using the above formulation, there is no need to run multiple simulations and averagethem to obtain the number of required queries as done in [1], instead, we can simply useEq. (5.25) and calculate q directly. As we will see in Section 5.5, the simulation resultsperfectly confirm the proposed SMC model and its formulation.5.4.2 Expected Number of Transmitted BitsAfter deriving the analytical formulation for the expected number of queries in the EPCGen-2 protocol, we derive the analytical formulation for the aggregate number of bits thatare sent by the tags, before they are successfully identified by the reader. According to [3],we assume that each idle transmission results in 0 transmitted bits, each single transmissionresults in 16 bits for RN16 and 96 bits for the tag serial number (112 bits in total), andeach collided transmission results in only 16 bits for RN16. First, we find the probabilitythat the EPC Gen-2 protocol starts the interrogation from the transient state Ti and endsup in the absorbing state Tj. This probability is denoted by bi,j. Using the Markov modelshown in Fig. 5.2 we have133Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolbi,j =??k=0( 16c )?N?r=1gki,r ? hr,j=( 16c )?N?r=1[??k=0gki,r]? hr,j=( 16c )?N?r=1mi,r ? hr,j= (M?H)i,j (5.26)where hr,j is the probability of jumping from the transient state Tr to the absorbing stateTj, and mi,r is calculated using Eq. (5.15). Therefore, we can define matrix B asB = M?H (5.27)where M is calculated using Eq. (5.15) and H is a subset of the transition matrix P whichshows the transition probabilities from the transient states to the absorbing states. In theEPC Gen-2 protocol, the query process always starts from state T(4?( 1c)?N+1), therefore,we can simply replace i with(4?(1c)?N + 1)in Eq. (5.26).In order to calculate the expected number of transmitted bits before all the tags areidentified by the reader, we need to calculate the expected number of idle, single andcollided transmissions during the tag identifying process. The aggregation of the expectednumber of idle, single and collided queries should equal the expected number of queries,therefore,I + S + C = q . (5.28)In the EPC Gen-2 protocol, the expected number of single transmissions always equals theinitial number of tags in the system. This gives us the second equation needed for deriving134Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolI, S and CS = N . (5.29)Finally, we always have4 + (C(i)? I(i))? c = Qfp(i) (5.30)where I(i) and C(i) are the number of idle and collided transmissions corresponding tothe ith absorbing state. Taking the expected value in Eq. (5.30) we have4 + (C ? I)? c = Qfp (5.31)where Qfp is calculated asQfp =( 16c )?(N+1)?i=( 16c )?N+1Qfp(i)? b(( 4c)?N+1),i . (5.32)Solving Eq. (5.28), (5.29) and (5.31) we have???????????I = q?N2 +4?Qfp2cS = NC = q?N2 ?4?Qfp2c .(5.33)Based on the above, we can calculate I, S and C for each of the 16c possible Qfp. We knowthat the EPC Gen-2 protocol starts from state T(4?( 1c)?N+1), and we have calculated theprobability that the EPC Gen-2 protocol ends up in each of the 16c absorbing states usingEq. (5.26). Therefore, the total expected number of transmitted bits isTB = 112? S + 16? C (5.34)135Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolwhere TB shows the expected number of transmitted bits, and S and C are calculatedusing Eq. (5.33).The expected number of transmitted bits and the expected number of required queriescan provide us an estimation of the time needed to detect all tags in the system using theEPC Gen-2 protocol. For example, assuming that each bit of data needs tb milliseconds(on average) to be transmitted by the tag and received by the reader, the average requiredtime T can be calculated asT = TB ? tb (5.35)where TB shows the expected number of transmitted bits calculated from Eq. (5.34). Thesame way, assuming that each round of query takes tq milliseconds (on average), the averagerequired time T can be calculated asT = q ? tq (5.36)where q represents the expected number of required queries calculated from Eq. (5.25).In order to show the accuracy of our SMC model in calculating the expected numberof required queries and to compare it with the FMC model, we define Difq asDifq = |q ? qsim| (5.37)where q denotes the expected number of queries calculated using the SMC (or FMC) modeland qsim is the number of queries obtained from simulating a real RFID system. We alsodefine DifTB asDifTB = |TB ? TBsim| (5.38)where TB denotes the expected number of transmitted bits calculated using the SMC (or136Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolFMC) model and TBsim is the number of transmitted bits obtained from simulating a realRFID system. We will use Eq. (5.37) and (5.38) in Section 5.5 to show the accuracy of theproposed model and to compare it with the model proposed in [1].5.4.3 Generalizing the SMC Model for Variable cSo far, we have modeled the EPC Gen-2 protocol based on an invariant c parameter.However, c might be a variable itself and changes as a function of the Q parameter. TheEPC Gen-2 standard ?recommends? using a small value of c when Q is large and a largevalue of c when Q is small, however, it does not suggest any criterion (or function) forchanging the value of c based on the value of Q [3]. Fortunately, our proposed SMC modelis a general analytical model for the EPC Gen-2 protocol and does not depend on a fixed orvariable c parameter. In other words, even if c is defined as a function of Q, our SMC modelwill remain valid and accurate. Here, we explain how the SMC model can be generalizedfor RFID systems that use a variable c parameter for their tag identification process.The Q-algorithm used in our SMC model is exactly the same as the one used by theEPC Gen-2 protocol during the tag identification process. In other words, for a fixed c inthe EPC Gen-2 protocol we use the same fixed c in our SMC model and for a variable c inthe EPC Gen-2 protocol we use the same variable c in our SMC model. Therefore, using avariable c parameter which changes over time based on Q does not degrade the accuracy ofour proposed analytical model. It should also be noted that the structure of the proposedabsorbing Markov model remains the same even if c changes over time as a function of Q.Even if c is a function of Q, the number of the states in the proposed SMC model is exactlythe same as that shown in Fig. 5.2 for a fixed c. The size of the G, H, I, 0 and P matricesare also the same as that we calculated for an invariant c. Even the PS(Q,n), PI(Q,n)and PC(Q,n) probabilities calculated using Eq. (5.12), (5.13) and (5.14) are the same for137Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolRFID systems which operate based on a variable c. The horizontal jumps (when a singletag ID is read successfully by the reader) are the same for both RFID systems with fixedand variable c as well. The only difference between the SMC model for RFID systems witha fixed c and the SMC model for RFID systems that assume c is a function of Q is in theirvertical jumps. If c is fixed during the tag identification process, vertical jumps can be fromone state to another state only ?one? row below (collided transmission) or ?one? row above(idle transmission), while in the SMC model with a variable c, vertical jumps can be fromone state to another state ?few? rows below (collided transmission) or ?few? rows above(idle transmission) depending on the function or criterion which changes c according to Q.The general form of the SMC model considering c as a function of Q is shown in Fig. 5.3.It should be noted that not all the vertical dotted arrows started from or ended in a statein Fig. 5.3 are used in the SMC model. Only one of the vertical dotted arrows started from(or ended in) a state happens with probability 1 if collision (or idle transmission) happensand the rest happen with probability 0. In other words, among all vertical arrows endedin (or started from) a state, the probability of one and only one of them is 1 and the restof the jumps do not happen. To answer which vertical jump happens with probability 1and which vertical jump happens with probability 0, we need to know c as a function ofQ. If we assume that c is fixed, then the arrow started from one state can only end upat the state just one row below (above) it if collision (idle transmission) happens. This isexactly the same as Fig. 5.2. If c changes over time based on the values of Q, then thearrow started from one state ends up at a state a few rows below (above) the starting stateif collision (idle transmission) happens. Based on the above, the only difference betweenthe SMC model for a fixed c parameter and the SMC model for a variable c parameter isin their G matrices, but the Markov model and Eq. (5.12) to (5.38) remain exactly thesame for both models. Therefore, knowing c as a function of Q, we can simply calculate138Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 ProtocolSSSSSSSSSSS S SSSS1T1 NT1 !NT 1 !TNc !"#$%& '(()* +,-. 116 C CC C C CC CI I IIIIII I IcQ fp ! 01 NNncQ fp ! 1 !" # cQ cfp !" 116 !" # cQ cfp !" 2162 N 1 0C C CCCCIICCCC C CCC CCIIIIIIIIFigure 5.3: Generalized form of the SMC model for variable c.the G matrix and the rest would be the same as that shown in sections 5.4.1 and 5.4.2.In Section 5.5, we use our proposed SMC model for an RFID system which uses thefunction shown in Eq. (5.39) for changing c based on Q,c =?????0.1; Q ? 80.5; Q < 8(5.39)and compare the average number of queries and the average number of transmitted bitsobtained from simulating the real RFID system with the expected number of queries and139Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 2000100200300400500600700nq?Our proposed SMC modelWang?s FMC modelSimulated RFID systemFigure 5.4: The expected number of required queries q for detecting all the tags vs. thenumber of tags in the system (c = 0.2).the expected number of transmitted bits calculated using our proposed SMC model.5.5 Performance EvaluationThis section presents the results of the simulation experiments we performed to evaluate theperformance of our proposed SMC model. We also present the performance comparisonsbetween the SMC model and the FMC model proposed by Wang et al. [1]. All simulationsare performed in the MATLAB environment.We simulated an RFID system which works based on the EPC Gen-2 protocol. Weinitialized c to 0.2, varied n (the number of tags in the system) between 2 and 200, and140Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 200010203040506070nDifq?Wang?s FMCmodelOur proposed SMC modelFigure 5.5: Difference between the q calculated using the FMC and SMC models and theqsim obtained from the simulated RFID system (c = 0.2).repeated the procedure 500 times for each n to see how many queries and how many trans-mitted bits are required (on average) to detect all tags in the system using the simulatedEPC Gen-2 protocol. In the next step, we calculated the expected number of queries usingEq. (5.25), and the FMC model [1]. Fig. 5.4 shows the expected number of queries versusthe number of tags for the simulated RFID system, our proposed SMC model and the FMCmodel. As can be inferred from Fig. 5.4, the proposed SMC model estimates the number ofrequired queries accurately and the plot obtained from Eq. (5.25) almost overlaps with theplot obtained from simulating a real RFID system. The FMC model, on the other hand,can imitate the behavior of the RFID system, but the accuracy of this model decreases asthe number of tags in the system increases.141Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 20000.511.522.53 x 104nTBOur proposed SMC modelWang?s FMC modelSimulated RFID systemFigure 5.6: The expected number of transmitted bits TB needed for detecting all tags vs.the number of tags in the system (c = 0.2).In Fig. 5.4, the two plots corresponding to our SMC model and the simulated RFIDsystem are very close to each other so the difference between them cannot be observedeasily. In Fig. 5.5, we used the Difq defined in Eq. (5.37) to better compare our proposedSMC model with the FMC model proposed in [1]. This figure shows the difference betweenthe values estimated using our SMC model and the values obtained from the simulatedRFID system, and compares it with the difference between the values obtained from theFMC model and the simulated RFID system. This figure confirms the accuracy of ourproposed analytical model. It should be noted that the values calculated using Eq. (5.25)are even more accurate than the values obtained from the simulated RFID system, and ifwe increase the number of iterations in the simulated RFID system, the solid blue line will142Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 2000100200300400500600nDif TBWang?s FMC modelOur proposed SMC modelFigure 5.7: Difference between the TB calculated using the FMC and SMC models andthe TBsim obtained from the simulated RFID system (c = 0.2).remain on the n-axis for all values of n.After showing the accuracy of the proposed SMC model in calculating the expectednumber of required queries q, the accuracy of the proposed SMC model in calculating theexpected number of transmitted bits TB is shown in Fig. 5.6. In this figure, the expectednumber of transmitted bits is calculated using the SMC model, the simulated RFID systemand the FMC model [1]. Again, it can be inferred from the figure that the proposed SMCmodel calculates the total expected number of transmitted bits more accurately comparedto the FMC model. In order to better show the accuracy of the proposed SMC model, thedifferences between the estimated TB and the number of transmitted bits obtained fromsimulations are shown in Fig. 5.7 for both the SMC model and the FMC model. As can beinferred from this figure, the accuracy of the FMC model degrades as the number of tags143Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocolin the system increases and it may even have up to 500 bits of error in an RFID systemwith 200 tags, while the proposed SMC model remains accurate for any number of tags inthe system. It should be noted that repeating the simulations and increasing the numberof iterations will result in a solid blue line which is indistinguishable from the n-axis for allvalues of n. In other words, if we increase the number of iterations, the results obtainedfrom the simulated RFID system would completely match the results obtained from ourSMC model.In our simulations, the only parameter that may change from one RFID system to theother is c. In order to see the effects of changing c on the accuracy of our SMC model andthe FMC model, we repeated the simulations for c = 0.4. Fig. 5.8 shows the value of qversus n for the new c. As before, the accuracy of the model proposed in [1] decreases asthe number of tags in the system increases. However, Fig. 5.9 shows that the differencebetween the q obtained from the FMC model and the simulated system (error) decreasesa little as the value of c increases. This happens because by increasing the value of c, therate of changing Q increases in the Q-algorithm and the system becomes less dependenton Qfp. Thus, the FMC model becomes a better approximation of the real EPC Gen-2protocol as the value of c increases.Fig. 5.10 compares the performance of the proposed SMC model with the FMC modelin terms of how accurately they calculate TB when c equals 0.4. Fig. 5.11 shows thedifferences between TB and TB obtained from the simulated RFID system for both theproposed SMC model and the FMC model. Again, it can be inferred from these two figuresthat the proposed analytical model can calculate the expected number of transmitted bitsmore accurately compared to the FMC model. However, the performance of the FMCmodel improves as the value of c increases. This happens because by increasing the valueof c, the rate of changing Q increases in the Q-algorithm and the system becomes less144Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 2000100200300400500600700nq?Our Proposed SMC modelWang?s FMC modelSimulated RFID systemFigure 5.8: The expected number of required queries q for detecting all the tags vs. thenumber of tags in the system (c = 0.4).dependent on Qfp. However, it should be noted that our proposed SMC model alwaysoutperforms the FMC model, even for large values of c, as it is not an approximation ofthe EPC Gen-2 protocol.We showed the accuracy of the proposed SMC model in estimating the expected numberof queries and the expected number of transmitted bits when c does not change over time(c = 0.2 and c = 0.4). However, as mentioned in Section 5.4.3, the c parameter may notbe a fixed value and it can change over time according to Q. For instance, the EPC Gen-2standard recommends using large values of c when Q is small and small values of c when Qis large [3]. If c changes as a function of Q, we can simply use the model shown in Fig. 5.3and repeat the same procedure as the one explained in Sections 5.4.1 and 5.4.2 to calculatethe expected number of queries and the expected number of transmitted bits. We used our145Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 20005101520253035404550nDifq?Wang?s FMC modelOur proposed SMC modelFigure 5.9: Difference between the q calculated using the FMC and SMC models and theqsim obtained from the simulated RFID system (c = 0.4).proposed SMC model for estimating q and TB in an RFID system which uses Eq. (5.39)for changing c during the tag identification procedure, and compared the estimated q andTB with the results obtained from simulating a real RFID system. Fig. 5.12 shows theaccuracy of the proposed SMC model in estimating the expected number of queries andFig. 5.13 shows the accuracy of the proposed method in estimating the expected numberof transmitted bits. As can be inferred from Fig. 5.12 and Fig. 5.13, the proposed SMCmodel accurately estimates q and TB even if c is a function of Q and changes during thetag identification process.146Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 20000.511.522.53 x 104nTBOur proposed SMC modelWang?s FMC modelSimulated RFID systemFigure 5.10: The expected number of transmitted bits TB needed for detecting all the tagsvs. the number of tags in the system (c = 0.4).5.6 SummaryIn this chapter, we studied the standard EPC Gen-2 protocol and its tag identifying pro-cedure which employs the Q-algorithm. Then, the FMC model proposed by Wang et al.was discussed [1]. We showed that the FMC model can be improved by changing the pa-rameters of the model. Moreover, the FMC model proposed in [1] provides a novel methodof studying the EPC Gen-2 protocol but it relies on extensive simulations to calculate thenumber of queries and the number of transmitted bits accurately.We modeled the EPC Gen-2 protocol as an absorbing Markov chain and named itthe SMC model. Using the SMC model and the analytical formulation we developed, wederived the closed form mathematical expressions for the expected number of required147Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 200050100150200250300350400450nDif TBWang?s FMC modelOur proposed SMC modelFigure 5.11: Difference between the TB calculated using the FMC and SMC models andthe TBsim obtained from the simulated RFID system (c = 0.4).queries and the expected number of transmitted bits as a function of the number of tags inthe system. These formulae enable us to calculate the number of queries and the number oftransmitted bits needed to identify all tags in the system accurately and without the needof any simulation. Knowing how long each query takes on average, we can also calculatethe average time needed to successfully identify all tags in the system. Using the proposedSMC model, we can also predict the values of the Qfp and Q parameters in the Q-algorithmwhen the EPC Gen-2 protocol completes the tag identification procedure for any given cand N . Simulation results confirm that our proposed SMC model completely matches theEPC Gen-2 protocol and outperforms the model proposed in [1]. The FMC model, usesan approximation of the EPC Gen-2 protocol and its accuracy decreases as the number148Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 2000100200300400500600700nq?Our porposed SMC modelSimulated RFID systemFigure 5.12: The expected number of required queries q for detecting all the tags vs. thenumber of tags in the system with the variable c shown by Eq. (5.39).of tags in the system increases. Our proposed SMC model, on the other hand, is not anapproximation of the EPC Gen-2 protocol and the values obtained from the mathematicalexpressions we derived are accurate, regardless of the number of tags in the system or anyother parameter. Moreover, the FMC model has been designed for RFID systems whichuse a fixed c during the tag identification process. Our proposed SMC model, on the otherhand, can accurately estimate the expected number of queries and the expected numberof transmitted bits even if c is not fixed during the tag identification process and changesover time as a function of Q.In this work, the proposed SMC model was used to formulate the EPC Gen-2 protocoland to calculate the expected number of queries and the expected number of transmit-ted bits. This analytical model, however, can be used for many other purposes such as149Chapter 5. Analytical Modeling and Performance Analysis of EPC Class-1 Gen-2 Protocol0 20 40 60 80 100 120 140 160 180 20000.511.522.53x 104n? TBOur proposed SMC modelSimulated RFID systemFigure 5.13: The expected number of transmitted bits TB needed for detecting all the tagsvs. the number of tags in the system with the variable c shown by Eq. (5.39).estimating the number of tags in an environment or improving the performance of RFIDsystems.150Chapter 6Performance Analysis of RFIDProtocols: CDMA vs. the StandardEPC Gen-26.1 IntroductionAn RFID reader is able to communicate with a single tag at a time, yet RFID systems areprone to transmission collisions due to the shared nature of the wireless channel used bytags. To solve the collision problem, the tree-walking and the ALOHA-based anti-collisionprotocols have been proposed [20, 53, 55, 57, 58, 59, 83]. Recently, a framed-slottedALOHA-based anti-collision scheme was standardized by EPCglobal [3]. This scheme iscalled the EPC Gen-2 protocol and allows each tag to randomly select a time slot andtransmit its ID. This protocol has been accepted as the main standard for the inventorychecking and supply chain management applications [1, 85].Recently, it has been suggested by many researchers to replace the dynamic framedslotted ALOHA mechanism used by the standard EPC Gen-2 protocol with the CDMAtechnique to make the reader able to read more tag IDs at each query and to expeditethe tag identification procedure. For instance, Mazurek suggested to use the DS-CDMAtechnique for active RFID tags [56], and implemented a simple RFID system in which the151Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2tags use the DS-CDMA technique for transmission and the reader employs a non-coherentdetector with successive interference cancellation [60]. Mutti and Floerkemeier suggested toreplace current ALOHA-based RFID systems with CDMA-based RFID systems to preventwasting the bandwidth during the singulation process. They focussed on the choice of thecode sets that can be used and the appropriate detector for a CDMA-based RFID system.They also proposed a method for estimating the number of tags in the range of such aspread spectrum RFID system [61]. Demeechai and Siwamogsatham proposed a new tagidentification protocol by modifying the standard EPC Gen-2 scheme and taking advantageof the CDMA technique in their proposed model [62]. Maina et al. studied typical storeand warehouse environments under worst-case scenarios and recommended to employ theCDMA technique for the tag identification purpose [63]. There are few other studiesthat suggested the use of the CDMA technique instead of the current ALOHA-based tagidentification technique employed in the standard EPC Gen-2 protocol [64, 65, 66, 67].Although it has been advised by many researchers to take advantage of the CDMAtechnique and to design the new RFID protocols based on it, no analytical proof has beenput forward for this idea so far. We know that the time needed to identify all tags in thesystem and the required bandwidth play an important role in commercial and industrialRFID systems. Therefore, we need to know whether and how the use of the CDMAtechnique instead of the current ALOHA-based tag identification technique would affectthe time needed to identify all the tags and the bandwidth of the system. In other words,we need to know the pros and cons of using the CDMA technique for the tag identificationpurpose and to have a fair analytical comparison of the CDMA-based scheme with thestandard EPC Gen-2 protocol before switching to the new system. In order to do that,we model the CDMA-based tag identification scheme as an absorbing Markov chain andderive the accurate analytical formulae for the expected number of queries and the total152Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2transmitted data needed to identify all tags in the system. A similar analytical model wasdeveloped for the EPC Gen-2 protocol in Chapter 5. Using the Markov model proposed forthe CDMA-based tag identification scheme and the Markov model developed for the EPCGen-2 protocol in Chapter 5, we compare these two techniques in terms of the expectednumber of queries and the total amount of transmitted data required to identify all tags inan RFID system. Such a performance analysis is helpful for RFID system deployment andin designing new algorithms for improving the tag identification performance. Moreover,this chapter provides an analytical model for researchers in the field to easily comparetheir proposed protocols with the CDMA-based schemes as well as the standard EPCGen-2 protocol.The contributions of this chapter are as follows:1. We study the CDMA-based tag identification scheme and model it as an absorbingMarkov chain system.2. Using this model, we derive the analytical formulae for the expected number of queries(q) and the total transmitted data (TD) needed to identify all tags in the systemusing the CDMA technique.3. We compare the performance of the EPC Gen-2 protocol and the CDMA-basedtag identification schemes and show that the EPC Gen-2 protocol outperforms theCDMA-based scheme in terms of the total transmitted data (TD).The rest of this chapter is organized as follows: In Section 6.2, we propose an absorbingMarkov model for the CDMA-based tag identification schemes. We derive the analyticalformulae for the expected number of queries and the total transmitted data required toidentify all tags in the CDMA-based RFID systems. In Section 6.3, we compare theperformance of the CDMA-based tag identification schemes and the standard EPC Gen-2153Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2tag identification protocol in terms of the total number of required queries and the totaltransmitted data. The conclusion and further discussions are presented in Section 6.4.6.2 CDMA-based Tag IdentificationAs discussed earlier, the CDMA technique has been widely suggested for the RFID systemsrecently. In traditional spread-spectrum (SS) systems such as CDMA systems, each userencodes its data using a spreading code which is orthogonal (or as close to orthogonalas possible) to the spreading codes of other users. This allows the successful decoding ofdata sent by two or more users simultaneously [61]. Using this idea, it has been suggestedthat several spreading codes are stored in each tag in an RFID system. Each spreadingcode consists of a predefined number of rectangular pulses, called the chips. Therefore, thelengths of a spreading code is defined by the number of its chips. Each tag randomly selectsone of these codes to spread (encode) its ID, and then sends its coded ID to the reader.This technique has been shown in Fig. 6.1. Using the CDMA technique, multiple tagscan be read simultaneously in each frame and thus the number of collisions is reduced.Although using the CDMA technique can reduce the number of collisions and increasethe number of identified tags at each query, the assumption that it speeds-up the wholetag identification procedure may not necessarily be true and should be investigated morecarefully.6.2.1 Tag Identification ProcedureIn order to use the CDMA technique, each bit of the tag ID should be first spread bythe user specific code and then transmitted to the reader. This means that the length ofthe coded tag ID becomes longer after being encoded by the tag?s spreading code. As anexample, if the tags use spreading codes of length l in a CDMA-based RFID system, each154Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2bit of the binary tag ID would be represented by a sequence of l binary chips. As a result,two different scenarios may happen. In the first scenario, the transmission rate shouldbe increased to compensate for the increase in the number of chips (data) that should betransmitted for each tag ID. In the second scenario, the tag simply transmits all the chipsof the spread tag ID one by one with the same transmission rate as the one recommendedby the EPC Gen-2 standard. In other words, the transmission rate does not change in thesecond scenario. The first scenario does not seem to be a good option since the frequencyband and the transmission rate in RFID systems have been standardized and most of thecurrent RFID systems have been designed and operate based on the EPC Gen-2 standard.Moreover, changing the transmission rate would require significant changes in the hardwarearchitecture of the RFID tags. In the second scenario, on the other hand, we do not needto significantly change the hardware architecture of RFID tags and the old system canstill be used. The only modifications required are adding a cheap and small memory toeach tag to store the spreading codes, and to update the readers in a way that they reada longer sequence of binary data and decode the tag IDs from the CDMA sequence.As an example, in Fig. 6.1 it has been assumed that a tag whose ID is 01 needs tosend its ID to the reader in a CDMA-based RFID system, and it randomly selects the1010 spreading code. Therefore, the spread data that should be transmitted to the readeris 01011010. In the second scenario, the transmission rate of the tag is not changed forusing the CDMA technique, so the time needed to transmit an information bit is the sameas the time needed to transmit a chip. Therefore, assuming that the transmission rate ofthe tag is 1 bit per second and using the second scenario, it takes 8 seconds for the tag totransmit all the 8 chips to the reader. The received data (chips) is then multiplied by thespreading code in the reader and the 01 (ID) is detected.Although the amount of transmitted data increases using the CDMA technique (both155Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2Original Data 01CDMA Code 1010Transmitted Data 01011010+1-1-1 -1+1 +1+1 +1 +1 +1-1 -1 -1 -1bitchipFigure 6.1: The CDMA technique, the bit and the chip concepts we used for RFID systems.the first and the second scenarios), the number of collisions decreases for sure and moretag IDs are identified at each round of query compared to the ALOHA-based techniqueused by the EPC Gen-2 protocol. In other words, using the CDMA technique results infewer queries but at each query more data should be transmitted by the tags. Therefore,we need to find (calculate) the expected number of queries and the total transmitted datafor both the standard ALOHA-based and the CDMA-based tag identification protocols tobe able to have a fair comparison between them.6.2.2 Proposed Absorbing Markov Chain ModelAs in the case of the EPC Gen-2 protocol in Chapter 5, we model the CDMA-based tagidentification technique as an absorbing Markov chain. This model is shown in Fig. 6.2.For an RFID system with n tags, the proposed model has n + 1 states starting at state non the left and ending at state 0. The number assigned to each state shows the numberof tags in the system that have not been identified yet. We assume that d codes of lengthl are also used by the tags to encode their IDs. Using the CDMA technique, each tagchooses one of the d codes stored in its memory at random, encodes its ID and transmits156Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2...n n-1 n-2 1 0...nnp ,1, -nnp1,1 -- nnp2,1 -- nnp2, -nnp1,np2,2 -- nnp1,1p0,np1,1-np0,1-npFigure 6.2: Our Proposed Markov chain model for the CDMA system.the result to the reader. In the reader, all d codes are examined one by one to decodethe information sent by the replying tags. In this tag identification technique, a tag isforced to be silent after it has been successfully identified by the reader. Using the aboveassumptions, two scenarios may happen. First, the tag chooses a spreading code whichis not used by any other tag. As a result, the reader successfully decodes the ID sent bythis tag. In the second scenario, two or more tags choose the same spreading code. Asa result, a collision happens and the reader cannot read the information sent by the tagsand identify their IDs.In order to formulate the proposed Markov model, first we need to calculate the proba-bility of jumping from state y to state z. In this model, py,z means there were y tags in thesystem, and after being queried by the reader, y? z tags were identified successfully whilez tags remained unidentified in the system. In other words, y ? z spreading codes (out ofthe total d codes) were only chosen by y?z separate tags, so the transmission of these y?ztags was successful while the other d?y+z spreading codes were chosen by more than one157Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2tag. We can consider this problem as putting n balls (tags) in d baskets (spreading codes)and calculating the probability of having y ? z baskets occupied by one and only one tag.This is a well-known problem in the classical urn model and the probability is providedin [95]. Assuming that C baskets were chosen by more than one ball, E baskets were notchosen by any ball and S baskets were chosen by S balls (one ball in each basket), we haved = E + S + C . (6.1)First, the probability of having E empty baskets is derived. This probability is denotedby P1(E, n, d) and is equal toP1(E, n, d) =(1? Ed)n, 0 ? E ? d . (6.2)In the next step, the probability of having S baskets each occupied by one ball only,conditional on having E empty baskets in the previous step is derived. This probability isdenoted by P2(S , n , d| E)P2(S , n , d| E) =(nS)(Sd? E)S (1? Sd? E)(n?S)?(S?i=0(?1)i(Si)(1? iS)S),0 ? S ? min{d? E, n}(6.3)where( Sd?E)S is the probability that S balls are assigned to the first S baskets in thetotal remaining (d ? E) baskets,(1? Sd?E)(n?S) is the probability that the remaining(n ? S) balls are assigned to the remaining (d ? E ? S) baskets, and the summation?Si=0(?1)i(Si) (1? iS)S is the probability that the mentioned S balls are assigned to Sbaskets, with no basket remains empty (in other words, each of the S baskets only accom-158Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2modates one and only one of the S balls). The summation?Si=0(?1)i(Si) (1? iS)S can besimplified asS?i=0(?1)i(Si)(1? iS)S= S!SS. (6.4)Based on the above, P2(S , n , d| E) can be written asP2(S , n , d| E) =(nS)(Sd? E)S?(1? Sd? E)(n?S) S!SS=(nS)((d? E ? S)(n?S)(d? E)n)S! . (6.5)Now, we need to calculate the probability of observing C baskets with more than oneball in each of them conditional on having E empty and S singly occupied baskets. ForP3(C , n , d| E, S), it is not easy to calculate the probability of observing C conditional onE and S directly. Therefore, we define a class of acceptable events that represents differentways of distributing (n? S) balls in C baskets such that each basket contains at least twoballs. We define the number of these acceptable events as rn?S(C, 2). We haveP3(C , n , d| E, S) =rn?S(C, 2)C(n?S), (6.6)in which C(n?S) is the total number of ways by which we can assign (n ? S) balls to theremaining C baskets. Now, the main problem is to determine rn?S(C, 2). Riordan [96]suggested two closed form expressions for r?(?, ?) using the classical urn model in which?, ? and ? denote the number of balls, the number of baskets, and the minimum numberof balls in each basket, respectively. The first closed form expression for r?(?, ?) isr?(?, ?) = ?r??1(?, ?) + ?(? ? 1?? 1)r???(? ? 1, ?), (6.7)159Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2and the second one isr?(?, ?) =??k=0(?1)k(?k)?!(?? 1)!k(? ? ?k + k)!? r???k+k(? ? k, ?? 1).(6.8)Using Eq. (6.7) and (6.8), we can find the exact number of acceptable events in Eq. (6.6)by replacing ? with (n? S), ? with C and ? with 2 for our problem. The above recursiveequations can be calculated in two different ways. In the first approach, we can only useEq. (6.7) and combine it with three simple logical constraints, as stated below:a) if (? 6= 0) and (? = 0), then r?(?, ?) = 0 ;b) if (? < ??), then r?(?, ?) = 0 ;c) if (? = 1) and (? 6= 0) and (? ? ??), then r?(?, ?) = 1.Using this method, we can start from an initial point and find the exact value for r?(?, ?)recursively. As the second approach, we can simplify Eq. (6.8) by replacing ? with 2 andwriter?(?, 2) =??k=0(?1)k(?k)?!(? ? k)!r??k(? ? k, 1) (6.9)in whichr??k(? ? k, 1) = p0(? ? k, ? ? k) (? ? k)(??k) , (6.10)and p0(? ? k, ? ? k) is the probability that we have (? ? k) balls and (? ? k) baskets andall the baskets contain at least one ball. From [95], we have the mathematical expressionfor p0(? ? k, ? ? k) asp0(? ? k, ? ? k) =??k?v=0(?1)v(? ? kv)(1? v? ? k)(??k). (6.11)160Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2By substituting Eq. (6.10) and (6.11) into (6.9), we getr?(?, 2) =??k=0??k?v=0(?1)(k+v)(?k)(? ? kv)? ?!(? ? k)!(? ? k ? v)(??k) .(6.12)Based on the above, Eq. (6.6) can be written asP3(C , n , d| E, S) =C?k=0C?k?v=0(?1)(k+v)(Ck)(C ? kv)? (n? S)!(n? S ? k)!(C ? k ? v)(n?S?k)C(n?S).(6.13)Using Eq. (6.2), (6.5), (6.6) and (6.12) or (6.7), we can determine P (E, S, C, n, d) asP (E, S,C, n, d) =(d!E! S! C!)P1(E) P2(S , n , d| E)? P3(C , n , d| E, S) .(6.14)In Eq. (6.14),( d!E! S! C!)is the number of ways by which the empty and singly occupiedbaskets and the ones containing more than one ball can be scrambled and mixed with eachother and make a random structure of E, S and C baskets.After deriving the analytical expression for P (E, S, C, n, d), we use it to calculate thepy,z probabilities needed to complete the Markov model shown in Fig. 6.2. Using thisMarkov model and the technique we used for the EPC Gen-2 protocol in Chapter 5, wederive the accurate closed form expressions for the expected number of queries and thetotal transmitted data in the CDMA-based RFID systems.161Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-26.2.3 Expected Number of Required QueriesAs done in Chapter 5 Section 5.4.1, we arrange the order and indices of the states sothat they can be divided into two separate groups, the transient states and the absorbingstates. In Fig. 6.2, the first N circles (shown by N to 1) are the transient states, and therightmost circle (shown by 0) is the absorbing state. Now, the transition matrix of theMarkov system in Fig. 6.2 can be written as belowP =G H0 ITr.Tr.Abs.Abs.where P is the transition matrix, pi,j denotes the probability of transition from state i tostate j, G is the matrix of transient states, H is the matrix of the absorbing states, 0 isthe zero matrix and I is the identity matrix. From the Markov chain theorem, we knowthat the probability of the system being in the transient state j after x jumps and havingstarted from the transient state i is given by gxi,j, where gxi,j is the i, jth component ofmatrix Gx. The following specifications of the G matrix given by Lemma 1 and Lemma 2are critical in deriving the analytical expressions for the expected number of queries andthe total transmitted data.Lemma 1: If the number of jumps (transitions) tends to infinity, then limx??Gx = 0.Lemma 2: In the proposed Markov model, (I ? G)?1 always exists, where I is thecorresponding identity matrix of the same size as G.The proofs of the above two lemmas are exactly the same as Chapter 5. We use thesetwo lemmas to derive a closed form expression for the expected number of queries and the162Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2total transmitted data. Using the second lemma, we define a matrix M asM = (I?G)?1 . (6.15)We also haveI?Gx+1 = (I?G)? (I+G+G2 +G3 + ...+Gx) . (6.16)Multiplying Eq. (6.16) by M, we getM? (I?Gx+1) = (I?G)?1 ? (I?G)? (I+G+G2 +G3 + ...+Gx) . (6.17)From the first lemma we have limx??Gx = 0, so by letting x tend to infinity we getM = (I+G+G2 +G3 + ...) (6.18)or equivalently,mi,j = g0i,j + g1i,j + g2i,j + ... . (6.19)Now let i and j be two transient states, and ?i,j(k) be a random variable which equals 1 ifthe absorbing Markov chain of Fig. 6.2 reaches state j after exactly k jumps and startingfrom state i, and ?i,j(k) equals 0 otherwise. According to matrix G we havePr(?i,j(k) = 1) = gki,j (6.20)Pr(?i,j(k) = 0) = 1? gki,j (6.21)163Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2where gki,j is the i, jth entry of Gk. The expected number of times that the absorbingMarkov chain is in state j in the first k steps, given that it starts at state i isE{?i,j(0) + ?i,j(1) + ?i,j(2) + ...+ ?i,j(k)}= E{?i,j(0)}+ E{?i,j(1)}+ ...+ E{?i,j(k)}= g0i,j + g1i,j + g2i,j + ... + gki,j . (6.22)Letting k tend to infinity, we getE{?i,j(0) + ?i,j(1) + ?i,j(2) + ...}= g0i,j + g1i,j + g2i,j + ... . (6.23)Finally from Eq. (6.19) and (6.23), we haveE{?i,j(0) + ?i,j(1) + ?i,j(2) + ...} = mi,j (6.24)where mi,j is the i, jth entry of matrix M defined in Eq. (6.15). Based on the above, if aCDMA-based tag identification protocol starts from state i, the expected number of timesthat it visits state j before all the tags in the system are identified can be calculated fromEq. (6.24). We know that the CDMA-based protocol always starts from state N (i = N).Knowing this fact and using the Markov model shown in Fig. 6.2, we can simply concludethat the expected number of queries in the CDMA-based protocol is calculated by addingall entries of the Nth row of the M matrix, i.e.,q? =N?j=1mN,j (6.25)164Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2where q? is the average number of queries required to identify all of the N tags in thesystem. Using the above formulation, there is no need to run multiple simulations andaverage them to obtain the number of queries needed to identify all tags in the system,instead, we can simply use Eq. (6.25) and calculate q? directly.6.2.4 Expected Number of Transmitted ChipsAfter deriving the closed form expression of the expected number of queries, we need toderive the closed form expression of the aggregate number of chips that are sent by thetags, before they are successfully identified by the reader. According to [3], we assume thateach tag ID is 96 bits long. Assuming that each tag selects a spreading code of length l outof the total d codes at random, the total number of transmitted chips in the CDMA-basedsystem isTC = q? ? l ? 96 (6.26)where TC shows the total expected number of transmitted chips, q? is the expected numberof queries calculated from Eq. (6.25), and l is the length of spreading codes used by tags.6.3 Performance ComparisonThis section presents the results of the simulation experiments we carried to evaluate theperformance of the CDMA-based tag identification schemes and to compare it with thestandard EPC Gen-2 protocol. To compare these schemes, we use the Markov modelproposed for the EPC Gen-2 protocol in Chapter 5 as well as the one we developed inthis chapter for the CDMA-based tag identification procedure. Using these analyticalmodels, we calculate the expected number of queries required to identify all the tags in165Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-20 20 40 60 80 100 120 140 160 180 200100101102103104105nq?CDMA (l = 16)CDMA (l = 31)CDMA (l = 64)EPC Gen-2Figure 6.3: The expected number of required queries q? for detecting all tags vs. thenumber of tags in the system for both the EPC protocol (c = 0.2) and the CDMA-basedtag identification scheme (l = 16, 31, 64).the system for both the EPC Gen-2 and the CDMA schemes. We also use these analyticalmodels to calculate and compare the total number of bits transmitted using the EPCGen-2 protocol and the total number of chips transmitted using the CDMA-based tagidentification scheme. All simulations have been performed in the MATLAB environment.We first consider an RFID system which operates based on the EPC Gen-2 protocol.We initialize c to 0.2, vary n (the number of tags in the system) between 0 and 200, andcalculate the number of queries needed to identify all tags in the RFID system. Then, weconsider a CDMA-based RFID system and calculate the number of queries required whenit uses spreading codes of length 16, 31 and 64 chips, respectively. Performance comparisonof the two systems (in terms of the expected number of queries) is shown in Fig. 6.3. Asexpected, the CDMA-based scheme outperforms the EPC Gen-2 protocol in terms of the166Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-20 20 40 60 80 100 120 140 160 180 200102103104105106107108nTDCDMA (l = 16)CDMA (l = 31)CDMA (l = 64)EPC Gen-2Figure 6.4: The total transmitted data TD for detecting all tags vs. the number of tagsin the system for both the EPC protocol (c = 0.2) and the CDMA-based tag identificationscheme (TDEPC = TB, TDCDMA = TC, and l = 16, 31, 64).number of required queries. It is obvious that the more spreading codes the tags can choosefrom, the less chance there is for collisions and therefore, fewer queries are needed.Although the expected number of required queries in the CDMA-based tag identifica-tion schemes is fewer compared to the EPC Gen-2 protocol, it does not necessarily meanthat the CDMA schemes can identify the tags more efficiently. As mentioned in Section 6.1,the total transmitted data is another factor (and probably the more important one) to judgethe efficiency of the CDMA-based scheme and the EPC Gen-2 protocol. Assuming thateach chip (bit) needs t seconds to be transmitted, the total time needed to identify all tagsin the system is t?TD. Therefore, it is a plausible assumption that the total time neededto identify all tags in the system is a function (multiple) of the TD calculated in Chapter 5167Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2and Chapter 6. It should be noted that for the EPC Gen-2 protocol, TDEPC = TB andit is calculated using Eq. (5.34), and for the CDMA systems, TDCDMA = TC and it iscalculated using Eq. (6.26). Fig. 6.4 shows the total transmitted data for the EPC Gen-2protocol and the CDMA-based tag identification technique, assuming that the parameterc is set to 0.2 [3] and the CDMA scheme uses the spreading codes of length 16, 31 and64. Interestingly, it can be observed from the figure that the standard EPC Gen-2 pro-tocol outperforms the CDMA-based scheme in terms of the total transmitted data (andequivalently the total time needed to identify all tags). In other words, for all values of n,the EPC Gen-2 protocol detects all tags in the system using fewer number of transmittedbits compared to the number of transmitted chips in the CDMA-based tag identificationscheme.As explained in [3], the value of c in the EPC Gen-2 protocol can be chosen from 0.1 to0.5 by the designer based on the system requirements and the applications. Therefore, weset the value of c to 0.4 and repeated the above procedure again. The results are shownin Fig. 6.5 and 6.6. The expected number of queries is shown in Fig. 6.5 for both theEPC Gen-2 protocol and the CDMA-based tag identification scheme. As expected, theCDMA scheme needs fewer queries to identify all the tags in the system. It is obviousthat the more spreading codes the tags have to choose from, the fewer is the number ofcollisions and therefore, the fewer queries are needed. However, Fig. 6.6 reveals that theEPC Gen-2 protocol still outperforms the CDMA-based tag identification scheme in termsof the transmitted data needed to identify all tags in the system.6.4 SummaryIn this chapter, we studied the CDMA-based tag identification protocol and modeled itas an absorbing Markov chain. Then, we formulated the model and derived the closed168Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-20 20 40 60 80 100 120 140 160 180 200100101102103104105nq?CDMA (l = 16)CDMA (l = 31)CDMA (l = 64)EPC Gen-2Figure 6.5: The total transmitted data TD for detecting all tags vs. the number of tagsin the system for both the EPC protocol (c = 0.4) and the CDMA-based tag identificationscheme (l = 16, 31, 64).form analytical expressions for the expected number of queries and the total transmitteddata needed to identify all tags in the system. We also used the absorbing Markov modelproposed in Chapter 5 for the EPC Gen-2 protocol. Using these two analytical models,the CDMA-based tag identification procedure was compared with the standard EPC Gen-2protocol in terms of the total expected number of queries and the total transmitted datarequired to identify all tags in the RFID systems.It was shown that the expected number of queries decreases if the CDMA techniqueis used for the tag identification purpose instead of the EPC Gen-2 protocol. This isbecause the number of collisions decreases when the CDMA technique is used. It is obviousthat the more spreading codes used by the tags, the less chance for collisions and thefewer the expected number of queries. However, the story is different for the amount169Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-20 20 40 60 80 100 120 140 160 180 200102103104105106107108nTDCDMA (l = 16)CDMA (l = 31)CDMA (l = 64)EPC Gen-2Figure 6.6: The total transmitted data TD for detecting all tags vs. the number of tagsin the system for both the EPC protocol (c = 0.4) and the CDMA-based tag identificationscheme (TDEPC = TB, TDCDMA = TC, and l = 16, 31, 64).of data that should be transmitted, and for the time needed to identify all tags in thesystem. Our study revealed that the EPC Gen-2 protocol outperforms the CDMA-basedtag identification scheme in terms of the total transmitted data (and of course the total timeneeded) to identify all the tags in the RFID systems. Reducing the total transmitted data(and consequently reducing the required tag identification time) was the main idea behindproposing the CDMA technique for RFID applications. However, this study revealedthat the CDMA technique cannot beat the EPC Gen-2 protocol in terms of the totaltransmitted data and the required time. Therefore, changing the current standard protocoland modifying the hardware architecture of the current passive RFID tags (to make themcapable of performing CDMA transmission) may not be a better solution. It should benoted that we did not design our analytical model based on the first or second CDMA170Chapter 6. Performance Analysis of RFID Protocols: CDMA vs. EPC Gen-2scenarios mentioned in Section 6.2.1. Therefore, the proposed analytical model and theperformance evaluation results are valid for both the first and second scenarios.It should also be noted that in the proposed analytical model, it was assumed that wehave complete synchronization between the reader and all the tags. This means that all thetags transmit their IDs concurrently and in complete synchronization with the reader. Itwas also assumed that the spreading codes used by the tags are orthogonal codes (like Walshcodes) with zero cross-correlation [77, 121]. In reality, however, complete synchronizationis a hard condition to achieve. Therefore, it has been suggested to use PN sequences likeGold and Kasami codes instead of orthogonal codes [61]. PN codes have better cross-correlation specifications compared to orthogonal codes, and therefore, can better toleratepoor synchronization situations. However, more queries would be needed if PN codes areused instead of the orthogonal codes, due to the autocorrelation characteristics of the PNcodes. In other words, we modeled and formulated the CDMA-based tag identificationscheme under ideal conditions (assuming complete synchronization and using orthogonalcodes). The expected number of queries and the total transmitted data would increase ifany of the two mentioned conditions is not satisfied. Fig. 6.3 to Fig. 6.6 show the bestpossible (the ideal) performance of the CDMA-based tag identification system. This workcan be extended by considering the synchronization problem and the autocorrelation issueof the PN codes in our Markov model as a future work.In this chapter, the proposed Markov model was used to formulate the CDMA-basedtag identification scheme and to calculate the expected number of queries and the totaltransmitted data. This analytical model, however, can be used for many other purposessuch as estimating the number of tags in an area of interest or for improving the perfor-mance of RFID systems.171Chapter 7Conclusions and Future WorkIn this chapter, we conclude the thesis by summarizing our results and highlighting thecontributions of this dissertation. We also suggest several topics for further research.7.1 Research ContributionsThe four analytical models we developed for RFID systems are the most important contri-butions of this thesis. We developed an analytical model for RFID systems that operatebased on the binary tree walking technique. We also developed an analytical model forRFID systems that operate based on the ALOHA technique. To the best of our knowledge,the probabilistic analysis of the binary tree walking-based and ALOHA-based RFID sys-tems has been accomplished in this thesis for the first time. In this thesis, we modeled thetag identification process of the EPC Class-1 Gen-2 UHF standard as an absorbing Markovchain, and developed an accurate analytical model for it. The tag identification processused by the EPC Class-1 Gen-2 UHF standard is exactly the same as the one used bythe EPC Class-1 HF standard. Therefore, the analytical model we developed for the EPCClass-1 Gen-2 UHF standard can be directly applied to the EPC Class-1 HF standard.Prior to our Markov model, there was only one other analytical model for the EPC Class-1Gen-2 standard [1]. We also modeled the CDMA-based RFID systems as an absorbingMarkov chain, and developed an accurate analytical model for these systems. To the bestof our knowledge, the use of a Markov model for the CDMA tag identification technique172Chapter 7. Conclusions and Future Workhas been proposed in this thesis for the first time. The four analytical models developedin this thesis can be used in multiple areas and for different purposes, as explained inChapter 1.In this thesis, we considered two challenging areas in RFID systems. First, we studiedthe security and privacy of RFID systems in Chapters 2 and 3, and proposed severalsolutions to improve the security and privacy of RFID systems. In the second step, wefocused on the efficiency of the tag singulation schemes in RFID systems. We performedanalytical modeling and performance analysis of the tag singulation schemes in Chapters 4,5 and 6. Below is the detailed list of our contributions in each chapter.? In Chapter 2, we first studied the blocking attack in RFID systems that operatebased on the binary tree walking tag singulation mechanism, and developed an an-alytical model for this attack against the binary tree walking-based RFID systems.Using the analytical model developed, we proposed a probabilistic blocker tag detec-tion algorithm (P-BTD) to detect the presence of an attacker in this type of RFIDsystems. Then, we focused on RFID systems that operate based on the ALOHA tagsingulation mechanism, and developed an analytical model for the blocking attackagainst the ALOHA-based RFID systems. Using this analytical model, we proposeda probabilistic blocker tag detection algorithm (P-BTD) to detect the presence of anattacker in this type of RFID systems. Simulation results revealed that the proposedP-BTD algorithms expedite the blocker detection process in both the binary treewalking and ALOHA-based RFID systems.? In Chapter 3, we investigated the security and privacy issues of the standard EPCGen-2 protocol, and studied the use of light-weight cryptography for increasing thesecurity and privacy in RFID systems. We performed the security analysis of severallight-weight RFID protocols recently proposed for RFID applications, and showed173Chapter 7. Conclusions and Future Worktheir vulnerabilities. Using this security analysis, we proposed a new light-weightauthentication protocol which improves the level of security and privacy in RFIDsystems. In designing the new light-weight protocol, the hardware limitation ofpassive RFID tags was taken into consideration.? In Chapter 4, we used the analytical model we derived in Chapter 3 to develop aprobabilistic tag estimation scheme. First, it was shown that the tag estimationmethod proposed in [2] is incorrect. Then, using the probabilistic model derivedin Chapter 3, we modified the model in [2] and proposed a new probabilistic tagestimation scheme for ALOHA-based RFID systems. In the proposed scheme, thereader estimates the number of RFID tags in the system after each interrogationbased on a posteriori probability and uses this estimated number to determine thenumber of required time slots for the next interrogation.? In Chapter 5, we studied the tag singulation mechanism in the EPC Gen-2 protocoland modeled it as an absorbing Markov chain. We formulated the proposed modeland derived the expected number of queries required by the EPC Gen-2 protocolto identify all RFID tags in the system. We also derived the expected number oftransmitted bits for the EPC Gen-2 protocol. These formulae allow us to provide ameasure of the speed of the EPC Gen-2 protocol in identifying all tags in the systemand the amount of data that should be transferred during this process.? In Chapter 6, we focused on the tag singulation process in CDMA-based RFIDsystems. We modeled the CDMA-based RFID systems as an absorbing Markovchain, and derived the closed form analytical expression for the average number ofqueries required and the total transmitted data needed to identify all tags in theCDMA-based RFID systems. Taking advantage of the Markov model proposed in174Chapter 7. Conclusions and Future WorkChapter 6 for the CDMA-based RFID systems and the one we developed for theEPC Gen-2 protocol in Chapter 5, the two tag singulation schemes were compared.It was shown that the EPC Gen-2 protocol outperforms the CDMA-based scheme interms of the total transmitted data and the average time needed to identify all tagsin the system.7.2 Suggestions for Future WorkIn the following, we consider several interesting possibilities for extension of the currentwork.1. Finding an Analytical Model for the Probability of Error in the ProposedP-BTD Algorithms. In Chapter 2, we determined the probability of error forbinary tree walking and ALOHA-based P-BTD algorithms using simulations. How-ever, a better way is to use an analytical model to find the closed form expressionof the probability of error. This is not a straightforward task, but it is a worthwhilestudy as it will enable us to perform the sensitivity analysis and determine the effectof using inaccurate values of N , F and p on the final performance of the proposedP-BTD algorithms. Moreover, the performance of the proposed P-BTD algorithmscan be improved by modifying the decision criterion we used in Fig. 2.3 and Fig. 2.4.2. Extending the P-BTD Algorithm for the EPC Gen-2 Protocol. We de-veloped two P-BTD algorithms for detecting the presence of blocker tags in RFIDsystems that operate based on the binary tree walking or ALOHA mechanisms. How-ever, it seems that the tag singulation mechanism proposed by the EPC Gen-2 pro-tocol is dominating the binary tree walking and the ALOHA mechanisms in recentyears. On the other hand and to the best of our knowledge, no solution has been175Chapter 7. Conclusions and Future Workproposed so far for detecting the presence of blocker tags in RFID systems whichuse the EPC Gen-2 protocol. We have developed an absorbing Markov model forthe EPC Gen-2 protocol in Chapter 5. This absorbing Markov model can be usedalong with the probabilistic blocker tag detection approach we used in Chapter 2 toprovide a P-BTD algorithm for RFID systems that operate based on the EPC Gen-2protocol.3. Reducing the Security Issues of RFID-based e-Passports. In 2006, the USDepartment of State started embedding RFID chips in US passports to increase theirsecurity. Some European countries such as Germany and the Netherlands as well assome Asian countries like Malaysia also started issuing RFID embedded e-passports[24]. Starting on July 1, 2013, all newly issued Canadian passports will be e-Passports[122]. Although using the e-passports can make it harder for unauthorized persons toforge them and expedite the check-in process at airports, it can add serious threatsand put the security, personal information and even the life of an e-passport holderinto great risks [9, 24, 25]. The security of RFID-based e-passports has been a greatconcern for many countries and this is considered as an open problem today.4. Improving the Q-Algorithm Using Probabilistic Tag Estimation. In Chap-ter 4, we introduced a new probabilistic method to estimate the number of tags inALOHA-based RFID systems. We also developed an analytical model for the Q-algorithm and the tag singulation process of the EPC Gen-2 protocol in Chapter 5.These two techniques can be combined to provide a more efficient tag singulationprocess for RFID systems. In the traditional Q-algorithm used by the EPC Gen-2 protocol, the values of Qfp are changed heuristically based on the responses thereader had received from the tags during its previous query. We can design a moreadvanced Q-algorithm which uses a probabilistic tag estimation method (similar to176Chapter 7. Conclusions and Future Workthe one proposed in Chapter 4) to first estimate the number of tags in the systemand then change the value of Qfp for the next query accordingly. This techniqueadds some computational costs to the system, however, these computational costsare added to the reader only, and not to the tags. In return, the tag singulationefficiency will increase using the advanced Q-algorithm.5. Synchronization and Orthogonality Issues in CDMA-based RFID Sys-tems. In the analytical model proposed for CDMA-based RFID systems in Chap-ter 6, it was assumed that we have complete synchronization between the readerand all the tags. This means that all the tags transmit their chips concurrentlyand in complete synchronization with the reader. It was also assumed that thespreading codes used by the tags are orthogonal codes (like Walsh codes) with zerocross-correlation [77, 121]. In reality, however, complete synchronization is a hardcondition to achieve. Therefore, it has been suggested to use PN sequences like Goldand Kasami codes instead of orthogonal codes [61]. PN codes have better cross-correlation specifications compared to orthogonal codes, and therefore, can bettertolerate poor synchronization situations. However, the autocorrelation of the PNcodes is not as good as the orthogonal codes, therefore, more queries would be neededif PN codes are used instead of the orthogonal codes. We modeled and formulated theCDMA-based tag identification scheme under ideal conditions (assuming completesynchronization and using orthogonal codes). The expected number of queries andthe total transmitted data would increase for sure if any of the two mentioned condi-tions is not satisfied. This work can be extended by considering the synchronizationproblem and the autocorrelation issue of the PN codes in our Markov model.177Bibliography[1] C. Wang, M. Daneshmand, K. Sohrabi, and B. Li, ?Performance analysis of RFIDgeneration-2 protocol,? IEEE Trans. on Wireless Communications, vol. 8, no. 5, pp.2592?2601, May 2009.[2] W.-T. Chen, ?An accurate tag estimate method for improving the performance ofan RFID anticollision algorithm based on dynamic frame length ALOHA,? IEEETrans. on Automation Science and Engineering, vol. 6, no. 1, pp. 9?15, Jan. 2009.[3] EPCglobal, ?EPC Radio-Frequency Identity Protocols: Class-1 Generation-2 UHFRFID Protocol for Communications at 860 MHz-960 MHz Version 1.2,? Oct. 2008.[Online]. Available: http://www.epcglobalinc.org/standards/uhfc1g2[4] H. M. Sun and W. C. Ting, ?A Gen2-based RFID authentication protocol for securityand privacy,? IEEE Trans. on Mobile Computing, vol. 8, no. 8, pp. 1052?1062, Aug.2009.[5] D. Henrici and P. Mu?ller, ?Hash-based enhancement of location privacy for radio-frequency identification devices using varying identifiers,? in Proc. of IEEE PER-COM?04, Orlando, FL, Mar. 2004.[6] T. L. Lim, T. Li, and T. Gu, ?Secure RFID identification and authentication withtriggered hash chain variants,? in Proc. of IEEE ICPADS?08, Melbourne, Australia,Dec. 2008.[7] C. C. Tan, B. Sheng, and Q. Li, ?Secure and serverless RFID authentication andsearch protocols,? IEEE Trans. on Wireless Communications, vol. 7, no. 4, pp. 1400?1407, Apr. 2008.[8] S. Ahson and M. Ilyas, RFID Handbook: Applications, Technology, Security, andPrivacy. CRC Press, 2008.[9] M. Meingast, J. King, and D. K. Mulligan, ?Embedded RFID and everyday things:A case study of the security and privacy risks of the U.S. E-passports,? in Proc. ofIEEE Int?l Conf. on RFID, Grapevine, TX, Mar. 2007.[10] V. Shah-Mansouri and V. W. Wong, ?Cardinality estimation in RFID systems withmultiple readers,? IEEE Trans. on Wireless Communications, vol. 10, no. 5, pp.1458?1469, May 2011.178Bibliography[11] A. Cangialosi, J. E. Monaly, and C. S. Yang, ?Leveraging RFID in hospitals: Patientlife cycle and mobility perspectives,? IEEE Communications Magazine, vol. 45, no. 9,pp. 18?23, Sept. 2007.[12] A. Juels, ?RFID security and privacy: A research survey,? IEEE J. on Selected Areasin Communication, vol. 24, no. 2, pp. 381?394, Feb. 2006.[13] J. Banks, M. Pachano, L. Thompson, and D. Hanny, RFID Applied. John Wiley,2007.[14] S. Shepard, RFID: Radio Frequency Identification. McGraw-Hill, 2005.[15] D. Ma and A. K. Prasad, ?A context-aware approach for enhanced security andprivacy in RFID electronic toll collection systems,? in Proc. of ICCCN, Hawaii, HI,Aug. 2011.[16] X. Guangxian, ?The research and application of RFID technologies in highwayselectronic toll collection system,? in Proc. of WiCOM, Dalian, China, Oct. 2008.[17] [Online]. Available: http://www.gs1.org/gsmp/kc/epcglobal[18] J. Ayoade, ?Roadmap to solving security and privacy concerns in RFID systems,?Computer Law and Security Report, vol. 23, pp. 555?561, Sept. 2007.[19] M. Langheinrich, ?A survey of RFID privacy approaches,? Personal and UbiquitousComputing, vol. 13, pp. 413?421, Aug. 2009.[20] E. Vahedi, V. Shah-Mansouri, V. Wong, I. F. Blake, and R. K. Ward, ?Probabilisticanalysis of blocking attack in RFID systems,? IEEE Trans. on Information Forensicsand Security, vol. 6, no. 3, pp. 803?817, Sept. 2011.[21] D. Molnar and D. Wagner, ?Privacy and security in library RFID: issues, prac-tices, and architectures,? in Proc. of Computer and Communications Security Conf.,Washington, DC, Oct. 2004.[22] A. Juels and R. Pappu, ?Squealing Euros: Privacy protection in RFID-enabled ban-knotes,? in Proc. of Financial Cryptography Conf., Guadeloupe, Jan. 2003.[23] Y. Xiao, X. Shen, B. Sun, and L. Cai, ?Security and privacy in RFID and applicationsin telemedicine,? IEEE Communications Magazine, vol. 44, no. 4, pp. 64?72, Apr.2006.[24] A. Juels, D. Molnar, and D. Wagner, ?Security and privacy issues in e-passports,? inProc. of Int?l Conf. on Security and Privacy for Emerging Areas in CommunicationsNetworks, Athens, Greece, Sept. 2005.179Bibliography[25] J. H. Hoepman, E. Hubbers, B. Jacobs, M. Oostdijk, and R. W. Schreur, ?Crossingborders: Security and privacy issues of the European e-passport,? in Proc. of Int?lWorkshop on Security, Kyoto, Japan, Oct. 2006.[26] R. C. W. Phan, ?Cryptanalysis of a new Ultra-lightweight RFID authenticationprotocol-SASI,? IEEE Trans. on Dependable and Secure Computing, vol. 6, no. 1,pp. 316?320, Mar. 2009.[27] H. Liu and H. Ning, ?Zero-knowledge authentication protocol based on alternativemode in RFID systems,? IEEE Sensors Journal, vol. 11, no. 12, pp. 3235?3245, Dec.2011.[28] D. Maimut and K. Ouafi, ?Light-weight cryptography for RFID tags,? IEEE Securityand Privacy, vol. 10, no. 2, pp. 76?79, Apr. 2012.[29] E. Blass, A. Kurmus, R. Molva, G. Noubir, and A. Shikfa, ?The ff -family of proto-cols for RFID-privacy and authentication,? IEEE Trans. on Dependable and SecureComputing, vol. 8, no. 3, pp. 466?480, June 2011.[30] P. Rizomiliotis, E. Rekleitis, and S. Gritzalis, ?Security analysis of the Song-Mitchellauthentication protocol for low cost RFID tags,? IEEE Commun. Letters, vol. 13,no. 4, pp. 274?276, Apr. 2009.[31] H. M. Sun, W. C. Ting, and K. H. Wang, ?On the security of the Chien?s ultra-lightweight RFID authentication protocol,? IEEE Trans. on Dependable and SecureComputing, vol. PP, no. 99, pp. 1?3, July 2009.[32] S. Piramuthu, ?Lightweight cryptographic authentication in passive RFID-taggedsystems,? IEEE Trans. on Systems, Man, and Cybernetics, vol. 38, no. 3, pp. 360?376, May 2008.[33] B. Calmels, S. Canard, M. Girault, and H. Sibert, ?Low cost cryptography for privacyin RFID systems,? in Proc. of Int?l Conf. on Smart Card Research and AdvancedApplication, Tarragona, Spain, Apr. 2006.[34] T. Dimitriou, ?A lightweight RFID protocol to protect against traceability andcloning attacks,? in Proc. of Int?l Conf. on Security and Privacy for Emerging Areasin Communications Networks, Athens, Greece, Sept. 2005.[35] J. Wu and D. R. Stinson, ?How to improve security and reduce hardware demandsof the WIPR RFID protocol,? in Proc. of IEEE Int?l Conf. on RFID, Orlando, FL,Apr. 2009.[36] H. Y. Chien, ?SASI: A new ultralightweight RFID authentication protocol providingstrong authentication and strong integrity,? IEEE Trans. on Dependable and SecureComputing, vol. 4, no. 4, pp. 337?340, Dec. 2007.180Bibliography[37] T. Cao, E. Bertino, and H. Lei, ?Security analysis of the SASI protocol,? IEEETrans. on Dependable and Secure Computing, vol. 6, no. 1, pp. 73?77, Mar. 2009.[38] S. Dolev, M. Kopeetsky, and A. Shamir, ?RFID authentication, efficient proactiveinformation security within computational security,? Theory of Computing Systems,vol. 48, no. 1, pp. 132?149, Jan. 2011.[39] Y. K. Lee, K. Sakiyama, L. Batina, and I. Verbauwhede, ?Elliptic curve-based secu-rity processor for RFID,? IEEE Trans. on Computers, vol. 57, no. 11, pp. 1514?1527,Nov. 2008.[40] F. Furbass and J. Wolkerstorfer, ?ECC processor with low die size for RFID appli-cations,? in Proc. of IEEE Int?l Symposium on Circuits and Systems, New Orleans,LA, May 2007.[41] S. I. Ahmed, F. Rahman, and M. E. Hoque, ?ERAP: ECC-based RFID authentica-tion protocol,? in Proc. of 12th IEEE Int?l Workshop on Future Trends of DistributedComputing Systems, Kunming, China, Oct. 2008.[42] L. Batina, J. Guajardo, T. Kerins, N. Mentens, P. Tuyls, and I. Verbauwhede, ?Publickey cryptography for RFID tags,? in Proc. of 5th IEEE Int?l Conf. on PervasiveComputing and Communications Workshop, White Plains, NY, Mar. 2007.[43] M. Feldhofer, S. Dominikus, and J. Wolkerstorfer, ?Strong authentication for RFIDsystems using the AES algorithm,? in Proc. of Int?l Workshop on CryptographicHardware and Embedded Systems, Cambridge, MA, Aug. 2004.[44] D. E. Holcomb, W. P. Burleson, and K. Fu, ?Power-Up SRAM state as an identify-ing fingerprint and source of true reandom numbers,? IEEE Trans. on Computers,vol. 58, no. 9, pp. 1198?1210, Sept. 2009.[45] A. Juels, R. Rivest, and M. Szydlo, ?The blocker tag: Selective blocking of RFID tagsfor consumer privacy,? in Proc. of Computer and Communications Security Conf.,Washington, DC, Oct. 2003.[46] G. Karjoth and P. Moskowitz, ?Disabling RFID tags with visible confirmation:Clipped tags are silenced,? in Proc. of ACM Workshop on Privacy in the ElectronicSociety, Alexandria, VA, Nov. 2005.[47] S. Inoue and H. Yasouura, ?RFID privacy using user-controllable uniqueness,? inProc. of RFID Privacy Workshop, Boston, MA, Nov. 2003.[48] D. Shih, R. Sun, D. Yen, and S. Huang, ?Taxonomy and survey of RFID anti-collisionprotocols,? Computer Communications, vol. 29, no. 11, pp. 2150?2166, July 2006.181Bibliography[49] J. Myung and W. Lee, ?Adaptive splitting protocols for RFID tag collision arbitra-tion,? in Proc. of ACM MobiHoc, Florence, Italy, May 2006.[50] Y.-C. Ko, S. Roy, J. R. Smith, H.-W. Lee, and C.-H. Cho, ?An enhanced dynamicRFID multiple access protocol for fast inventory,? in Proc. of IEEE Globecom, Wash-ington, DC, Nov. 2007.[51] J. S. Choi, H. Lee, D. W. Engels, and R. Elmasri, ?Robust and dynamic bin slottedanti-collision algorithms in RFID systems,? in Proc. of IEEE Int?l Conf. on RFID,Las Vegas, NV, Apr. 2008.[52] H. Koh, S. Yun, and H. Kim, ?Sidewalk: A RFID tag anti-collision algorithm ex-ploiting sequential arrangements of tags,? in Proc. of IEEE ICC, Beijing, China,May 2008.[53] J.-B. Eom, T.-J. Lee, R. Rietman, and A. Yener, ?Efficient framed-slotted Alohaalgorithm with pilot frame and binary selection for anti-collision of RFID tags,?IEEE Communications Letters, vol. 12, no. 11, pp. 861?863, Nov. 2008.[54] C.-H. Quan, J.-C. Choi, G.-Y. Choi, and C.-W. Lee, ?The Slotted-LBT: A RFIDreader medium access scheme in dense reader environments,? in Proc. of IEEE Int?lConf. on RFID, Las Vegas, NV, Apr. 2008.[55] C. Floerkemeier, ?Bayesian transmission strategy for framed ALOHA based RFIDprotocols,? in Proc. of IEEE RFID Conf., Grapevine, TX, Mar. 2007.[56] G. Mazurek, ?Active RFID system with spread-spectrum transmission,? IEEE Trans.on Automation Science and Engineering, vol. 6, no. 1, pp. 25?32, Jan. 2009.[57] Y. Lai and C. Lin, ?Two blocking algorithms on adaptive binary splitting: Singleand pair resolution for RFID tag identification,? IEEE/ACM Trans. on Networking,vol. 17, no. 3, pp. 962?975, June 2009.[58] H. Wu and Y. Zeng, ?Efficient framed slotted aloha protocol for RFID tag anti-collision,? IEEE Trans. on Automation Science and Engineering, vol. 8, no. 3, pp.581?588, July 2011.[59] Y. Lai and L. Y. Hsiao, ?General binary tree protocol for coping with the captureeffect in RFID tag identification,? IEEE Communications Letters, vol. 14, no. 3, pp.208?210, Mar. 2010.[60] G. Mazurek, ?Design of RFID system with DS-CDMA transmission,? in Proc. ofIEEE CASE, Washington DC, Aug. 2008.[61] C. Mutti and C. Floerkemeier, ?CDMA-based RFID systems in dense scenarios:Concepts and challenges,? in Proc. of IEEE RFID, Las Vegas, NV, Apr. 2008.182Bibliography[62] T. Demeechai and S. Siwamogsatham, ?Using CDMA to enhance the MAC perfor-mance of ISO/IEC 18000-6 type C,? IEEE Communications Letters, vol. 15, no. 10,pp. 1129?1131, Oct. 2011.[63] J. Y. Maina, M. H. Mickle, M. R. Lovell, and L. A. Schaefer, ?Application of CDMAfor anti-collision and increased read efficiency of multiple RFID tags,? Journal ofManufacturing Systems, vol. 26, no. 1, pp. 37?43, June 2008.[64] H. Liu, M. Bolic, A. Nayak, and I. Stojmenovic, ?Taxonomy and challenges of theintegration of RFID and wireless sensor networks,? IEEE Networks, vol. 22, no. 6,pp. 26?35, Dec. 2008.[65] L. Wuu, Y. Chen, C. Hung, and W. Kuo, ?Zero-collision RFID tags identificationbased on CDMA,? in Proc. of IAS, Xian, China, Aug. 2009.[66] A. Loeffler, F. Schuh, and H. Gerhaeuser, ?Realization of a CDMA-based systemusing a semi-active UHF transponder,? in Proc. of ICWMC, Valencia, Spain, Sept.2010.[67] P. Wang, A. Hu, and W. Pei, ?The design of anti-collision mechanism of UHF RFIDsystem based on CDMA,? in Proc. of IEEE APCCAS, Singapore, Dec. 2006.[68] T. S. L. Porta, G. Maselli, and C. Petrioli, ?Anticollision protocols for single-readerRFID systems: Temporal analysis and optimization,? IEEE Trans. on Mobile Com-puting, vol. 10, no. 2, pp. 267?279, Feb. 2011.[69] H. Vogt, ?Efficient object identification with passive RFID tags,? in Proc. of Int?lConf. on Pervasive Computing, Zurich, Switzerland, Aug. 2002.[70] J.-B. Eom and T.-J. Lee, ?Accurate tag estimation for dynamic framed-slotted alohain rfid systems,? IEEE Communications Letters, vol. 14, no. 1, pp. 60?62, Jan. 2010.[71] C.-F. Lin and F. Y.-S. Lin, ?Efcient estimation and collision-group-based anticolli-sion algorithms for dynamic frame-slotted aloha in rfid networks,? IEEE Trans. onAutomation Science and Engineering, vol. 7, no. 4, pp. 840?848, Oct. 2010.[72] M. Kodialam and T. Nandagopal, ?Fast and reliable estimation schemes in RFIDsystems,? in Proc. of ACM Mobicom Conf., Los Angeles, CA, Sept. 2006.[73] J. Park, M. Y. Chung, and T. J. Lee, ?Identification of RFID tags in framed-slottedALOHA with robust estimation and binary selection,? IEEE Commun. Letters,vol. 11, pp. 452?454, May 2007.[74] H. Wu and Y. Zeng, ?Bayesian tag estimate and optimal frame length for anti-collision ALOHA RFID system,? IEEE Trans. on Automation Science and Engi-neering, vol. 7, no. 4, 0.183Bibliography[75] I. Onat and A. Miri, ?A tag count estimation algorithm for dynamic framed ALOHAbased RFID MAC protocols,? in Proc. of IEEE ICC, Kyoto, Japan, June 2011.[76] EPCglobal, ?EPC Radio-Frequency Identity Protocols: EPC Class-1 HF RFIDAir Interface Protocol for Communications at 13.56 MHz,? 2011. [Online].Available: http://www.gs1.org/sites/default/files/docs/epcglobal/epcglobal hf 2 03-standard-20110905r3.pdf[77] L. Hanzo and M. M OFDM and MC-CDMA for Broadcasting Multi-user Communi-cations, WLANs and Broadcasting. John Wiley, 2003.[78] R. Prasad and T. Ojanpera, ?An overview of CDMA evolution toward widebandCDMA,? IEEE Communications Surveys, vol. 1, no. 1, pp. 2?29, Mar. 1998.[79] E. Vahedi, V. Shah-Mansouri, V. Wong, and I. F. Blake, ?A probabilistic approachfor detecting blocking attack in RFID systems,? in Proc. of IEEE ICC, Cape Town,South Africa, May 2010.[80] E. Vahedi, R. K. Ward, V. Shah-Mansouri, V. W. Wong, and I. F. Blake, ?Onsecuring RFIDs against blocking attacks,? IEEE MMTC Letter, vol. 2, no. 6, pp.16?18, Dec. 2011.[81] E. Vahedi, R. K. Ward, and I. F. Blake, ?Security analysis and complexity comparisonof some recent light-weight RFID protocols,? in LNCS 6694 (Springer-Heidelberg),Malaga, Spain, June 2011.[82] ??, ?Toward a secure light-weight protocol for RFID systems,? IET Journal ofInformation Security, submitted.[83] E. Vahedi, V. Wong, and I. F. Blake, ?A note on a probabilistic analysis of an accuratetag estimate method,? IEEE Trans. on Automation Science and Engineering, vol. 8,no. 3, pp. 659?663, July 2011.[84] E. Vahedi, R. K. Ward, and I. F. Blake, ?Analytical modeling of RFID generation-2 protocol using absorbing markov chain theorem,? in Proc. of IEEE Globecom,Anaheim, CA, Dec. 2012.[85] ??, ?Analytical modeling and performance analysis of RFID generation-2 proto-col,? IEEE Trans. on Wireless Communications, submitted.[86] ??, ?Performance analysis of RFID protocols: CDMA vs. the standard EPC Gen-2,? IEEE Trans. on Automation Science and Engineering, submitted.[87] Draft protocol specification for a 900 MHz class 0 Radio Frequency IdentificationTag. Auto-ID Center, 2003.184Bibliography[88] J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, ?A hybrid query tree protocol forRFID systems,? in Proc. of IEEE ICC, China, June 2007.[89] S. S. Choi, Y. S. Hong, and S. K. Kim, ?Dynamic framed ALOHA algorithm usinga collision factor in RFID systems,? in Proc. of IEEE VTC-Fall, Barcelona, Spain,Sept. 2009.[90] D. Liu, Z. Wang, J. Tan, H. Min, and J. Wang, ?ALOHA algorithm considering theslot duration difference in RFID system,? in Proc. of IEEE RFID Conf., Orlando,FL, Apr. 2009.[91] I. Onat and A. Miri, ?DiSEL: A distance based slot selection protocol for framedslotted ALOHA RFID systems,? in Proc. of IEEE WCNC, Budapest, Hungary, Apr.2009.[92] S. Geng, D. M. Gao, C. Zhu, M. He, and W. C. Wu, ?An improved dynamic framedslotted ALOHA algorithm for RFID anti-collision,? in Proc. of IEEE ICSP, Leipzig,Germany, Oct. 2008.[93] M. Kodialam, T. Nandagopal, and W. C. Lau, ?Anonymous tracking using RFIDtags,? in Proc. of IEEE Infocom, Anchorage, AK, May 2007.[94] M. Roberti, ?Wal-Mart relaunches EPC RFID effort, starting with men?s jeans andbasics,? RFID Journal, July 2010.[95] W. Feller, An Introduction to Probability Theory and Its Applications. John Wiley,1957.[96] J. Riordan, An Introduction to Combinatorial Analysis. John Wiley, 1958.[97] G. Avoine and P. Oechslin, ?RFID traceability: A multilayer problem,? in Proc. ofFinancial Cryptography and Data Security, Roseau, Dominica, Feb. 2005.[98] A. Shamir, ?SQUASH-A new MAC with provable security properties for highly con-strained devices such as RFID tags,? in Proc. of FSE, Lausanne, Switzerland, Feb.2008.[99] L. Lamport, ?Password authentication with insecure communication,? Communica-tions of the ACM, vol. 24, no. 11, pp. 770?772, Nov 1981.[100] M. Feldhofer and C. Rechberger, ?A case against currently used hash functions inRFID protocols,? in Proc. of RFID Security, Graz, Austria, Sept. 2006.[101] D. Engels, X. Fan, G. Gong, H. Hu, and E. M. Smith, ?Hummingbird: Ultra-Lightweight Cryptography for Resource-Constrained Devices,? in Proc. of FCDS,Tenerife, Spain, Jan. 2010.185Bibliography[102] D. Engels, M. O. Saarinen, P. Schweitzer, and E. M. Smith, ?The Hummingbird-2Lightweight Authenticated Encryption Algorithm,? in Proc. of RFIDSec, Amherst,MA, June 2011.[103] X. Fan, G. Gong, K. Lauffenburger, and T. Hicks, ?FPGA Implementations of theHummingbird Cryptographic Algorithm,? in Proc. of HOST, Anaheim, CA, June2010.[104] M. Hell, T. Johansson, A. Maximov, and W. Meier, ?A stream cipher proposal:Grain-128,? in Proc. of ISIT, Seattle, WA, July 2006.[105] J. P. Aumasson, L. Henzen, W. Meier, and M. N. Plasencia, ?QUARK: a LightweightHash,? in Proc. of CHES, Santa Barbara, CA, Aug. 2010.[106] M. O. Rabin, Digitized Signatures and Public-Key Functions as Intractable as Fac-torization. MIT-TR 212, 1979.[107] J. Hermans, A. Pashalidis, F. Vercauteren, and B. Preneel, ?A new RFID privacymodel,? in Proc. of ESORICS, Leuven, Belgium, Sept. 2011.[108] R. Deng, Y. Li, M. Yung, and Y. Zhao, ?A new framework for RFID privacy,? inProc. of ESORICS, Athens, Greece, Sept. 2010.[109] A. Juels and S. A. Weis, ?Defining strong privacy for RFID,? in Proc. of PerCom,New York, USA, Mar. 2007.[110] S. Vaudenay, ?On privacy models for RFID,? in Proc. of ASIACRYPT, Kuching,MALAYSIA, Dec. 2007.[111] S. Wang, W. Hong, L. Yin, and S. Li, ?A novel fast tag estimate method for dynamicframe length aloha anti-collision algorithms in RFID system,? in Proc. of IEEE VTC,Quebec City, Canada, Sept. 2012.[112] S.-D. J. S.-R. Lee and C.-W. Lee, ?An enhanced dynamic framed aloha algorithmfor RFID tag identication,? in Proc. of MOBIQUITOUS, San Diego, CA, July 2005.[113] C. Quan, Y. Liu, H. Ngan, and L. M. Ni, ?ASAP: Scalable identification and countingfor contactless RFID systems,? in Proc. of ICDCS, Genoa, Italy, June 2010.[114] Y. Zheng and M. Li, ?PET: Probabilistic estimating tree for large-scale RFID esti-mation,? IEEE Trans. on Mobile Computing, vol. 11, no. 11, pp. 1763?1774, Nov.2012.[115] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu, ?Counting RFID tagsefficiently and anonymously,? in Proc. of IEEE INFOCOM, San Diego, CA, Mar.2010.186Bibliography[116] C. Qian, H. Ngan, and Y. Liu, ?Cardinality estimation for large-scale RFID systems,?in Proc. of PerCom, Hong Kong, Mar. 2008.[117] Y. Sun, P. J. Hawrylak, and M. H. Mickle, ?Application of ICA in collision resolutionfor passive RFID communication,? in Proc. of WCECS, San Fransisco, CA, Oct.2009.[118] Y. Maguire and R. Pappu, ?An optimal Q-algorithm for ISO 18000-6C UHF RFID,?IEEE Trans. on Automation Science and Engineering, vol. 6, no. 1, pp. 16?24, Nov.2009.[119] H. Hirayama, Y. Satake, N. Kihuma, and K. Sakakibara, ?Improvement of null zoneavoidance capability for HF-band RFID using diversity combining of loop antennas,?in Proc. of 3rd European Conference on Antennas and Propagation, Berlin, Germany,Mar. 2009.[120] J. G. Kim, W. J. Shih, and J. H. Yoo, ?Performance analysis of EPC class-1generation-2 RFID anti-collision protocol,? LNCS, Springer, vol. 4707, pp. 1017?1026, Aug. 2007.[121] J. G. Proakis and M. Salehi, Communication Systems Engineering. Prentice Hall,2003.[122] Passport-Canada. [Online]. Available: http://www.ppt.gc.ca/eppt/about.aspx?lang=eng187
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Security, privacy and efficiency in RFID systems
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Security, privacy and efficiency in RFID systems Vahedi, Ehsan 2013
pdf
Page Metadata
Item Metadata
Title | Security, privacy and efficiency in RFID systems |
Creator |
Vahedi, Ehsan |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | Radio frequency identification (RFID) is a ubiquitous wireless technology that allows objects to be identified automatically. Using the RFID technology can simplify many applications and provide many benefits but meanwhile, the security and privacy of RFID systems should be taken into account. In this thesis, we have two goals. The first one is to improve the security and privacy in RFID systems. Our second goal is to provide accurate analytical models for the most important tag singulation schemes. We use these analytical models to evaluate and compare the efficiency of the tag singulation schemes. First, we study the blocking attack in RFID systems and develop an analytical model for it. Using this analytical model, we propose two probabilistic blocker tag detection (P-BTD) algorithms for RFID systems that operate based on the binary tree walking and ALOHA techniques. Then, we study the security and privacy of some recently introduced light-weight authentication protocols, and discuss their advantages and drawbacks. Based on this analysis and considering the hardware limitations of RFID tags, we propose a new authentication protocol that improves the security and privacy in RFID systems. By taking advantage of the analytical model we proposed for the ALOHA-based P-BTD algorithm, we develop an accurate tag estimate method. Using the proposed method, we can estimate the number of tags in RFID systems accurately, and design more efficient ALOHA-based tag singulation mechanisms. Next, we study the EPC Gen-2 protocol and its tag singulation mechanism. We model the EPC Gen-2 protocol as an absorbing Markov chain. Using the model proposed, we derive accurate analytical expressions for the expected number of queries and the expected number of transmitted bits needed to identify all tags in the RFID system. Finally, we study the use of the CDMA technique for RFID systems. We model the CDMA-based tag singulation procedure as an absorbing Markov chain, and derive accurate analytical expressions for the expected number of queries and the amount of transmitted data needed to identify all tags in the system. Using the analytical models developed, we compare the performance of the CDMA-based and the EPC Gen-2 tag singulation schemes. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2013-10-01 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
IsShownAt | 10.14288/1.0103285 |
URI | http://hdl.handle.net/2429/45181 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2013-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2013_fall_vahedi_ehsan.pdf [ 1.47MB ]
- Metadata
- JSON: 24-1.0103285.json
- JSON-LD: 24-1.0103285-ld.json
- RDF/XML (Pretty): 24-1.0103285-rdf.xml
- RDF/JSON: 24-1.0103285-rdf.json
- Turtle: 24-1.0103285-turtle.txt
- N-Triples: 24-1.0103285-rdf-ntriples.txt
- Original Record: 24-1.0103285-source.json
- Full Text
- 24-1.0103285-fulltext.txt
- Citation
- 24-1.0103285.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0103285/manifest