Why not use `<`, `>` or `==` in constant time comparison?

Question

I am comparing secret data stored in arrays a and b to see which holds a greater value. My current (pseudo)code looks like this:

unsigned char smaller = 0, bigger = 0;
for (i = 0; i < size; ++i) {
   smaller |= (!bigger)  & (a[i] < b[i]);
   bigger  |= (!smaller) & (a[i] > b[i]);
}
return bigger;

But when I look at (for example) sodium_compare, I see they are not using the < or > operators. Instead they subtract values and do some bit-operations, amongst which shifting a byte by 8 (as a sidenote: doesn't that result in undefined behaviour in C?).

Is there a reason for avoiding the < and > operator?

Similarly, constant-time comparison for equality is usually implemented by taking the byte-wise xor (^) and take the or (|) of all values. Is there a reason for prefering ^ over == in that situation?

Answer 1

C comparison operators (strictly relational < <= > >= and equality == !=) yield 1 if the condition is satisfied and 0 if not. On some implementations (compilers) depending on the CPU and sometimes options, this may be implemented by code something like:

; int a = ..., b = ...;
; int x = a > b;
  move a, r0
  compare r0, b ; sometimes subtract with value ignored and only flags used
  bgtr lab1
    move 0, r1
    br lab2
lab1:
    move 1, r1
lab2:
  move r1, x

This executes a different sequence of instructions depending on whether the condition is true or false. Depending on the CPU, and if it has branch prediction/speculation as many (not all) do today depending on whether the conditional branch is predicted correctly which in turn depends on lots of other factors that are usually impossible to fully analyze, this may take different amounts of time which may be detectable (although typically damn small).

Some modern CPUs have conditional-move instructions, or even logicize-flag(s) instructions, that avoid this problem, but when writing source to be ported to unknown compiler versions and environments you can't be certain these will be present and (if so) used.

Actually you aren't guaranteed that even bitwise operations are constant time but in practice they're your best bet.

Similarly the logical negation operator ! in your code may be implemented by something like this which is not constant time:

move x, r0
test r0 ; sometimes included in the move
bzer lab1   ; (EDIT)
  move 0, r1
  br lab2
lab1:
  move 1, r1
lab2:
; use r1 as result

No Undefined Behavior:

Shifting by a count greater than or equal the width of the left operand is UB. Even when it comes from an unsigned char as in the code you linked, the left operand of a shift is subject to the Integer Promotions of 6.3.1.1 (though NOT the Usual Arithmetic Conversions of 6.3.1.8) and so the left operand always has a width of at least 16 and they shift by 8 which is okay.

Also left shifting a signed type with a negative value or a value that overflows (i.e. at least one of the high N magnitude bits of the input is nonzero) is UB. They don't shift left.

Right shifting a signed type with a negative value is Implementation Defined: the sign bit may propagate or shift out. They do shift right values that are sometimes negative, but they immediately mask the result so that the bits which could be affected by this IB are not used.