王笑梅，張秋劍

上海師范大學 信息與機電工程學院，上海 200234

基于橢圓曲線零知識的RFID雙向身份認證

王笑梅，張秋劍

上海師范大學 信息與機電工程學院，上海 200234

針對RFID系統(tǒng)中標簽與讀寫器的攻擊，從攻擊方式來看，主要有兩種形式：一是直接攻擊，利用電子通信對RFID系統(tǒng)的不同物理位置實施攻擊。如拒絕服務攻擊（DoS），攻擊者可以通過一些射頻信號裝置短時間內向讀寫器端發(fā)送大量數據信號，導致RFID系統(tǒng)被大量的信號所淹沒，使系統(tǒng)喪失處理正常數據的能力，陷入停滯狀態(tài)[1]。另一種是身份欺騙攻擊，電子標簽是存儲一定數據的信息源，與社會工程學相關的安全威脅會被黑客或者攻擊者利用，成為新型的信息化犯罪。從攻擊實施的位置上看，可以通過造標簽，欺騙讀寫器，從而將非法數據信息送入系統(tǒng)；也可以通過偽造讀寫器，在用戶不被覺察的情況下讀取用戶的標簽信息，竊取用戶隱私；還可以通過射頻設備在空中截獲標簽與讀寫器之間的通信，從而利用這些設備偽造讀寫器或者電子標簽，展開數據攻擊、病毒攻擊、ONS攻擊等多種具體的入侵方法。本文設計的認證方案主要用于對抗第二種形式的攻擊，即身份欺騙攻擊，其主要形式有[1]：

（1）嗅探：攻擊者可以竊聽標簽與讀寫器之間的通信，獲取其中有用的信息和數據。這種竊取信息的行為可能不被RFID系統(tǒng)和用戶所覺察。

（2）標簽追蹤：電子標簽中常存儲機要的或者個人隱私的信息，攻擊者可以利用RFID便攜設備，在用戶不知情的條件下，查詢用戶的電子標簽，從而非法獲取用戶數據，并可與個人身份或攜帶標簽的物體位置相關聯(lián)。

（3）重播攻擊：攻擊者可以使用RFID中繼設備截獲RFID信號，將其中的數據保存下來，并不斷重復地發(fā)送給讀寫器。由于這些數據是真實有效的，所以系統(tǒng)就會以正常接收的方式處理這些數據。

（4）篡改信息：攻擊者通過獲取到的標簽數據，利用空白或可擦寫的標簽制造“真實的”RFID標簽，將一些非法信息寫入標簽內；或者直接修改某個非法獲得的標簽上信息，然后用篡改后的標簽訪問讀寫器，從而攻擊RFID系統(tǒng)。

1 相關協(xié)議分析

RFID系統(tǒng)中，電子標簽具有一定的數據存儲和處理能力，可以進行數據加密、數字簽名、身份認證等應用。其自身存在存儲容量和計算速度限制的特點，且被動標簽電源供給有限。隨著RFID系統(tǒng)應用越來越廣泛，很多電子標簽中存儲信息的敏感度以及安全性要求較高，所以，在設計安全協(xié)議時要做到低成本、低功耗、輕量級，在選擇加密體制時應根據上述特點選擇較為適合的加密算法。

隨著RFID技術的發(fā)展，國內外學者已提出了許多安全協(xié)議，包括基于對稱加密體制的認證協(xié)議[2-6]。主要有哈希函數或AES算法的協(xié)議，例如文獻[2]提出的基于哈希函數的認證協(xié)議，在每次通信時閱讀器都生成一個隨機數r，與標簽ID的更新相結合，可以防止重放攻擊和位置檢測，但一個會話如果被非法終止，容易導致標簽的位置檢測攻擊與ID更新非同步攻擊，且不能有效防止假冒攻擊。這些基于對稱加密體制的協(xié)議較簡單，能滿足RFID標簽有限存儲空間和計算能力的特性，以確保RFID標簽的低成本，但現(xiàn)在很多RFID應用需要能確保更高的安全等級。近年來，RFID的運算能力越來越強，公鑰計算的復雜性已不再成為瓶頸?；诠€密碼體制的安全協(xié)議在RFID技術的研究和應用中越來越廣泛。然而一些知名的公鑰加密算法密鑰長度太大，運算代價太高，因而部分研究者將注意力轉向橢圓曲線加密技術（Elliptic Curves Cryptosystems，ECC）。

