CIKS-128分組算法的相關(guān)密鑰-差分攻擊

郭建勝，崔競一，羅 偉，劉翼鵬

(1.解放軍信息工程大學(xué)，河南鄭州 450004；2.信息保障技術(shù)重點實驗室，北京 100000；3.78179部隊，四川成都 611843)

?

CIKS-128分組算法的相關(guān)密鑰-差分攻擊

郭建勝1,2，崔競一1，羅 偉3，劉翼鵬1

(1.解放軍信息工程大學(xué)，河南鄭州 450004；2.信息保障技術(shù)重點實驗室，北京 100000；3.78179部隊，四川成都 611843)

分析研究了CIKS-128分組密碼算法在相關(guān)密鑰-差分攻擊下的安全性.利用DDP結(jié)構(gòu)和非線性函數(shù)的差分信息泄漏規(guī)律構(gòu)造了一條高概率相關(guān)密鑰-差分特征，并給出攻擊算法，恢復(fù)出了192bit密鑰；在此基礎(chǔ)上，對剩余64bit密鑰進行窮舉攻擊，恢復(fù)出了算法的全部256bit密鑰.攻擊所需的計算復(fù)雜度為277次CIKS-128算法加密，數(shù)據(jù)復(fù)雜度為277個相關(guān)密鑰-選擇明文，存儲復(fù)雜度為225.4字節(jié)存儲空間.分析結(jié)果表明，CIKS-128算法在相關(guān)密鑰-差分攻擊條件下是不安全的.

分組密碼；密碼分析；CIKS-128分組算法；相關(guān)密鑰-差分攻擊

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.09.010

1 引言

隨著物聯(lián)網(wǎng)相關(guān)技術(shù)地快速發(fā)展，資源受限環(huán)境下的信息安全問題日益突出.這類硬件設(shè)備的計算、存儲資源受限的環(huán)境下，常規(guī)的分組密碼算法在資源占用率和實現(xiàn)效率上難以滿足需求.DDP(Data-Dependent Permutations)[1,2]結(jié)構(gòu)具有實現(xiàn)速率快、資源占用小、數(shù)據(jù)處理規(guī)模靈活等特點，被廣泛應(yīng)用于算法設(shè)計[3～5].基于DDP結(jié)構(gòu)設(shè)計的密碼算法具有高效低耗特點.然而，目前針對這類算法的安全性分析有待完善，嚴重制約了這類算法走向應(yīng)用.

近年來，復(fù)合攻擊方法的研究成為分組密碼分析領(lǐng)域的研究熱點，特別是相關(guān)密鑰-差分類型的攻擊方法的應(yīng)用[6～10]極大推動了分組密碼分析的發(fā)展.特別地，為減小計算-存儲開銷，基于DDP結(jié)構(gòu)設(shè)計的分組密碼算法通常選用簡單的密鑰生成算法，相關(guān)密鑰類型的復(fù)合攻擊成為分析這類算法的有力手段之一.2010年，Lee等人利用分割攻擊的思想對DDP-64分組密碼算法抵抗相關(guān)密鑰-差分分析的能力進行了評估[11]；2012年，在WAINA會議上，Jinkeon Kang等人提出了針對MD-64算法的相關(guān)密鑰-擴大飛來去器攻擊[12]，為基于高次DDP結(jié)構(gòu)的分組密碼算法安全性分析提供了新的思路.

作為基于DDP結(jié)構(gòu)的典型算法，CIKS-128算法[3]采用DDP結(jié)構(gòu)提升了數(shù)據(jù)的處理效率，選用簡單的密鑰生成算法降低了實現(xiàn)功耗，設(shè)計者聲稱該算法能夠抵抗所有已知攻擊.針對CIKS-128算法，Youngdai Ko等人于2004年提出了相關(guān)密鑰-差分攻擊[13]，恢復(fù)出了47bit密鑰信息；Lee等人于2011年構(gòu)造了算法的一條高概率相關(guān)密鑰-差分特征[14]，恢復(fù)出了63bit密鑰信息，這是針對該算法最好的分析結(jié)果.

本文研究了CIKS-128算法的相關(guān)密鑰-差分性質(zhì)，利用DDP結(jié)構(gòu)的差分信息泄漏規(guī)律構(gòu)造了算法的高概率相關(guān)密鑰-差分特征，并給出了相應(yīng)攻擊算法，恢復(fù)出了192bit密鑰，并利用窮舉攻擊恢復(fù)出了算法剩余64bit密鑰.攻擊算法計算復(fù)雜度為277次CIKS-128算法加密，數(shù)據(jù)復(fù)雜度為277個選擇明文，存儲復(fù)雜度為225.4字節(jié).

