【作者】 刘志强；

【导师】 谷大武；

【作者基本信息】 上海交通大学 ， 计算机系统结构， 2011， 博士

【摘要】 分组密码是现代密码学的重要组成部分,是信息与网络安全中实现数据加密、消息认证及密钥管理的核心密码算法。随着差分分析方法以及线性分析方法的提出,人们对分组密码的安全性分析有了系统的研究工具。它们的出现不仅为分组密码的分析理论奠定了坚实的基础,同时也为分组密码的设计理论提供了一定的依据。此后,基于这两种分析方法的研究工作成为了分组密码的研究热点,密码学者相继提出了多种扩展方法,如截断差分分析方法、高阶差分分析方法、不可能差分分析方法、飞来去器攻击方法、矩形攻击方法、多线性分析方法、非线性分析方法、多维线性分析方法、差分-线性分析方法等。这些工作极大地推动了分组密码的分析理论的发展,从而对分组密码的设计理论提出了更高的要求,并最终促进了分组密码的发展。本文主要从两个方面研究了线性类密码分析方法。一方面,针对几种国际上比较流行的分组密码算法,我们研究了这些算法抵抗线性分析方法、多线性分析方法的能力,从而对这些算法的安全性评估起到借鉴作用;另一方面,基于已有的线性类密码分析思想和方法(如线性分析方法、多线性分析方法、多维线性分析方法、线性堆思想,等等),我们提出了一些新的、有效的组合类分析方法,这些分析方法几乎适用于各种分组密码。它们的出现将对分组密码的分析理论与设计理论起到积极的作用。论文的主要贡献如下:(1)研究了ARIA算法抵抗线性分析的能力,通过引入一种针对SPN类型分组密码的线性特征,得到了一系列4轮简化ARIA的线性特征,在此基础上,提出了针对7轮、9轮以及11轮简化ARIA的线性攻击算法。ARIA算法是韩国官方2004年公布的分组密码标准算法,主要用于轻量级环境实现和硬件系统实现。在ARIA算法的设计文档中,设计者认为不存在对8轮或8轮以上简化ARIA的线性攻击算法,而本文的结果表明这样的线性攻击是存在的。该结果是到目前为止关于ARIA算法最好的分析结果。(2)研究了SMS4算法抵抗多线性分析的能力,提出了针对22轮简化SMS4的多线性攻击算法。SMS4是用于国内无线局域网安全标准WAPI的分组密码,是国内官方公布的第一个商用密码算法。我们首次从多线性分析的角度出发来研究SMS4的安全性,通过分析SMS4的算法结构和轮函数的特性,提出了一系列18轮简化SMS4的线性特征,基于这些线性特征,我们对22轮简化SMS4进行了有效的多线性攻击并得到了关于SMS4算法较好的分析结果。(3)提出了差分-线性堆分析方法,并通过将该方法应用于SERPENT算法来证实其有效性。线性堆思想是由K. Nyberg提出的、利用具有相同输入掩码和相同输出掩码的线性特征集合来研究分组密码安全性的方法。基于该思想,我们提出了差分-线性堆的概念并引入了一种利用差分-线性堆来研究分组密码安全性的分析方法。与已有的差分-线性分析方法相比,新方法能够充分挖掘属于同一差分-线性堆的多个差分-线性特征的统计特性,从而使得该方法具有更优的数据复杂度。我们将其用于分析SERPENT算法的安全性并得到了较好的分析结果。(4)提出了差分-多线性分析方法以及差分-多维线性分析方法,通过将新方法分别应用于DES算法和SERPENT算法来证实其有效性。在现代分组密码算法的设计中,设计者往往已经考虑了算法抵抗差分分析方法、截断差分分析方法与线性分析方法的能力,分析者很难得到可用的、较多轮数的简化算法的截断差分特征或线性特征,但是,他们一般可以找到有效的、较少轮数的简化算法的这些统计特征。基于该特征,分析者就能够利用差分-线性分析方法对较多轮数的简化算法进行有效的攻击。本文将差分分析方法分别与多线性分析方法、多维线性分析方法进行有机结合,得到了新的组合类分析方法。与已有的差分-线性分析方法相比,新方法具有更优的数据复杂度。为了验证新方法的有效性,我们将其分别用于DES算法和SERPENT算法,得到了较好的分析结果。(5)提出了线性故障攻击方法,并通过将该方法应用于SERPENT算法来证实其有效性。作为旁路攻击的一种重要方法,差分故障攻击已经被广泛用于分组密码的安全性分析,但攻击者需要将故障导入在该分组密码的最后少数几轮中。本文通过研究故障攻击方法的特性,结合线性分析方法的思想,首次提出了线性故障攻击方法。与差分故障攻击方法相比,新方法能够将故障导入的轮数进一步提前并实现有效的攻击。为了验证新方法的有效性,我们将其用于分析SERPENT算法的安全性并得到了较好的分析结果。更多还原

