無線射頻辨識系統(Radio Frequency Identification, RFID)已被廣泛應用於各種不同的地方，其主要目的就是用來迅速且準確地識別出一個物件，RFID目前最廣泛的應用的是於供應鏈管理中用來取代條碼，有別於傳統的條碼，RFID具有免直線視野、對環境變化的忍受度高、更遠的讀取距離、更多的儲存容量、可追蹤性，與一次多重存取等特性。RFID系統由讀取器(Reader)、標籤(Tag)與後端伺服器系統(back-end host system)組成，其運作方式通常是先由讀取器發送特定工作頻率的無線射頻信號，而標籤一旦收到讀取器的信號便利用不同的頻率來進行回應。因為標籤與讀取器是透過無線通道來傳輸資訊的，一旦數個讀取器或標籤同時傳送資訊，將會導致訊號互相影響而無法辨別。多個RFID讀取器間往往可以透過實體線路互相連結，而RFID標籤卻因為資源的受限(大多沒有內部電源)，並沒有辦法互相溝通。因此，為了成功地單獨挑出每一個RFID標籤，我們必須使用特殊的方法來達成目標，這個方法就是防碰撞(anti-collision)協定。
我們首先針對現有的防碰撞協定做了概述，再根據每個協定的特性對這些協定進行分類與比較。在RFID系統中，現存的RFID防碰撞方法有Space Division Multiple Access (SDMA)、Time Domain Multiple Access (TDMA)、Frequency Domain Multiple Access (FDMA)與Code Division Multiple Access (CDMA)四大類，而其中又以TDMA最適用於RFID系統上且廣受討論。TDMA又可分成以讀取器來主導的Reader-driven與由標籤來主導的Tag-driven兩類，由於沒有內建電源的被動式標籤要進行防碰撞不是那麼容易，必須由讀取器來主導，所以我們的討論焦點會集中於Reader-driven中。Reader-driven又可分為許多方式來進行，其中利用ID來建立二元樹的協定我們稱作樹狀樣式協定，而使用到以時槽競爭概念為基礎的多重存取則是分類成ALOHA樣式協定，這也是現今的RFID標準大多採用的方式(如UHF的無線射頻辨識第二代標準EPCglobal Class 1 Generation 2所採用的Q-Algorithm即是ALOHA樣式協定)，因此本篇論文的重點將著重於這兩類協定的介紹。儘管已有相關研究針對RFID上的防碰撞協定進行分類，但並沒有涵蓋到最新被提出的防碰撞協定，所以我們充實了原有的分類，特別是在樹狀樣式協定與ALOHA樣式協定中，同時介紹了除TDMA外，近來還有以SDMA來達成多重存取目的之防碰撞協定。
除了傳輸碰撞的問題外，現今RFID的實際應用中還有安全性與隱私權的威脅，由於RFID標籤可能會洩漏它所貼附物品的資訊，使得一個躲在暗處的敵人可以悄悄追蹤或監控這個RFID標籤。因此，為了避免假冒的標籤欺騙合法的讀取器，令讀取器以為該標籤是合法標籤的一員，或讓假冒的讀取器欺騙合法的標籤，使得讀取器非法竊取該標籤的秘密資訊，我們必須在RFID系統中使用認證(authentication)協定，藉以確保標籤的安全性與隱私權不受威脅。雖然已有許多用來達成防碰撞或認證的協定，但沒有一個方法是十全十美，可以適用各個不同場景的需要。所謂的認證協定都是由一方送出一個challenge給被另一方來開始。舉例來說，若讀取器為發起者，則由讀取器送出一個challenge給標籤，而標籤在收到後就透過事先已與讀取器共享的一個秘密金鑰來算出 response (回應)，再送回給讀取器，接著由讀取器驗證該response是否與剛才送出的challenge配上共享秘密金鑰算出之結果相符，若符合，則讀取器可判定該標籤是合法的，並提供標籤所要求之服務，若不符則拒絕提供服務。而在這篇論文中，我們所探討的是一個由Hopper與Blum所提出的認證協定，簡稱HB認證協定，HB認證協定的安全性是基於推測LPN (Learning Parity with Noise)問題之困難度。HB認證協定與其他認證協定不同之處在於能與防碰撞協定相結合。除此之外，我們還介紹了HB認證協定的一些變種形式，並針對這些協定的安全性與效率進行比較。
過去總是把防碰撞協定與認證協定分開探討，並於防碰撞完成後才針對標籤個別進行認證協定，但實際上，在標籤數量多的場景下，這樣將耗費大量的資源與時間於這兩個目的上。所以我們提出了一個可同時進行的方法，叫做CRPA (Collision Resolution Protocol with Authentication)，在進行防碰撞協定時，令防碰撞協定指令挾帶著讀取器給標籤的認證用challenge，且於防碰撞完成後再由標籤將回應送給讀取器，藉以達到一石二鳥的目的。我們提出的CRPA協定其安全性也是基於推測LPN問題之困難度。透過將防碰撞指令與認證用的challenge同時送給標籤，讓傳輸資源得以共享，並且使得整個協定的流程更加有效率。換言之，相較於以往在完成防碰撞後才進行認證的方式，我們提出的方法能夠於完成防碰撞的同時，已完成大部分的認證協定程序，大大節省了認證標籤的時間，並且因為採取針對認證協定並行處理的緣故，也少了非常多的認證傳輸資料。除此之外，我們的協定沒有用到任何複雜的運算函數，所有需要的功能都能由現有的EPCglobal Class 1 Generation 2之標準配備來支援。我們提出的CRPA協定特別適用於在同時需要防碰撞協定與認證協定的多樣複合標籤的情況（譬如是檢查一堆含有RFID標籤的高價商品時）。若讀取器所預備送出的多個challenge能在進行防碰撞協定時所耗費的時槽內完全送出，則可以發揮CRPA協定的最大效能。舉例來說，在EPCglobal Class 1 Generation 2的防碰撞協定Q-Algorithm中，只要在場的標籤超過100個，我們所提出的CRPA協定便能發揮最高效能。在此論文中，我們也證實了這個CRPA協定的實用性與可行性，並能夠確保該協定在面對被動式攻擊下依舊保有安全性、隱私性與不可追蹤性。我們還提出了一個衍生型的CRPA，稱作ECRPA (Extended CRPA)。由於ECRPA利用決定性的方式來決定答錯機率，也就是讀取器收到的答案其錯誤率與翻轉機率完全一樣。因此能透過更少的答案數量來完成認證，儘管更少的答案數量會導致安全性略為降低，但卻能更適用於低成本的RFID標籤中。

