Information Technology Reference
In-Depth Information
function on one LFSR) and combinatorial sequences (i.e., operating a boolean
function on multiple LFSRs), the clock control sequences and shrinking genera-
tors [12, 23]. In practice, such key steam generators include E0 [4], and most of
the submissions in EStream Project [11]. In this type of key stream generators,
the initial states the LFSRs are served as a cryptographic key in each commu-
nication session. The goal of an attack is to recover the key, i.e., initial states of
the LFSRs, from some known bits of the key stream, then generates the rest of
bits of the key stream used in that particular session. There are many attacks
proposed in the literation for the LFSR based key stream generators. In this
paper, we consider those attacks related to solve a system of linear equations,
i.e., algebraic attacks and fast algebraic attacks.
1.1
Linearizations, Algebraic Attacks, Fast Algebraic Attacks, and
Selective DFT Attacks
Algebraic attacks and fast algebraic attacks have been shown as an important
cryptanalysis method for symmetric-key cryptographical systems in recent work
by Shamir, Patrin, Courtois and Klimov [24], Courtois and Meier [8], and Cour-
tois [7,9]. Especially, it significantly improved eciency of attacks on stream ci-
pher systems in which key streams are generated by linear feedback shift register
based systems. Those attacks usually contain three steps: (a) pre-computation,
(b) substitution for establishing a system of linear equations over
F
2
or
F
2
n
from
known key stream bits, and (c) solving the system.
A. Equations with Unknown Keys.
In a stream cipher model, a ciphertext is
abitstream
c
0
,c
1
,...,
obtained by exclusive-or a message bit stream
m
0
,m
1
,...,
with the key stream
s
0
,s
1
,...
, i.e.,
c
i
=
m
i
+
s
i
,i
=0
,
1
,...,
in
F
2
. One of strong
attacks comes from
known plaintext attacks
, i.e., if a certain plaintext is known,
then some bits of
{
s
t
}
can be recovered. If the key can be recovered from those
known bits of
,
can be reconstructed. Assume that
K
=(
k
0
,...,k
n−
1
) be an initial state of an
LFSR or a concatenation of the initial states of several LFSRs. In general, the
key stream
{
s
t
}
, then the rest of bits of the key stream, i.e., all bits of
{
s
t
}
{
s
t
}
can be written as
s
t
=
f
t
(
k
0
,k
1
,...,k
n−
1
)
,
t
=0
,
1
,...,m
−
1
(1)
or
W
t
(
s
0
,...,s
t−
1
,k
0
,...,k
n−
1
)=0
,
t
=0
,
1
,...,M
−
1
(2)
where
f
t
(or
W
t
) is a function given by
f
(or
W
), a boolean function in
n
variables, and
L
t
,where
L
is the (left) shift operator of a binary stream, and
L
t
a
is a resulting sequence shifted by
t
bits from
a
=
a
0
,a
1
,...
. In the paper,
we focus on the case (1).
B. Linearization and Algebraic Attacks.
The system of the equations (1)
can be linearized when each monomial in
k
i
1
...k
i
s
is treated as a variable. The
number of unknowns in (1) is varied, but it is dominated by the degree of
f
.
