于鈞合 侯文瑞 徐銘澤

（1.海軍陸戰(zhàn)學(xué)院 廣州 510430）（2.海軍參謀部 北京 100841）（3.海軍工程大學(xué)理學(xué)院 武漢 430033）

適用于RFID的輕量級(jí)算法的實(shí)現(xiàn)和評(píng)估?

于鈞合1侯文瑞2徐銘澤3

（1.海軍陸戰(zhàn)學(xué)院 廣州 510430）（2.海軍參謀部 北京 100841）（3.海軍工程大學(xué)理學(xué)院 武漢 430033）

隨著RFID技術(shù)的快速發(fā)展，其安全問(wèn)題也越來(lái)越嚴(yán)峻，論文結(jié)合RFID系統(tǒng)的特點(diǎn)，對(duì)在其中應(yīng)用較為廣泛的HIGHT、KLEIN、TEA和KATAN算法進(jìn)行了分析和比較研究。首先，對(duì)這些算法的匯編代碼進(jìn)行了分析，確定相關(guān)操作和指令集的耗時(shí)情況。隨后，在AVR單片機(jī)上執(zhí)行這些算法，從能量消耗、擴(kuò)散和混亂程度等方面對(duì)算法的安全性進(jìn)行了比較研究。最后，將所有結(jié)果進(jìn)行對(duì)比，指出代碼分析結(jié)果和算法實(shí)際實(shí)現(xiàn)結(jié)果之間的不同。論文的研究成果既揭示了各算法之間的不同的性能又表明算法的實(shí)現(xiàn)結(jié)果和代碼分析結(jié)果存在較大的差異。

RFID；輕量級(jí)算法；仿真

1 引言

RFID（Radio Frequency Identificatio）技術(shù)作為目前最熱門的技術(shù)之一，在我們的生活中得到了廣泛的應(yīng)用［1］。RFID系統(tǒng)最大的優(yōu)點(diǎn)就是實(shí)現(xiàn)成本比其它技術(shù)低很多，但該系統(tǒng)的隱私和安全問(wèn)題也一直困擾著相關(guān)領(lǐng)域的研究人員，其中最主要的原因就是RFID這樣的設(shè)備沒(méi)有足夠的硬件資源用來(lái)完成復(fù)雜的計(jì)算。

RFID是一種在不進(jìn)行直接接觸就能對(duì)物體進(jìn)行識(shí)別的技術(shù)，它主要由三個(gè)部分組成：標(biāo)簽、讀寫器和后端處理系統(tǒng)。讀寫器是RFID的重要組成部分，它的功能是為標(biāo)簽提供向外發(fā)送信息的能量，同時(shí)對(duì)標(biāo)簽的信息進(jìn)行收集并傳送至后端系統(tǒng)處理［2］。

RFID系統(tǒng)很容易受到各種各樣的攻擊，包括主動(dòng)攻擊和被動(dòng)攻擊［3］。在RFID系統(tǒng)中有兩種防御機(jī)制：基于主機(jī)的防御機(jī)制和集中防御機(jī)制。由于在無(wú)線網(wǎng)絡(luò)中進(jìn)行識(shí)別，RFID系統(tǒng)的標(biāo)簽和讀寫器始終處于不安全的環(huán)境之中，并且隨著系統(tǒng)安全性的加強(qiáng)也會(huì)出現(xiàn)不同的威脅對(duì)其進(jìn)行破解。隨著大量的輕量級(jí)算法被分布出來(lái)，RFID系統(tǒng)的安全性有了進(jìn)一步的提升。在電子標(biāo)簽中用不同的加密算法對(duì)信息進(jìn)行加密會(huì)降低用戶隱私被竊取的風(fēng)險(xiǎn)，但是又由于標(biāo)簽自身的限制，并不是的所有的算法都適用于任何一種標(biāo)簽，本文選取幾個(gè)常用的輕量級(jí)算法從代碼和實(shí)現(xiàn)結(jié)果等不同角度進(jìn)行比較，并對(duì)比較結(jié)果進(jìn)行歸納總結(jié)。

