無線射頻識別(Radio Frequency Identification, RFID)是一種非接觸式的自動識別技術，主要是利用無線電波來進行資料的擷取及辨識。早在二次世界大戰時，RFID已被英軍發明用來區分進入英國領空飛機之「敵我識別」。近年來，隨著無線射頻識別技術的成熟，使得RFID相關的應用系統蓬勃發展，隨著應用越來越普及(例如倉儲管理、門禁管制、動物監控)，使得在大量使用電子標籤的同時，就必須能有效的降低RFID認證系統成本及提升效率(成本效益(Cost-Effective))。影響成本主要有四大因素：運作模式複雜度、讀取器成本、電子標籤成本、認證機制模式的成本。而影響認證系統效率則有三大因素：電子標籤運算量及運算複雜度、後端伺服器(讀取器)負擔、認證機制複雜度。

RFID認證機制主要是用來確認RFID電子標籤的有效性與保護電子標籤的隱私。現今大多數的RFID認證機制模式，RFID讀取器幾乎都必須與後端伺服器保持連線的狀態，我們稱之為連線式(On-Line)RFID認證機制模式。在On-Line RFID認證機制中，國內外學者所提出之機制仍有安全上的弱點，直到2007年，Conti et al.提出基於雜湊鏈(Hash Chain)的RFID認證機制RIPP-FS，RIPP-FS改善了安全性不足的缺點。但我們發現，RIPP-FS雖可抵抗目前已知的攻擊手法，卻導致電子標籤運算量過高及成本效益不佳。而在現實生活的應用當中，RFID認證機制不只是需要可靠的安全性，還必須具有高的成本效益。因此，本研究基於改善RIPP-FS在效能上的缺點，提出新的On-Line RFID認證機制EARAP，EARAP不但可抵抗目前已知的攻擊手法，同時亦兼顧電子標籤效能上的表現，具有極佳的成本效益。

在許多真實的環境中，並不是每種應用在讀取器與後端伺服器之間都需要或都能夠提供安全可靠且持續的連線，此時就必須單獨依賴讀取器來認證RFID電子標籤；當讀取器不需要後端伺服器就能獨自對電子標籤進行認證，此類的認證機制我們稱之為離線式(Off-Line)RFID認證機制模式。在2007年，Tan et al.提出不適用連線式RFID認證機制的案例，並且率先提出使用Verifier的離線式RFID認證機制。但是我們發現Tan et al.認證機制仍存在一些缺點，包括：讀取器與離線伺服器之間的通訊必須為安全性通道、讀取器內所存的認證存取清單為永久有效、讀取器運算量大、硬體成本高等。而在Off-Line的應用環境下，是由多個讀取器認證數個電子標籤，讀取器的成本效益將成為商業考量的重要關鍵。因此，本研究提出新的Off-Line RFID認證機制OLRAP，OLRAP不但可抵抗目前已知的攻擊手法，同時亦兼顧讀取器效能上的表現，具有極佳的成本效益。

由於RFID的應用非常廣泛，在某些低價值商品應用中(例如食品應用、醫療應用)，為了商業成本考量，必須選擇使用較低成本的電子標籤，相對的電子標籤內部晶片的運算能力就較為薄弱，而RFID認證機制可依照電子標籤內部晶片的運算能力區分為Full-Fledged、Simple、Lightweight、Ultralightweight四種類型。其中，Full-Fledged類型運算能力最佳，但成本、運算複雜度及消耗功率相對也最高，其次為Simple、Lightweight。運算能力最差、成本最低、運算複雜度及消耗功率最低則為Ultralightweight類型。早期有許多學者研究於Ultralightweight類型RFID認證機制，但都無法有效的達到安全性的需求。2007年，Chien提出Ultralightweight類型RFID認證機制SASI，但我們發現SASI雖然改進了Ultralightweight類型RFID認證機制安全性不足的缺點，卻仍然無法抵抗重送攻擊及向前安全攻擊。因此，本研究基於改善SASI安全性上的弱點，提出新的Ultralightweight類型RFID認證機制ASURAP，ASURAP改善SASI安全性上的弱點，同時亦可抵抗目前已知的攻擊手法。

