Cryptography Reference
In-Depth Information
variant expected to defeat Simple Power Analysis. As a consequence, only checking
the correctness of the output may not be enough to protect an implementation of
a cryptographic algorithm against faults. Furthermore, designers of secure instan-
tiations must be careful not to add new vulnerabilities while trying to defeat other
ones.
7.4 Exploiting Perturbations of RSA Public Modulus
Although the issue of exploiting malicious modifications of public elements was
addressed in the context of elliptic curve-based cryptosystems [90], it took half a
decade to see the first application to RSA. Indeed, the first fault attack against public
key elements was presented by Seifert with a method for corrupting RSA signature
verification [298, 367]. This fault attack aims to corrupt a signature verification mech-
anism by modifying the value of the public modulus
N
. Nevertheless, no information
about the private exponent
d
is revealed with this fault attack.
Whether it is necessary or not to protect RSA public elements was an open question
until Brier et al. proposed an attack for recovering the whole private key. This attack,
inspired by Seifert's [298, 367], was published in [70] and reviewed in [92]. It makes it
possible to extract the private key using a modulus perturbation. As in Seifert's attack,
the fault on the modulus is induced before executing the exponentiation. Hence, if the
faulty modulus has a small divisor
r
, the attacker will be able to solve an instance of
the Discrete Logarithm Problem from the corresponding faulty signature and obtain
d
mod
r
.
A new fault attack against “right-to-left”-based implementations of the core RSA
exponentiation [39], complemented by the attack of the dual implementation [37],
has recently appeared in the literature. Contrary to previous attacks, authors assumed
that the fault is injected during the execution of an RSA signature. Then, from the
knowledge of a correct and a corresponding faulty signature, the attacker guesses and
determines simultaneously the faulty modulus and the part of the private exponent
that has been isolated by the fault injection. To recover the whole exponent, the
attacker has to repeat the analysis for a sufficient number of signatures with faults at
different moments of the execution.
In the following we will detail the different fault attacks published against RSA
public elements.
7.4.1 Modifying N Before a Signature to Solve a Small
Discrete-Log Problem (DLP)
Although Seifert—with his attack proposal to corrupt an RSA signature verification
mechanism [298, 367]—first addressed the issue of exploiting RSA signatures per-
formed under a faulty public modulus
N
, the first analysis leading to a complete