2 相關(guān)知識

2.1 符號約定

本文常用符號約定如下：

逐位模2加ei角標(biāo)位置取值為1,其它位置為0的二元序列,ei1,i2,ei1,i2,i3依此類推P(C)明文(密文)XL(XR)數(shù)據(jù)塊X的左(右)半部分ΔX表示二元序列X的兩組取值逐位模2加X·Y表示二元序列X,Y逐位相乘xiX的第i比特X>>>n表示二元序列X循環(huán)右移nbitei→ej輸入差分為ei,輸出差分為ej的差分對pi,qi概率Pn/m輸入輸出為nbit,控制信息為mbit的DDP結(jié)構(gòu)(變換)

2.2 CIKS-128分組密碼算法

CIKS-128算法分組長度為128bit，密鑰長度為256bit，迭代圈數(shù)為12輪，算法整體結(jié)構(gòu)和圈函數(shù)結(jié)構(gòu)如圖1所示.

如圖1所示，CIKS-128算法采用類Feistel結(jié)構(gòu)，圈函數(shù)對右半部分處理后作為下一輪左半部分輸入，左半部分直接輸出作為下一輪右半部分輸入，最后一輪圈函數(shù)變換后不進行左右數(shù)據(jù)塊互換.特別地，圈函數(shù)左半部分數(shù)據(jù)和圈子密鑰共同作為右半部分DDP結(jié)構(gòu)的控制信息.

V=(V1,V2,V3,V4,V5,V6)=π(L,L′,L″)其中(L′,L″)∈{(L?A(1),L?A(4)),(L?A(3),L?A(2))}，L,A(i)∈{1,0}64,i=1,2,3,4.Vi取值如下：

線性變換∏由四個長度為16bit的輪換的乘積構(gòu)成，可描述為

(1,50,9,42,17,34,25,26,33,18,41,10,49,2,57,58);

(3,64,43,24,19,48,59,8,35,32,11,56,51,16,27,40);(4,7,28,47,52,23,12,63,36,39,60,15,20,55,44,31);(5,14,13,6,21,62,29,54,37,46,45,38,53,30,61,22).

移位變換I輸入輸出均為64bit，若其輸入為X=(X1,X2,…,X8)，則輸出為

其中Xi∈{0,1}8.

非線性函數(shù)G定義為

P64/192變換輸入輸出均為64bit，控制信息為192bit，圖2給出了P64/192的結(jié)構(gòu)圖.P64/192由6層基本P2/1構(gòu)成，每層包含32個并置的P2/1，層與層之間通過線性變換連接，其中基本單元P2/1定義為

表1 CIKS-128算法圈子密鑰

關(guān)于CIKS-128算法詳細信息參見文獻[3].

3 相關(guān)密鑰-差分特性分析

定義1 重量表示二元序列中1的個數(shù).

3.1 輪函數(shù)差分特性分析

下面分析第12輪輸入差分ΔX12=(ej,0),密鑰差分ΔQ12=(0,0,e64,e64)時，各變換環(huán)節(jié)的差分轉(zhuǎn)移規(guī)律.

定義2 若DDP結(jié)構(gòu)的控制信息差分重量為0時，輸入輸出重量相等，則稱該DDP結(jié)構(gòu)具有差分重量平衡性.

性質(zhì)2 ΔX11=(0,0),ΔQ11=(e64,e64,0,0)時，ΔX12=(ej,0)的概率為2-9.

性質(zhì)3 ΔX12=(ej,0)(j≠64),ΔQ12=(0,0,e64,e64)時，P64/192輸出差分為0的概率為p1=2-4.

證明 由P2/1的定義，控制比特差分重量為1時，其輸出差分為0的概率為2-1.由π的定義可知，圈函數(shù)左半部分輸入差分重量為1時，P64/192的控制信息V的差分重量為3(不考慮密鑰差分).由于j≠64，結(jié)合密鑰差分(ΔA(1),ΔA(4))=(0,e64)后，控制信息V的差分重量為4.因此，P64/192輸出差分為0的概率為p1=2-4.證畢.