ECC是利用有限域上的橢圓曲線有限群代替基于離散對數問題密碼體制中的有限循環(huán)群后得到的一類密碼體制。與其他公鑰算法相比，ECC有非常大的優(yōu)越性[7]：抗攻擊性強，相同的密鑰長度，其抗攻擊性要強很多倍；存儲空間占用小，其密鑰長度和系統(tǒng)參數比RSA、DSA要小得多；帶寬要求低，尤其應用于短消息加解密時；計算量小，處理速度快，總的速度比RSA要快得多，如在一定的相同計算資源條件下，160 bit的ECC算法的簽名時間為3.0 ms，密鑰對生成時間為3.8 ms，而1 024 bit的RSA算法卻分別高達228.4 ms和4 708.3 ms，且隨著密鑰長度的增加，ECC存儲空間較小的優(yōu)勢會愈加明顯。因此，ECC特別適用于在計算能力和存儲空間上都有局限性的RFID系統(tǒng)。

基于ECC的認證協(xié)議主要有文獻[8-12]。文獻[8]中介紹了基于有限域GF(2n)上的橢圓曲線的硬件實現(xiàn)，為了達到面積小和速度快的目標，設計中采用Montgomery階梯算法來進行橢圓曲線上點的計算，以節(jié)省存儲空間；同時由于采用了射影坐標，使得整個過程只需要在讀寫器上進行一次模逆計算，從而大大提高了速度，但其不具有向前安全性。文獻[9]利用修正的橢圓曲線數字簽名算法實現(xiàn)讀寫器和標簽之間的簽名和驗證，提供一個雙向身份驗證協(xié)議。文獻[10]提出的是基于ECC的ASPECΤ協(xié)議，該協(xié)議具有一定高效性，但也不具備向前安全性。文獻[11]提出的是基于ECC的ASK協(xié)議，該協(xié)議存在已知密鑰攻擊缺陷，甚至不能完成相互認證，用戶身份的保密性也存在問題。文獻[12]介紹了一個近似橢圓曲線運算器，并提出了基于Okamoto的標簽認證協(xié)議并進行性能分析。

本文在橢圓曲線加密體制的基礎上，引入零知識身份證明思想，提出了一種基于橢圓曲線零知識的雙向認證協(xié)議，具有更高的安全性和效率，能夠較好地防御各種身份欺騙攻擊，保障通信的安全與隱秘。

2 基本原理

2.1 橢圓曲線加密體制的基本原理

橢圓曲線密碼體制是在各種涉及有限域乘法群的公鑰密碼體制中，用有限域上的橢圓曲線構成的群來類比有限域上的乘法群，從而獲得類似的公鑰密碼體制。這類體制的安全性是基于橢圓曲線離散對數問題（ECDLP）求解的困難性。從而引出橢圓曲線密碼技術的核心，由有限域上橢圓曲線的點所構成的Abel群的離散對數問題。

2.2 零知識協(xié)議的基本原理

零知識證明是指證明者（prover）在不泄露任何信息的情況下向驗證者（verifier）證明自己知道秘密。假設證明者P擁有秘密S，并需要向驗證者V證明。V首先向P發(fā)送若干問題中的一個，問題只能夠P回答，而且問題只是與S相關，在一定程度上并不泄露任何關于S的信息；P收到后，向V發(fā)送這個問題的答案；然后V繼續(xù)選取問題向P發(fā)送；以上過程重復n次，全部成功即可證明P擁有S。在這個過程中，為了做到不泄露任何與秘密相關的信息，V與P之間安全連續(xù)的信息交換主要依靠選取隨機數值[13]。

