Nicolas T. Courtois
1
and Willi Meier
2
1
Cryptography Research, Schlumberger Smart Cards, 36-38 rue de la Princesse,
BP 45, F-78430 Louveciennes Cedex, France,
2
FH Aargau, CH-5210 Windisch, Switzerland,
Abstract. A classical construction of stream ciphers is to combine
several LFSRs and a highly non-linear Boolean function f. Their
security is usually analysed in terms of correlation attacks, that can
be seen as solving a system of multivariate linear equations, true
with some probability. At ICISC’02 this approach is extended to
systems of higher-degree multivariate equations, and gives 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 is the Boolean function
used (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.
Keywords: Algebraic attacks on stream ciphers, pseudo-random gener-
ators, nonlinear filtering, Boolean functions, factoring multivariate poly-
nomials, multivariate equations, overdefined problems, XL algorithm,
ciphertext-only attacks, Toyocrypt, Cryptrec, LILI-128, Nessie.
1 Introduction
In this paper we study stream ciphers with linear feedback and a nonlinear com-
biner that produces the output, given the state of the linear part. The security
of such stream ciphers received much attention. In [13], Golic gives a set of cri-
teria that should be satisfied in order to resist to the known attacks on stream
ciphers. For example, a stream cipher should resist to the fast correlation at-
tack [15], the conditional correlation attack [1] and the inversion attack [13]. In
order to resist different types of correlation attacks, many authors focused on
proposing Boolean functions that will have no good linear approximation and
that will be correlation immune with regard to a subset of several input bits,
E. Biham (Ed.): EUROCRYPT 2003, LNCS 2656, pp. 345–359, 2003.
c© International Association for Cryptologic Research 2003
346 N.T. Courtois and W. Meier
see for example [5]. Recently the scope of application of the correlation attacks
have been extended. In [10], the author exploits rather correlation properties
with regard to a non-linear low degree multivariate function that uses all of the
variables, or in other words, non-linear low degree approximations. This kind
of correlations is not new, see for example in [14]. However their application to
cryptographic attacks did not receive sufficient attention, probably because only
recently people became aware of the existence of efficient algorithms for solving
systems of nonlinear multivariate equations of low degree [21,8,9,10].
Following [10], stream ciphers with linear feedback are potentially very vul-
nerable to such algebraic attacks. If for one state we are able, by some method,
to deduce from the output, a multivariate equation of low degree in the state
bits, then it is also of low degree in the initial state bits. Then the same can
(probably) be done for many other states, and given many keystream bits, we
inevitably obtain a very overdefined system of equations (i.e. many equations).
Such systems can be solved efficiently by techniques such as XL [21,8], adapted
for this purpose in [10] or the simple linearization [21].
In [10], the equations of low degree are obtained by approximating the non-
linear component f of the cipher by a function of low degree. If the probability
that the approximation holds is close to 1, then it can be used simultaneously for
many equations, and we obtain efficient attacks with XL method. For example
in [10], an attack in 2
92
against Toyocrypt
1
is proposed, that requires only some
2
19
bits of the keystream. With more keystream, and if at least some 32 bits are
consecutive, a better attack is possible, due to Mihaljevic and Imai [18].
In this paper we show that algebraic attacks on stream ciphers will apply
even if there is no good low degree approximation. We propose a new method of
generating low degree equations, basically by multiplying the initial equations
by well-chosen multivariate polynomials. This method allows to cryptanalyse a
large class of stream ciphers, satisfying all the previously known design criteria.
For example, all very traditional designs using only a small subset of the state
bits, are shown to be insecure, whatever is the Boolean function used.
The paper is organized as follows: in Section 2 we give a general view of
algebraic attacks on stream ciphers. The main component of our new attack on
stream ciphers is described in Section 2.3. In Section 3 we overview Toyocrypt
and previously known attacks, then in Section 3.1 we apply our new attack for
Toyocrypt. In Sections 4 and 5 we will study LILI-128 and apply our attack.
Then in Section 6 we develop our general attack on stream ciphers using a small
subset of state bits. Finally we present our conclusions about the design of stream
ciphers.
1
Toyocrypt has been accepted to the second evaluation phase of the Japanese Cryptrec
call for primitives, and (apparently) rejected later.
Algebraic Attacks on Stream Ciphers with Linear Feedback 347
2 Algebraic Attacks against Stream Ciphers
In this part we overview and substantially extend the general strategy given in
[10], that reduces an attack on a stream cipher, to solving a system of multivari-
ate equations.
2.1 The Stream Ciphers That May Be Attacked
We consider only synchronous stream ciphers, in which each state is generated
from the previous state independently of the plaintext, see for example [17] for
precise definitions. In principle also, we consider only regularly clocked stream
ciphers, and also (it makes no difference) stream ciphers that are clocked in a
known way. However this condition can sometimes be relaxed, cf. attacks on
LILI-128 described in Sections 4-5.
For simplicity we restrict to binary stream ciphers in which the state and
keystream are composed of a sequence of bits and that generate one bit at a
time. We also restrict to the case when the “connection function” that computes
the next state is linear over GF(2). We call L this “connection function”, and
assume that L is public, and only the state is secret. We also assume that the
function f that computes the output bit from the state is public and does not
depend on the secret key of the cipher. This function f is called “a nonlinear
filter”. The ciphers described here include the very popular filter generator, in
which the state of a single LFSR
2
is transformed by a Boolean function, and
also not less popular nonlinear function generators, in which outputs of several
LFSRs are combined by a Boolean function [17].
The problem of cryptanalysis of such a stream cipher can be described as
follows. Let (k
0
,...,k
n−1
) be the initial state, then the output of the cipher (i.e.
the keystream) is given by: