對LBloc k算法的多重零相關(guān)線性分析

羅 芳,周學(xué)廣,歐慶于

(海軍工程大學(xué)信息安全系,湖北武漢 430033)

對LBloc k算法的多重零相關(guān)線性分析

羅 芳,周學(xué)廣,歐慶于

(海軍工程大學(xué)信息安全系,湖北武漢 430033)

為了降低對LBlock進(jìn)行零相關(guān)線性分析所需的數(shù)據(jù)復(fù)雜度,提出了對LBlock進(jìn)行多重零相關(guān)線性分析的方法,證明了14輪LBlock存在26條零相關(guān)線性逼近,并給出了其具體構(gòu)造.利用26條14輪零相關(guān)線性逼近為區(qū)分器,并基于正態(tài)分布的概率計(jì)算模型對22輪LBlock進(jìn)行了多重零相關(guān)線性攻擊,攻擊的數(shù)據(jù)復(fù)雜度約為263.45個(gè)已知明文,計(jì)算復(fù)雜度約為276.27次22輪LBlock加密,成功實(shí)施攻擊的概率為0.85.結(jié)果表明,該方法有效解決了需要利用整個(gè)明文空間對LBlock進(jìn)行零相關(guān)線性分析的問題.

輕量級分組密碼;LBlock算法;多重零相關(guān)線性逼近;密碼分析;數(shù)據(jù)復(fù)雜度

隨著信息技術(shù)、計(jì)算機(jī)技術(shù)以及微電子技術(shù)的快速發(fā)展,無線傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng)正逐步深入到人們生活的各個(gè)領(lǐng)域,但同時(shí),物聯(lián)網(wǎng)領(lǐng)域日益突出的數(shù)據(jù)安全問題也正引起人們的極大關(guān)注.與傳統(tǒng)計(jì)算平臺不同,物聯(lián)網(wǎng)系統(tǒng)中的應(yīng)用組件多是計(jì)算能力相對較弱的微型處理設(shè)備,其運(yùn)算、存儲能力有限,導(dǎo)致傳統(tǒng)密碼算法,如高級加密標(biāo)準(zhǔn)(AES)等已無法較好地解決其存在的數(shù)據(jù)安全問題[1].為了保護(hù)計(jì)算資源受限環(huán)境的數(shù)據(jù)安全,出現(xiàn)了許多輕量級密碼算法[2-5].與傳統(tǒng)密碼算法相比,輕量級密碼算法資源消耗少,運(yùn)行效率高.其中,LBLock是由Wu等提出的一個(gè)輕量級分組密碼,與其他輕量級分組密碼相比,LBlock的軟、硬件執(zhí)行效率更高,適應(yīng)性更強(qiáng).

目前,對LBlock的安全性分析僅限于差分分析、線性分析、積分攻擊以及不可能差分分析.Wu等指出, LBlock不存在15輪的有效差分路徑,并且也不存在可以利用的15輪有效線性逼近,將算法與隨機(jī)置換區(qū)分開.對于積分攻擊,李艷俊[6]基于15輪積分區(qū)分器給出了對22輪LBlock的積分攻擊.Liu等[7]利用14輪不可能差分特征對21輪LBlock實(shí)施了不可能差分攻擊,攻擊的數(shù)據(jù)復(fù)雜度為O(262.5),計(jì)算復(fù)雜度為O(273.7),這也是單密鑰模式下對LBlcok的最好分析結(jié)果.

由于傳統(tǒng)意義上差分分析與線性分析有很多相似之處,因此,存在與不可能差分分析相對應(yīng)的線性分析方法是可能的.文獻(xiàn)[8]首次提出了零相關(guān)線性分析,該方法是利用相關(guān)系數(shù)為零的線性逼近作為區(qū)分器,將分組密碼與隨機(jī)置換區(qū)分開.與上述分析方法不同,零相關(guān)線性分析屬于已知明文攻擊,易于實(shí)施.因此,從零相關(guān)線性分析的角度出發(fā),重新評價(jià)LBlock的安全性是十分必要的.但由于在實(shí)施零相關(guān)線性分析的過程中,攻擊者需要準(zhǔn)確計(jì)算線性逼近的相關(guān)系數(shù),因此,該方法在實(shí)際應(yīng)用中存在數(shù)據(jù)復(fù)雜度高的問題,限制了其在輕量級分組密碼分析領(lǐng)域的應(yīng)用.

