基于遍歷異或運算的RFID標簽所有權轉移算法

盧 愛 芬

(廣州科技職業技術大學信息工程學院 廣東 廣州 510550)

0 引 言

射頻識別技術出現在20世紀,由于當時科技等因素,未能廣泛得到運用[1]。進入21世紀后,不斷有新科技產生,諸如云計算、大數據、物聯網、區塊鏈等技術的運用,也逐漸帶動射頻識別技術再次推廣[2-3]。

一個典型的RFID系統一般包含標簽、讀卡器、服務器,其中電子標簽在其一生使用過程中,歸屬者可能經常發生變更[4-5]。一個典型的嵌有電子標簽的物品歸屬者變更例子如下:嵌有電子標簽的商品在未出廠之前,商品的歸屬者是廠商;待批發商從廠商手中購買走該批商品,商品的歸屬者由廠商變更為批發商;當零售商又從批發商手中購買走商品,則商品的歸屬者再次由批發商變更為零售商;最后消費者從零售商那里買到該商品,商品的歸屬者最終變更為消費者[6-7]。在商品歸屬者變更過程中,原來的歸屬者不能去訪問當前歸屬者存放在商品中的隱私信息,相對應的,當前歸屬者亦不能訪問原來的歸屬者存放在商品中的隱私信息,為能夠確保用戶存放在商品中隱私信息的安全,需要用到所有權轉移算法[8-9]。

文獻[10]最先給出所有權轉移概念,同時提出一個所有權轉移算法,該算法基于傳統的對稱密碼體制對信息進行加解密,同時算法中引入TTP進行相關信息的更新操作,不僅增加了通信的復雜度,而且算法存在去同步化攻擊安全隱患。文獻[11]中基于樹設計一個所有權轉移算法,具備一定安全需求,但仍無法抵抗攻擊者的跟蹤攻擊,無法推廣。文獻[12]中同樣引入可信第三方,使用TTP來掌握相關共享秘密值的更新操作,對算法分析,算法無法提供前向安全的安全需求,攻擊者可以利用前向安全分析獲取隱私信息。文獻[13]中利用哈希函數及對稱加密算法給出一個所有權轉移算法,算法除了存在計算量大問題外,算法還無法提供后向隱私信息的安全,攻擊者可以發動異步攻擊,迫使通信實體之間失去一致性。文獻[14]基于優化的Rabin加密算法設計一個所有權轉移算法,對使用的優化的Rabin加密算法分析,發現其本質就是模運算,對于計算受限制的標簽來說,模運算計算量有些超出標簽的計算能力,無法推廣。同時對算法本身進行分析,發現算法本身存在多余的計算步驟。

鑒于現有的較多經典算法存在安全不足或計算量大或無法滿足要求等缺陷,本文在結合眾多算法的基礎之上給出一種改進的所有權轉移算法。本文算法在保證安全的情況,秉著盡可能降低標簽及其他通信實體計算量的理念,引入創新型設計的遍歷異或運算實現對信息的加解密,遍歷異或運算采用位運算的方式實現,能夠將計算量提升到超輕量級的級別。同時盡量優化算法的通信過程,避免出現冗余的計算步驟。對算法從安全和計算量角度分析,算法能夠提供較好的安全需求,同時相對于原算法而言,計算量有較大幅度的降低。

1 算法設計

1.1 原算法的分析

文獻[14]基于Rabin算法給出一個標簽所有權轉移算法,算法具體步驟可以見文獻[14]中描述,此處不再贅述。對算法進行分析,該算法主要存在兩個不足之處,詳細分析如下:

1) 原算法在第五步驟中,標簽原所有者對標簽進行驗證過程中,標簽原所有者通過E和F兩個消息即可實現標簽原所有者對標簽的驗證,但算法在對E和F進行計算驗證之后,將再次對D進行驗證,完全沒有必要多此一舉。

2) 原算法在第七步驟中,標簽對標簽新所有者進行驗證過程中,標簽通過H和G兩個消息即可實現標簽對標簽新所有者的驗證,但算法在對H和G進行計算驗證之后,將再次對P進行驗證,完全沒有必要多此一舉。

