HIGHT算法的積分攻擊

郭建勝，崔競一，潘志舒，劉翼鵬

(1. 解放軍信息工程大學三院，河南 鄭州 450001；2. 信息保障技術重點實驗室，北京 100072；3. 西安衛星測控中心，陜西 西安 710043)

HIGHT算法的積分攻擊

郭建勝1,2，崔競一1，潘志舒3，劉翼鵬1

(1. 解放軍信息工程大學三院，河南 鄭州 450001；2. 信息保障技術重點實驗室，北京 100072；3. 西安衛星測控中心，陜西 西安 710043)

對輕量級分組密碼算法 HIGHT在積分攻擊方法下的安全性進行了研究。首先糾正了現有研究成果在構造區分器時的不當之處，重新構造了HIGHT算法的11輪積分區分器，并構造了相應高階積分擴展下的17輪區分器；其次利用所構造的17輪區分器，結合“時空折中”原理對25輪HIGHT算法進行了積分攻擊；最后對攻擊算法的復雜度進行了分析，攻擊算法需要的數據復雜度為262.92，時間復雜度為266.20，空間復雜度為2119。分析結果表明，所給出的攻擊算法的攻擊輪數和時間復雜度要優于現有研究結果。

密碼分析；分組密碼；積分攻擊；HIGHT算法

1 引言

HIGHT算法是由Hong等[1]在CHES 2006上提出的輕量級分組密碼，其采用一種廣義Feistel結構，輪函數輸入和輸出均為8 bit，規模很小，且沒有用S盒，只使用循環移位、異或和模加操作，在8位處理器的環境中表現出很好的效率。子密鑰是在加密過程中通過密鑰擴展算法得到的，密鑰寄存器只需要存儲128 bit的主密鑰。

針對 HIGHT的分析方面，最初由設計者給出了 HIGHT算法的差分分析、線性分析、截段差分分析、不可能差分分析、積分分析等結果[1]。其積分分析構造了 12輪的積分區分器，并對 16輪HIGHT算法進行了攻擊。2009年，文獻[2]指出了算法設計者在構造積分區分器時的錯誤，利用高階積分擴展構造了 17輪的積分區分器，并利用密鑰擴展算法攻擊了22輪HIGHT算法。在ICISC 2010上，Koo等[3]在相關密鑰條件下給出了全輪HIGHT算法的攻擊結果。在單密鑰條件下，Hong等[4]在ICISC 2011上利用Biclique攻擊給出了全輪HIGHT算法的攻擊結果，但其時間復雜度較高。Chen等[5]在2012年非洲密碼年會上提出了HIGHT算法不可能差分分析的相關結論。在 2015年，由 Igarashi等[6]提出了對19輪HIGHT算法的中間相遇攻擊結果。同時，HIGHT算法也有在故障分析下安全性的相關研究成果[7,8]。

本文對 HIGHT算法在積分攻擊下的安全性進行了研究。首先，對文獻[2]所構造的積分區分器進行了分析，指出了文獻[2]在構造區分器時的不當之處，重新構造了HIGHT算法的11輪積分區分器，并構造了相應高階積分擴展下的 17輪區分器；然后，根據高階積分擴展構造的 17輪區分器，攻擊了25輪HIGHT算法。其中，根據“時空折中”的原理，利用存儲空間分擔了部分計算時間，降低了整個攻擊算法的計算復雜度。攻擊25輪HIGHT算法的數據復雜度、時間復雜度和空間復雜度分別為262.92、266.20和2119。攻擊輪數和時間復雜度都要優于文獻[2]與文獻[11]的結果。

2 相關知識

2.1 HIGHT算法結構簡介

HIGHT算法采用了具有8分支的廣義 Feistel結構。其分組長度為64 bit，密鑰長度為128 bit，加密輪數為32輪。每一輪包含2個不同的F函數(F ：{0,1}8→{0,1}8， F ：{0,1}8→ {0,1}8)、異或

0

1運算⊕、模28加運算以及內部位置變換。其F函數為： F0( x) =x <<<1 ⊕ x <<<2 ⊕ x<<<7，F1( x) = x <<< 3 ⊕ x <<< 4 ⊕ x<<< 6。設64 bit明文為經過32輪算法后變換成64 bit密文具體結構如圖1所示。

HIGHT算法具體加密流程如下。

圖1 HIGHT算法加密流程