為了減少對LBlock進(jìn)行零相關(guān)線性分析所需的明、密文對的數(shù)量,降低攻擊所需的數(shù)據(jù)復(fù)雜度,筆者提出了同時(shí)利用多條零相關(guān)線性逼近對LBlock進(jìn)行零相關(guān)線性分析的方法.通過對LBlock算法結(jié)構(gòu)的研究,找到了多條14輪零相關(guān)線性逼近,以多條零相關(guān)線性逼近為區(qū)分器,利用正態(tài)分布的概率計(jì)算模型以及中間相遇法對22輪LBlock實(shí)施了密鑰恢復(fù)攻擊,解決了零相關(guān)線性分析存在的數(shù)據(jù)復(fù)雜度高的問題,同時(shí)也為輕量級分組密碼的設(shè)計(jì)與分析提供了新思路.

1 零相關(guān)線性分析

對于一個(gè)分組長度是n比特的迭代型分組密碼算法C=EK(P),其中,P、C和K分別表示明文、密文和密鑰;若ΓP和ΓC分別是n比特的非零明文掩碼和密文掩碼,則稱ΓP→ΓC為EK的一個(gè)線性逼近;而⊕為EK的線性逼近表達(dá)式,其中表示域F2上n比特向量的乘積.

定義1線性逼近ΓP→ΓC成立的概率[8],其中,Pr表示等式成立的概率.

定義2若線性逼近ΓP→ΓC成立的概率為pΓP,ΓC,則ΓP和ΓC的相關(guān)系數(shù)[9]cΓP,ΓC=2pΓP,ΓC-1.

對于傳統(tǒng)線性密碼分析,當(dāng)線性逼近概率pΓP,ΓC與1/2的偏差越大時(shí),ΓP→ΓC越有益于線性密碼分析.與傳統(tǒng)線性密碼分析不同,當(dāng)pΓP,ΓC=1/2時(shí),有相關(guān)系數(shù)cΓP,ΓC=0,此時(shí),利用相關(guān)系數(shù)為0的線性逼近作為區(qū)分器,并利用類似于Matsui的算法2進(jìn)行的密鑰恢復(fù)攻擊[9],即零相關(guān)線性分析.

在進(jìn)行零相關(guān)線性分析時(shí),首先需要構(gòu)造相關(guān)系數(shù)為0的線性逼近,定理1給出了零相關(guān)線性逼近存在的充分條件.

定理1對于一個(gè)迭代型分組密碼算法,若與其線性殼相對應(yīng)的每條線性特征中都至少存在一對矛盾的相鄰線性掩碼,則該線性殼的相關(guān)系數(shù)為零[8].

假設(shè)攻擊者已經(jīng)找到一條r輪零相關(guān)線性逼近ΓE→ΓD,并擁有N對用當(dāng)前密鑰加密的明、密文對,其中,E和D分別表示零相關(guān)線性逼近起始輪和結(jié)束輪的狀態(tài)變量.對于N個(gè)已知明、密文對,將線性逼近ΓE→ΓD置于被攻擊算法的中間輪,并利用猜測的密鑰部分加密明文P,得到中間狀態(tài)E;同時(shí)利用猜測的密鑰部分解密密文C,得到D.對于這N個(gè)中間狀態(tài)對E-D,計(jì)算成立的概率.若上式成立的概率為1/2,則有cΓP,ΓC=0,這時(shí)猜測的密鑰為正確密鑰;否則,為錯誤密鑰.

