Hacker News Reader

Comment by josefx | Hacker News Reader

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.

View on HN

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....

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.

> 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/200...

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.

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

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.

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.

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.

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.

Reply on news.ycombinator.com