在V與P通過通信信道連續(xù)的信息交換過程中，如果攻擊者采用偷聽的方式，那么他一次獲得的信息只可能是某一次的問題，或者答案。因為認證過程是隨機的，所以獲得的信息不能幫助他來完成對RFID系統(tǒng)欺騙[3]。

3 雙向身份認證協(xié)議的設計

任何一種通過對閱讀器與標簽的身份欺騙攻擊，都是為了間接攻擊RFID系統(tǒng)。其實質都是對標簽和讀寫器某一方的仿冒，然后對另一方進行身份欺騙，從而獲得身份認定，進入RFID系統(tǒng)內部。本文將橢圓曲線加密體制與零知識證明身份認證機制兩者有機集合，設計出一種對標簽與閱讀器雙方都做身份鑒別的雙向認證協(xié)議，該協(xié)議將應用于低成本的無源電子標簽RFID環(huán)境中。

3.1 橢圓曲線有限域的選取

通過橢圓曲線定義和點群運算法則可知，不同特征值決定不同的有限域，不同的有限域上有各自通用的算法，所提供的運算性能各有長短。根據NISΤ規(guī)范，常用在加密體制中應用的有限域是大素數域GF(q)和特征2域GF(2m)。由于RFID系統(tǒng)對計算量、處理速度、存儲空間、安全性等特殊要求，GF(2m)更適合Τag-reader間的加密、解密，且GF(2m)作為二進制域更有利于在RFID硬件系統(tǒng)中快速實現(xiàn)。

3.2 橢圓曲線的參數

設計算法的第一步是對橢圓曲線相關參數的選取。橢圓曲線密碼體制的系統(tǒng)參數為[13]：

為求解上述橢圓曲線離散對數問題，實現(xiàn)高效安全的加密機制，必須對這些參數作特殊限制：

（1）有限域GF(q)，由于有限域選擇GF(2m)，q=2m，m為正整數。

（2）參數a和b，定義GF(q)上橢圓曲線E，即Y2=X3+aX+b(p＞3)或Y2+XY=X3+aX+b(p=2)（由于特征值為3時有限域上的橢圓曲線在密碼體制中的實現(xiàn)不具有實際意義，因此將忽略該種形式的曲線）。

（3）P表示基點，n為素數是P的階。

（4）h是余因子，等于橢圓曲線的階除以n的商(h=E(Fq)/n)。

（5）f(x)為次數為m的不可約二進制多項式，定義了有限域的域多項式。

在設計加密機制時，通過對橢圓曲線參數的選取，從而確定一條最佳橢圓曲線和基點。然而，確定具有素數階為n的基點P，最為困難和耗時[13]。

3.3 核心算法的設計

在RIFD系統(tǒng)中，標簽與讀寫器的雙向認證需要數據庫存儲標簽的動態(tài)ID值和橢圓曲線點，每次對標簽認證成功后，數據庫更新ID值和橢圓曲線點兩部分值，為下次認證做準備。在識別標簽之前，首先要對讀寫器的身份進行鑒別：

（1）系統(tǒng)初始化。此步驟主要完成參數選取，密鑰生成等工作：

①根據3.2節(jié)的相關介紹，在有限域GF(2m)上確定橢圓曲線E(Fq)。

②在區(qū)間[ ] 1，n-1中隨機選取整數X，作為私鑰。

③根據基點P，計算點Y=XP，Y為公鑰；利用離散對數問題的求解困難性，由私鑰計算公鑰，保證了在已知公鑰Y的情況下不能求出私鑰X。

④在E(Fq)上為每個標簽Ti選取橢圓曲線上一點，Ti每次被讀取后，更換新的點。

⑤將私鑰X保密，將公鑰Y公開。

（2）讀寫器身份認證。為了不使系統(tǒng)中出現(xiàn)仿冒的讀寫器，在對標簽身份驗證之前，先對讀寫器進行身份認證：

①讀寫器在區(qū)間[1 ，n-1]中隨機選取整數R1，計算Q=R1P，并發(fā)送Q給標簽。

②標簽選取一個隨機數R2(R2≥1)，發(fā)送給讀寫器。

