Paper 2003/125

Algebraic Attacks on Combiners with Memory and Several Outputs

Nicolas T. Courtois


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.

Note: I wish to thank Willi Meier and the reviewers of Crypto 2004, SAC 2004 and ICISC 2004.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. This is the extended version of the paper that appears in ICISC 2004.
algebraic attacks on stream cipherscombiners with memoryfiltered generators
Contact author(s)
courtois @ minrank org
2004-10-18: last of 7 revisions
2003-06-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas T.  Courtois},
      title = {Algebraic Attacks on Combiners with Memory and Several Outputs},
      howpublished = {Cryptology ePrint Archive, Paper 2003/125},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.