為了準(zhǔn)確計(jì)算出相關(guān)系數(shù),要求數(shù)據(jù)復(fù)雜度N=2n,即需要利用整個(gè)明文空間來實(shí)施攻擊.因此,傳統(tǒng)零相關(guān)線性分析方法普遍存在數(shù)據(jù)復(fù)雜度高的問題,這也成為了該分析方法在實(shí)際應(yīng)用中的障礙.

2 LBlock算法零相關(guān)線性逼近的構(gòu)造

2.1 LBlock算法

LBlock算法總體采用類Feistel結(jié)構(gòu),分組長度為64 bit,迭代32輪,主密鑰為80 bit.LBlock的一輪加密流程如圖1所示,其操作步驟如下:

(1)對于i=1,2,…,31,計(jì)算Ri=Li-1,Li=F(Li-1,Ki)⊕(Ri-1＜＜＜8).

(2)對于i=32,計(jì)算R32=F(L31,K32)⊕(R31＜＜＜8),L32=L31.

(3)輸出C=L32||R32為64 bit密文.

輪函數(shù)F由3部分組成,分別為圈密鑰加AK、S盒混淆以及P盒擴(kuò)散,其中,混淆層由8個(gè)4×4的S盒并置而成,P盒則以4 bit字為單位對S盒變換后的結(jié)果進(jìn)行置換,S盒的定義詳見文獻(xiàn)[5].由于采用了類Feistel結(jié)構(gòu),LBlock的解密算法是加密算法的逆過程.

圖1 LBlock算法的1輪加密流程圖

為了縮短圈子密鑰的生成時(shí)間,減少硬件成本,LBlock的密鑰生成算法設(shè)計(jì)簡單,但也存在擴(kuò)散特性較差的問題.針對這一不足,Wang等對原算法的圈子密鑰生成部分進(jìn)行了改進(jìn),改進(jìn)后的圈子密鑰生成算法參見文獻(xiàn)[10].

2.2 14輪LBlock零相關(guān)線性逼近

文獻(xiàn)[11]中,Soleimany通過矩陣及中間相遇法自動搜索到了LBlock的多條14輪零相關(guān)線性逼近,并證明了當(dāng)輸入掩碼中僅有1位非零4 bit字,且輸出掩碼中也僅有1位非零4 bit字時(shí),線性殼的相關(guān)系數(shù)為0.例如,(000α0000|00000000)→(00000000|0β000000)就是一條14輪零相關(guān)線性逼近,其中,α,β∈{0,1}4{0}4.

通過改變α和β的位置,并結(jié)合LBlock算法的結(jié)構(gòu)特點(diǎn),這里選取了其中一條14輪零相關(guān)線性逼近,對22輪LBlock進(jìn)行零相關(guān)線性分析.相對于其他零相關(guān)線性逼近,該條零相關(guān)線性逼近所涉及的線性活躍S盒的數(shù)目較少,且充分利用了圈子密鑰生成算法的冗余特征.

為了便于描述,將ei～j記為1個(gè)32 bit字,其中最左端的比特位記為第0比特,第j+1至第31比特以及第0至第i-1比特取值為0,第j比特取值為1,第i至第j-1比特取值不確定.將第i+7輪掩碼左邊32 bit取值記為

命題1對于14輪LBlock,若其輸入掩碼為,輸出掩碼為|0),則線性殼的相關(guān)系數(shù)為零.

證明 如圖2所示,從加密方向看,當(dāng)?shù)趇輪掩碼為(e12～15|0)時(shí),經(jīng)過7輪LBlock加密后,的第27比特取值應(yīng)為1.從解密方向看,當(dāng)i+14輪掩碼為(e4～7|0)時(shí),經(jīng)過7輪LBlock解密后,可得的第27比特取值為0,矛盾.因此,14輪LBlock線性特征中至少存在一對矛盾的相鄰線性掩碼,再由定理1,該條14輪線性特征所對應(yīng)的線性殼即的相關(guān)系數(shù)為零.

