广义Independent Biclique攻击框架及其应用

Generalized Independent Biclique Automated Attack Framework and Its Applications

该文对Biclique攻击框架及其实现方法进行了研究.Biclique攻击是一种结合Biclique初始结构与中间相遇攻击的一种攻击方法,有平衡Biclique攻击、非平衡Biclique攻击、Star攻击等多种攻击形式.该文提出了广义Biclique结构的概念,对Biclique结构重新进行了定义,涵盖了现有Biclique结构.同时提出了一种广义Biclique结构分类方式,按照维数分为高维Biclique结构与低维Biclique结构.通过进一步研究发现,高维Biclique结构可由低维Biclique结构直接构造得到,从而提出了一种高维Biclique结构构造方法,降低了结构构造过程的复杂度,同时利用该方法所得到的Biclique结构,结合计算与预计算技术,可以给出时间复杂度更优的Biclique攻击结果.在此基础上,设计并提出了一个广义Independent Biclique攻击框架,借助自动化实现技术能够面向比特构造出算法包括平衡Biclique结构、Star结构、非平衡Biclique结构在内的多种结构,同时能够给出算法在广义Biclique攻击下的安全性分析结果.最后,以LBlock算法为例,利用框架综合分析了其在Biclique攻击下的安全性,同时改进了AES-128算法基于Star结构的相关分析结果.获得分析结果如下:(1)针对LBlock算法,分别给出了两个低维Biclique攻击结果与两个高维Biclique攻击结果.构造了明文方向6轮4维的平衡Biclique结构,给出了数据复杂度更优的平衡Biclique攻击结果,其时间复杂度为2^(78.425)次全轮LBlock算法加密,数据复杂度为2^(40)选择明文;构造了明文方向6轮4维Star结构,给出了首个最低数据复杂度下全轮LBlock算法攻击结果,时间复杂度为2^(78.66)次全轮LBlock算法加密,数据复杂度为2个已知明文;构造了明文方向6轮8维平衡Biclique结构,给出了目前最优的全轮LBlock算法分析结果,其时间复杂度为2^(78.14)次全轮LBlock算法加密,数据复杂度为2^(60)个选择明文;构造了明文方向6轮规模2~4×2~8的非平衡Biclique结构,在2^(40)个选择明文条件下,给出了时间复杂度为2^(78.24)的全轮LBlock算法分析结果;(2)针对AES-128算法,改进了算法在Star攻击下的安全性.通过构造密文方向2.5轮Star结构代替明文方向的2轮Star结构,改进了最低数据复杂度下全轮AES-128的分析结果,其时间复杂度为2^(126.66)次全轮AES加密,数据复杂度为2个已知明文.

This paper researches on the automated attack framework of Biclique cryptanalysis and its implementation method.Biclique cryptanalysis is a kind of meet-in-the-middle attack with the initial contractures such as balanced Biclique,unbalanced Biclique and Star.In this paper,a new concept was proposed to define all kinds of Bicliques,named generalized Biclique.The generalized Biclique contained the Bicliques known before such as balanced Biclique,unbalanced Biclique and Star.And a classification of generalized Bicliques was proposed.The Bicliques were divided intotwo broad categories:high-dimension Bicliques and low-dimension Bicliques which are decided by the number of differential characteristics used in the structures while constructing the Bicliques.Furthermore,the further study showed that high-dimension Bicliques could be constructed by two or more low-dimension Bicliques,but not to exhaustively search the differential characteristics repeatedly.Based on this,a new method used to construct high-dimension Biclique was proposed to reduce the complexity in constructing Bicliques.At the same time,with the usage of the Bicliques constructed by this method,the Biclique attack could reach a better time complexity combined with precomputation and recomputation technique.Based on this method,ageneralized Independent Biclique framework was designed.By programming,the bit-oriented Bicliques including balanced Biclique,unbalanced Biclique and Star could be constructed.And the attacks based on these Bicliques could be given at the same time.In the end,take LBlock for an example.By using the framework proposed in this paper,the security of LBlock under various Biclique attacks was analyzed automatically and the best attack on full-round LBlock was given.And the security of AES-128 under Biclique attack based on Star was improved.The details are as follows:As for LBlock,the framework firstly proposed two attacks on LBlock based on 4-dimension Bicliques and gave two attacks based on 8-dimension Bicliques then.A new 6-round 4-dimension balanced Biclique was constructed to improve the attack on full-round LBlock with a lower data complexity.The time complexity is 2^(78.425) full-round LBlock encryptions and the data complexity is 2^(40) chosen plaintexts.Based on 6-round 4-dimension Star,with the knowledge of 2 known plaintexts,the first Biclique attack of the full-round LBlock with minimum data complexity was given with the time complexity of 2^(78.66) full-round LBlock encryptions.The 6-round 8-dimension balanced Biclique was constructed and the framework gave the best attack on full-round LBlock known before. The time complexity and data complexity were 2^(78.14) full-round LBlock encryptions,2^(60) chosen plaintexts respectively.Finally,based on 6-round unbalanced Biclique with the size of 2~4×2~8,the attack on full-round LBlock was presented with a time complexity of2^(78.24) full-round LBlock encryptions and a data complexity of 2^(40) chosen plaintexts respectively.As for AES-128,the security of AES-128 under Star attack was imporved.There was a2.5-round 8-dimension Star at the backward direction which was used to replace the 2-round8-dimension Star at the forward direction.Based on this initial structure,the Star attack on AES-128 was improved with a time complexity of 2^(126.66) full-round AES-128 encryptions and a data complexity of 2 known plaintexts respectively.