位替換運算的超輕量級移動RFID認證協議

梅松青，鄧小茹

廣州醫科大學，廣州510006

1 引言

射頻識別技術出現于二十世紀三四十年代，大面積推廣在二十世紀九十年代。因當時技術受限，及人們需求不大等眾多因素，射頻識別技術在應用中的RFID系統中讀寫器與服務器之間基于有線連接鏈路進行信息交換，該交換方式一般認定為安全可靠，并將該系統稱之為傳統的RFID系統[1-2]。

進入二十一世紀，伴隨著科技的快速發展，以及人類需求的增長，傳統的RFID系統早已無法滿足人們的需求，于是導致移動式RFID系統的產生[3]。移動式RFID系統區別于傳統的RFID系統最大的不同之處在于：移動式RFID系統中讀寫器與服務器之間的通信不在基于有線連接鏈路，而是采用無線連接線路進行信息傳送。無線鏈路因其自身固有的屬性，使得該傳輸方式存在一定的安全隱患[4-5]。適用于傳統RFID系統的雙向認證協議不再適用于移動式RFID系統中，因此需要設計適用于移動式的RFID系統的新雙向認證協議。

在分析近些年提出的適用于移動式RFID系統協議的基礎之上，文中給出一種基于位替換運算的超輕量級的適用于移動式的RFID系統的雙向認證協議。為達到降低通信實體計算量的目標，設計的協議采用位運算進行信息的加密；同時對協議進行基于GNY邏輯形式化分析和安全性分析。

2 相關工作

文獻[6]中提出單向認證的移動認證協議，分析發現該協議無法抵抗中間人攻擊及重放攻擊。文獻[7]中提出了一種基于橢圓曲線的移動認證協議，但分析發現，該方案不能確保讀寫器端隱私的安全，同時標簽端的計算量也較大。

文獻[8]中給出一個輕量級的移動雙向認證協議，協議對信息的加密主要基于PUF函數（物理不可克隆函數）。對協議進行分析：協議無法抵抗異步攻擊。攻擊者通過監聽可獲取完整的通信消息，在阻塞通信實體會話過程時，攻擊者通過將監聽獲取的信息進行重放多次，即可使得標簽一端與后端服務器之間的共享加密密鑰失去一致性，使得攻擊者發起的異步攻擊成功。

文獻[9]中設計出一個超輕量級的移動認證協議，該協議基于按位操作實現對信息的加密。對協議研究：攻擊者可以通過一定的物理手段獲取隱私信息，從而使得攻擊者可以假冒成標簽或其他通信實體進一步進行攻擊，以便于獲取更多的隱私信息，使得攻擊者發起的假冒攻擊成功。

文獻[10]中提出的基于Edwards曲線的移動協議，分析可得知該協議在認證過程中并未實現讀寫器對標簽的認證，使得攻擊者可以假冒標簽發送信息，從而使得協議無法抵抗標簽假冒攻擊。

文獻[11]提出一個移動雙向認證協議，該協議具備一定的安全性。對協議分析：協議未提供標簽一端對讀寫器的認證，使得攻擊者可以假冒成讀寫器給標簽發送信息，以便于攻擊者通過標簽的驗證，獲取標簽反饋的信息，對消息進行分析，使得攻擊者發起的假冒攻擊有效。

鑒于篇幅有限，更多移動式RFID系統雙向認證協議可以參見文獻[12-16]。

鑒于上述移動式雙向認證協議存在的計算量大、通信復雜或存在安全缺陷等不足，文中設計出一種能夠滿足較高安全需求的認證協議MSB。MSB協議采用位替換運算對所要傳送的信息進行加密，盡可能降低通信實體的計算量；為能夠增大攻擊者的破解難度，所有信息加密過程中混入隨機數。對協議進行安全性分析和性能分析，表明協議具備較高的安全性，且協議能夠適用于移動式的無源標簽系統中。

3 MSB設計

3.1 符號說明及協議初始化

為便于文中描述，用符號Bro(X,Y)表示位替換運算（Bit Replacement Operation，Bro）。位替換運算按如下定義進行計算：X和Y屬于二進制序列，長度均為L位；對X和Y均從左向右依次遍歷，當X上的數為0時，將Y上相對應的數替換（0替換為1，1替換為0），X上的數為1時，Y不做任何操作，從而形成一個新的二進制序列Z，即Z=Bro(X,Y)。

