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.

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)