Radio Frequency Identification (RFID) system has been widely used in many different areas. Its main purpose is to identify an object quickly. The most popular application of RFID is in supply chain management for barcode replacement. Different from traditional barcode, RFID has many advantages such as no line-of-sight requirement, high toleration of harsh environments, long read range, large storage space, traceability, and multiple reads at once. A RFID system consists of the Reader(s) (or Interrogator), the Tag(s) (or Transponder) and the back-end host system. Usually a reader sends a RF signal at the working frequency, and then the tag responds with a RF signal at different frequency. Because the information conveyed between the reader and the tag is through RF channel, if multiple readers or tags transmit data simultaneously, then these data may interfere with one another and can not be recognized. Multiple readers can communicate with each other via physical lines, however tags won’t be able to do that due to their limited resources (e.g., most tags do not have internal power). Therefore in order to singulate each tag by the reader successfully, we need a specific method, which is the anti-collision protocol to achieve this goal.
First, we present an overview of the existing anti-collision protocols and then we classify and compare them according to their major characteristics. The existing multiple access techniques in RFID system include Space Division Multiple Access (SDMA), Time Domain Multiple Access (TDMA), Frequency Domain Multiple Access (FDMA) and Code Division Multiple Access (CDMA) four major categories. TDMA is the most popular approach to achieve anti-collision and further divided into Reader-driven and Tag-driven. Because it is hard for a RFID passive tag without internal power to drive anti-collision actions, therefore we will concentrate our discussions only on the Reader-driven anti-collision schemes, which are the main streams in the passive tags environment. In those schemes, a reader must dominate the anti-collision protocol and tell the tags what they should do. Reader-driven protocols could be classified into two major approaches, one is tree-style since it uses the tag ID to build a binary tree, while the other is ALOHA-style since it uses a contention-based multiple access scheme to assign each tag into a unique timeslot. They are both widely used in today’s RFID standards and specifications (e.g., the EPCglobal Class 1 Generation 2 uses an anti-collision protocol named Q-Algorithm, which is an ALOHA-style protocol), therefore this thesis mainly addresses the tree-style protocols and ALOHA-style protocols. Although there already exist several taxonomies on the anti-collision protocols for RFID system, none of them has incorporated all the latest proposed protocols. Therefore, we enhance the existing taxonomies especially with a special focus on tree-style protocols and ALOHA-style protocols, and also add a recently proposed SDMA based anti-collision protocol which is different to the mainstream TDMA.
Besides the collision problem, RFID applications today also face the threats of security and privacy. A tag may leak the information of the tagged item if an invisible adversary could trace or monitor this item surreptitiously. In order to prevent either a fraudster who uses a counterfeit tag to cheat a legitimate reader into believing it is an authorized tag, or a fake reader intends to obtain the sensitive information from a legitimate tag, we need an authentication protocol to protect the security and privacy of the RFID system especially in the tags. Although many authentication protocols have been proposed, none of them is perfect and not suitable to be deployed in many different scenarios. The authentication protocol usually starts by sending a challenge from an authentication server / verifier (a person or a device) to a party who is to be authenticated. For instance, if the reader sends a challenge to the tag, then the tag computes a response by using a pre-shared secret key in combination with the challenge as a feedback reply to the reader. Subsequently the reader verifies whether the received response is a correct to determine the tag’s legitimacy. If true, the reader provides the service that the tag requested or denies its request if false. This thesis discusses an authentication protocol proposed by Hopper and Blum, named HB protocol. The security of HB protocol is based on the conjectured hardness of the “Learning Parity with Noise” (LPN) problem. HB protocol can combine with anti-collision protocol that is different to other authentication protocol. We will also show other HB protocol variants and then compare the security and efficiency of these protocols.
In the past, the anti-collision protocol and authentication protocol are usually treated separately. Normally, an authentication protocol will begin when an anti-collision protocol ends. In fact, it costs the RFID system too much resources and time to accomplish both purposes when there are many tags present on the scene. Therefore we propose a new protocol called CRPA (Collision Resolution Protocol with Authentication) to make both of them working together. While the anti-collision protocol is progressing, the authentication challenges are piggybacked with the anti-collision commands sent by the reader and the tag will reply the answers after finishing anti-collision. This combined approach can kill two birds with one stone by achieving both anti-collision and authentication at the same time. The security of the proposed protocol is still based on the conjectured hardness of the LPN problem. Let the anti-collision commands piggybacking the authentication challenges can share the transmission resources by streamlining their overall operations. Compared to the traditional separate anti-collision and authentication schemes, this combined approach can complete most of the authentication procedure by the time anti-collision process is finished. It saves a lot of time and message overheads to authenticate the tags due to the parallel processing of the authentication and anti-collision protocols. Furthermore, CRPA doesn’t make use of any complicated mathematical operations (e.g. cryptographic primitives). All the required functions of CRPA are supported by the standard equipments of EPCglobal Class 1 Generation 2. The proposed CRPA protocol is especially applicable to multiple tags scenario that requires anti-collision and authentication. The proposed CRPA protocol will perform the best, if all the challenges sent out are within the timeslot allocations that are required to resolve the anti-collisions. For example, if the tag population on the scene is more than 100, then the proposed CRPA protocol will perform the best for the anti-collision protocol “Q-Algorithm” in EPCglobal Class 1 Generation 2. We will also verify the feasibility and practicability of the proposed CRPA protocol in this thesis, and ensure its security, privacy and un-traceability under passive attacks. In addition, we also propose an extended CRPA, called ECRPA. The ECRPA flips answers using a deterministic probability. The error rate of the answers which received by the reader is identical to the flipping probability. Therefore, the reader can authenticate the same number of tags by fewer answers. Although the reduced answers may lower the overall security, it is more applicable to the low cost RFID tags applications.