性質(zhì)4 ΔX12=(ej,0)(1≤j≤58),ΔQ12=(0,0,e64,e64)時，G1輸出差分為ej的概率為p2=2-6.

證明 ΔX12=(ej,0),(ΔA′,ΔA″)=(0,0)時，G1輸入差分為ej，其輸出差分ΔW1滿足：

由上式可知，ΔW1(i)=1的概率為0.5(i=j+1,j+2,j+3,j+4,j+5,j+6)，從而G1輸出差分ΔW1=ej的概率為p2=2-6.證畢.

性質(zhì)5 ΔX12=(ej,0)(1≤∏(j)≤58),ΔQ12=(0,0,e64,e64)時，G2輸出差分為e∏(j)的概率為p3=2-7.

證明 根據(jù)定義，密鑰差分(ΔA′,ΔA″)=(e64,e64)引起的輸出差分滿足ΔW1(64)=1?l63.又根據(jù)性質(zhì)4的分析過程，1≤∏(j)≤58時，數(shù)據(jù)差分與密鑰差分引起的輸出差分非0比特位不重合，因此密鑰差分對G2輸出差分無影響的概率為2-1.根據(jù)性質(zhì)4，ΔX12=(ej,0)(1≤∏(j)≤58)使得G2輸出差分為e∏(j)的概率為2-6.因此，G2輸出差分為e∏(j)的概率為p3=2-1×2-6=2-7.證畢.

證明 由性質(zhì)3，4，5即得.證畢.

3.2 相關(guān)密鑰差分特征

由∏變換的定義，“1≤j,∏(j)≤58”等價于“1≤j≤58且j≠3,12,21,30,39,48”.結(jié)合定理1和文獻[14]給出的相關(guān)密鑰-差分特征，表2給出了CIKS-128算法的相關(guān)密鑰-差分特征，其中1≤j≤58且j≠3,12,21,30,39,48.

如表2所示，本文構(gòu)造的相關(guān)密鑰-差分特征概率為

(2-3)10×2-9×2-31.98≈2-71

3.3P64/192-1差分特性分析

記vi表示第12輪192比特的控制信息V′的第i比特.

表2 相關(guān)密鑰-差分特征

重量為2的差分對eI(j),∏(j)→es,t存在2類差分傳遞線路，每類包括兩條重量為1的差分傳遞線路.例如j=57時，I(j)=53,∏(j)=58，e53,58→e4,59的兩條差分傳遞線路由圖4給出：第Ⅰ類差分傳遞線路中，e53傳遞到e4，e58傳遞到e59(如圖4實線所示)；第Ⅱ類差分傳遞線路中，輸入差分e53傳遞到e59，e58傳遞到e4(如圖4虛線所示).e53,58→e4,59的差分傳遞線路由表3給出.

表3 e53,58→e4,59的兩類差分傳遞線路

4 相關(guān)密鑰-差分攻擊算法

下面利用本文構(gòu)造的相關(guān)密鑰-差分特征，給出CIKS-128算法的相關(guān)密鑰-差分攻擊算法.

算法1 相關(guān)密鑰-差分攻擊算法對j=2,10,16,18,20,23,26,27,28,31,33,34,41,44,49,51,55,56,57執(zhí)行以下步驟:Step1 選擇n個滿足差分X⊕X*=(e64,e64)的明文對(X,X*).Step2 利用密鑰K,K*分別加密明文X,X*,得到相應(yīng)的密文Y,Y*,其中K⊕K*=(0,0,e64,e64);對固定的s,t執(zhí)行Step3～Step4:Step3 拋棄不滿足Y⊕Y*=(ej,es,t)(1≤j≤58,j≠3,12,21,30,39,48)的密文對,利用重量為2的差分對eI(j),∏(j)→es,t恢復(fù)出第12輪P-164/192兩組12bit控制信息,建立密文、控制信息與密鑰塊O1,O2,O3的方程組,將得到兩組12bit密鑰信息kjs,t,kj's,t作為整體存入集合Kjs,t.Step4 對集合Kjs,t中的12bit密鑰比特鏈kjs,t,kj's,t分別計數(shù),將計數(shù)次數(shù)不小于5次的12bit密鑰鏈分別作為正確密鑰,存入Kjs,t*;Step5 取另一組s,t執(zhí)行Step3～Step4;Step6 整理得到Kj=∪s,tKjs,t*

