The scenario he's describing is:
1. A user submits a password (with no username) to authenticate.
2. The server looks up the password in a hash table. This involves:
a. Hashing the password to find the correct bucket.
b. Doing a string comparison against passwords stored in the bucket.
There are vulnerabilities in two places:1. Buckets containing more passwords will take longer to return a negative result because they will have to perform more string comparisons. (This irrelevant except in pathological cases.)
2. String comparisons with longer common prefixes will take longer to return a negative result.
This is a bad example for a couple reasons:
1. Password inputs are not compared directly to stored values in any real authentication system. They are hashed first. A timing attack here implies a preimage attack against the hash function.
2. Passwords are not global. Passwords are paired with a username. You don't get to time the comparison against every password in the system to determine common prefixes, for example.
A better example might have been API tokens, which are often stored in cleartext and fetched directly from the database.
I still don't follow. Good authentication tokens make extremely sparse use of their numeric domain; they are e.g. 128 bit numbers, of which only ~15-20 bits are needed. It doesn't look like there's enough information in the indices to incrementally attack them, which is how timing attacks work.
I buy that I'm just missing something here. I'm just looking for someone to reframe this issue in terms of what an attacker actually does.
The canonical example of the target you're referring to is a Java JSESSIONID cookie. So: what's the timing attack against JSESSIONID?
That said, I think we'd be talking of something like this for a web framework session storage attack:
Assumptions:
- A separate chained hash table implementation that doesn't use any kind of per-table randomization (e.g. like what Perl does for DOS prevention).
- A string comparison function that's not constant time.
What the attacker would do:
- Log in, observe session key.
- Generate on client side other tokens that would hash to the same bucket as the real session key
- Use a timing attack using the generated keys to determine the number of other session keys in the same hash bucket.
- Repeat with new logins until they find a bucket with exactly one other session key.
- Conduct a timing attack on the first character of the other session key in the bucket. (I.e. generate 256 fake session keys all hashing to the same bucket, each starting with a different byte).
- Conduct a timing attack on the second character.
- And so on.
- Once you've found a genuine session key, see whether it granted you any elevated rights.
Seems to me that the only thing that's needed is the ability to generate strings with an arbitrary prefix that hash to an arbitrary bucket. Without giving it too much thought, that seems pretty simple. I must be missing something here since you guys are finding this to be such an outlandish idea. Looking forward to hearing what it is.
That said, 'tedunangst's suggestion to hash before comparison seems sound; double-hashing is an old hack people use to do timing-safe comparisons of normal hashes, too.
So I'm still not sure you need timing-safe containers or timing-safe indices, although it's interesting to think about how you'd design them.
If this concerns you, I think I'd be more worried about a system that looks up tokens in a database. A (My/Post)SQL btree index may leak more data and is more "linearly" attackable.
I wouldn't have thought that figuring out the chain size is the weak point. Every step in the chain must add at least as much processing time as a string comparison that fails on the first byte, and the rest of the attack is already assuming that we can measure something at that resolution.
Sure, it's usually poignant critique, but anyone who actually knows anything about this subject agrees that doing a non-constant-time-compare on what is essentially a random oracle leaks nothing of value to an attacker, and people are just parroting a catch phrase without understanding it. It's the evolution of the fan favorite "That's security through obscurity!" applied outside cryptography.
As far as I can tell, you're implying an attacker can determine a password using timing of hash comparisons. How is this any different (just more complicated) than a regular brute force attack?
You do not need constant-time comparisons of password hashes; to see why, reason through how you'd attack them.
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.
You can 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.
In reality, though, you could just use a salted SHA1 hash (don't, though) and still be safe from this attack.