Can't explain data from side channel attack attempt

Question

I found the comparison function below (slightly modified) from a crypto library I was using. I was curious about the potential vulnerability to side channel attacks. Specifically, the character comparison is only done if the character being compared is within the bounds of the two strings. I suspected this might allow an attacker to determine string length.

Perhaps this difference is simply too small to be subject to a timing attack, but I played with an attempt below. I basically create strings of increasing lengths and compare to a given initial string. I was expecting to perhaps see linear growth in comparison time both before and after the point where the second string becomes longer, but perhaps with a different slope since the operations performed are different.

Instead, I see the data below (note the string being compared is 27 characters in length). Any explanation as to why I have no clue what I'm talking about would be greatly appreciated :)

A small note, I did try with -O0 in case some strange optimization was at fault. The only thing I can think to do from here is start digging into the generated assembly.

#include <string.h>
#include <sys/time.h>
#include <stdio.h>


int CompareStrings(const char* s1, const char* s2) {
    int eq = 1;
    int s1_len = strlen(s1);
    int s2_len = strlen(s2);

    if (s1_len != s2_len) {
        eq = 0;
    }

    const int max_len = (s2_len < s1_len) ? s1_len : s2_len;

    // to prevent timing attacks, should check entire string
    // don't exit after found to be false
    int i;
    for (i = 0; i < max_len; ++i) {
      if (s1_len >= i && s2_len >= i && s1[i] != s2[i]) {
        eq = 1;
      }
    }

    return eq;
}

double time_diff(struct timeval x , struct timeval y) {
    double x_ms , y_ms , diff;

    x_ms = (double)x.tv_sec*1000000 + (double)x.tv_usec;
    y_ms = (double)y.tv_sec*1000000 + (double)y.tv_usec;

    diff = (double)y_ms - (double)x_ms;

    return diff;
}

void test_with_length(char* str1, int n) {
    char str2[n + 1];
    struct timeval tp1;
    struct timeval tp2;
    int i;

    for (i = 0; i < n; i++) {
        str2[i] = 'a';
    }
    str2[n] = '\0';

    gettimeofday(&tp1, NULL);
    for (i = 0; i < 20000000; i++) {
        CompareStrings(str1, str2);
    }
    gettimeofday(&tp2, NULL);
    printf("%d %.01f\n", n, time_diff(tp1, tp2));
}

int main() {
    char *str1 = "XXXXXXXXXXXXXXXXXXXXXXXXXXX";

    int i = 0;
    for (i = 1; i <= 100; i++) {
        test_with_length(str1, i);
    }
}

Answer 1

First, some comments on the code:

• Your calls to strlen are a black box - you cannot possibly know how they react to timing attacks.
• Your compare loop exits after you exhaust the shortest string, leaking the shorter length.
• You did not remove bias generated by the loop in test_with_length.
• Array accesses are not O(1) time complexity, especially if each element is smaller than the word width of your CPU.

A better way to compensate for such attacks:

bool CompareStr(char* strA, char* strB)
{
    bool result = true;
    int lenA, lenB = 0;

    while(strA[n] != 0)
        lenA++;
    while(strB[n] != 0)
        lenB++;

    int maxLen = (lenA > lenB) ? lenA : lenB;

    // compensate for array access to some extent
    int diff = (lenA > lenB) ? lenA - lenB : lenB - lenA;
    char dummy = '\0';
    for(int i = 0; i < diff; i++) { dummy = strA[0]; }

    // better way to avoid timing attacks
    for(int i = 0; i < maxLen; i++)
    {
        if ( ((i >= lenA) ? strA[0] : strA[i]) != ((i >= lenB) ? strB[0] : strB[i]) )
            result = false;
    }

    return false;
}

// compute loop overhead
time_pre_loop = getTime();
for(int i = 0; i < LOOP_COUNT; i++) { }
time_post_loop = getTime();
double diff = time_diff(time_post_loop, time_pre_loop);

time_pre_test = getTime();
for(int i = 0; i < LOOP_COUNT; i++)
    CompareStr(strA, strB);
time_post_test = getTime();

double result = time_diff(time_post_test, time_pre_test) - diff;

Anyway, here's where the fun part starts. Consider the following assembly code that could be used to compute whether two strings are equal, with early-out optimisation removed as a basic timing attack defense:

 xor ecx, ecx                         ; clear counter to 0
 mov dword ptr ds:[0040AAAA], 1       ; set result to true