③讀寫器計算V=R1+R2X，并發(fā)送給標簽。

④標簽計算VP是否等于R2Y+Q，若相等，則讀寫器身份有效，否則讀寫器身份無效。

讀寫器身份認證過程，如圖1所示。

圖1 讀寫器身份認證過程

（3）標簽身份認證。為了防止同一個標簽被系統(tǒng)破壞者再次讀取，標簽Ti的曲線點用表示的坐標，在每次被成功讀取后生成新的點每次驗證Ti時，Ti根據計算動態(tài)ID編號，用表示，其中j表示Ti被j次讀取。標簽Ti身份認證的步驟：

①在讀寫器認證成功后，Ti根據，計算=，并發(fā)送給讀寫器。

②Ti計算=，作為新的橢圓曲線點，替換存儲。

③系統(tǒng)將讀寫器接收到的與后臺數據庫中存儲的ID值作匹配，若匹配成功，則證明標簽身份有效，否則認證失敗。

標簽身份認證過程，如圖2所示。

4 性能分析

4.1 效率分析

圖2 標簽身份認證過程

硬件資源占用方面，普通的被動標簽中一般擁有15 000個邏輯門[14]，m=137的特征2域GF(2137)，只需使用10 000個邏輯門。標簽中用于產生R2的隨機數發(fā)生器僅需要幾百個邏輯門。然而在Hash鎖協(xié)議中，一個Hash函數單元就需要17 000個邏輯門。

運算復雜度方面，該協(xié)議的認證過程中只使用到簡單的矩陣運算、橢圓曲線的點群運算、異或運算和隨機數的產生，沒有復雜的指數運算。Karthikeyan[15]等提出了一種簡單加密技術的安全認證協(xié)議，實現(xiàn)比較容易，也只涉及異或和矩陣運算操作等簡單邏輯運算，但是存在重放攻擊，不能保證不可追蹤性等問題。Chien[15]等在EPC-C1G2標準下提出了一個讀寫器和標簽相互認證的安全協(xié)議，協(xié)議只涉及XOR、CRC和PRNG等簡單邏輯運算，且每次認證后都對數據庫和標簽進行秘密信息同步更新，但協(xié)議存在讀寫器和標簽假冒以及去同步化攻擊的安全缺陷。密鑰為160 bit的橢圓曲線加密計算一次需要3.69 ms[16]，m= 137的特征2域GF(2137)密鑰長度為137 bit，計算一次需要3.16 ms。在雙向驗證過程中的三次點乘法運算時間為1.53 s[17]，由于點乘運算可以和認證信息傳輸同時進行，所以整個運算時間為0.91 s，運算速度較快。

通信時間則取決于協(xié)議中讀寫器和標簽交換的認證信息長度。每次傳輸的認證消息量最多為420位（包括用戶標識和加密消息），這比以往提出的消息交換量都?。˙eller-Chang-Yacobi使用8 320位，Aziz-Diffie使用8 680位，M.Aydos使用1 602位）。在使用普通被動標簽的RFID系統(tǒng)中，Τag-reader通信信道的波特率一般在520～640 bit/s，假定波特率為520 bit/s的情況下，完成雙向身份認證(send(Q，R2，V))的傳輸時間為0.8 s，可以滿足RFID系統(tǒng)對帶寬的限制。若該RFID系統(tǒng)中使用100萬個標簽，根據防碰撞算法，位數為48 bit可將沖突降低到1%，其傳輸時間為0.09 s。從低成本電子標簽的角度分析，該協(xié)議的硬件消耗和運算復雜度適當，運行效率較高。

4.2 安全性分析

本文提出的認證協(xié)議具有一定的前向安全性和抗攻擊性，對身份欺騙類型的幾種典型攻擊都具有一定的防御能力，可以保障通信的安全與隱秘。

雙向可認證性：本文提出的協(xié)議是一種雙向認證協(xié)議，強調被驗證雙方都必須提供完整的有效驗證信息，標簽認證讀寫器身份過程中的核心是計算VP是否等于R2Y+Q：