Radio Frequency Identification (RFID) is an automatic and contact-less identification technology that uses radio wave to retrieve and identify data. In World War II, RFID had been invented by the England armed forces for IFF (Identification Friend or Foe) to distinguish airplanes that enter English territorial airspace. In recent years, with the maturity of the Radio Frequency Identification technology, RFID related applications are in vigorous development. With the population of more and more RFID applications, e.g. warehouse management, access control, animal monitoring, the tags are used in large numbers. It needs to efficiently reduce the cost and enhance the efficiency of the RFID authentication system. There are four factors that influence the cost: the complexity of operation mode, reader cost, tag cost, and the cost of authentication scheme. There are three factors that influence the efficiency of authentication system: the computational complexity on the tags, the overhead of the back-end server (reader), and the complexity of the authentication scheme.

The RFID authentication scheme is used to verify the validity of RFID tags and protect their privacy. In nowadays, most RFID authentication schemes need the readers to keep connection with the back-end server. The RFID authentication schemes for such an environment are called on-line RFID authentication schemes. In previous on-line RFID authentication schemes, there still exist some security weaknesses in them. Until 2007, Conti et al. proposed a RFID authentication scheme, called RIPP-FS, which uses the hash chain to improve the security. However, we find that the RIPP-FS scheme is not cost-effective and has high computational cost on the tags, even though it can resist all well-known attacks. In practical environment, the RFID authentication scheme not only needs the reliable security, but also has to be high cost-effective. In this thesis, we propose a new on-line RFID authentication scheme, called EARAP. The proposed EARAP scheme is high cost-effective, since it improves the efficiency of RIPP-FS especially it has low computational cost on the tags and resists all well-known attacks.

In some practical environments, however, it is difficult to provide a secure and reliable connection between the back-end server and the RFID reader. Thus, it requires that the reader can authenticate the tag. The authentication schemes without on-line servers are called off-line RFID authentication schemes. In 2007, Tan et al. introduced an application that the on-line authentication is not suit for, and they first proposed an off-line RFID authentication scheme using verifiers. However, we find that Tan et al.’s scheme still has some shortcomings, including: the communication between the read and the off-line server must be a secure channel, the lifetime of access list stored in the reader is forever, and the reader has high computational and hardware cost. In off-line environment, most applications use several readers to authenticate multiple tags. Thus the cost benefit of the read will become the main commercial considerations. In this thesis, we propose a new off-line RFID authentication scheme, called OLRAP. The proposed OLRAP scheme is high cost-effective, since it has good performance on the readers and resists all well-known attacks.

The application of RFID is very widespread, including low-value goods, e.g. food and medical applications. For the commercial cost consideration, it must choose the low-cost tags. Hence, the computational power of the low-cost tags is weak. According to the tag computational power, the RFID authentication schemes can be divided into four types: full-fledged, simple, lightweight, and ultralightweight. The full-fledged type has the best computational power, but has high cost, computational complexity, and power consumption. Next is the simple and lightweight type. The ultralightweight type has the lowest computational power, cost, and power consumption. The previously proposed ultralightweight RFID authentication schemes did not satisfy basic security requirements. In 2007, Chien proposed a new ultralightweight RFID authentication scheme SASI. Although Chien’s scheme provides better security, however, we find that Chien’s scheme still suffers from replay attack and cannot provide forward security. In this thesis, we propose a new ultralightweight authentication scheme ASURAP. The proposed ASURAP scheme improves the security problems of SASI and can resist all well-known attacks.

