莫 釗，韋永壯

?

簡化輪LBlock的密鑰中比特檢測及分析

莫 釗，韋永壯

(桂林電子科技大學(xué)廣西信息科學(xué)實驗中心，廣西 桂林 541004)

LBlock密碼算法是近來提出的一類輕量級分組加密算法。利用LBlock算法的結(jié)構(gòu)特點，結(jié)合立方檢測的基本思想，設(shè)計2個密鑰中比特捕獲算法，對LBlock算法輸出所涉及的密鑰比特個數(shù)情況進行分析。9輪簡化LBlock的每個輸出比特全部卷入所有的主密鑰比特信息，在18維立方變元下，11輪簡化LBlock的輸出累加中每個比特全部卷入所有的主密鑰比特信息。上述2輪簡化LBlock均不存在密鑰中比特。研究結(jié)果表明，全輪LBlock密碼算法具有穩(wěn)固的密鑰信息擴散及混淆性，足以抵抗經(jīng)典立方攻擊。

輕量級密碼；分組密碼；密鑰中比特；立方測試；盒；LBlock密碼

1 概述

射頻識別(Radio Frequency Identification, RFID)[1]技術(shù)與無線傳感器網(wǎng)絡(luò)[2]的資源(包括計算和處理能力、能量資源、存儲空間和通信帶寬等)非常有限，大大限制了各種傳統(tǒng)密碼算法的使用。如何確保射頻識別無線傳感器網(wǎng)絡(luò)的安全可靠性成為業(yè)界的瓶頸問題。在構(gòu)建安全的射頻識別和無線傳感器網(wǎng)絡(luò)中，輕量級的密碼技術(shù)[3](即在確保算法足夠安全性的前提下，功耗、計算及存儲資源等開銷較少、實現(xiàn)速度輕便的密碼)成為當前研究的熱點。輕量級分組密碼具有算法加解密速度快、容易標準化、便于軟硬件實現(xiàn)等優(yōu)點。目前，輕量級分組密碼在RFID安全和無線傳感器網(wǎng)絡(luò)中發(fā)揮著重要的作用。

近幾年出現(xiàn)一系列輕量分組密碼算法，如：TEA[4]，KTANTAN[5]，HIGHT[6]，MIBS[7]，mCrypton[8]等。特別值得關(guān)注的是，在2011年國內(nèi)學(xué)者提出了一種新的輕量級分組密碼LBlock(魯班鎖)[9]。LBlock的分組長度為64比特，密鑰長度為80比特(共有32輪)。由于其結(jié)構(gòu)簡潔、緊湊，在軟、硬件環(huán)境中高效實現(xiàn)，特別適合受限環(huán)境下使用等優(yōu)點，因此受到業(yè)內(nèi)廣泛的關(guān)注。

文獻[10]通過分析LBlock密鑰編排存在的缺陷，以時間復(fù)雜度為270和數(shù)據(jù)復(fù)雜度為247的明文對，給出第22輪LBlock相關(guān)密鑰不可能差分攻擊。文獻[11]從設(shè)計者算法評估分析結(jié)果中，將LBlock攻擊輪數(shù)提高至第21輪和 第22輪，攻擊的復(fù)雜度分別可達269.5及279.28。文獻[12]對第16輪LBlock構(gòu)建一種相關(guān)密鑰的飛去來器差分攻擊。其次，基于上面第16輪相關(guān)密鑰的截斷差分，對第22輪LBlock實施密鑰恢復(fù)攻擊，與之前其他人的攻擊結(jié)果對比，數(shù)據(jù)復(fù)雜度和計算復(fù)雜度均有提高。文獻[13]以262.5選擇明文對的數(shù)據(jù)復(fù)雜度和273.7的時間復(fù)雜度，對第21輪LBlock加密進行了不可能差分攻擊。文獻[14]基于矩陣分析的方法，得到第14輪LBlock區(qū)分器，并提出了第22輪LBlock的零相關(guān)線性攻擊。攻擊的數(shù)據(jù)復(fù)雜度和時間復(fù)雜度分別可達262.1和271.27。文獻[15]分析了LBlock算法的安全強度，指出基于2種獨立密鑰差分路徑的Biclique分析，結(jié)合不完全匹配和預(yù)計算技術(shù)，對全輪(32輪)LBlock進行密鑰恢復(fù)攻擊。攻擊的數(shù)據(jù)復(fù)雜度不超過252個選擇明文，還有時間復(fù)雜度是278.4左右。文獻[16]對LBlock進行了側(cè)信道立方攻擊。結(jié)果顯示，結(jié)合第3輪LBlock比特輸出的密鑰擴散分析，在單比特泄露模型下通過捕獲第3輪的第44個狀態(tài)比特，以210.7時間復(fù)雜度和27.6個選擇明文，至少可以恢復(fù)14個比特密鑰。而在漢明重量泄露模型下，以誤差允許概率為5.52%，數(shù)據(jù)復(fù)雜度為230和28.5個選擇明文，得到第32輪LBlock的80比特密鑰。

