超輕量級所有權轉移算法研究

謝海寶，呂 磊

(1.河南省市場監督管理局信息中心，河南 鄭州 450008； 2.河南工業大學 信息科學與工程學院，河南 鄭州 450008)

0 引 言

射頻識別技術近些年伴隨云計算、大數據、物聯網等新技術的產生而得到進一步發展[1-2]。一個經典的RFID系統至少包含電子標簽、讀卡器、數據庫三部分，電子標簽在使用過程中，電子標簽擁有者可能經常發生變化，擁有者發生變化之后，之前用戶在電子標簽里存放的隱私信息對當前用戶來說應該是無權限訪問之前用戶存放的隱私信息[3-5]。為確保標簽中隱私信息的安全，所有權轉移協議是當前的熱點研究方向。

文獻[6]中STATIO等人首次提出標簽所有權轉移協議，并在該文獻中設計一個所有權協議，協議引入可信第三方參與消息交換，具備一定安全性及一定價值意義。文獻[7]中作者針對文獻[6]的協議進行安全分析，指出該協議無法保證標簽原所有者隱私信息的安全性，同時協議因缺少存放前后兩次會話密鑰，無法抗攻擊者發起的去同步化攻擊。文獻[8]利用可信第三方設計一個協議，協議雖基于對稱加密算法對隱私信息進行加密，但文獻[9]指出文獻[8]的協議存在攻擊者可分析出下輪會話消息值可行性，即協議存在無法提供前向安全性的不足。文獻[10]利用可信第三方，同時結合哈希函數給出一個協議，但文獻[11]指出文獻[10]的協議無法保障用戶后向隱私安全性，同時加密算法的選擇使得協議推廣受到局限性。文獻[12]給出一個改進的協議，并對協議進行分析，得出協議仍無法提供去同步化攻擊安全性。文獻[13]給出的協議，雖是采用優化后的RABIN算法對信息進行加密，對優化后的RABIN算法實則還是模運算，使得計算量較大，同時文獻[13]的協議設計過程中步驟計算冗余，增加了標簽端計算量。

鑒于較多協議存在計算量大或無法提供相對應的安全需求等不足，文中給出一個超輕量級的所有權協議。先自定義設計一個創新型的加密算法，即異或交叉運算，將在下一章節給出該加密算法詳細設計過程。結合算法實現描述，可以知曉算法基于位運算實現，能夠降低計算量，使得設計協議能夠使用在計算受限制的標簽中。協議中引入標志位STATUS信息，將根據該信息量得知標簽歸屬者，具有唯一性。將文中算法與其他算法在相同環境下進行仿真實驗，仿真數據表明文中算法能夠彌補其他算法存在的安全不足之處，同時在大規模電子標簽信息交互時，文中算法在計算時間開銷角度具備較大的優勢，計算時間復雜度要少于其他算法。

1 超輕量級算法

1.1 異或交叉運算定義

異或交叉運算(exclusive or cross operation，ECO(X,Y))按如下方式實現：

(1)X、Y、Z、T都表示二進制序列，長度都為L位；

(2)Wt(X)、Wt(Y)分別表示二進制序列X、Y的漢明重量；

(3)Px、Py分別表示指向二進制序列X、Y的指針；

(4)當Wt(X)≥Wt(Y)時，對二進制序列X、Y分別同時從第一位開始遍歷，當指針Px指向二進制序列X的第i位Xi時，指針Py同時指向二進制序列Y的第i位Yi，將Xi和Yi數值進行加法運算，結果為偶數，則Xi和Yi進行異或運算，并將運算結果放置于二進制序列Z的第i位上，得到Zi；否則，將Xi放置于二進制序列Z的第i位上，得到Zi；

(5)當Wt(X)

通過兩個例子對上述異或交叉運算進行解釋。取值L=12位，X=001011100110，Y=010000100001，則可以得到Wt(X)=6、Wt(Y)=3，滿足Wt(X)≥Wt(Y)條件，按照(4)中操作所得到異或交叉運算的結果為ECO(X,Y)=Z=001011000110。具體過程見圖1。