中文摘要
英文摘要
誌　　謝
目　　錄
表　目　錄
圖　目　錄
一、緒論
1.1 研究背景
1.2 研究動機
1.3 研究目的及成果
1.4 論文架構
二、RFID認證機制
2.1 簡介
2.2 特性與需求
2.3 相關函數
2.3.1虛擬亂數產生器函式(PRNG)
2.3.2單向Hash函數
2.3.3 AES函數
三、On-line Simple RFID 認證機制
3.1 簡介 21
3.2 相關研究
3.3 簡述RIPP-FS認證機制
3.4 本論文針對RIPP-FS認證機制所提出的缺點
3.4.1標籤運算量不固定
3.4.2後端伺服器無法由電子標籤的錯誤回應中得知電子標籤身份
3.4.3雜湊鏈有限的使用次數
3.4.4 Hash函數電路比AES函數電路成本高
3.5 簡述TL-RFID認證機制
3.5.1初始化階段
3.5.2認證階段
3.6 本論文針對TL-RFID認證機制所提出的安全性攻擊
3.6.1阻斷服務攻擊(Denial-of-Service attack)
3.6.2向前安全攻擊(Forward Security attack)
3.7 本論文所提出之On-line simple RFID認證機制EARAP
3.7.1初始化階段
3.7.2相互認證階段
3.8 安全分析與效能分析
3.8.1安全性比較
3.8.2效能比較
四、Off-line Simple RFID認證機制
4.1 簡介
4.2 相關研究
4.3 簡述Tan et al.認證機制
4.4 本論文針對Tan et al.認證機制所提出的缺點
4.4.1讀取器與離線伺服器的通訊必須為安全性通道
4.4.2讀取器內部所存的認證存取清單為永久有效
4.4.3讀取器運算量大
4.4.4讀取器成本高
4.5 本論文所提出Off-Line Simple RFID認證機制OLRAP
4.5.1 OLRAP 架構
4.5.2 OLRAP 認證機制
4.6 安全分析與優缺點比較
五、Ultralightweight RFID認證機制
5.1 簡介
5.2 相關研究
5.3 SASI認證機制
5.3.1標籤認證階段
5.3.2相互認證階段
5.3.3金鑰更新階段
5.4 本文針對SASI認證機制所提出的缺點
5.4.1重送攻擊
5.4.2向前安全攻擊
5.4.3認證效率差
5.5 本論文提出之New Ultralightweight RFID認證機制ASURAP
5.6 安全分析與效率分析
六、結論與研究貢獻
6.1 結論
6.2 研究貢獻
參考文獻
簡歷

[1]奚正德和張克章, “RFID相關應用與安全機制簡介,” 資通安全專論 T95013.
[2]簡宏宇和陳哲豪, “適用於EPC Class 1 Generation 2 RFID 標籤之安全認證機制,” 第十六屆全國資訊安全會議, 2006年6月8-9日, pp. 206-213.
[3]RFID發展動態電子半月刊,“全球面對RFID隱私權的發展現況”, http://rfid.more.org.tw/epaper5/ver05_c.html, 2006年4月16日
[4]H. Y. Chien and C. H. Chen (2007), “Mutual Authentication Protocol for RFID Conforming to EPC Class 1 Generation 2 Standards,” Computer Standards & Interfaces, Vol. 29, pp.254-259.
[5]H. Y. Chien (2007), “SASI: A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity,” IEEE Transcations On Dependable And Secure Computing, Vol. 4, No. 4.
[6]D. N. Duc, J. Park, H. Lee and K. Kim (2006), “Enhancing Security of EPCglobal Gen-2 RFID Tag against Traceability and Cloning,” The 2006 Symposium on Cryptography and Information Security.
[7]資安人科技網, “美數位身份證引爭議”, http://www.informationsecurity.com.tw/news/view.asp?nid=3020
[8]Enjoy RFID technology, “數位ID在美國引起爭議”, http://enjoyrfid.blogspot.com/2007/03/id.html
[9]EPCglobal Inc., http://www.epcglobalinc.org/
[10]Wikipedia, “Pseudorandom number generator”, http://en.wikipedia.org/wiki/Pseudorandom_number_generator
[11]C. S. Laih, L. Harn, C. C. Chang, “Contemporary Cryptography and It’s Applications,” 旗標出版.
[12]A. Juels, D. Molner, and D. Wagner (2005), “Security and Privacy Issues in E-passport,” Proceedings First Int’l Conference. Security and Privacy for Emerging Areas in Comm. Networks.
[13]S. Kinoshita, M. Ohkubo, F. Hoshino, G. Morohashi, O. Shionoiri, and A. Kanai (2005), “Privacy Enhanced Active RFID Tag,” Proceedings Int’l Workshop Exploiting Context Histories in Smart Environments.

