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.