Timing vulnerability of byte array equality test?

Question

Would the following code to test MAC equality leak timing information ?

bool equal(unsigned char *a, unsigned char *b, int len) {
    unsigned char c = 0;
    for (int i = 0; i < len; i++) {
        c |= a[i] ^ b[i];
    }
    return c == 0;
}

More precisely, does the last expression c == 0leak timing information ?

I don't think so, because it doesn't allow to know where would be the mismatch.

Why are then some crypto libraries using complex expression to convert c into a 1 or 0 value than later simply compare that value with a simple == with 1 (or 0) ?

Would a timing difference between MAC mismatch and identical MAC condition be relevant ?

Answer 1

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.)

Answer 2

I looked over at how the Golang crypto library did this. The subtle package implements ConstantTimeCompare():

// ConstantTimeCompare returns 1 if and only if the two slices, x
// and y, have equal contents. The time taken is a function of the length of
// the slices and is independent of the contents.
func ConstantTimeCompare(x, y []byte) int {
    if len(x) != len(y) {
        return 0
    }

    var v byte

    for i := 0; i < len(x); i++ {
        v |= x[i] ^ y[i]
    }

    return ConstantTimeByteEq(v, 0)
  }

It looks to be largely similar to your own implementation, except the last comparison is different. It uses the ConstantTimeByteEq() function:

// ConstantTimeByteEq returns 1 if x == y and 0 otherwise.
func ConstantTimeByteEq(x, y uint8) int {
    z := ^(x ^ y)
    z &= z >> 4
    z &= z >> 2
    z &= z >> 1

    return int(z)
}

The reason for this is extreme caution. There are cases when, if both values are zero, the comparison can take less time. There's also the consideration of unknown compiler optimisations.

One StackOverflow answer mentions that the end comparison is for preventing branch misdirections.

Put simply, it is to allow the CPU only a single, constant-time, execution path for the single-byte comparison.