1) 初始白化密鑰加變換

2) 輪變換

(Xi?1,7,Xi?1,6,Xi?1,5,Xi?1,4,Xi?1,3,Xi?1,2,Xi?1,1,Xi?1,0)為第i輪的輸入，其中， i= 1,2,… ,31，則輸出為

(X31,7,X31,6,X31,5,X31,4,X31,3,X31,2,X31,1,X31,0)為第32輪的輸入，則對應的輸出為

3) 結尾白化密鑰加變換

HIGHT算法的密鑰擴展算法由兩部分組成。第一部分是常數生成部分，利用線性反饋移位寄存器生成128個7 bit常數δ0,δ1… ,δ127；第二部分為白化密鑰和子密鑰生成部分，通過主密鑰MK與第一部分生成的常數生成白化密鑰和子密鑰。首先將主密鑰MK化分為16 byte，即 MK =(M K15,M K14,… ,M K0)。

白化密鑰生成部分： wki= MKi+12(i = 0,1,2,3)，wki= MKi?4(i = 4,5,6,7)。

2.2 積分攻擊

積分攻擊是Knudsen等[9]總結提出的一種分組密碼選擇明文攻擊方法，自提出以來，其得到了越來越廣泛的關注，該攻擊方法被應用于許多算法的安全性分析中，例如 AES[10]、LBlock[11]、E2[12]和MIBS[13]等。

積分攻擊就是選擇特定形式的明文進行加密，再對所得密文求和（積分），通過積分值的不隨機性將密碼算法與隨機置換區分開。在構造積分區分器時，需要定義一些符號。

定義1[9,14]一些特殊形式的集合

1) 活躍集：若對任意的0 ≤ i

iji i2n集，記為A。

2) 穩定集：若對任意的0

i 0i i2n記為C。

0 ≤ i≤ 2n?1}是平衡集，記為B。

此外，記不能確定是否平衡的集合為U。這些集合之間的運算遵循一些基本原則。性質1[9,14]不同集合之間滿足如下性質。1) 集合 A通過雙射（如密鑰加）后，仍是集合A；集合C通過雙射后，仍是集合C。

2) 2個集合A的異或和不一定為集合A，但一定是集合B；集合A與集合C的異或和仍是集合A；2個集合B的異或和仍為集合B。

3) 集合B通過非線性雙射（如模28加），將無法確定其平衡性。

本文討論的 HIGHT算法以字節為操作單位，即將定義1中的n取8。

由于HIGHT算法涉及到模28加運算，有必要對不同形式集合間的模28加運算原則進行歸納，由性質1的3)進一步得到性質2。

性質2 不同集合類型的字節之間進行模28加運算遵循以下性質。

1)集合A與集合C的模28加和仍是集合A；集合B與集合C的模28加和仍是集合B。

2)集合B與集合A的模28加和無法確定其平衡性，但其最低比特仍保持平衡，記為 uuuuuuub；2個B集合的模28加和無法確定其平衡性，但其最低比特仍保持平衡，記為uuuuuuub。

證明 2個集合間的模28加運算結果：最低比特為2個集合最低比特之間進行異或加運算所得，其余比特為2個集合對應比特之間進行異或加運算再加上低比特的進位所得。由于集合B與集合A最低比特均為平衡比特，所以根據性質1的2) 可得，集合B與集合A進行模28加運算后，最低比特仍保持平衡，其余比特由于涉及到低比特的進位，平衡性不能確定。同理可得2個集合B的模28加運算的結果。

證畢

3 HIGHT算法17輪積分區分器的構造

文獻[2]給出了 HIGHT算法的 11輪積分區分器，在構造過程中，認為集合A經過F函數仍為集合A，根據性質1的2）可知，集合A經過F函數后應為集合B，據此，本文重新構造HIGHT算法的11輪積分區分器（定理1），所得結果與文獻[2]仍相同。如圖2所示。

定理1 （11輪積分區分器） 選擇28個明文，滿足條件：7P遍歷所有 28個取值，即為集合均為固定值，即為集合C。則經過11輪HIGHT算法后，則輸出的X11,3最低比特仍保持平衡。

圖2 HIGHT算法的11輪積分區分器

進一步，文獻[2]將 11輪區分器向前做高階積分擴展，得到17輪積分區分器（定理2）。如圖3所示。

