Cryptography Reference
In-Depth Information
S-box for all combinations of
y
i
(8)
,
y
j
(8)
,and
δ
ij
(8)
. The total number of combi-
nations of
y
i
(8)
,
y
j
(8)
,and
δ
ij
(8)
is 2
24
(= 16
,
777
,
216).
The results are shown in Table 2. In the table,
is the size of the
candidates, and
NC
is number of case that the size of the candidates is
|
x
(8)
|
x
(8)
|
in all combinations of (
y
i
(8)
,y
j
(8)
,
δ
ij
(8)
). P is the probability that the number
of the candidates is
|
when 2 inputs of the S-box,
y
i
(8)
,and
y
j
(8)
,andthe
output difference,
δ
ij
(8)
, are randomly set, which is defined as
NC/
2
24
.P
|x
(8)
|
=0
is probability except for
|
x
(8)
|
= 0, which is defined as
NC
|x
(8)
|
=0
/
(2
24
|
x
(8)
|
−
NC
|x
(8)
|
=0
). E(
|
x
(8)
|
) is the expected value of
|
x
(8)
|
except for
|
x
(8)
|
=0,
which is defined as
P
|x
(8)
|
=0
. Table 2 suggests that the number of
solutions for (2) is 2 with 99.2% probability and 4 with 0.8 % probability when
there is a candidate.
|
x
(8)
| ·
Appendix B: Probability That a Solution Can be Uniquely
Determined Using Two Pairs of Correct and Faulty
Outputs
In order to obtain the probability of a solution can be uniquely determined using
2 pairs of correct and faulty outputs, we examine the number of simultaneous
equations in (5) for all combinations of (
y
i
,y
j
,y
k
,y
l
) when answer
x
is fixed.
The total number of all cases is 2
32
because
δ
ij
(8)
,δ
kl
(8)
are calculated from all
combinations of (
y
i
,y
j
,y
k
,y
l
), and the fixed
x
. The results have no relation to
the value of
x
.
S
[
x
(8)
⊕
y
i
(8)
]
⊕
S
[
x
(8)
⊕
y
j
(8)
]=
δ
ij
(8)
S
[
x
(8)
⊕
y
k
(8)
]
⊕
S
[
x
(8)
⊕
y
l
(8)
]=
δ
kl
(8)
(5)
Therefore, the probability that the number of solutions to the S-box equation
(2) in Sec.5.2 is calculated as 98.8%.
Table 3.
Number of Solutions and Probability for All Input Cases
Number of solutions Number of cases
Probability
1
4,243,730,400
0.9881
over 2
51,236,896
0.0119
4,294,967,296 (= 2
32
)
Total
1