Cryptography Reference
In-Depth Information
find a private RSA key or even IDEA keys illegibly hidden in a chip card
non-destructively and fast.
The method is called
timing attack
and was published by Paul Kocher at the
end of 1995 [Koch.Tim]. You will find the work in a PostScript file on our Web
site. Kocher's cryptanalysis requires an attacker to be able to measure the time
a program or chip needs to encrypt or decrypt a plaintext or ciphertext block.
We will look at the example of decrypting the RSA method (see Figure 4.16)
to see how this works. Suppose the attacker knows many ciphertexts and can
monitor the program or chip as it decrypts, i.e., the attacker can measure the
execution time. RSA decryption requires the computation of an
R
c
d
mod
n
expression. This power can be computed as follows (all operations modulo
n)
,
for example:
=
•
Set
R
equal to 1 and traverse the bits of
d
, starting with the least signif-
icant.
•
If the bit of
d
currently looked at is equal to 1, then multiply intermediate
result
R
by
c
; otherwise leave
R
unchanged.
•
Substitute
c
by its square and advance to the next bit of
d
.
The multiplication times in the second step now have a certain distribution
that depends on
c
and on the method used. For example, when using bitwise
multiplication, it will take longer the more bits you set in
c
. Suppose the
attacker already knows
b
bits of
c
(
b
=
0 at the beginning). He can determine
the computation time consumed for these
b
bits himself and deduct the result
from the total time. Depending on whether bit
b
+
1 is equal to 1 or equal to 0,
he can also deduct the computation time required for bit
b
+
1 and check in both
possibilities whether or not the distribution of the remaining computation times
thus obtained deviates from the theory. This way the attacker can determine
bit
b
+
1 and successively compute the entire exponent
d
.
The nice thing about this method is that mistakes are permitted. It can be imple-
mented similarly to the tree search in my
vigc crk
.
c
program (see Figure 2.1
and Section 3.6.4): even if you happen to end up on the wrong branch, you
will obtain a computation time distribution that clearly indicates an error at
some point in time, and you just walk back along that same branch.
Putting this train of thought more generally: it suffices to find that the compu-
tation time for
b
fixed bits of a secret key and random ciphertexts depends on
bit
b
+
1. What's more, these
b
bits don't even have to be the least significant
or most significant of the key.
