Cryptography Reference
In-Depth Information
7.3 Classical Fault Analysis of Standard RSA Implementations
Since the introduction of fault attacks at the end of the 1990s, the security against
perturbation of CRT-based implementations of RSA has not been the sole implemen-
tation mode targeted [56]. Indeed, the security of standard RSA implementations
has been also challenged, leading to various attack methodologies. Among these
fault attacks, we have chosen to distinguish between two main categories. The first
one deals with the perturbation of intermediate computations. The fault attacks that
belong in this category take advantage of the perturbation of intermediate values
or of the execution flow. The second category includes attacks based on exploiting
modifications of RSA public elements. This trend is quite recent but has ever led to
successful applications against various standard RSA implementations.
The following details the different attacks that we have identified from our state
of the art study.
7.3.1 Perturbation of Intermediate Computations
7.3.1.1 Register Faults
Bellcore researchers not only introduced the concept of fault attacks [32] but also
showed it could be applied to many public key cryptosystems, including standard
RSA, and their various implementations. They explained in [56] how to exploit fault
injections during the execution of a standard RSA signature to recover the private
exponent. The fault model they considered, the so-called register fault, is a transient
or permanent bit-flip induced in the memory area containing the current value of
the exponentiation algorithm. Using this model, they showed that the perturbation
of standard RSA signature, implemented with a “right-to-left” exponentiation, may
leak some secret information. The principle of the attack is described next.
General Methodology
The fault attack against a standard RSA signature proposed by Bellcore researchers
can be split into two parts. The first one is online and consists in gathering sufficiently
many message/faulty signature pairs
m
i
,
S
i
)
by inducing permanent faults, one per
faulty signature, on the register that contains an intermediate value. Then, in the
second part, the attacker tries to analyze the collected faulty signatures to recover the
whole secret key. Hence, this part of the attack is completely off-line. The principle
of the analysis is recalled below. Let
S
i
be the correct signature and let
(
2
b
ε(
m
i
)
=±
<
be the mathematical representation of a bit-flip with 0
n
. Since this fault is
supposed to be permanent, then corresponding faulty signature can be expressed as
b