基于上述兩個不足之處,還引出其他問題,問題一:整個通信過程中,標簽發送給標簽原所有者消息沒必要發送D、E、F三個,只需要發送兩個消息即可;標簽新所有者發送給標簽消息沒必要發送H、G、P三個,只需要發送兩個消息即可,使得整個通信過程中通信量增大。問題二:標簽一端因需要計算D、E、F三個消息,使得標簽的計算量增大;同時標簽對標簽新所有者的驗證也因H、G、P三個消息而增大了計算量,兩處計算極大地增加了標簽一端的計算量。

基于上述,文中改進的算法避免出現冗余的計算步驟,從而盡可能降低標簽一端的計算量;同時改進的算法采用計算量更低的遍歷異或運算實現對信息的加密,更進一步降低標簽一端的計算量。

1.2 遍歷異或運算的設計

遍歷異或運算(Ergodic XOR operation,EXO(X,Y))按照如下方式實現:

(1)X、Y、Z均表示二進制序列,長度取值均為L位。

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

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

(4) 當Wt(X)

(5) 當Wt(X)≥Wt(Y)時,對二進制序列X、Y同時從第一位開始遍歷,指針Px指向二進制序列X的第i位Xi時,指針Py指向二進制序列Y的第i位Yi,如果Yi=1,則Xi和Yi進行異或運算,并將運算結果放置于二進制序列Z的第i位上,得到Zi;如果Yi=0,則直接將二進制序列X的第i位Xi的值放置于二進制序列Z的第i位上,得到Zi。

通過下面兩個例子來說明遍歷異或運算的實現。取值L=12位,X=011000000100,Y=101011010101,則可以得到Wt(X)=3、Wt(Y)=7,滿足Wt(X)

圖1 EXO(X,Y) Wt(X)

再次取值L=12位,X=101111100101,Y=011000011000,則可以得到Wt(X)=8、Wt(Y)=4,滿足Wt(X)≥Wt(Y)條件,根據(5)中操作步驟,可得到遍歷異或運算最終結果為EXO(X,Y)=Z=110111111101。具體可以見圖2所示。

圖2 EXO(X,Y) Wt(X)≥Wt(Y)

1.3 算法符號含義

算法中涉及到的符號含義如下:

SN:標簽所有權新所有者;

SO:標簽所有權原所有者;

T:標簽;

State:標簽所有權歸屬標志位,當State=0時,表示標簽所有權當前歸屬于SO;當State=1時,表示標簽所有權當前歸屬于SN。

a:SO產生的隨機數;

b:T產生的隨機數;

c:SN產生的隨機數;

IDL:T的標識符左半部分;

IDR:T的標識符右半部分;

KO:T與SO之間的共享秘密值;

KN:T與SN之間的共享秘密值;

⊕:異或運算;

EXO(X,Y):遍歷異或運算。

1.4 算法實現

本文算法與其他算法一致[15-16],SN與SO之間通信鏈路安全,SO與T之間通信鏈路不安全,SN與T之間通信鏈路不安全。所有權轉移算法開始之前,SN存放信息有IDL、IDR、KN;SO存放信息有IDL、IDR、KO;T存放信息有IDL、IDR、KN、KO。

改進的所有權轉移算法示意圖如圖3所示。

圖3 改進的所有權轉移算法

結合圖3,本文算法具體步驟如下:

(1)SO向T發送Request命令,開啟所有權轉移過程。

(2)T收到信息,當前State=0,表明標簽所有權當前歸屬于SO所有。T將IDR發送給SO。

(3)SO收到信息,在數據庫中查找是否有與IDR相等的參數。沒有,算法結束;有,先產生隨機數a,再調用與IDR相對應的IDL的值,分別計算Ne、Nf,并將Ne、Nf發送給T。其中Ne=a⊕IDL、Nf=EXO(a,KO)。

