5 ms·

The worst case was once used to attack Java based servers, using colliding post parameters I think. Since then the Java HashMap sorts colliding entries if the e

by josefx 10y ago

The worst case was once used to attack Java based servers, using colliding post parameters I think. Since then the Java HashMap sorts colliding entries if the entries implement Comparable.

masklinn 10y ago
> The worst case was once used to attack Java based servers The worst case was revealed able to efficiently DOS pretty much any hashtable-based stack back in 2011[0] (practical attacks on real-world implementations, not theoretical work), following which most stacks added hash randomisation during 2012. [0] https://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf https://events.ccc.de/congress/2011/Fahrplan/attachments/200...
bhaak 10y ago
Needs a (2012) in the title. The hash collisions you mentioned probably got fixed after or because of these CCC congress talks: https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.... https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.html https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.... The article talks about peculiar myths that I haven't heard before. And the first one "the worst case is terrible" is not even a myth if you're hashing function isn't well designed and you have a malicious data provider.
danbruc 10y ago
But that is of course true for all algorithms without uniform performance, another famous example being sorting with quicksort which on average takes O(n x log(n)) time but can become O(n²) in the worst case. Or zip bombs making you decompress a few kilobytes of data into gigabytes. If a user can control a relevant fraction or important piece of the data you are processing, then you always have to be careful not to expose yourselves to algorithmic complexity attacks.
jkot 10y ago
Also String.hashCode is broken, it generates too many collisions. It can not be fixed for historic reasons.
- arethuza 10y ago
  Wasn't an early version really broken - where it only looked at the first N characters of a string when hashing it? Where N was actually pretty low.
  - jkot 10y ago
    Perhaps, but it made sense with 16MB RAM and 486 CPU. Current implementation uses 31 multiplier which is useless over 1M entries. This problem is also in Arrays.hash*() and many other places.
espadrine 10y ago
The answer to that has always been universal hash functions. You have a family of hash functions, one of which is picked randomly. In the family, each hash function is such that Pr(collision) ≤ Pr(randomly picking that hash function). That way, for a sufficiently large family, it is virtually impossible to hit its worst case.
- rurban 10y ago
  No, it's not. With enough data leaking, like ordering and timings attacks are computable. Only a proper collision resolution method can prevent from DoS attacks. The blog post doesn't even know about modern hash tables, not chasing ptrs in a linked list, which is not recommended where ptrs chasing is 50x slower than adjacent entries (cpu's of the last 15 years). But for newbies it's at least a beginning.

by josefx 10y ago

The worst case was once used to attack Java based servers, using colliding post parameters I think. Since then the Java HashMap sorts colliding entries if the entries implement Comparable.

masklinn 10y ago

> The worst case was once used to attack Java based servers The worst case was revealed able to efficiently DOS pretty much any hashtable-based stack back in 2011[0] (practical attacks on real-world implementations, not theoretical work), following which most stacks added hash randomisation during 2012. [0] https://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf https://events.ccc.de/congress/2011/Fahrplan/attachments/200...

bhaak 10y ago

Needs a (2012) in the title. The hash collisions you mentioned probably got fixed after or because of these CCC congress talks: https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.... https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.html https://events.ccc.de/congress/2012/Fahrplan/events/5152.en.... The article talks about peculiar myths that I haven't heard before. And the first one "the worst case is terrible" is not even a myth if you're hashing function isn't well designed and you have a malicious data provider.

danbruc 10y ago

But that is of course true for all algorithms without uniform performance, another famous example being sorting with quicksort which on average takes O(n x log(n)) time but can become O(n²) in the worst case. Or zip bombs making you decompress a few kilobytes of data into gigabytes. If a user can control a relevant fraction or important piece of the data you are processing, then you always have to be careful not to expose yourselves to algorithmic complexity attacks.

jkot 10y ago

Also String.hashCode is broken, it generates too many collisions. It can not be fixed for historic reasons.

arethuza 10y ago
Wasn't an early version really broken - where it only looked at the first N characters of a string when hashing it? Where N was actually pretty low.
- jkot 10y ago
  Perhaps, but it made sense with 16MB RAM and 486 CPU. Current implementation uses 31 multiplier which is useless over 1M entries. This problem is also in Arrays.hash*() and many other places.

espadrine 10y ago

The answer to that has always been universal hash functions. You have a family of hash functions, one of which is picked randomly. In the family, each hash function is such that Pr(collision) ≤ Pr(randomly picking that hash function). That way, for a sufficiently large family, it is virtually impossible to hit its worst case.

rurban 10y ago
No, it's not. With enough data leaking, like ordering and timings attacks are computable. Only a proper collision resolution method can prevent from DoS attacks. The blog post doesn't even know about modern hash tables, not chasing ptrs in a linked list, which is not recommended where ptrs chasing is 50x slower than adjacent entries (cpu's of the last 15 years). But for newbies it's at least a beginning.