Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
复制标题
DOI：
10.1007/3-540-36178-2_17
复制
发表时间：
2002-12
期刊：
影响因子：
--
通讯作者：
N. Courtois;J. Pieprzyk
中科院分区：
文献类型：
--
作者：
N. Courtois;J. Pieprzyk
最近提出的几种密码，如Rijndael和Serpent，都是用线性密钥依赖层相互连接的小S盒构建的。S盒的安全性依赖于这样一个事实，即经典的密码分析方法(如线性攻击或差分攻击)都是基于概率特征的，这使得它们的安全性随着轮数Nr的增加而指数增长。在另一个假设下，我们研究了这种密码的安全性：可以用一个超定义的代数方程组(概率为1)来描述这种密码。我们证明了这对于Serpent(由于S盒的小尺寸)和Rijndael(由于意外的代数性质)都是正确的。我们研究了已知的求解超定方程组的一般方法，例如Eurocrypt‘00的XL，并证明了它们的效率低下。然后，我们提出了一种新的方法XSL，它利用了方程的稀疏性及其特殊的结构，XSL攻击只使用概率为1的真关系，因此安全性不必随着轮数的增加而指数增长。XSL有一个参数P，根据我们的估计，P应该是一个常量，或者随着轮数的增加而缓慢增长。然后，XSL攻击将是Nr>；的多项式(或次指数)，具有一个巨大的常数，该常数在S盒子的大小中是双指数的。由于存在冗余方程，此类攻击的确切复杂性尚不清楚。尽管XSL攻击的当前版本总是提供比彻底搜索Rijndael更多的信息，但它似乎(略微)破解了256位的Serpent。我们提出了分组密码中S盒的一个新的设计准则：它们不能用一个太小或太过定义的多项式方程组来描述。
Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of roundsNrr.In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure.The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameterP, and from our estimations is seems thatPshould be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) inNr>, with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.