Cryptography Reference
In-Depth Information
One can notice that the advantage of this method is that it may lead to a full
key recovery regardless of the faults injected into the different moduli. According
to [70, 92], the implementation of this methodology enables one to recover 512-bit
private exponents (1,024-bit in the case of a small public exponent
e
2
) by gathering
about 2
10
4
faulty signatures are
enough to recover 1,024-bit secret exponents (2,048-bit in the case of a small public
exponent
e
).
Analysis with a dictionary
The attack performance can be improved if the attacker is able to identify and validate
a fault model from the faulty signatures collected during the “online” phase. From
this fault model and the knowledge of
N
, the attacker can establish a list of possible
values for the faulty moduli. This list is also called the dictionary of moduli. Once
the dictionary is generated, the attacker tries to guess the pairs
10
4
.
5
×
faulty signatures. On the other hand, 6
×
m
i
,
S
i
)
that result
from a computation with one of the dictionary entries. Each successful guess, or
“hit”, brings a certain amount of information on the private exponent
d
.Interms
of performance, this approach is very interesting since, according to [70, 92], 28
“hits” and only 1,100 faulty signatures are enough for recovering a 1,024-bit RSA
private exponent. Moreover, by finding these “hits” with a statistical approach, it is
possible to extract the private exponent with a number of faults equal to the number
of “hits” (which is proved to be optimal). In this case 28 faulty signatures may suffice
to recover a 1,024-bit RSA private exponent.
Although fault attacks has been considered as a powerful way to attack imple-
mentations of cryptographic algorithms, the presented attacks highlight that even
noncritical elements, such as public keys, have to be protected against fault injection.
While public elements are not supposed to reveal secret information, their perturba-
tion may be a source of leakage leading to the corruption of a signature verification
mechanism [298, 367] or, worse, to a full private key recovery [70, 92]. However, the
use of an exponent randomization technique may be an effective way of defeating
such attacks. Furthermore, these attacks only apply to perturbations that occur before
performing the core exponentiation of the RSA signature. The attack presented in
the next section prove that this claim is no longer the case since the perturbation of
public elements during the signature can also be exploited.
(
7.4.2 Exploiting Faults on N During the Computation of an RSA
Signature
In Seifert's and Brier et al.'s proposals [70, 367], the authors exploited perturbations
of the public modulus provoked before the core exponentiation so that the whole
2
When
e
is small, the authors take advantage of the RSA equation
e
·
d
≡
1mod
ϕ(
N
)
to determine
themostsignificantpartof
d
. Indeed, knowing that
ϕ(
N
)
=
N
+
1
−
p
−
q
≈
N
for its most
1
+
k
·
(
N
+
1
)
2
1
6
significant part, then
d
1), the most
significant part of
d
can be directly deduced from the previous relation completed by an exhaustive
search on
k
.
≈
with
k
<
e
. Hence, if
e
is small (e.g.
e
=
+
e
