[Cryptography] Implementing constant-time string comparison
sycamoreone
sycamoreone at riseup.net
Tue Jun 17 15:36:15 EDT 2014
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;
}
More information about the cryptography
mailing list