6
$\begingroup$

While practically diving into collision resistance, I am trying to first write a non-cryptographic hash (to learn from it) which is limited to arithmetic operations on 32-bit integers only. It produces two 32-bit results similar to MurmurHash2_x86_64 (aka MurmurHash64B), but each have differing initial states and are mixed together more thoroughly (MurmurHash2_x86_64 only mixes at the end). Essentially I aim to produce a fast, well-distributed and collision-resistant 64-bit hash using two 32-bit states.

Trying to learn some things by looking at MurmurHash2_x86_64, I noticed that at first glance, it produces a 64-bit digest. But the author had this to say on the SMHasher wiki:

MurmurHash2_x86_64 computes two 32-bit results in parallel and mixes them at the end, which is fast but means that collision resistance is only as good as a 32-bit hash. I suggest avoiding this variant.

Then I saw this exchange on the subject:

  • Hacker News comment by martincmartin:
    Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.

    • Hacker News comment (reply) by finnw
      Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.

This made me naively test MurmurHash2_x86_64 to find collisions in one 32-bit result, and I found that the second result had no collision. This confused me, because that seemed to be the very definition of collision resistance greater than what a 32-bit hash can provide… and it contradicted what Appleby said about his function.

This makes me ask:

  1. How can two 32-bit results of a hash function correlate, or otherwise increase probability of collisions? Can the outputs from multiple functions correlate at all? And if, how could this weaken the collision resistance of their combination?

  2. What can be done to avoid this situation, and to achieve the collision resistance of a 64-bit hash (or more) using multiple 32-bit results? Is there a way one can combine two correlated hash outputs to maximize the collision resistance?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Collision resistance is a property of a family of hash functions $H_k$ for a key $k$, measured by the probability that a random algorithm can achieve at finding a collision given a random key $k$. Specifically, it is measured by $$\Pr[x \ne y, H_k(x) = H_k(y)]$$ where $k$ is a uniform random key, and $(x, y) = A(k)$ are chosen by a random collision-finding algorithm $A$. There are generic algorithms $A$, such as Pollard's $\rho$, achieving probability near 1 with modest memory cost requiring $2^{n/2}$ evaluations of the function, where $n$ is the number of bits in the hashes, and there are various area-time tradeoffs available. If this probability is negligible for any algorithm $A$ limited to area*time cost below $O(2^{n/2})$, then we call $H_k$ collision-resistant.

Concerning MurmurHash:

  • First, 64 bits is too small for any useful notion of collision resistance, because it generically takes only about four billion evaluations of a hash function to find a collision, and that cost is affordable on your laptop today—as in, before the end of the day.

  • Second, MurmurHash2 and MurmurHash3 aren't even collision-resistant in the formal sense, because there are better-than-generic algorithms for computing collisions under any prescribed key. Actually, it's worse than that: there are pairs of messages that collide under every key in MurmurHash. For example, 390b2e1717dfba58 and b9e9ba6497bd47a6 collide under every key in MurmurHash2. The same applies to MurmurHash3 (and CityHash64), and can be extended into $m$-way multicollisions for any $m$ you want. You can create more of them nearly instantaneously in the privacy of your own living room.