上述的攻擊方法大都是從LBlock算法的“整體結(jié)構(gòu)”來研究算法的安全性(盡管文獻[17]研究了低輪LBlock算法的代數(shù)次數(shù))，如何從算法“局部”把握算法的安全性，如算法局部密鑰信息擴散及混淆性程度(如密鑰中比特)問題等亟待解決。

另一方面，由于立方攻擊實現(xiàn)的條件比較簡潔，且應(yīng)用范圍廣泛，對多種密碼的分析(如Trivium[18-19]、Grain- 128[20]、MD6[18]、Hitag2[21]等)取得良好的效果。特別地，Hitag2是一種應(yīng)用于遠程控制小車門鎖的輕量級密碼；文獻[22]對Hitag2實施了立方攻擊。實驗結(jié)果表明，在PC機上僅需1 min便可完全破解Hitag2。可見立方攻擊對輕量級流密碼可產(chǎn)生實際威脅。那么一個重要的問題是：新型的輕量級分組密碼算法LBlock是否足以抵抗立方攻擊，這仍有待深入研究。

本文基于LBlock算法的結(jié)構(gòu)特點，結(jié)合立方檢測(Cube testers)[18]的基本思想，設(shè)計2個密鑰中比特捕獲算法。算法1檢測了2輪~9輪簡化LBlock算法的密鑰信息擴散及混淆性。算法2檢測了在18維立方變元下，2輪~11輪簡化LBlock算法的密鑰信息擴散及混淆性，并進一步分析了LBlock算法抵抗立方測試攻擊的能力。

2 立方測試的基本思想

例假設(shè)6個比特的輸入加密函數(shù)：

立方密鑰中比特檢測算法步驟如下：

第1步

第2步

(3)最終輸出所有的密鑰中比特。

如果密碼算法存在密鑰中比特，則說明此密鑰比特并沒有對密文輸出產(chǎn)生任何影響，因而其密鑰信息擴散性并不好。根據(jù)密碼算法擴散原則，即算法的每個明文比特和密鑰比特都要對密文產(chǎn)生影響。密鑰中比特檢測的目的就是分析密文輸出中所涉及的密鑰比特個數(shù)，以便檢驗和評判密鑰信息在算法內(nèi)部狀態(tài)中擴散的程度。

3 LBlock的算法描述

圖1 LBlock加密流程

(1)LBlock的數(shù)據(jù)處理過程如下：

(2)輪函數(shù)的執(zhí)行過程：

：(2)64→(2)64

其中，代表輪函數(shù)的輸出；和分別表示混淆函數(shù)和擴散函數(shù)，后面給出和的定義。

(3)混淆函數(shù)的定義：

混淆函數(shù)的輸入輸出均為32比特?；煜瘮?shù)代表輪函數(shù)的非線性層，由8個盒01234567并行組成。每個盒的輸入輸出均為4個比特。其中，LBlock 的8個盒的數(shù)據(jù)如表1所示。

