Cryptography Reference
In-Depth Information
More specifically, the computation of
c
d
with a 256-bit exponent
d
and a 512-bit
module
n
takes between 392 411 and 393 612 CPU clocks on a 120-MHz Pen-
tium computer under MS-DOS, which means that it fluctuates by 0.3 % at most
[Koch.Tim]. About 2000 ciphertexts suffice to identify strong dependencies of
the computation time distributions on the bits in the exponent.
Many vulnerabilities can be exploited by timing attacks, including the following
examples:
•
The computation times necessary to determine (
c
mod
p)
— where
c
is in
the order of magnitude of
p
— depend on whether
c
is greater or smaller
than
p
.
•
Rotations can be time-dependent. This can play a role when computing
DES subkeys (depending on the hardware used) and, of course, with
RC5.
•
IDEA also uses a multiplication, in this case modulo 2
16
+
1.
•
When the internal tables are not always addressed in the same way, for
example, with Blowfish, SEAL, or DES, then
cache hits
can represent
a vulnerability, i.e., how often a looked-up table entry is already in the
processor cache.
I'm sure you have long asked yourself this question: 'How does an attacker
get hold of these times?' The most intuitive possibility is offered by chip
cards with non-readable keys burnt in. Measuring clock times should be fairly
easy. Imagine that your credit card would one day use an RSA cipher. Just
like organized gangs can copy your ATM card stealthily, they can recover
your credit card's key. Say an encryption took 0.3 seconds and required 1000
ciphertexts. You would have to let your credit card out of your hands (perhaps
not voluntarily) for not more than 5 minutes to risk compromising your secret
key with the legal force of a signature!
There are many more possibilities. Say you work on a secure multi-user oper-
ating system that sends encrypted messages to other similar computers and
exchanges RSA-encrypted session keys. You can have somebody listen in on
all ciphertexts at the cable, but you don't have access to other users' jobs.
Never mind, the system has a flaw that allows you to measure the execution
times of other users' work. Or even more likely, the system holds a valid pri-
vate key that nobody can read for all users. That's no big deal, for you could
send ciphertexts in separate (perhaps identical) blocks to other computers and
