Welcome to the resource topic for 2003/125
Title:
Algebraic Attacks on Combiners with Memory and Several Outputs
Authors: Nicolas T. Courtois
Abstract:Algebraic attacks on stream ciphers proposed by Courtois et al. recover the key by solving an overdefined system of multivariate equations. Such attacks can break several interesting cases of LFSR-based stream ciphers, when the output is obtained by a Boolean function. As suggested independently by Courtois and Armknecht, this approach can be successfully extended also to combiners with memory, provided the number of memory bits is small. At Crypto 2003, Krause and Armknecht show that, for ciphers built with LFSRs and an arbitrary combiner using a subset of k LFSR state bits, and with l memory bits, a polynomial attack always do exist when k and l are fixed. Yet this attack becomes very quickly impractical: already when k and l exceed about 4. In this paper we give a much simpler proof of this result and prove a more general theorem. We show that much faster algebraic attacks exist for any cipher that (in order to be fast) outputs several bits at a time. In practice our results substantially reduce the complexity of the best attack known on four well known constructions of stream ciphers when the number of outputs is increased. We present attacks on modified versions of Snow, E0, LILI-128, Turing, and some other ciphers.
ePrint: https://eprint.iacr.org/2003/125
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .