3 ms·

> a key-value map on common hardware that runs in constant time and is sublinear in the number of entries in the map Counterexample: Cuckoo hashmap, at least f

> a key-value map on common hardware that runs in constant time and is sublinear in the number of entries in the map 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.

Retric 12y ago
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.
- TheLoneWolfling 12y ago
  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.
nkurz 12y ago
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.

Retric 12y ago

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.

TheLoneWolfling 12y ago
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.

nkurz 12y ago

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.