Optimization-stable constant-time array comparisons

Question

(Note: by "constant time", I mean a constant number of machine cycles when one of the inputs is fixed, rather than O(1). This is the standard meaning of the term in the context of cryptography.)

The most common way to compare a fixed value against an unknown value of the same size such that no information about the fixed value is leaked through timing is to use an XOR loop:

bool compare(const char* fixed, const char* unknown, size_t n)
{
    char c = 0;
    for (size_t i=0; i<n; ++i)
        c |= fixed[i] ^ unknown[i];
    return (c == 0);
}

GCC 4.6.3 and CLANG 3.0 do not short-circuit this loop on AMD64, even at -O3 (I checked the generated machine code). However, I do not know of anything in the C standard that would prevent some clever compiler from recognizing that if c is ever non-zero, then the function can only return false.

If you're willing to accept a big performance hit and a probabilistic comparison rather than a deterministic one, the more paranoid way to implement a constant-time comparison is to compute cryptographic hashes of both inputs and compare the hashes; it doesn't matter how the hashes are compared because unless the attacker can compute pre-images of the hash, it can't make successive approximations of an unknown value. It's hard to imagine a compiler ever being smart enough to optimize this out, but I can't guarantee that it can't happen. The even more paranoid method is to use HMAC with an instance-specific key rather than a simple hash, though I can still imagine a miraculously-smart optimizer that recognizes that regardless of what key is used, the algorithm it's compiling is just a slow way to do a string comparison and optimizes accordingly. By adding additional layers of complexity, calls into shared libraries, etc., I can make my comparison arbitrarily hard to optimize, but I still can't guarantee that no standards-compliant compiler can ever short-circuit my comparison and leave me vulnerable to timing attacks.

Is there any way to implement an efficient, deterministic, constant-time comparison that's guaranteed to always work by the C standards? If not, do any popular C (or C++) compilers or libraries provide such a method? Please cite your sources.

Matchmaker

By "constant-time," do you mean O(1), or do you mean "always taking the same amount of time to run, regardless of the input, and therefore suitable for cryptographic use?" – Unquote

The OP very clearly means the latter. – Committeewoman

@templatetypedef: I mean that the comparison always runs in the same number of machine cycles when one of the inputs is fixed. In other words, no timing side channels that could be used to calculate the fixed input's value. – Matchmaker

Answer 1

The "as-if" rule requires that access to volatile objects be performed as written, so I think the following might work:

bool compare(const char* p1, const char* p2, size_t n)
{
    volatile char c = 0;
    for (size_t i=0; i<n; ++i)
        c |= p1[i] ^ p2[i];
    return (c == 0);
}

Even if the compiler can determine statically whether the two input arrays differ, it must still generate code for all of the intermediate stores to c. So the generated code should always run for a time proportional to n.

---

Version 2, in response to AlexD's helpful comments:

bool compare(volatile const char* p1, volatile const char* p2, size_t n)
{
    volatile char c = 0;
    for (size_t i=0; i<n; ++i)
        c |= p1[i] ^ p2[i];
    return (c == 0);
}

Even if the compiler can statically determine the return value of the function, it will still have to emit code to read both the input arrays in full, from start to finish, and to write to c in between those loads. Optimization could still eliminate the computation (XOR and OR), but the memory behaviors is going to be the much more visible timing characteristic. Power-wise, an attacker may still be able to tell the difference.

If we wanted to eliminate the data-dependent branch in the return statement, we could use something akin to Go's ConstantTimeByteEq

---

Just a note, that the relevant bit of the 'as-if' rule has changed from C++98/03 to C++11:

1) At every sequence point, the values of all volatile objects are stable (previous evaluations are complete, new evaluations not started) (until C++11)

1) Accesses (reads and writes) to volatile objects occur strictly according to the semantics of the expressions in which they occur. In particular, they are not reordered. (since C++11)

Committeewoman

In your case, if the compiler statically determines that arrays are the same, it does not need to generate code for any comparisons, right? It just needs to write 0 to c n times. – Carillo

You're right, that the compiler could reduce "statically equal" cases to just emitting c = 0 stores n times. That could reasonably take less time than actually computing the XOR on each point. You've reminded me that I should make the inputs volatile as well so that the loads can't be elided. – Committeewoman

You're replicating the OP's bug of using n as the index ... you should point that out and fix it. Also the missing semicolon (and unnecessary parens) in the return statement. – Venezuela

Good catch. I've fixed the correcness errors you pointed out, but left the stylistic choices as in the OP. – Committeewoman

@AlexD: The case where both inputs can be statically proved to be identical isn't an issue in practice, since in order for there to be a timing attack, one of the inputs must be controlled by the attacker. But that's still a good detail to point out. – Matchmaker

Update: Robert Seacord (who is on the C standards committee) told me that this answer is correct. – Matchmaker