Cryptography Reference
In-Depth Information
13.3.2.1 Excluding the Final Powering
One of the specific examples discussed is the
η
G
pairing described by Algorithm 13.4.
The authors assume an attacker can inject a transient fault in the first cell
of the
function
v
computed in line 6 of Algorithm 13.4 during the last round of the Miller
loop (i.e., when
i
[
v
0
]
=
m
). Denote by
η
G
(
P
,
Q
)
the output of this faulty pairing; then
dividing
η
G
(
P
,
Q
)
by this value gives
η
G
(
P
,
Q
)
u
/
v
v
v
=
[¯
¯
v
0
][
v
1
][
v
2
][
v
3
]
)
=
v
=
v
3
]
=[
N
0
][
N
1
][
N
2
][
N
3
]
,
η
G
(
P
,
Q
u
/
¯
[
v
0
][
v
1
][
v
2
][
where the
N
i
∈ F
2
m
are the cells of the division of the two pairings. From Algo-
rithm 13.4 it follows that
v
1
=
1,
v
2
=
1 and
v
3
=
0. By multiplying the last equality
with
[
v
0
][
v
1
][
v
2
][
v
3
]
, and using the fact that
v
1
=
1, one finally obtains a simple
expression for the correct
v
0
, namely
N
0
+
N
2
+
1
v
0
=
.
N
1
Since
v
0
is explicitly given by
x
Q
+
P
can be
easily extracted (since the adversary knows
x
Q
) and from this it is easy to recover
±
x
+
1, the coordinate
x
2
m
−
1
2
m
−
1
[
]
P
[
]
P
(simply multiply by the inverse of 2
m
−
1
modulo the group order), and thus
P
by recomputing the pairing.
13.3.2.2 Including the Final Powering
The authors also investigate a more general situation by introducing a targeted fault
during computation of the reduced Tate pairing. Since
r
is an odd prime, we know
that
r
0
=
0),
line 7 will always be executed. Assuming we can inject a fault into the computation
of
l
T
+
P
(
1; this implies that in the last iteration of Algorithm 13.1 (i.e., when
i
=
Q
)
, we obtain
l
[
r
−
1
]
P
,
P
(
(
q
k
¯
(
q
k
−
1
)/
r
ˆ
−
1
)/
r
e
T
(
P
,
Q
)
Q
)
v
P
(
Q
)
)
=
=
,
e
T
(
ˆ
P
,
Q
l
[
r
−
1
]
P
,
P
(
Q
)
v
P
(
Q
)
where the last equality follows from the fact that
P
has order
r
. The problem, how-
ever, is that one would need to reverse the final powering, and find the correct root
from amongst all
r
possibilities. This is a special instance of the so-called Hidden
Root Problem [406], which currently seems impossible for exponents of the form
(
q
k
−
1
)/
r
with
r
a proper divisor of
Φ
k
(
q
)
(and
Φ
k
the
k
th cyclotomic polynomial).