(4)T收到信息,通過Ne計算得到隨機數a′,將a′、KO結合計算得到Nf′,比較Nf與Nf′的值。若不等,T驗證SO失敗,算法結束。若相等,表明a′=a,T產生隨機數b,分別計算Ng、Nh,并將Ng、Nh發送給SO。其中a′=Ne⊕IDL、Nf′=EXO(Ne⊕IDL,KO)、Ng=b⊕KO、Nh=EXO(b,a)。

(5)SO收到信息,通過Ng計算得到隨機數b′,將b′、a結合計算得到Nh′,比較Nh與Nh′的值。若不等,SO驗證T失敗,算法結束。若相等,表明b′=b,SO通過安全信道將信息b、IDR發送給SN。其中b′=Ng⊕KO、Nh′=EXO(Ng⊕KO,a)。

(6)SN收到信息,產生隨機數c,分別計算Ni、Nj,并將Ni、Nj發送給T。其中Ni=c⊕IDL、Nj=EXO(KN,c)。

(7)T收到信息,通過Ni計算得到隨機數c′,將c′、KN結合計算得到Nj′,比較Nj與Nj′的值。若不等,T驗證SN失敗,算法結束。若相等,表明c′=c,T計算Nk,并將Nk發送給SN。其中c′=Ni⊕IDL、Nj′=EXO(KN,Ni⊕IDL)、Nk=EXO(c,b)。

(8)SN收到信息,通過相同的運算規則計算得到Nk′,比對Nk′與Nk的值。若不等,SN驗證T失敗,算法結束。若相等,SN計算Nn,并將Nn發送給T。其中Nk′=EXO(c,b)、Nn=EXO(b,KN)。

(9)T收到信息,通過相同的運算規則計算得到Nn′,比對Nn′與Nn的值。若不等,T驗證SN失敗,算法結束。若相等,T將標志位State的值由0置換為1,表明現在標簽的所有權歸屬于SN,到此標簽的所有權轉移順利結束。其中Nn′=EXO(b,KN)。

2 算法安全性

本文算法在減少系統會話參數量之后,仍能保障信息的安全性,通過如下各不同角度對算法進行安全性分析。

(1) 所有權排他轉移。所有權排他轉移指的是算法完成之后,標簽所有權歸屬于SN,而非歸屬于SO。本文算法通過T一端的標志位State來標記標簽所有權當前歸屬于誰所有。算法沒有開始之前,State=0,表明所有權歸屬于SO,當且僅當SO、SN、T三者之間通過彼此之間的認證之后,標簽一端的標志位State的值才會發生變化,由0變為1,當State=1時,表示標簽所有權當前歸屬于SN。本文算法中,SN與T之間用到KN作為共享秘密值,SO與T之間用到KO作為共享秘密值,KN與KO的值不一樣,且SO不知曉KN的值,因此SO就無法假冒SN通過T的驗證,從而無法修改標簽一端標志位的值,因此,本文算法能夠保障所有權排他轉移安全。

(2) 目標標簽轉移。標簽所有權轉移過程中涉及到很多標簽的隱私信息,因此必須確保轉移的標簽是目標標簽,而非其他標簽。本文算法通過通信實體之間的認證來確保轉移的標簽就是目標標簽,具體的如下:SO通過算法中的步驟(3)、步驟(5)確定是目標標簽身份;SN通過算法中的步驟(8)確定是目標標簽身份。攻擊者缺少必要的認證信息,無法假冒目標標簽進行通信。因此,本文算法能夠確保轉移的標簽即為目標標簽。

(3) 定位攻擊。本文算法標簽在發送消息的時候,所有信息加密過程中含有隨機數,其中Ng和Nh中含有隨機數a和b,Nk中含有隨機數c和b,使得每次通信過程中Ng、Nh、Nk的值都是不同的。當攻擊者截獲上述消息時,攻擊者也無法定位標簽的位置。因此,本文算法可以確保標簽的位置安全。