攻擊算法的成功率和復(fù)雜度分析分別由定理2和定理3給出.

與此同時，錯誤密鑰鏈的計數(shù)次數(shù)不小于5次的概率為

定理3n=276時，利用攻擊算法能夠恢復(fù)出CIKS-128算法的192比特密鑰信息，計算復(fù)雜度為277次CIKS-128算法加密，數(shù)據(jù)復(fù)雜度為277個選擇明文，存儲復(fù)雜度為225.4字節(jié).

在利用攻擊算法恢復(fù)出CIKS-128算法192比特密鑰的基礎(chǔ)上，對于剩余的64比特密鑰信息進行窮舉攻擊，所需的計算復(fù)雜度為264次CIKS-128算法加密.由于264+277≈277，利用277次CIKS-128算法加密，277個相關(guān)密鑰-選擇明文以及225.4字節(jié)存儲空間，即可恢復(fù)出CIKS-128算法全部256比特密鑰.

5 結(jié)束語

基于DDP結(jié)構(gòu)類的分組密碼算法主要面向?qū)γ艽a算法的加解密速率和資源占用要求較高的硬件環(huán)境，因此算法大多選用簡單的密鑰生成算法，節(jié)省了密鑰計算時間和存儲空間.作為一種典型的基于DDP結(jié)構(gòu)設(shè)計的分組密碼算法，CIKS-128算法具有低能耗、高效率的特點.本文的分析結(jié)果表明，簡單的密鑰生成算法和DDP結(jié)構(gòu)的差分重量平衡性，導(dǎo)致CIKS-128算法難以抵抗相關(guān)密鑰-差分攻擊.表4列出了部分典型分組密碼算法在相關(guān)密鑰-差分攻擊條件下的最優(yōu)攻擊結(jié)果.

對比傳統(tǒng)的差分攻擊，相關(guān)密鑰-差分攻擊要求密鑰生成算法具有較差的差分擴散特性.LBlock、AES-256的密鑰生成算法差分擴散特性較好，相關(guān)密鑰-差分攻擊效果較差.作為基于DDP結(jié)構(gòu)的典型分組密碼算法，Cobra-H128、CIKS-128的密鑰生成算法比較簡單，密鑰長度分別為128bit和256bit，與文獻[17]相比，本文以相當(dāng)?shù)膹?fù)雜度攻擊得到了CIKS-128全部256密鑰比特.針對CIKS-128算法，本文首次恢復(fù)出了算法的全部密鑰比特，攻擊結(jié)果明顯優(yōu)于Youngdai Ko和Lee給出的攻擊結(jié)果.分析結(jié)果表明，利用DDP結(jié)構(gòu)設(shè)計算法時，一應(yīng)當(dāng)充分考慮DDP結(jié)構(gòu)的差分信息泄漏規(guī)律，在不影響效率的前提下，利用一些密碼學(xué)指標(biāo)較好的變換與DDP結(jié)構(gòu)結(jié)合使用，提升圈函數(shù)密碼學(xué)指標(biāo)；二增強密鑰生成算法的差分擴散性，降低各圈子密鑰的相關(guān)性.

表4 部分算法在相關(guān)密鑰-差分攻擊下的攻擊結(jié)果

[1]Moldovyan A A.Fast block ciphers based on controlled permutations[J].Computer Science Journal of Moldova,2000,8(3):270-283.

[2]Moldovyan A A,Moldovyan N A.A cipher based on data-dependent permutation[J].Journal of Cryptology,2002,15(1):61-72.

[3]Sklavos N,Moldovyan N A,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.

[4]Minh N,Bac D,Duy H.New SDDO-based block cipher for wireless sensor network security[J].I.J.Computer Network and Network Security,2010,10(3):54-60.

[5]Bac Do Thi,Minh Nguyen Hieu,Duy Ho Ngoc.An effective and secure cipher based on SDDO[J].I.J.Computer Network and Information Security,2012,4(11)：1-10.

[6]Biryukov A,Nikolic I.Search for related-key differential characteristics in DES-Like ciphers[A].LNCS 6733:FSE 2011[C].Lyngby,Denmark:Springer,2011.18-34.

[7]Minier M,Naya-Plasencia M.A related key impossible differential attack against 22 rounds of the lightweight block cipher LBlock[J].Information Processing Letters,2012,112(16):624-629.

