zbMATH — the first resource for mathematics

Fast algebraic attacks on stream ciphers with linear feedback. (English) Zbl 1122.94365
Boneh, Dan (ed.), Advances in cryptology – CRYPTO 2003. 23rd annual international cryptology conference, Santa Barbara, California, USA, August 17–21, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40674-3/pbk). Lect. Notes Comput. Sci. 2729, 176-194 (2003).
Summary: Many popular stream ciphers apply a filter/combiner to the state of one or several LFSRs. Algebraic attacks on such ciphers are possible, if there is a multivariate relation involving the key/state bits and the output bits. F. Armknecht [A linearization attack on the Bluetooth key stream generator, Report 2002/191, eprint.iacr.org/2002/191/], Armknecht and M. Krause [in Advances in cryptology – CRYPTO 2003, Lect. Notes Comput. Sci. 2729, 162–175 (2003; Zbl 1122.94346], N. Courtois [Lect. Notes Comput. Sci. 2587, 182–199 (2003; Zbl 1031.94515); updated version available at eprint.iacr.org/2002/087/], and N. T. Courtois and W. Meier, Lect. Notes Comput. Sci. 2656, 345–359 (2003; Zbl 1038.94525); extended version available at minrank.org/toyolili.pdf] 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 N. T. Courtois, loc. cit; N. T. Courtois and W. Meier, loc. cit.]. similar algebraic attacks exist also for the stateful combiner construction used in Bluetooth keystream generator \(E_0\) [F. Armknecht, loc. cit.]. More generally, in [F. Armknecht and M. Krause, loc. cit.] 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.
For the entire collection see [Zbl 1027.00041].

94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
Full Text: DOI