表1 LBlock的S盒

：(2)32→(2)32

=7‖6‖5‖4‖3‖2‖1‖0→

=7‖6‖5‖4‖3‖2‖1‖0

(4)擴散函數(shù)的定義：

:(2)32→(2)32

=7‖6‖5‖4‖3‖2‖1‖0→

=7‖6‖5‖4‖3‖2‖1‖0

, , ,

由于篇幅有限，密鑰編排可參見文獻[9]。

4 S盒的布爾函數(shù)表達式

5 2輪~9輪LBlock的密鑰中比特檢測

性質(zhì)1 簡化LBlock算法至少需要迭代9輪，才足以保證其輸出位涉入全部密鑰比特。

第3步最終輸出所有的密鑰中比特。

在配置為Intel Core i7-2600 3.40 GHz，4 GB DDR3的PC機上，利用軟件Visual C++ 6.0進行C語言編程測試(后面進行的測試以同樣的配置)。

通過搜索發(fā)現(xiàn)：

第2、3輪LBlock的第1個輸出位其中比特、布爾表達式及最高代數(shù)次數(shù)如下：

第2輪：

中比特：022,2759,6479

中比特個數(shù)：72

代數(shù)表達式：2425266123252425236123622461256023632462246325636061606260636163626323606223616224606225606124616225606225606325616360626325606263

最高代數(shù)次數(shù)：4

第3輪：

中比特：030,3555,6063,6873,78,79

中比特個數(shù)：64

最高代數(shù)次數(shù)：6

代數(shù)表達式：(在此省略)。

第4輪~第9輪LBlock的第1個輸出位其中特如下：

第4輪：

中比特：0,1,626,3134,3942,5267,7679

中比特個數(shù)：51

第5輪：

中比特：25,1013,2338,4751,5759,7275

中比特個數(shù)：36

第6輪：

中比特：09,1822,28,29,30,4346,64

中比特個數(shù)：23

第7輪：

中比特：011415161735

中比特個數(shù)：7

第8輪：

中比特：6

中比特個數(shù)：1

第9輪：

中比特：無

中比特個數(shù)：0

從以上結(jié)果看出：LBlock第2、3輪輸出表達式所涉及的密鑰分別只有8個和16個；類似地，同樣發(fā)現(xiàn)其他輸出位存在類似的結(jié)果(密鑰中比特檢測失敗概率為2–30)。

6 8輪~11輪LBlock的立方密鑰中比特檢測

性質(zhì)2 在18維立方變元測試下，簡化LBlock算法至少需要迭代11輪，才能保證其輸出位涉入全部密鑰比特。

最終輸出所有的密鑰中比特。

對LBlock算法輸出第13位進行檢測結(jié)果如下：

第8輪：

中比特：0~79

中比特個數(shù)：80

第9輪：

中比特：78,79

中比特個數(shù)：2

第10輪：

中比特：28

中比特個數(shù)：1

第11輪：

中比特：沒有

中比特個數(shù)：0

類似地，改變立方變元位置和函數(shù)輸出位置，對LBlock進行立方中比特檢測，結(jié)果見表2。

由表2看出：LBlock第8輪~第10輪輸出表達式中 (第13位)仍存在中比特。在18個立方變元下LBlock至少需要迭代11輪，才足以保證其第13個輸出位涉入全部密鑰比特。類似地，把立方變元提高到23個比特時，多次的測試結(jié)果仍表明11輪變換下不存在密鑰中比特，并且這些密鑰信息是以非線性形式存在的，包括測試其他輸出比特(密鑰中比特檢測失敗概率為2–30)。

表2 立方中比特的檢測

注意到，全輪LBlock采用32次輪函數(shù)迭代，因此，該算法具有穩(wěn)固的密鑰信息擴散及混淆性以抵抗立方密鑰中比特測試。

7 結(jié)束語