【Abstract】 Block cipher is one of the most important components in cryptology, and it is always served as the core cryptological algorithm in the aspects such as data encryption, message authentication, key management, and so on. With the presentation of differential cryptanalysis and linear cryptanalysis, people can investigate the security of block cipher systematically. Since then, the research work based on differential cryptanalysis and linear cryptanalysis has become a hotspot in cryptology, many efforts have been made to generalize and extend these approaches in order to derive more effective crypanalytic methods such as truncated differential cryptanalysis, higher order differential cryptanalysis, impossible differential cryptanalysis, boomerang attack, rectangle attack, multiple linear cryptanalysis, non-linear cryptanalysis, multidimensional linear cryptanalysis, differential-linear cryptanalysis, and so on. Such work has dramatically pushed forward the analysis theory of block cipher, resulting in considerable improvement of the design theory of block cipher and finally facilitating the development of block cipher greatly.In this dissertation, we work on linear cryptanalysis and its extensions from two aspects. Firstly, we study the security of some well-known block ciphers by means of linear cryptanalysis and multiple linear cryptanalysis, which may be helpful in the security evaluation of these ciphers. Moreover, we propose some new effective cryptanalytic methods based on the approaches such as linear cryptanalysis, multiple linear cryptanalysis, multidimensional linear cryptanalysis, linear hull, and so on. As a matter of fact, our novel cryptanalytic tools can be used in the security analysis of various block ciphers. The highlights of this dissertation are listed as follows:(1) The block cipher ARIA was selected as a data encryption standard by the Korean Ministry of Commerce, Industry and Energy in 2004. In this dissertation, we present a kind of special linear characteristics for SPN block ciphers and then derive a series of 4-round linear characteristics of ARIA. Based on such 4-round linear characteristics, we propose attacks on 7-round, 9-round and 11-round ARIA respectively. The designers of ARIA expect that there isn’t any effective attack on 8 or more rounds of ARIA by means of linear cryptanalysis. However, our work shows that such attacks do exist. Moreover, our cryptanalytic results are the best known cryptanalytic results of ARIA so far.(2) SMS4, the first commercial cryptological algorithm released by Chinese government in 2006, is an underlying block cipher used in WLAN Authentication and Privacy Infrastructure (WAPI), the Chinese national standard for WLAN. In this dissertation, we study the security of the block cipher SMS4 against multiple linear crytanalysis for the first time. By analyzing the properties of the structure and the round function of SMS4, we find a series of 5-round iterative linear characteristics of the cipher, from which a list of 18-round linear characteristics of the cipher can be constructed. With the help of such 18-round linear characteristics, we mount an effective key recovery attack on 22-round SMS4. Compared with the previously best cryptanalytic results on 22-round SMS4, our result has better data complexity as well as comparable time complexity and memory complexity.(3) In 1994, K. Nyberg proposed a cryptanalytic approach by using a set of linear characteristics with the same input mask and the same output mask which is denoted as linear hull. Following this idea, we introduce the concept of differential-linear hull and the cryptanalytic method by adopting differential-linear hull. In comparison with differential-linear crypatanlysis, our new method can exploit more statistical properties from a differential-linear hull, thus leading to a better data complexity. For the purpose of illustration, we mount an effective key recovery attack on reduced-round SERPENT by applying the new method.(4) Generally, modern block ciphers are devised to avoid good long truncated differential and linear characteristics in order to resist traditional attacks such as differential, truncated differential and linear cryptanalysis, but usually good short ones still exist. According to differential-linear cryptanalysis, an adversary can obtain long cryptanalytic distinguishers by concatenating good short truncated differential and linear characteristics, which leads to more powerful attacks on block ciphers. In this dissertation, we present several extensions to differential-linear cryptanalysis, called differential-multiple linear cryptanalysis and differential-multidimensional linear cryptanalysis, by combining differential and multiple linear cryptanalysis, differential and multidimensional linear cryptanalysis respectively. Compared with differential-linear cryptanalysis, our extensions improve the data complexity of cryptanalysis. As a demonstration, we use the new approaches to cryptanalyze reduced-round DES and SERPENT respectively, and the corresponding cryptanalytic results confirm the effectiveness of these approaches.(5) As one of the most important approaches in side channel attacks, differential fault analysis (DFA) has already been applied to attack many block ciphers by means of inducing some faults at the last few rounds of block ciphers. In this dissertation, we present a new fault attack on block ciphers called linear fault analysis (LFA), in which linear characteristics for some consecutive rounds of a block cipher will be utilized instead of exploiting differential distributions of S-Boxes within the block cipher in DFA. Basically, the new approach can handle the case that faults are induced several rounds earlier compared to DFA. For the sake of verification, we mount a key recovery attack on SERPENT by adopting LFA and achieve a good cryptanalytic result.更多还原