基于位替換運算的RFID雙向認證協(xié)議

杜宗印，章國安，袁紅林

(南通大學 電子信息學院，江蘇 南通226019)

責任編輯:薛 京

射頻識別(Radio Frequency Identification，RFID)是一種非接觸式自動識別技術(shù)，現(xiàn)已廣泛應用于身份認證、物品識別、門禁系統(tǒng)、高速公路自動收費甚至動物跟蹤等領(lǐng)域。RFID系統(tǒng)主要包含標簽、閱讀器及后端數(shù)據(jù)庫3部分，在其通信協(xié)議設計時，通常認為，后端數(shù)據(jù)庫與閱讀器之間的傳輸信道是安全的，可將它們共同視為協(xié)議一方，本文統(tǒng)稱為閱讀器;而標簽與閱讀器之間的傳輸信道存在多種潛在攻擊[1]，可將標簽單獨視為協(xié)議另一方。同時，由于RFID系統(tǒng)硬件資源受到計算能力、存儲空間等因素的限制，因而，設計出安全性較好、成本較低的RFID認證協(xié)議是至關(guān)重要的。

目前，研究者們已提出多種認證協(xié)議，如HB系列協(xié)議、Hash-Lock協(xié)議、LMAP等，文獻[2]中將它們劃分為全面、簡單、輕量級及超輕量級4類認證協(xié)議。全面認證協(xié)議需要密碼算法的支持，如對稱密碼算法、公開密碼算法等;簡單認證協(xié)議需要在標簽中建立偽隨機數(shù)發(fā)生器和單向哈希函數(shù);輕量級認證協(xié)議需要在標簽中建立偽隨機數(shù)發(fā)生器和循環(huán)冗余檢驗編碼;超輕量級認證協(xié)議只需在標簽中提供簡單的位運算，如異或(⊕)、或(∨)、與(∧)及模二加(+)等。其中，超輕量級認證協(xié)議較前3類，可大大降低標簽的存儲空間和計算需求。因而，它是近期的研究熱點。

超輕量級認證協(xié)議LMAP[3]由Peris-Lopez等人率先提出，并且進一步提出了EMAP[4]和M2AP[5]，這些協(xié)議只需⊕、∨、∧和+運算，在認證通信中非常有效，引起了人們一時的關(guān)注。但文獻[6]指出它們存在主動與被動攻擊;文獻[2]中Chien在協(xié)議中引入左循環(huán)移位運算Rot(X，Y)——將X循環(huán)左移wt(Y)位，wt(Y)是Y的漢明重量，并提出了非常典型的SASI協(xié)議，其認證性和數(shù)據(jù)完整性更強，但文獻[7]分析發(fā)現(xiàn)它存在跟蹤及拒絕服務(DoS)攻擊;超輕量級Gossamer協(xié)議[8]，首次引入MIXBITS函數(shù)，該函數(shù)采用右移及加法操作實現(xiàn)，具有很高的效率，但由于該協(xié)議的初始狀態(tài)與SASI協(xié)議相同，故它仍存在DoS攻擊。

為解決現(xiàn)有RFID認證協(xié)議所存在的問題，本文根據(jù)AES加密算法[9]設計了位替換運算Sub(X，Y)，并協(xié)同按位異或及Rot(X，Y)運算提出一種新的基于位替換的RFID雙向認證協(xié)議(SRMAP)。

1 所提協(xié)議SRMAP

1.1 位替換運算

SRMAP中，異或和左循環(huán)移位[2，7]已詳細描述，位替換運算Sub(X，Y)設計如下:

設X、Y是兩個具有L位的二進制數(shù)組，獲取Y中為1的位，X中與之對應的位元素取反將其替換，則二進制數(shù)組X中共有n=wt(Y)個元素被替換，其中wt(Y)為Y的漢明重。

位替換運算在標簽中實現(xiàn)時，采用文獻[10]提出的指針形式，它比直接采用邏輯門效率更高。設指針rX、rY分別指向數(shù)組X、Y，rX、rY同時從X、Y最高位遍歷，當rY指向Y中元素為0時，rX所指X中元素不變;當rY指向Y中元素為1時，rX所指X位上元素用其反(0的反為1)替換，最后Sub(X，Y)即是被替換后的二進制串X。與文獻[10]中各指針需遍歷數(shù)組2次相比，Sub(X，Y)運算只需遍歷1次，效率提高。

