News for hackers. Stuff that matters.
Re:There are no good constant-time data structures by pbsd on Tuesday December 02, 2014 @06:42PM (#8690890)
> 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;
    }
Re:There are no good constant-time data structures by tedunangst on Tuesday December 02, 2014 @09:31PM (#8691556)
This is very similar to the algorithm OpenBSD uses in timingsafe_memcmp().

http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string...

Re:There are no good constant-time data structures by pbsd on Tuesday December 02, 2014 @10:09PM (#8691686)
Indeed. 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).
Re:There are no good constant-time data structures by mirabilos on Wednesday December 03, 2014 @04:46AM (#8692765)
Right-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.
Re:There are no good constant-time data structures by pbsd on Wednesday December 03, 2014 @11:46AM (#8694716)
The `-` 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.
Re:There are no good constant-time data structures by DannyBee on Tuesday December 02, 2014 @07:31PM (#8691117)
Why not just use xor instead of "or + subtraction" in your "ne" function.
Re:There are no good constant-time data structures by pbsd on Tuesday December 02, 2014 @07:40PM (#8691143)
I'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.