圖1 ECO(X,Y) Wt(X)≥Wt(Y)

再次取值L=12位，X=101000000101，Y=110101011110，則可以得到Wt(X)=4、Wt(Y)=8，滿足Wt(X)

圖2 ECO(X,Y) Wt(X)

異或交叉運算破解的難度在于：其一，參與加密運算的兩個參數信息攻擊者不知曉，則無法進行后續的破解操作；其二，即便是攻擊者可以獲取部分參與加密的參數信息，但攻擊者仍無法具體獲悉兩個參數漢明重量具體數值為多少，則攻擊者不會知曉按照哪種方式進行交叉異或運算。因此，基于上述分析，新設計的異或交叉運算可以提供較好的安全需求，確保加密參數信息的安全性。同時，異或交叉運算在按照上述定義實現過程中，是基于位運算實現的，可以使得加密算法的計算量得到大幅度降低，從而使得算法可以得到超輕量級的級別，能夠適用于低成本的RFID系統標簽中。

1.2 算法符號含義

SN表示標簽新所有者；

SO表示標簽原所有者；

T表示電子標簽；

IDL表示T標識符左半邊；

IDR表示T標識符右半邊；

STATUS表示T所有權歸屬標志位，當STATUS=0時，表示所有權歸屬者為SO，當STATUS=1時，表示所有權歸屬者為SN；

a表示SO產生的隨機數；

b表示T產生的隨機數；

c表示SN產生的隨機數；

K表示SO與T之間共享密鑰；

KO表示SO與T之間當前共享密鑰；

KO1表示SO與T之間上輪共享密鑰；

KT表示SN與T之間共享密鑰；

REQ表示請求命令；

ACK表示確定命令；

⊕表示異或運算；

&表示與運算；

ECO(X,Y)表示異或交叉運算。

1.3 算法具體設計

類似其他算法[14-16]，做出如下假設規定：SN與SO之間通信安全，SN與T之間通信存在隱患，SO與T之間通信同樣存在隱患。文中超輕量級協議示意圖見圖3。

圖3 所有權轉移算法實現過程

文中設計算法具體步驟如下：

STEP 1

由SO向T發送REQ請求命令開啟所有權轉移算法。

STEP 2

T接到消息，查閱歸屬權標志位STATUS值，當前STATUS值為0，表示當前所有權歸屬于SO，因此T將IDR發送給SO以作為響應。

STEP 3

SO接到消息，在數據庫中查詢是否存在與IDR相等的值，未找到，SO對T驗證失敗，算法停止。找到，SO立刻生成隨機數a，接著分別計算會話消息A、B，最后將A、B傳送給T。

其中A=a⊕IDL、B=ECO(a,IDL)。

STEP 4

T接到消息，對A進行變形處理得到a'=A⊕IDL，將a'再結合IDL進行相同運算法則計算得到B'，再對比B'與B。B'≠B，算法停止。B'=B，表明a'=a，且T驗證SO通過，T馬上生成隨機數b，再分別計算D、E消息，最后將D、E發送給SO。

其中a'=A⊕IDL、B`=ECO(a',IDL)=ECO(A⊕IDL,IDL)、D=b⊕K、E=ECO(b,a)。

STEP 5

SO接到消息，對D進行變形處理得到b'=D⊕KO，將b'再結合KO進行相同運算法則計算得到E'，再對比E'與E。

E'≠E，則SO將用KO1替換KO再次計算得到E''，并再次對比E''與E。仍不等，算法停止；若E''=E，表明SO對T驗證通過，接著SO將向T發送ACK消息，告知T接下來可以與SN之間進行會話，同時SO向SN發送T相關信息及ACK消息，告知SN做好與T進行會話的準備。

