4 ms·

So, the problem here is that you're thinking of "cryptographic properties" as only the "cryptographic hashes" such as those built with the Merkle–Damgård constr

So, the problem here is that you're thinking of "cryptographic properties" as only the "cryptographic hashes" such as those built with the Merkle–Damgård construction (SHA-512/256 being the one you might reasonably pick today) But, it's actually desirable to have some cryptographic properties in a faster one way function for making hash tables. Read about SipHash to see why. Because Java didn't (and as others have discussed, now can't) choose otherwise the hash table structures provided must resist sabotage via collision, which isn't necessary if your attacker can't collide the hash you use.

jillyboel 2y ago
java hashcodes are just 4 bytes, there will always be collisions
- dwattttt 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y ago
ivan_gammel 2y ago
There’s no reason to add extra properties and associated complexity to hash used in collections because of one exotic use case. To be able to execute hash flooding, the server must accumulate arbitrary user inputs in a hash map, which is problematic design anyway. Even if that would make sense, what kind of function could work as 32 bit gash? You mention SipHash as an example: it is poor example anyway, because this function requires a secret key - meaning Java would have to do the key management behind the scene (just for strings? For Number subclasses?) or impose key management on API users. What’s the point? The case is so rare that it’s easier for developers of vulnerable applications to use a wrapper with desired hash properties.
- int_19h 2y ago
  It is not at all an exotic use case, though. It is very common to add external strings as keys to collections. This is precisely why that attack was effective in the first place, and why so many languages these days do hash randomization. E.g. .NET does that.
  - ivan_gammel 2y ago
    Unconstrained user input in a hash map big enough to produce observable effect is not an exotic use case compared to everything else?
    - dwattttt 2y ago
      The alternative is to never key a hash map from user input. Which is a choice to make, but that seems much harder to achieve (over every program?), vs have the implementation be safe in case someone does key off user input.
      - ivan_gammel 2y ago
        The original report from CCC demonstrated an attack on HTTP servers with a lot of request parameters that had hash collisions. That vulnerability was fixed by verifying and limiting user inputs (eg Tomcat 7.0.23 limited number of parameters to 10000 by default among other improvements). You cannot have unconstrained collection for user inputs anyway, otherwise memory based DoS attack becomes possible. So yes, any program that handles user inputs must take care of such scenarios. The best defense perimeter are the parsers of inputs, not just HTTP parameters and headers, but also JSON and XML deserializers, which must be hardened against various types of attacks anyway. Many scenarios where vulnerability may theoretically exist in application code are unpractical for execution of attack, e.g. when inputs are processed after user authentication or rate limit filter.

jillyboel 2y ago

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

dwattttt 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y ago

ivan_gammel 2y ago

There’s no reason to add extra properties and associated complexity to hash used in collections because of one exotic use case. To be able to execute hash flooding, the server must accumulate arbitrary user inputs in a hash map, which is problematic design anyway. Even if that would make sense, what kind of function could work as 32 bit gash? You mention SipHash as an example: it is poor example anyway, because this function requires a secret key - meaning Java would have to do the key management behind the scene (just for strings? For Number subclasses?) or impose key management on API users. What’s the point? The case is so rare that it’s easier for developers of vulnerable applications to use a wrapper with desired hash properties.

int_19h 2y ago
It is not at all an exotic use case, though. It is very common to add external strings as keys to collections. This is precisely why that attack was effective in the first place, and why so many languages these days do hash randomization. E.g. .NET does that.
- ivan_gammel 2y ago
  Unconstrained user input in a hash map big enough to produce observable effect is not an exotic use case compared to everything else?
  - dwattttt 2y ago
    The alternative is to never key a hash map from user input. Which is a choice to make, but that seems much harder to achieve (over every program?), vs have the implementation be safe in case someone does key off user input.
    - ivan_gammel 2y ago
      The original report from CCC demonstrated an attack on HTTP servers with a lot of request parameters that had hash collisions. That vulnerability was fixed by verifying and limiting user inputs (eg Tomcat 7.0.23 limited number of parameters to 10000 by default among other improvements). You cannot have unconstrained collection for user inputs anyway, otherwise memory based DoS attack becomes possible. So yes, any program that handles user inputs must take care of such scenarios. The best defense perimeter are the parsers of inputs, not just HTTP parameters and headers, but also JSON and XML deserializers, which must be hardened against various types of attacks anyway. Many scenarios where vulnerability may theoretically exist in application code are unpractical for execution of attack, e.g. when inputs are processed after user authentication or rate limit filter.