例如，給定L=8，取X=10011001，Y=01101011，則Sub(X，Y)=11111010，運算過程如圖1所示。

圖1 Sub(X，Y)運算實例

1.2 SRMAP通信流程

協(xié)議SRMAP運行時，標簽內(nèi)需存儲其真正ID、當前標簽假名IDS、當前認證密鑰K1和K2，閱讀器中需含有偽隨機數(shù)發(fā)生器及存儲各標簽真正ID、當前信息}及前一次會話信息}。該協(xié)議包括標簽識別、雙向認證、假名和密鑰更新3個階段。各個階段進行詳細描述如下，具體通信流程如圖2所示。

圖2 所提協(xié)議SRMAP通信流程

標簽識別:閱讀器向標簽發(fā)送請求信號“Query”，標簽收到請求信號后，向閱讀器返回假名IDS，閱讀器在后端數(shù)據(jù)庫中搜索相同的IDS，若搜到，則進入雙向認證階段;若未搜到，閱讀器再次向標簽發(fā)送請求。

雙向認證:閱讀器查找與IDS匹配的密鑰，然后生成隨機數(shù)N1、N2，計算A=Sub(K1，K2)⊕N1，B=Sub(K1，Rot(N1，N1))⊕Rot(Sub(K2，K1)，N1)，并發(fā)送至標簽。

標簽接收到A||B后，提取隨機數(shù)N1，N1=A⊕Sub(K1，K2)，并采用與B相同的算法計算B'，如果B'=B，則認證閱讀器成功;如果B'≠B，認證失敗，協(xié)議終止。標簽成功認證閱讀器后，計算C=Sub(Rot(N1，K1)，K2)⊕Sub(N1⊕K2，K1)并返回給閱讀器，閱讀器采用與C相同的算法，利用自身存儲的數(shù)據(jù)計算C'，若C'=C，則成功認證標簽，進入下一階段;若C'≠C，認證失敗，協(xié)議終止。

假名和密鑰更新:閱讀器成功認證標簽后，閱讀器立即進行標簽假名和密鑰更新，算法為

而原來使用的{IDS，K1，K2}則變?yōu)?/p>

若此時的IDSnew與后端數(shù)據(jù)庫中其他某個IDS相同，則必須重新生成N2再計算IDSnew，直到IDSnew與數(shù)據(jù)庫中原存儲的各IDS不同為止，以確保標簽的IDSnew與其ID是一一對應的。然后計算D=Sub(K1⊕K2，N1)⊕N2和E=Sub(N1，N2)⊕Rot(N1，N2)并發(fā)送至標簽。

標簽收到D||E后，提取隨機數(shù)N2=D⊕Sub(K1⊕K2，N1)，并用與E相同的算法計算E'，若E'=E，則同閱讀器更新算法進行標簽內(nèi)數(shù)據(jù)更新，并丟棄原來使用的數(shù)據(jù){IDS，K1，K2}，如果E'≠E，標簽內(nèi)不更新數(shù)據(jù)。

2 安全與性能分析

2.1 安全分析

1)雙向認證和數(shù)據(jù)完整性:SRMAP能夠確保標簽與閱讀器得到相互認證，因為只有合法的閱讀器擁有預共享密鑰K1、K2，能計算傳輸消息A||B，也只有合法的標簽才能夠根據(jù)消息A獲取正確的隨機數(shù)N1，計算消息C;該協(xié)議始終運用位替換Sub(X，Y)與異或運算共同對隨機數(shù)加密傳輸，且閱讀器和標簽各自產(chǎn)生了認證消息B、C，用于與接收到的消息進行比較，保證了數(shù)據(jù)的完整性。

2)標簽匿名性和不可跟蹤性:該協(xié)議中標簽對所有攻擊者具有匿名性，因為協(xié)議運行時，標簽始終未透漏其真正ID，而一直使用的是其假名IDS，而且協(xié)議結(jié)束時，標簽都會更新其假名和密鑰;攻擊者若截獲標簽響應，對其認真分析，跟蹤該標簽，但每一次會話都生成新的隨機數(shù)N1、N2參與運算，對以前消息分析是毫無意義的，故攻擊者不可能成功跟蹤標簽。