分組密碼輸出位的密鑰中比特數(shù)量是度量算法安全強度的一個重要參數(shù)。若某一輸出位含有多個密鑰中比特信息，則被認為算法的擴散及混淆程度不足。本文利用立方測試基本思想，結(jié)合密鑰中比特算法，檢測了LBlock加密算法輸出位密鑰比特的分布情況。2種測試結(jié)果表明，全輪 (32輪)LBlock算法具有理想的密鑰信息擴散及混淆性。下一步將通過密鑰中比特檢測技術(shù)減小具體攻擊中的時間復(fù)雜度。

[1] Finkenzeller K. RFID Handbook: Fundamentals and Applica- tions in Contactless Smart Cards and Identifiaction[M]. Chichester, UK: John Wiley, 2003.

[2] Akyildiz I F, Su Weilian, Sankarasubramaniam Y, et al. A Survey on Sensor Networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114.

[3] Bogdanov A, Knudsen L R, Leander G, et al. Present: An Ultra-lightweight Block Cipher[C]//Proceedings of the 9th Inter- national Workshop on Cryptographic Hardware and Embedded Systems. Berlin, Germany: Springer-Verlag, 2007: 450-466.

[4] Wheeler D, Needham R. A Tiny Encryption Algorithm[C]// Proceedings of the 2nd International Workshop on Fast Software Encryption. Berlin, Germany: Springer-Verlag, 1994: 363- 366.

[5] Cannière C D, Dunkelman O, Kne?evi? M. KATAN and KTANTAN——A Family of Small and Efficient Hardware- oriented Block Ciphers[C]//Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems.Berlin, Germany: Springer-Verlag, 2009: 272-288.

[6] Hong D, Sung J, Hong S, et al. HIGHT: A New Block Cipher Suitable for Low-resource Device[C]//Proceedings of the 8th International Workshop on Cryptographic Hardware and Embedded Systems. Berlin, Germany: Springer-Verlag, 2006: 46-59.

[7] Izadi M, Sadeghiyan B, Sadeghian S, et al. MIBS: A New Lightweight Block Cipher[C]//Proceedings of the 8th International Conference on Cryptology and Network Security. Berlin, Germany: Springer-Verlag, 2009: 334-348.

[8] Lim C, Korkish O. MCrypton——A Lightweight Block Cipher for Security of Low-cost RFID Tags and Sensors[C]// Proceedings of the 6th International Workshop on Information Security Applications. Berlin, Germany: Springer-Verlag, 2005: 243-258.

[9] Wu Wenling, Zhang Lei. LBlock: A Lightweight Block Ci- pher[C]//Proceedings of the 9th International Conference on Applied Cryptography and Network Security. Berlin, Germany: Springer-Verlag, 2011: 327-344.

[10] Minier M, Naya-Plasencia M. A Related Key Impossible Differential Attack Against 22 Rounds of the Lightweight Block Cipher LBlock[J]. Elsevier Information Processing Letters, 2012, 112(1): 624-629.

[11] KarakocF, Demirci H, Harmanc?A E. Impossible Differential Cryptanalysis of Reduced-round LBlock[C]//Proceedings of the 6th IFIP WG11.2 International Workshop on Information Security Theory and Practice. Berlin, Germany: Springer-Verlag, 2012: 179-188.

[12] Liu Shusheng, Gong Zheng, Wang Libin. Improved Related Key Differential Attacks on Reduced-round LBlock[C]//Proceedings of the 14th International Conference on Information and Communications Security. Berlin, Germany: Springer-Verlag, 2012: 58-69.

[13] Liu Ya, Gu Dawu, Liu Zhiqiang, et al. Impossible Differential Attacks on Reduced-round LBlock[C]//Proceedings of the 8th International Conference on Information Security Practice and Experience. Berlin, Germany: Springer-Verlag, 2012: 97-108.

[14] SoleimanyH, Nyberg K. Zero-correlation Linear Cryptan- alaysis of Reduced-round LBlock[DB/OL]. (2012-10-05). http://eprint.i-acr. org/2012/570.pdf.

