MD-64算法的相關密鑰-矩形攻擊

郭建勝崔競一羅 偉劉翼鵬（信息保障技術重點實驗室 北京 100072）（解放軍信息工程大學 鄭州 450001）（解放軍78179部隊 成都 611830）

MD-64算法的相關密鑰-矩形攻擊

郭建勝*①②崔競一②羅 偉③劉翼鵬②
①（信息保障技術重點實驗室 北京 100072）②（解放軍信息工程大學 鄭州 450001）③（解放軍78179部隊 成都 611830）

該文針對 MD-64分組密碼算法在相關密鑰-矩形攻擊下的安全性進行了研究。分析了算法中高次 DDO（Data Dependent Operations）結構、SPN結構在輸入差分重量為1時的差分轉移規律，利用高次DDO結構的差分特性和SPN結構重量為1的差分路徑構造了算法的兩條相關密鑰-差分路徑，通過連接兩條路徑構造了算法的完全輪的相關密鑰-矩形區分器，并對算法進行了相關密鑰-矩形攻擊，恢復出了32 bit密鑰。攻擊算法所需的數據復雜度為262相關密鑰-選擇明文，計算復雜度為291.6次MD-64算法加密，存儲復雜度為266.6Byte存儲空間，成功率約為0.961。分析結果表明，MD-64算法在相關密鑰-矩形攻擊條件下的安全性無法達到設計目標。

分組密碼；密碼分析；MD-64算法；相關密鑰-矩形攻擊

1 引言

近年來，基于相關密鑰的復合攻擊成為分組密碼分析領域的研究熱點，其中相關密鑰-差分攻擊方法極大促進了密碼分析的發展［1-4］。矩形攻擊是一種常見的差分分析手段，文獻［5］利用飛來去器攻擊給出了LBlock算法的分析結果；文獻［6］利用相關密鑰-矩形攻擊對KASUMI算法進行了攻擊實驗；文獻［7］利用相關密鑰-飛來去器攻擊給出了KATAN32 /48/64算法的分析結果，文獻［8］利用相關密鑰-飛來去器攻擊給出了MMB算法的分析結果。

在分組密碼設計當中，DDP（Data-Dependent Permutation）［9］， DDO（Data-Dependent Operations）［10］，高次DDO［11］等比特控選結構具有可并行計算、執行效率高、易于軟硬件實現、數據處理規模靈活、應用范圍廣泛等優點，被廣泛應用于分組密碼算法設計［12-14］。目前，針對應用上述結構的分組算法的安全性分析成果較少，分析這類算法的安全性具有十分重要的意義。

作為高次DDO結構的一個典型應用，MD-64算法由文獻［11］于2010年提出。算法設計者利用高次DDO結構提升了算法的執行效率和資源利用率。與此同時，設計者在算法圈函數一路數據處理過程中引入了SPN結構，實現了對數據的擴散和置亂。安全性分析方面，設計者構造了一條概率約為的兩輪循環差分鏈，并認為8輪迭代使得MD-64算法能夠抵抗所有差分類型攻擊。文獻［15］于2011年對MD-64算法進行了相關密鑰-擴大飛來去器攻擊，文獻［16］對MD-64算法同樣進行了相關密鑰-擴大飛來去器攻擊，但二者均未分析攻擊算法的存儲復雜度和成功率。

本文研究了MD-64算法在相關密鑰-矩形攻擊下安全性，利用高次DDO結構和SPN結構存在的信息泄漏規律構造了算法的兩條高概率相關密鑰-差分路徑，進而給出了算法的全輪相關密鑰-矩形區分器，在相關密鑰-選擇明文條件下對算法的進行了攻擊，攻擊算法所需的數據復雜度為 262個相關密鑰-選擇明文，計算復雜度為 291.6次 MD-64算法加密，存儲復雜度為266.6Byte存儲空間，成功率約為0.961。

2 相關知識

2.1 符號說明

下面對本文所使用的符號進行說明，K表示算法主密鑰，P表示算法的明文輸入，C表示算法的密文輸出。第i輪的輪函數左半分組與右半分組分別記為 Li與 Ri， ΔLi與 ΔRi分別表示第i輪的輪函數左半分組的輸入差分與右半分組的輸入差分。 ΔQi與為第i圈加密圈子密鑰的差分與解密圈子密鑰的差分。ei表示第i位非零且其余位為零的32 bit數據塊， ei，j第i位與第j位非零且其余位為零的32 bit數據塊。

2.2 MD-64算法

