Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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
share|improve this question
    
There are two core problems here: 1) JIT languages generally suck for demonstrating timing attacks; the overheads of JITing, object creation, boxing, GC, etc. swamp the execution time until the timing is almost meaningless 2) The operations you are doing don't have big enough discrepancies; a string compare of a few tens of characters is not a good choice for a demonstration. In fact, your assertion that the comparisons you chose should be faster or slower seems to be entirely wrong; abbbbb / bbbbbb should be fast, aaaaab / aaaaaa should be about the same. –  Polynomial Feb 4 at 15:27
    
@Polynomial, What do you mean by "about the same"? My "slow" ones are the same for the first ~100 characters so it should take 101 comparisons to see they aren't equal. My fast ones should return on the second comparison. I am thinking you are not seeing the comparison these correlate with, although I could absolutely be wrong. If string comparison timing attacks are supposed to be bruteforceable character-by-character remotely, across the internet, wouldn't 100 characters timed locally would be sufficient? –  Alex Lauerman Feb 4 at 17:11

1 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.

share|improve this answer
    
Thanks for your input! I reimplemented your solution and just repeated a few of the checks and your perceived time correlations are apparently because of program entrance and exit. Fair warning, I did not disable any comipiler optimizations. I can't put code in here and I dont want to create an answer so I'm linking externally for my example. gist.github.com/alexlauerman/8808811 –  Alex Lauerman Feb 4 at 17:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.