2 ms·

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 fra

by jsnell 12y ago

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.

tedunangst 12y ago
The solution is the same. The server does sha256(token) and then looks that up in its magic table.
- tptacek 12y ago
  In fairness, almost nobody actually does this; they directly index the token itself.
- jsnell 12y ago
  Sure, and the post explicitly mentions that solution multiple times.
tptacek 12y ago
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?
- jsnell 12y ago
  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.
  - tptacek 12y ago
    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.
  - tedunangst 12y ago
    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.
    - jsnell 12y ago
      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.

by jsnell 12y ago

tedunangst 12y ago

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

tptacek 12y ago
In fairness, almost nobody actually does this; they directly index the token itself.
jsnell 12y ago
Sure, and the post explicitly mentions that solution multiple times.

tptacek 12y ago

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?

jsnell 12y ago
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.
- tptacek 12y ago
  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.
- tedunangst 12y ago
  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.
  - jsnell 12y ago
    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.