DoS vulnerability in Scala 2.12 HashMap #11203
Description
In 2011, a vulnerability was raised against Java application servers about a DoS possibility that exploited Java String's vulnerability to collisions. This vulnerability was so widespread and fundamental that it was fixed not in the application servers, but in the JDK's HashMap implementation.
Scala's HashMap has the same vulnerability. This has been brought to our attention through this issue raised against play-json:
This vulnerability doesn't just affect play-json. It affects anything that uses Scala's default map implementation to store String keyed data where the keys are controlled remotely. So, HTTP headers, HTTP forms, JSON, any library that uses Scala's Map for any of these is vulnerable, so that includes Play, Akka HTTP, and many, many other Scala libraries.
The fix that the JDK did is quite simple, when buckets in the hash table got too big due to poor hashing (or malicious collisions), it reverted to essentially using a TreeMap in the bucket, and if, determined by reflection, the keys are Comparable, it uses the compareTo method to compare them.
Currently, we use ListMap in the case of collisions:
// 32-bit hash collision (rare, but not impossible)
new HashMapCollision1(hash, ListMap.empty.updated(this.key,this.value).updated(key,value))Obviously that comment is wrong, if you're under attack, they won't be rare at all. I think a simple solution here would be to modify HashMapCollision1 such that it has both a ListMap and a TreeMap, anything that implements Comparable can be put in and queried from the TreeMap, and everything else in the ListMap.
I don't think there's much consequence to doing this, the biggest impact will be a potential change in iteration order of colliding elements when you merge two maps - if the keys implement Comparable, the ordering will change from keys from the first map followed by keys in the second map to lexical ordering, and if you're mixing Comparable and non Comparable keys, the ordering gets a bit weirder. But it's still stable. And, who really depends on ordering in hash maps? And it only affects ordering when there are collisions. There's also a slight increase in space used, but again, it's only for collisions, for 99.9999% of the world, it will have no impact.