定理2 （17輪積分區分器）選擇256個明文，滿足條件： P7, P6, P5, P4, P3,P2, P1分別遍歷所有 28個取值，P0為固定值，即為集合C。則經過17輪HIGHT后，輸出的X17,3最低比特仍保持平衡。

圖3 17輪積分區分器

4 對25輪HIGHT算法的積分攻擊

文獻[2]在17輪積分區分器的基礎上攻擊了22輪 HIGHT算法，本文利用“時空折中”的原理降低攻擊的計算復雜度，實現對25輪HIGHT算法的積分攻擊。選取構造 17輪區分器時需要的明文，得到25輪加密的密文，通過猜測相關密鑰，從25輪加密的結果恢復出第 17輪的結果，驗證其中X17,3的最低比特是否平衡。

4.1 積分攻擊流程

記字節X的最低比特為(0)X 。根據算法加密流程，攻擊算法如下。

算法1 25輪HIGHT算法積分攻擊

步驟1 選擇構造17輪積分區分器時的明文（256個），進行25輪加密得到256個密文。

步驟2 猜測結尾密鑰 wk7,w k6, w k5, wk4，對256個密文解密，計算第 25輪的輸出： X25,7=C7，

步驟3 猜測第25輪子密鑰 sk99,s k96,s k97,sk98，用步驟2的結果解密第25輪，得到256個第24輪部分輸出步驟 4 猜測第 24輪子密鑰 sk95,s k92,sk93和sk(0)，用步驟3的結果解密第24輪，得到256個第

94

步驟5 猜測第23輪子密鑰 sk91,s k88,sk89，用步驟4的結果解密第23輪，得到256個第22輪部分輸出

步驟6 猜測第22輪子密鑰 sk84, sk85， sk8(7

0)，用步驟5的結果解密第22輪，得到256個第21輪部 分輸 出其中， F0( X22,7)(0)表示 F0( X22,7)的最低比特。

步驟7 猜測第21輪子密鑰 sk80, sk81，用步驟6的結果解密第21輪，得到256個第20輪部分輸出：

步驟8 猜測第20輪子密鑰sk77， sk7(60)，用步驟7的結果解密第20輪，得到256個第19輪部分輸出：表示 F1( X20,5)的最低比特。

步驟9 猜測第19輪子密鑰sk73，用步驟8的結果解密第19輪，得到256個第18輪部分輸出：

(70,)3是否為平衡比特，若是，則所猜測的密鑰為候選密鑰，否則為錯誤密鑰，刪除。

步驟11 選擇另一組構造17輪區分器時的明文，重復步驟1～步驟10，直至密鑰唯一確定。

攻擊流程如圖4所示。

4.2 積分攻擊算法的分析

對算法1進行分析，利用存儲空間分擔算法的計算時間：單獨計算算法中每一步驟的時間復雜度，存儲每一步的計算結果，在下一步計算中調用上一步存儲的結果，最后將每一步的時間復雜度相加得到整個算法的時間復雜度。得到定理3。

定理3 利用算法1對25輪HIGHT算法進行積分攻擊，攻擊的數據復雜度為262.92，時間復雜度為266.20，空間復雜度為2119。

證明 算法 1需要猜測 8 bit密鑰 wk7, wk6,wk5, w k4,s k73,s k77,s k80,s k81,s k84,s k85,s k88,sk89,sk91,sk92,s k93,s k95,s k96,s k97,s k98,sk99和1 bit密鑰 sk6(90),sk(0),s k(0),sk(0)。根據密鑰擴展算法，這些密鑰由某

76 87 94些主密鑰生成，如表1所示。

根據算法1及表1可知，攻擊過程中需要先后 猜 測 wk7, w k6, w k5, wk4； sk99, sk98； sk95,sk92,sk, sk(0)；sk ,s k ,sk ；sk；sk的前 7 bit，sk，

9394918889847773共120 bit密鑰。對于正確密鑰，一定能保證為平衡比特；對于錯誤密鑰，其使平衡的概率為，所以經過一組明密文淘汰后，剩余錯誤密鑰數目為為了唯一確定正確密鑰，需要121組明文，從而攻擊的數據復雜度為121組( 256× 121 ≈ 262.92個明文)。

圖4 25輪HIGHT算法的積分攻擊