MD-64算法分組規模為64 bit，密鑰規模為128 bit，迭代輪數為8輪。算法圈函數將64 bit輸入數據分成兩路32 bit數據塊，其中一路數據主要利用高次DDO結構進行處理，另一路數據利用SPN結構進行處理，能夠同時對兩路數據進行擴散和置亂。算法整體結構和圈函數結構分別如圖1（a）和圖1（b）所示，圈函數中SPN結構如圖2所示。

圖1 MD-64算法示意圖

圖2 SPN結構示意圖

線性變換 P1：

線性變換 P2：

線性變換 P3：

（1，3，19，17）（2，7，20，21）（4，23，18，5）（6，8，24，22）

（11，27，25，9）（10，15，28，29）（12，31，26，13）（14，16，32，30）

表1 大小為4×4的S盒

表2 MD-64算法圈子密鑰

線性變換 I1：

記拓展變換E的32 bit輸入為 （B1，B2）， 192 bit輸出為Z6），則

其中 B，V，Z均為16 bit數據， X＜＜＜n表示對16 bit

iii數據進行循環左移nbit。

2.3 相關密鑰-矩形攻擊算法

矩形攻擊是一種差分類型的分析方法，于2005年由Biham等人［17］提出。矩形攻擊的主要思想是通過連接兩條短的高概率差分路徑構造輪數更長區分器。假設算法E可以用表示， E0存在概率為p的差分路徑α → β， E1存在概率為q的差分路徑δ→ γ，若滿足 （pq ）2＞ 2-n，則認為可以構造區分器將密碼算法與隨機置換區分開，其中n為算法分組規模。

相關密鑰-矩形攻擊是在矩形攻擊中引入相關密鑰，其目的是提升算法的攻擊輪數，圖3給出了相關密鑰-矩形區分器示意圖。

如圖3所示，攻擊者獲得了密鑰 K，K *，K'，K '*間的差分關系，但并不知道密鑰的取值，在相關密鑰條件下，利用兩條短的高概率相關密鑰-差分路徑即可構造出輪數更長的相關密鑰-矩形攻擊區分器。

定義 1［17］若明文四元組（P，P'，P *，P'*）同時滿足圖3中所示的4條差分路徑，則稱其為正確四元組。

3 MD-64算法圈函數差分特性分析

3.1 基本單元差分特性分析

性質1當控制信息差分為0，基本單元 F2/2輸入差分重量為1時，

證明當控制信息差分為0，基本單元 F2/2輸入差分 Δx1Δ x2重量為1時，x1x2的取值情況只有同種01， 10。分別代入 y1與 y2的表達式中可得：

當輸入 Δx1Δ x2為10時，通過控制vz取值遍歷00， 01， 10， 11共4種情況，對應 y1y2的4個輸出分別為10， 01， 10， 11。

當輸入 Δx1Δ x2為01時，通過控制vz取值遍歷00， 01， 10， 11共4種情況，對應 y1y2的4個輸出分別為11， 10， 11， 01。 證畢

類似地，得到性質2和性質3。

性質2當控制信息差分為0，基本單元 F2/2輸入差分重量為2時，

性質 3當基本單元 F2/2控制信息差分 Δv Δz重量為1時，

圖3 相關密鑰-矩形區分器示意圖

3.2 SPN結構差分特性分析

通過實驗模擬，遍歷搜索得到SPN結構重量為1的最優差分路徑，由表3給出。如表3所示，SPN結構重量為 1的最優差分路徑為對于MD-64算法圈函數，由 I1知，圈函數輸入差分為 （0，e13），密鑰差分為（0，0）時，SPN結構輸入差分為 e6，即圈函數右半部分存在輸入輸出重量為 1 的差分路徑

4 MD-64算法圈的相關密鑰矩形攻擊

如表4所示，第1條相關密鑰-差分路徑長度為3輪（第1輪到第3輪），輸入輸出差分分別為α=密鑰差分為差分轉移概率為 p= 1；第2條相關密鑰-差分路徑長度為5輪（第4輪到第8輪），輸入輸出差分分別為密鑰差分為 Δ K'= K ⊕ K' = K * ⊕K '* = （0，e1，0，0），其中k∈｛1，2，3，4，5｝， ？表示任意32 bit二元序列。

第2條相關密鑰-差分路徑中，第7輪輸入差分為（0，0），密鑰差分為 （e1，0），下面分析計算其輸出差分為 （e1，13，0）的概率q'。

第7輪輸入差分為（0，0），密鑰差分為 （e1，0）時，函數的輸入差分為 e1。利用性質1，圖4加粗線條給出了使得函數G的輸出差分為 e1，13的差分路徑。

圖4 F3 2/192 ·I1 ·F 32/192中 e1 → e1，13的一條差分路徑

