Are there any working proof-of-concept string comparison timing attacks?

Question

I've tried to reproduce a string comparison timing oracle in two languages (Java and Python), but I'm not seeing any correlation in the timing based on the input into the comparison. Are there any examples out there, or do you see an issue with my code? Note that I would like something simple, like the example I have given. An attack on a large program "in the wild" is not a good example.

I've also not been able to find any simple and ready-to-run examples of timing attacks. I believe I've disabled Java's optimization with -Djava.compiler=NONE. It's taking a significant amount of time to run the code, so it's clearly not completely optimizing the code.

It seems odd that this is frequently talked about, but there are no actual easily-found examples out there.

Here is my Java code as it stands today. The output varies a bit randomly with no apparently correlation that I have identified. I've added some notes to the output so you can see which should be slower comparisons.

public class TimingAttackJavaTest {
    public static void main(String[] args) {
        TimeCompare("a0", "b0", "a, b      ");
        TimeCompare("aaaaaaaaaa1", "bbbbbbbbbbb1", "a*10, b*10");
        TimeCompare("aaaaaaaaaa10", "bbbbbbbbbbb10", "a*10, b*10");
        TimeCompare("aaaaaaaaaa2", "b2", "a*10, b  ");
        TimeCompare("a3", "bbbbbbbbbbb3", "a, b*10  ");
        TimeCompare("aaaaaaaaaa4", "bbbbbbbbbbb4", "a*10, b*10  ");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1", "a*100, a*100");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1", "a*100, a*100");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa2", "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb", "a*100, b*100");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa2", "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb", "a*100, b*100");

        TimeCompare("a", "a", "a, a      ");
        TimeCompare("aaaaaaaaaaa", "aaaaaaaaaaa", "a*1, a*10 ");
        TimeCompare("1aaaaaaaaaa10", "2bbbbbbbbbbb10", "a*10, b*10");
    }


    static void TimeCompare(String a, String b, String outputLabel)
    {
        boolean temp = false;
        long startTime;
        long endTime;
        long duration;

        startTime = System.nanoTime();
        for(int i = 0; i < 10000000; i++)
        {
            temp = a.equals(b);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println(outputLabel + temp + "\t\t" + duration);

    }
}

Output (note that the first comparison is always slow, as the program gets started):

a, b      false     930418800
a*10, b*10false     513034800
a*10, b*10false     510905300
a*10, b  false      534267200
a, b*10  false      524720700
a*10, b*10  false       509250100
a*100, a*100false       516159000    **This should return slowly**
a*100, a*100false       508714700    **This should return slowly**
a*100, b*100false       511160700    **This should return quickly**
a*100, b*100false       522029800    **This should return quickly**
a, a      true      278492700
a*1, a*10 true      284238900
a*10, b*10false     506245000

Answer 1

Your example isn't working for several reasons, chief of which is the fact that you're using the best possible case data (i.e. least likely to display differences). If the difference in the strings was at the start, the early-out comparison should alert you. However, since you're using a JIT language, there are all sorts of weird possibilities that might hinder such a check.

The best way to demonstrate this type of attack is not with loops, but with a single measurement in a low-level language such as C.

Here's a quick example that works very well:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
using namespace std;

// this is just strcmp() wrapped in timer calls
bool CheckEqual(char* a, char* b, bool show)
{
    int i, r, trv;
    long time_pre, time_post;
    struct timespec ts;

    if((trv = clock_gettime(CLOCK_MONOTONIC,&ts)) != 0) {
        printf("Timing error, pre. Code = %d\n", trv);
    }
    time_pre = ts.tv_nsec + (ts.tv_sec * 1000000000L);

    r = strcmp(a, b);

    if((trv = clock_gettime(CLOCK_MONOTONIC,&ts)) != 0) {
        printf("Timing error, post. Code = %d\n", trv);
    }
    time_post = ts.tv_nsec + (ts.tv_sec * 1000000000L);

    if (show)
        printf("Time: %ld\n", time_post - time_pre);
    else
        printf("First compare done.\n");

    return r == 0;
}

// this function helps us avoid the problem of the compiler being too smart.
// if we were to use string literals that were equal, it'd optimise compile-time
// constant strings into a single instance, so strcmp() would just early-out on
// the fact that the two pointers were equal, which is not what we want to
// demonstrate here - in reality we'd be comparing buffers that aren't static.
char* MakeStr(char c, int n)
{
    int i;
    char* s = (char*)calloc(n+1, sizeof(c));
    for(i=0; i<n; i++)
        s[i] = c;
    return s;
}

int main()
{
    // equal apart from last
    char* aa = MakeStr('0', 64);
    char* ab = "0000000000000000000000000000000000000000000000000000000000000001";

    // equal apart from first
    char* ba = MakeStr('0', 64);
    char* bb = "1000000000000000000000000000000000000000000000000000000000000000";

    // inequality in the middle
    char* ca = "0000000000000000000000000000010000000000000000000000000000000000";
    char* cb = "0000000000000000000000000000001000000000000000000000000000000000";

    // equal
    char* da = MakeStr('0', 64);
    char* db = MakeStr('0', 64);

    // first call to strcmp() and time functions will result in cache misses
    // so we call it once and don't display output to account for that.
    CheckEqual(aa, ab, false);

    printf("Equal but last, ");
    CheckEqual(aa, ab, true);
    printf("Equal but first, ");
    CheckEqual(ba, bb, true);
    printf("Equal but mid, ");
    CheckEqual(ca, cb, true);
    printf("Completely equal, ");
    CheckEqual(da, db, true);

    free(aa); free(ba); free(da); free(db);
    return 0;
}

Your output should look something like this:

First compare done.
Equal but last, Time: 345
Equal but first, Time: 229
Equal but mid, Time: 234
Completely equal, Time: 270

Notice the large difference between the first two? This is due to early-out optimisation, whereby the comparison exits as soon as it finds a difference. In the second comparison, it takes less time because the first character comparison shows it's not equal, so it can return early. In the third comparison, we see that this goes a little further into the string, resulting in a slightly longer runtime than the "equal but first", but shorter runtime than the "equal but last".

The completely equal one is an interesting beast. I'm guessing that, when the last character is not equal, there is some additional required logic. In comparison, the completely equal one takes less time, I assume because it just has to return 0.