最近幾年，RFID被廣泛的應用在製造業、身份識別、貨物盤點等各方面。由於RFID有著遠距離批次處理的特性，可以有效率地提升貨品的管理效能，進而節省作業時間與成本。但是在貨物管理方面，若是透過一般的認證機制去搜尋某一內嵌電子標籤的特定貨物，大多只能將N個電子標籤逐一認證過一遍之後，方可找到該特定的貨物。但是這樣是相當不合理並且使得時間複雜度會達到O(N)。2008年Ahamed等學者與Tan等學者提出了有別於使用過去的認證方法來執行搜尋。在Ahamed等人的方法中，將每一個電子標籤賦予一個種子值，讀取器便可先記錄這些種子值之後、不透過後端伺服器，僅藉由該種子值計算出搜尋訊息，來取得目標電子標籤的回應，以找到特定的貨物。另外，在Tan等人的設計中，有別於Ahamed等人的搜尋機制；當要搜尋某一個特定的電子標籤時，讀取器可利用該電子標籤的識別碼與已知秘密值產生查詢訊息，電子標籤即可藉由檢驗訊息得知自己是否為搜尋目標而作出回應。本篇文章裡，我們針對了他們協定中的問題點提出改良的方法，希望可以在相同的應用環境下，設計出更有效率，更安全的離線式搜尋機制。

RFID has been considered as a time- and money saving solution for a wide variety of applications, such as manufacturing and inventory. Plenty of RFID authentication protocol which provides adequate security and privacy can be used for RFID tag searching. However, when the number of tags within a system increase, the overall data collection cost will be increased. Therefore, more efficient RFID tag searching method is needed. In 2008, Ahamed et al. and Tan et al. proposed lightweight and serverless RFID tag searching protocols. These two protocols can search a particular tag efficiently without server’s intervention. However, there are several weaknesses in their protocol. In this paper we propose a secure and serverless RFID tag searching protocol. This protocol can search a particular tag efficiently without server’s intervention. Moreover, the proposed protocol is secure against major security threats.

第一章 緒論 1
1.1 研究背景與動機 1
1.1.1 無線射頻辨識系統(RFID)的介紹 1
1.2 研究目的 5
1.3 本文架構 6
第二章 無線射頻辨識系統搜尋機制之探討 7
2.1 研究背景 7
2.2 驗證協定中常用的安全機制介紹 7
2.2.1 雜湊函式與其應用 7
2.2.2 挑戰與回應驗證機制 10
2.3 RFID 系統的應用實例與安全性議題 11
2.4 RFID Search 等相關協定 18
2.4.1 Ahamed等人的RFID Search 設計 18
2.4.2 Tan等人的RFID Search 協定 20
第三章 安全的離線式RFID搜尋機制之設計 23
3.1 協定架構 23
3.1.1 符號列表 23
3.1.2 參與角色與初始化階段簡介 24
3.2 本協定執行之介紹 24
3.3 安全需求之分析 27
3.3.1 基本安全性： 27
3.3.2 不可追蹤： 27
3.3.3 竊聽無效 28
3.3.4 防止重送攻擊 28
3.3.5 偽造無效 29
3.3.6 防止非同步攻擊 29
3.4 本協定之總結 30
第四章 安全的有線式RFID搜尋機制之設計 31
4.1 協定架構 31
4.1.1 符號列表 31
4.1.2 參與角色簡介 32
4.2 本協定執行之介紹 33
4.3 安全需求之分析 37
4.3.1 基本安全性： 37
4.3.2 不可追蹤： 38
4.3.3 竊聽無效 38
4.3.4 防止重送攻擊 39
4.3.5 偽造無效 40
4.3.6 防止非同步攻擊 40
4.4 本協定之總結 41
第五章　研究貢獻與未來工作 42
5.1 離線式RFID搜尋機制之安全設計之研究貢獻 42
5.2 有線式RFID搜尋機制之安全設計之研究貢獻 42
5.3 未來工作 43
參考文獻 45
附件 47

