[Cryptography] Implementing constant-time string comparison

[Steve Weis]

Comments inline...

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.

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