12
$\begingroup$

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?

$\endgroup$
27
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Excellent answer of course. Did you also note the last part of the question though? "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?" Seems a logical thing to choose ^ over == to me, but maybe not so clear to Sebastian or other readers. $\endgroup$ – Maarten Bodewes Aug 17 '16 at 21:57
  • 1
    $\begingroup$ From the above answer I concluded that == might also be implemented with a branch. But let me know if something else is going on. $\endgroup$ – Sebastian Aug 17 '16 at 22:03
  • 2
    $\begingroup$ Excellent answer, especially the part that highlights fact that C standard does not in any way require even bitwise operations to produce constant time code. If implementor has to produce optimal code and/or be very certain that a compiler does not produce non-constant time code, the implementor needs to implement the instruction sequences in native code, rather than using C code (for instance via subfunctions, asm inline fragments, in some cases intrinsics). Even then documentation of the target platform needs to be examined carefully as some instructions execute in non-constant time. $\endgroup$ – user4982 Aug 18 '16 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.