[15] Wang Yanfeng, Wu Wenling, Yu Xiaoli, et al. Security on LBlock Against Biclique Cryptanalysis[C]//Proceedings. of the 13th International Workshop on Information Security Applications. Berlin, Germany: Springer-Verlag, 2012: 1-14.

[16]Li Zhenqi, Zhang Bin, Yao Yuan, et al. Cube Cryptanalysis of LBlock with Noisy Leakage[C]//Proceedings of the 15th International Conference on Information Securityand Cryptology. Berlin, Germany: Springer-Verlag, 2012: 141-155.

[17] 彭昌勇, 祝躍飛, 顧純祥, 等. 1~5輪LBlock 的多項式表示及完全性分析[J]. 計算機工程, 2012, 38(9): 155-157, 179.

[18] AumassonJ P, Dinur I, Meier W, et al. Cube Testers and Key Recovery Attacks on Reduced-round MD6 and Trivium[C]// Proceedings of the 16th International Workshop on Fast Software Encryption. Berlin, Germany: Springer-Verlag, 2012: 1-22.

[19] Piotr M, Janusz S. The Cube Attackon Stream Cipher Trivium and Quadraticity Tests[EB/OL]. (2011-01-18). http://eprint.iacr. org/2011/032.pdf.

[20] AumassonJ P, Dinur I, Meier W, et al. Efficient FPGA Implements of High-dimensional Cube Testers on the Stream Cipher Grain-128[C]//Proceedings of IACR’09. [S. 1.]: IEEE Press, 2009: 218-230.

[21]Wiener I. Hitag2 Specification, Reference Implementation and Test Vectors[EB/OL]. (2011-05-13). http://cryptolib.com/cip hers/hitag2.

[22] Sun Siwei, Hu Lei, Xie Yonghong, et al. Cube Crypt-analysis of Hitag2 Stream Cipher[C]//Proceedings of the 10thInternational Conference on Cryptology and Network Security. Berlin, Germany: Springer-Verlag, 2011: 15-25.

[23] DinurI, Shamir A. Cube Attacks on Tweakable Black Box Polynomials[C]//Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer-Verlag, 2009: 278- 299.

[24] DinurI, Shamir A. Applying Cube Attacks to Stream Ciphers in Realistic Scenarios[J]. Cryptography and Communications, 2012, 4(3/4): 217-232.

[25] Dinur, Shamir A. Side Channel Cube Attacks on Block Ciphers[DB/OL]. (2009-05-18). http://eprint.iacr.org/2009/127. pdf.

編輯 索書志

Detection and Analysis of Key Neutral-bit for Reduced Round LBlock

MO Zhao, WEI Yong-zhuang

(Guangxi Experiment Center of Information Science, Guilin University of Electronic Technology, Guilin 541004, China)

Recently, LBlock as a new lightweight block cipher is presented. By using both the structure of LBlock algorithm and the basic idea from the cube test, two neutral-bit detection algorithms are proposed. It is shown that all master key bits are involved in the each output of 9-round reduced LBlock cipher. Moreover, for given 18 cube variables, there still is nonexistence of key neutral-bit for 11-round reduced LBlock cipher. Research result shows that the full-round LBlock cipher has good key bits confusion against the classical cube attacks.

lightweight cipher; block cipher; key neutral-bit; cube test;box; LBlock cipher

1000-3428(2014)03-0028-05

A

TP309

國家自然科學(xué)基金資助項目(61100185)；廣西自然科學(xué)基金青年基金資助項目(2011GXNSFB018071)；廣西無線寬帶通信與信號處理重點實驗室(桂林電子科技大學(xué))主任基金資助項目(11101)。

莫 釗(1987－)，男，碩士研究生，主研方向：分組密碼分析；韋永壯，教授、博士。

2013-06-05

2013-08-02 E-mail：cw277346909@126.com

10.3969/j.issn.1000-3428.2014.03.006