本協(xié)議中零知識證明只需一次驗證，就可取得有效信息，無需將驗證步驟重復n次以達到可信度[12]。

零知識性：任何一種基于身份欺騙的攻擊，主要前提是攻擊者對驗證信息的獲取。如果攻擊者采用竊聽設備接收通信信號，驗證信息的零知識性使得這些信息對其毫無用處，無論是(Q，R2，V)，還是動態(tài)ID，都沒有泄露任何有用信息，大大降低了嗅探所能造成的破壞。

求解復雜性：攻擊者利用RFID便攜設備跟蹤標簽時，標簽首先驗證該設備的身份，則該設備必須具有私鑰X，若沒有X，攻擊者通過截取到的Y和P求算私鑰X的困難性等同于基于橢圓曲線離散對數問題求解的困難性。

不可轉讓性：在讀寫器驗證階段，交互雙方傳輸的信息(Q，R2，V)是由認證方產生的隨機數或者通過隨機數計算出的結果，由于標簽每次隨機產生R2值都不一樣，這樣攻擊者所截取的一次認證中交換的全部信息重放到讀寫器端時，讀寫器通過V=R1+R2X的計算可發(fā)覺重播攻擊。

前向安全性：篡改標簽需要有效的橢圓曲線點，用于求出動態(tài)ID鑒別標簽身份，前提首先是使用RFID設備讀取有效標簽。然而在標簽身份證明過程中引入動態(tài)ID的方式，實現(xiàn)標簽和數據庫中該標簽的橢圓曲線點在每次雙向驗證成功后同步更新。所以即使當前標簽的ID被非法獲取，標簽以前的通信信息仍然無法獲得，使得仿造或篡改標簽不具備新的身份認證信息。

對于有代表性的基于ECC的各種認證協(xié)議在安全性上的對比結果如表1所示?？梢姳疚乃釁f(xié)議在安全性上可以抵制前面分析中所提及的身份欺騙攻擊中的各種形式。從以上的比較研究中可知，本文的協(xié)議有很好的安全性和抗攻擊性，且具有較好的實現(xiàn)效率和實現(xiàn)成本，更適合于RFID系統(tǒng)。

表1 各協(xié)議安全性對比

5 結語

針對RFID系統(tǒng)應用中越來越多的身份欺騙攻擊，本文以橢圓曲線加密體制和零知識身份證明為基礎，提出一種對標簽與閱讀器雙方都做身份鑒別的雙向認證協(xié)議，且在協(xié)議中提出一種動態(tài)標簽ID的識別方式。經過性能和安全性分析，該協(xié)議對于低成本的電子標簽，通信和計算復雜性適當，運行效率較高，具有一定的前向安全性和抗攻擊性，能夠較好地防御各種身份欺騙攻擊，保障通信的安全與隱秘。因此針對目前的RFID系統(tǒng)的安全認證，本協(xié)議是一個比較安全、高效、實用的RFID低功耗安全認證方案。

[1]Τhornton F，Haines B，Das A M.RFID security[M].[S.l.]：Syngress Pulishing，Inc，2007.

[2]Chien Hung-Yu，Chen Chehao.Mutual authentication protocol for RFID conforming to EPC class 1 generation 2 standards[J]. Computer Standards&Interfaces，2007，29（2）：254-259.

[3]Dimitriou Τ.A lightweight RFID protocol to protect against traceability and cloning attacks[C]//Τhe First International Conference on Security and Privacy for Emerging Areas in Communications Networks.Washington：IEEE Computer Society，2005：59-66.

[4]Godor G，Antal M，Imre S.Mutual authentication protocol for low computational capacity RFID systems[C]//Global Τelecommunications Conference，2008：1-5.

[5]Godor G，Imre S.Security analysis of the simple lightweight authentication protocol[C]//Ninth International Conference on Digital Object Identifier，2010：231-236.

[6]Τolruul B，Lee K.An advanced mutual-authentication algorithm using AES for RFID systems[J].International Journal of Computer Science and Network Security，2006，6（9）.