2 相關(guān)算法簡(jiǎn)介

2.1 KLEIN算法

KLEIN算法在2011年被提出，使用的是SPN（Substitution-permutation Network）結(jié)構(gòu)。KLEIN算法的密鑰長(zhǎng)度有64、80和96位，算法根據(jù)密鑰長(zhǎng)度的不同有12、16和20輪迭代，在進(jìn)行加解密時(shí)，主要采用面向字節(jié)的處理方式，在非線性結(jié)構(gòu)中，使用了4bit并具有自反特性的S盒［4］。在擴(kuò)散過(guò)程中，KLEIN算法的設(shè)計(jì)者將AES算法中的MixColumns函數(shù)通過(guò)改進(jìn)變形成為MixNibbles函數(shù)，并與RotateNibbles函數(shù)相結(jié)合，使得函數(shù)在軟硬件實(shí)現(xiàn)中效率都有所提升。算法通過(guò)密鑰擴(kuò)展過(guò)程得到一系列的輪密鑰，這個(gè)過(guò)程采用了Feistel結(jié)構(gòu)，主要有移位、異或等運(yùn)算，圖1展示了KLEIN-64算法的一次密鑰擴(kuò)展過(guò)程。

圖1 一次密鑰擴(kuò)展過(guò)程

2.2 KATAN算法

KATAN算法有三種類型：KATAN32，KATAN48和KATAN64，所有的類型都使用80bit的密鑰［5］。本文選取KATAN-48進(jìn)行研究。KATAN32的明密文的分組長(zhǎng)度最短，只有32bits，該算法的結(jié)構(gòu)與流密碼相似，如圖2所示。算法共有254輪，每輪使用的非線性變換定義如下：

其中，IR是一個(gè)254位的數(shù)組，ka、kb都是子密鑰。

圖2 KATAN算法結(jié)構(gòu)

2.3 HIGHT算法

HIGHT算法的分組長(zhǎng)度為64bit，使用的密鑰為128bit，經(jīng)過(guò)32輪計(jì)算。算法的主密鑰有16個(gè)字節(jié)：MK=(MK15，MK14，…，MK0)，算法的加密過(guò)程如圖3所示，WK和SK分別是白化密鑰和子密鑰 ，明 文 用 P=(P7，P6，…，P0) 表 示 ，密 文 用C=(C7，C6，…，C0)表示［6］。

圖3 HIGHT算法加密流程

2.4 TEA算法

TEA算法采用了Feistel結(jié)構(gòu)，包含的主要運(yùn)算方式是模加，異或和移位［7］。該算法的分組長(zhǎng)度為 64bit，密鑰長(zhǎng)度為 128bit，運(yùn)用了香農(nóng)的擴(kuò)散和混淆原則，提高了P盒和S盒的安全性。算法的結(jié)構(gòu)如圖4所示，算法通過(guò)交叉使用模加和異或來(lái)保證非線性。

圖4 TEA算法結(jié)構(gòu)

3 算法的代碼分析及比較

3.1 算法的時(shí)鐘周期數(shù)

算法的時(shí)鐘周期數(shù)根據(jù)算法代碼中各組件需要執(zhí)行的指令類型及次數(shù)計(jì)算出來(lái)，分析結(jié)果如圖5所示。

圖5 算法的時(shí)鐘周期數(shù)

圖5 展示了各算法加密和解密的時(shí)鐘周期數(shù)，總的周期數(shù)通過(guò)加解密周期數(shù)相加再減去重復(fù)的部分得到。由圖中可以看出，HIGHT算法所用的周期數(shù)最少，表明此算法各組件的指令較少或每個(gè)指令使用的平均周期數(shù)最少，同時(shí)，與其它幾個(gè)算法相比只有HIGHT算法的加密的時(shí)鐘周期比解密的多，雖然實(shí)際運(yùn)行的結(jié)果與代碼分析有差異，但通過(guò)這樣的分析有助于寫出更高效的代碼。KLEIN算法占用的時(shí)鐘周期最多，因?yàn)榕c其它3個(gè)算法相比，KLEIN是唯一一個(gè)使用SPN結(jié)構(gòu)的算法，在輪函數(shù)中的 MixColumns、RotateNibbles和SubNibbles步驟都需要較多的指令來(lái)完成運(yùn)算。

