Cryptography Reference
In-Depth Information
1.3 Simple Power Analysis
Having introduced the basics of commonly exploited leakages and sketched how to
capture and record these leakages, we now explain how to use them in simple power
analysis (SPA) scenarios to aid fault attacks. The basic idea underlying all these
attacks is to identify operations using a side-channel, and to then inject faults into
the identified functions. We first explain this idea in more detail by briefly reviewing
some examples of what is possible using SPA. We then discuss how someone wishing
to implement a fault attack could use these techniques in practice. An attacker may
be required to identify an appropriate trigger point for a fault injection mechanism,
i.e. to automatically examine a power trace to trigger a fault inducing mechanism.
1.3.1 Case Study: RSA Private Operation
The principal operation of the RSA [349] signature scheme is a modular exponentia-
tion in
Z
)
∗
. That is, a signature
s
is generated from a message
m
by computing
(
Z
/
N
d
mod
N
, where
d
is the private key,
N
is the product of two large primes,
s
=
μ(
m
)
and
is an appropriate padding function. This signature can be verified by checking
whether
μ
is equal to
s
e
mod
n
. We define
d
e
−
1
μ(
m
)
≡
(
mod
φ(
N
))
where
φ
is
Euler's totient function.
One of the most widely known algorithms for implementing an exponentiation
is the square-and-multiply algorithm, where an exponent
e
is read from left to right
bit by bit. Starting with an accumulator set to 1, a squaring operation is performed
if a bit is equal to 0, and a squaring operation followed by a multiplication (with the
value being raised to
e
) is performed if a bit is equal to 1. This algorithm is detailed
in Algorithm 1.1.
Algorithm 1.1:
Binary left-to-right exponentiation
Input
:
m
,
x
the binary length of
d
(i.e. 2
−
1
2
)
<
m
,
d
≥
1,
≤
d
<
x
d
mod
m
1
A
←
x
;
R
←
x
2
for
i
=
−
2
Down to
0
do
3
Output
:
A
=
A
2
A
←
if
(
bit
(
n
,
i
)
=
0
)
then
A
←
A
·
R
4
5
end
6
return
A
In Fig.
1.3
we show a power consumption trace captured while a microprocessor
was computing a modular exponentiation using Algorithm 1.1. A series of opera-
tions can be seen in the power consumption that are separated by downward peaks.
From the ratio of operations, dictated by Algorithm 1.1, we can determine that the