(4) 暴力攻擊。攻擊者對截獲的消息進行窮舉的方式進行破解,該種攻擊方式可稱之為暴力攻擊。攻擊者通過監聽一個完整的消息交換過程,可以獲取IDR、Ne、Nf、Ng、Nh、Ni、Nj、Nk、Nn信息,攻擊者可以根據竊聽的消息對其中任何一個或幾個發起暴力攻擊。選擇Ne、Nf為例進行分析,其他消息暴力攻擊分析方式相一致,不再闡述。

首先攻擊者獲取的Ne、Nf是加密之后的密文,設定攻擊者知曉Ne、Nf加密的運算法則,即攻擊者知曉Ne是由SO產生的隨機數a與IDL進行異或運算所得。攻擊者可對Ne進行變形,變形之后得到a′=Ne⊕IDL。接著攻擊者再將變形之后得到的數據代入Nf中,可得到Nf′ =EXO(a′,KO) =EXO(Ne⊕IDL,KO)。在整個變形或計算過程中,涉及到的參數有a、IDL、KO,其中a可由Ne和IDL變形得到,因此在最后變形得到的Nf′中實則有IDL、KO兩個參數值攻擊者不知曉。再結合本文遍歷異或運算加密算法的定義可知,攻擊者同時也不知道Ne⊕IDL、KO漢明重量值,因此,于攻擊者而言,有四個參數值不知道,故攻擊者對消息Ne、Nf發起的暴力攻擊是失敗的。

(5) 假冒攻擊。會話系統中共有三個會話實體,攻擊者可假冒其中任何一個實體與其他實體進行會話。此處選擇攻擊者假冒成電子標簽與標簽所有權原歸屬者、新所有者進行消息交換進行分析。

當攻擊者假冒成電子標簽與標簽所有權原歸屬者進行會話時,攻擊者想要通過SO的驗證,則攻擊者必須獲取合法的IDR值。當然攻擊者可以竊聽上輪會話獲取該消息值,可以通過SO的第一次驗證;當攻擊者通過SO的第一次驗證之后,SO會進行一系列操作之后向攻擊者發送合法的Ne、Nf消息,但SO收到后無法正確地解密得到SO產生的隨機數a。當攻擊者無法解密得到正確的a時,攻擊者只能隨機選擇一個數值充當a,進行后續的加密操作得到錯誤的消息Ng、Nh。當SO再次收到攻擊者發送來的消息,并對攻擊者再次驗證時,攻擊者是無法通過SO的第二次驗證的。原因在于:攻擊者并不知曉IDL的值,因此無法解密出正確的a,就無法用正確的a加密得到正確的消息Ng、Nh值?；谏鲜?攻擊者假冒電子標簽向SO發起假冒攻擊以失敗告終。

當攻擊者假冒成電子標簽與標簽所有權新歸屬者進行會話時,攻擊者想要通過SN的驗證,則攻擊者必須計算得到正確的Nk消息(攻擊者當然可以通過竊聽的方式獲取正在會話的Nk消息,并在下一輪會話時偽裝成標簽向SN發送該消息,但攻擊者是無法成功的,具體原因可見下面一點的有關“重放攻擊”的分析。)。既然攻擊者無法通過竊聽在重放方式通過SN的驗證,那攻擊者只能先破解計算正確Nk消息所需要的隨機數c的值。攻擊者無法通過竊聽的消息中破解出SN產生的隨機數c的值,同時攻擊者也根本無法得到真正電子標簽隨機產生的隨機數b的值,因此攻擊者根本無法計算得到正確的Nk值。攻擊者只能隨機選擇兩個數作為上述參數的值進行計算,當SN收到消息只需進行簡單計算,即可驗證攻擊者假冒。基于上述,攻擊者假冒電子標簽向SN發起假冒攻擊以失敗告終。

