隨著無線射頻辨識（Radio Frequency Identification, RFID）在製造業、零售業、醫藥業等各種產業的大量應用下，RFID在資訊安全上的弱點或是個人隱私的侵害等議題，也逐漸成為全世界研究人員、人權組織、政府機構和業者關心的重點。由於RFID在開放式的空間中容易發生多種的資訊安全問題，如：訊息竊取、重送攻擊、阻斷服務、惡意追蹤等問題，因此有許多研究人員致力於此類問題的解決。然而，受限於無線射頻辨識現有標準所制定的記憶體、天線、電池容量、晶片大小等硬體限制及低成本的要求，過去研究仍未能完全杜絕上述四種安全威脅，而無法有效大幅提高RFID在使用上的安全性。
因此本研究希望能在符合現有標準如EPC global的前提下，提出一個RFID的雙向認證協定，就我們所知，本研究中的認證機制不僅所需的資料儲存空間比其他雙向認證安全機制還小了將近45%至50%，更可以達成資料安全、匿名性、向前安全等要求，消除各方面可能的安全缺失及加強個人隱私權保護。

In recent years, RFID technology is rapidly adopted by various industries such as manufacturing, retailer business and medical treatment. Since then security weakness and privacy invasion in RFID systems have become the concern to academic researchers, human right advocators, government apparatus and enterprises. As RFID system operates in wireless environment, it is easy to be threatened by various attacks such as eavesdropping, replay attack, denial of service, tracking and so on. Hence, many researchers devote to solve those security problems in recent years. However, restricted by the current RFID standards, a proposed security solution not only has to comply with hardware restrictions for antenna, battery capacity and chip size, but also needs to meet low-cost requirement; in consequence, pervious researches were not able to eliminate major security threats successfully and enhance the security of RFID usage under such challenging environment.
In this thesis, we propose a novel Secure Mutual Authentication Protocol for Low-cost RFID System (SMAP-LRS) whose design and operation can meet the requirements of current RFID standards, such as EPCglobal proposed ones. As best we know, the required memory space of our scheme decreases about 45% to 50% in comparison with other existing mutual authentication protocols. Our scheme also eliminates the major security threats and enhances privacy protection to achieve security requirement such as data security, anonymity and forward security.
Keywords: RFID, Privacy, Security, Mutual Authentication

中文摘要 IV
Abstract V
誌謝 VI
Contents VII
List of Figures VIII
List of Tables IX
Chapter 1.Backgrou 1
Chapter 2.Introduction of RFID System 5
2.1 Radio Frequency Identification System 5
2.2 EPCglobal Standards 7
2.3 ISO/IEC 10
2.4 Security Threats 11
Chapter 3.Related Work 14
Chapter 4.Proposed SMAP-LRS Protocol 17
4.1 System Assumption 17
4.2 Mutual Authentication Protocol 20
Chapter 5.Security and Performance Analysis 25
5.1 Security Analysis 25
5.2 Performance Analysis 27
Chapter 6.Conclusion 30
Reference 31

