c++ - Optimization-stable constant-time array comparisons -

(note: "constant time", mean constant number of machine instructions 1 of inputs fixed, rather o(1). standard meaning of term in context of cryptography.)

the common way compare fixed value against unknown value of same size such no information fixed value leaked through timing use xor loop:

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

gcc 4.6.3 , clang 3.0 not short-circuit loop on amd64, @ -o3 (i checked generated machine code). however, not know of in c standard prevent clever compiler recognizing if c ever non-zero, function can return false.

if you're willing accept big performance hit , probabilistic comparison rather deterministic one, more paranoid way implement constant-time comparison compute cryptographic hashes of both inputs , compare hashes; doesn't matter how hashes compared because unless attacker can compute pre-images of hash, can't make successive approximations of unknown value. it's hard imagine compiler ever being smart enough optimize out, can't guarantee can't happen. more paranoid method use hmac instance-specific key rather simple hash, though can still imagine miraculously-smart optimizer recognizes regardless of key used, algorithm it's compiling slow way string comparison , optimizes accordingly. adding additional layers of complexity, calls shared libraries, etc., can make comparison arbitrarily hard optimize, still can't guarantee no standards-compliant compiler can ever short-circuit comparison , leave me vulnerable timing attacks.

is there way implement efficient, deterministic, constant-time comparison that's guaranteed work c standards? if not, popular c (or c++) compilers or libraries provide such method? please cite sources.

the "as-if" rule requires access volatile objects performed written, think following might work:

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

even if compiler can determine statically whether 2 input arrays differ, must still generate code of intermediate stores c. generated code should run time proportional n.

---

version 2, in response alexd's helpful comments:

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

even if compiler can statically determine return value of function, still have emit code read both input arrays in full, start finish, , write c in between loads. optimization still eliminate computation (xor , or), memory behaviors going more visible timing characteristic. power-wise, attacker may still able tell difference.

if wanted eliminate data-dependent branch in return statement, use akin go's constanttimebyteeq

---

just note, relevant bit of the 'as-if' rule has changed c++98/03 c++11:

1) @ every sequence point, values of volatile objects stable (previous evaluations complete, new evaluations not started) (until c++11)

1) accesses (reads , writes) volatile objects occur strictly according semantics of expressions in occur. in particular, not reordered. (since c++11)