對(duì)算法各組件指令周期的分析有助于對(duì)算法的實(shí)現(xiàn)性能進(jìn)行改進(jìn)，所以很有必要在算法實(shí)現(xiàn)前對(duì)各指令的耗時(shí)情況進(jìn)行比較分析，從而根據(jù)實(shí)現(xiàn)平臺(tái)的不同特性選取具有更高效率的運(yùn)行方式，提高算法效率。

3.2 代碼行數(shù)的比較分析

另外一種分析代碼的方式是比較代碼的長(zhǎng)度來(lái)確定算法的復(fù)雜程度。對(duì)代碼行數(shù)進(jìn)行分析的結(jié)果也可以從一定程度上反應(yīng)出算法的性能，從而更加有效地指導(dǎo)編寫者對(duì)代碼做出改進(jìn)，提升算法性能。圖6展示了各算法代碼行數(shù)的分析比較結(jié)果。

從圖中可以看出，KLEIN算法的代碼行數(shù)最多，說(shuō)明該算法比其它算法有更多的執(zhí)行步驟。HIGHT算法的代碼行數(shù)最少，這也是在代碼分析中HIGHT占用時(shí)鐘周期最少的原因。

圖6 各算法代碼行數(shù)

造成KLEIN算法的代碼長(zhǎng)度最長(zhǎng)的原因主要有兩個(gè)。首先KLEIN使用的是SPN網(wǎng)絡(luò)結(jié)構(gòu)，SPN結(jié)構(gòu)的加密和解密過(guò)程與Feistel結(jié)構(gòu)不同，這種結(jié)構(gòu)運(yùn)行起來(lái)的代碼行數(shù)普遍較多。另一個(gè)原因是KLEIN算法的主要步驟中包含AddRoundKey，RotateNibbles，MixNibbles和 SbuNibbles，每個(gè)函數(shù)都需要單獨(dú)的代碼，因此增加了代碼的行數(shù)。HIGHT算法代碼行數(shù)最少的原因是算法的結(jié)構(gòu)，F(xiàn)eistel結(jié)構(gòu)減少了代碼的行數(shù)，另外，HIGHT算法的數(shù)學(xué)運(yùn)算過(guò)程也進(jìn)行了簡(jiǎn)化，執(zhí)行過(guò)程中的加減、異或、移位等步驟比其它較復(fù)雜的函數(shù)運(yùn)行起來(lái)更簡(jiǎn)單，也大大減少了代碼長(zhǎng)度。

4 算法硬件平臺(tái)實(shí)現(xiàn)的性能對(duì)比評(píng)估

在對(duì)算法的實(shí)現(xiàn)性能進(jìn)行對(duì)比研究中，本文的源代碼以Thomas Eisenbarth［8］等人所做的相關(guān)研究為基礎(chǔ)，對(duì)各算法在AVR單片機(jī)上進(jìn)行實(shí)現(xiàn)，并整理了相關(guān)參數(shù)進(jìn)行后續(xù)的對(duì)比分析，主要的對(duì)比項(xiàng)目有內(nèi)存占用，時(shí)鐘效率和能量消耗。

4.1 內(nèi)存占用分析

圖7展示了各算法實(shí)現(xiàn)后內(nèi)存占用的百分比。

圖7 各算法內(nèi)存占用百分比

圖中百分比的計(jì)算以單片機(jī)上SRAM和可編程Flash空間的大小為基礎(chǔ)。從圖中反映出的數(shù)據(jù)可以看出KATAN算法的SRAM和Flash的內(nèi)存占用都比其它算法少，KLEIN算法占用了最多的Flash空間，因?yàn)橛缮瞎?jié)的分析可得該算法的代碼長(zhǎng)度最長(zhǎng)，但SRAM的占用百分比與其它算法比起來(lái)就相對(duì)較少。

