Cryptography Reference
In-Depth Information
Applying this attack repeatedly enables the attacker to recover the scalar
k
starting
from the least significant bit. A simpler variant of the attack, where it is assumed that
the attacker can target a specific iteration, is described here. However, the attack can
be extended to allow for uncertainty in fault injection [54].
Suppose that the basic double-and-add algorithm (Algorithm 9.1) is used to com-
pute
Q
kP
, and that the attacker has the correct value for
Q
.Itisassumedthat
the attacker can inject a temporary sign change fault into the doubling step
Q
=
←
2
Q
so that it effectively becomes
Q
←−
2
Q
. The attack starts by targeting the last
iteration of the algorithm, where
i
=
0. This results in the faulty output
n
−
1
Q
2
i
k
i
P
=−
+
k
0
P
=−
Q
+
2
k
0
P
,
i
=
1
which lies on the original curve and cannot be detected by point validation. Moreover,
depending on whether
k
0
is equal to 0 or 1,
Q
will be equal to either
2
P
,
respectively, which easily reveals
k
0
to the attacker. In general, if a sign change fault
is injected into iteration
i
, the resulting faulty point can be written as
−
Q
or
−
Q
+
i
Q
k
j
2
j
P
=−
+
Q
2
j
=
0
where only one of the
i
+
1 least significant bits of
k
is unknown, namely,
k
i
.Asa
Q
will take one of two values,
result,
2
i
−
1
j
0
k
j
2
j
P
−
Q
+
k
i
=
0
Q
=
=
2
i
−
1
j
=
1
.
0
k
j
2
j
Pk
i
−
Q
+
2
P
+
=
The attack can be generalized to cases where the attacker may not know the precise
iteration in which the change happened. The idea is to recover the bits of
k
in blocks of
1
m
, where
m
is chosen to control a trade-off between the required exhaustive
search and the number of faulty results required to give a success probability of at
least
≤
r
≤
1
2
.
9.4.1 Countermeasures
The sign change fault attack is not applicable to Montgomery's scalar multiplication
algorithm [294] since it does not use the
y
-coordinate, which prevents the attacker
from changing the sign of intermediate points. Moreover, randomizing the scalar,
e.g., by splitting, is effective since the same fault at the same stage of the algorithm
would generate a different result every time.
