Information Technology Reference
In-Depth Information
For filtering function generators, i.e., apply
f
on
m
tap positions of an LFSR of
degree
n
, the number of unknowns in (1) is
T
deg
(
f
)
where
deg
(
f
) is the degree
of
f
and
T
j
is defined as
n
i
.
j
T
j
=
(3)
i
=0
The algebraic attack is to multiply
f
by a function
g
with a degree lower than
that of
f
such that the product
fg
is zero, see Courtois and Meier [8]. In other
words, using
g
with
deg
(
g
)
<deg
(
f
) such that
fg
=0,wehavethesystemof
the linear equations as follows
s
t
g
t
(
K
)=0
,t
=0
,
1
,....
(4)
Thus, the number of the unknowns of (4) is now dominated by the degree of
g
instead of
f
. For example, in the filtering generators, this is equal to
T
deg
(
g
)
which is smaller than
T
deg
(
f
)
. Compared with the system of the linear equations
directly from linearization, the algebraic attack can reduce the complexity for
solving a system of linear equations by decreasing the number of unknowns in
the system of linear equations as well as reducing the number of the required
known bits of the key stream.
C. Algebraic Immunity.
From this result, study for algebraic immunity of
boolean functions is in fashion for resistance against this attack, see [6, 10, 15,
17, 18, 19], just list a few. Let
B
n
be the set consisting of all boolean functions in
m
variables. The algebraic immunity of
f
is defined as the smallest degree
deg
(
g
)
such that
fg
=0or(1+
f
)
g
= 0, denoted by
AI
(
f
), i.e.,
AI
(
f
)=
min
g∈Ann
(
f
)
deg
(
g
)
,
where
Ann
(
f
)=
{
g
∈B
n
|
fg
=0or
g
(
f
+1)=0
}
,
(5)
see Meier, Pasalic and Carlet in [17].
D. Fast Algebraic Attacks.
In 2003, Courtois [9] also proposed the fast al-
gebraic attack (FAA) on stream ciphers to accelerate the algebraic attack by
introducing linear relations among the key stream bits. The consideration is
whether we can find some
g
such that
h
=
fg
where
deg
(
g
)
<AI
(
f
). If so, one
could further reduce the number of the unknowns in the linear equations. The
reason is that from
h
=
fg
,weget
f
(
g
+
h
) = 0. So that
g
+
h
Ann
(
f
). Thus
deg
(
g
+
h
)maybegreaterthan
AI
(
f
). FAA consists of two steps: (a) find a
boolean function
g
with
d
=
deg
(
g
)
<deg
(
f
) such that the product
h
=
fg
∈
=0
with
e
=
deg
(
h
)
>
0; (b) compute
q
(
x
) which is a linear recursive relation of the
resulting sequence by replacing
f
in the same key stream generator, and apply
q
(
x
)=
i
c
i
x
i
to
s
t
g
t
(
K
)=
h
t
(
K
)whichresultsin
r
r
c
i
s
i
+
t
g
i
+
t
(
K
)=
c
i
h
i
+
t
(
K
)
(6)
i
=0
i
=0
where
i
=0
c
i
h
i
+
t
(
K
)=0
,t
=0
,
1
,...
in the original paper [9], and we have
i
=0
c
i
h
i
+
t
(
K
)
= 0 with the same unknowns in the left-hand side of (6) in