3)抵抗假冒攻擊:攻擊者可以假冒合法閱讀器向標簽發(fā)送請求消息，獲得標簽響應，但由于攻擊者本身并不含有真正的密鑰K1、K2，不能得出正確的認證消息A||B，協(xié)議失敗。同樣，如果攻擊者假冒標簽截獲閱讀器發(fā)出的消息A||B，但由于其本身并不含有密鑰K1、K2而不能正確計算B'，即使攻擊者假裝認證閱讀器成功，它也不能計算出一致的消息C，協(xié)議運行失敗。所以，該協(xié)議能夠抵抗假冒攻擊。

4)抵抗重傳攻擊:即使攻擊者多次收集閱讀器與標簽的交互信息，在以后的會話中進行重放，也不能使協(xié)議成功運行。攻擊者如果重放前次會話中的消息A、B和C，由于在每次會話中都有新的偽隨機數(shù)N1、N2，且每次會話后密鑰也要更新，保證了數(shù)據(jù)的新鮮性，重傳失效。

5)抵抗DoS攻擊:在更新階段，如果攻擊者截獲最后的傳輸消息D||E，標簽無法驗證E'是否等于E，則不進行更新，而后端數(shù)據(jù)庫中存有標簽的兩組消息，當協(xié)議再次運行時，標簽返回的是IDSold閱讀器仍然能夠搜索到相應的信息，協(xié)議能夠正常運行。因而，該協(xié)議可以抵抗DoS攻擊[7]。

6)前向安全性:該協(xié)議能夠提供前向安全性，是因為每次會話都有新的隨機數(shù)參與運算，其對攻擊者是不可預知的，即使最后攻擊者破解了標簽的當前信息}，該協(xié)議也能夠保證標簽之前任何信息的秘密性。

2.2 性能分析

由于閱讀器不受硬件資源的限制，主要從標簽內(nèi)部的計算需求、存儲空間和通信量這3個方面來分析所提協(xié)議SRMAP。

計算需求:SRMAP在計算上只需要XOR、Rot(X，Y)及位替換Sub(X，Y)三種簡單的位運算。其中，XOR與Rot(X，Y)只需少量簡單邏輯門即可硬件實現(xiàn)，而本文設計的Sub(X，Y)運算在標簽中運用指針也可有效實現(xiàn)。

再者，本文協(xié)議有效避開了按位與或的存儲空間:協(xié)議運行結(jié)束時，標簽需丟棄前一次會話使用的數(shù)據(jù)，標簽中只存儲一組信息{ID，IDSnew，K1new，K2new};當認證協(xié)議運行中斷時，標簽不更新會話信息，只存儲{ID，IDSold，K1old，K2old}。設標簽身份識別和密鑰的長度都為L位，則標簽內(nèi)存空間共需4L位。

通信量:協(xié)議運行共需傳輸?shù)南⑹恰癚uery”，IDS及A～F，設“Query”需5 byte，其他消息均為L位，則總通信量即是5×8+L×6=6L+40位，而標簽傳輸?shù)南⒅挥蠭DS和C，即標簽上的通信量為2L位。

將所提超輕量級認證協(xié)議SRMAP與其他幾種超輕量級認證協(xié)議對比，如表1所示。

表1 超輕量級認證協(xié)議性能對比

3 協(xié)議的形式化分析

BAN邏輯[11]是在多種安全協(xié)議形式化分析方法中應用最為廣泛的，它于1989年由Burrows、Abadi和Needham提出。本文即采用BAN邏輯形式化證明協(xié)議的安全性。

3.1 BAN邏輯語法及推導準則

由于BAN邏輯知識較為復雜，本文只介紹證明過程中所用到的相關(guān)語法及推導規(guī)則如下，詳細見文獻[11]。

1)語法

{X}K:用密鑰K加密后X的密文;

P←→KQ:主體P和Q之間共享密鑰;

P believes X:主體P相信消息X是真的;

P sees X:主體P接收到包含X的消息;

P said X:主體P曾發(fā)送過消息X;

P controls X:主體P對消息X有管轄權(quán);

fresh(X):X是新鮮的。

2)推導規(guī)則

R1消息含義規(guī)則

式(3)表示:如果P相信K是P和Q的共享密鑰，并且P曾經(jīng)接收到用K加密的消息{X}K，則P相信Q發(fā)送過消息X。

R2隨機數(shù)驗證規(guī)則

