CompareStrings is not timing safe

[AndrewCarterUK]

I've created a script for testing the CompareStrings function as after glancing over it I suspected that it wasn't a constant time function.

The results from my script suggest that my suspicions were correct and that the function does not execute in a constant time.

The graph below shows the average time to execute 100 million comparisons, where Z is a zero length string and A and B are different strings of the same length (26 chars).

As you can see, comparisons with a different length of string have very different execution times. Even with the same length of string, comparisons of matching strings run faster than comparisons of different strings.

I've annotated the function in question below, to show where I understand that it might be leaking timing information.

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

    // UNSAFE: This executes different instructions for a different length of string
    if (s1_len != s2_len) {
        eq = false;
    }

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

    for (int i = 0; i < max_len; ++i) {
      // UNSAFE: s1 and s2 are only referenced if the index is valid (different instructions executed for different length of string)
      if (s1_len >= i && s2_len >= i && s1[i] != s2[i]) {
        // UNSAFE: This instruction is only executed if the bytes are different
        eq = false;
      }
    }

    return eq;
}

One fundamental component to writing timing safe code, is ensuring that the same instructions are executed regardless of the input. Comparison statements such as if and ? are almost always not timing safe, as they result in different instructions executed dependent on the outcome of the comparison. Even when this is done, execution may be dependent on input as processor caches and branch prediction can also have a large impact on execution speed.

It's very difficult to get a timing safe comparison algorithm that can handle strings of different lengths. The only approach I can suggest is hashing the strings before comparing them, and even then there are other flaws associated with this approach.

I'm not a security expert (and I would seek the advice on one for a topic as important as this on a popular library), but a function such as the one below appears to have less variation on execution time (though it still have some). The downside of course is that it requires the strings to be of the same length, but this could potentially be mitigated by passing the inputs through a timing safe hash function beforehand.

bool CompareStrings(const char* s1, const char* s2, int len) {
    int different = 0;

    for (int i = 0; i < len; ++i) {
        different = different | (s1[i] ^ s2[i]);
    }

    return (bool) !different;
}

[recrsn]

It is indeed difficult to write a timing-safe code handling strings of varying length.

But if we short-circuit immediately after encountering unequal lengths. This will, however, probably leak the length of the known string. This should be fine as the attacker knows the length of the known string anyway.

String comparison implementation in Java and PHP exhibit this behaviour.

[ncb000gt]

This has been discussed a few times before in the history of this project (GH-13 and GH-266), but basically it boils down to bcrypt isn't susceptible to timing attacks like you're describing.

It basically boils down to the comparison function compares hashes: https://github.com/kelektiv/node.bcrypt.js/blob/master/src/bcrypt_node.cc#L338

You can see that we do hash the value passed in before running the comparison. We couldn't do it any other way anyway since we can't reverse the hash in the first place.

Also, here is a more detailed discussion related to this topic @ bcrypt-ruby/bcrypt-ruby#43

Does that help?

[AndrewCarterUK]

Yup that makes sense.

I actually stumbled across this because a member of my team was using a comparison with an empty hash to try and prevent leaking to an attacker whether an authentication failure was due to the user not existing or an incorrect password.

The pseudo-code for what they were doing is something like:

user = getUser(email)

if (validate(user.hash or "", password)) {
  // logged in
} else {
  // auth fail
}

Ignoring the many other obvious places where the above code leaks information through timing (database access, etc) - I assume this isn't a supported feature of the library? I doubted it was which was part of the reason I was digging into the code in the first place.

If this isn't something that the library supports then it might be worth just using a normal string comparison function and removing the claim that the design of the function prevents timing attacks?

[ncb000gt]

@AndrewCarterUK yea. I agree with that. There was discussion very early on about changes to prevent timing attacks, and some work done to try to make the comparator be "constant time". But, once we realized that bcrypt wasn't actually susceptible, we stopped focusing on that. We get enough of these that it makes sense to put something, like what I posted above, in the readme. So I'll make a couple of those changes.