無線射頻識別 (Radio Frequency Identification, RFID) 為一種非接觸式、短距離的自動化識別技術，可藉由無線射頻來辨識嵌於物品上之標籤內容資料，此技術已廣泛地運用於存貨管理與追蹤、身分鑑別、自動付費、供應鏈管理等多項領域。近年來由於社會對於個人隱私議題的重視，因此在眾多有使用身分鑑別技術的應用中，凡嵌有標籤之物件，都需要能夠支援其前/後向安全性之協定，以抵擋攻擊者任意追蹤及攻擊，基於以上緣由，考量採用低成本且具安全性之RFID極輕量級身分鑑別協定是一項值得探討的研究議題。
為抵擋惡意攻擊活動所造成的隱私問題，RFID極輕量級身分鑑別協定大多在標籤端與讀取器/伺服器端採用動態更新秘鑰機制，以確保其通訊前/後向安全性。然而，在現實環境中，攻擊者依舊可以輕易地干擾或阻斷每個身分鑑別期間所傳遞的訊息，使得在標籤端與讀取器/伺服器端所存有的秘鑰不一致，導致兩端呈現秘鑰非同步狀態，此類的攻擊即稱為「不同步攻擊(De-synchronization Attack)」。為了進一步抵抗不同步攻擊，最近發展之協定開始採用秘鑰冗餘的設計概念，以允許當標籤與資料庫兩端呈現不同步狀態時，兩端仍舊可透過秘鑰冗餘設計於下一個身分鑑別期間正常且成功地相互溝通。
在此篇論文當中，我們分析並證明許多現存同時使用秘鑰冗餘機制於標籤端與伺服器端的RFID極輕量級身分鑑別協定，對於避免遭受不同步攻擊並無顯著地幫助，且無法有效地抵擋攻擊者所發動的非同步攻擊。同時我們也提出一強健的補救機制，能有效確保RFID極輕量級身分鑑別協定之安全性，以抵擋不同步攻擊，並做為日後RFID極輕量級身分鑑別協定設計之基礎。

Radio Frequency Identification (RFID) is a contactless and short distance automatic identification technology which can identify the information of RFID tags attached on objects by radio frequency signal and send information to the system side to authenticate and track. In nowadays, RFID technology is being used for many applications in our life. For example, asset management, tracking, authenticity verification and soon.
In real environment, there are many attackers on the RFID system. With the personal privacy, the demand for RFID authentication protocol which can protect the forward and backward security is more rising in recent years. To resist the attack, the RFID ultra-lightweight authentication protocol has become more important.
To deliver robust privacy-aware RFID ultra-lightweight authentication protocol against malicious tracing activities, automatically secret updating mechanism is exploited at both tag end and server end during each authentication session to support forward/backward security. Nevertheless, an adversary may easily interrupt transmission of necessary key update message in each authentication session such that key re-synchronization between tag and server cannot be completed, which is named as de-synchronization attack. For this reason, current RFID ultra-lightweight authentication protocols have applied key redundancy design to allow a tag with de-synchronized secret to successfully communicate with server in its next authentication session. In this paper, we identify most of existing RFID ultra-lightweight authentication protocols with key redundancy mechanism both at tag side and server side cannot defend against de-synchronization attack. All of those protocols are totally insecure because the key redundancy mechanisms are not well-designed.We also propose a remedy mechanism which is robust enough to resist de-synchronization attack for KRP model protocols.

中文摘要
Abstract
誌謝
Contents
List of Figures
Chapter 1 Introduction
Chapter 2 Related Work
Chapter 3 Security Analysis on De-synchronization Attack
3.1 Notations and Model Definitions
3.1.1Notations Definitions
3.1.2Attack Oracle Query
3.1.3Definition: Service Availability
3.2 Key Redundancy-based Protocol Model (KRP Model)
3.3 Generic De-Synchronization Attack Process
3.4 Analysis on De-synchronization Attack for Protocols in KRP Model
3.5 Security Analysis on Existing Protocols Categorized in KRP Model
3.5.1Analysis on SULMA Protocol [2]
3.5.2Analysis on KGY Protocol [3]
3.5.3Analysis on LHYC Protocol [4]
Chapter 4 Remedy Mechanism for KRP Protocols
Chapter 5 Conclusion
References