式(4)表示:如果主體P相信消息X是新鮮的，并且P相信Q發(fā)送過消息X，則P相信主體Q相信消息X。

式(5)表示:如果主體P收到了消息(X，Y)，則P收到了消息X。

R4管轄規(guī)則

式(6)表示:如果主體相信P相信主體Q對消息X具有管轄權(quán)，并且P相信Q相信X，則P相信消息X。

R5消息新鮮性規(guī)則

式(7)表示:如果主體P相信消息X是新鮮的，則P相信消息(X，Y)是新鮮的。

3.2 形式化證明過程

BAN邏輯形式化證明可簡化為:建立協(xié)議理想化模型、給出協(xié)議的初始假設、給出協(xié)議預期達成的安全目標及分析推理4個步驟。SRMAP的證明過程如下:

1)協(xié)議理想化模型

在理想化模型中，需去除原來協(xié)議所有的明文傳輸

其中，A、B、C為用密鑰Ki加密后的密文。

2)初始假設

3)預期安全目標)

4)分析推理

由Msg3、初始假設P2及消息含義規(guī)則R1、接收準則R3得

由初始假設P4及消息新鮮性規(guī)則R5得

又由隨機數(shù)驗證規(guī)則R2及以上推出的式(11)、(12)得

最后由初始假設P5、管轄規(guī)則R4及式(13)推出T believes B，目標G1得證。

同樣，由Msg4、假設P1及規(guī)則R1得R believes T said C;由初始假設P3及規(guī)則R得R believes #(C);又因為準則R2得R believes T believes C;最后由假設P6及規(guī)則R4得到R believes C，目標G2得證。

綜上，該協(xié)議可以達到預期的安全目標，故它是安全的、可行的。

4 小結(jié)

本文運用新設計的位替換運算以及異或、左循環(huán)移位運算，提出了一種新的超輕量級認證協(xié)議SRMAP，并通過BAN邏輯形式化分析方法證明了該協(xié)議的安全性與可行性。安全與性能分析結(jié)果表明:該協(xié)議可抵抗DoS等多種攻擊，安全性較好;采用該協(xié)議的標簽實現(xiàn)效率高，且所需存儲空間和通信量較少。

[1]游相柏，劉毅敏.RFID安全認證協(xié)議研究[J].電視技術(shù)，2012，36(15):104-107.

[2]CHIEN H Y.SASI:a new ultra-lightweight RFID authentication protocol providing strong authentication and strong integrity[J].IEEE Trans.Dependable and Secure Computing，2007，4(4):337-340.

[3]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，ESTEVEZ-TAPIADOR J M，et al.LMAP:A real lightweight mutual authentication protocol for low-cost RFID tags[C]//Proc.2nd Workshop on RFID Security.New Jersey，USA:IEEE Press，2006:137-148.

[4]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，ESTEVEZ-TAPIADOR J M，et al.EMAP:an efficient mutual authentication protocol for low-cost RFID tags[C]//Proc.IS’06.Berlin:Springer Press，2006:352-361.

[5]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，TAPIADOR J M，et al.M2AP:a minimalist mutual authentication protocol for low-cost RFID tags[C]//Proc.UIC’06.Berlin:Springer Press，2006:912-923.

[6]王少輝，王高麗.RFID認證協(xié)議ULAP的被動攻擊分析[J].計算機工程，2010，36(22):17-19.

[7]SUN H M，TING W C，WANG K H.On the security of Chien's ultralightweight RFID authentication[J].IEEE Trans.Dependable and Secure Computing，2011，8(2):315-319.

[8]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，ESTEVEZ-TAPIADOR J M，et al.Advances in ultra-lightweight cryptography for low-cost RFID tags:Gossamer protocol[C]//Proc.9th International Workshop，WISA 2008.Berlin:Springer Press，2009:56-68.

[9]王沁，梁靜，齊悅.一種有效縮減AES算法S盒面積的組合邏輯優(yōu)化設計[J].電子學報，2010，38(4):939-942.

[10]TIAN Yun，CHEN Gongliang，LI Jianhua.A new ultra-lightweight RFID authentication protocol with permutation[J].IEEE Communications Letters，2012，16(5):702-705.

[11]王聰，劉軍，王孝國，等.安全協(xié)議原理與驗證[M].北京:北京郵電大學出版社，2011.