基于以上數(shù)據(jù)對(duì)比，KATAN算法更適用于對(duì)內(nèi)存占用要求限制較高的設(shè)備，HIGHT和TEA算法的SRAM占用百分比相同，主要原因是這兩個(gè)算法的密鑰長(zhǎng)度（128bit）和分組長(zhǎng)度（64bit）都相同，同理KLEIN和KATAN算法的SRAM占用量也相同，兩種算法的密鑰長(zhǎng)度和分組長(zhǎng)度分別是80bit和64bit，又由于HIGHT和TEA的密鑰長(zhǎng)度比KLEIN和KATAN的密鑰長(zhǎng)度長(zhǎng)，所以SRAM的占用量更高。Flash空間的占用量取決于匯編代碼的大小，KLEIN算法代碼的長(zhǎng)度決定了占用的Flash空間最多，KATAN算法占用最少的Flash空間也是由于代碼的長(zhǎng)度最短。

4.2 CPU時(shí)鐘周期消耗分析

通過(guò)在AVR單片上各個(gè)算法來(lái)獲取參數(shù)，對(duì)加密和密鑰擴(kuò)展過(guò)程的耗費(fèi)的時(shí)鐘周期時(shí)行比對(duì)，結(jié)果如表1所示。

表1 各算法占用的CPU時(shí)鐘周期

由表中數(shù)據(jù)可以看出，KLEIN算法占用的時(shí)鐘周期最少，KATAN算法占用的時(shí)鐘周期最多。

4.3 能量消耗分析

為了計(jì)算各算法執(zhí)行過(guò)程中的能量消耗，假設(shè)每個(gè)CPU時(shí)鐘周期的能量消耗不變，利用以下公式進(jìn)行計(jì)算：

其中，I是消耗的平均電流值，VCC是系統(tǒng)電源電壓，τ是每個(gè)時(shí)鐘周期的時(shí)間，N是時(shí)鐘周期數(shù)［9］。計(jì)算結(jié)果如圖8所示。

圖中能量單位為微焦耳，由圖中對(duì)比可以看出，KATAN算法消耗了最多的能量，并且與其它算法相比，能量值高出很多。KLEIN算法雖然代碼長(zhǎng)度最長(zhǎng)，但卻是消耗能量最少的算法。由此可以得出，相比于代碼長(zhǎng)度，耗費(fèi)的CPU時(shí)鐘周期對(duì)能量消耗值的影響更加顯著，或者可以說(shuō)算法實(shí)現(xiàn)過(guò)程中所體現(xiàn)出來(lái)的性能更多地依賴于算法采用的結(jié)構(gòu)，循環(huán)次數(shù)以及運(yùn)行的時(shí)鐘周期數(shù)。例如，同一個(gè)算法采用不同的迭代輪數(shù)，最終的能量消耗也不同。

算法各組件實(shí)現(xiàn)的指令也是一個(gè)很重要的度量標(biāo)準(zhǔn)。每一個(gè)指令運(yùn)行的時(shí)鐘周期都不同，為了有效降低算法的能量消耗，在編寫代碼時(shí)選取最適合本算法的指令運(yùn)行方式非常重要。同時(shí)，算法的運(yùn)行結(jié)構(gòu)也不能忽視，因?yàn)椴煌慕Y(jié)構(gòu)占用的時(shí)鐘周期也有較大的差異，例如Feistel和SPN網(wǎng)絡(luò)結(jié)構(gòu)就存在很大的不同，這些不同將直接對(duì)算法的主循環(huán)次數(shù)產(chǎn)生影響。

5 算法安全性分析

