Cryptography Reference
In-Depth Information
find candidate values for
k
, and then uses those to compute candidates for the secret
key as
d
r
−
1
s
k
mod
p
.
Attack using a faulty base point with multiple-bit error [90]
Let
E
be an elliptic curve over
K
and let
P
=
(
−
H
(
m
))
be the base point. Faults can be
assumed to occur in either or both of the coordinates of
P
. For example, assume that
the value stored for the
x
-coordinate,
x
, is corrupted in some unknown bit positions
and let
P
=
(
=
(
x
P
,
y
)
kP
can be computed and will lie as before on the
curve
E
, which shares all the parameters of
E
except
a
6
. The corresponding value
for
E
,
a
6
, can be computed from the coordinates of
Q
as
x
,
. Then,
Q
=
y
)
a
6
=
y
Q
+
x
Q
−
a
2
x
Q
−
a
1
x
Q
y
Q
+
a
3
y
Q
−
a
4
x
Q
.
Then, we know that
x
is a root in
K
of
x
3
a
2
x
2
a
6
−
y
2
+
+
(
a
4
−
a
1
y
)
x
+
(
−
a
3
y
)
since
P
∈
E
.
Assuming that
r
, the order of
P
in
E
, is small, the root of the above polynomial
with the least Hamming distance from the original
x
P
can be used as a candidate for
x
.
Assuming that the DLP on
E
is weak, the Pohlig-Hellman reduction can be used to
obtain a candidate for
k
.
Note that this attack applies in a similar fashion when errors are injected into the
y
-coordinate instead. However, when both coordinates are faulty, it becomes harder
to recover the faulty point
P
as the attacker only knows that it lies on
E
.Oneway
to recover candidate values of
P
is to perform the scalar multiplication repeatedly
using modified copies of the scalar as illustrated in more detail in [90].
Attacks on the Montgomery ladder
Fouque et al. [143] have proposed a fault attack on the Montgomery ladder algorithm
over prime fields. Their work uses the fact that the
y
-coordinate is not used in the
scalar multiplication, and hence the faulty computation can leave the original curve
and move to its twist. More specifically, since the
y
-coordinates are not utilized in
the Montgomery ladder elliptic curve scalar multiplication [205], the computation
applies also to the set of points
(
x
,
y
)
with
x
∈ F
p
and
y
∈ F
p
2
that form a twist of
the original elliptic curve
E
, denoted by
E
.
The order of the group of the original elliptic curve and that of its twist are roughly
of the same size. In practice, an elliptic curve is chosen to have a group with prime
order, but the group order of the twist is not necessarily prime. In fact, among the
five NIST-recommended curves over prime fields only the curve denoted by P-384
has a twist with a prime order. For the remaining curves, the group orders of their
twists are composite and are easier to attack.
In [143], two attacks have been presented. The basic attack is when the adversary is
able to choose the input point
P
and the implementation does not use point validation