[1] S. Garfinkel and B. Rosenberg, RFID: Applications, Security, and Privacy: Addison-Wesley Professional, 2005.
[2] T. Karygiannis, B. Eydt, G. Barber, and L. Bunn, "Guidelines for Securing Radio Frequency Identification (RFID) Systems," in National Institute of Standards and Technology, April, 2007.
[3] A. Juels, D. Molnar, and D. Wagner, "Security and privacy issues in e-passports," in IEEE SecureComm. vol. 5, 2005.
[4] S. A. Weis, "Security and Privacy in Radio-Frequency Identification Devices," Massachusetts Institute of Technology, 2003.
[5] S. A. Weis, S. E. Sarma, R. L. Rivest, and D. W. Engels, "Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems," in Security in Pervasive Computing, pp. 201–212, 2003.
[6] M. Ohkubo, K. Suzuki, and S. Kinoshita, "Cryptographic approach to “privacy-friendly” tags," in RFID Privacy Workshop, MIT, MA, USA, pp. 624-654, 2003.
[7] D. Henrici and P. Muller, "Hash-based enhancement of location privacy for radio-frequency identification devices using varying identifiers," in Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops, Orlando, Florida, pp. 149-153, 2004.
[8] Y. An and S. Oh, "RFID System for User's Privacy Protection," In 2005 Asia-Pacific Conference on Communications, pp. 516-519, 2005.
[9] D. H. Technology, "MD5, SHA-1, SHA-256 hash core for Asic,” 2005.
[10] M. Feldhofer, S. Dominikus, and J. Wolkerstorfer, "Strong authentication for RFID systems using the AES algorithm," Workshop on Cryptographic Hardware and Embedded Systems–CHES, vol. 3156, pp. 357–370, 2004.
[11] S. Kumar and C. Paar, "Are standards compliant elliptic curve cryptosystems feasible on RFID," in Proceedings of Workshop on RFID Security, Austria, July 2006.
[12] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda, "EMAP: An Efficient Mutual Authentication Protocol for Low-cost RFID Tags," OTM Federated Conferences and Workshop: IS Workshop, 2006.
[13] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda, "M2AP: A Minimalist Mutual-Authentication Protocol for Low-cost RFID Tags," in Proc. of International Conference on Ubiquitous Intelligence and Computing UIC’06, LNCS 4159, pp. 912-923, 2006.
[14] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda, "LMAP: A Real Lightweight Mutual Authentication Protocol for Low-cost RFID tags," in Proc. of 2nd Workshop on RFID Security, 2006.
[15] H. Chien, "SASI: A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity," IEEE Transactions on Dependable and Secure Computing, vol. 4, pp. 337–340, 2007.
[16] S. Sarma and D. W. Engels, "On the Future of RFID Tags and Protocols," in White paper, Auto-ID Center, Massachusetts Institute of Technology, 2003.
[17] EPCglobal, http://www. EPCgloballinc.org/
[18] M. Brown, S. Patadia, and S. Dua, Mike Meyers' Comptia RFID+ Certification Passport (Mike Meyers' Certification Passport): Mc Graw Hill, 2007.
[19] K. Rhee, J. Kwak, S. Kim, and D. Won, "Challenge-response based RFID authentication protocol for distributed database environment," in International Conference on Security in Pervasive Computing–SPC. vol. 3450, pp. 70–84, 2005.
[20] H. W. Kim, S. Y. Lim, and H. J. Lee, "Symmetric Encryption in RFID Authentication Protocol for Strong Location Privacy and Forward-Security," in Proceedings of the 2006 International Conference on Hybrid Information Technology-Volume 02, pp. 718-723, 2006.
[21] T. Li and G. Wang, "Security Analysis of Two Ultra-Lightweight RFID Authentication Protocols," IFIP SEC, 2007.
[22] T. Li and R. H. Deng, "Vulnerability Analysis of EMAP-An Efficient RFID Mutual Authentication Protocol," in the Proceedings of the Second International Conference on Availability, Reliability and Security-AReS, pp. 10-13, 2007.
[23] T. Li, "Security Analysis on a Family of Ultra-lightweight RFID Authentication Protocols," JOURNAL OF SOFTWARE, vol. 3, p. 1, 2008.
[24] H. Y. Chien and C. W. Huang, "Security of ultra-lightweight RFID authentication protocols and its improvements," in ACM SIGOPS Operating Systems Review vol. 41 New York, NY, USA , ACM 2007.
[25] N. W. Lo and K. H. Yeh, "An Efficient Mutual Authentication Scheme for EPCglobal Class-1 Generation-2 RFID System," in the 2nd International Workshop on Trustworthiness, Reliability and services in Ubiquitous and Sensor networks, TRUST. vol. 7: LNCS, 2007.
[26] H. Huang, "An Efficient Mutual Authentication Protocol on RFID Tags," in LNCS. vol. 4809, pp. 550-556, 2007.
[27] D. N. Duc, J. Park, H. Lee, and K. Kim, "Enhancing Security of EPCglobal Gen-2 RFID Tag against Traceability and Cloning," in The 2006 Symposium on Cryptography and Information Security, 2006.
[28] A. Juels, "Strengthening EPC tags against cloning," in Proceedings of the 4th ACM workshop on Wireless security: ACM, pp. 67-76, 2005.
[29] S. Karthikeyan and M. Nesterenko, "RFID security without extensive cryptography," in Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks: ACM, pp. 63-67, 2005.
[30] Wal-Mart http://www.walmart.com/
[31] METRO Group http://www.metrogroup.de/servlet/PB/menu/-1_l1/index.html
[32] J. Yang, K. Ren, and K. Kim, "Security and Privacy on Authentication Protocol for Low-cost RFID," in Symposium on Cryptography and Information Security, January Japan: Maiko Kobe, pp. 25-28, 2005.
[33] H. S. Kim and J. Y. Choi, "Security and Privacy Analysis of RFID Authentication Protocol for Ubiquitous Computing," in Proceedings of 16th International Conference on Computer Communications and Networks, ICCCN, pp. 1359-1363, 2007.
[34] A. Poschmann, G. Leander, K. Schramm, and C. Paar, "New Light-Weight Crypto Algorithms for RFID," in Proceedings of The IEEE International Symposium on Circuits and Systems, ISCAS: IEEE, 2007.
[35] A. Poschmann, G. Leander, K. Schramm, and C. Paar, "A Family of Light-Weight Block Ciphers Based on DES Suited for RFID Applications," in Workshop on RFID Security–RFIDSec. vol. 6, 2006.
[36] S. Yu, K. Ren, and W. Lou, "A Privacy-preserving Lightweight Authentication Protocol for Low-Cost RFID Tags," in Military Communications Conference, MILCOM, IEEE, pp. 1-7, 2007.
[37] A. Juels, "Strengthening EPC tags against cloning," in Proceedings of the 4th ACM workshop on Wireless security: ACM, pp. 67-76, 2005.
[38] D. H. Shih, P. L. Sun, D. C. Yen, and S. M. Huang, "Taxonomy and survey of RFID anti-collision protocols," Elsevier Computer Communications, vol. 29, pp. 2150-2166, 2006.
[39] J. Lee, T. Kwon, Y. Choi, S. K. Das, and K. Kim, "Analysis of RFID anti-collision algorithms using smart antennas," in Proceedings of the 2nd international conference on Embedded networked sensor systems, Baltimore, pp. 265-266, 2004.