This web page gives some information about my masters thesis and the topic of side channel cryptanalysis.
-James
Traditionally, the security of the algorithms used in cryptography have been analyzed only as mathematical functions. However, cryptography is done in the real world, with real devices like computers and smartcards which can cause these algorithms to behave quite differently than abstract mathematical functions. Doing cryptography in the real world can have physical side effects which are not considered in the traditional cryptographic model. For example, using a smart card to do cryptography requires an external power source, and the operations the smart card performs affects this power source. By monitoring the power consumed by the smart card an adversary can gain some information about what the smart card is doing.
The physical side effects of doing cryptography in the real world are said to be conveyed to observers through side channels. So, as noted above, a cryptographic algorithm implemented on a smart card has at least one side channel, namely, its power consumption.
Side channel cryptanalysis is the act of analyzing or attacking cryptosystems using side channel information.
Research done in the last half of the 1990s has shown that the information transmitted by side channels, such as execution time, computational faults and power consumption, can be detrimental to the security of ciphers like DES and RSA.
This thesis surveys the techniques of side channel cryptanalysis developed by Kocher [1996], Boneh, DeMillo and Lipton [1997], and Kocher, Jaffe and Jun [1999] and shows how side channel information can be used to break implementations of DES and RSA. Some specific techniques covered include the timing attack, differential fault analysis, simple power analysis and differential power analysis. Possible defenses against each of these side channel attacks are also discussed.
You can download a copy of my thesis by using these links.
PDF Version (836 KB)
Gzipped Post Script Version (619 KB)
Note, the postscript version has been compressed using gzip. Ghostview knows how to view compressed postscript, but should you need to uncompress the postscript version, you can do so with the following command:
gunzip mmthesis-side-channel.ps.gz.
A few people have asked me to give some more details about the timing experiments I conducted in Chapter 2 of my thesis.
The following email is a reply I wrote to a person asking about my timing experiments. It covers some of the more common questions I have received so I thought I would post it here:
(**please see the updated postscript at the end of the email**).
Date: Thu, 2 May 2002 15:24:24 -0400 (EDT)
From: James Muir
To: Eve
Subject: Re: Ask For Your Journal
Hi Eve,
Thank-you for your interest in my master's thesis. I hope this email will
help answer your questions.
> 1.Would you like to explain about your experiment at a glance and what
> steps have you done until you got the result at figure 2.4, 2.5, 2.6.
I will try to explain how I collected the experimental data and results
displayed in figures 2.3-2.7
First, my general goal in writing Chapter 2 was to perform a timing attack
against an implementation of RSA and present my experimental results. The
implementation of RSA I used was called RSAREF 2.0. I am attaching a copy
of the RSAREF 2.0 source code to this email.
I make several references to functions and constants defined in the RSAREF
2.0 source code in Chapter 2. I suggest you print out a copies of the files
NN.c and NN.h so you can see where these references come from.
Before you can do a timing attack you must have some sort of mechanism for
collecting timing measurements. Most modern CPUs have a built in function
called RDTSC (Read Time Stamp Counter) and it is this function that I used
to collect my timing measurements. You can call this function using
assembler code. An example of how to do this is given in Kris Heidenstrom's
FAQ document which is reference [27] in my bibliography.
I should note, you will need to do some programming in order to reproduce my
results. Hopefully, your are comfortable programming in C.
Here is the assemble code I used to call RDTSC. It is written for Borland's
Turbo Assembler:
#define rdtsc \
db 0x0f; \
db 0x31
#define gettimestamp(var) \
asm { \
rdtsc; \
db 0x66; \
mov word ptr var, ax; \
db 0x66; \
mov word ptr[+4] var, dx; \
}
Now, I will explain Figures 2.3-2.7.
Note, in each of the following experiments, N is a fixed 512-bit modulus.
The same value of N is used in each of the experiments.
Figure 2.3: The data in this figure represents the results of the following
experiment:
repeat one million times {
let x be a random 512-bit integer less than N.
read the TSC ( Time Stamp Counter ) into t0.
calculate x^2 mod N.
read the TSC into t1.
output t1-t0.
}
So, the figure represents the timing distribution of the modular square
operation.
Figure 2.4: The data in this figure represents the results of the following
experiment:
repeat one million times {
let x be a random 512-bit integer less than N.
let y be a random 512-bit integer less than N.
read the TSC ( Time Stamp Counter ) into t0.
calculate x*y mod N.
read the TSC into t1.
output t1-t0.
}
So, the figure represents the timing distribution of the modular
multiplication operation.
Figure 2.5: Fix a 64-bit exponent d = 0xFEDCBA9876543210. Note that the
value of d is write in Hexadecimal notation. The data in this figure
represents the results of the following experiment:
repeat ten thousand times {
let x be a random 512-bit integer less than N.
read the TSC ( Time Stamp Counter ) into t0.
calculate x^d mod N.
read the TSC into t1.
output t1-t0.
}
So, the figure represents the timing distribution of the modular
exponentiation operation.
Figure 2.6: In this experiment we pretend the value of d is a secret and
we try to use timing analysis to recover the value of d.
First, we choose 100 random messages:
x_1, x_2, ..., x_{100}
and timed how long it takes to compute x_i^d mod N for i=1..100. This
results in 100 timing measurements which we call:
T_1, T_2, ..., T_{100}
Let g be a guess for d. We are going to assume that the two most
significant bits of d are known. Now we are going to try and determine the
second most significant pair of bits. We let
g = 1100
g = 1101
g = 1110
g = 1111
Note here that the value of each g is written in binary.
Now, we timed how long it takes to compute x_i^g mod N for i=1..100.
This results in 100 timing measurements which we call:
t_1, t_2, ..., t_{100}
We do this for each of the four values of g. We compare each of the four
sets of data to
T_1, T_2, ..., T_{100}
and try to determine which one is correct using a statistical test
(comparison of variances). For example, we computed
T_1-t_1, T_2-t_2, ..., T_{100}-t_{100}
and then took the sample variance of this data. Doing this for each of the
four values of g results in four sets of data. The data set with the lowest
sample variance is supposed to represent the correct guess for the bits
of d.
Once the correct value for the pair of bits is determined you can move onto
the next most significant pair of bits. However, in my experiments to save
some time I decide to only do the timing analysis for every other pair of
bits.
The data in figure 2.6 describes how the successful the timing attack was.
I repeated the attack 25 times (using new values for x_1 ... x_{100} each
time).
Recall d = 0xFEDCBA9876543210. The position of each of the characters
F,E,D,C,B,A,9,8,7,6,5,4,3,2,1,0 denotes a pair of bits of d that I tried to
attack.
The first line of figure 2.6 reads:
bits observed estimated
F 0.44 0.41
When I say "bits F" I mean the second pair of most significant bits of d.
So in attacking these two bits I was only able to identify the correct value
44% of time (ie. in 44% of the 25 trials.)
The second line reads:
bits observed estimated
E 0.68 0.42
When I say "bits E" I mean the fourth most significant pair of bits of d.
So in attacking these two bits I was only able to identify the correct value
44% of time (ie. in 44% of the 25 trials.). By the way, the four values of
g you would use to determine these pair of bits are:
g = 1111 1100
g = 1111 1101
g = 1111 1110
g = 1111 1111
Remember g is written in binary.
Figure 2.7: Basically, I just repeated the experiment of Figure 2.6 except
that I used 1000 timing measurements instead of 100.
> 2.Would you like to give me your experiment timing attack program.
Unfortunately, I no longer have a soft copy of the program I used to collect
my results. It was on a computer in our lab and someone erased that hard
drive. However, it shouldn't take very long to write up a program from the
RSAREF 2.0 source code. And remember, you don't necessarily have to use the
RSAREF 2.0 source code. There might be another implementation of modular
exponentiation that might be easier to work with. For example, there is a
C++ library called NTL ( Number Theory Library ) that would work.
I hope this helps. Best of luck with your experiments.
Cheers.
-James
----------
Attachment:
RSAREF2.0 Source code
Pentium II Processor Application Notes: Using the RDTSC Instruction for Performance Monitoring (74 KB)
The Centre for Applied Cryptographic Research has a study group which focuses on implementation issues affecting the security of cryptosystems. The web page for the study group contains references to many relevant academic papers.
It has been remarked that the electromagnetic ( EM ) radiation which emanates from cryptographic devices might leak sensitive information to eavesdroppers. Apparently, the US government has done some (extensive) research in this area -- they have developed standards, code named TEMPEST, to protect against this type of side channel leakage.
An academic paper has recently appeared which takes some of the mystery out of EM attacks. Rao and Rohatgi report on some of the techniques they used to analysis the EM radiation from cryptographic tokens.
Bruce Schneier wrote a good non-technical overview of side channel attacks in his Crypto-gram Newsletter back in 1998.