Equality and hash typeclasses

Just to point out that Cats have === for Eq-based equality and .hash for Hash-based hashing.

What kind of attack can be made using object hash collisions? Object hashes are not cryptographic hashes.

That depends on whether the hash function is random per map/set instance, or per JVM (or classloader). Eg, you could have:

implicit lazy val stringHashFunction: Hash[String] = nextRandomHashFunction()

Then there would be no problems merging maps/sets. You would have to be careful with serialization, the serialization of keys/values would need to not be dependent on the hash function (with the current Map implementation it’s not), and you would need to ensure the deserialized hash function replaced itself with the current random hash function.

What kind of attack can be made using object hash collisions? Object hashes are not cryptographic hashes.

Here’s an actual reported vulnerability caused by using Scala’s Map with String keys: Denial of service when parsing JSON object with keys that have the same hash code · Issue #186 · playframework/play-json · GitHub

trait Hash[Z] {
  def empty: Z

  def bytes(z: Z, bytes: ImmArray[Byte]): Z

  def byte(z: Z, x: Byte): Z = ...
  def short(z: Z, x: Short): Z = ...
  def int(z: Z, x: Int): Z = ...
  def long(z: Z, x: Long): Z = ...
}

trait Hashable[T] extends Eq[T] {
  def hash[Z](implicit Z: Hash[Z]): Z
}

implicit def mapHashable[K: Hashable, V: Hashable]: Hashable[Map[K, V]] = ...

def mkMap[K: Hashable, V]((K, V)*): Map[K, V] = ...
// it can use some *fixed* hash function inside

def mkMap[Z : Hash : Eq, K : Hashable, V]((Z, K, V)*): XMap[Z, K, V] = ...
// uses a specific implementation of a hash function

(m : Map[Int, Int]).hash[SipHash]
// or if you pass it explicitly, you can have your *random state* somewhere
// it *doesn't* have to be inside the map itself

This looks strange since internals of Hashable[T] do not depend on T. This class looks like merging two independent things: equality for T and hashing for Z.

Probably a typo or copy-paste error (or unfinished editing)