[Cryptography] Implementing constant-time string comparison

[sycamoreone]

Dear list,

various people have repeatedly shown that even small timing
side-channels in cryptographic software can be exploited
(e.g. Kocher, Bernstein, Boneh and Brumley).
I think that most libraries take this problems seriously now.

For comparison of byte arrays the NaCl library of Bernstein,
Lange et al. contains a function similar to this one
(with the loop unrolled):

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.

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.

Cheers,
Frithjof

---

Keyzar got this function in 2009, after Nate Lawson discovered that
the HMAC check uses a non-constant time string comparison.
(Similarly were added for the Java and Python implementations.)

bool SafeStringEquals(const std::string& s1, const std::string& s2) {
  if (s1.length() != s2.length())
     return false;

  int result = 0;
  for (int i = 0; i < s1.length(); ++i)
    result |= s1[i] ^ s2[i];
  return result == 0;
}

---

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

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;
        }

---

http://codahale.com/a-lesson-in-timing-attacks/  suggested this
Java implementation for Keyzar:

public static boolean isEqual(byte[] a, byte[] b) {
    if (a.length != b.length) {
        return false;
    }

    int result = 0;
    for (int i = 0; i < a.length; i++) {
      result |= a[i] ^ b[i]
    }
    return result == 0;
}