本節(jié)用擴(kuò)散和混亂的程度對(duì)算法的安全性進(jìn)行分析，針對(duì)分組密碼體制，可以通過(guò)統(tǒng)計(jì)非線性擴(kuò)散程度來(lái)對(duì)算法的擴(kuò)散和混亂程度做出一個(gè)概率上的估計(jì)，通過(guò)兩種程度的對(duì)比對(duì)算法的安全性進(jìn)行分析［10］。

5.1 擴(kuò)散程度

擴(kuò)散程度是對(duì)算法安全性進(jìn)行分析時(shí)的一個(gè)重要因素，為了得到更加可靠的分析結(jié)果，本文使用一串隨機(jī)的明文，其它的明文全部由此明文得到。首先保持其它比特位不變，對(duì)明文的前20比特逐個(gè)進(jìn)行單比特改變，也就是每個(gè)加密的明文與初始明文相比只改變了一個(gè)比特位，每一步輸出的密文進(jìn)行異或運(yùn)算，最終構(gòu)造出一個(gè)20×64的矩陣，對(duì)矩陣中“1”的個(gè)數(shù)所占百分比進(jìn)行計(jì)算，結(jié)果如表2所示。

表2 各算法擴(kuò)散程度測(cè)試

5.2 混亂程度

混亂特性可以讓明文和密文間的統(tǒng)計(jì)關(guān)系變得復(fù)雜，從而增加算法破譯的難度。對(duì)混亂程度進(jìn)行測(cè)試時(shí)，輸入的明文長(zhǎng)度為64bits。首先確定一個(gè)初始密鑰，隨后使用的密鑰都由初始密鑰變化得到。每一次加密都只改變初始密鑰的一個(gè)比特位，對(duì)每一輪加密的輸出進(jìn)行異或運(yùn)算，最后對(duì)所有輸出統(tǒng)計(jì)結(jié)果中“1”的個(gè)數(shù)所占百分比進(jìn)行計(jì)算，如表3所示。

表3 各算法的混亂程度測(cè)試

算法的結(jié)構(gòu)是影響算法安全性的一個(gè)重要因素，從以上擴(kuò)散和混亂特性中的分析可以得出，KLEIN算法的擴(kuò)散程度最低，而混亂程度最高。由前文的介紹中可知，KLEIN算法采用的是SPN網(wǎng)絡(luò)結(jié)構(gòu)，而其它三種算法都采用的是Feistel結(jié)構(gòu)，結(jié)構(gòu)的不同導(dǎo)致了KLEIN算法在擴(kuò)散和混亂特性上的不同。

6 結(jié)語(yǔ)

從以上的研究中可以得出，算法的代碼分析所得出的結(jié)果與算法實(shí)現(xiàn)后的結(jié)果有一定的差異，并不是代碼最簡(jiǎn)單的性能最好，算法在實(shí)現(xiàn)過(guò)程中所表現(xiàn)出來(lái)的性能更多是受算法的結(jié)構(gòu)，循環(huán)的次數(shù)以及各指令函數(shù)的復(fù)雜程度的影響，僅僅靠對(duì)代碼進(jìn)行分析是不能對(duì)算法的實(shí)際性能做出正確評(píng)估的。但兩者之間又是相互聯(lián)系，相互制約的，算法所表現(xiàn)的不同性能都可以通過(guò)代碼之間的比對(duì)找到解釋的方法，例如，從以上的對(duì)比中可以得出算法代碼中各組件的指令函數(shù)是影響算法性能的一個(gè)重要因素，所以，結(jié)合算法實(shí)際性能對(duì)比所得出的結(jié)果又可以對(duì)算法的代碼進(jìn)行改進(jìn)，選用更合適的函數(shù)完成相同的指令，從而使代碼更加地合理完善。

［1］Kardas S，Celik S，Yildiz M，et al.PUF-enhanced offline RFID security and privacy［J］.Journal of Network and Computer Application，2012，35：2059-2067.

［2］黃玉蘭.基于物聯(lián)網(wǎng)的RFID電子標(biāo)簽研究進(jìn)展［J］.電訊技術(shù)，2013，53（4）：522-529.HUANG Yulan.Research progress of RFID tag based on Internet of things［J］.Telecommunication Engineering，2013，53（4）：522-529.

