Cryptography Reference
In-Depth Information
hardens an adversary's life for fault attacks. For instance, in [6] it is stated that
higher-order faults (several faults per algorithm invocation) are needed to apply
their attack to the Montgomery ladder.
An attack that combines side-channel analysis and fault attacks was presented
by Park et at. [7]. In their work, they induce single faults either during the
multiplication or during the squaring and check which future intermediate results
are affected by looking at the device's power consumption.
Our Contribution:
In this paper, we present a general fault attack against
the Montgomery powering ladder. We show that various fault models can be
used to put the attack into practice, such as tampering with the intermediate
variables or with the program flow. Moreover, we show how our approach can
be extended to blinded implementations. In particular, our attack can defeat
the blinded implementation of the Montgomery ladder proposed by Fumaroli
and Vigilant [8]. To the best of our knowledge this is the first fault attack on a
blinded Montgomery powering ladder.
The remaining paper is organized as follows: Section 2 gives a brief introduc-
tion into RSA and the Montgomery powering ladder. The general attack method
is detailed in Section 3. Afterwards, Sections 4 and 5 show how to launch the
attack in a realistic scenario. Finally, we extend the attack to work on blinded
implementations in Section 6. The complexity of the attacks is discussed in Sec-
tion 7. Conclusion is drawn in Section 8.
2 Preliminaries
In this section, we first discuss the RSA public-key algorithm. Afterwards, we
look at the Montgomery powering ladder and its protected version as proposed
by Fumaroli and Vigilant [8]. Finally, we revisit the Jacobi symbol.
The security of RSA is based on the hardness of factoring the product of
two large primes. Let
p
and
q
be such primes,
n
=
pq
their product, and
ϕ
(
)
denote Euler's totient function. All computations of the RSA take place in the
ring
Z
n
. The public exponent
e
is an element of
Z
ϕ
(
n
)
, its corresponding secret
exponent is
d
=
e
−
1
mod
ϕ
(
n
). Due to this construction,
m
=(
m
e
)
d
mod
n
holds for any
m ∈
Z
n
. The owner of the secret key can sign messages by com-
puting
s
=
m
d
mod
n
or decrypt ciphertexts by calculating
m
=
c
d
mod
n
.By
giving away the public key (
N, e
), he enables everybody else to either verify
signatures (
m
=
s
e
mod
n
) or to encrypt messages (
c
=
m
e
mod
n
). In order
to omit side-channel attacks on the exponentiation, it is recommended to use
regular exponentiation algorithms, which leak as little information as possible
about the secret exponent. As mentioned before, one such regular algorithm to
compute a modular exponentiation is the Montgomery powering ladder [9]. It is
depicted in Algorithm 1.
In each iteration of the ladder, one intermediate is assigned the product of
both, the other one is squared. If the current bit is one,
R
0
is set to
R
0
·
·
R
1
and
R
1
is squared, and vice versa if the bit is zero. Let
d
=(
d
t−
1
,...,d
0
)
2
=
[
d
L
,d
i
,d
T
]. Here,
d
i
denotes the bit which is currently processed and
d
L
the
Search WWH ::
Custom Search