[1] A.Juels,” Strengthening epc tags against cloning.” Proceedings of the 4th ACM workshop on Wireless security, 2005, pp67-76
[2] Ahamed, S.I. Rahman, F. Hoque, E. Kawsar, F. Nakajima, T., “S3PR: Secure Serverless Search Protocols for RFID ” in Information Security and Assurance(ISA), 2008, pp.187-192.
[3] Ahamed, S.I. Hoque, E. Rahman, F. Kawsar, F. Nakajima, T. “YA-SARP: Yet another Serverless Authentication RFID Protocol.” in Intelligent Environments, 2008, pp.1-8
[4] D.G. Han, T. Takagi, H. W. Kim, and K.I.Chung.” New security problem in RFID systems tag killing”. in Applied Cryptography and Information Security, 2006, pp375-384
[5] D.Molnar, D.Wanger. ” Privacy and Security in Library RFID: Issues, Practices, and Architectures” in 11th ACM Conference on Computer and Communications Security, 2004, pp.210-219
[6]Hong Lei, Tianjie Cao, ” RFID Protocol enabling Ownership Transfer to protect against Traceability and Dos attacks” in The First International Symposium on Data,
Privacy, and E-Commerce (ISDPE), 2007, pp.508 - 510
[7] Hossain, M.S. Ahamed, S.I., “Towards a Simple Secured Searching Protocol for Future RFID Applications” in Future Trends of Distributed Computing Systems, 2008, pp.151-157
[8] Iuon-Chang Lin, Shih-Chang Tsaur and Kai-Ping Chang, ”Lightweight and serverless RFID Authentication and Search Protocol” in Computer and Electrical Engineering, 2009.pp. 95-99
[9]K. Osaka, T. Takagi, K. Yamasaki and O. Takahashi, “An Efficient and Secure RFID Security Method with Ownership Transfer”, in Computational Intelligence and Security, 2006, pp.1090-1093
[10] Kulseng, L. Zhen Yu Yawen Wei Yong Guan ,”Lightweight Secure Search Protocol for Low-cost RFID Systems” in IEEE International Conference on Distributed Computing Systems, 2009, pp.40-48
[11] M.Ohkubo, K. Suzuki, S.Kinoshita, “Cryptographic approach to” privacy-friendly” tags”, in RFID Privacy Workshop, 2003. pp. 21-30
[12] Min-Hua Shao, ” An Effective Privacy-Preserving RFID Scheme against Desynchronization”, in Intelligent Information Hiding and Multimedia Signal Processing, 2007, pp.659-662.
[13] Sheikh Iqbal Ahamed, Farzana Rahman, Md. Endadul Hoque “ Secured Tag Indentification Using EDSA(Enhances Distributed Scalable Architecure)”in Symposium on Applied Computing Proceedings, 2008, pp1902-1907
[14] T. Dimitriou. ” A lightweight RFID protocol to protect against traceability and cloning attacks.” in Security and Privacy for Emerging Areas in Communications Networks,2005, pp.59-66
[15] Tae Youn Won, Ji Young Chun, Dong Hoon Lee, ”Strong Authentication Protocol for Secure RFID Tag Search Without Help of Central Database” in Embedded and Ubiquitous Computing, 2008.,pp. 153-158
[16] Tan, C.C. Bo Sheng Qun Li, “Secure and Serverless RFID Authentication and Search Protocols”, in IEEE Transactions on Wireless Communications, 2008, pp1400-1407.
[17] Tsudik, G. “YA-TRAP : Yet another trivial RFID authentication protocol” in Pervasive Computing and Communications Workshops, 2006, pp.13-17.
[18] A.Juels,” Privacy and Authentication in Low cost RFID Tags”, 2003
[19] J.Saito, J. C. Ryou and K. Sakurai, “Enhancing Privacy of Universal Re-encryption Schema for RFID Tags”, Embedded and Ubiquitous Computing-EUC 2004, LNCS3207, Aizu-wakatsuma City, Japan , Aug.2004
[20] D.N.Duc, J.Park, H.Lee and K.Kim, “Enhancing Security of EPCglobal Gen-2 RFID Tag against Traceability and Cloning” The 2006 Symposium on Cryptography and Information Security,2006.
[21] Stephen A.Weis, Sanjay E “Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems” First International Conference on Security in Pervasive Computing, 2006
[22] Sanjay E Sarma, Stephen A.Weis, and Daniel W.Engels ”RFID Systems and Security and Privacy Implications” in Workshop on Cryptographic Hardware AND Embedded Systems, Lecture Notes in Computer Science,2002