Cryptography Reference
In-Depth Information
The
variance
of the
{
t
j
}
is defined to be
var
{
j
=1
=
(
t
1
−
m
)
2
+(
t
2
−
m
)
2
+
···
(
t
r
−
m
)
2
t
j
}
,
r
and the
standard deviation
is just the square root of the variance. It can be
shown that for another set of outputs
s
1
,s
2
,...,s
r
,
var
{
j
=1
+var
{
j
=1
≈
var
{
j
=1
.
j
=1
+
s
j
}
t
j
}
s
j
}
{
t
j
}
(4.5)
An analogue for the following attack is for a thief to watch someone turning
the lock on a safe and measuring the time it takes to go to each combination
number in order to guess the combination, quite clever.
Timing Attack
Here is what Eve knows: the hardware, such as a smart card or computer,
that is being used; the RSA modulus
n
; and prior to her attack, Eve has mea-
sured the time values that it takes the hardware to compute
x
i
≡
c
i
(mod
n
)in
the repeated squaring method (given on page 171) for some large number
r
of ci-
phertexts
x
i
. Eve wants to obtain the RSA decryption exponent
d
=
j
=0
d
j
2
j
,
which she knows is odd, so she already has
d
0
= 1. Suppose that she has ob-
tained
d
0
,d
1
,...,d
−
1
for some
. Since Eve knows the hardware, she
therefore knows the time
t
i
(for each
x
i
) that it takes the hardware to compute
c
,...,c
k
in the repeated squaring method. She now wants to determine
d
.If
d
= 1, then the multiplication
x
·
∈
N
x
(mod
n
) is calculated for each ciphertext
x
i
, and Eve knows that this takes time
q
i
, say. However, if
d
= 0, this multi-
plication does not take place. Now suppose it takes time
s
i
for the computer
to complete the calculation
after
the multiplication. Then by Equation (4.5), if
d
=1,
r
i
=1
)
r
i
=1
)+var(
r
i
=1
)
>
var (
r
i
=1
)
,
var (
{
t
i
}
≈
var (
{
q
i
}
{
s
i
}
{
s
i
}
(4.6)
and if
d
= 0, then this fails to hold. Hence, Eve can determine
d
, and similarly
d
j
for each
j>
. This simple observation allows for Eve to find
d
without having
to factor
n
.
To summarize: the attack essentially consists of simulating the computation
to some point, then building a decision criterion (4.6), with only one correct
interpretation possible, depending on the selected value, and finally deciding
the bit value by observing whether (4.6) holds. This attack is most effective
against smart cards and such devices where timing measurements can be ob-
tained precisely.
So how do we defend against Eve's (passive) attack? There are two basic
methods for defense against Kocher's timing attack. The simplest is to ensure
that the modular exponentiation being used always takes a
fixed
amount of
time. This may be accomplished by adding a suitable delay factor in each
operation. The second method of defense is attributable to Rivest. The method
is called
blinding
. Suppose that
b
is the ciphertext and
e
is the RSA encryption
Search WWH ::
Custom Search