攻擊的時間復雜度按如下方法估計：對第一組明文，步驟1需要256次25輪加密，步驟2需要猜測 wk7, w k6, w k5, wk4共32 bit密鑰，共232個可能值，在密鑰固定的情況下，結尾密鑰模28加運算只依賴于C4和C0，取值最多216種（相同的不重復計算），最多需 232× 216× 2 = 249次模28加運算，步驟3需要猜測 sk99, sk98共16 bit密鑰，216個可能值，在密鑰固定的情況下，模28加運算依賴于 F0( X25,5),X24,4,共48 bit，最多248個可能值，最多需 216× 248× 4 = 266次模28加運算，步驟4需要猜測 sk95,s k92,s k93,sk9(40)共25 bit密鑰，共225個可能值，在密鑰固定的情況下，模28加運算依賴于共32 bit，最多232個可能值，最多需要 225× 232×3 = 258.58次模28加運算，同理，步驟 5需要猜測 sk91s k88,sk89共24 bit密鑰，最多需要 224× 232× 3 = 257.58次模28加運算，步驟 6需要猜測sk84這 8 bit密鑰，最多需28× 224× 2 = 233次模28加運算，步驟7需要猜測0 bit密鑰，最多需 224×2=225次模28加運算，步驟8需要猜測sk77的前7 bit密鑰，最多需 27×28=215次模28加運算，步驟9需要猜測sk73這8 bit密鑰，最多需 28×28=216次模28加運算，步驟10計算量可忽略不計，由于25輪算法一共有4× 25 + 4 =104次模28加運算，因此，在忽略其他運算所耗時間的情況下，模28加運算轉換為25輪加密操作，相當于次25輪加密；處理完第一組明文后，錯誤密鑰還剩2119個（大于232），同理處理第二組明文最多需259.45次

25輪加密；只要候選密鑰剩余個數不小于232，處理每組明文均最多需259.45次25輪加密，因此當處理完89組明文后，剩余候選密鑰231個，處理第90組最多需次25輪加密；處理完90組明文后，剩余候選密鑰230個，處理第91組最多仍需259.45次25輪加密；類似地，處理后30組明文分別最多需 259.45, 259.45,259.45, 259.45, 259.45, 259.45, 259.44, 259.44, 259.44,259.44, 259.44, 259.44, 259.44, 258.57, 257.79, 257.16,256.69, 256.39, 256.21, 256.17, 256.05, 256.03, 256.01,256.01, 256, 256, 256, 256, 256次25輪加密。所以攻擊過程時間復雜度不超過 259.45× 97 + 259.44×8+ 258.57+257.79+ 257.16+ 256.69+ 256.39+ 256.21+ 256.17+ 256.05+ 256.03+256.01× 2 + 256× 5 ≈ 266.20。此外，攻擊過程中還需要2119的存儲空間存儲候選密鑰，模28加運算的表以及攻擊過程中每一步驟的某些中間數據。

表1 算法1所猜密鑰與主密鑰的關系

證畢

同理，可利用區分器I對25輪HIGHT算法進行攻擊。

5 結束語

本文對HIGHT算法在積分攻擊下的安全性進行了研究，糾正了文獻[2]中構造 11輪區分器時的錯誤，通過向前做高階積分將 11輪區分器擴展至17輪。依據17輪區分器，利用“時空折中”的原理降低計算復雜度，攻擊了25輪HIGHT算法。攻擊算法的數據復雜度、時間復雜度和空間復雜度分別為262.92、266.20和2119。攻擊輪數和時間復雜度都要優于文獻[2]的結果。

本文結果表明，針對廣義 Feistel結構的算法，在擁有足夠的存儲空間的情況下，可以利用“時空折中”的原理攻擊更多輪算法結構。在未來的工作中，將利用這一原理，對其他結構分組密碼算法（SPN結構、Feistel結構等）進行分析，以達到在降低時間復雜度的同時，攻擊更多輪算法的研究目的，進一步推廣積分攻擊算法的應用范圍。

表2將本文積分攻擊的結果與文獻[2]的結果做了比較。

表2 HIGHT算法積分攻擊的結果比較

[1] HONG D, SUNG J, HONG S, et al. HIGHT： a new block cipher suitable for low-resource device[C]//Cryptographic Hardware and Embedded Systems - CHES 2006. c2006： 46-59.

[2] ZHANG P, SUN B, LI C. Saturation attack on the block cipher HIGHT[C]//The 8th International Conference on Cryptology and Network Security. c2009：76-86.

