Cryptography Reference
In-Depth Information
The Jacobi symbol can be eciently computed using the law of quadratic reci-
procity (see e.g. [10]), even if the factorization of the modulus is not known.
Note that the Jacobi symbol only gives a guarantee for quadratic non-residues
by evaluating to
−
1, but a result of 1 does not imply that
c
is a quadratic residue
modulo
k
.
3 General Attack Method
As already mentioned, the aim of a fault attack is to deduce information on
secrets involved in the internal computation of the device. In most cases, this is
done by manipulating the device and analyzing its erroneous output
1
. Normally,
an adversary is assumed to have access to the attacked device and can manipulate
it. Hence, the inputs of the device are chosen by the adversary.
In order to successfully attack a device, it is important to know the algorithm
that is computed internally. Furthermore, it is necessary to make assumptions
about the faults that occur and to set up relations between the intermediates
processed inside the device and the erroneous output.
In this paper, we discuss such relations for the Montgomery powering ladder.
A fault attack on its implementation can exploit a general observation: For two
arbitrary values in
R
0
and
R
1
the algorithm behaves as in Table 1. For
a
=1
Table 1.
The Montgomery powering ladder starting with
R
0
and
R
1
set to arbitrary
values. (
·
)
d
denotes the application of the ladder with the exponent
d
of length
t
.
Step
R
0
R
1
a
b
b
a
=
a
a ·
a
2
t
a
2
t
(
·
)
d
·
(
a
)
d
·
(
a
)
d
+1
a
2
t
−d
· b
d
a
2
t
−d
· b
d
·
b
a
=
and
b
=
m
this evaluates directly to
m
d
. In a fault attack an adversary would
set one of the two intermediates to a random (or partially random) value during
the exponentiation. As before, let
d
=(
d
t−
1
,...,d
0
)
2
=[
d
L
,d
i
,d
T
]. After the
computation of
d
L
, one intermediate is modified to contain a random value
z
.As
a consequence, the intermediate values develop as depicted in Table 2. This basic
property can be exploited to retrieve the secret exponent. Therefore, the fault
must be injected in a way it is predictable. What is left is to reduce the number
of unknown bits of the exponent in the equation by exploiting the property of
RSA that
d
=
e
−
1
(mod
ϕ
(
n
)). In the following, we are considering different
1
Note that for some fault attacks the behavior of the device itself, after a fault is
injected, is sucient [11].
Search WWH ::
Custom Search