Information Technology Reference
In-Depth Information
Definition 2.
For every S-box
F
:
F
2
→
F
2
, for every positive integers
s
≤
m
and
t
≤
n
+
m
, and every non-negative integer
r
≤
n
, we define:
∈B
m
,d
◦
f
nl
s,r
(
F
)=min
{
nl
r
(
f
◦
F
);
f
≤
s, f
=
cst
}
∈B
m
,d
◦
f
∈B
n
,d
◦
g
=min
{
d
H
(
g, f
◦
F
);
f
≤
s, f
=
cst, g
≤
r
}
and
∈B
n
+
m
,d
◦
h
NL
t
(
F
)=min
{
w
H
(
h
(
x, F
(
x
)));
h
≤
t, h
=
cst
}
where
w
H
denotes the Hamming weight,
d
H
denotes the Hamming distance and
B
n
denotes the set of
n
-variable Boolean functions.
d
◦
(
F
)
,r
and
t
d
◦
(
F
) are strictly smaller than
n
,then
f
Note that when
s
F
,
g
and
h
(
x, F
) have even weights and
nl
s,r
(
F
),
NL
t
(
F
) are therefore even. We
have also that
nl
s,r
(
F
)isevenwhen
F
is a non-bijective balanced function and
r
is strictly smaller than
n
,andwhen
F
is a permutation and
s, r
are strictly
smaller than
n
,since
f
·
·
◦
F
+
g
have then even weights too.
Definition 2 excludes obviously
f
=
cst
and
h
=
cst
because the knowledge of
the distance
d
H
(
g, f
◦
F
,
g
and
f
◦
F
)oroftheweight
w
H
(
h
(
x, F
(
x
))) when
f
or
h
is constant
gives no information specific to
F
and usable in an attack against a stream or
block cryptosystem using
F
as an S-box. Note that once the value of
nl
s,r
(
F
)
(resp.
NL
t
(
F
)) has been determined, the number of linearly independent pairs
(
f, g
) such that
d
◦
f
◦
=
cst, d
◦
g
≤
s, f
≤
r
and
nl
s,r
(
F
)=
d
H
(
g, f
◦
F
)(resp.
of linearly independent functions
h
such that
d
◦
h
=
cst
and
NL
t
(
F
)=
w
H
(
h
(
x, F
(
x
)))) is also important (see [36] for linear attacks and [18,21] for
algebraic attacks).
T. Shimoyama and T. Kaneko have exhibited in [50] several quadratic func-
tions
h
and pairs (
f, g
) of quadratic functions showing that the nonlinearities
NL
2
and
nl
2
,
2
of some sub-S-boxes of the DES are null (and therefore that the
global S-box of the DES has the same property). They deduced a “higher-order
non-linear” attack (an attack using the principle of the linear attack by Matsui
but with non-linear approximations, as introduced by Knudsen and Robshaw
in [40]) which needs 26% less data than Matsui's attack. This improvement is
not very significant, practically, but some recent studies [32], not yet published,
seem to show that the notions of
NL
t
and
nl
s,r
can be related to potentially
more powerful attacks. Note that we have
NL
max(
s,r
)
(
F
)
≤
t, h
≤
nl
s,r
(
F
)bytaking
h
(
x, y
)=
g
(
x
)+
f
(
y
)(since
f
=
cst
) and the inequality can
be strict if
s>
1or
r>
1sinceafunction
h
(
x, y
) of low degree and such that
w
H
(
h
(
x, F
(
x
))) is small can exist while no such function exists with separated
variables
x
and
y
, that is, of the form
g
(
x
)+
f
(
y
). This is the case, for instance,
of the S-box of the AES for
s
=1and
r
= 2 (see below). It is not yet quite clear
whether better attacks can be achieved when
h
has separated variables than
when it does not. We need therefore to study both notions for the eventuality
that such better attack could be found in the future.
Note that Theorem 1 generalizes to
nl
s,r
(
F
), but the case where
h
is constant
reduces the bound to at most 2
m−s
AI
(
F
)
−
1
i
=0
=
cst
implies then
h
i
and when
s
grows, it is this