[3] KOO B, HONG D, KWON D. Related-key attack on the full HIGHT[C]//Information Security and Cryptology - ICISC 2010. c2010：49-67.

[4] HONG D, KOO B, KWON D. Biclique attack on the full HIGHT[C]//Information Security and Cryptology - ICISC 2011. c2011： 365-374.

[5] CHEN J, WANG M, PRENEEL B. Impossible differential cryptanalysis of the lightweight block ciphers TEA, XTEA and HIGHT[C]// AFRICACRYPT 2012. c2012： 117-137.

[6] IGARASHI Y, SUEYOSHI R, KANEKO T, et al. Meet-in-the-middle attack with splice-and-cut technique on the 19-round variant of block cipher HIGHT[J]. Infromation Science and Applications, 2015, 339： 423-429.

[7] 范偉杰, 吳文玲, 張蕾. HIGHT算法的差分故障攻擊[J]. 中國科學院研究生院學報, 2012, 29(2)： 271-276.FAN W J, WU W L, ZHANG L. Differential fault analysis on HIGHT[J]. Journal of Graduate University of Chinese Academy of Science. 2012, 29(2)： 271-276.

[8] 陳浩, 王韜, 張帆, 等. HIGHT密碼代數故障分析[J]. 上海交通大學學報. 2015, 49(12)： 1817-1825.CHEN H, WANG T, ZHANG F, et al. Algebraic fault analysis of HIGHT[J]. Journal of Shanghai Jiaotong University, 2015, 49(12)：1817-1825.

[9] KNUDSEN L, WAGNER D. Integral cryptanalysis[C]//FSE 2002.Leuven, Belgium, c2002： 112-127.

[10] MINER M, PHAN R W, POUSSE B. On integral distinguishers of rijndael family of ciphers[J]. Cryptologia, 2012, 36(2)： 104-118.

[11] YU S, LEI W. Meet-in-the-middle technique for integral attacks against feistel ciphers[C]//Selected Areas in Cryptography 2012. c2012： 234-251.

[12] YI W, CHEN S. Integral cryptanalysis of the block cipher E2[EB/OL].http：//arxiv.org/pdf/1404.6100.pdf.

[13] YI W, CHEN S. Improved results on integral and zero-correlation linear cryptanalysis of the block cipher MIBS[EB/OL]. http：//arxiv.org/pdf/1404.6100.pdf.

[14] 李超, 孫兵, 李瑞林. 分組密碼的攻擊方法與實例分析[M]. 北京：北京科學出版社, 2010： 175-207.LI C, SUN B, LI R L. Block cipher attack method and example analysis[M]. Beijing： Beijing Science Press, 2010：175-207.

Integral attack on HIGHT block cipher

GUO Jian-sheng1,2, CUI Jing-yi1, PAN Zhi-shu3, LIU Yi-peng1
(1. The Third Department, The PLA Information Engineering University, Zhengzhou 450001, China;2. Science and Technology on Information Assurance Laboratory, Beijing 100072, China;3. Xi’an Satellite Control Center, Xi’an 710043, China)

The security of HIGHT block cipher under integral attack was studied. Firstly, the flaw in the existing results on building the distinguisher was corrected. And a new 11-round integral distinguisher of HIGHT was built. Based on this new distinguisher, a 17-round multiple-integral distinguisher was built. By using the 17-round distinguisher, 25-round integral attack on HIGHT was proposed based on the principle of time memory trade-off, with the data, time and memory complexity of 262.92, 266.20and 2119respectively. The results show that the attack was better than results before on the number of round and time complexity.

cryptanalysis, bock cipher, integral attack, HIGHT block cipher

China Postdoctoral Science Foundation (No.2014M562582)

TN918.1

A

10.11959/j.issn.1000-436x.2016135

2015-01-27；

2016-06-04

中國博士后科學基金資助項目（No.2014M562582）

郭建勝（1972-），男，河南沁陽人，解放軍信息工程大學教授，主要研究方向為信息安全與密碼學。

崔競一（1992-），男，河南登封人，解放軍信息工程大學碩士生，主要研究方向為分組密碼設計與分析。

潘志舒（1985-），男，江蘇鎮江人，西安衛星測控中心助理工程師，主要研究方向為分組密碼設計與分析。

劉翼鵬（1992-），男，山東煙臺人，解放軍信息工程大學碩士生，主要研究方向為信息安全與量子密碼。