20-CS-6056 Security Vulnerability Assessment Spring 2017
Lab 5

Authentication, Availability, Confidentiality, Integrity, Defense Principles, Intrusion Detection, Attack vectors, more

Determine Keybits from Timing Data

Some cryptographic schemes have mathematical properties which make them difficult to attack mathematically. However, some of these are vulnerable to other methods of attack, such as timimg attacks, that were largely unknown when the schemes were first embraced. A case in point are algorithms which rely on modular exponentiation, like this:

   S = md mod n

where m is a string of bits representing, say, a message, d is a private key, and n is a publicly known modulus. An eavedropper intercepting S could use a fast algorithm for finding the modular log of S to find the private key but no such algorithm is known if the keysize is a couple of thousand bits long, hence the claim of security.

Unfortunately, the algorithm for computing S may be implemented in such a way that key bit information is leaked through timing differences between iterations that use a 0 key bit and those that use a 1 key bit. For example, consider the following C code for computing S:

  01 int modpow (int base, int exp, int mod) {
  02    int w, k, r0, r1 = 1;
  04    w = ceil(log(exp)/log(2));
  05    for (k=w-1 ; k >= 0 ; k--) {
  06       if (((exp >> k) & 1) == 1)
  07          r0 = r1*base % mod;
  08       else
  09          r0 = r1;
  10       r1 = r0*r0 % mod;
  11    }
  12    return r0;
  13 }
  14 ...
  14 int S = modpow(m, d, n);

The modpow function iterates w times, one time for each bit of private key exp (the size w of key exp is computed on line 04). When an iteration is on a key bit that has value 1, line 07 is computed. Otherwise, line 09 is computed. Clearly, on a computer for which an iteration on a 1 key bit always takes the same amount of time and likewise for a 0 key bit, the 1 key bit iterations will always take longer than the 0 key bit iterations because line 07 will always take more time than line 09. This would allow an attacker to determine the key bits easily by running a spy process that measures the time of each iteration of modpow. However, such a computer is not likely to be used by a victim that uses modpow. But, an attacker can use statistics from a number of input samples to get most of the key bits: more correct key bits will be acquired as the number of samples increases. Here's how.

The attacker collects some large number of input samples, m1, m2, ..., mp. The attacker measures and records the time of each of w iterations on each mi input for both key bit 0 and key bit 1. That's a total of w*p*2 measurements. These will be referenced below as iterTimei,k,b where i refers to sample mi, k refers to a key bit, and b refers to the value of the key bit. Note that the times for the same iteration on the same key bit value will differ from input to input due to non-deterministic changes in execution by the operating system and other threads running on the same machine. For example, for key bit 0 and 5 inputs the following might be recorded (in nanoseconds):

   for key value 0: 45 48 39 42 41
   for key value 1: 46 44 40 46 47

Observe that, over all inputs, sometimes the measured time is less for a 0 value of key bit and sometimes it is more.

The attacker also has the victim exponentiate samples m1 ... mp using the key d and modulus n. This is easily possible if, for example, the key is used to sign plaintext messages. The attacker's spy thread watches the victim's code as it iterates and creates a table of times from victim start to victim's kth iteration, for k from 0 to w-1. There are a number of ways a spy thread can know when the victim thread is running a particular operation and therefore is at a particular point in the loop, particularly if both threads share some hardware resources such as a multiplier. Let this table be indexed as spyTimei,k. Consider the two differences:

   abs(iterTimei,0,0-spyTimei,0)     (1)
   abs(iterTimei,0,1-spyTimei,0)     (2)

If the 0th key bit is 0, one would expect the sum of differences (1) over all input samples to be less than the sum of differences (2). If the 0th key bit is 1, the (2) differences would be less. Recall the definition of variance:

    Σi (Xi-μ)2
σ2  = 
for p random samples Xi with mean μ. Let Xi be (1) or (2). The smallest resulting variance of the two cases will likely determine the 0th key bit if the sample size is large enough, hence we call this a guess. Once the first key bit is guessed the attacker can guess the second key bit in the same way using times associated with the first two iterations (the attacker has this information for the spy thread and can get it from the iterTime table that was constructed from experiments). Assuming the random values are independent (probably reasonable) the variance of the second key bit difference is only affected by the correctness of the second guessed key bit and again the lowest variance fingers the likely key bit value. This process may be repeated to guess the remaining key bits with high likelihood that the key bits have been found.

The file lab5aux.o is an ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV) object file. This file has functions that enable building iterTimei,k,b and spyTimei,k tables. The number of input samples these tables are built for is given by the user as will be shown below. The spyTime tables are built from a fixed key of 32 bits. Access to these tables is through the following functions:

    getIterationTime(i,k,b)  :  Time it takes for the kth iteration of the exponentiation algorithm on input sample i if the kth exponent bit (keybit) is b.

    getSpyTime(i,k)  :  Time it takes for the victim's code to complete iterations 0 through k on the ith input sample as observed by the spy thread.

The file lab5.c shows how to use lab5aux.o. Compile this file and link it to lab5aux.o with the following:

   gcc lab5.c lab5aux.o -o lab5

run it like this, for example:

   ./lab5 30

which produces tables for 30 input samples and prints those tables.

Your assignment is to modify lab5.c to enable guessing all the key bit values stored in lab5aux.o. Please do not try to reverse engineer the key bit values. Please observe that you will have to find an optimal number of samples - too few will incur errors, too many may cause a crash.

Upload both the code and your guess of the key (binary, decimal, or hex).