[Cryptography] Implementing constant-time string comparison

[sycamoreone]

Steve Weis:
> On Tue, Jun 17, 2014 at 12:36 PM, sycamoreone
> <sycamoreone at riseup.net> wrote:
>> static int vn(const u8 *x,const u8 *y,int n) { u32 i,d = 0; for
>> (i = 0,i < n,++i) d |= x[i]^y[i]; return (1 & ((d - 1) >> 8)) -
>> 1; }
>> 
>> Here the expression in the return statement evaluates to (d ==
>> 0)-1 in a way that makes it impossible for the CPU to produce a
>> timing side-channel by short-circuiting a comparison of
>> (half)words.
> 
> I had not considered the (d == 0) comparison as potential timing
> leak, but think there is probably a good reason NaCl is using it.
> 
> I can see it would be a problem if there weren't a comparison 
> instruction of sufficient width, or if the compiler/interpreter
> did not use it, or if that instruction itself might not be constant
> time. My guess is that the first case is the issue motivating this.
> I'll find out though.

Or both are motivating this.

My guess so far was that this is just the philosophical difference
between writing "provable" constant-time code (taking into account that
processor makers don't document if word comparisons are constant time)
vs. fixing timing side-channels that have been shown to be exploitable.

> Incidentally, it looks like Go implements a constant-time int 
> comparison function as well: 
> http://golang.org/src/pkg/crypto/subtle/constant_time.go?s=897:936#L17

Go's
> 
subtle package was actually the first place I tripped over special
code for constant-time byte-equality. I thought that it would be better
to stick to C and Java here.