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

于鈞合 侯文瑞 徐銘澤

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

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

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

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

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

RFID；輕量級算法；仿真

1 引言

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

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

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

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

2.1 KLEIN算法

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

圖1 一次密鑰擴展過程

2.2 KATAN算法

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

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

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

2.3 HIGHT算法

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

圖3 HIGHT算法加密流程

2.4 TEA算法

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

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

3 算法的代碼分析及比較

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

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

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

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

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

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

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

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

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

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

4 算法硬件平臺實現(xiàn)的性能對比評估

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

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

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

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

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

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

4.2 CPU時鐘周期消耗分析

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

表1 各算法占用的CPU時鐘周期

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

4.3 能量消耗分析

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

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

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

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

5 算法安全性分析

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

5.1 擴散程度

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

表2 各算法擴散程度測試

5.2 混亂程度

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

表3 各算法的混亂程度測試

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

6 結(jié)語

從以上的研究中可以得出，算法的代碼分析所得出的結(jié)果與算法實現(xiàn)后的結(jié)果有一定的差異，并不是代碼最簡單的性能最好，算法在實現(xiàn)過程中所表現(xiàn)出來的性能更多是受算法的結(jié)構(gòu)，循環(huán)的次數(shù)以及各指令函數(shù)的復(fù)雜程度的影響，僅僅靠對代碼進(jìn)行分析是不能對算法的實際性能做出正確評估的。但兩者之間又是相互聯(lián)系，相互制約的，算法所表現(xiàn)的不同性能都可以通過代碼之間的比對找到解釋的方法，例如，從以上的對比中可以得出算法代碼中各組件的指令函數(shù)是影響算法性能的一個重要因素，所以，結(jié)合算法實際性能對比所得出的結(jié)果又可以對算法的代碼進(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］周世杰，張文清，羅嘉慶.射頻識別（RFID）隱私保護(hù)技術(shù)綜述［J］.軟件學(xué)報，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］.計算機應(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］劉愛森.KATAN算法相關(guān)密鑰的條件差分分析［D］.濟南：山東大學(xué)，2014：34-50.LIU Aisen.Conditional difference analysis of KATAN algorithm related key［D］.Jinan：Shandong University，2014：34-50.

［6］郭建勝，崔競一，潘志舒，等.HIGHT算法的積分攻擊［J］.通信學(xué)報，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］李繼中.密碼算法識別與分析關(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ò)安全。徐銘澤，男，研究方向：信息安全。