Cryptography Reference
In-Depth Information
secret key recovery was described by Brier et al. [170]. The main idea behind their
attack is to analyze faulty signatures performed under a faulty modulus
N
to recover
small parts of the private exponent
d
(i.e. 20-30 bits from each faulty signature).
All the parts of exponent extracted from different faulty RSA signatures are finally
combined with the Chinese Remainder Theorem to build the full private exponent.
General Methodology
This fault attack can be split into two distinct phases. The first one is “online” and
consists in gathering
K
pairs message/faulty signatures
(
m
i
,
S
i
)
1
i
K
computed
N
i
with faulty moduli
=
N
such that
m
i
d
mod
N
i
.
S
i
=˙
(
N
i
)
1
i
K
are not known
to the attacker. However, they have also supposed that theses values are uniformly
distributed over the
n
-bit long integers [70, 92]. From this set of faulty signatures,
the attacker performs an “off-line” phase which consists in recovering the private
exponent by parts. The proposed analysis is derived in different variants depending
on the decision of the attacker to generate, or not generate, a table of possible values
for faulty moduli. But, generating such a table, also referred as the dictionary of
moduli [70], requires one to choose a fault model. Finally, one can notice that the
number of signatures to gather (i.e. the parameter
K
) depends on the method chosen
to perform the analysis. Both methods are detailed below.
Analysis without a dictionary
This first method is used when the attacker is not able to identify a fault model from
the set of gathered faulty signatures or, if the identified model induces a dictionary
too large to be handled (e.g. more than 2
32
entries). In this case, it is not possible
to retrieve faulty moduli used to perform the faulty signatures. To overcome this
difficulty, the authors give a means of finding some factors
p
a
of
N
i
thanks to the
Eq. (
7.6
) that is satisfied under some conditions
1
with probability 1 if
p
a
The authors assumed that the values of the different faulty
N
i
and
1
r
|
otherwise (where
r
is a small prime that divides the multiplicative order of
m
i
),
˙
m
i
d
mod
ϕ(
p
a
)
mod
p
a
S
i
=˙
.
(7.6)
Then, for such a
p
a
,if
p
a
is divisible by a small enough prime
r
k
(i.e. 20-30-bit
long), the attacker can take advantage of the bias (see [70, Proposition 1] for details)
with a counting method that enables him to determine parts of the private exponent
d
k
=
ϕ(
)
d
mod
r
k
by solving small discrete logarithms on the faulty signatures gathered.
Hence, when
R
=
k
r
k
is bigger than
N
(and obviously bigger than
), it is
possible to use the Chinese Remainder Theorem to build the whole private exponent
d
from the recovered parts.
ϕ(
N
)
1
p
is a prime number such that
p
m
i
and
p
S
i
.