為便于對位替換運算的理解，文中給出如下例子進行解釋：取L=8位，X=01100101，Y=00001100，則根據上述有關位替換運算的定義可得Z=Bro(X,Y)=10010110。具體示意圖見圖1所示。

圖1 位替換運算示意圖

對協議中出現的符號進行如表1說明。

表1 符號說明

認證協議開始之前，對協議中的所有通信實體進行初始化操作，初始化完成之后，各通信實體存放信息如下：標簽端存放(KL,KR,IDTag)；移動讀寫器端存放(KL,KR,IDReader)；服務器端存放(KL,KR,IDTag,IDReader)。

3.2 MSB認證流程

雙向認證協議MSB認證過程描述可參見圖2所示。

圖2 MSB認證示意圖

對圖2中雙向認證協議出現的符號進行如表2中的公式說明。

表2 公式說明

結合圖2雙向認證協議MSB具體過程描述如下：

步驟1讀寫器產生隨機數rReader，然后計算A和B，最后將＜Query,A,B＞一并傳送給標簽。

其中A和B計算過程詳細見表2所示。

步驟2標簽比對A⊕KR與B⊕KL是否相等。若A⊕KR=B⊕KL，則讀寫器通過驗證，然后標簽產生隨機數rTag，接著計算C、D、E、F，最后將＜C,D,E,F＞一并傳送給讀寫器，以表示標簽對讀寫器的響應。若A⊕KR≠B⊕KL，表明讀寫器是偽造的，協議停止。

其中C、D、E、F計算過程詳細見表2所示。

步驟3讀寫器通過計算(rReader&KR)⊕C得到隨機數rTag；然后將計算所得隨機數rTag，結合rReader、KL進行計算得到F′，比對F′與F是否相等。

若F′=F，表明讀寫器計算所得隨機數rTag與標簽產生的隨機數rTag是相同的，且標簽通過驗證，然后讀寫器再計算G和H，最后將＜D,E,G,H＞一并傳送給服務器。

若F′≠F，說明標簽是偽造的，協議停止。

其中F′=Bro(rReader&KL,(rReader&KR)⊕C)；G、H計算過程詳細見表2所示。

步驟4服務器分兩步進行，先對讀寫器進行驗證，當且僅當讀寫器驗證通過，再對標簽進行驗證。

（1）對讀寫器的驗證

服務器通過計算G⊕IDReader得到隨機數rReader；然后將計算所得隨機數rReader，結合IDReader、KL進行計算得到H′，比對H′與H是否相等。

若H′=H，表明服務器計算所得隨機數rReader與讀寫器產生的隨機數rReader是相同的，且讀寫器通過驗證，然后服務器開始對標簽的驗證。

若H′=H，服務器將用Kold替換Knew再次進行計算H″。將再次比對H″與H是否相等。如果H″=H，表明讀寫器通過驗證，然后服務器開始對標簽的驗證。如果仍然H″=H，說明讀寫器是偽造的，協議停止。

其中H′=Bro((G⊕IDReader)⊕(IDReader&KL),(G⊕IDReader)&IDReader)、H″=Bro((G⊕IDReader)⊕(IDReader&G⊕IDReader)&IDReader)。

（2）對標簽的驗證

服務器通過計算(IDTag&KL)⊕D得到隨機數rTag；然后將計算所得隨機數rTag，結合KR進行計算得到E′，比對E′與E是否相等。

若E′=E，表明服務器計算所得隨機數rTag與標簽產生的隨機數rTag是相同的，且標簽通過驗證，然后服務器進行步驟（1）。

若E′≠E，服務器將用Kold替換Knew再次進行計算E″。將再次比對E″與E是否相等。如果E″=E，表明標簽通過驗證，然后服務器進行步驟（1）。如果仍然E″≠E，說明標簽是偽造的，協議停止。

