Security / Timing Attack and Constant-time Compare Algorithm

Posted On 02.07.2022

Timing attack is the type of attack when an attacker tries to analyze the time it takes your application to do something, in order to guess the data it’s operating on.

For example, you build an API and try to secure it by checking if the access token matched with some secret token:

const verifyAccessToken = (request: RequestData) => {
    const token = request.header['AccessToken'];
    if (token == SECRET_TOKEN) {
        return true;
    } else {
        return false;
    }
};

By doing this, your code is vulnerable to timing attacks. The reason is, for most languages, string comparison algorithm works like this:

compare(s1, s2):
    if len(s1) != len(s2) then
        return false
    else
        for each character (c1, c2) in (s1, s2)
            if c1 != c2 then
                return false
    finally
        return true

The algorithm iterates over each character of the two string, and stop right after it found the difference. So, different inputs will take different amounts of time to run, depending on the location of the first difference.

Using the time difference, the attacker can guess what’s inside the secret token. For example, if comparing each character takes 1µs, and some complete mismatch input will fail immediately:

Time taken: 0µs
 
S E C R E T
^
D O N U T S
^

Then, the attacker found that input starts the letter S takes a slightly longer time to return, they know that the letter S exists in the secret code:

Time taken: 1µs
 
S E C R E T
  ^
S O N U T S
  ^

Repeat this process for the remaining letters somehow, they can guess their way to the final secret:

Time taken: 4µs
 
S E C R E T
      ^
S E C U R E
      ^

So, it’s necessary to avoid variable-time comparison algorithms like this when comparing secrets, instead, we should use constant-time comparison algorithms, these algorithms take the same amount of time to run regardless of the location of the difference in the input.

constant_compare(s1, s2):
    if len(s1) != len(s2) then
        return false
    else
        result = 0
        i = 0
        while i < len(s1) and i < len(s2)
            result |= s1[i] ^ s2[i]
            i++
        return result == 0

What’s next?