Re:There are no good constant-time data structures
by nkurz on Tuesday December 02, 2014 @08:43PM
(#8691378)
A 2-way 1-ary cuckoo hash was going to be my answer as well. As you say, you want to always check both table indexes rather than waiting to see if you need to, but in almost all cases it's faster to do this anyway.
Since I think he only wants to check for equality, a constant time comparison of 160-bit values should be easy too. If you have a modern x86 machine with SSE4.1, the easiest might be to use _mm_cmpeq_epi64(vpcmpeqq), _mm_and_si128(pand), and _mm_testz_si128(ptest). With 256-bit vectors, it gets even simpler. But any scalar solution should be fine too as long as you can convince the compiler to do what you want.
Re:There are no good constant-time data structures
by Retric on Tuesday December 02, 2014 @05:55PM
(#8690615)
You likely to leak a fair amount of information simply from cache misses, but also things like branch prediction. Constant time operations in x86 is surprisingly hard.
Re:There are no good constant-time data structures
by TheLoneWolfling on Tuesday December 02, 2014 @06:21PM
(#8690791)
A cuckoo hashmap doesn't have any data-dependent branches, assuming the hash function itself is thusly secure.
And as for cache misses - what exactly is a cache miss going to tell you in this case? All it'll tell you is that that an input having a hash close to either hash of your input wasn't accessed recently. That, as far as I can tell, doesn't leak anything, assuming your passwords are salted.
Counterexample: Cuckoo hashmap, at least for lookup.
Calculate both hashes. Index the table via each hash. Check both table indexes to see if either match.
The only timing information this leaks is the length of the input string, and that an adversary already knows.
Now, there will be some cache information potentially leaked, although there are ways around that too. But this is constant time disregarding cache, and is sublinear.
As for the question of "a nice constant-time comparison algorithm for (say) 160-bit values", it's relatively easy. Do a pairwise comparison of constant-size chunks of the value, mapping <, =, and > to 01, 10, and 11, respectively. Then recurse as necessary. Of course, this assumes you have a constant-time comparison function for a single chunk.