Cryptography Reference
In-Depth Information
Table 1.
The number of faults and messages to recover the secret key in our fault
attacks on
G
Big Field (
§
3.2.1)
STS (
§
3.2.2)
#Fault
1
n −
1
1
2
#(
x, δ
)
(
n
+1)(
n
+2)
1
Recovering
parts of
S, T
apartof
T
where
c
is a constant. This means that
δ
(1)
=(
δ
(1
1
,
,δ
(1
m
)
t
···
coincides with a
,t
ml
1
)
t
in
T
1
.Thus,taking
constant multiple of the
l
1
-thcolumnvector(
t
1
l
1
,
···
the transform
⎛
⎝
⎞
⎠
⎛
⎝
⎞
⎠
l
ˇ
1
0
∗
∗∗
−δ
(1
2
/δ
(1)
∗
∗
. . .
∗
0
∗
0
1
T
(1)
:=
T
(1)
T
1
=
I
m−
1
,
we have
.
(15)
.
−δ
(1
m
/δ
(1)
1
Next, cause another fault on
G
, and get a pair (
x
(2)
,δ
(2)
) by Step 1-4 with
(
G
)
=
G
,namely,
x
(2)
:=
S
−
1
(
G
−
1
(
T
−
1
(
y
(2)
))),
δ
(2)
:=
F
(
x
(2)
)
F
(
x
(2)
).
−
Assume that the fault changes the coecient
a
(
l
2
)
i
2
j
2
to (
a
(
l
2
)
i
2
j
2
)
.Thenweseethat
S
(
x
(2)
)=
T
1
(0
,
,
0)
t
,
,
0
,
l
,
0
,
l
δ
(2)
=
T
1
◦
G
)
(
G
−
◦
···
c
2
,
0
,
···
c
1
,
0
,
···
where
c
1
and
c
2
are constants. Then, similar to (15), the attacker can reduce the
elements in the
l
2
-thcolumnin
T
1
.
Repeating such processes
n
1 times, one can reduce
T
1
to a permutation of
a triangle matrix. Recall that the purpose of the rank attack is to find (a part
of)
T
. Thus the fault attack reduces the parameters in
T
to be found by the
rank attack.
Table 1 shows a comparison of the fault attack results against the Big Field
type in section 3.2.1 and the STS type in section 3.2.2. #Fault is the number of
faults required for the attack and #(
x, δ
) is the number of pairs (
x
(
l
)
,δ
(
l
)
)given
in Step 4 for
each fault
. The proposed fault attack can recover parts of the secret
keys
S
and
T
for the Big Field type and a part of
T
in equation (2) for the STS
type, respectively.
−
3.2.3 Success Probability and Distinguishing the Faulty Place
Our fault attacks on
G
succeed if the fault changes a parameter in
G
. However,
there are fixed system parameters other than
G
,whicharein
S
and
T
.Ifthe
fault changes entries in
S
or
T
, our fault attack fails to recover the desired secret
information. In this subsection, we discuss the probability that a parameter in
G
is changed by a random fault, and how to distinguish which map (
G
,
S
or
T
)
is faulty.
Success probability.
Thenumbersoftheentries(over
k
)in
S
and
T
are
n
(
n
+1) and
m
(
m
+ 1) respectively, and the total number of the coecients
