4 ms·

Java hashCode contract is to optimize calculation of hash for performance not for collision search resistance. Its sole purpose is to use it in collections. It

Java hashCode contract is to optimize calculation of hash for performance not for collision search resistance. Its sole purpose is to use it in collections. It must not be used in situations where you need cryptographic properties.

tialaramex 1y ago
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 1y ago
  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.
- ivan_gammel 1y 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 1y 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 1y 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 1y 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 1y 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.
GolDDranks 1y ago
The thing is, even it being used just in collections can lead to DOS, if the attacker can control the string contents, and selectively choose strings that your hash table stops being a hash table and turns into a linked list.
- deleted 1y ago
  [deleted]
- ivan_gammel 1y ago
  That’s clear and that is not a reason to have it in general purpose collections or String::hashCode. If your app is vulnerable to this sort of attack, just use a wrapper for keys and specialized collection (you may want to limit the maximum size of it too).
  - int_19h 1y ago
    This sounds a great deal like all the C++ devs who say "well just don't write code with buffer overflow bugs then". The reason why this kind of thing should be the default is because it's unreasonable to expect this level of understanding from your average coder, yet most software is written by the later. That's why PL and framework design has been moving towards safety-by-default for quite some time now - because nothing else works, as proven by experience.
    - ivan_gammel 1y ago
      You are misunderstanding and exaggerating this particular risk and assuming there’s only one way to handle it. First of all, it concerns unchecked user inputs: it is not enough just to fix the hash code, the entire HashMap is not great for storing it regardless of hash algorithms. Hash may be ok, but HashMap has no size constraints, so there may exist a vulnerability related to DoS attack exhausting server memory. Developers must always validate inputs as early as possible. Even the dumb ones. Second, this risk was reliably mitigated in Java as soon as it was discovered. Just because hash collisions may exist, it doesn’t mean they are exploitable. CVE for JDK was not fixed, because it has been taken care of elsewhere, in Tomcat etc, where meaningful validation could take place. Context matters.
andrewaylett 1y ago
Even in collections, an unstable hash is desirable -- to avoid denial of service attacks caused by attacker-controlled hash collisions. For example, Python back in 2012: https://nvd.nist.gov/vuln/detail/cve-2012-1150 https://nvd.nist.gov/vuln/detail/cve-2012-1150.
- pfdietz 1y ago
  Or the hash table implementation should be resistant to collisions, falling back to another data structure in that case (as described below, using trees instead of lists in buckets with sufficiently many occupants.)
- ivan_gammel 1y ago
  There exists CVE-2012-5373 for Java and it is not fixed because it is not a risk worth taking care of.

tialaramex 1y ago

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 1y ago
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.
ivan_gammel 1y 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 1y 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 1y 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 1y 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 1y 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.

GolDDranks 1y ago

The thing is, even it being used just in collections can lead to DOS, if the attacker can control the string contents, and selectively choose strings that your hash table stops being a hash table and turns into a linked list.

deleted 1y ago
[deleted]
ivan_gammel 1y ago
That’s clear and that is not a reason to have it in general purpose collections or String::hashCode. If your app is vulnerable to this sort of attack, just use a wrapper for keys and specialized collection (you may want to limit the maximum size of it too).
- int_19h 1y ago
  This sounds a great deal like all the C++ devs who say "well just don't write code with buffer overflow bugs then". The reason why this kind of thing should be the default is because it's unreasonable to expect this level of understanding from your average coder, yet most software is written by the later. That's why PL and framework design has been moving towards safety-by-default for quite some time now - because nothing else works, as proven by experience.
  - ivan_gammel 1y ago
    You are misunderstanding and exaggerating this particular risk and assuming there’s only one way to handle it. First of all, it concerns unchecked user inputs: it is not enough just to fix the hash code, the entire HashMap is not great for storing it regardless of hash algorithms. Hash may be ok, but HashMap has no size constraints, so there may exist a vulnerability related to DoS attack exhausting server memory. Developers must always validate inputs as early as possible. Even the dumb ones. Second, this risk was reliably mitigated in Java as soon as it was discovered. Just because hash collisions may exist, it doesn’t mean they are exploitable. CVE for JDK was not fixed, because it has been taken care of elsewhere, in Tomcat etc, where meaningful validation could take place. Context matters.

andrewaylett 1y ago

Even in collections, an unstable hash is desirable -- to avoid denial of service attacks caused by attacker-controlled hash collisions. For example, Python back in 2012: https://nvd.nist.gov/vuln/detail/cve-2012-1150 https://nvd.nist.gov/vuln/detail/cve-2012-1150.

pfdietz 1y ago
Or the hash table implementation should be resistant to collisions, falling back to another data structure in that case (as described below, using trees instead of lists in buckets with sufficiently many occupants.)
ivan_gammel 1y ago
There exists CVE-2012-5373 for Java and it is not fixed because it is not a risk worth taking care of.