Cryptography Reference
In-Depth Information
signature is performed with a faulty modulus
N
. The attack presented by Berzati et
al. [39] extended the fault model by enabling an attacker to exploit faults injected
into a “right-to-left”-based exponentiation. The modification of
N
was supposed to
be a transient random byte fault modification. It means that only one byte of
N
is changed to a random value. Moreover, they also assumed that the value of the
faulty modulus
N
is not known to an attacker. However, the time location of the
fault is a parameter known to an attacker and used to perform the cryptanalysis. This
fault model has been chosen for its simplicity and practicability in the smart card
context [52, 160]. Furthermore, it can be easily adapted to 16- or 32-bit architectures.
This attack was later generalized to “left-to-right”-based implementations including
Montgomery and Sliding Window exponentiations. It has also been proven that
exponent randomization method—also known as exponent blinding—suggested by
Kocher [239] may not be efficient for protecting RSA implementations against faults
in public key elements [41].
General Methodology
In order to detail the general methodology, we assume that the implementation of
the modular exponentiation is “right-to-left”-based (see Sect.
7.2.2.1
) and that an
attacker is able to modify one byte of the public modulus
N
at the
t
th step of the
exponentiation. If we denote by
A
t
and
B
t
the internal register values, then for a fault
occurring while
B
t
is computed, we have
·
...
·
B
2
(
n
−
1
)
−
t
·
d
n
−
1
A
t
·
B
d
t
S
t
=
N
mod
(7.7)
t
t
d
[
t
]
2
t
A
t
·
B
t
N
=
mod
(7.8)
where
d
[
t
]
=
n
−
1
2
i
d
i
Hence, the fault injection splits the computation into a
correct and a faulty part. The main consequence is that a part of the private exponent,
namely
d
[
t
]
, is isolated by the fault injection. In practice this part of the exponent is
composed of a known (already determined) part and a part to guess. So, if the part to
guess is small enough, it is possible to guess and determine it from a faulty/correct
signature pair
·
i
=
t
(
S
t
,
. Therefore, since the faulty modulus is also unknown to the
attacker, he has to choose a candidate value
N
(built according to the fault model)
and another candidate value for the part of
d
[
t
]
S
t
)
to guess. Then he computes from the
m
−
d
[
t
]
correct signature
A
t
=
S
t
·˙
mod
N
and
d
[
t
]
2
t
mod
N
2
·
m
2
t
−
1
S
(
d
[
t
]
,
N
)
=
A
t
·
N
.
˙
mod
(
N
,
d
[
t
]
)
is the expected one with high probability. Otherwise, the attacker has to choose
another candidate pair and perform this test again.
If this rebuilt faulty signature satisfies (
7.9
) then the pair of candidate values
