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

莫 釗，韋永壯

?

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

莫 釗，韋永壯

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

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

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

1 概述

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

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

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

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

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

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

2 立方測試的基本思想

例假設6個比特的輸入加密函數：

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

第1步

第2步

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

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

3 LBlock的算法描述

圖1 LBlock加密流程

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

(2)輪函數的執行過程：

：(2)64→(2)64

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

(3)混淆函數的定義：

混淆函數的輸入輸出均為32比特。混淆函數代表輪函數的非線性層，由8個盒01234567并行組成。每個盒的輸入輸出均為4個比特。其中，LBlock 的8個盒的數據如表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)擴散函數的定義：

:(2)32→(2)32

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

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

, , ,

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

4 S盒的布爾函數表達式

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

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

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

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

通過搜索發現：

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

第2輪：

中比特：022,2759,6479

中比特個數：72

代數表達式：2425266123252425236123622461256023632462246325636061606260636163626323606223616224606225606124616225606225606325616360626325606263

最高代數次數：4

第3輪：

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

中比特個數：64

最高代數次數：6

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

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

第4輪：

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

中比特個數：51

第5輪：

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

中比特個數：36

第6輪：

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

中比特個數：23

第7輪：

中比特：011415161735

中比特個數：7

第8輪：

中比特：6

中比特個數：1

第9輪：

中比特：無

中比特個數：0

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

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

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

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

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

第8輪：

中比特：0~79

中比特個數：80

第9輪：

中比特：78,79

中比特個數：2

第10輪：

中比特：28

中比特個數：1

第11輪：

中比特：沒有

中比特個數：0

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

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

表2 立方中比特的檢測

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

7 結束語

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

[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

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

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

2013-06-05

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

10.3969/j.issn.1000-3428.2014.03.006