自动化搜索ARX型密码差分—线性特征的模型及应用

发布时间：2018-06-18 06:01

本文选题：ARX + 差分-线性　；参考：《山东大学》2017年硕士论文

【摘要】：ARX结构是一类仅包含模加(Addition)、循环移位(Rotation)和异或(Exclusive-OR)运算的密码结构,在分组密码、流密码、Hash函数以及MAC算法中都有着广泛的应用。ARX型密码有着算法结构简单、运算效率高的特点,非常适合于软件的实现。差分-线性分析方法是在1994年的美密会上被提出的。通过将满足一定条件的高概率截断差分特征与高偏差线性逼近进行组合得到高偏差的差分-线性特征,可对部分密码算法进行有效地攻击。2016年的欧密会上,Leurent使用差分-线性分析方法,结合改进的比特划分技术,对ARX型MAC算法Chaskey进行了攻击,严重威胁了 Chaskey的安全性,体现了差分-线性分析方法对ARX型密码分析的有效性。自动化搜索技术在密码学中有着广泛的应用。尤其在近几年,随着对ARX型密码研究的深入,已形成一整套搜索该类密码差分特征和线性逼近的自动化方法,然而并没有搜索差分-线性特征的自动化工具问世。在实际应用中,将搜索差分特征的自动化技术与搜索线性逼近的自动化技术进行简单结合,以期获得长轮数的差分-线性特征的方法并不十分可行。鉴于如上现状,本文提出了自动化搜索ARX型密码差分-线性特征的模型,并给出了实现该模型的一种可行方法。同时,为验证该模型的有效性,本文将该模型应用到对ARX型MAC算法SipHash和分组密码SPECK的差分-线性分析中,给出了二者的差分-线性分析结果。对于SipHash系列算法中使用最广泛的SipHash-2-4算法,本文找到了终止化阶段4轮的多条较优的差分-线性特征。其中最优特征的绝对值仅为2-2.84，进行区分攻击仅需27.68个已知明文。此前公布的最好的分析结果为差分分析结果,其最优的差分特征概率为2-35,区分需235对选择明文。在明文消息长度不大于7字节且不考虑生成MAC的四支异或运算的情况下,本文同样给出多条较优的差分-线性特征。此外,在原始消息长度不大于7字节情况下,本文给出了 SipHash-2-4全算法的差分-线性分析结果,这是已知的对SipHash系列算法的第一个差分-线性分析结果。对于SPECK系列算法,本文分别给出了最小分组实例SPECK32/64和最大分组实例SPECK128/192、SPECK128/256的差分-线性特征。同时,结合搜索到的特征,本文给出了具体差分-线性攻击的流程、数据复杂度、存储复杂度与时间复杂度等,这同样是已知对SPECK系列算法的第一个差分-线性分析结果。
[Abstract]:ARX structure is a class of cryptographic structures that only contain modular addition, cyclic rotation and XOR exclusive ORs. ARX is widely used in block cipher, stream cipher Hash function and MAC algorithm. Very suitable for software implementation. The difference-linear analysis method was proposed at the Meimei meeting in 1994. By combining the high probability truncated difference characteristic with the high deviation linear approximation, the difference linear characteristic of high deviation is obtained. Leurent used differential linear analysis method and improved bit-partitioning technology to attack the ARX-type MAC algorithm Chaskey, which seriously threatened the security of Chaskey. The effectiveness of differential-linear analysis method for ARX cipher analysis is demonstrated. Automatic search technology is widely used in cryptography. Especially in recent years, with the development of ARX-type cryptography, a whole set of automatic methods to search for the differential characteristics and linear approximation of ARX cipher have been developed. However, there is no automatic tool to search for differential-linear features. In the practical application, it is not very feasible to combine the automatic technology of searching difference feature with the automatic technique of searching linear approximation in order to obtain the difference linear feature of long wheel number. In view of the above situation, this paper presents a model of ARX-type cryptosystem differential-linear features for automatic search, and gives a feasible method to implement the model. At the same time, in order to verify the validity of the model, this paper applies the model to the differential linear analysis of ARX-type MAC algorithm SipHash and block cipher speck, and gives their results. For the most widely used SipHash-2-4 algorithm in the SipHash series of algorithms, this paper finds several better differential-linear characteristics of four rounds in the termination stage. The absolute value of the optimal feature is only 2-2.84, and only 27.68 known plaintext is required for distinguishing attack. The best analysis result previously published is the difference analysis result, the optimal difference characteristic probability is 2-35, and 235 pairs of selected clear text are needed to distinguish. When the message length of clear text is less than 7 bytes and the four XOR operations of MAC are not considered, this paper also gives several better difference-linear characteristics. In addition, when the original message length is less than 7 bytes, the difference linear analysis results of SipHash-2-4 algorithm are given, which is the first known difference linear analysis result for SipHash series algorithms. For the SPECK series of algorithms, the differential linear characteristics of the minimum packet instance SPECK32 / 64 and the maximum packet instance SPECK128 / 192 / 256 are given respectively. At the same time, combined with the characteristics of search, this paper gives the specific differential linear attack flow, data complexity, storage complexity and time complexity, which is also the first known differential linear analysis results for speck series algorithms.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN918.1

【相似文献】