The comparison c == 0
, like the rest of your code, will probably run in constant time.
However, there's no guarantee that it will, and it's just barely conceivable that there might be some compiler and CPU combination out there where it might not. Of course, that's basically true of any code not written in assembly for a specific CPU model and version.
After all, the C language standard does not actually offer any guarantees about execution times, and it would be perfectly valid for a smart enough compiler to look at your code, go "Hey! It looks like you're trying to compare two byte arrays for equality!" and decide to replace your code with a call to memcmp()
or something equivalent. And, as you can see from the results below, modern compilers actually are getting close to that level of cleverness, if they're not quite there yet.
Indeed, I suspect that the real reason why your code isn't getting optimized away like that is because compiler authors have more or less consciously decided not to make their compilers recognize it as a memory comparison, on the assumption that if you're writing your comparison code in such a convoluted way, you're probably doing something unusual and don't want it replaced by memcmp()
.
You can take a look at how common compilers translate your code into assembly using the Godbolt Compiler Explorer. It turns out that, even on the same CPU architecture, the result depends a lot on the compiler and the optimization level chosen.
(I've included a fairly long discussion of the x86-64 assembly produced by various compilers below, since it's kind of interesting in itself, but it's really only relevant as an illustration of how much the compiler output varies. Feel free to skip it.)
As a fairly typical example, when told to optimize your code for minimum size (-Os
), GCC 7.2 generates a rather nice and simple piece of assembly code:
equal(unsigned char*, unsigned char*, int):
xor eax, eax
xor ecx, ecx
.L3:
cmp edx, eax
jle .L2
mov r8b, BYTE PTR [rdi+rax]
xor r8b, BYTE PTR [rsi+rax]
inc rax
or ecx, r8d
jmp .L3
.L2:
test cl, cl
sete al
ret
The last three lines of assembly correspond to your return (c == 0)
statement, and indeed that part of the output seems to look pretty much the same (modulo register choices) for all compilers (for the x86-64 platform, that is) and optimization levels. I would indeed expect it to run in constant time, assuming that the timing of test
isn't data-dependent, which it really shouldn't be.
(At worst, if it wasn't constant-time on some CPU architecture, I'd expect the most likely timing differences to most likely be between the cases c == 0
and c != 0
, which the code reveals through its return value anyway. Of course, if you don't want that return value leaked through timings, e.g. because it's used as just one input to a more complex condition whose individual inputs should be secret, then even that leak could be too much.)
Of course, what typical timing attacks target isn't the final byte test, but the comparison loop itself. And that's where the compiler differences really come in. For example, at optimization level 1 or level 2, GCC's output looks quite similar to the code above. (The main difference is that the loop condition test is moved to the end and an explicit test for len <= 0
is inserted at the top of the code instead.) At optimization level 3, however, something weird happens and the output turns into this unrolled monstrosity:
equal(unsigned char*, unsigned char*, int):
test edx, edx
jle .L9
mov rcx, rdi
lea r8d, [rdx-1]
mov r9d, 17
neg rcx
push rbp
push rbx
and ecx, 15
lea eax, [rcx+15]
cmp eax, 17
cmovb eax, r9d
cmp r8d, eax
jb .L10
test ecx, ecx
je .L11
movzx r8d, BYTE PTR [rdi]
movzx r10d, BYTE PTR [rsi]
xor r10d, r8d
cmp ecx, 1
je .L12
movzx eax, BYTE PTR [rdi+1]
xor al, BYTE PTR [rsi+1]
or r10d, eax
cmp ecx, 2
je .L13
movzx eax, BYTE PTR [rdi+2]
xor al, BYTE PTR [rsi+2]
or r10d, eax
cmp ecx, 3
je .L14
movzx eax, BYTE PTR [rdi+3]
xor al, BYTE PTR [rsi+3]
or r10d, eax
cmp ecx, 4
je .L15
movzx eax, BYTE PTR [rdi+4]
xor al, BYTE PTR [rsi+4]
or r10d, eax
cmp ecx, 5
je .L16
movzx eax, BYTE PTR [rdi+5]
xor al, BYTE PTR [rsi+5]
or r10d, eax
cmp ecx, 6
je .L17
movzx eax, BYTE PTR [rdi+6]
xor al, BYTE PTR [rsi+6]
or r10d, eax
cmp ecx, 7
je .L18
movzx eax, BYTE PTR [rdi+7]
xor al, BYTE PTR [rsi+7]
or r10d, eax
cmp ecx, 8
je .L19
movzx eax, BYTE PTR [rdi+8]
xor al, BYTE PTR [rsi+8]
or r10d, eax
cmp ecx, 9
je .L20
movzx eax, BYTE PTR [rdi+9]
xor al, BYTE PTR [rsi+9]
or r10d, eax
cmp ecx, 10
je .L21
movzx eax, BYTE PTR [rdi+10]
xor al, BYTE PTR [rsi+10]
or r10d, eax
cmp ecx, 11
je .L22
movzx eax, BYTE PTR [rdi+11]
xor al, BYTE PTR [rsi+11]
or r10d, eax
cmp ecx, 12
je .L23
movzx eax, BYTE PTR [rdi+12]
xor al, BYTE PTR [rsi+12]
or r10d, eax
cmp ecx, 13
je .L24
movzx eax, BYTE PTR [rdi+13]
xor al, BYTE PTR [rsi+13]
or r10d, eax
cmp ecx, 14
je .L25
movzx eax, BYTE PTR [rsi+14]
xor al, BYTE PTR [rdi+14]
or r10d, eax
mov eax, 15
.L4:
mov ebp, edx
pxor xmm1, xmm1
sub ebp, ecx
mov r8d, ecx
xor r9d, r9d
mov ebx, ebp
lea r11, [rdi+r8]
xor ecx, ecx
shr ebx, 4
add r8, rsi
.L6:
movdqu xmm0, XMMWORD PTR [r8+rcx]
add r9d, 1
pxor xmm0, XMMWORD PTR [r11+rcx]
add rcx, 16
cmp ebx, r9d
por xmm1, xmm0
ja .L6
movdqa xmm0, xmm1
mov ecx, ebp
and ecx, -16
psrldq xmm0, 8
por xmm1, xmm0
add eax, ecx
movdqa xmm0, xmm1
psrldq xmm0, 4
por xmm1, xmm0
movdqa xmm0, xmm1
psrldq xmm0, 2
por xmm1, xmm0
movdqa xmm0, xmm1
psrldq xmm0, 1
por xmm1, xmm0
movaps XMMWORD PTR [rsp-40], xmm1
movzx r8d, BYTE PTR [rsp-40]
or r8d, r10d
cmp ebp, ecx
je .L7
.L3:
cdqe
.L8:
movzx ecx, BYTE PTR [rdi+rax]
xor cl, BYTE PTR [rsi+rax]
add rax, 1
or r8d, ecx
cmp edx, eax
jg .L8
.L7:
test r8b, r8b
sete al
pop rbx
pop rbp
ret
.L14:
mov eax, 3
jmp .L4
.L9:
mov eax, 1
ret
.L12:
mov eax, 1
jmp .L4
.L13:
mov eax, 2
jmp .L4
.L10:
xor eax, eax
xor r8d, r8d
jmp .L3
.L15:
mov eax, 4
jmp .L4
.L16:
mov eax, 5
jmp .L4
.L19:
mov eax, 8
jmp .L4
.L17:
mov eax, 6
jmp .L4
.L11:
xor eax, eax
xor r10d, r10d
jmp .L4
.L18:
mov eax, 7
jmp .L4
.L20:
mov eax, 9
jmp .L4
.L21:
mov eax, 10
jmp .L4
.L22:
mov eax, 11
jmp .L4
.L23:
mov eax, 12
jmp .L4
.L24:
mov eax, 13
jmp .L4
.L25:
mov eax, 14
jmp .L4
It looks like GCC has vectorized the XOR/OR loop to process 16 bytes at a time using SSE instructions, with a bunch of additional special case code to handle the possibility that len
might not be a multiple of 16. At a glance, I suspect this may still run in constant time (for any given len
value), but I wouldn't be more than pocket change on it.
FWIW, replacing the len
parameter with the constant 16
gets rid of all the special-case handling and yields this very elegant assembly code with no jumps or loops whatsoever. Literally translated back into C / C++, what it basically does is:
bool equal(unsigned char *a, unsigned char *b) {
uint128_t c = *(uint128_t *)a ^ *(uint128_t *)b;
c |= (c >> 64);
c |= (c >> 32);
c |= (c >> 16);
c |= (c >> 8);
return (unsigned char)c == 0;
}
As for other compilers, Clang's output looks pretty similar to GCC's at low optimization levels, but at -O2
and above, things get even weirder than with GCC. Again, that's clearly vectorized with SSE, but (if I'm parsing the code correctly) it's only reading the input 4 bytes at a time and doing some really weird within-register byte shuffling.
The core loop of ICC's output at -O3
looks similarly vectorized as GCC's, although the rest of the code is quite different. FWIW, if you fix the length at 16 bytes, ICC doesn't vectorize the code at all, although it does unroll it. Also, ICC at -O2
and above is the only x86-64 compiler I found that doesn't use the test
+ sete
combo for the final c == 0
test; it uses test
+ cmove
instead:
mov edx, 1
test al, al
mov eax, 0
cmove eax, edx
Anyway, in practice, the only way to be really confident that your code runs in constant time is to (first examine the assembly output for any telltale signs of potential timing issues, and then) test it.
For example, here's a quick and dirty online benchmark showing that (at least for the specific platform, compiler, options and parameters used) your code does seem to be constant-time:

The first two tests (AllDifferent and AllSame) are general baseline timing tests, the next two (FirstHalfSame and LastHalfSame) exercise the comparison loop to see if its execution time depends on the length of the matching prefix / suffix, and the last two (CaseFlipped and LSBFlipped) exercise the final c == 0
test by comparing two strings which differ only by having a specific bit in each byte flipped.
Of course, in practice, you should carry out your benchmark using the specific compiler and hardware you're targeting (or as wide a selection of both as possible, if you don't have a specific target) and using realistic inputs (e.g. not just constant strings) to reduce the chance of compiler optimizations messing up your benchmarks.
(For example, while making the quick benchmark above, I noticed that assigning the output of the comparison to a global variable was necessary to stop the compiler from optimizing out all the comparisons entirely(!) and making them all run at same speed as the "Noop" baseline loop. Also, in the AllSame test, I found that Clang is in fact smart enough to optimize out the comparison if both inputs point to the same address, so I had to use two separate strings with the same content to properly test it. Benchmarks can be tricky like that.)