[Cryptography] Implementing constant-time string comparison

[Ben Laurie]

On 17 June 2014 20:36, 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.

Not impossible. The compiler could make the same observation you have,
and optimise for that.

> Why are other libraries not doing this? That is, is this paranoid,
> or merely taking constant-time serious? Or does the 'unusual' return
> statement serve another purpose?
>
> For reference I added the code of some other implementations below.

You seem to be saying that other libraries are doing this?

> OpenSSL passes the problem on to the user of the library:

By "the problem", I presume you mean the issue of getting 0 or 1 out
of this. In general, the style is if (CRYPTO_memcmp(...)) (or ! that),
so 0 or 1 is not needed.

But I admit to once being bitten in the ass comparing "booleans" that
weren't (in this case bitfields, though), so I can agree it isn't best
practice.

> int CRYPTO_memcmp(const void *in_a, const void *in_b, size_t len)
>         {
>         size_t i;
>         const unsigned char *a = in_a;
>         const unsigned char *b = in_b;
>         unsigned char x = 0;
>
>         for (i = 0; i < len; i++)
>                 x |= a[i] ^ b[i];
>
>         return x;
>         }