[7]胡焰智，馬大瑋，田增山，等.基于ECC的雙向認證及密鑰協(xié)商方案的分析與改進[J].計算機工程與設計，2009，30（2）：318-320.

[8]Braun B，Hess E，Meyer B.Using elliptic curves on RFID tags[J].IJCSNS International Journal of Computer Science and Network Security，2008，8（2）：1-9.

[9]Ahamed S I，Rahman F，Hoque E.ERAP：ECC based RFID authentication protocol[C]//12th IEEE International Workshop on Digital Object Identifier，2008：219-225.

[10]Guenther H，Bart P.Authentication and payment in future mobile systems[J].Journal of Computer Security，2000，8（2）：183-207.

[11]Aydos M，Yanik Τ，Koc K.An high-speed ECC-based wireless authentication protocol on an ARM microprocessor[C]// Τhe 16th Annual Computer Security Applications Conference，2000.

[12]Godor G，Giczit N，Imre S.Elliptic curve cryptography based mutual authentication protocol for low computational complexity environment[C]//5th IEEE International Symposium on Digital Object Identifier Wireless Pervasive Computing（ISWPC），2010：331-336.

[13]Martinez S，Valls M，Roig C，et al.An elliptic curve and zero knowledge based forward secure RFID protocol[C]// Workshop on RFID Security，RFID Sec’07，Malaga，Spain，2007.

[14]Gupta V，Stebila D，F(xiàn)ung S.Speeding up secure Web transactions using elliptic curve cryptography[C]//Network and Distributed Systems Security，2004：231-239.

[15]胡韜，魏國珩.基于低成本標簽的RFID匿名雙向認證協(xié)議[J].計算機應用，2012，32（1）：111-114.

[16]Hein D，Wolkerstorfer J，F(xiàn)elber N.ECC is ready for RFID—a proof in Silicon[C]//Lecture Notes in Computer Science，2009，5381：401-413.

[17]Batina L，Guajardo J，Kerins Τ，et al.An elliptic curve processor suitable for RFID-tags，Report 2006/227[R].Cryptology E-Print Archive，2011.

WANG Xiaomei,ZHANG Qiujian

School of Information&Electronic Engineering,Shanghai Normal University,Shanghai 200234,China

Within the wider spread of RFID technology,all kinds of identity deception attacks aiming at RFID tags and readers grow up.Τo ensure the security and privacy in this communication,the RFID tags and readers need to identify them each other, thus the system will create a credible communication channel.Τhis paper proposes a mutual authentication protocol based on elliptic curve cryptography and zero knowledge authentication,and proposes a dynamic tag-ID technology,solving the sniffing, tracking attacks and other issues efficiently.

elliptic curve cryptography;zero knowledge authentication;Radio Frequency IDentification（RFID）;dynamic ID; user authentication

RFID技術在被廣泛應用的同時，各種針對RFID標簽與讀寫器間身份欺騙的攻擊層出不窮。為保證通信間的安全與隱秘，需要兩者之間相互鑒別身份真?zhèn)?，從而?chuàng)造一條可信的通信信道。以橢圓曲線加密體制和零知識身份證明為基礎，提出一種標簽與讀寫器雙向身份認證的協(xié)議，提出一種動態(tài)標簽ID的方式，更好地解決了嗅探、跟蹤攻擊等問題。

橢圓曲線；零知識證明；射頻識別（RFID）；動態(tài)ID；身份認證

A

ΤP312

10.3778/j.issn.1002-8331.1111-0494

WANG Xiaomei,ZHANG Qiujian.Mutual authentication for RFID based on elliptic curve and zero knowledge.Computer Engineering and Applications,2013,49（15）：97-100.

上海師范大學基金項目（No.SK201051）。

王笑梅（1970—），女，副教授，主要研究方向為無線射頻技術；張秋劍（1983—），男，碩士研究生，主要研究方向為RFID系統(tǒng)安全。E-mail：xiaomei@shnu.edu.cn

2011-11-28

2012-03-22

1002-8331（2013）15-0097-04

CNKI出版日期：2012-04-25 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120425.1719.022.html