To address the letter of your questions, simply concatenating hash values derived by any iterated hash functions (which is how ~all hash functions are made to work on arbitrary-length inputs, MurmurHash included) fails to achieve collision resistance much better than the individual hash functions alone. Concatenating $H_k$ and $H_{k'}$ with independent keys $k$ and $k'$ doesn't necessarily give worse than 32-bit collision resistance (which would mean a cost of less than a few tens of thousands of evaluations of the function to find a collision), but it doesn't give much better collision resistance either—it certainly won't even reach 64-bit collision resistance.

But since you're asking about 64-bit non-cryptographic hash functions, I can't imagine you actually want collision resistance. Here are a couple of alternatives that you might actually want:

  • You might want a universal hash family, or a $\varepsilon$-almost universal hash family. This means that for any fixed messages $x$ and $y$, and for uniform random $k$, the collision probability is bounded: $$\Pr[H_k(x) = H_k(y)] \leq \varepsilon,$$ a property which we can often prove of specific constructions. Note that this implies nothing about the difficulty of finding collisions if you know the key: it is only a bound on the probability of collisions under uniform random unknown key.

    This prevents an adversary from furnishing you a data set that will, when you load it into a hash table, have many collisions with nonnegligible probability. On the other hand, it doesn't prevent an adaptive adversary from measuring timing of hash table operations to learn about the key $k$ and then furnishing in more collisions. For that you will need a PRF—see below.

    You can get smaller collision probabilities by concatenating independent universal hash functions. Pick keys $k_0$ and $k_1$ independently; if $H_k$ was an $\varepsilon$-universal hash family, then $x \mapsto H_{k_0}(x) \mathbin\| H_{k_1}(x)$ is an $\varepsilon^2$-universal hash family. Proof: A collision $x \ne y$ means $H_{k_0}(x) = H_{k_0}(y)$ and $H_{k_1}(x) = H_{k_1}(y)$, which, since $H_{k_0}$ and $H_{k_1}$ are independent, has probability \begin{align*} \Pr&[H_{k_0}(x) = H_{k_0}(y), H_{k_1}(x) = H_{k_1}] \\ &= \Pr[H_{k_0}(x) = H_{k_0}(y)]\cdot\Pr[H_{k_1}(x) = H_{k_1}(y)] \\ &\leq \varepsilon^2. \end{align*}

    A variation on this theme is relevant in cryptography for message authentication codes: an $\varepsilon$-almost xor-universal hash family, where $$\Pr[H_k(x) \oplus H_k(y) = \delta] \leq \varepsilon$$ for any $x$, $y$, and $\delta$, and random $k$, makes a good one-time secret-key authenticator. For example, Poly1305 and GHASH are $\varepsilon$-almost xor-universal hash families with $\varepsilon \lll \lceil\ell/128\rceil/2^{100}$ where $\ell$ is the message length. AES-GCM uses GHASH in Carger–Wegman's construction to authenticate many messages; NaCl crypto_secretbox_xsalsa20poly1305 uses Poly1305 in a different construction to authenticate many messages.

    There are other variations on the theme, like $\varepsilon$-almost pairwise independent hash families, where $$\Pr[H_k(x) = u, H_k(y) = v] \leq \varepsilon^2$$ for any fixed messages $x$ and $y$, any fixed hash values $u$ and $v$, and uniform random $k$. Zobrist hashes are a popular choice of pairwise independent hash families outside cryptography.

  • You might want a pseudorandom function family, or PRF. This means that no cost-limited adversary given oracle access to a uniformly randomly chosen member $H_k$ of the family can distinguish from a uniform random function with the same domain and codomain: $$|\Pr[A(H_k) = 1] - \Pr[A(U) = 1]|$$ is bounded by a small constant, for any cost-limited random distinguishing algorithm $A$, where $U$ is a uniform random function.

    Note that the adversary isn't given $k$ here—they are only given $H_k$. Obviously, they could try to guess $k$ and use the oracle to confirm their guess, but this succeeds with negligible probability as long as the family, i.e. the number of distinct keys, is reasonably large, say at least $2^{128}$.

    This implies that even if the adversary knows $H_k(x_1)$, $H_k(x_2)$, $\ldots$, $H_k(x_{m-1})$, that doesn't help them to guess $H_k(x_m)$ for a distinct message $x_m$. That means that even timing information about hash table operations—revealing when collisions happened—won't let them guess what other keys will also collide. It also means that a PRF makes a good message authentication code.

    Concatenating independent PRFs, $x \mapsto H_{k_0}(x) \mathbin\| H_{k_1}(x)$, does not confer better PRF-security than any one of them alone. Why? An adversary need only guess one of the independent keys to win the PRF game and distinguish it from a uniform random function, so the generic security attainable by this construction is at most half the generic security attainable by a PRF with a double-size key. That doesn't mean concatenating independent PRFs damages security—just that it never provides higher security than one of them alone.

    We don't know a way to prove that a hash family is a PRF, but typical examples that we conjecture are PRFs are HMAC-SHA256, keyed BLAKE2, and KMAC. For short messages and short, ≤64-bit outputs, SipHash is another popular example, particularly intended to replace MurmurHash where it failed to provide security.

P.S. The comments you quoted on the orange site are, unsurprisingly, meaningless nonsense, compounded by the fact that they are responding to a meandering answer to a confused question on another stackexchange, none of which questions, answers, or responses are grounded by, say, articulation of actual goals in a system.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.