Change the function such that there are no more side-channels

Question

Given is the function compareKey which is a part of a crackme (a binary file). Which side-channel attack can be used to find the right password (password is made up by ASCII coded big and small letters from a-z, and decimals) and how can you design this function such that there isn't any side-channel?

int compareKey() {
    unsigned int leng = strleng(keyInput);
    unsigned int correctLeng = strleng(correctKey);
    int i, randomTime, falseKey = 0;

    unsigned int seed = getpid() + keyInput[0];
    srand(seed);  // initialize the random seed

    if (leng != correctLeng)
        return 1;

    for (i = correctLeng-1; i >= 0; i--) {
        if (keyInput[i] != correctKey[i]) {
            usleep(500000);  // that delay will stop bruteforce attack

            falseKey = 1;
        }
    }
    randomTime = 500000 * (rand() % 3);
    usleep(randomTime); // take that
    // and this will prevent the attacker to perform a timed attack

    return falseKey;
}

So I have already executed the crackme binary and entered some passwords of different length. I realized that if the password has length 7, it needs waaay more time to print Wrong (wrong password..). If the password has any other length than 7, it immediately prints Wrong. Thus the password is most likely of length 7 (it indeed is!) and we probably have a timing attack here because we see from the above code that the two strings keyInput and correctKey) are compared character by character and alert mismatch when they see a difference between the two characters that are currently being compared.

Is this correct obersvation so far?

We can fix this side-channel like this:

def secureCompare(stringA, stringB) :
    if (sha256(A) == sha256(B))
        return True
    else
        return False
OR

def secureCompare(stringA, stringB) :
    if leng(A) != leng(B):
        return False

    result = 0
    for x, y in zip(A, B) :
        result |= x ^ y
    return result == 0

Is it alright like that I'm really not sure? : /

score 3 · Answer 1 · answered May 07 '18 at 18:45

Both of your suggested implementations have issues.

The first one fails because you still have to worry about timing when comparing hashes, and the == operator is almost certainly not constant time.

The second one fails for two reasons, both of which allow an attacker to easily determine the length of the secret:

You have an early out.
Python's zip truncates to the length of the shortest iterator, so an attacker can keep increasing the length of their input until the time stays the same.

Maarten Bodewes · Answer 2 · 2018-05-11T12:26:30.757

I'd first copy the passwords into a buffer of a static size, then fill the rest of the buffer with a static zero string using the same copy function (otherwise the copy will leak size info). Even then you may leak some size info as the copy may cross a page boundary, but in general that kind of caching information is only leaked if an attack originates from the same machine. Calculating the size may also leak information (round and round we go, aint that fun).

The static string must have a specific value that cannot be part of the input, otherwise passwords that end with something in the static buffer will compare to the same value as shorter passwords (hiy|aa would be identical to hiya|a), where | is concatenation.

Another option is to first copy the length into the array so you can have a randomized string (which must of course be the same for the value to compare).

Let's name the statically sized x and y as x' and y' Then I would generate a random key and compare HMAC(K_r, x') with HMAC(K_r, y'). This won't leak any info about the input value because the HMAC instead of the input is randomized for each comparison. You could possibly also use H(K_r | x') and H(K_r | y') for this.

If you decide to use a random delay then perform it before the operation. This makes it harder to perform any power measurements during the operations, in case you're not just worried about timing based attacks.

Change the function such that there are no more side-channels

2 Answers2