[Cryptography] Implementing constant-time string comparison

[ianG]

On 17/06/2014 23:07 pm, Steve Weis wrote:
> 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.


The problem is (I suspect) the optimiser.  If it can see back from the
boolean comparison, and into the loop, we run the danger of having
wildly different timings.

In C, you can do the neat trick with maths which an optimiser can't be
expected to reduce;  in fully typed languages, no such help applies
because we want a boolean, so from that boolean, optimisation can tease
its way in.

iang


> 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