3 ms·

To fix it at the framework level, assuming the language gives me access to the hash values, I would probably keep a second table mapping hashes to keys. Then I

To fix it at the framework level, assuming the language gives me access to the hash values, I would probably keep a second table mapping hashes to keys. Then I can tell the difference between collisions and dupes. Just kill the request once there are more than a few collisions.

Groxx 15y ago
Dupes aren't the problem, it's duplicate hashes of different data. Dupes should just override the previous value, which matches other hashtable behavior, and works in O(1). Some frameworks may add them to an array, but that's likely to be a real array, or a double-ended queue, or something easier to append to than a plain linked list like hashtables use (because they don't need anything else - to append, they need to check equality on every entry in the list, so they must traverse the whole thing every time, causing the O(n^2) time).
- extension 15y ago
  That's why I would keep a hash->key table. If the hash matches but the key doesn't, it's a collision.
  - Groxx 15y ago
    That's exactly what hashtables do. When they find collisions, they add it to a list of keys that hash to the same value. They do this to be able to return valid data when you request a key - otherwise, you'd find them rarely and seemingly randomly forgetting data or overriding with unrelated values. It's a useful behavior, and it's the very source of the problem. One way to prevent this attack is to use a hashtable that has a limit on the number of collisions per table, or per key, and throw an exception when it's exceeded. The problem is that doing so by default would break valid uses in very surprising ways in favor of protecting against an unlikely and probably unknown (when designed) attack, which you won't do, because that shouldn't be handled by basic datatypes.
- anonymoushn 15y ago
  While it is true that traversing the entire list takes O(n^2) time, it also takes O(n) time.
  - deleted 15y ago
    [deleted]
  - mdwe 15y ago
    He is talking about the total creation time -- putting n distinct elements into the same hash bucket means traversing to the end n times for an overall o(n^2) time

Groxx 15y ago

Dupes aren't the problem, it's duplicate hashes of different data. Dupes should just override the previous value, which matches other hashtable behavior, and works in O(1). Some frameworks may add them to an array, but that's likely to be a real array, or a double-ended queue, or something easier to append to than a plain linked list like hashtables use (because they don't need anything else - to append, they need to check equality on every entry in the list, so they must traverse the whole thing every time, causing the O(n^2) time).

extension 15y ago
That's why I would keep a hash->key table. If the hash matches but the key doesn't, it's a collision.
- Groxx 15y ago
  That's exactly what hashtables do. When they find collisions, they add it to a list of keys that hash to the same value. They do this to be able to return valid data when you request a key - otherwise, you'd find them rarely and seemingly randomly forgetting data or overriding with unrelated values. It's a useful behavior, and it's the very source of the problem. One way to prevent this attack is to use a hashtable that has a limit on the number of collisions per table, or per key, and throw an exception when it's exceeded. The problem is that doing so by default would break valid uses in very surprising ways in favor of protecting against an unlikely and probably unknown (when designed) attack, which you won't do, because that shouldn't be handled by basic datatypes.
anonymoushn 15y ago
While it is true that traversing the entire list takes O(n^2) time, it also takes O(n) time.
- deleted 15y ago
  [deleted]
- mdwe 15y ago
  He is talking about the total creation time -- putting n distinct elements into the same hash bucket means traversing to the end n times for an overall o(n^2) time