［3］周世杰，張文清，羅嘉慶.射頻識(shí)別（RFID）隱私保護(hù)技術(shù)綜述［J］.軟件學(xué)報(bào)，2015，26（4）：960-976.ZHOU Shijie，ZHANG Wenqing，LUO Jiaqing.Review of radio frequency identification（RFID）privacy protection technology［J］.Journal of software，2015，26（4）：960-976.

［4］李浪，劉波濤，鄒祎，等.KLEIN加密算法優(yōu)化研究［J］.計(jì)算機(jī)應(yīng)用研究，2015，32（3）：877-880.LI Lang，LIU Botao，ZOU Yi，et al.Research on Optimization of KLEIN encryption algorithm［J］.Computer Application Research，2015，32（3）：877-880.

［5］劉愛(ài)森.KATAN算法相關(guān)密鑰的條件差分分析［D］.濟(jì)南：山東大學(xué)，2014：34-50.LIU Aisen.Conditional difference analysis of KATAN algorithm related key［D］.Jinan：Shandong University，2014：34-50.

［6］郭建勝，崔競(jìng)一，潘志舒，等.HIGHT算法的積分攻擊［J］.通信學(xué)報(bào)，2016，37（7）：71-78.GUO Jiansheng，CUI Jingyi，PAN Zhishu，et al.Integral attack of HIGHT algorithm［J］.Journal of communication，2016，37（7）：71-78.

［7］李繼中.密碼算法識(shí)別與分析關(guān)鍵技術(shù)研究［D］.鄭州：解放軍信息工程大學(xué)，2014：20-25.LI Jizhong.Research on Key Technologies of identification and analysis of cryptographic algorithms［D］.Zhengzhou：ThePLA Information EngineeringUniversity，2014：20-25.

［8］Eisenbarth T，Gong Z，Tim G，et al.Compact Implementation and Performance Evaluation of Block Ciphers in ATtiny Devices［C］//Progress in Cryptology-AFRICACRYPT 2012.Springer Berlin Heidelberg，2012：172-187.

［9］Roy D，Datta P，Mukhopadhyay S.A New Variant of Algebraic Attack［J］.Communications in Computer and Information Science，2014，420：211-222.

［10］ Bogdanov A， Rechberger C. A 3-Subset Meet-in-the-Middle Attack：Cryptanalysis of the Lightweight Block Cipher KTANTAN［C］//In：Biryukov A，GONG Guang，Stinson D R.LNCS 6544：Selected Areas in Cryptography，Berlin：Springer Berlin Heidelberg，2011：229-240.

Implementation and Evaluation of Lightweight Algorithms for RFID

YU Junhe1HOU Wenrui2XU Mingze3
（1.Naval Marine Academy，Guangzhou 510430）（2.Naval Staff，Beijing 100841）（3.College of Science，Naval University of Engineering，Wuhan 430033）

With the rapid development of RFID technology，the security problem is becoming more and more serious.In this paper，combined with the characteristics of RFID system，the HIGHT，KLEIN，TEA and KATAN algorithms which are widely used in RFID are analyzed and compared.Firstly，the assembly code of these algorithms is analyzed，and the time consuming of related operation and instruction set is determined.Subsequently，these algorithms are implemented on AVR MCU，and the security of the algorithm is compared with the aspects of energy consumption，diffusion and confusion.Finally，all the results are compared，and the difference between the code analysis results and the actual implementation results is pointed out.The research results of this paper not only reveal the different performance of the algorithm，but also show that the results of the algorithm and the results of the code analysis are quite different.

RFID，lightweight algorithm，simulation

TP301

10.3969/j.issn.1672-9722.2017.11.008

Class Number TP301

2017年5月8日，

2017年6月24日

于鈞合，男，碩士研究生，助理工程師，研究方向：信息安全。侯文瑞，男，助理工程師，研究方向：網(wǎng)絡(luò)安全。徐銘澤，男，研究方向：信息安全。