Strength of two data encryption standard implementations under timing attacks.
We study the vulnerability of two implementations of the Data Encryption Standard (DES) cryptosystem under a timing attack. A timing attack is a method, recently proposed by Paul Kocher, that is designed to break cryptographic systems. It exploits the engineering aspects involved in the implementation of cryptosystems and might succeed even against cryptosys-tems that remain impervious to sophisticated cryptanalytic techniques. A timing attack is, essentially, a way of obtaining some users private information by carefully measuring the time it takes the user to carry out cryptographic operations. In this work, we analyze two implementations of DES. We show that a timing attack yields the Hamming weight of the key used by both DES implementations. Moreover, the attack is computationally inexpensive. We also show that all the design characteristics of the target system, necessary to carry out the timing attack, can be inferred from timing measurements.
INTRODUCTION
An ingenious new type of cryptanalytic attack was introduced by Kocher in [Kocher
1996]. This new attack is called timing attack. It exploits the fact that cryptosystems
often take slightly different amounts of time on different inputs. Kocher gave
several possible explanations for this behavior, among these: branching and conditional
statements, RAM cache hits, processor instructions that run in non-fixed
time, etc. Kocher's most significant contribution was to show that running time
differentials can be exploited in order to find some of a target system's private infor-
mation. Indeed, in [Kocher 1996] it is shown how to cryptanalyze a simple modular
exponentiator. Modular exponentiation is a key operation in Diffie-Hellman's key
exchange protocol [Diffie and Hellman 1976] and the RSA cryptosystem [Rivest
et al. 1978]. A modular exponentiator is a procedure that on inputs k; n 2 N,
n). In the cryptographic protocols mentioned
above n is public and k is private. Kocher reports that if a passive eavesdropper can
measure the time it takes a target system to compute (y k mod n) for several inputs
y, then he can recover the secret exponent k. Moreover, the overall computational
effort involved in the attack is proportional to the amount of work done by the vic-
tim. For concreteness sake and clarity of exposition we now describe the essence of
Kocher's method for recovering the secret exponent of the fixed-exponent modular
exponentiator shown in Fig. 1.
Code:
be k in binary
For l down to 0 do
Output: z.
Fig. 1. Modular exponentiator.
The attack allows someone who knows k l \Delta to recover k t\Gamma1 . (To obtain the
entire exponent the attacker starts with repeats the attack until
The attacker first computes l iterations of the for loop. The next iteration
requires the first unknown bit k t\Gamma1 . If the bit is set, then the operation
n) is performed, otherwise it is skipped. Assume that each timing observation
corresponds to an observation of a random variable
is the time required for the multiplication and squaring steps corresponding to the
bit k l\Gammai and e is a random variable representing measurement error, loop overhead,
etc. An attacker that correctly guesses k t\Gamma1 may factor out of T the effect of
obtain an adjusted random variable of known variance (provided
the times needed to perform modular multiplications are independent from each
other and from the measurement error). Incorrect guesses will produce an adjusted
random variable with a higher variance than the one expected. Computing the
variance is easy provided the attacker collects enough timing measurements. The
correct guess will be identified successfully if its adjusted values have the smaller
variance.
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 3
In theory, timing attacks can yield some of a target system's private information.
In practice, in order to successfully mount a timing attack on a remote cryptosystem
a prohibitively large number of timing measurements may be required in order to
compensate for the increased uncertainty caused by random network delays. Nev-
ertheless, there are situations where we feel it is realistic to mount a timing attack.
We now describe one of them. Challenge-response protocols are used to establish
whether two entities involved in communication are indeed genuine entities and can
thus be allowed to continue communication with each other. In these protocols one
entity challenges the other with a random number on which a predetermined calculation
must be performed, often including a secret key. In order to generate the
correct result for the computation the other device must posses the correct secret
key and therefore can be assumed to be authentic. Many smart cards, in particular
dynamic password generators (tokens) and electronic wallet cards, implement
challenge-response protocols (e.g. the message authentication code generated according
to the ANSI X9.26 [Menezes et al. 1997, page 651] standard). It is expected
that extensive use will be made of smart cards based in general purpose programmable
integrated circuit chips. Thus, the specific functionality of each smart card
will be achieved through programming. The security of these smart cards will be
provided using tamper-proof technology and cryptographic techniques. The above
described scenario is an ideal setting in which to carry out a timing attack. The
widespread availability of a particular type of card will make it easy and inexpensive
to determine the timing characteristics of the system on which to mount the attack.
Later, the obtaining of precise timing measurements (e.g. by monitoring or altering
a card reader or by gaining possession of a card) could be used to retrieve some of
the secret information stored in the card by means of a timing attack. Thus, cards
that implement challenge-response protocols where master keys are involved could
give rise to a security problem. (See [Dhem et al. 1998] for a discussion of a practical
implementation of a timing attack against an earlier version of the CASCADE
smart card.)
New unanticipated strains of timing attacks might arise. Hence, timing attacks
should be given some serious consideration. This work contributes, ultimately, in
furthering our understanding of the strengths of this new cryptanalytic technique,
the weaknesses it exploits, and the ways of eliminating the possibility of it becoming
practical.
Kocher implemented the attack against the Diffie-Hellman key exchange proto-
col. He also observed that timing attacks could potentially be used against other
cryptosystems, in particular against the Data Encryption Standard (DES). This
claim is the motivation for this work.
2.


