Cryptography Reference
In-Depth Information
S
(
d
[
t
]
,
N
)
=
S
t
mod
N
.
(7.9)
The whole exponent is gradually recovered by cascading the previous analysis with
signatures faulted at different moments of the execution and using the knowledge
about already found parts. The performance of this fault attack mainly depends on
the number of exponent bits
that the attacker can extract from correct/signature
pair. This parameter is a trade-off between fault number and performance, and so has
to be carefully chosen. Authors estimated that for
w
4 (which ensures reasonable
execution time), the number of faulty signatures to gather for recovering a 1,024-bit
private exponent is about 250 [39]. Finally, one can notice that a similar analysis can
be performed when the first operation infected by the fault is a multiplication (i.e. the
computation of
A
t
is infected first). The details of this variant are provided in [39].
Application to “Left-to-Right”-Based Exponentiations
After exploiting public key perturbation during execution of “right-to-left” imple-
mentations of RSA signatures, Berzati et al. generalized their attack to left-to-right-
based exponentiations. Although both algorithms are very similar, a generalization
of the previous fault attack is not straightforward. To illustrate the difficulties induced
by this generalization the authors consider a classical “left-to-right” exponentiation
(see Sect.
7.2.2.2
) and an attacker able to modify the modulus
N
during its execution,
as in the previous fault model but
t
steps before the end of the execution. Denoting
by
A
n
−
t
the internal register before the perturbation of
N
, the faulty signature
S
t
can
be expressed as
w
=
A
n
−
t
2
t
S
t
=
m
d
[
t
]
N
·˙
mod
,
(7.10)
t
−
1
i
=
0
2
i
and this time
d
d
i
denotes the
t
-bit least-significant part of
d
.By
observing (
7.10
), one can notice that, in contrast to the “right-to-left” case,
t
cascaded
squares are induced by the fault injection. Hence, extending the previous analysis
supposes that the attacker is able to compute modular square roots (which is a difficult
problem in RSA rings). Fortunately, since these additional squares are computed
modulo
N
, it is possible to efficiently compute square roots when
N
is prime (or
B
-smooth) using the probabilistic Tonelli and Shanks algorithm [97]. To validate
the consistency of considering only prime faulty moduli, the authors provided a
complete theoretical analysis based on number theory. Hence they estimated that,
according to the fault model and for a 1,024-bit RSA, one faulty modulus over 305
will be prime [37]. Moreover, they observed that, although two square roots may be
computed from a given quadratic residue, the number of the
t
th square root is not 2
t
but is bounded by the bigger power of 2 dividing
]
=
·
[
t
N
1. Since this power is usually
quite small (i.e. smaller than 5 in their experiments), they concluded that, in practice,
the computation of square roots does not prevent an attacker from using a guess and
determine approach derived from “right-to-left” analysis and recovering parts of
d
when “left-to-right”-based exponentiations are targeted.
In the previous paragraph, we detailed a proposal for attacking the dual imple-
mentations of the modular exponentiation [37, 39]. In both cases, an attacker takes
−
