Cryptography Reference
In-Depth Information
at the end of the scalar multiplication. The second attack assumes that the attacker
cannot select P and that the implementation validates the resulting point at the end
of the scalar multiplication. In this case, the attacker needs to inject two faults. First,
the attacker injects a fault into the x -coordinate of the input point P . Since half of the
x 's correspond to points that lie on the original curve while the other half correspond
to those that lie on the twist, the resulting value will correspond to points on the twist
E with probability
1
2 . Second, at the end of the computation, just before the point
validation, the attacker needs to inject a fault into the x -coordinate of the result. Note
that due to the missing y -coordinate, point validation will accept any x for which
x 3
1
2 . In effect, the point validation can
be bypassed and the faulty output can be obtained with probability
+
ax
+
b is a square, i.e., with probability
1
4 .
A similar attack that targets the Montgomery ladder over a binary field was pro-
posed independently in [122]. This attack takes advantage of the fact that the para-
meter a in ( 9.3 ) is not used during the scalar multiplication, and the authors adopt
the single bit-flip fault model proposed in [56], which has been shown to be practical
[379]. It can be shown that for a fixed value of the curve parameter b there are only
two isomorphic classes of curves, one for each value of Tr (
is the
trace function. It follows that it is possible to define two elliptic curves, E 0 and E 1 ,
one for each of these isomorphic classes:
a
)
, where Tr ( · )
y 2
x 3
E 0 :
+
xy
=
+
b
,
y 2
x 3
x 2
E 1 :
+
xy
=
+
+
b
.
It is known that the orders of E 0 and E 1 are roughly the same. It is not necessary,
however, that both curves be strong (in the cryptographic sense). In fact, among the
ten NIST-recommended binary curves, there is only one for which the orders of both
E 0 and E 1 are almost prime, namely, the curve K-283.
The key idea behind this attack is to produce an incorrect result from the
computation being performed in the weaker curve of the pair E 0 and E 1 due to
a fault. It is assumed that the degree of extension is odd, i.e., Tr (
1in
the field. The attack starts by injecting a fault into the x -coordinate of the input
point P
1
) =
of a device computing the scalar multiplication.
If the resulting finite field pair after the fault injection is known and the result
Q
= (
x P ,
y P )
E
( F 2 m
)
k P
is released it is possible to obtain the full scalar with high
probability of success. Moreover, a variant of this attack has been presented where
the faulty finite field pair P is unknown and two computations with the same scalar
are obtained. In such a case, the scalar can also be obtained.
=
= (
x Q ,
y Q )
9.3.1.3 Countermeasures
It is commonly advisable to check the correctness of the input points, i.e., whether
they belong to the original curve. One way to do that is to compute and verify the
value of a 6 using the coordinates of P . It is advisable to avoid NIST curves that
Search WWH ::




Custom Search