Cryptography Reference
In-Depth Information
a product of polynomials of the form
2
m
y
3
i
P
y
3
m
−
i
+
1
Q
x
3
i
P
x
3
m
−
i
+
1
Q
x
3
i
P
x
3
m
−
i
+
1
Q
2
(
−
·
σ
−
(
+
+
)
)
−
(
+
+
)ρ
−
ρ
b
b
i
=
1
the algorithm instead produces
2
Δ
y
3
i
P
y
3
m
−
i
+
1
Q
x
3
i
P
x
3
m
−
i
+
1
Q
x
3
i
P
x
3
m
−
i
+
1
Q
2
(
−
·
σ
−
(
+
+
b
)
)
−
(
+
+
b
)ρ
−
ρ
i
=
1
Δ
for some value
(remembering that for now, we ignore the final powering). If the
attacker is able to induce a fault so that
Δ
=
m
+
1, then recovering
P
is trivial:
compute the two results
R
1
=
e
m
(
P
,
Q
)
and
R
2
=
e
m
+
1
(
P
,
Q
)
;
i.e.,
R
1
is correct and
R
2
is faulty. Using
g
to denote the
i
th factor of a product
produced by the algorithm, dividing the two results produces a single factor
(
i
)
R
2
R
1
=
y
3
m
+
1
P
x
3
m
+
1
P
x
3
m
+
1
P
2
2
R
=
g
(
m
+
1
)
=
(
−
·
y
Q
σ
−
(
+
x
Q
+
b
)
)
−
(
+
x
Q
+
b
)ρ
−
ρ
.
z
3
m
Given that
∀
z
∈ F
q
,
=
z
, the attacker can easily extract
x
P
or
y
P
based on
knowledge of
x
Q
and
y
Q
.
However, the ability to selectively induce a fault so that
Δ
=
m
+
1 is a little
tenuous; it is far more realistic to assume that each fault induces
d
for
a random, unknown disturbance
d
. As such, it is reasonable to assume the attacker
must compute the two results
Δ
=
m
±
R
1
=
e
m
±
d
(
P
,
Q
)
and
R
2
=
e
m
±
d
+
1
(
P
,
Q
),
again producing a single term,
g
(
m
±
d
+
1
)
; this allows the same approach as above, but
demands that the attacker know
d
so as to correct the differing powers of
x
P
,
x
Q
and
y
Q
. Recovery of
d
is, however, reasonable: since the algorithm is straight-line
and takes a fixed number of operations, the execution time leaks the number of loop
iterations performed fairly directly. This approach requires only a modest number of
invocations due to an argument similar to that of the birthday paradox; we simply keep
provoking random faults until we recover an
R
1
and
R
2
that satisfy our requirements.
y
P
,