(6) 重放攻擊。攻擊者通過竊聽當前會話完整過程,可以獲取該輪會話的所有消息,然后在下次會話過程中,攻擊者假冒其中一個實體向其他實體發送截獲上輪消息,以企圖通過其他實體的驗證,進而進行獲取隱私信息,該種攻擊方式可稱之為重放攻擊。抵抗重放攻擊最為常用的方法便是在每輪消息加密過程中都混入隨機數。通過加密消息過程中混入隨機數方法抵抗攻擊者發起的重放攻擊原因有如下:其一,隨機數一般由隨機數產生器隨機產生,所得到隨機數具有隨機性,使得攻擊者根本無法預測下輪會話加密用到隨機數的值;其二,隨機數產生器得到的隨機數還具備互異性,即不會產生重復的隨機數,這樣使得前后每輪會話加密時混入的隨機數一定不同,則每輪會話加密得到的同一個消息數值每次也不同。本文協議所有攻擊者竊聽獲取的消息在加密時都混入隨機數,因此,基于上述,本文算法能夠抵抗攻擊者發起的重放攻擊。

將本文算法同文獻[11-14]中算法進行相同環境下仿真實驗。選擇某個時間段內,上述不同算法面對攻擊者發起的來自不同角度網絡攻擊進行仿真實驗,因此選取的時間節點為1 000秒、2 000秒、3 000秒、4 000秒、5 000秒、6 000秒、7 000秒、8 000秒、9 000秒、10 000秒;并在每個時間節點進行仿真實驗時,為提高仿真實驗數據準確性,每個時間節點進行仿真實驗次數不低于500次,同時記錄這500次仿真實驗數據,最后求取這500次實驗數據的平均值作為最終的仿真實驗結果,如圖4所示。

圖4 不同算法間網絡攻擊成功次數對比

從圖4中可以分析得到,相對于文獻[11-13]中算法而言,文獻[14]中算法及本文算法面對相同仿真環境時,攻擊者發起的網絡攻擊成功次數得到大幅度的減少,表明本文算法及文獻[14]中算法安全性提高很多。但同時也可以看出,本文算法在每個時間節點統計的仿真實驗數據均少于文獻[14]中算法數據,表明本文算法具備比文獻[14]中算法更好的安全性能。

3 算法性能

原所有者和新所有者包含讀卡器及服務器具備強大的計算能力和存儲空間,因此僅選擇標簽為對象進行性能角度分析。本文算法與其他經典算法之間性能比較如表1所示。

表1 算法之間性能對比

表1中各符號含義如下,QPUF表示物理不可克隆函數的計算量,QW表示按位運算的計算量(按位運算常見的有按位異或運算、按位與運算等),QHASH表示哈希函數的計算量,QEK、QDK、QFT都表示變形或改進后的哈希函數的計算量,QL表示左移運算的計算量,QR表示右移運算的計算量,QRABIN表示優化之后的Rabin算法的計算量,QEXO表示遍歷異或運算的計算量。L表示算法通信過程中每個消息的長度均為L長度,S表示算法通信過程中類似于Request命名指令占用長度。

在上述運算中,屬于超輕量級運算的有按位運算、遍歷異域運算、左移運算、右移運算,其他都不屬于超輕量級運算。相對于超輕量級運算來說,其他運算的計算量遠遠多于超輕量級運算的計算量。上述比較的文獻中,除了本文算法用到的運算均屬于超輕量級,其他文獻中的算法或多或少均使用到非超輕量級的運算,因此從標簽一端的計算量角度出發,本文算法在計算量方面有較大程度上的減少。整個算法的通信過程中通信量大小與其他文獻中的算法通信量相當,但本文算法能夠彌補其他算法存在的安全缺陷,仍具備一定的優勢,有一定的推廣價值。

4 結 語

針對原算法存在計算多余缺陷,設計出一個改進的所有權轉移算法。改進的算法在減少計算的同時亦能保證會話的安全性;本文算法并未沿用原算法中Rabin算法對信息加密,而是采用自創的遍歷異或運算算法對信息加密,能夠一定程度上減少系統整體的計算量;對算法本身進行分析,可以提供用戶的安全需求;本文算法通過標簽端標志位State值來顯示當前標簽所有權歸屬,只有通過嚴格的認證之后,標志位值才會發生變更,確保了所有權的唯一性。對本文算法進行安全和計算量角度的比對分析,本文算法在減少計算量和通信量的情況,能夠提供較好的安全性,滿足當前RFID系統對安全和計算量的要求。