E'=E，表明SO對T驗證通過，接著SO將向T發送ACK消息，告知T接下來可以與SN之間進行會話，同時SO向SN發送T相關信息及ACK消息，告知SN做好與T進行會話的準備。

其中b'=D⊕KO、E'=ECO(b',a)=ECO(D⊕KO,a)、E''=ECO(b',a)=ECO(D⊕KO1,a)。

算法實現過程中，可能受到外界干擾或攻擊者的蓄意破壞，使得算法中T與新舊所有者間短暫失去一致性，因此需要通過該步驟再次實現兩者間的一致性。SO首先用KO驗證，如果驗證失敗，此時有可能是會話實體兩端短暫失去一致性，則SO將立刻用KO1替換KO再次發起驗證，再次驗證通過，則就可以恢復二者之間的一致性。

STEP 6

T接到消息，T開始計算F、G消息，并向SN發送F、G。

其中F=b⊕IDL、G=ECO(b,KT)。

STEP 7

SN接到消息，對F進行變形處理得到b'=F⊕IDL，將b'再結合KT根據相同運算法則計算得到G'，再對比G'與G。G'≠G，算法停止。G'=G，表明b'=b，且SN驗證T通過，SN馬上生成隨機數c，再分別計算H、N消息，最后將H、N發送給T。

