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

Generalized Independent Biclique Automated Attack Framework and Its Applications

作　　者：崔竞一 郭建胜[1,2] 刘翼鹏 

机构地区：[1]信息工程大学,郑州450001 [2]信息保障技术重点实验室,北京100072

出　　处：《计算机学报》2018年第2期349-367,共19页Chinese Journal of Computers

基　　金：博士后科学基金(2014M562582)资助~~

摘　　要：该文对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的非平衡BiclThis 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-

关 键 词：Biclique攻击 INDEPENDENT Biclique结构 广义Biclique结构 攻击框架 AES算法 LBlock算法 

分 类 号：TN918[电子电信—通信与信息系统]