OF RESULTS AND ORGANIZATION
We study the vulnerability of one of the most widely used cryptosystems in the
world, DES, against a timing attack. The starting point of this work is the observation
of Kocher [Kocher 1996] that in DES's key schedule generation process
moving nonzero 28-bit C and D values using a conditional statement which tests
whether a one-bit must be wrapped around could be a source of non-constant encryption
running times. Hence, he conjectured that a timing attack against DES
Alejandro Hevia and Marcos Kiwi
could reveal the Hamming weight of the key. 1 We show that although Kocher's
observation is incorrect (for the DES implementations that we analyzed), his conjecture
is true. But, we do more.
In Sect. 3 we give a brief description of DES.
In Sect. 4.1 we describe a timing attack against DES that assumes the attacker
knows the target system's design characteristics. We first discuss experimental
results that show that a computationally inexpensive timing attack against two
implementations of DES could yield enough information to recover the Hamming
weight of the DES key being used. Hence, assuming the DES keys are randomly
chosen, an attacker can recover approximately 3:95 bits of key information. To the
best of our knowledge, this is the first implementation of a timing attack against a
symmetric cryptosystem. (Since the preliminary version of this work appeared two
timing attacks against RC5 have been reported [Handschuh and Heys 1999].) In
Sect. 4.1.1 we describe computational experiments that measure the threat implied
by an actual implementation of a timing attack against DES.
Recovering 3:95 bits of a DES key is a modest improvement over brute force
search. But, recovering the Hamming weight of the key is, potentially, more
threatening. In particular, an adversary can restrict attention to keys determined
to have either a significantly low or high Hamming weight. Although such keys may
be rare once the adversary determines that one such key is being used the ensuing
search may be significantly sped up. Thus, the adversary can balance the time
to find such rare keys with the time needed for key recovery. In some systems, even
the recovery of a single (although rare) key may be of serious concern.
In Sect. 4.1.2 we identify the sources of the dependencies between the encryption
time and the key's Hamming weight in the implementations of DES that we studied.
The most relevant are conditional statements.
In both DES implementations that we analyzed the encryption time T is roughly
equal to a linear function of the key's Hamming weight X plus some normally
distributed noise e. Since a DES key is a 56 bit long string and keys are chosen
uniformly at random in the key space, we have that X - Binom (56; 1=2). 2 Thus,
for some ff, fi, and oe,
In Sect. 4.2 we show that it is not necessary, in order to perform a timing attack
against DES, to assume that the design characteristics of the target system are
known. Indeed, we propose two statistical methods whereby a passive eavesdropper
can infer from timing measurements all the target system's design information
required to successfully mount a timing attack against DES. To the best of our
knowledge, this is the first proof that it is possible to infer a target system's design
characteristics through timing measurements.
We would like to stress that all of the timing attacks described in this work
only require precise measurements of encryption times but no knowledge of the
encrypted plaintexts or produced ciphertexts.
1 Recall that the Hamming weight of a bitstring equals the number of its bits that are nonzero.
2 Recall that the distribution Binom (N;p) corresponds to the distribution of the sum of N
independent identically distributed f0; 1g-random variables with expectation p.
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 5
In Sect. 5 we propose a "blinding technique" that can be used to eliminate almost
all of the execution time differentials in the analyzed DES implementations. This
blinding technique makes both DES implementations that we study impervious to
the sort of timing attack we describe in this work. Finally, we discuss under which
conditions all, and not only the Hamming weight of, a DES key might be recovered
through a timing attack.
2.1 Related Work
Modern cryptography advocates the design of cryptosystems based on sound mathematical
principles. Thus, many of the cryptosystems designed over the last two
decades can be proved to resist many sophisticated, mathematically based, cryptanalytic
techniques (provided one is willing to accept some reasonable assumptions).
Traditionally, the techniques used to attack such cryptosystems exploit the algorithmic
design weaknesses of the cryptosystem. On the other hand, timing attacks take
advantage of the decisions made when implementing the cryptosystems (specially
those that produce non-fixed running times). But, timing attacks are not the only
type of attacks that exploit the engineering aspects involved in the implementation
of cryptosystems. Indeed, recently Boneh, Lipton, and DeMillo [Boneh et al. 1997]
introduced the concept of fault tolerant attacks. These attacks take advantage of
(possibly induced) hardware faults. Boneh et al. point out that their attacks show
the danger that hardware faults pose to various cryptographic protocols. They conclude
that even sophisticated cryptographic schemes sealed inside tamper-resistant
devices might leak secret information.
A new strain of fault tolerant attacks, differential fault analysis (DFA), was proposed
by Biham and Shamir [Biham and Shamir 1997]. Their attack is applicable
to almost any secret key cryptosystem proposed so far in the open literature. DFA
works under various fault models and uses cryptanalytic techniques to recover the
secret information stored in tamper-resistant devices. In particular, Biham and
Shamir show that under the same hardware fault model considered by Boneh et al.,
the full DES key can be extracted from a sealed tamper-resistant DES encryptor
by analyzing between 40 and 200 ciphertexts generated from unknown but related
plaintexts. Furthermore, in [Biham and Shamir 1997] techniques are developed to
identify the keys of completely unknown ciphers sealed in tamper-resistant devices.
The new type of attacks described above have received widespread attention (see
for example [English and Hamilton 1996; Markoff 1996]).
3. THE
DES is the most widely used cryptosystem in the world, specially among financial
institutions. It was developed at IBM and adopted as a standard in 1977 [NBS
1977]. It has been reviewed every five years since its adoption.
DES has held up remarkably well against years of cryptanalysis. But, faster and
cheaper processors allow, using current technology, to build a reasonably priced
special purpose machine that can recover a DES key within hours [Stinson 1995,
pp. 82-83]. For concreteness sake, we provide below a brief description of DES. For
a detailed description see [NBS 1977]. More easily accessible descriptions of DES
can be found in [Schneier 1996; Stinson 1995].
DES is a symmetric or private-key cryptosystem, i.e., a cryptosystem where the
6 \Delta Alejandro Hevia and Marcos Kiwi
Key schedule
Encryption
Plaintext
Perm.
Perm.
Key
Fig. 2. DES encryption process.
parties that wish to use it must agree in advance on a common secret key which
must be kept private. DES encrypts a message (plaintext) bitstring of length 64
using a bitstring key of length 56 and obtains a ciphertext bitstring of length 64.
It has three main stages. In the first stage the bits of the plaintext are permuted
according to a fixed initial permutation. In the second stage 16 iterations of a
certain function are successively applied to the bitstring resulting from the first
stage. In the final stage the inverse of the initial permutation is applied to the
bitstring obtained in the second stage.
The strength of DES resides on the function that is iterated during the encryption
process. We now give a brief description of this iteration process. The input to
iteration i is the output bitstring of iteration long string, K i .
Actually, each K i is a permuted selection of bits from the DES key. The strings
what is called the key schedule. During each iteration a 64
bit long output string is computed by applying a fixed rule to the two input strings.
The encryption process is depicted in Fig. 2.
Decryption is done with the same encryption algorithm but using the key schedule
in reverse order K
The best traditional cryptanalytic attacks known against DES are due to Biham
and Shamir [Biham and Shamir 1991; Biham and Shamir 1993] and Matsui [Matsui
1994a; Matsui 1994b]. However, they are not considered a threat to DES in practical
environments (see [Menezes et al. 1997, pp. 258-259]).
4. TIMING ATTACK OF DES
We now consider the problem of recovering the Hamming weight of the DES key
of a target system by means of a timing attack. We first address the problem, in
Sect. 4.1, assuming the attacker knows the design of the target system. We then
show, in Sect. 4.2, that this assumption can be removed.
4.1 Timing Characteristics of Two Implementations of DES
We studied the timing characteristics of two implementations of DES. The first
one was obtained from the RSAEuro cryptographic toolkit [Kapp 1996], henceforth
referred to as RSA-DES. The other implementation of DES that we looked at was
one due to Louko [Louko 1992], henceforth referred to as L-DES. We studied both
implementations on a 120-MHz Pentium TM computer running MSDOS TM . The
advantage of working on an MSDOS TM environment is that it is a single process
operating system. This facilitates carrying out timing measurements since there are
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 7
50200300400500Hamming weight of key
Time
Encryption
Key Schedule
Fig. 3. RSA-DES.
5050150250350Hamming weight of key
Time
Key Schedule
Encryption
Fig. 4. L-DES.
no other interfering processes running and there are less operating system maintenance
tasks being performed. We measured time in microseconds (-s).
In our first experiment we fixed the input message to be the bitstring of length
all of whose bits are set to 0. For each we randomly chose
keys of Hamming weight i. For each selected key we encrypted the message a total
of times. During each encryption we measured the time it took to generate the
schedule and the total time it took to encrypt the message. The plots, for each
of the implementations that we looked at, of the average (for each key) encryption
and key schedule generation times are shown in Fig. 3 and Fig. 4.
Only obvious outliers were eliminated. In fact the only outliers that we noticed
appeared at fixed intervals of 2 clock ticks. These outliers were caused by system
maintenance tasks.
Alejandro Hevia and Marcos Kiwi
A randomly chosen DES key has a Hamming weight between 23 and 33 with
probability approximately 0:86. Thus, the most relevant data points shown in
Fig. 3 and Fig. 4 are those close to the middle of the plots.
For various keys chosen at random we performed 2 (for each
key) of the encryption and key schedule generation times. After discarding obvious
outliers we graphed the empirical frequency distributions of the collected data. The
empirical distributions we observed were roughly symmetric and concentrated in a
few contiguous values (usually three or four). This concentration of values is due to
the fact that we were only able to perform time measurements with an accuracy of
0:8381-s and that time differentials among encryptions performed under the same
were rarely larger than 3:0-s. (For an explanation of how to measure time with
this precision on an MSDOS TM environment see Appendix A). The above suggests,
as one would expect, that the variations on the running time observed when the
same process is executed many times over the same input are due to the effect of
normally distributed random noise.
For different values of we randomly chose 2 8 keys of Hamming
weight i. After throwing away outliers we graphed the empirical frequency distributions
of the collected data. The empirical frequencies observed looked like
normal distributions with small deviations (typically 1:2-s for L-DES and 1:8-s
for RSA-DES). We conclude that the variations on the encryption and key schedule
generations times observed among keys of same Hamming weight are mostly due to
the total number of bits of the key that are set and not by the position where these
set bits occur. Thus, the effect of which bits are set among keys of same Hamming
weight is negligible.
We repeated all the experiments described so far but instead of leaving the input
message fixed we chose a new randomly selected message at the start of each encryption
process. All the results reported above remained (essentially) unchanged.
There was only a negligible increase in the measured deviations.
Assuming that the attacker knows the design of the target system, he can build
on his own a table of the average encryption time versus the Hamming weight of
the key. The clear monotonically increasing relation between the encryption time
and the Hamming weight of the key elicited by our experiments is a significant
implementation flaw. It allows an attacker to determine the Hamming weight of the
DES key. Indeed, the attacker has to obtain a few encryption time measurements
and look in the table he has built to determine the key's Hamming weight from
which such time measurements could have come. Thus, the attacker can recover
bits of key information (H denotes the binary entropy function).
Remark 1. A precise estimation of the Hamming weight of the DES key can be
achieved by means of a timing attack if two situations hold. First, accurate time
measurements can be obtained. Second, the variations in the encryption and key-schedule
generation time produced by different keys with identical Hamming weight
is small compared to the time variations produced by keys with one more or one less
set bit. We have noticed that the latter situation approximately holds. An exact
estimation of Hamming weight of the DES key can be achieved if the attacker can
accurately perform time measurements of several encryptions of the same plaintext.
But, this requires a more powerful attacker, one that should be capable of fixing the
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 9
Where - is the time it takes DES to generate ciphertext C from message M
Code: For
Let l be such that
g.
Randomly choose m in g.
For
Let K be the (m lexicographically first elem. of K l .
If (DES encryption of M under key K yields C) then return(K).
Fig. 5. Key recovery procedure based on a timing attack that reveals the Hamming weight of
the key.
input message fed into the encryption process.
More remarkable than the established monotonically increasing relation between
the encryption times and the Hamming weight of the key is the linear dependency
that exists between the two measured quantities. The correlation factors for the
data shown in Fig. 3 and Fig. 4 are 0:9760 and 0:9999 respectively. The sharp linear
dependency between encryption times and Hamming weight allows an attacker to
infer the target system's information which is required to carry out the attack
described above. This topic is discussed in the next section.
4.1.1 Experimental Results. In this section we describe a computational experiment
that shows the expected reduction in the size of the key space search that
would be achieved by the implementation of the timing attack described in the
previous section.
Assume that for every we have a T i 2 R corresponding to the
expected time it takes the target DES implementation to encrypt a message with
a key of Hamming weight i. Furthermore, assume that T supported
by our experimental observations). Consider the procedure of Fig. 5 for recovering
the DES encryption key through a timing attack that exploits the facts reported
in Sect. 4.1. Note that it is possible to experimentally determine the expected
number of keys that this procedure would try without having to actually execute it.
Indeed, if the DES encryption of plaintext M under key K generates the ciphertext
C in -s, then the expected size of the key space searched by the given procedure is,
For both DES implementations we studied we randomly chose DES message/key
pairs, measured the encryption time, and computed the expected number of keys
that the procedure of Fig. 5 would have tried before finding the correct encryption
key. From our discussion of Sect. 4.1 it follows that the best that one can hope
for is to have to try half of the keys whose Hamming weight equals that of the
correct encryption key. This corresponds to 3:24 percent of all the key space, since
k=0 pk log 2 pk =2. We found that for RSA-DES 5:30
3 In the (unlikely) event that l is not uniquely defined, perturb - by a value uniformly chosen in
the interval [\GammaOE; OE], where OE is tiny compared to the precision of the timing measurements.
Alejandro Hevia and Marcos Kiwi
26 28