其中E′=Bro((IDTag&KL)⊕D,((IDTag&KL)⊕D)⊕KR)、E″=Bro((IDTag&)⊕D,((IDTag&⊕D)⊕

步驟（1）：服務器產生隨機數rDataBase，然后計算I、J、M、N；接著服務器開始進行信息更新Kold=K、K=Knew；最后將＜I,J,M,N＞一并傳送給讀寫器，以表示服務器對讀寫器的響應。

其中Knew=Bro(rDataBase⊕rTag⊕rReader,K)；J、M、N計算過程詳細見表2所示。

步驟5讀寫器通過計算I⊕(rReader&IDReader)得到隨機數rDataBase，然后將計算所得隨機數rDataBase，結合IDReader、rReader進行計算得到M′，比對M′與M是否相等。

若M′=M，表明讀寫器計算所得隨機數rDataBase與服務器產生的隨機數rDataBase是相同的，且服務器通過驗證；然后讀寫器計算Q；接著讀寫器開始進行信息更新K=Bro(rDataBase⊕rTag⊕rReader,K)；最后將＜J,N,Q＞一并傳送給標簽。

若M′≠M，說明服務器是偽造的，協議停止。

其中M′=Bro(rReader,(I⊕(rReader&IDReader))&IDReader)；Q計算過程詳細見表2所示。

步驟6標簽需要完成對讀寫器和服務器的驗證。

（1）對服務器的驗證

標簽通過計算J⊕(rTag&IDTag)得到隨機數rDataBase，然后將計算所得隨機數rDataBase，結合rTag、IDTag計算得到N′，比對N′與N是否相等。

若N′=N，表明標簽計算所得隨機數rDataBase與服務器產生的隨機數rDataBase是相同的，且服務器通過驗證，然后標簽開始對讀寫器進行驗證。

若N′≠N，說明服務器是偽造的，協議停止。

其中N′=Bro(rTag,(J⊕(rTag&IDTag))&IDTag)。

（2）對讀寫器的驗證

標簽通過上述（1）中計算得到的隨機數rDataBase，結合rTag、rReader計算得到Q′，比對Q′與Q是否相等。

若Q′=Q，表明讀寫器通過驗證，接著標簽開始更新信息K=Bro(rDataBase⊕rTag⊕rReader,K)；待信息更新完成，通信實體之間的認證結束。

若Q′≠Q，說明讀寫器是偽造的，協議停止。

其中Q′=rReader&(J⊕(rTag&IDTag))&rTag。

4 協議全性分析

（1）重放攻擊

攻擊者想要發起重放攻擊需先進行竊聽以獲取上一輪通信消息，通過將竊聽所獲取再次發送給通信系統中的一方，以企圖驗證通過，從而獲取相對應的隱私信息。文中協議為抵抗攻擊者發動的重放攻擊，在所有通信消息加密過程中全部混入隨機數，使得前后兩輪通信中消息并不一致。因隨機數隨機產生，且具備不重復性，使得混入隨機數加密的通信消息前后不同，且無法預測。因此，當攻擊者重放監聽獲取上一輪消息時，當前正在進行的通信中用到的消息值早已發生變化，故攻擊者發動的重放攻擊失敗，協議能夠抵抗重放攻擊。

（2）異步攻擊

攻擊者通過某種手段使得通信系統中，其中一方通信實體加密用到的共享密鑰進行更新，而另一方通信實體加密用到的共享密鑰未進行更新或更新過程中用到的參數值不同，從而使得兩個通信實體之間共享密鑰失去一致性。文中協議為抵抗異步攻擊，在服務器端特地存放當前一輪通信過程中的共享密鑰值，且同時保存上一輪通信中用到的共享密鑰值。當服務器用當前密鑰無法驗證讀寫器或標簽之時，將會調用上一輪密鑰再次發起對標簽或讀寫器的驗證，以此方法來抵抗攻擊者發起的異步攻擊。基于上述，協議能夠抵抗異步攻擊。

（3）中間人攻擊

攻擊者通過竊聽一個會話過程，以此獲取通信消息，對獲取的消息進行刪除或篡改等操作，以發起中間人攻擊，達到通過通信實體驗證通過的目的。文中協議為抵抗該種攻擊方式，信息加密過程中引入隨機數，對于攻擊者來說并不知道每輪加密過程中用到的隨機數；且因隨機數隨機產生，具備無法預測性，因此攻擊者再不知道隨機數的前提下，想要發起中間人攻擊，就只能隨機選擇一個數作為隨機數進行消息的修改或篡改。當系統中任何一個通信實體接收到消息后，通過簡單的計算就可以識別出消息發送源是偽造的，協議立刻停止。基于上述，因此協議能夠抵抗中間人攻擊。

（4）前向安全

前向安全是指攻擊者通過某種手段獲取的當前通信中的消息，對該消息進行各種方式的分析，也無法預測出下一輪通信過程中用到的消息的值，以保證隱私信息的安全性。文中協議為確保能夠提供前向安全需求，標簽一端通過隨機數rTag來保證消息的新鮮性；讀寫器一端通過隨機數rReader來保證消息的新鮮性；服務器一端通過隨機數rDataBase來保證消息的新鮮性。隨機數每輪都是隨機產生，且具備無法預測性和不重復性，使得攻擊者根本無法預測下輪通信中加密用到的隨機數，自然使得攻擊者無法通過當前獲取的消息分析出任何有用的隱私信息。基于上述，協議能夠提供前向安全。

（5）假冒攻擊

假冒攻擊是指攻擊者偽裝成通信實體中的一方向另外的通信實體發送消息，以通過驗證，并獲取相關隱私信息。文中協議中通信實體有三個：標簽、讀寫器、服務器。對于攻擊者來說，可以偽裝成任何其中的一方發起重放攻擊，鑒于篇幅有限，此處僅選擇攻擊者偽裝成標簽發起假冒攻擊。

當攻擊者偽裝成標簽之時，向讀寫器發送消息。攻擊者要想向讀寫器發送的消息通過讀寫器的驗證，則攻擊者需要計算出正確的＜C、D、E、F＞值。但對于攻擊者來說，是不可能做到正確計算上述四個通信消息的值，原因如下：攻擊者不知曉共享密鑰K的情況，是不可能通過消息A和B計算得到正確的隨機數rReader的值；沒有正確的隨機數rReader的值，就不可能進行正確的＜C、D、E、F＞的計算。當攻擊者無法獲取隨機數rReader的值之時，攻擊者只能隨便選擇一個數充當該隨機數進行計算，由此可推測出，攻擊者計算得到的＜C、D、E、F＞的值肯定都是錯誤。當讀寫器收到消息后，進行簡單的計算，即可辨別出消息發送源是偽造的，協議停止，攻擊者未獲取任何有用的信息。因此，協議能夠抵抗假冒攻擊。

（6）雙向認證

雙向認證是一個認證協議應具備的最基本的安全要求。協議中的雙向認證包含三部分：讀寫器與標簽之間的雙向認證、讀寫器與服務器之間的雙向認證、標簽與服務器之間的雙向認證。該三部分雙向認證分析過程相類似，鑒于篇幅有限，此處選擇讀寫器與標簽之間的雙向認證為例子進行闡述。

根據上述有關于MSB協議的描述可得知：在步驟2中標簽通過A和B第一次對讀寫器進行認證；在步驟6中標簽通過Q將再一次對讀寫器進行認證。而讀寫器對標簽的認證是在步驟3中通過C和F完成的。有關于兩者之間具體的雙向認證是如何實現的，可以詳見前文中有關MSB協議的步驟闡述。基于上述，協議能夠提供通信實體之間的雙向認證。

本文協議與其他此類協議進行安全性比對，比對結果見表3所示。

5 基于GNY邏輯形式化分析

（1）協議形式化描述

雙向認證協議采用GNY邏輯形式化描述如下：

表3 協議安全性比較

消息1 T＜*[A,B,Query]；

消息2 R＜*[C,D,E,F]；

消息3 DB＜*[D,E,G,H]；

消息4 R＜*[I,J,M,N]；

消息5 T＜*[J,N,Q]。

其中，T表示標簽，R表示讀寫器，DB表示服務器。

（2）協議初始化假設

假設1 TЭ(K，rTag，IDTag)；表示標簽擁有共享密鑰K、標簽標識符IDTag、標簽產生隨機數rTag。

假設2 RЭ(K,IDReader,rReader）；表示讀寫器擁有共享密鑰K、讀寫器標識符IDReader、讀寫器產生隨機數

假設3 DBЭ(K,IDReader,rReader,rTag,rDataBase,IDTag)；表示服務器擁有共享密鑰K、讀寫器標識符IDReader、標簽標識符IDTag、讀寫器產生隨機數rReader、服務器產生隨機數rDataBase、標簽產生隨機數rTag。

假設4 R|≡#(rReader,rDataBase,rTag）；表示讀寫器相信隨機數rReader,rDataBase,rTag新鮮性。

假設5 T|≡#(rReader,rDataBase,rTag）；表示標簽相信隨機數rReader,rDataBase,rTag新鮮性。

假設6 DB|≡#(rReader,rDataBase,rTag）；表示服務器相信隨機數rReader,rDataBase,rTag新鮮性。

假設7 T|≡DB；表示標簽相信標簽、讀寫器、服務器三者之間共享密鑰K。

假設8 R|≡TDB；表示讀寫器相信標簽、讀寫器、服務器三者之間共享密鑰K。

假設9 DB|≡TDB；表示服務器相信標簽、讀寫器、服務器三者之間共享密鑰K。

假設10 T|≡D；表示標簽相信標簽、服務器之間共享的信息IDTag。

假設11 DB|≡DB；表示服務器相信標簽、服務器之間共享的信息IDTag。

假設12 R|≡DB；表示讀寫器相信讀寫器、服務器之間共享的信息IDReader。

假設13 DB|≡DB；表示服務器相信讀寫器、服務器之間共享的信息IDReader。

（3）協議證明目標

雙向認證協議需要證明的目標有五個，如下：

目標1 T|≡R|～#(A,B)；

目標2 R|≡T|～#(C,D,E,F)；

目標3 DB|≡R|～#(D,E,G,H)；

目標4 R|≡DB|～#(I,J,M,N)；

目標5 T|≡R|～#(J,N,Q)。

（4）協議證明過程

GNY邏輯包含多種運算法則，此處用T表示邏輯推理規則；用P表示告知規則；用F表示新鮮規則；用I表示擁有規則[17-18]。

上述五個證明目標的證明過程相類似，此處選擇目標Goal1為例子進行證明。鑒于篇幅有限，其他證明目標的詳細證明過程不再闡述。

∴TЭ{A,B}

∴T=#{A,B}

∴TЭ{A,B}

∴T|≡#{A,B}

∵規則I3又∵假設7：T|≡R?KT?KDB、假設8：R|≡T?KR?KDB以及消息1：T＜*【A,B,Query】

∴T|=R～{A,B}

∵新鮮性定義以及推導出來的T=#{A,B}、T|=R～{A,B,}

∴目標1：T|≡R|～#(A,B)得證明。

6 性能分析

在移動式的RFID系統中一共有三個通信實體：標簽、讀寫器、服務器。讀寫器與服務器兩者均有較大的存儲空間和較強的計算能力，而標簽并不具備上述優點，因此在性能分析時，一般選擇標簽為研究對象，從標簽一端的計算量和存儲量兩個角度進行性能分析。本文協議與其他類型協議進行性能分析結果見表4所示。

表4 協議性能比較

對表4中出現的符號進行下面的解釋說明：pa表示哈希函數的計算量；pb表示標量乘運算的計算量；pc表示偽隨機數函數的計算量；pd表示模運算的計算量；pe表示物理不可克隆函數的計算量；pf表示交叉運算的計算量；pg表示產生隨機數的計算量；ph表示位替換運算的計算量；pi表示位運算的計算量（此處的位運算是指包含與運算、異或運算等）。

在上述運算的計算量中，pa、pb、pc、pd、pe、pg屬于輕量級的計算；pf、ph、pi屬于超輕量級的計算。專家學者一般認定為一次輕量級的計算量相當于幾十次甚至上百次超輕量級的計算量；因此協議運行過程中，相對于輕量級的計算而言，超輕量級的計算次數多幾次，甚至多十幾次，對于整個系統的總體計算量影響是很小的，幾乎可忽略不計。文中協議涉及的運算包含三種：產生隨機數的計算、位替換運算，位運算；其中產生隨機數的計算有且只有一次，即輕量級的運算次數只有一次，其他運算均屬于超輕量級的計算。文中協議與其他此類協議進行計算量角度的比較：文中協議在標簽一端的計算量方面具備一定的優勢，計算總量明顯少于其他協議計算總量。

標簽一端主要用于存放標簽標識符IDTag、通信實體之間的共享密鑰K兩個參數。約定IDTag、K的長度均為l位，因此文中協議標簽一端的存儲量為2l。

7 結束語

介紹傳統RFID系統無法滿足人們需求，使得移動式RFID系統的產生，但適用于傳統RFID系統的協議無法滿足移動式RFID系統，文中為解決該問題，提出一種能夠運用在移動式RFID系統的認證協議。所提協議基于位替換運算實現對傳輸信息的加密，位替換運算可采用按位運算實現，一定程度上降低了通信實體的計算量；為保證通信消息的安全性，所有信息先加密再傳輸，同時所有信息加密過程中混入隨機數，增大攻擊者的破解難度。從不同的攻擊類型角度出發對協議進行安全性，表明協議具備較高的安全性；以標簽為對象對協議進行性能分析，表明協議能夠適用于無源標簽系統中；同時基于GNY邏輯對協議進行形式化推理證明。下一步的研究方向為將設計的協議運用在具體的移動RFID系統中，對協議運行的具體時間等參數進行統計研究分析。