I feel like I must be missing something here.<p>You do not need constant-time comparisons of password hashes; to see why, reason through how you'd attack them.<p>An attack against an HMAC authenticator provides full, incremental control over the hash. No such control exists for a password hash; you can't step from "AAAAAA" to "AAAAAB" without a devastating break in the hash function itself. The capability to predict the input that generates "AAAAAB" implies a total failure of preimage resistance.<p>You <i>can</i> end up in a situation where timing leaks are relevant to password authentication. To do that, you need to design your own password storage system, and it needs to be badly flawed; for instance, you could literally use a general-purpose fast lookup hash and a chaining hash table. This is yet another reason to simply use bcrypt or scrypt to store passwords; doing so takes timing off the table.<p>In reality, though, you could just use a salted SHA1 hash (don't, though) and still be safe from this attack.
I don't understand: why not write the function to take a predetermined (or even slightly random) amount of time to run, and have it just sleep at the end of execution until the timer's up?
> a key-value map on common hardware that runs in constant time and is sublinear in the number of entries in the map<p>Counterexample: Cuckoo hashmap, at least for lookup.<p>Calculate both hashes. Index the table via each hash. Check both table indexes to see if either match.<p>The only timing information this leaks is the length of the input string, and that an adversary already knows.<p>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.<p>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.
> 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.<p>The following should be constant-time relatively to the contents of its inputs:<p><pre><code> // 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;
}</code></pre>
<p><pre><code> //quantize run duration to mitigate timing attacks
checkPasswordWrapper(...) {
result = checkPassword(...)
until (getMilliseconds() % 250) {
sleep(1) //Needs optimization
}
return result
}</code></pre>
You can gate the completion of each hash lookup with an absolute-sleep, e.g. using the POSIX function clock_nanosleep with a flags value of TIMER_ABSTIME.<p>Before the hash lookup, calculate a set time into the future, say 300 ms. Then do the hash lookup. Then wait until the predetermined time and return the result.<p>Waking up a thread at a specific time is just real-time programming 101.<p>Another idea: if you have some context information that lets you identify that queries are coming from the same entity (same IP address, same tty, same operating system user, whatever), you can impose a shadow ban after 10 unsuccessful tries: fail even if there is a hash "hit", and randomize the times to feed the attacker junk timing data.
One approach is to use a hash table where each entry has a block of values, not a linear list. The entire block is always tested linearly, even though most of the values are null. Block overflow means an expensive operation to increase the size of the hash table or the blocks, but that's an insertion-time issue, not a lookup-time one.<p>There's still the problem of cache noise.
So, hash tables don't really work like this. There's no reason for the "FOOBAR" password to be stored close to "FOOBAZ", if you pick a well behaved hash function. You might get to know how many passwords are on the same hash bucket, but that's it. Furthermore, the authentication will be accessed over a network. The network latency (and it's variance) is several orders of magnitude larger than the possible variations. It would be seriously hard to measure something like this with the resolution needed (nanoseconds). Even if you're taking samples and doing an average based guess, you'd need an absurd number of samples (so a bruteforce attack on passwords would be more feasible?)<p>Edit: Actually, even if by coincidence you did get FOOBAZ on the same bucket as FOOBAR, you wouldn't be able to easily distinguish from a single comparison with 5 equal characters from multiple comparisons with smaller number of equal characters. Also, if you're getting that many collisions to the point that this is a problem, you've sized your hash table incorrectly.
For the problem mentioned in the post (determining whether a given password is valid), how about using a Trie[0]? Wouldn't this work perfectly in this situation?<p>[0]: <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow">http://en.wikipedia.org/wiki/Trie</a>
I'm embarrassed to admit that I thought "timing attacks" had something to do with race condition bugs. ...Crap, I've got some reading to catch up on.