Hacker News Reader

I had to read the article a couple times.

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 don't think the post is about passwords in that sense, but of some kind of authorization tokens handed out by the server after authentication. E.g. in web frameworks an opaque session cookie that's used to index into server side session storage doesn't seem like a horribly exotic design choice.

The solution is the same. The server does sha256(token) and then looks that up in its magic table.

In fairness, almost nobody actually does this; they directly index the token itself.

Sure, and the post explicitly mentions that solution multiple times.

Never mind, I think I see it now. For posterity:

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?

So I'm not a security guy. And I don't know what kind of constraints Andy's system has, or what attack he was thinking of. But it just didn't seem like there was a need for a "use bcrypt" response since from the context these were not passwords in the classical sense. That'd be an inappropriate operation to have on the authorization fast path.

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.

This doesn't look like a straightforward attack, but it seems plausible and worth exploring. I think the word "password" just turned my brain off --- in part because I see so many people obsess about constant-time comparison for password hashes.

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.

This may be doable. Finding the size of the hash table and the length of each bucket seems like the hard part. What are real world differences between zero, one, and two long chains? Also, practically speaking, I think the attack assumes chaining, but both python and lua and others use open addressing, which makes it harder to target one bucket.

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.

Sure, I'm definitely not personally worried about this :-) Just spitballing on what such an attack might look like.

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.

Write a password library that uses bcrypt. Compare hashes with strcmp. Put it on the internet. See what happens. :)

That doesn't tell me anything. :/

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?

strcmp will stop at the end of the string. (the first zero or \0) Comparing the hashes ABC\0DEF and ABC\0XYZ will result true. There are a lot of hashcollisions which make finding a password a lot easier but the password won't work with sites that don't use strcmp.

That (using ==) is what py-bcrypt does, written by Damien Miller, a fairly well-known OpenSSH and OpenBSD hacker. It has definitely attracted some "smart" comments from "experts," as does anything that uses == in a security setting, no matter the actual context.

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.

Who do you think told me what happens? :)

Perfect. Small world.