CryptoDB
Algebraic Attacks on Combiners with Memory and Several Outputs
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2003-11840,
title={Algebraic Attacks on Combiners with Memory and Several Outputs},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / algebraic attacks on stream ciphers, combiners with memory, filtered generators},
url={http://eprint.iacr.org/2003/125},
note={This is the extended version of the paper that appears in ICISC 2004. courtois@minrank.org 12709 received 23 Jun 2003, last revised 18 Oct 2004},
author={Nicolas T. Courtois},
year=2003
}