Summary: A classical construction of stream ciphers is to combine several LFSRs and a highly nonlinear Boolean function \(f\). Their security is usually analysed in terms of correlation attacks, which can be seen as solving a system of multivariate linear equations, true with some probability. At ICISC 2002 [N. Courtois, Lect. Notes Comput. Sci. 2587, 182–199 (2003; Zbl 1031.94515)] this approach was extended to systems of higher-degree multivariate equations, giving an attack in \(2^{92}\) for Toyocrypt, a Cryptrec submission. In this attack the key is found by solving an overdefined system of algebraic equations. In this paper we show how to substantially lower the degree of these equations by multiplying them by well-chosen multivariate polynomials. Thus we are able to break Toyocrypt in \(2^{49}\) CPU clocks, with only 20 Kbytes of keystream, the fastest attack proposed so far. We also successfully attack the Nessie submission LILI-128, within \(2^{57}\) CPU clocks (not the fastest attack known). In general, we show that if the Boolean function uses only a small subset (e.g. 10) of state/LFSR bits, the cipher can be broken, whatever the Boolean function used is (worst case). Our new general algebraic attack breaks stream ciphers satisfying all the previously known design criteria in at most the square root of the complexity of the previously known generic attack.
For the entire collection see [Zbl 1020.00023].