Cryptography Reference
In-Depth Information
9.3.3.1 Exploiting Random Faults During the Computation
Assume that E is defined over a field
F q , and that the binary algorithm is used to
perform the scalar multiplication, as in Algorithm 9.1. Also, assume that the attacker
can repeatedly input a point P and induce a fault during a specific iteration of the
computation, and that the correct result Q
kP is known. Let Q i denote the values
of Q at the i th iteration. During the computation, a fault is injected into a random
iteration j to modify Q j to Q j and get Q as an output. Then, the values of Q , Q
and j can be used to determine the intermediate value Q j , which can be used to
guess the higher n
=
j bits of k . The process can then be repeated going downwards
through the bits of k .
It has been shown in [44] that finding a secret key of length n bits using this attack
requires O
bit operations for
subsequent calculations. It is also possible to decrease the accuracy of random fault
injection, i.e., inject faults into blocks of at most m consecutive iterations rather
than into a specific iteration. The choice of the block size m presents a trade-off
between the number of register faults required and the time needed to analyze the
faulty results.
(
n log n
)
faulty scalar multiplications and O
(
n log n
)
9.3.3.2 Countermeasures
As seen earlier, point validation is essential when fault attacks are considered.
In particular, output points should be validated and any point that does not belong to
the original curve should be discarded.
9.4 Sign Change Fault Attack
Earlier fault attacks on ECC worked by inducing faults in a way that would move
the computation to a different, probably weaker, elliptic curve. This can be achieved
by modifying the base point, an intermediate point, or a parameter of the curve.
However, this can be easily countered by verifying the correctness of the parameters
and that the resulting point belongs to the original curve.
The attack described in [54] does not move the computation to a different curve,
but rather results in a faulty point on the original curve. By collecting enough of these
faulty results, the secret can be recovered in expected polynomial time. It follows
that point validation is not an effective countermeasure against this attack. Actually,
it may help the attacker to remove useless faulty points, i.e., points that fall off the
curve, and hence it makes a less precise attack more effective.
Attack description
As the name indicates, this attack involves changing a sign of an intermediate variable
during the scalar multiplication, which can be achieved by replacing an intermediate
point with its inverse or by changing a digit of the NAF-encoded scalar from 1 to
1.
Search WWH ::




Custom Search