loopStart:
 mov ah, byte ptr ds:[ecx+00401234]   ; read char from string A
 mov bh, byte ptr ds:[ecx+00402468]   ; read char from string B
 cmp ah, bh                           ; compare the chars
 jz match                             ; are they equal?
 mov dword ptr ds:[0040AAAA], 0       ; strings don't match! set result to true
match:
 cmp ah, 0                            ; are we at the end of string A?
 jz done
 cmp bh, 0                            ; are we at the end of string B?
 jz done
 inc ecx                              ; increment counter and continue loop
 jmp loopStart
done:
 ret

There are actually a few timing attacks here. The first two instructions are O(1). However, the two single-byte reads that follow are not.

Whilst memory reads are usually O(1), in practice they will not be. In fact, they don't fit into the big-O model at all. On a 32-bit system, every 4th byte read will be faster than the others. On a 64-bit system, every 4th byte will be faster, and every 8th byte will be faster still. This is due to non-aligned memory reads. The CPU is great at fetching blocks of data that are aligned to its bus size, but not so great at fetching random individual bytes. The CPU will attempt to optimise this by pipelining instructions and loading the block into its L2 cache, which makes this issue more subtle, but it's still there.

The next trick is for strings that are larger than the CPU's cache. If you have a string that exceeds this size (usually 128KB or higher for the L2 cache) you'll see slight delays in memory fetches every time a read exceeds that boundary. This is usually only a small delay, since the L3 cache will be used to store the next block, but we can see an even bigger difference for larger strings (8MB+) as the memory fetches have to be done from system memory.

If we consider a block memory copy as O(n), where n is the memory length, this makes some sense, but does not properly depict the small variances in timing caused by implementation idiosyncrasies.

Finally, we can see that the mov dword ptr ds:[0040AAAA], 0 instruction is executed whenever one string does not match another. This leaks information in two ways:

• Allows us to estimate the relative length of the shorter string by identifying the extra time used when repeatedly setting the result.
• If we can measure accurately, allows us to identify which characters are different.

As we can see, it's quite difficult to prevent these issues. Here's my attempt at a better system, assuming fixed-length strings padded to alignment with null bytes:

int r, d = 0;
int* bufferA = (int*)stringA;
int* bufferB = (int*)stringB;
for(int i = 0; i < BUFFER_SIZE; i += 4)
{
    d = bufferA[i] ^ bufferB[i]; // if equal, d = 0
    r |= d; // if all cases are 0, r will be 0
}
return r; // result is 0 if equal, non-zero if not equal

This is almost perfectly O(n) for the following reasons:

• Bitwise xor of aligned ints is O(1)
• Bitwise or of aligned ints is O(1)
• Memory reads are aligned.
• Neither length is leaked, due to BUFFER_LENGTH padding.
• No branches, excluding the loop.

Answer 2

First, there is a bug in your comparison function; the "eq = 1;" in the loop should read "eq = 0;". It should not change the timing, though, assuming that the compiler does not play games with the optimizer. To make your code more resistant to optimization games, you should put the benchmarked function (your CompareStrings()) and the benchmark code (test_with_length()) in distinct modules (separately compiled C source files, and pray for the compiler not to perform inter-module optimizations -- gcc should be safe for that).

What you see looks correct. The two strlen() calls should have a cost which rises roughly linearly with the sum of the lengths of the two strings; but strlen() plays some nifty games in order to be faster. In particular, strlen() will try to read data bytes by whole aligned chunks (4, 8, 16 bytes maybe), and this will work because the compiler knows that memory access control by the MMU works on a page granularity, so it is possible to make "safe" out-of-bounds accesses in many cases. The small strings will have specialized versions, and the lengths here (at most 100 bytes) are too small to really exhibit asymptotic behaviours.

Chances are that the cost of the two strlen() is small with regards to the for loop. It will introduce some "noise" in the graph, though, so you should not look too closely at the dots.

The for loop will run for max_len steps, which is the length of the longer of the two strings. Therefore, as a first approximation, we expect the cost of that loop to be linear in the length of the larger of the two strings, so you should see a roughly constant time when the second operand length grows from 1 to 27, then an increase -- which is what you see in the graph.