其中b'=F⊕IDL、G'=ECO(b',KT)=ECO(F⊕IDL,KT)、H=c⊕(b&IDL)、N=ECO(KT,c)。

STEP 8

T接到消息，對H進行變形處理得到c'=H⊕(b&IDL)，將c'再結合KT根據相同運算法則計算得到N'，再對比N'與N。N'≠N，算法停止。N'=N，表明c'=c，且T驗證SN通過，T將所有權歸屬標志位STATUS值由0置為1，表明T所有權發生變更，變更后T所有權歸屬者變為SN所有，最后T向SN發送ACK命令。

其中c'=H⊕(b&IDL)、N'=ECO(KT,c')=ECO(KT,(H⊕(b&IDL)))。

其中T一端的所有權歸屬標志位STATUS的值，攻擊者是無法通過物理手段修改的。當且僅當，只有通過上述方式正確通過T的驗證之后，T一端才會進行對所有權歸屬標志位STATUS的值的變動修改，從而可以保證T歸屬權的歸屬者唯一性。

STEP 9

SN接到消息，看到ACK命令，SN得知當前自己已獲取T的所有權歸屬權限。

文中算法主要的創新點或優勢在于：其一，給出一種新的信息加密方式，即異或交叉運算；其二，對于新的信息加密方式，不僅給出詳細定義及實現步驟，同時結合具體實例進行分析；其三，所有信息全部采用密文方式發送，即信息先加密再發送，使得攻擊者難以破解；其四，摒棄冗余的計算步驟，簡化算法實現步驟，提高算法效率。

2 算法安全性分析

(1)所有權唯一性。

需確保不論何時標簽所有權歸屬者必須具備唯一性，不能出現某個時刻存在有兩個或兩個以上所有權歸屬者。文中算法設計過程中引入歸屬權標志位STATUS，依據STATUS值來確定標簽當前歸屬者。攻擊者無法修改標簽端STATUS值，標簽端想修改STATUS值需通過若干輪會話驗證，而攻擊者無法通過驗證，因此算法具備所有權唯一性要求。

(2)目標標簽。

某用戶可能某個時刻擁有多個標簽的所有權限，當某標簽所有權需進行轉移時，要確保待轉移的標簽即為目標標簽。文中協議前面幾個步驟便是原所有者SO與標簽T之間的相互認證過程，當且僅當兩者相互認證都通過，才會進行T與SN之間的消息交換，從而可以確保待轉移的標簽即為目標標簽。

(3)假冒攻擊。

系統整個會話過程中，任何一個會話實體都可能被攻擊者假冒，從而發起假冒攻擊。文中算法在SN與T之間、SO與T之間進行消息交互時，先對消息來源方進行驗證，驗證失敗，算法就停止，只有驗證通過，才會進行后續操作，因此攻擊者發起的假冒攻擊肯定失敗。

(4)去同步化攻擊。

在SO與T交換消息的過程中，為抵抗攻擊者發起的去同步化攻擊，在SO端特地存放有當前以及上輪會話過程用到的共享密鑰信息。SO首先用當前密鑰發起對T的驗證，驗證通過，則進行后續操作；驗證失敗，SO在采用上輪會話密鑰再次發起對T的驗證，通過前后兩次驗證，可以抵抗攻擊者發起的去同步化攻擊。

(5)后向安全性。

攻擊者通過某種手段獲取整個會話消息，通過對獲取的消息進行分析，獲取之前某輪會話中的隱私信息，從而造成用戶隱私信息泄露。文中算法為確保攻擊者無法分析出之前會話隱私信息，加密過程中混入隨機數，隨機數前后兩次值不同，攻擊者在不知曉上輪及本輪隨機數情況下，攻擊者根本無法分析出之前加密隱私信息，因此算法具備后向安全性。

(6)前向安全性。

攻擊者通過某些手段獲取當前會話消息，企圖對獲取消息進行分析，從而預測下一次會話消息，并提前計算好下輪會話消息，通過一方認證。文中算法通過加密消息過程中混入隨機數的方式來抵抗攻擊者的攻擊，因混入隨機數，可以使得每輪會話過程中消息具備新鮮性，即每輪消息值不同，因隨機數是隨機產生，無規律性，因此攻擊者無法提前預測下輪會話消息值，從而算法具備前向安全性。

(7)窮舉攻擊。

窮舉攻擊也可以稱之為暴力破解攻擊，即攻擊者采用超級計算機對獲取的密文進行窮舉的方式窮舉出所有可能的情況，從而破解出隱私信息。窮舉攻擊需要考慮成本開銷，同時也需要考慮時間開銷，不論是成本開銷，還是時間開銷，只要其中任意一個開銷過大，則攻擊者采用窮舉攻擊就代價過大，得不償失。

文中算法一個完整通信過程被攻擊者監聽，則攻擊者可以獲取該通信過程中所有會話消息。這里選擇消息A=a⊕IDL、B=ECO(a,IDL)為例進行窮舉攻擊分析。攻擊者可以對消息A進行變形，然后帶入消息B中，可得到B=ECO(A⊕IDL,IDL)，在變形處理之后的B中，對于攻擊者來說，看似好像只有IDL一個參量信息不知曉，攻擊者以為可以窮舉出IDL的值，但攻擊者至少還有兩個參量不知曉。其中一個是IDL參量自身攜帶的漢明重量值；另一個是A⊕IDL運算結果自身攜帶的漢明重量值。攻擊者不知曉上述兩個參數值，則無法在加密過程中涉及到如何進行異或運算或交叉運算，則攻擊者窮舉失敗。

綜上，攻擊者無法窮舉出有用隱私信息，故文中算法可抵抗攻擊者發起的窮舉攻擊，確保信息的安全。

將文中算法與其他部分經典算法進行安全性對比，對比分析結果見表1。

表1 算法間安全性對比

說明：表1中，√符號表示可以抵抗該種類型的攻擊方式，×符號表示無法抵抗該種類型的攻擊方式。

3 算法性能分析

從一輪完整會話通信量、標簽端計算量對多個算法進行對比分析，見表2。

表2 算法間性能對比

針對表2中出現的符號給出下面的含義說明：Ha表示位運算(比如異或運算)的計算量大小，Hb表示異或交叉運算的計算量大小，Hc表示模運算的計算量大小，Hd表示哈希函數的計算量大小，He表示物理不可克隆函數的計算量大小，Hf表示產生隨機數的計算量大小。L表示會話消息的長度，La表示會話過程中相關命令長度(比如REQ命令等)。

文中算法一輪完整會話消息包含IDR、A、B、D、E、F、G、H、N以及SO向SN發送的內容同10L；另外還包含一個REQ命令、三個ACK命令，共計4La，因此文中算法一個完整會話的通信量為10L+4La。

標簽端計算量由來：計算a'過程中第一次用到Ha、計算消息D過程中第二次用到Ha、計算消息F過程中第三次用到Ha、計算c'過程中第四次、第五次用到Ha(其中一次是按位異或運算，另一次是按位與運算)，共計用到五次Ha運算。計算B'過程中第一次用到Hb、計算消息E過程中第二次用到Hb、計算消息G過程中第三次用到Hb、計算N'過程中第四次用到Hb，因此共計用到四次Hb運算。算法在整個過程中T需要產生一個隨機數b，因此需要用到一次Hf運算。基于上述，文中算法標簽一端總計算量為5Ha+4Hb+Hf。

從表2中可以看出，從通信量角度出發，文中算法與其他算法大致相當；從標簽端計算量角度出發，文中算法具有較大的改進，原因在于文中算法采用超輕量級自定義的加密算法，而沒有采用傳統的類似哈希函數、模運算等加密算法，同時文中算法可以彌補其他算法在安全性方面的不足。

4 算法仿真實驗

文中選擇后臺數據庫搜索特定標簽成功所花費時間指標進行性能分析。好的加密算法，除了會話實體計算量減少之外，也會帶來后臺數據庫對標簽搜索時間的降低。

進行仿真實驗相關的實驗環境如下：電腦選擇惠普筆記本、2013年9月購買、I 5處理器、內存2 GB、硬盤500 GB；以C語言作為仿真實驗過程中部分算法編程實現的語言；選擇小型數據庫MySQL用來存放仿真實驗過程中產生的相關數據；用MATLAB軟件作為仿真實驗用到的仿真平臺。

系統在一個時間段內會對多個標簽進行會話，單個標簽與系統進行會話時，標簽被搜索成功的時間長度會存在一定的差別。為減少誤差，提升仿真實驗的準確性，仿真實驗時，假定系統中共有6 000個特定標簽，依次對每組不同數量(1 000個、2 000個、3 000個、4 000個、5 000個、6 000個)的標簽進行200次搜索，記錄每一次搜索成功時間值，并求取平均值作為最終的仿真實驗結果。

將文中算法與文獻[7，12-13]中的算法在相同的仿真實驗環境下進行仿真實驗，繪制出如圖4所示的仿真結果。

圖4 特定位置標簽數量與搜索時間開銷對比

從圖4中可以看出，最開始標簽數量不多的時候，后臺數據庫搜索時間相差不大。但隨著搜索標簽數量的不斷增加，不同算法中后臺數據庫搜索標簽成功的時間都在增加，但各算法增加的趨勢并不相同。可以看出，文獻[7，13]中算法隨著標簽數量增多，搜索標簽時間幾乎成線性增長；而文獻[12]中算法搜索時間相對于上述算法搜索時間有所降低，但與文中算法的搜索時間相比，文中算法的搜索時間仍優于文獻[12]中算法的搜索時間。基于上述闡述，文中算法具備一定的推廣使用價值及意義。

5 結束語

針對存放在電子標簽中的隱私信息易泄露問題，文中設計一種超輕量級的算法。不同于其他算法，文中算法并未采用經典的哈希函數或PUF函數或偽隨機函數對信息加密，而是采用一種自己設計的異或交叉運算算法實現信息加密；異或交叉運算將基于加密信息漢明重量不同進行不同方式的交叉操作，從而提升加密算法安全性，同時該運算設計思想基于位運算實現，使得文中算法整體計算時間開銷得到一定程度的降低。通過理論及仿真實驗將文中算法與其他算法進行對比分析，表明文中算法在安全性角度優于其他算法，能夠彌補其他算法存在的安全缺陷，同時在性能上文中算法在對標簽搜索時間開銷上優于其他算法，降低了搜索時間開銷。