Fast Algebraic Attacks on Stream Ciphers with Linear Feedback
Fast Algebraic Attacks on Stream Ciphers with Linear Feedback
复制标题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
N. Courtois
中科院分区：
文献类型：
--
作者：
N. Courtois
.许多流行的流密码将滤波器/组合器应用于一个或多个LFSR的状态。如果存在涉及密钥/状态位和输出位的多变量关系，则对此类密码[10，11]的代数攻击是可能的。Courtois，Meier，Krause和Armknecht [1，2，10，11]最近的论文表明，对于几种对所有已知攻击免疫的著名流密码结构，存在这样的关系。特别是，它们允许使用LFSR和完全“精心设计”的布尔函数来破解两个密码：Toyocrypt和LILI-128，参见[10，11]。令人惊讶的是，类似的代数攻击也存在于蓝牙密钥流生成器E0 [1]中使用的有状态组合器构造中。更一般地说，在[2]中，证明了它们可以在多项式时间内打破任何具有固定数量输入和固定数量存储位的组合器。在本文中，我们提出了一种方法，可以大幅降低所有这些攻击的复杂性。我们表明，当已知的密钥流位是连续的，方程的一个重要部分将具有递归结构，这允许部分取代通常的次立方高斯算法消除单项式，由一个更快的，基本上是线性的，版本的Berlekamp-Massey算法。新方法给出了迄今为止对Toyocrypt、LILI-128和E0密码中使用的密钥流生成器提出的最快攻击。此外，我们提出了两个新的快速通用代数攻击的流密码使用布尔函数，适用于当度和/或输入的数量不是太大。尼斯湖水怪E0蓝牙
. Many popular stream ciphers apply a filter/combiner to the state of one or several LFSRs. Algebraic attacks on such ciphers [10,11] are possible, if there is a multivariate relation involving the key/state bits and the output bits. Recent papers by Courtois, Meier, Krause and Armknecht [1,2,10,11] show that such relations exist for several well known constructions of stream ciphers immune to all previously known attacks. In particular, they allow to break two ciphers using LFSRs and completely “well designed” Boolean functions: Toyocrypt and LILI-128, see [10,11]. Surprisingly, similar algebraic attacks exist also for the stateful combiner construction used in Bluetooth keystream generator E0 [1]. More generally, in [2] it is proven that they can break in polynomial time, any combiner with a fixed number of inputs and a fixed number of memory bits. In this paper we present a method that allows to substantially reduce the complexity of all these attacks. We show that when the known keystream bits are consecutive, an important part of the equations will have a recursive structure, and this allows to partially replace the usual sub-cubic Gaussian algorithms for eliminating the monomials, by a much faster, essentially linear, version of the Berlekamp-Massey algorithm. The new method gives the fastest attack proposed so far for Toyocrypt, LILI-128 and the keystream generator that is used in E0 cipher. Moreover we present two new fast general algebraic attacks for stream ciphers using Boolean functions, applicable when the degree and/or the number of inputs is not too big. Nessie, E0, Bluetooth.