多维零相关线性分析模型的改进及在23轮LBlock-s算法中的应用

Improved Multidimensional Zero-Correlation Linear Cryptanalysis and Applications to 23-Round LBlock-s

基于相关性为零的线性逼近的多维零相关线性密码分析是目前最重要的分组密码分析手段之一.该文主要对多维零相关线性分析模型的密钥恢复阶段进行了深入的研究,通过定义等价密钥的距离来刻画等价密钥在压缩表达式中的位置关系,进一步约简区分器候选集合同时优化密钥猜测顺序,从而改进了原有的多维零相关线性分析的攻击模型.改进的模型首先找到所有最长的多维零相关线性区分器,然后利用密钥编排算法求得密钥恢复阶段所涉及的独立猜测密钥量,以此筛选区分器候选集合.最后,根据等价密钥的距离对候选区分器进行再次筛选,同时得到相应的密钥猜测顺序.LBlock-s算法是CAESAR竞赛中所提交的认证加密算法LAC的核心分组算法.与Lblock算法不同,LBlock-s采用具有更快混淆速度的密钥编排算法.基于改进的优化模型,该文分析了该算法抵抗多维零相关线性攻击的能力.研究表明,攻击23轮LBlock-s算法所需的数据复杂度为2^(62.3)个选择明文,时间复杂度为2^(73.75)次23轮LBlock-s加密,存储复杂度为2^(56)字节.这是目前针对LBlock-s算法的最优攻击结果.

Multidimensional zero-correlation linear cryptanalysis is a novel promising technique for block cipher.The distinguishing property used in the multidimensional zero-correlation linear cryptanalysis is the existence of zero-correlation linear hulls over a part of the cipher.In general,we take advantage of the partial-compression technique and the equivalent relations of guessed keys to reduce the complexity in the key recovery attack.In this paper,we mainly deeply research techniques in the key recovery attack and give an improved model of multidimensional zero-correlation linear cryptanalysis.For most ciphers,there are a large number of the longest zero-correlation linear hulls with the same dimension.The active position of the zero-correlation linear hull and key schedule algorithm decide the number of guessed keys and influence the resultof security evaluation.The existing model regards the distinguishers with the least independent guessed keys as the optimal distinguishers.However,we found that the location of the equivalent keys in the compress expression and the order of guessed keys in partial-compression have an important influence on complexity.We introduced a new definition of the distance of equivalent keys.The distance of equivalent keys and is the number of extra guessed keys to obtain the compression of and after guessing one of them.Obviously,the distance of equivalent keys is proportional to the number of extra guessed keys.According to all the distance of equivalent keys,we can sieve to optimal distinguishers and obtain the order of guessed keys.In improved attack model,the following steps are processed to obtain the multidimensional zero-correlation linear attack on r-round cipher:Step1,find out all the longest multidimensional zero-correlation linear distinguishers for cipher by using the matrix method or other properties of encryption algorithm.Step2,expand the distinguisher to r-round and compute the number of related round keys.Save distinguishers with the least number of keys and the round number of partial encryption/decryption in set S.Step3,obtain the distinguishers with the least independent guessed keys fromSby taking the key schedule algorithm and save the result in set O.Step4,minimize the set Oto an optimal set Lby using the distance of the equivalent keys.We need to compute all the distance of the equivalent keys.The distinguishers with the shortest distance will be saved.Step5,choose an element in set Lto implement the key recovery attack.According to distances,we get the order of guessed keys.Obviously,the equivalent keys with the short distance should be guessed firstly.To demonstrate the practical impact of our attack's model,we applied the improved multidimensional zero-correlation linear cryptanalysis model to 23-round LBlock-s.LBlock-s is the kernel block cipher of the authentication encryption algorithm LAC.LBlock-s is an improved version of LBlock with 64-bit block size and 80-bit key size.The general structure of LBlock-s is a variant of Feistel Network.The number of iterative rounds is 32.Different from the LBlock,LBlock-s adopts an improved key schedule algorithm with a faster diffusion speed.We obtained a key recovery attack on 23-round LBlock-s by adding 5-round before and appending4-round after the 14-round distinguisher(0a000000,00000000)→(00000000,0000000b).The result shows that the multidimensional zero-correlation linear attack on 23-round LBlock-s requires 2^(62.3) known plaintexts,2^(73.75) 23-round LBlock-s encryption and 2^(56) bytes memory.As far as we know,this is the currently best result on LBlock-s.