對LBloc k算法的多重零相關線性分析

羅 芳,周學廣,歐慶于

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

對LBloc k算法的多重零相關線性分析

羅 芳,周學廣,歐慶于

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

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

輕量級分組密碼;LBlock算法;多重零相關線性逼近;密碼分析;數據復雜度

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

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

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

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

1 零相關線性分析

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

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

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

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

在進行零相關線性分析時,首先需要構造相關系數為0的線性逼近,定理1給出了零相關線性逼近存在的充分條件.

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

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

為了準確計算出相關系數,要求數據復雜度N=2n,即需要利用整個明文空間來實施攻擊.因此,傳統零相關線性分析方法普遍存在數據復雜度高的問題,這也成為了該分析方法在實際應用中的障礙.

2 LBlock算法零相關線性逼近的構造

2.1 LBlock算法

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

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

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

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

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

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

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

2.2 14輪LBlock零相關線性逼近

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

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

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

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

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

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

3 22輪LBlock算法的多重零相關線性逼近攻擊

為了解決傳統零相關線性分析中普遍存在的數據復雜度高的問題,Bogdanov等提出了利用多條獨立的零相關線性逼近,來降低攻擊所需數據復雜度的方法.在文獻[12]的基礎上,這里將利用第2節得到的26條14輪零相關線性逼近,對22輪LBlock進行密鑰恢復攻擊.

3.1 多重零相關線性分析

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

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

圖2 14輪LBlock零相關線性逼近

而對于一個分組長度為n,并且有l條零相關線性逼近的隨機置換則服從期望是ln+l2n,標準差是(2l)1/2n+(2l)1/22n的正態分布為

比較式(2)和式(3),可發現對于固定密鑰的分組密碼算法和隨機置換,分別計算式(1)的值,前者的計算結果將明顯小于后者.事實上,如果l的值足夠大,正確密鑰導致的式(1)的值是最低的.

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

則門限值t的取值為

與傳統零相關線性分析不同,多重零相關線性分析是基于正態分布的概率計算模型,來將一個固定密鑰的分組密碼算法與隨機置換區分開,避免了利用整個明文空間來準確計算線性逼近成立的概率,從而可以有效地降低對算法進行密鑰恢復攻擊所需的數據復雜度.

3.2 攻擊步驟

在對LBlock進行多重零相關線性攻擊時,將第2節得到的14輪零相關線性逼近置于算法的第5至18輪,并在14輪零相關線性逼近前添加4輪,在其后也添加4輪.

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

對于k的每一個可能取值,執行以下步驟:

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

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

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

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

3.3 攻擊復雜度分析

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

圖3 22輪LBlock零相關線性逼近攻擊

因此,對22輪LBlock進行多重零相關線性攻擊的數據復雜度約為263.45個已知明文,小于整個明文空間.

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

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

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

4 結束語

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

[1]陳杰,張躍宇,胡予濮.一種新的6輪AES不可能差分密碼分析方法[J].西安電子科技大學學報,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].北京:中國科學院軟件研究所,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]詹英杰,關杰,丁林,等.對簡化版LBlock算法的相關密鑰不可能差分攻擊[J].電子與信息學報,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">網絡出版時間:

時間:2014-01-12

國家自然科學基金資助項目(61100042,61202338);海軍工程大學自然科學基金資助項目(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