[1]H.Y. Chien, “SASI: A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity,” IEEE Transactions on Dependable and Secure Computing,Vol.4, No.4, pp. 337–340, 2007.
[2]M. Kianersi, M. Gardeshi and M. Arjmand, “SULMA: A Secure Ultra Light-Weight Mutual Authentication Protocol For Low-Cost RFID Tags,” International Journal of UbiComp (IJU), Vol.2, No.2, April 2011.
[3]M. Kianersi, M. Gardeshi, and H. Yousefi, “Security Analysis of Ultra-lightweight Protocol for Low-Cost RFID Tags: SSL-MAP,” WiMo/CoNeCo, CCIS 162, pp. 236–245, 2011.
[4]Y.C Lee, Y.C Hsieh, P.S You, and T.C. Chen, “A New Ultralightweight RFID Protocol with Mutual Authentication,” WASE International Conference on Information Engineering, 2009.
[5]Z.Bilal, A .Masood and F. Kausar, “Security Analysis of Ultra-lightweight Cryptographic Protocol for Low-cost RFID Tags: Gossamer Protocol,” International Conference on Network-Based Information Systems, 2009.
[6]D. Tagra, M. Rahman and S. Sampalli, “Technique for preventing DoS attacks on RFID systems,” International Conference onSoftware, Telecommunications and Computer Networks (SoftCOM), 2010.
[7]M. David and N. R. Prasad, “Providing Strong Security and High Privacy in Low-Cost RFID network,” MobiSec, LNICST 17, pp. 172-179, 2009.
[8]J. C. Hernandez-castro, P. Peris-lopez, R. C. W.Phan and J. M. E. Tapiador, “Cryptanalysis of the David-Prasad RFID Ultralightweight Authentication Protocol,” RFIDSec'10 Proceedings of the 6th international conference on Radio frequency identification, 2010.
[9]H. M Sun, W. C. Ting, and K. H. Wang, “On the Security of Chien’s Ultralightweight RFID Authentication Protocol,” IEEE Transactions On Dependable And Secure Computing, Vol. 8, No. 2, 2011.
[10]K. H. Yeh, N.W. Lo, Y. Li, Y.C. Chen and T.C. Wu, “New Findings on RFID Authentication Schemes against De-synchronization Attack,” accepted by International Journal of Innovative Computing, Information and Control, Sep 2011.
[11]Pedro, P. Lopez, Julio, C. Hernandez, Juan, M. Estevez Tapiador and Arturo Ribagorda, “M2AP: A minimalist mutual authentication protocol for low-cost RFID tags,” Proc. of UIC’06, Vol. 4159 of LNCS, pp 912–923, 2006.
[12]Pedro, P. Lopez, Julio, C. Hernandez, Juan, M. Estevez Tapiador and Arturo Ribagorda, “LMAP: A real lightweight mutual authentication protocol for low-cost RFID tags,” Hand. Of Workshop on RFID and Lightweight Cryptography,2006.
[13]Pedro, P. Lopez, Julio, C. Hernandez, Juan, M. Estevez Tapiador and Arturo Ribagorda, “EMAP: An efficient mutual authentication protocol for low-cost RFID tags,” Proc. of IS’06, Springer-Verlag, Vol. 4277, LNCS, pp 352–361, 2006.
[14]T. Li and R. Deng, “Vulnerability analysis of EMAP an efficient RFID mutual authentication protocol,”Proc. of AReS, 2007.
[15]T. Li, G. Wang, “Security analysis of two ultra-lightweight RFID authentication protocols,” Proc. of IFIP-SEC, 2007.
[16]Yu C. Hung and Wei H. Chen, “Security of ultra-lightweight RFID authentication protocols and its improvements,” SIGOPS Oper. Syst.Vol. 41, No. 4, 83–86, 2007.
[17]M. Barasz, B. Boros, P. Ligeti, K. Loja and D. Nagy, “Passive Attack Against the M2AP Mutual Authentication Protocol for RFID Tags,” Proc. of First International EURASIP Workshop on RFID Technology, 2007.
[18]T. Cao, E. Bertino, and H. Lei, “Security Analysis of the SASI Protocol,” IEEE Transactions on Dependable and Secure Computing, Vol. 6, No. 1, pp. 73–77, 2009.
[19]P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Tapiador, and A. Ribagorda “Advances in ultralightweight cryptography for low-cost RFID tags: Gossamer protocol”, Information Security Applications, Lecture Notes in Computer Science, LNCS, Vol. 5379, pp. 56-68, 2009.
[20]J. C. H. Castro, J. M. Est’evez Tapiador, P. Peris-Lopez, and J. J. Quisquater, “Cryptanalysis of the SASI Ultralightweight RFID Authentication Protocol with Modular Rotations,” CoRR, Vol. abs/0811.4257, 2008.
[21]Eslam Gamal, Emanshaaban, and Mohamed Hashem, “Lightweight Mutual Authentication Protocol for Low Cost RFID Tags,” International Journal of Network Security & Its Applications (IJNSA), Vol 2, No. 2. pp 27-37, 2010.
[22]N Ram and R Suganya, “SSL-MAP: A More Secure Gossamer Based Mutual authentication Protocol for Passive RFID Tags,” International Journal on Computer Science and Engineering, Vol. 02, pp 363-367, 2010.