[1] R. Weinstein, “RFID: A technical overview and its application to the enterprise,” IT Professional, Vol. 7, No. 3, pp.27-33, 2005.
[2] S. E. Sarma, S. A. Weis, and D.W. Engels, ”Radio-frequency identification systems,” in CHES '02, Springer-Verlag, 2002. LNCS no. 2523, pp. 454-469.
[3] 日經BP RFID技術編輯部/編, 周湘琪/譯, RFID技術與應用. 旗標, 2004.
[4] R. Damith and C. Peter, “Security in Low Cost RFID”, Technical Report Adelaide-AUTOID-WP-HARDWARE-027, Adelaide Auto-ID Center, 2006
[5] K. Finkenzeller, RFID Handbook: Fundamentals and Application in Contactless Smart cards and Identification 2nd edition. John Wiley & Sons, 2003.
[6] D. Shih, P. Sun, D. Yen and S. Huang, “Taxonomy and Survey of RFID Anti-collision protocols”, Computer and communications, vol.29, pp. 2150–2166, 2006.
[7] Z. Tang, Y. He, “Research of Multi-access and Anti-collision Protocols in RFID Systems”, IEEE International Workshop on Anti-counterfeiting, Security, Identification, 2007.
[8] MIT Auto-ID Center, “Draft protocol specification for a 900 MHz Class 0 Radio Frequency Identification Tag,” http://auto-id.mit.edu, February 2003.
[9] B. Feng, J. Li, J. Guo and Z.-H. Ding, “ID-Binary Tree Stack Anticollision Algorithm for RFID,” In Proceedings of the 11th IEEE Symposium on Computers and Communications (ISCC’06), 2006.
[10] C. Law, K. Lee and K. Siu, “Efficient Memoryless Protocol for Tag Identification,” In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, ACM, pages 75-84, 2000.
[11] J. Choi, D. Lee and H. Lee, “Query Tree-Based Reservation for Efficient RFID Tag Anti-Collision,” IEEE Commun. Lett., vol. 11, no. 1, pp.85-87, 2007.
[12] EPCTM, “Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz-960MHz,” Version 1.1.0, 2007.
[13] J. Myung and W. Lee, “Adaptive Splitting Protocols for RFID Tag Collision Arbitration," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 6, June 2007.
[14] D. Lee, K. Kim and W. Lee, Q+-Algorithm: An Enhanced RFID Tag Collision Arbitration Algorithm," Springer-Verlag: Lecture Notes in Computer Science, 2007.
[15] J. Myung and W. Lee, “Adaptive Binary Splitting for Efficient RFID Tag Anti-collision,” IEEE Commun. Lett., vol.10, no.3, pp.144–146, 2006.
[16] J. Park, M. Chung and T.-J. Lee, “Identification of RFID Tags in Framed-Slotted ALOHA with Tag Estimation and Binary Splitting,” ICCE'06, 2006.
[17] W. Chen and S. Horng, P Fan, “An Enhanced Anti-collision Algorithm in RFID Based on Counter and Stack,” Systems and Networks Communications on ICSNC, 2007.
[18] K. Ali, H. Hassanein and A. Taha, “RFID Anti-collision Protocol for Dense Passive Tag Environments,” 32nd IEEE Conference on Local Computer Networks, 2007.
[19] S. Tsai, J. Lan, M. Liang, “A Research on Adjustable Electromagnetic Wave on Passive RFID Tag”, “RFID Technology Conference at National Taipei University of Technology, 2008.
[20] S. Shiu, R. Jeng, B. Ye, “RFID Tag Collision Resolving Algorithm for Tag Identification, “RFID Technology Conference at National Taipei University of Technology, 2008.
[21] D.C. Ranasinghe and P.H. Cole, “Security in Low Cost RFID”, Auto-ID Labs White Paper WP-HARDWARE-027, 2006.
[22] S. Piramuthu, "Protocols for RFID tag/reader authentication", Decision Support Systems Vol. 43, No. 3, pp. 897-914, April 2007.
[23] N.J. Hopper and M. Blum, “Secure Human Identification Protocols”, In Advances in Cryptology - ASIACRYPT (2001), vol. 2248 of Lecture Notes in Computer Science, pp. 52–66.
[24] A. Juels and S. Weis, “Authenticating Pervasive Devices with Human Protocols," In V. Shoup, eitor, Advanced in Cryptology - CRYPTO'05, Volume 3126, Lecture Notes in Computer Science, pp. 293-308, Springer-Verlag, 2005.
[25] H. Gilbert, M. Robshaw, and H. Sibert, “An Active Attack Against HB+ - A Provably Secure Lightweight Protocol”, Cryptology ePrint Archive, Report 2005/237, 2005. http://eprint.iacr.org.
[26] S. Piramuthu, “HB and Related Lightweight Authentication Protocols for Secure RFID Tag/Reader Authentication”, CollECTeR Europe Conference, Basel, 2006.
[27] J. Bringer, H. Chabanne, and E. Dottax, “HB++: a Lightweight Authentication Protocol Secure Against Some Attacks”, IEEE International Conference on Pervasive Services, Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing － SecPerU, 2006.
[28] D.N. Duc, and K. Kim. “Securing HB+ against GRS Man-in-the-Middle Attack”, Proceedings of the Symposium on Cryptography and Information Security (SCIS2007), 2007.
[29] S. Piramuthu and Y.-J. Tu, “Modified HB authentication protocol”, Western European Workshop on Research in Cryptology (WEWoRC), 2007.
[30] H. Gilbert, M.J.B. Robshaw, and Y. Seurin, “Good Variants of HB+ are Hard to Find”, In Proceedings of Financial Crypto 2008, to appear.
[31] S. A. Weis, “New Foundations for Efficient Authentication, Commutative Cryptography, and Private Disjointness Testing”, PhD thesis, Massachusetts Institute of Technology, May 2006.
[32] A. Blum, Kalai A., and Wasserman, H, “Noise-tolerant learning, the parity problem, and the statistical query model”, Journal of the ACM 50, 4, pp. 506–519, 2003.
[33] A. Juels and S. Weis, “Authenticating Pervasive Devices with Human Protocols," In V. Shoup, eitor, Advanced in Cryptology - CRYPTO'05, Volume 3126, Lecture Notes in Computer Science, pp. 293-308, Springer-Verlag, 2005.
[34] E. Levieil, Fouque P.-A, “An Improved LPN Algorithm,” In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, 2006.
[35] J. Wang, Y. Zhao and D. Wang , “A Novel Fast Anti-Collision Algorithm for RFID Systems,” Wireless Communications, Networking and Mobile Computing (WiCom), 2007.