由于零相關(guān)線性逼近在大部分情況下為截?cái)嗔阆嚓P(guān)線性逼近,即如果找到一條對于所有密鑰都成立的零相關(guān)線性逼近,則存在一類與其相似的零相關(guān)線性逼近.事實(shí)上,由命題1可知,通過設(shè)置輸入掩碼中的3位未定義比特,即第12～14比特,以及14輪輸出掩碼中的3位未定義比特,即第4～6比特,一共可以獲得26條14輪LBlock零相關(guān)線性逼近.

3 22輪LBlock算法的多重零相關(guān)線性逼近攻擊

為了解決傳統(tǒng)零相關(guān)線性分析中普遍存在的數(shù)據(jù)復(fù)雜度高的問題,Bogdanov等提出了利用多條獨(dú)立的零相關(guān)線性逼近,來降低攻擊所需數(shù)據(jù)復(fù)雜度的方法.在文獻(xiàn)[12]的基礎(chǔ)上,這里將利用第2節(jié)得到的26條14輪零相關(guān)線性逼近,對22輪LBlock進(jìn)行密鑰恢復(fù)攻擊.

3.1 多重零相關(guān)線性分析

已知l條零相關(guān)線性逼近以及N個(gè)明、密文對,若Ti(i∈{1,2,…,l})表示滿足第i條零相關(guān)線性逼近的明、密文對的個(gè)數(shù),則有

定理2對于一個(gè)分組長度為n,且固定密鑰的分組密碼算法[8],若存在l條零相關(guān)線性逼近和N個(gè)已知明、密文對,則近似服從期望是ln,標(biāo)準(zhǔn)差是(2l)1/2n的正態(tài)分布,即

圖2 14輪LBlock零相關(guān)線性逼近

而對于一個(gè)分組長度為n,并且有l(wèi)條零相關(guān)線性逼近的隨機(jī)置換則服從期望是ln+l2n,標(biāo)準(zhǔn)差是(2l)1/2n+(2l)1/22n的正態(tài)分布為

比較式(2)和式(3),可發(fā)現(xiàn)對于固定密鑰的分組密碼算法和隨機(jī)置換,分別計(jì)算式(1)的值,前者的計(jì)算結(jié)果將明顯小于后者.事實(shí)上,如果l的值足夠大,正確密鑰導(dǎo)致的式(1)的值是最低的.

基于定理2,考慮兩個(gè)正態(tài)分布:N(μ0,σ0)和N(μ1,σ1),其中,μ0和μ1是期望,σ0和σ1為標(biāo)準(zhǔn)差, N(μ0,σ0)和N(μ1,σ1)分別為樣本對于固定密鑰的分組密碼算法和隨機(jī)置換的正態(tài)分布,并設(shè)μ0＜μ1.為判斷是從N(μ0,σ0)中還是從N(μ1,σ1)中取值,可通過比較樣本與門限值t的大小來實(shí)現(xiàn).在這種情況下,可能存在兩種錯誤判斷的概率,分別為α和β,其中,

則門限值t的取值為

與傳統(tǒng)零相關(guān)線性分析不同,多重零相關(guān)線性分析是基于正態(tài)分布的概率計(jì)算模型,來將一個(gè)固定密鑰的分組密碼算法與隨機(jī)置換區(qū)分開,避免了利用整個(gè)明文空間來準(zhǔn)確計(jì)算線性逼近成立的概率,從而可以有效地降低對算法進(jìn)行密鑰恢復(fù)攻擊所需的數(shù)據(jù)復(fù)雜度.

3.2 攻擊步驟

在對LBlock進(jìn)行多重零相關(guān)線性攻擊時(shí),將第2節(jié)得到的14輪零相關(guān)線性逼近置于算法的第5至18輪,并在14輪零相關(guān)線性逼近前添加4輪,在其后也添加4輪.