Table

1. Results of computational experiment.
percent of the key space would have been searched, in average, before finding the
correct encryption key. For L-DES, the percentage goes down to 3:84 percent.

Table

1 shows in more detail some of the data collected in our experiments.
Columns are labeled according to the weight of the DES key. We denote the weight
of a key by k. The second row represents the percentage of the total key space
corresponding to DES keys of Hamming weight k (with a precision of 0:0005). We
denote this value by p k . For each DES key of weight k we estimated (16000
times) the expected percentage of the key space that would have been searched
before finding the encryption key. Each of theses estimates was based on 16000 \Delta p k
measurements in order to insure that at least 16 measurements were considered for
every estimate associated to nonzero p k 's. The last two rows of Table 1 show, for
each DES implementation and some key weights, the average of the values obtained.
Recovering 3:95 bits of a DES key gives a modest improvement in the time
needed to recover the key. But, Table 1 implies that a timing attack that reveals
the Hamming weight of the key is potentially more threatening. In particular, an
adversary can restrict attention to keys determined to have either a significantly
low or high Hamming weight. The adversary can do this by performing timing
measurements until one is found to be either significantly low or high. Once the
adversary detects such a rare key the subsequent key search can be much less than
the usual amount. Thus, the adversary can balance the time to find such rare keys
with the time needed for key recovery. In some systems the recovery of even a
single may cause total disruption and/or forward vulnerability.
4.1.2 Sources of the dependency between DES encryption time and key's Hamming
weight. The key schedule generation in L-DES is carried out by a procedure
called des set key. This procedure computes the resulting key schedule bitstring
by performing a bitwise OR with some pre-computed constants. For each bit of the
key, such bitwise or's are computed if and only if the key bit is set. For that purpose,
it uses a piece of code of the following form: If (condit) then
else instr. The number of times condit is true turns out to be exactly the Hamming
weight of the DES key. This is the main source of running time differentials
in L-DES.
In RSA-DES's key schedule generation code there is also a procedure that contains
two conditional statements. These conditional statements are used in the
computation of the subkeys. More precisely, they implement a fixed permutation
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 11
PC2 of some bits of the key. Their code is of the following form: If (condit) then
instr. The total number of times condit is true is equal to the sum of the Hamming
weight of all subkeys. Thus, the number of times instr is executed is directly
proportional to the Hamming weight of the DES key.
As mentioned in Sect. 2, Kocher [Kocher 1996] conjectured that in DES's key
schedule the rotation of nonzero bits using conditional statements could give rise
to running time differentials. In the implementations of DES we analyzed we found
no evidence to support this conjecture.
Finally, note that it is clear from Fig. 4 that in L-DES there is a source of non-fixed
running times which does not depend on the key schedule generation process.
This is evidenced by the non-constant distance between the two curves shown in
Fig. 4. The source of these time differentials is not due to conditional statements.
We were not able to identify the cause of this dependency nor able to exploit it in
order to recover all of the DES key.
4.2 Derivation of the Timing Characteristics of the Target System
As discussed in Sect. 4.1, in both DES implementations that we studied the encryption
time was roughly equal to a linear function of the key's Hamming weight
plus some normally distributed random noise. In this section we exploit this fact
in order to derive all the necessary information needed to perform a timing attack
that reveals the Hamming weight of the target system's DES key.
First we need to introduce some notation. Assume we have m measurements on
the time it takes the target system to perform a DES encryption. The time measurements
might correspond to encryptions performed under different DES keys.
For g, denote by K i the i-th key that is used by the target system during
the period that timing measurements are performed. We make the (realistic)
assumption that K are chosen at random in f0; 1g 56 and independent of
each other. Let X (i) denote the Hamming weight of key K i . Thus, the distribution
of X (i) is a Binom (56; 1=2). Since we are assuming that the K i 's are chosen independently
we have that X are independent random variables. Note
that successive time measurements can correspond to encryptions of the message
under the same key. For be the index of the
last measurement corresponding to an encryption performed with key K i . For con-
venience's sake, let - m. Denote by
I i the set of indices that correspond to time measurements under key K i , i.e. for
g. For
let T (i)
j be the random variable representing the time it takes the target system to
perform the j-th encryption of the message with key K i . Finally, for
be a random variable representing the effect of random noise on the j-th encryption
with key K i . Thus, the e (i)
inaccuracies and the target
system's running time fluctuations.
We now have all the notation necessary to formally state the problem we want
to address. Indeed, the linear dependency between the encryption time and the
Hamming weight of the key in both DES implementations that we studied implies
Alejandro Hevia and Marcos Kiwi
that there exists ff, fi, and oe, such that for all
Our problem is to infer from timing measurements the parameters ff, fi, and oe for
which (1) holds. We address two variations of this problem. In Sect. 4.2.1 we show
how to deal with the case where the - i 's are known. In Sect. 4.2.2 we show how to
handle the case where the - i 's are unknown. The former case is the most realistic
one. Indeed, a standard cryptanalytic assumption is that the attacker knows the
management procedure of the target system.
4.2.1 Known - 0
We propose two alternative statistical methods for deducing
the parameters ff, fi, and oe for which (1) holds. One method is based on maximum
likelihood estimators and the other one on asymptotically unbiased estimators.
Since the following discussion heavily relies on standard concepts and results from
probability and statistics we refer the reader unfamiliar with these subjects to [Feller
1966; Ross 1988; Zacks 1971] for background material and terminology.
Maximum Likelihood Estimators: Let
. Thus, X;T
more, let
be the actual values taken
by X, T (i) , and T respectively.
oe) be the marginal distribution of T given ff, fi, and oe. For a
fixed collection of time measurements t the values of ff, fi, and oe that maximize
are the maximum likelihood estimators we are looking for. The maximum
likelihood estimators are the values most likely to have produced the observed
time measurements. They can also be regarded as the values minimizing the loss
This explains why maximum likelihood estimators are
thought to be good predictors. Thus, in order to determine good estimators for ff,
fi, and oe we first compute f T (t; ff; fi; oe).
Proposition 1. The marginal distribution of T given ff, fi, and oe is
Y
Proof. Let f X;T (\Delta; ff; fi; oe), f T=X=x (\Delta; ff; fi; oe) and f X (\Delta; ff; fi; oe) denote the joint
density function of X and T , the density function of T given and the
probability distribution of X respectively. For convenience's sake, we henceforth
omit ff, fi, and oe from the expressions for f X;T , f T=X=x , and f X .
Observe that the independence of the X (i) 's and e (i)
's imply that the T (i) 's are
independent. Thus, the joint density function of X and T given ff, fi, and oe is
Y
where the last equality follows since the X (i) 's are independent and the T (i) 's are
independent.
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 13
From (1) we get that T (i)
like a Norm
Moreover, for fixed i, the T (i)
j 's are independent random variables. Hence,
Y
we know that f X (i)
. Thus,
Y
The marginal distribution of T given ff, fi, and oe equals the sum, over all values
taken by x, of f X;T (x; t). Hence,
Y
The conclusion follows directly from the previous equality and the fact that X (i) -
Binom (56; 1=2).
For a given t the values of ff, fi, and oe that maximize the right hand side of the
expression in Proposition 1 are the maximum likelihood estimators sought. As is often
the case when dealing with maximum likelihood estimators it is difficult to solve
explicitly for them. (See [Zacks 1971, Ch. 5, x2] for a discussion of computational
routines that can be used to calculate maximum likelihood estimators.)
The advantage of the above described approach for determining the parameters
relevant for carrying out the timing attack is that it uses all the available timing
measurements. But, it does not allow us to determine how many measurements are
sufficient in order to obtain accurate estimations of the parameters sought. The
alternative approach described below solves this problem.
Asymptotic Estimators: Our goal is to find good estimators b ff, b
fi, and b oe for
ff, fi, and oe. Moreover, we are interested in determining the asymptotic (on the
number of timing measurements) behavior of such estimators. In particular, their
asymptotic distributions, their limiting values, and their rate of convergence.
We will now derive good predictors for ff, fi, and oe. We start with a key observa-
tion. Since the expectation and variance of a Binom (56; 1=2) are 28 and 14 respec-
tively, taking the expectation and variance in (1) yields that for all
28
Hence, if we knew - T , oe 2
T , and oe 2 we could solve for ff and fi in (2). This suggests
that if we can find good estimators for - T , oe 2
T , and oe 2 , then we can derive good
estimators for ff and fi. We now provide candidates for c
T , and c oe 2 , the estimators
T , and oe 2 respectively. But, we first need to introduce additional
14 \Delta Alejandro Hevia and Marcos Kiwi
notation. Let
e (i)
c
Solving for ff and fi in (2) yields that the two natural candidates for b
ff and b
fi,
the estimators for ff and fi, are
We now prove that b
ff is well defined.
Proposition 2. c
Proof. Just note that
c
We henceforth denote a chi-square distribution with l degrees of freedom by - 2
l .
Proposition 3. If jI the distribution of c
Proof. Since T (i)
j , we have that T (i)
Since e (i) is the average of n independent Norm
\Delta . In addition, the de Moivre-Laplace Theorem [Hazewinkel 1988,
pp. 397] states that the Binom (m; p) distribution can be expressed in terms of
the standard normal distribution. Moreover, if m ! 1, then such an expression
is exact, and if mp(1 \Gamma p) - 10, then the expression provides a good approximation
of the Binomial distribution [Ross 1988, pp. 170-171]. Thus, since X (i) -
Binom (56; 1=2), the distribution of X (i) is well approximated by a Norm (28; 14).
Hence, since X (i) is independent of e (i) and the sum of independent normal distributions
is a normal distribution, it follows that T (i) is approximately distributed as
a Norm
. The desired conclusion follows from a classical statistics
result [Hogg and Tanis 1997, Theorem 5.3.4] and Proposition 2.
Proposition 4. If jI negligible, then
converges (in distribution) 4 to a Norm
small constant error term
when k !1.
4 Recall that when X are random variables on some probability
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 15
Proof. First, note that if we neglect oe 2 =n then Proposition 2 and our definition
of b ff imply that the distribution of b
.
Second, recall that the sum of the squares of l independent identically distributed
normal random variables with zero mean and variance equal to 1 is distributed
according to a - 2
l . Equivalently, the sum of l independently distributed - 2
variables is distributed according to a - 2
l . Hence, since the expectation and variance
of a - 2
random variable are 1 and 3 respectively, the Central Limit Theorem implies
that
(in distribution) to a Norm (0; 3).
Putting the two observations together shows that
distribution) to a Norm
small constant term when k !1. The
stated result follows immediately.
Theorem 1. If jI negligible and k is sufficiently
large, then the distribution of b
ff is (approximately) a Norm
Proof. The Law of Large Numbers implies that c
T and c
(almost
surely) 5 to oe 2
T and oe 2 respectively. Hence, by continuity, b
converges (almost surely) to
1. This fact and
Proposition 4 yield that if k !1, then
ff+ff converges (in dis-
tribution) to a Norm
small error term. The desired conclusion
immediately.
Remark 2. Theorem 1 provides an approximation to the distribution of b
ff. The
approximation error arises from three sources. The first one is the use of the de
Moivre-Laplace Theorem to express a Binom (56; 1=2) in terms of a Norm (28; 14).
The second one is due to the use of the Central Limit Theorem to approximate the
distribution of an estimator by its limit distribution. The final source of error
is due to the use of the Law of Large Numbers to approximate an estimator by
its asymptotic value. These three sources of approximation error can be bounded
through the de Moivre-Laplace Theorem, Berry-Essen's inequality[Hazewinkel 1988,
pp. 369], and Chebyshev's inequality[Ross 1988, pp. 337] respectively. A bound on
the accumulated approximation error shows that Theorem 1 is fairly accurate.
Corollary 1. If jI negligible and k is sufficiently
large, then
Proof. The bound concerning b
ff follows from Theorem 1 and Chebyshev's in-
equality[Ross 1988, pp. 337]. In order to prove the other bound recall that b
said that Xn converges in distribution to X as n !1, if P[
all points x at which FX
5 Recall that when X are random variables on some probability
said that converges almost surely to X as
is an event whose probability is 1.
Alejandro Hevia and Marcos Kiwi
c
ff and
where the last inequality is a consequence of applying Chebyshev's inequality twice.
Note that from Theorem 1 we have that V[ b
=n). The result follows.
Corollary 1 tells us that with probability at least suffices to take n time
measurements for each of 1
different keys to approximate ff and fi to within
a multiplicative factor of (1 \Sigma ffl).
4.2.2 Unknown - 0
s. The assumption that the - i 's are known made in the previous
section is not strictly necessary since an attacker may alternate between performing
several timing measurements over a short period of time and resting for an appropriately
long period of time. Hence, the problem of deducing the target system's
design characteristics reduces to the case in which the - i 's are known provided that
the keys are not changed too often and the attacker's resting period is longer than
a key's lifetime. (Changing keys too often creates a key management problem for
the cryptosystem's user. Thus, it is reasonable to assume that a key's lifetime is
not excessively short.)
We now discuss another approach for handling the case of unknown - i 's under
the assumption that the attacker has access to several identical copies of the target
system, e.g., several copies of a smart card supporting a DES based challenge-response
protocol. Lets make the reasonable assumption that the target system's
are independently generated. In this case the attacker may perform, over
a short period of time, several timing measurements for each copy of the target
system. If the key's are not changed too often the attacker can deduce the target
system's relevant timing characteristics as in Sect. 4.2.1. Indeed, the attacker can
assume that all the timing measurements arising from the same copy of the system
come from encryptions performed under the same key. Since keys corresponding
to different copies of the target system are independently generated and the copies
of the system are identical, the problem of deducing the target system's design
characteristics reduces to the case in which the - i 's are known.
Tests of statistical hypothesis give rise to another alternative for handling the case
of unknown - i 's. Indeed, consider the situation in which an attacker determines m
timing measurements t arising from random variables satisfying (1). Assume
keys are not changed too often, i.e., at least n - m timing measurements
come from encryptions performed under the same key. Thus, for each j such that
the attacker can perform a test of equality of two normal distri-
butions[Hogg and Tanis 1997, pp. 372-385] on the samples of t j
. The significance level of such tests allows the attacker to determine
the measurements around where a change of key occurs. Discarding the measurements
around where the attacker suspects a change of key occurs yields a sequence
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 17
of timing measurements from which the target system's design characteristics can
be deduced as in the case of known - i 's.
5. FINAL COMMENTS
In [Kocher 1996] a "blinding technique" similar to that used for blind signatures
[Chaum 1983] is proposed in order to prevent a timing attack against a modular
exponentiator. For both implementations of DES we studied, blinding techniques
can be adapted to produce (almost) fixed running time for the key schedule generation
processes. Indeed, let K be the DES key of Hamming weight wt(K) whose key
schedule we want to generate. Let K 0 be a bitstring of length 56 generated as fol-
lows: randomly choose b wt(K)c (respectively d 56\Gammawt(K)e) of the bits of K which are
set to 1 (respectively 0) and set the corresponding bits of K 0 to 0 (respectively 1).
Denote the bitwise xor of K and K 0 by K \PhiK 0 . Note that wt(K 0
when the Hamming weight of K is even, and wt(K 0 28 and wt(K \PhiK 0
the Hamming weight of K is odd. Modify the key schedule generation processes so
schedules for keys K 0 and K \Phi K 0 are generated. Note that the work required
for this is independent of the Hamming weight of K. Hence, no sources of non-fixed
running time are introduced during this step. Let K 0
the key schedules obtained. Recall that K i (respectively K 0
permuted selection
of bits from the key K \Phi K 0 (respectively K 0 ). Thus, the key schedule of
K is

Figure

6 plots the encryption times of RSA-DES
as previously explained. Note the very clear reduction in time differentials. The
reduction is achieved at the expense of increasing the encryption time by a factor
of approximately 1:6. Unfortunately, this blinding technique still leaks the parity
of the weight of the original DES key, i.e., 1 bit of information. careful look at
Fig. 6 confirms this fact). This fact can be fixed using the idea developed above.
Indeed, for a given DES key K one can generate three DES
two of them with Hamming weight 28 and one with Hamming weight 27. Of the
three keys one will be spurious meaning that its key schedule should be generated
and the results discarded. The xor of the key schedules generated by the two non-
spurious keys will give rise to the key schedule sought. When the Hamming weight
of the original DES key is even (respectively odd) the spurious key will be the one
of Hamming weight 27 (respectively one of the keys of Hamming weight 28).
We have seen that the main source of non-fixed running times were caused by
the key schedule generation procedure. In many fast software implementations
key setup is an operation which is separated from encryption. This would thwart a
timing attack if encryption time is constant. But, in several systems it is impractical
to precompute the key schedule. For example, in smart cards pre-computations are
undesirable due to memory constraints.
both DES implementations we studied are fairly resistant to a timing
attack. This leads us to the question of whether a timing attack can find all of the
DES key and not only its Hamming weight. Although we did not succeed in tuning
the timing attack technique in order to recover all the bits of a DES key, we identified
in L-DES a source of non-fixed running time that is not due to the key generation
process. Indeed, the difference in the slopes of the curves plotted in Fig. 4 shows
that the encryption time, not counting the key generation process, depends on the
used. This fact is a weakness that could (potentially) be exploited in order to
Alejandro Hevia and Marcos Kiwi
50400500600700Hamming weight of key
Time
Blinded RSA-DES
RSA-DES
Fig. 6. RSA-DES and modified RSA-DES encryption times.
recover all of the DES key. It opens the possibility that the time it takes to encrypt
a message M with a key K is a non-linear function of both M and K, e.g., it is a
monotonically increasing function in the Hamming weight of M \Phi K. This would
allow a timing attack to recover a DES key by carefully choosing the messages to be
encrypted. We were not able to identify clear sources of non-linear dependencies
between time differentials and the inputs to the DES encryption process in either
of the DES implementations that we studied. Nevertheless, we feel that the partial
information leaked by both implementations of DES that we analyzed suggests that
care must be taken in the implementation of DES, otherwise, all of the key could
be compromised through a timing attack.

ACKNOWLEDGMENTS

We are grateful to Shang-Hua Teng for calling to our attention the work of Kocher.
We thank Raul Gouet, Luis Mateu, Alejandro Murua, and Jaime San Martin for
helpful discussions. We also thank Paul Kocher for advise on how to measure running
times accurately on an MSDOS TM environment. Finally, we thank an anonymous
referee for pointing out that the blinding technique of Sect. 5 was leaking
information about the parity of the Hamming weight of the key.




A.



Standard C routines allow to measure time events in an MSDOS TM environment
with an accuracy of 54:9254-s [Heidenstrom 1995]. In order to measure with a time
precision of 0:8381-s on a Pentium TM computer running MSDOS TM we followed
Kocher's advice [Kocher 1997]. He suggested reading the value of a high-precision
timer by accessing port 64. Whenever this timer overflows to 65536 it generates
one interrupt. Interrupts occur once every 54925:4-s. Hence, one can measure time
intervals with a precision of 54925:4-s=65536 - 0:8381-s. It is also a good idea
to run from a RAM disk. For more information on how to perform accurate time
Strength of Two Data Encryption Standard Implementations under Timing Attacks \Delta 19
measurements on the PC family under DOS the reader is referred to [Heidenstrom
1995]. Performing the timing measurements in a Windows or Unix environment is
clearly a bad idea since both of them are multi-process operating systems.



--R

Differential cryptanalysis of DES-like cryptosystems
Journal of Cryptology
Differential cryptanalysis of the full 16-round DES

On the importance of checking cryptographicprotocols for faults.
Blind signatures for untraceable payments.
A practical implementation of the timing attack.
New directions in cryptography.
Network security under siege.
An introduction to probability theory and its applications
A timing attack on RC5.
Encyclopaedia of Mathematics
FAQ/application notes: Timing on the PC family under DOS.

Probability and statistical inference (fifth
RSAEuro: A cryptographic toolkit.
Timing attacks on implementations of Diffie-Hellman
Private communication.
DES package.

Potential flaw seen in cash card security.
The first experimental cryptanalysis of the data encryption standard.

Linear cryptanalysis method for DES cipher.


A method for obtaining digital signatures and public-key cryptosystems
A first course in probability (third
Applied Cryptography: protocols

The theory of statistical inference.
--TR
Linear cryptanalysis method for DES cipher
Applied cryptography (2nd ed.)
Network Security Under Siege
A method for obtaining digital signatures and public-key cryptosystems
Cryptography
A Timing Attack on RC5
A Practical Implementation of the Timing Attack
Differential Cryptanalysis of the Full 16-Round DES
The First Experimental Cryptanalysis of the Data Encryption Standard
Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems

--CTR
Ruggero Lanotte , Andrea Maggiolo-Schettini , Simone Tini, Information flow in hybrid systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.4, p.760-799, November 2004
cryptography;data encryption standard;timing attack;cryptanalysis