分组密码算法几种分析模型的研究

发布时间：2018-05-26 16:26

本文选题：分组密码 + 线性分析　；参考：《山东大学》2017年博士论文

【摘要】：分组密码算法是保证当今网络空间中信息私密性的一类重要的密码算法,密码设计与密码分析是研究分组密码算法的两个主要方面,两者相辅相成,不断推动对称密码算法体系的发展。本文主要研究分组密码算法的安全性分析方法,对几类重要的分析模型的攻击过程或者是攻击使用的区分器进行改进。具体研究的分析模型包括线性分析、多维线性分析、多维零相关线性分析、不可能差分分析、零相关分析以及积分分析,相关工作为(1)改进了卡方法多维线性分析模型以及多维零相关线性分析模型的攻击过程;(2)将动态密钥猜测技术引入到面向比特的分组密码算法的线性分析模型中并对Simon进行了改进的线性分析,有效的降低了攻击的时间复杂度;(3)对不可能差分区分器、零相关区分器、积分区分器之间的关系进行了进一步研究,提出了零相关区分器向积分区分器转化的一般方法,并建立了 Feistel-type算法不可能差分区分器与零相关区分器之间更有效的等价条件。·改进卡方法多维线性分析以及多维零相关分析模型:多维线性分析和多维零相关线性分析是攻击分组密码算法的两种重要的分析模型,在使用卡方法的多维线性分析模型中(或者多维零相关线性分析模型),用来区分正确密钥和错误密钥的统计数是从多维区分器的概率分布情况计算得出。而在本文中,我们提出了一种计算统计数更简单的方法:在随机的明文空间下,从多维(零相关)线性路线的试验的相关系数出发,计算最终的统计数。这样,可以省掉计算概率分布的过程,如果在计算每条路线相关系数的时候,将FFT技术引入的话,可以降低distillation阶段的时间复杂度。为了说明我们新模型的有效性,我们使用多维零相关线性分析方法对具有双射轮函数且模加(或异或)轮密钥的Feistel结构进行了一般性攻击,对于模加密钥的情况,我们的结构攻击在轮数上是最优的;我们还分析了 CAST-256,将其多维零相关分析结果从28轮扩展到了 29轮,改进了一轮攻击,虽然与已有的29轮多重零相关分析结果具有相近的复杂度,但是我们的攻击对区分器没有独立假设,是在无假设条件下最优的攻击结果。·利用动态密钥猜测技术改进对Simon的线性分析:Simon是美国国家安全局(NSA)在2013年提出的轻量级分组密码算法,自出现起就吸引了广大密码学者的注意力,至今已存在许多的分析结果,包括差分分析、线性分析、不可能差分分析、积分分析等。在本文中,我们将动态密钥猜测技术(该思想提出时是与差分分析结合,有效的改进了对Simon的差分分析结果)引入到面向比特的分组密码算法的线性分析模型中并对Simon进行了改进的线性分析,有效的降低了攻击的时间复杂度。基本思路是:首先建立线性区分器的活性比特向两边扩展几轮后的布尔函数,发现其中存在许多"与"运算,通过猜测"与" 一边的密钥来简化布尔函数,进而使得针对不同的情况,猜测不同的密钥值,可以有效的降低密钥的平均猜测量,从而降低时间复杂度。我们改进了Simon算法所有10个版本的线性分析结果,具体为可以攻击23轮SIMON32/64,24 轮 SIMON48/72,25 轮 SIMON48/96,30 轮 SIMON64/96,31 轮 SImON64/128,37 轮 SImON96/96,38 轮 SImON96/144,49 轮SIMON128/128,51 轮 SIMON128/192 以及 53 轮 SIMON128/256。对大多数版本来说,我们的攻击在轮数上是最优的。·零相关、不可能差分、积分区分器的新关系:零相关(ZC)、不可能(ID)以及积分(IG)分析方法也是分析分组密码算法的三种重要模型,最近几年,三种分析模型攻击使用的区分器之间的关系成为密码学者关注的焦点之一。在ASIACRYPT'12上,Bogdanov等人给出了零相关路线与积分路线的一个基本关系,可以从输入掩码与输出掩码相互独立的零相关路线推导出一条积分路线。在ACNS'14上,Blondeau等人使用矩阵表示法,给出了几类结构的不可能差分路线与零相关路线的等价条件。在CRYPTO'15上,Sun等人也给出了针对这几个分析方法区分器等价关系的结论。在本文中,我们(1)针对具有非独立的输入输出掩码的零相关路线转化为积分路线的方法进行了深入研究,并给出了将零相关路线转化为积分路线的更容易的方法,并给出了 TEA、XTEA和HIGHT的新的积分路线;(2)使用可逆的矩阵构造Feistel-type结构不可能差分路线与零相关路线等价性条件,与之前的置换矩阵相比,可以覆盖更多算法。利用此方法,成功利用算法自身的特点解释了 SMS4-like、MARS-like、Skipjack算法Rule-A结构和Rule-B结构中不可能差分路线与零相关路线的等价性问题;同时,还利用Four-Cell的18轮不可能差分路线推导出了其18轮零相关路线,远远长于之前的12轮路线。
[Abstract]:Block cipher algorithm is one of the most important cryptographic algorithms that guarantee the privacy of information in today's network space. Cryptographic design and cryptanalysis are two main aspects of the study of block cipher algorithms. Both complement each other and constantly promote the development of symmetric cryptographic algorithms. This paper mainly studies the security analysis method of block cipher algorithms. Several important types of analysis model attack process or the discriminator used in attack are improved. The analysis model of specific research includes linear analysis, multidimensional linear analysis, multidimensional zero correlation linear analysis, impossible difference analysis, zero correlation analysis and integral analysis. The related work improves the multidimensional linear analysis model of card method (1). And the attack process of the multidimensional zero correlation linear analysis model; (2) introducing the dynamic key guessing technique into the linear analysis model of the bit oriented block cipher algorithm and improving the linear analysis of Simon, effectively reducing the time complexity of the attack; (3) the integral division, the zero correlation discriminator and the integral distinction The relationship between the devices is further studied, and the general method of transforming the zero correlation diffuser into the zoning partition is put forward, and the more effective equivalence conditions between the Feistel-type algorithm and the zero correlation discriminator are established. Analysis and multidimensional zero correlation linear analysis are two important analysis models for the attack block cipher algorithm. In the multidimensional linear analysis model using the card method (or multidimensional zero correlation linear analysis model), the statistical number of the correct key and the error key is calculated from the probability distribution of the multidimensional diffuser. In this paper, we propose a simpler method for calculating statistics: in the random clear text space, the final statistics are calculated from the correlation coefficient of the multidimensional (zero correlation) linear route. In this way, the process of calculating the probability distribution can be eliminated. If the FFT technology is introduced in the calculation of the correlation coefficient of each route, We can reduce the time complexity of the distillation phase. In order to illustrate the effectiveness of our new model, we use the multidimensional zero correlation linear analysis method to attack the Feistel structure with double ejection function and the mode plus (or or otherwise) key. For the case of encryption key, our structural attack is the best in the number of wheels. We also analyzed the CAST-256, and expanded its multidimensional zero correlation analysis from 28 round to 29 round, improved a round of attack, although it has a similar complexity with the existing 29 round multiple zero correlation analysis results, but our attack has no independent hypothesis, it is the optimal attack result under no hypothesis. Simon is a lightweight block cipher algorithm proposed by the National Security Administration (NSA) of the United States in 2013. It has attracted the attention of many cryptography scholars since it appeared in 2013. There have been many analysis results, including differential analysis, linear analysis, impossible difference analysis, integral analysis, etc. In this paper, we introduce the dynamic key guessing technique (the idea is combined with the difference analysis, improve the difference analysis of Simon effectively) into the linear analysis model of the bit based block cipher algorithm and improve the linear analysis of the Simon, which effectively reduces the time complexity of the attack. It is first established that the active bits of the linear differentiator extend the Boolean function after several rounds on both sides. It is found that there are many "and" operations. By guessing the key of "and", the Boolean function is simplified, and then the average guessing measurement of the key can be effectively reduced by guessing the different key values in different situations and reducing the time of the key. Inter complexity. We improved the linear analysis results of all 10 versions of the Simon algorithm, specifically for the 23 wheel SIMON32/64,24 wheel SIMON48/72,25 wheel SIMON48/96,30 wheel SIMON64/96,31 wheel SImON64/128,37 wheel SImON96/96,38 wheel SImON96/144,49 wheel SIMON128/128,51 wheel SIMON128/192 to the 53 wheel SIMON128/256. pair. In most versions, our attack is the best in the number of wheels. Zero correlation, impossible difference. The new relation of integrator: zero correlation (ZC), ID and IG analysis are also the three important models for analyzing block cipher algorithm. In the last few years, the relationship between the three analysis model attacks is the relationship between the discriminator used. In ASIACRYPT'12, Bogdanov and others give a basic relationship between the zero correlation and the integral route. We can derive an integral route from the independent zero correlation route of the input mask and the output mask. On ACNS'14, Blondeau and other people use matrix representation to give several kinds of structure. The equivalent condition of the possible difference route and the zero correlation route is possible. On CRYPTO'15, Sun et al. Also gives the conclusion of the discriminator equivalence relation for these analysis methods. In this paper, we (1) have studied the method of transforming the zero correlation route of the non independent input and output mask into the integral route. The correlation route is more easy to transform into integral route, and the new integration route of TEA, XTEA and HIGHT is given. (2) the equivalent condition of the impossible difference route with the zero correlation route is constructed by using a reversible matrix. Compared with the previous substitution matrix, it can cover more algorithms. By this method, the algorithm can be used successfully. Its own characteristics explain the equivalence of the SMS4-like, MARS-like, Skipjack algorithm Rule-A structure and the zero correlation route in the Rule-B structure. At the same time, it also derives its 18 round zero correlation route by using the 18 round of the impossible difference route of Four-Cell, which is far longer than the previous 12 wheel route.
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TN918.1

【相似文献】