由圖2可知,14輪零相關(guān)線性逼近只與8個(gè)具體狀態(tài)位有關(guān),分別為和,其中表示第i輪中間密文左邊32 bit中第j個(gè)4 bit字的取值,其中最左側(cè)的4 bit字記為,并以同一方式定義為了通過已知明、密文對來估計(jì)線性逼近的取值,文中選取了相關(guān)子密鑰k對已知明、密文對進(jìn)行部分加、解密.若將第i輪圈子密鑰的第j個(gè)4 bit字記為,由LBlock算法可知,相關(guān)子密鑰為

對于k的每一個(gè)可能取值,執(zhí)行以下步驟:

(1)對于N對明、密文對中的每一對取值,用密鑰k部分加密1-4輪得x4=,并部分解密22-19輪得x18=,具體過程如圖3所示.其具體操作步驟如下:

(3)對于第i(i=1,2,…,26)條14輪零相關(guān)線性逼近,執(zhí)行以下步驟:

(4)若ci2＜t,則密鑰k為正確候選子密鑰,再由密鑰生成算法,并通過窮舉攻擊得到K的未知比特位.

設(shè)錯誤概率α=2-2.7,β=2-4.49,則分位數(shù)z1-α=1,z1-β=1.7.由于14輪零相關(guān)逼近共有l(wèi)=26條,分組長度n=64,由式(4)可知,門限值t的取值為

3.3 攻擊復(fù)雜度分析

攻擊的數(shù)據(jù)復(fù)雜度即攻擊所需的已知明、密文對的個(gè)數(shù),記為N,由式(5)可知,N的取值為

圖3 22輪LBlock零相關(guān)線性逼近攻擊

因此,對22輪LBlock進(jìn)行多重零相關(guān)線性攻擊的數(shù)據(jù)復(fù)雜度約為263.45個(gè)已知明文,小于整個(gè)明文空間.

攻擊的計(jì)算復(fù)雜度主要由步驟(1)和(4)決定.步驟(1)中部分加、解密相當(dāng)于1/2輪加密,對于263.45個(gè)已知明文中的每一個(gè)取值都需要用214個(gè)猜測子密鑰來計(jì)算線性逼近,計(jì)算復(fù)雜度為214×263.45×8×0.5/22≈274.99次22輪LBlock加密.步驟(4)需要進(jìn)行280×β=280×2-4.49≈275.5次加密運(yùn)算.因此,攻擊所需的總計(jì)算復(fù)雜度為274.99+275.5≈276.27次22輪LBlock加密,存儲復(fù)雜度可忽略不計(jì).當(dāng)錯誤概率α=2-2.7時(shí),成功實(shí)施攻擊的概率為1-α=1-2-2.7≈0.85.單密鑰模式下對LBlock的攻擊復(fù)雜度比較如表1所示.

表1 單密鑰模式下對LBLock算法的攻擊比較

與對LBlock的其他分析方法不同,多重零相關(guān)線性分析可以通過設(shè)置α和β的取值來決定攻擊效果.同時(shí),相對于選擇明文攻擊,多重零相關(guān)線性分析屬于已知明文攻擊,因此易于實(shí)施,這在某些場合依然是有意義的.

4 結(jié)束語

從多重零相關(guān)線性分析的角度評價(jià)了輕量級分組密碼LBlock的安全性.通過對LBlock算法結(jié)構(gòu)的研究,給出了26條14輪LBlock零相關(guān)線性逼近的構(gòu)造.基于26條零相關(guān)線性逼近,利用正態(tài)分布的概率計(jì)算模型以及中間相遇法對22輪LBlock進(jìn)行了多重零相關(guān)線性攻擊,攻擊的數(shù)據(jù)復(fù)雜度為O(263.45),小于O(264),計(jì)算復(fù)雜度為O(276.27),有效解決了零相關(guān)線性分析需要利用整個(gè)明文空間來實(shí)施攻擊的問題.

