4 ms·

java hashcodes are just 4 bytes, there will always be collisions

dwattttt 1y ago
The point is that since the hash is known and predictable, an attacker who can choose what keys get added to the map can choose them so every key collides, resulting in a DoS. I assume Java has to add some other layer to avoid this, rather than using a collision resistant hash scheme.
- chii 1y ago
  > added to the map can choose them so every key collides, resulting in a DoS the application creator needed to have anticipated this threat model, and they can prepare for it (for example, salt the keys). But to put onto every user a hash that is collision resistent, but costs performance, is unjustified because not every user needs it.
- homebrewer 1y ago
  There are specialized collections in external libraries for these kinds of situations to be used when you need them (and are ready to pay for them in terms of performance).
  - dwattttt 1y ago
    I don't imagine it was ivan_gammel's intention, but his mention of the original CCC/tomcat issue I think makes the point quite clear: have you ever had a hashmap of HTTP header to values? I hope it used one of those external libraries, because otherwise that's now a vector for DoS'ing any app that has one. User influenced/controlled input happens way more than we expect, I think the more sensible approach would be for the map to be safe by default, and to reach for a high performance external map for those times when that particular data structure is the bottleneck.
    - ivan_gammel 1y ago
      >I think makes the point quite clear: have you ever had a hashmap of HTTP header to values? Number of headers is limited by default to a relatively small value (10k), which in the worst case of hash collisions results in relatively fast lookup time due to tree-like implementation of HashMap.
      - tialaramex 1y ago
        > due to tree-like implementation of HashMap. Exactly, this data structure has to provide counter-measures to cope with the fallout from this other poor choice. The fast data structures for this work don't need a tree here, they're open addressed instead, but this would mean they can't cope if your attacker can arbitrarily collide input, so, too bad.
        ivan_gammel 1y ago
        This data structure has tree-like fallback for hash collisions in general, which do happen regardless of hash algorithm by definition of what is hash. It is not a coping mechanism for a poor choice, it’s elegant design allowing better performance for Comparable keys. By coincidence it mitigates the DoS attack too.
        tialaramex 1y ago
        All the closed addressing strategies mean more allocator burden. In this case, each of these trees needs to grow separately. But with open addressing we can avoid that. Suppose we have 10'000 key->value pairs to store. A Swiss Table (a popular open addressed hash table design) will need space for 16384 contiguous pairs plus metadata†. So it'll do that allocation once, but with the closed addressing and trees you're paying to grow trees during insertion, you can't know which trees will grow and which are unused. You're correct that the Swiss Table will see collisions, but an attacker can't choose them, so they're rare. Each collision costs us a search step, but because the Java design incurs a pointer chase (to find the tree) for every lookup that's actually the same price [one memory fetch] as a single collision for the Swiss Table, yet most of the time the Swiss Table sees less than 1.0 collisions per lookup. † It's ensuring no more than 87.5% of the storage is used and then rounding up to a power of two because that means less work for each look-up step. 11429 would be enough space, but 16384 is the next largest power of two.

The point is that since the hash is known and predictable, an attacker who can choose what keys get added to the map can choose them so every key collides, resulting in a DoS. I assume Java has to add some other layer to avoid this, rather than using a collision resistant hash scheme.

chii 1y ago
> added to the map can choose them so every key collides, resulting in a DoS the application creator needed to have anticipated this threat model, and they can prepare for it (for example, salt the keys). But to put onto every user a hash that is collision resistent, but costs performance, is unjustified because not every user needs it.
homebrewer 1y ago
There are specialized collections in external libraries for these kinds of situations to be used when you need them (and are ready to pay for them in terms of performance).
- dwattttt 1y ago
  I don't imagine it was ivan_gammel's intention, but his mention of the original CCC/tomcat issue I think makes the point quite clear: have you ever had a hashmap of HTTP header to values? I hope it used one of those external libraries, because otherwise that's now a vector for DoS'ing any app that has one. User influenced/controlled input happens way more than we expect, I think the more sensible approach would be for the map to be safe by default, and to reach for a high performance external map for those times when that particular data structure is the bottleneck.
  - ivan_gammel 1y ago
    >I think makes the point quite clear: have you ever had a hashmap of HTTP header to values? Number of headers is limited by default to a relatively small value (10k), which in the worst case of hash collisions results in relatively fast lookup time due to tree-like implementation of HashMap.
    - tialaramex 1y ago
      > due to tree-like implementation of HashMap. Exactly, this data structure has to provide counter-measures to cope with the fallout from this other poor choice. The fast data structures for this work don't need a tree here, they're open addressed instead, but this would mean they can't cope if your attacker can arbitrarily collide input, so, too bad.
      - ivan_gammel 1y ago
        This data structure has tree-like fallback for hash collisions in general, which do happen regardless of hash algorithm by definition of what is hash. It is not a coping mechanism for a poor choice, it’s elegant design allowing better performance for Comparable keys. By coincidence it mitigates the DoS attack too.
        tialaramex 1y ago
        All the closed addressing strategies mean more allocator burden. In this case, each of these trees needs to grow separately. But with open addressing we can avoid that. Suppose we have 10'000 key->value pairs to store. A Swiss Table (a popular open addressed hash table design) will need space for 16384 contiguous pairs plus metadata†. So it'll do that allocation once, but with the closed addressing and trees you're paying to grow trees during insertion, you can't know which trees will grow and which are unused. You're correct that the Swiss Table will see collisions, but an attacker can't choose them, so they're rare. Each collision costs us a search step, but because the Java design incurs a pointer chase (to find the tree) for every lookup that's actually the same price [one memory fetch] as a single collision for the Swiss Table, yet most of the time the Swiss Table sees less than 1.0 collisions per lookup. † It's ensuring no more than 87.5% of the storage is used and then rounding up to a power of two because that means less work for each look-up step. 11429 would be enough space, but 16384 is the next largest power of two.