由于函數G輸出差分重量2，因此1 bit輸入差分在傳遞過程中必然會在經過某個基本單元 F2/2后，變換為2 bit差分，并最終傳遞到函數G輸出的第1和第13個比特位。根據函數G的拓撲結構與假設，1 bit差分變換為2 bit差分的 F2/2所在基本單元層只能在第 2個 F32/192中，圖4所示的差分路徑中的差分路徑的概率分為兩個部分，其中

表3 SPN結構重量為1的最優差分路徑

第2條相關密鑰差分路徑中，MD-64算法第7輪、第8輪的差分傳遞情況如圖5所示。

相關密鑰-矩形攻擊算法步驟如表5所示。

根據上述相關密鑰-差分路徑，相關密鑰-矩形攻擊算法的成功率和復雜度分析分別由定理1和定理2給出。

定理1取 n= 61時，相關密鑰-矩形攻擊算法的成功率約為0.961。

證明取 n= 61時，相關密鑰-矩形攻擊算法步驟 1構造出個四元組。隨機密文對差分為 （Δ CL，eI1（k））的概率為因此通過步驟 2 的密文四元組數量約為 2121×（2-29.7）2= 261.6個。

步驟3中，正確 K3的計數次數不小3次的概率為

表4 MD-64算法的兩條相關密鑰-差分路徑（k=1，2，3，4，5）

圖5 MD-64算法最后兩輪的差分傳遞情況

表5 相關密鑰-矩形攻擊算法

因此，攻擊算法的成功率約為0.961。 證畢

定理2利用相關密鑰-矩形攻擊算法能夠恢復出MD-64算法的128 bit密鑰，相應的數據復雜度為 262個相關密鑰-選擇明文，計算復雜度為 291.6次MD-64算法加密，存儲復雜度為 266.6Byte存儲空間。

證明步驟1加密明文需要 2 × 2n= 262次MD-64算法加密。步驟 2存儲密文四元組需要 261.6×4 ×8 = 266.6Byte存儲空間。步驟3中反解一輪算法約為1/16次MD-64算法加密，因此步驟3所需的計算復雜度為 261.6× 232× 4 × 1/16 = 291.6次 MD-64算法加密。綜上所述，利用相關密鑰-矩形攻擊算法恢復 32 bit密鑰所需的數據復雜度為 262個相關密鑰-選擇明文，計算復雜度為 262+291.6≈ 291.6次MD -64算法加密，存儲密鑰度約為 266.6Byte存儲空間。

證畢

表6給出了針對MD-64算法攻擊結果的對比情況。

如表6所示，本文給出了針對MD-64算法完整分析結果，攻擊算法整體復雜度為≈ 291.6，優于已有攻擊結果的整體復雜度 295。

5 結束語

本文對MD-64算法進行了相關密鑰-矩形分析，利用相關密鑰構造了算法的高概率相關密鑰-矩形區分器，并恢復出了32 bit算法主密鑰。本文的分析結果表明，MD-64算法選用的SPN結構的數據規模相對較小，因此存在著明顯的差分不平衡，從而造成部分信息泄漏；同時，攻擊者能夠利用高次DDO結構的基本單位所固有的差分信息泄漏規律構造高概率差分路徑。因此，使用高次 DDO結構時應當綜合考慮到高次 DDO結構與算法中其它編碼環節、圈子密鑰與數據的結合方式的相互影響，從而消除高次 DDO結構和其它編碼環節在差分分析下所存在的固有信息泄漏規律。

表6 MD-64算法攻擊結果對比情況

［1］ Sareh E， San L， Ivica N， et al.. The resistance of PRESENT-80 against related-key differential attacks［J］. Cryptography and Communications， 2014， 6（3）: 171-187.

［2］ Yuseop L， Kitae J， Changhoon L， et al.. Related-key cryptanalysis on the full PRINTcipher suitable for IC-printing［J］. International Journal of Distributed Sensor Networks， 2014（1）: 1-10.

［3］ Wen L， Wang M Q， and Zhao J Y. Related-key impossible differential attack on reduced-round LBlock［J］. Journal of Computer Science and Technology， 2014， 29（1）: 165-176.

［4］ 詹英杰， 關杰， 丁林， 等. 對簡化版 LBLock 算法的相關密鑰不可能差分攻擊［J］. 電子與信息學報， 2012， 34（9）: 2161-2166. Zhan Y J， Guan J， Ding L， et al.. Related-key impossible differential attack on reduced round LBlock［J］. Journal of Electronics & Information Technology， 2012， 34（9）: 2161-2166.

