Cryptology ePrint Archive: Report 2003/125

Algebraic Attacks on Combiners with Memory and Several Outputs

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.

Category / Keywords: secret-key cryptography / algebraic attacks on stream ciphers, combiners with memory, filtered generators

Publication Info: This is the extended version of the paper that appears in ICISC 2004.

Date: received 23 Jun 2003, last revised 18 Oct 2004

Contact author: courtois at minrank org

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Version: 20041018:173902 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]