4 ms·
> One problem is, I don't know of a nice constant-time comparison algorithm for (say) 160-bit values. [...] I would appreciate any pointers to such a constant-t
by pbsd 12y ago
> One problem is, I don't know of a nice constant-time comparison algorithm for (say) 160-bit values. [...] I would appreciate any pointers to such a constant-time less-than algorithm.
The following should be constant-time relatively to the contents of its inputs:
// return -1 if x < y, else 0
static unsigned lt(unsigned x, unsigned y) {
return -((x - y) >> (sizeof(x)*8-1));
}
// return -1 if x != y, else 0
static unsigned ne(unsigned x, unsigned y) {
const unsigned d = (x - y) | (y - x);
return -(d >> (sizeof(d)*8-1));
}
// return 1 if x[0..n-1] is lexicographically less than y[0..n-1], else 0
int less_than(const unsigned char * x, const unsigned char * y, size_t n) {
unsigned flag = 0;
unsigned done = 0;
for(size_t i = 0; i < n; ++i) {
flag |= lt(x[i], y[i]) & ~done;
done = ne(x[i], y[i]);
}
return flag & 1;
}
- deleted 12y ago[deleted]
- DannyBee 12y agoWhy not just use xor instead of "or + subtraction" in your "ne" function.
- pbsd 12y agoI'm not sure I understand what you're suggesting. x ^ y will obviously never be 0 when x != y, but there is no quick way to locate where they differ to turn it into a mask. When x != y, either x - y or y - x will be negative and therefore have the MSB set.
- tedunangst 12y agoThis is very similar to the algorithm OpenBSD uses in timingsafe_memcmp(). http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/timingsafe_memcmp.c?rev=1.1&content-type=text/x-cvsweb-markup http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string...
- pbsd 12y agoIndeed. The two main differences are that I didn't care about returning {-1, 0, 1} to emulate `memcmp`, and that I don't rely on implementation-defined behavior (signed shifts being arithmetic).
- mirabilos 12y agoRight-shift of signed integer values is implementation-defined behaviour though. If (x - y) is unsigned, the comments are wrong, they would return 1, not -1.
- pbsd 12y agoThe `-` is there to turn 1 into -1 (mod 2^n), and 0 into 0. I use `- (x >> (sizeof(x)*8-1))` to get arithmetic shift semantics while only using unsigned arithmetic.