［5］ Chen J G and Atsuko M. Differential cryptanalysis and boomerang cryptanalysis of LBlock［C］. The International Cross Domain Conference and Workshops 2013， Regensburg，Germany， 2013: 1-15.

［6］ Jongsung K， Seokhie H， Bart P， et al.. Related-key boomerang and rectangle attacks: theory and experimental analysis［J］. IEEE Transactions on Information Theory， 2012，58（7）: 4948-4966.

［7］ Takanori I， Yu S， and Jiageng C. Related-key boomerang attacks on KATAN32/48/64［C］. Australasian Conference on Information Security and Privacy 2013， Brisbane， Australia，2013: 268-285.

［8］ Ashur T and Dunkelman O. A practical related-key boommerang attack for the full MMB block cipher［C］. Cryptology and Network Security 2013， Paraty， Brazil， 2013: 271-290.

［9］ Moldovyan A and Moldovyan N. A cipher based on data-dependent permutation［J］. Journal of Cryptology， 2002，15（1）: 61-72.

［10］ Moldovyan A， Moldovyan N， and Sklavos N. Controlled elements for designing ciphers suitable to efficient VLSI implementation［J］. Telecommunication System， 2006， 32（2）: 149-163.

［11］ Nguyen Hieu-minh， Do Thi-bac， and Ho Ngoc-duy. New SDDO-based block cipher for wireless sensor network security［J］. International Journal of Computer Science and Network Security， 2010， 10（3）: 54-60.

［12］ Sklavos N， Moldvyan N A， and Koufopavlou O. High speed networking security: design and implementation of two new DDP-based ciphers［J］. Mobile Networks and Applications-MONET， 2005， 10（1/2）: 219-231.

［13］ Moldovyan N， Sklavos N， and Moldovyan A. CHESS-64， a block cipher based on data-dependent operations: design variants and hardware implementation efficiency［J］. Asian Journal of Information Technology， 2005， 4（4）: 323-334.

［14］ Bac Do-thi， Minh Nguyen-hieu， and Duy Ho-ngoc. An effective and secure cipher based on SDDO［J］. International Journal of Computer Network and Information Security， 2012，4（11）: 1-10.

［15］ Chang-Hoon L. Security analysis of block cipher MD-64 suitable for wireless sensor network environments［J］. Journal of Korea Navigation Institute， 2011， 15（5）: 865-869.

［16］ Jinkeon K， Kitae J， Sang-Soo Y， et al.. Related-key attack on the MD-64 block cipher suitable for pervasive computing environments［C］. International Conference on Advanced Information Networking and Applications Workshops，Fukuoka， Japan， 2012: 726-731.

［17］ Biham E， Dunkelman O， and Keller N. Related-key boomerang and rectangle attacks［C］. EUROCRYPT 2005，Aarhus， Denmark， 2005: 507-525.

郭建勝： 男，1972年生，教授，研究方向為密碼學與信息安全.

崔競一： 男，1992年生，碩士，研究方向為分組密碼設計與分析.

羅 偉： 男，1987年生，助理工程師，研究方向為分組密碼設計與分析.

劉翼鵬： 男，1992年生，碩士，研究方向為分組密碼設計與分析.

Related-key Rectangle Attack on MD-64

Guo Jian-sheng①②Cui Jing-yi②Luo Wei③Liu Yi-peng②
①（Science and Technology on Information Assurance Laboratory， Beijing 100072， China）②（The PLA Information Engineering University， Zhengzhou 450001， China）③（The PLA Unit 78179， Chengdu 611830， China）

The security of MD-64 block cipher under related-key rectangle attack is studied. Firstly， when the weight of input difference is 1， the differential properties of high order DDOs （Data Dependent Operations） and SPN structures are researched. By the differential properties of high order DDOs and the high probability differential of SPN structures， two related-key differentials are constructed. Secondly， a full round related-key rectangle distinguisher of MD-64 is constructed by connecting two related-key differentials. Thirdly， a related-key rectangle attack is proposed on MD-64， and 32 bits of the master key is recovered with 262related-key chosenplain-text， 291.6encryptions of MD-64 block cipher， and a storage complexity of 266.6Byte. The success rate of this attack is about 0.961. Analysis results show that MD-64 can not reach the design target under related-key rectangle attack.

Block cipher； Cryptanalysis； MD-64 algorithm； Related-key rectangle attack

China Postdoctoral Science Foundation（2014M562582）

TN918.1

A

1009-5896（2015）12-2845-07

10.11999/JEIT150049

2015-01-08；改回日期：2015-09-15；網絡出版：2015-11-01

*通信作者：郭建勝 tsg_31@126.com

博士后科學基金（2014M562582）