[8]詹英杰,關(guān)杰,丁林，等.對簡化版LBLock 算法的相關(guān)密鑰不可能差分攻擊[J].電子與信息學(xué)報,2012,34(9):2161-2166.

Zhan Ying-jie,Guan Jie,Ding Lin,et al.Related-key impossible differential attack on reduced round LBlock[J].Journal of Electronics & Information Technology,2012,34(9):2161-2166.(in Chinese)

[9]Tomer Ashur,Orr Dunkelman.A practical related-key boomerang attack for the full MMB block cipher[A].LNCS 8257:Cryptology and Network Security 2013[C].Paraty,Brazil:Springer.2013.20-22.

[10]Marine Minier.On the security of piccolo lightweight block cipher against related-key impossible differentials[A].LNCS 8250:INDOCRYPR 2013[C].Mumbai,India:Springer,2013.308-318.

[11]Lee Changhoon,Lee Sangjin,Park Jong Hyuk,et al.Security analysis of pure DDP-based cipher proper for multimedia and ubiquitous device[J].Telecommunication System,2010,44(3-4):267-279.

[12]Kang Jinkeon,Jeong Kitae,Yeo Sang-Soo,et al.Related-key attack on the MD-64 block cipher suitable for pervasive computing environments[A].26th International Conference on Advanced Information Networking and Applications Workshops(WAINA 2012)[C].Fukuoka:IEEE,2012.726-731.

[13]Ko Youngdai,Lee Changhoon,Hong Seokhie,et al.Related-key attacks on DDP based ciphers:CIKS-128 and CIKS-128H[A].LNCS 3348:INDOCRYPT 2004[C].Chennai,India:Springer,2004.191-205.

[14]Lee Changhoon,Kim Jongsung,Sung Jaechul,et al.Cryptanalysis of CIKS-128 and CIKS-128H suitable for intelligent multimedia and ubiquitous computing systems[J].Computing and Informatics,2011,30(3):447-466.

[15]Shusheng Liu,Zheng Gong,Libian Wang.Improved related-key differential attacks on reduced-round LBlock[A].Information and Communications Security-14th International Conference(ICICS 2012)[C].Hong Kong,China:Springer,2012.58-69.

[16]Alex Biryukov,Dmitry Khovratovich,Ivica Nikoli′c.Distinguisher and related-key attack on the full AES-256[A].CRYPTO’09,Santa Barbara[C].CA,USA:Springer,2009.231-249.

[17]羅偉，郭建勝.Cobra-H64/128算法的相關(guān)密鑰-差分攻擊[J].電子學(xué)報，2013,41(8):1569-1573.

LUO Wei,GUO Jian-sheng.Related-key differetial attacks on cobra-H64/128[J].Acta Electronica Sinica,2013,41(8):1569-1573.(in Chinese)

郭建勝 男，1972年出生，河南沁陽人，博士，解放軍信息工程大學(xué)教授、博士生導(dǎo)師，主要研究方向為密碼學(xué)和信息安全.

E-mail:tsg-31@126.com

崔競一(通訊作者) 男，1992出生，河南登封人，解放軍信息工程大學(xué)碩士生，主要研究方向為密碼分析.

E-mail:tsg-31@126.com

Related-Key Differential Attack on Block Cipher CIKS-128

GUO Jian-sheng1,2,CUI Jing-yi1,LUO Wei3,LIU Yi-peng1

(1.ThePLAInformationEngineeringUniversity,Zhengzhou,Henan450004,China;2.ScienceandTechnologyonInformationAssuranceLaboratory,Beijing100000,China;3.TheUnitof78179,Chengdu,Sichuan,611843,China)

The security of CIKS-128 block cipher under related-key differential attack was studied.A related-key differential of high probability was constructed with the differential information leakages in the structure of DDPs and nonlinear functions.By proposing a corresponding key recovery attack based on the related-key differential,the master key of 192 bits was recovered.The rest 64 bits of the master key could be obtained by exhaustive search.The computational complexity,the data complexity and the memory complexity are 277CIKS-128 block cipher encryptions,277chosen-plaintexts and 225.4bytes of storage resources,respectively.Analysis results show that CIKS-128 is unsafe under related-key differential attack.

block cipher;cryptanalysis;CIKS-128;related-key differential attack

2014-12-24；

2015-06-24；責(zé)任編輯：馬蘭英

博士后科學(xué)基金(No.2014M562582)

TN918.1

A

0372-2112 (2016)08-1837-08