[14]S. S. Kumar and C. paar (2006), “Are Standards Compliant Elliptic Curve Cryptosystems Feasible on RFID,” Proceedings Workshop RFID Security.
[15]G. Tsudik (2006), “YA-TRAP: Yet another trivial RFID authentication protocol,” Proceedings of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, page 640.
[16]M. Burmester, T. v. Le, and B. d. Medeiros (2006), “Provably secure ubiquitous systems: Universally composable RFID authentication protocols,” In Conference on Security and Privacy for Emerging Areas in Communication Networks – SecureComm, IEEE.
[17]C. Chatmon, T. v. Le, and M. Burmester (2006), “Secure anonymous RFID authentication protocols,” Technical Report TR- 060112, Florida State University, Department of Computer Science.
[18]G. Avoine and P. Oechslin (2005), “A scalable and provably secure hash based RFID protocol,” In International Workshop on Pervasive Computing and Communication Security, pages 110–114, IEEE, IEEE Computer Society Press.
[19]M. Conti and R. D. Pietro and L. V. Mancini (2007), “RIPP-FS: an RFID Identification, Privacy Preserving protocol with Forward Secrecy,” Proceedings of the Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops.
[20]M. Feldhofer, J. Wolkerstorfer, and V. Rijmen (2005), “AES implementation on a grain of sand,” IEE Proceedings Information Security, Vol. 152, No 1, pp.13-20.
[21]M. Feldhofer, S. Dominikus, and J. Wolkerstorfer (2004), “Strong authentication for RFID systems using the AES algorithm,” In Conference of Cryptographic Hardware and Embedded Systems, pp. 357–370.
[22]A. Juels and S. Weis (2005), “Authenticating pervasive devices with human protocols,” In V. Shoup, editor, Advances in Cryptology – CRYPTO’05, volume 3126 of LNCS, pages 293–308.
[23]J. Bringer, H. Chabanne, and D. Emmanuelle (2006), “HB++: a lightweight authentication protocol secure against some attacks,” In IEEE International Conference on Pervasive Services, Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing, IEEE, IEEE Computer Society Press.
[24]B. Toiruul and K. Lee (2006), “An Advanced Mutual-Authentication Algorithm Using AES for RFID Systems,” IJCSNS International Journal of Computer Science and Network Security, VOL.6, NO.9B.
[25]C. C. Tan, B. Sheng and Q. Li (2007), “Serverless Search and Authentication Protocols for RFID,” Fifth Annual IEEE International Conference on Pervasive Computing and Communications, pp. 3-12.
[26]C. C. Tan, B. Sheng and Q. Li (2007), “Secure and Serverless RFID Authentication and Search Protocols,” MANUSCRIPT ID PAPER-TW-DEC-06-1012.R1.
[27]P. Peris-Lopez, J.C. Hernandez-Castro, J.M. Estevez-Tapiador, and A. Ribagorda (2006), “LMAP: A Real Lightweight Mutual Authentication Protocol for Low-Cost RFID Tags,” Proc. Second Workshop RFID Security.
[28]P. Peris-Lopez, J.C. Hernandez-Castro, J.M. Estevez-Tapiador, and A. Ribagorda (2006), “EMAP: An Efficient Mutual Authentication Protocol for Low-Cost RFID Tags,” Proc. OTM Federated Conference. and Workshop: IS Workshop.
[29]P. Peris-Lopez, J.C. Hernandez-Castro, J.M. Estevez-Tapiador, and A. Ribagorda (2006), “M2AP: A Minimalist Mutual-Authentication Protocol for Low-Cost RFID Tags,” Proc. Int’l Conference. Ubiquitous Intelligence and Computing (UIC’06), pp. 912-923.
[30]T. Li and G. Wang (2007), “Security Analysis of Two Ultra-Lightweight RFID Authentication Protocols,” Proc. 22nd IFIP TC-11 Int’l Information Security Conference.
[31]T. Li and R.H. Deng (2007), “Vulnerability Analysis of EMAP-An Efficient RFID Mutual Authentication Protocol,” Proc. Second Int’l Conference. Availability, Reliability, and Security (AReS ’07).
[32]H.-Y. Chien and C.-W. Huang (2007), “Security of Ultra-Lightweight RFID Authentication Protocols and Its Improvements,” ACM Operating System Rev., vol. 41, no. 2, pp. 83-86.