• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>8th International Conference on the Theory and Application of Cryptology and Information Security, Dec 1-5, 2002, Queenstown, New Zealand >Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
【24h】

Cryptanalysis of Block Ciphers with Overdefined Systems of Equations

机译：具有超定义方程组的分组密码的密码分析

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 rounds N_r. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdeflned 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 parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in N_r, 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.
机译：几种最近提出的密码，例如Rijndael和Serpent，都由小型S-box层构成，这些S-box层由依赖于线性密钥的层互连。它们的安全性取决于以下事实：经典的密码分析方法（例如线性或差分攻击）基于概率特征，这使得其安全性随着N_r轮数呈指数增长。在本文中，我们在另外一个假设下研究了这种密码的安全性：S-box可以用代数方程的超定义系统描述（概率为1的情况为真）。我们证明，对于蛇（由于S盒的尺寸较小）和Rijndael（由于意外的代数性质）都是如此。我们研究了已知的解决超定义方程组的通用方法，例如Eurocrypt'00的XL，并证明了它们的无效性。然后，我们引入了一种称为XSL的新方法，该方法使用了方程的稀疏性及其特定结构。 XSL攻击仅使用概率为1的真关系，因此安全性不必在回合数中呈指数增长。 XSL具有参数P，根据我们的估计，似乎P应该是常数，或者随着回合数的增加而非常缓慢地增长。 XSL攻击将是N_r中的多项式（或次指数），其巨大常数在S-box的大小上是双指数的。由于冗余方程式，这种攻击的确切复杂性未知。尽管给出的XSL攻击版本总是比穷尽Rijndael的搜索要多，但它似乎（勉强地）破坏了256位Serpent。我们为分组密码中的S盒设计提出了一个新的标准：不应由太小或定义过多的多项式方程组来描述它们。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号