4 ms·

I'm rather surprised that string hashes aren't randomized in JVM - or at least that's what the article implies. These days, it's a fairly common mitigation for

I'm rather surprised that string hashes aren't randomized in JVM - or at least that's what the article implies. These days, it's a fairly common mitigation for DDoS attacks based on hash collisions. Does Java not do it to preserve backwards compatibility because too much existing code relies on a specific hashing algorithm?

sedatk 2y ago
Java uses a tree instead of a linked list for collided items, so the search performance degrades more gracefully (e.g. O(N) vs O(logN)).
- 77 2y ago
  To be more precise, Java initially uses a linked list for nodes within a bin. If the number of items inside the bin crosses TREEIFY_THRESHOLD (which is 8), then that specific bin is converted into a RB tree. This is detailed in implementation notes comment here: https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc2ae603cff05b55e3/src/java.base/share/classes/java/util/HashMap.java#L146 https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc...
- jillesvangurp 2y ago
  Depends on which Map / Set implementation you use. There are multiple, each with different and interesting properties.
yxhuvud 2y ago
Nothing stops the jvm from caching hashes even if the hashes are unique per process invocation.
- PaulHoule 2y ago
  They aren’t and it’s quite unfortunate that the empty string hashes to 0 so it will have to recompute every time although presumably it is quick to compute the hash of the empty string.
ivan_gammel 2y ago
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 2y 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 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.
ncruces 2y ago
The hashing algorithm is specified in the docs: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] Per Hyrum's law, there's no changing it now. https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#hashCode-- https://docs.oracle.com/javase/8/docs/api/java/lang/String.h...
jillesvangurp 2y ago
No, it would break the semantics of equals and hash which dictate that two objects that are equal should also have the same hash code. So hash codes for objects must be deterministic. Which in turn is an important property for sets, hash tables, etc. It's unlikely to be ever changed because it would break an enormous amount of stuff. For things that need to be secure, there are dedicated libraries, standard APIs, etc. that you probably should be using. For everything else, this is pretty much a non issue that just isn't worth ripping up this contract for. It's not much of an issue in practice and easily mitigated by just picking things that are intended for whatever it is you are trying to do.
- xmcqdpt2 2y ago
  Languages that choose to fix this problem at the hash code level have hash codes that are still deterministic within a given program execution. They are not deterministic between executions, cf https://docs.python.org/3/reference/datamodel.html#object.__hash__ https://docs.python.org/3/reference/datamodel.html#object.__...
TacticalCoder 2y ago
[dead]

sedatk 2y ago

Java uses a tree instead of a linked list for collided items, so the search performance degrades more gracefully (e.g. O(N) vs O(logN)).

77 2y ago
To be more precise, Java initially uses a linked list for nodes within a bin. If the number of items inside the bin crosses TREEIFY_THRESHOLD (which is 8), then that specific bin is converted into a RB tree. This is detailed in implementation notes comment here: https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc2ae603cff05b55e3/src/java.base/share/classes/java/util/HashMap.java#L146 https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc...
jillesvangurp 2y ago
Depends on which Map / Set implementation you use. There are multiple, each with different and interesting properties.

yxhuvud 2y ago

Nothing stops the jvm from caching hashes even if the hashes are unique per process invocation.

PaulHoule 2y ago
They aren’t and it’s quite unfortunate that the empty string hashes to 0 so it will have to recompute every time although presumably it is quick to compute the hash of the empty string.

ivan_gammel 2y ago

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

ncruces 2y ago

The hashing algorithm is specified in the docs: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] Per Hyrum's law, there's no changing it now. https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#hashCode-- https://docs.oracle.com/javase/8/docs/api/java/lang/String.h...

jillesvangurp 2y ago

No, it would break the semantics of equals and hash which dictate that two objects that are equal should also have the same hash code. So hash codes for objects must be deterministic. Which in turn is an important property for sets, hash tables, etc. It's unlikely to be ever changed because it would break an enormous amount of stuff. For things that need to be secure, there are dedicated libraries, standard APIs, etc. that you probably should be using. For everything else, this is pretty much a non issue that just isn't worth ripping up this contract for. It's not much of an issue in practice and easily mitigated by just picking things that are intended for whatever it is you are trying to do.

xmcqdpt2 2y ago
Languages that choose to fix this problem at the hash code level have hash codes that are still deterministic within a given program execution. They are not deterministic between executions, cf https://docs.python.org/3/reference/datamodel.html#object.__hash__ https://docs.python.org/3/reference/datamodel.html#object.__...

TacticalCoder 2y ago

[dead]