Cryptography Reference
In-Depth Information
Computation circuit
Mask circuit
X
b
S
B
Y
Y
=
S
(
X
)
a
a
·
Y
=
b
·
X
⊕
B
Figure 4.7.
Dual circuit of a substitution box.
If the mask includes some output bits from a substitution box
S
, namely some
β
·
S
(
u
), the mask on the previous layer will include some
α
·
u
so that the
correlation between
β
·
S
(
u
)) be the bias bit which is associated to this substitution box (see Fig. 4.7).
α
·
u
and
β
·
S
(
u
) is significant. We let
B
=
(
α
·
u
)
⊕
(
Piling up all propagations, we obtain that
(
b
·
f
(
x
))
⊕
(
a
·
x
)
=
(
c
·
k
)
⊕
B
i
i
where
k
is the key vector and the
B
i
's are all bias vectors that we met in the substitution
boxes.
Let us now introduce the following lemma.
=
Lemma 4.1 (Piling-up lemma).
For any Boolean variable B we define
LP(
B
)
=
−
1)
2
. Let B
1
,...,
(2 Pr[
B
0]
B
n
be n independent random variables. We have
LP(
B
1
⊕···⊕
B
n
)
=
LP(
B
1
)
×···×
LP(
B
n
)
.
1)
B
))
2
,
1)
α
⊕
β
=
To
prove
this,
we
simply
observe
that
LP(
B
)
=
(
E
((
−
that
(
−
1)
α
(
1)
β
, and we use the independence of the
B
i
's .
(
−
−
Going back to the propagation of masks, we now assume that the input of
f
is a
random variable
X
and that the key
k
is fixed. We further make the heuristic assumption
that all
B
i
's are independent. We obtain from the piling-up lemma that
LP
f
(
a
,
b
)
=
LP(
B
i
)
.
i
Hence, by making sure that all LP(
B
i
) are large, then the product LP
f
(
a
b
) will be
large. We also have to make sure that the number of
B
i
biases is as low as possible.
This means that we have as few “active substitution boxes” as possible. Unfortunately
there exists no general way to find these efficient
a
and
b
masks, nor to approximate
LP
f
(
a
,
,
b
) with the above techniques. We only have heuristic ways to find it.
Search WWH ::
Custom Search