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.