Information Technology Reference
In-Depth Information
the variant introduced by Armknecht and Ars [3]. The eciency of the pre-
computation and substitution in the fast algebraic attack is improved by Hawkes
and Rose in [16] for the case of filtering sequence generators and Armknecht in [2]
for combinatorial generators with or without memory. According to the above
analysis, the number of unknowns in (6) is smaller than the number of unknowns
in the algebraic attack. But in FAA, the known bits of the key stream should be
consecutive. However this condition is not needed in the algebraic attack.
E. Selective DFT Attacks.
More recently, Rønjom and Helleseth [20] pro-
posed a method to recover an initial state in a filtering sequence generator by
reducing the number of unknowns in the system of linear equations to the min-
imum, which is the degree of the LFSR by an increased complexity in the both
pre-computation and substitution, especially, in the substitution step. Shortly
after that, the work [21, 22] improved the eciency of the pre-computation and
substitution in terms of forming a system of linear equations over
F
2
n
with
n
unknowns instead of linear equations over
F
2
where
n
is the degree of the LFSR,
and reduced the number of the required consecutive bits of the filtering sequence
to the linear span of the sequence. Recently, these authors proposed a new attack
by multiplying
s
t
by a sequence, say
b
=
, with the linear span less than
the linear span of the sequence
s
0
,s
1
,...
, i.e., to recover the key from the rela-
tion
u
t
=
s
t
b
t
,t
=0
,
1
,...
, which is referred to as the selective discrete Fourier
transform (DFT) attack. The select DFT attack results in either a more ecient
attack than FAA or it can work for the case that the number of the known con-
secutive bits of the key stream is too small to apply FAA by requiring the exact
linear span of the key stream sequence
{
b
t
}
{
s
t
}
and their respective DFT spectra of
{
b
t
}
and
{
u
t
}
, which are not needed in FAA.
1.2
When Is the Fast Algebraic Attack Applicable?
In FAA,
h
=
fg
where
deg
(
g
) determines the number of the unknowns in the
system of the linear equations in (6), and
deg
(
h
) governs the number of the
required consecutive bits of the sequence
for establishing the system (6).
These two parameters provides a trade-off between the number of the unknowns
and the number of the required consecutive bits. Thus, in order to apply FAA in
a way which is more ecient than the algebraic attack, one should investigate
the following question: For a given boolean function
f
in
n
variables, and a pair
of two positive integers (
d, e
), does there exist some boolean function
g
with
deg
(
g
)
{
s
t
}
e
. The following assertion is given
by Courtois and Meier for answering this question.
≤
d
such that
h
=
fg
with
deg
(
h
)
≤
Assertion A. (Theorem 6.0.1 in [8], Theorem 7.2.1 in [9])
With
the above
f
,
d
and
e
, there exists a boolean function
g
in
n
variables
such that
h
=
fg
with
deg
(
g
)
n
≤
d
and
deg
(
h
)
≤
e
when
d
=
2
and
n
+1
2
e
=
in [8] where
x
denotes the smallest integer that is greater
or equal to
x
,orwhen
d
+
e
≥
n
in [9].
