应用MILP方法搜索基于分离特性的算法积分区分器

发布时间：2018-06-05 22:16

本文选题：积分分析 + 分离特性　；参考：《山东大学》2017年硕士论文

【摘要】：2015年的欧密会上,密码学者Todo将传统的积分分析进行推广,提出了分离特性的概念。由于分离特性可以更加明确地刻画介于"活跃"和"零和"之间的隐含性质,所以可以应用在使用了非双射、比特级或低次数部件的分组密码算法的分析中。同年的美密会上,Todo考虑S盒为公开函数,首次在理论上成功地分析了 MISTY1的全轮算法。FSE2016,日本学者Todo和Morri提出比特级分离特性,更细致地利用了算法的内部结构。之后,Sun和Wang将S盒的代数标准型和分离特性的定义相结合,提出了借助表的比特级分离特性。2016年的亚密会中,Xiang等将混合整数线性规划的思想应用到比特级分离特性的搜索中。Sun等通过刻画复杂线性层和模加运算中比特级分离特性的传递模型,分析了比特级分离特性在SPN算法和ARX类算法分析中的适用性,使得该方法能够分析更为广泛的分组密码算法。本文主要研究了三种密码算法在比特级分离特性分析下的安全程度。根据已知的发表文献,本文首次研究了 Kuznyechik和Chaskey算法的分离特性,找到了轮数均为4的积分区分器。对于SPARX算法,其作者在设计之初就进行了分离特性分析。本文采用了比特级分离特性进行分析,得到了与设计文档一致的分析结果,表明在比特级别上考虑分离特性不一定能够改进分析结果。Kuznyechik算法为SPN结构,S盒为8比特的替换,线性层为有限域上的乘法。Chaskey和SPARX为ARX算法,由模加、循环移位和轮密钥异或组成。本文通过分析比特级分离特性在这些算法模块之间的传递方式,利用混合线性整数规划搜索积分区分器。此外,对于Serpent、PRESENT和Noekeon等算法的已有较好积分区分器,本文通过综合分析算法的结构模块和密钥生成方案进行了密钥恢复分析,分别攻击了12轮、9轮和7轮的相应算法。
[Abstract]:At the 2015 Euclidean meeting, cryptographer Todo extended the traditional integral analysis and proposed the concept of separation characteristics. Since the separation property can more clearly characterize the implicit properties between "active" and "zero sum", it can be applied to the analysis of block cipher algorithms using non-bijective, bit-level or low-order components. In the same year, considering S-box as an open function, Todo first successfully analyzed the full-wheel algorithm of MISTY1. FSE 2016. The Japanese scholars Todo and Morri put forward the characteristic of special order separation, and used the inner structure of the algorithm in more detail. Sun and Wang then combined the algebraic canonical form of the S-box with the definition of the separation property. The idea of mixed integer linear programming (MILP) is applied to the search of bitt order separation properties by characterizing complex linear layers and bit-gradations in modular addition operations by characterizing complex linear layers and modular addition. The transfer model of the separation characteristics, The applicability of bit-order separation in the analysis of SPN algorithm and ARX class algorithm is analyzed, which makes it possible to analyze a wider range of block cipher algorithms. This paper mainly studies the security degree of three cryptographic algorithms under the analysis of bit-level separation characteristics. Based on the known literatures, the separation characteristics of Kuznyechik and Chaskey algorithms are studied for the first time, and an integral discriminator with 4 wheels is found. For the SPARX algorithm, the author analyzed the separation characteristics at the beginning of the design. In this paper, we analyze the BST separation characteristics, and get the analysis results consistent with the design documents. It shows that considering the separation characteristics at the bit level is not necessarily able to improve the analysis result. Kuznyechik algorithm is an 8-bit replacement for the S-box with SPN structure. The linear layer is multiplication over finite fields. Chaskey and SPARX are ARX algorithms, which consist of modular addition, cyclic shift and wheel key XOR. In this paper, by analyzing the transfer of bit-order separation between these algorithms, the mixed linear integer programming is used to search the integral discriminator. In addition, for the existing better integral discriminators of Serpentine preset and Noekeon algorithms, this paper analyzes the key recovery by synthetically analyzing the structure module and the key generation scheme of the algorithm, and attacks the corresponding algorithms of 12 rounds, 9 rounds and 7 rounds, respectively.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN918.1

【相似文献】