对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