[1]陳杰,張躍宇,胡予濮.一種新的6輪AES不可能差分密碼分析方法[J].西安電子科技大學(xué)學(xué)報(bào),2006,33(4):598-601.

Chen Jie,Zhang Yueyu,Hu Yupu.A New Method for Impossible Differential Cryptanalysis of the 6-round Advanced Encryption Standard[J].Journal of Xidian University,2006,33(4):598-601.

[2]Gong Zheng,Nikova S,Law Y W.KLEIN:A New Family of Lightweight Block Ciphers[C]//Proceedings of the 7th International Workshop on RFID,Security and Privacy.Heidelberg:Springer,2011:1-18.

[3]Ojha S,Kumar N,Jain K,et al.TWIS—a Lightweight Block Cipher[C]//Proceedings of the 5th Information Systems Security.Heidelberg:Springer,2009:280-291.

[4]Guo Jian,Peyrin T,Poschmann A,et al.The LED Block Cipher[C]//Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems.Heidelberg:Springer,2011:326-341.

[5]Wu Wenling,Zhang Lei.LBlock:a Lightweight Block Cipher[C]//Proceedings of International Conference on Applied Cryptography and Networks Security.Heidelberg:Springer,2011:327-344.

[6]李艷俊.分組密碼的積分攻擊[D].北京:中國科學(xué)院軟件研究所,2012.

[7]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.Heidelberg:Springer,2012:97-108.

[8]Bogdanov A,Rijmen V.Zero Correlation Linear Cryptanalysis of Block Ciphers[DB/OL].[2013-06-12].IACR Cryptology ePrint Archive 01/2011.2011:123.

[9]Matsui M.Linear Cryptanalysis Method for DES Cipher[C]//Proceedings of EUROCRYPT.Heidelberg:Springer, 1994:386-397.

[10]Wang Yanfeng,Wu Wenling,Yu Xiaoli,et al.Security on LBlock against Biclique Cryptanalysis.[C]//Proceedings of 13th International Workshop on Information Security Application.Heidelberg:Springer,2012:1-14.

[11]Soleimany H.Zero-correlation Linear Cryptanalysis of Reduced-round LBlock.[C]//Proceedings of International Workshop on Coding and Cryptography.Heidelberg:Springer,2013:243-329.

[12]Bogdanov A,Wang Meiqin.Zero Correlation Linear Cryptanalysis with Reduced Data Complexity[C]//Proceedings of International Workshop on Fast Software Encryption.Heidelberg:Springer,2012:29-48.

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

Zhan Yingjie,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.

(編輯:齊淑娟)

Cryptanalysis of the LBlock using multiple zero-correlation linear approximations

LUO Fang,ZHOU Xueguang,OU Qingyu
(Department of Information Security,Naval University of Engineering,Wuhan 430033,China)

In order to reduce the data complexity of zero-correlation linear cryptanalysis of the LBlock, cryptanalysis of the LBlock using multiple zero-correlation linear approximations is presented.26zerocorrelations for 14 the round LBlock is proven,and its construction is given.The normal distribution probability model is applied to attack the 22 round LBlock,with the 26zero-correlations for the 14 round LBlock used as the distinguisher.The data complexity of the cryptanalysis is about 263.45known plaintexts, the computing complexity is about 276.27,and the success probability is 0.85.It is proved that the problem that the whole plaintext is needed to cryptanalyze the LBlock is solved.

lightweight block cipher;LBlock cipher;multiple zero-correlation linear approximation; cryptanalysis;data complexity

TN918.1

A

1001-2400(2014)05-0173-07

2013-07-10< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-01-12

國家自然科學(xué)基金資助項(xiàng)目(61100042,61202338);海軍工程大學(xué)自然科學(xué)基金資助項(xiàng)目(HGDQNJJ13043)

羅 芳(1983-),女,講師,E-mail:lf_0215@sina.com.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.029.html

10.3969/j.issn.1001-2400.2014.05.029