5
$\begingroup$

Bad hash functions are not so perfect as in the "general collision probability" hypothesis... And a general concept of "collision resistence" not need the constraint of independence between the hash function and the sample set.

Let $H$ be a hash function with digest of $k$ bits, and $S$ a input sample set with size $s=|S|$.
$H$ is collision resistant if it is "hard to find" two inputs that hash to the same output,
  $\exists x\ne y\in S|H(x)=H(y)$

But "hard to find" is not a good definition: to compare the performance of two hash functions $H_1$ and $H_2$ we need a precise metric... Wikipedia use $Pr[H]$, the probability concept to define this metric... But, in real-life tests or benchmarking, we have only the number of collisions $c$, and a big standard deviation to compare $c$ values when change $S$ or $H$.

Puting the question in other words:
  there are a "standard way" to obtain the real-life $Pr[H]$ of bad hash functions?


Context. Let me be a programmer that buy low quality proprietary software that implement exotic hash functions: the hash function $H$ for me is a black box, and I need to test it.

enter image description here

So, if the seller of the function says it is resistant, I need to check it by experiments and some statistical analysis of the experimental results.


Back to the question... If this standard exists, I am supposing that is a kind of probability definition, so, will be someting like (is it? need only to check the number $c$ of collisions) $$Pr[H](S)=\frac{c}{|S|}=\frac{c}{s}$$

Bad hash functions (example) have characteristic values of $Pr$ that not depends only on $|S|$... We can use $c$ to compare the efficiency of the bad hash with other hashes. I am imagining that I can use $c$ or an averaged $\overline{c}$ based on many $c_i$ tests as a metric of collision rates.


NOTES

Let $c_1$ the number of collisions in $H_1(S)$ and $c_2$ the number of collisions in $H_2(S)$, them we can compare the two hash functions.

To avoid bias we can do an average about many sample sets $S_1$, $S_2$, etc. So there are averaged $\overline{c}_1$ and $\overline{c}_2$ as good estimators.

Theoretically we can also estimate the minimum $\overline{c}$ of a hash function with digests of $k$ bits by $${Pr}_{min}[H](S) ~=~ 1 - \frac{2^k!}{(2^k)^s (2^k - s)!} ~\approx~ 1 - exp({-s^2/2^{k + 1}})$$

Conclusion, a good score to compare hash functions is $$q ~=~ Pr[H](S) - Pr_{min}[H](S) ~\approx~ \frac{\overline{c}}{s} -1+exp({-s^2/2^{k + 1}})$$

When $q=0$ we have "perfect hash function", that have an expected behaviour about collisions... Imagining that hashes like SHA1 are always perfect because is impossible to compute $\overline{c}$, but truncated SHA1 or "bad hashes" can be tested about big $S$ samples.
PS: negative $q$ is possible when $H$ and $S$ are not independent.

My interest is the behaviour of these truncated or bad hashes, and to compare them.

$\endgroup$
6
  • 1
    $\begingroup$ I'm not certain that the definition of $q$ you give in your notes corresponds to what we mean by the quality of a hash function. If we consider a CRC, I believe that it would have $q=0$ (because, given a set of random strings, it's equidistributed), however it is trivial to find collisions/preimages. $\endgroup$
    – poncho
    Commented Apr 21, 2018 at 21:25
  • $\begingroup$ @poncho, perhaps that is the point (!), I am imagining that in a big database test comparing truncated SHA1 with old checksums (like XOR8 or CRC) we will find non-zero $q$ values and something like $q_{sha1}<q_{xor8}$. $\endgroup$ Commented Apr 21, 2018 at 21:37
  • $\begingroup$ Your bounty is still out and I don't see an accept. Meanwhile there is a very extensive answer from Squeamish. Could you indicate what is missing from it? $\endgroup$
    – Maarten Bodewes
    Commented Apr 29, 2018 at 22:00
  • 1
    $\begingroup$ @MaartenBodewes Well,there's no metric for a start... $\endgroup$
    – Paul Uszak
    Commented Apr 30, 2018 at 2:28
  • $\begingroup$ If you're buying proprietary crypto, I have a bridge to sell you. Forget testing it as a black box—don't give your money to snake oil salesmen; use a real hash function instead. $\endgroup$ Commented May 2, 2018 at 13:27

1 Answer 1

7
+25
$\begingroup$

There are a few standard quantities related to families of hash functions $H_k\colon \{0,1\}^m \to \{0,1\}^h$ for a uniform random key $k$. You might call them metrics. They came to prominence in Carter and Wegman's research program on universal hash families (paywall-free), though their first use in cryptography for one-time authenticators, by Gilbert, MacWilliams, and Sloane (paywall-free), predated the Carter–Wegman program by several years.

  • An upper bound on $\Pr[H_k(x) = u]$ for any $x \in \{0,1\}^m$ and $u \in \{0,1\}^h$. If it is $1/2^h$, then we say the family is equidistributed.

  • An upper bound on $\Pr[H_k(x) = H_k(y)]$ for any distinct $x, y \in \{0,1\}^m$. For example, if it's at most $1/2^h$, we say the family is universal; if it's at most $\varepsilon = O(1/2^h)$, we say it's $\varepsilon$-almost universal. The quantity $\Pr[H_k(x) = H_k(y)]$ is sometimes called the collision probability.

  • An upper bound on $\Pr[H_k(x) \oplus H_k(y) = u]$ for any distinct $x, y, \in \{0,1\}^m$ and any $u \in \{0,1\}^h$. If it's at most $\varepsilon = O(1/2^h)$, we say it's $\varepsilon$-almost xor-universal.

  • An upper bound on $\Pr[H_k(x) = u, H_k(y) = v]$ for any distinct $x, y \in \{0,1\}^m$ and any $u, v \in \{0,1\}^h$. If it's at most $\varepsilon = O(1/2^{2h})$, we say it's $\varepsilon$-almost strongly universal or $\varepsilon$-almost pairwise independent.

  • An upper bound on $\Pr[H_k(x_1) = u_1, \dots, H_k(x_n) = u_n]$ for any distinct $x_i \in \{0,1\}^m$ and any $u_i \in \{0,1\}^h$. If it's at most $\varepsilon = O(1/2^{nh})$, we say it's $\varepsilon$-almost $n$-independent or $n$-universal.

There are standard provable examples of functions attaining optimal or near-optimal values of the above bounds. In cryptography, these bounds are relevant to one-time authenticators such as Poly1305 and GHASH, which are based on equidistributed $\varepsilon$-almost xor-universal hash families for $\varepsilon \approx \lceil m/128\rceil/2^{128}$, as well as to other applications such as hash tables with non-adaptive adversaries. The quantity $\Pr[H_k(m') = a' \mathrel| H_k(m) = a]$ for $m' \ne m$ is sometimes called the forgery probability.

An $n$-independent hash family has the property that the probability of a collision $H_k(x) = H_k(y)$ for distinct $x, y \in S$ in a subset $S \subseteq \{0,1\}^m$ of $n$ elements is $$1 - \frac{2^h!}{(2^h)^n (2^h - n)!} \approx 1 - e^{-n^2/2^{h + 1}}.$$ However, the key must be enormous to guarantee this. Further, none of these bounds guarantees anything about the difficulty of deliberately computing a collision knowing the key.

What you are probably getting at is not collision probabilities for unknown keys, but rather the collision resistance of a hash family:

  • An upper bound on $\Pr[x \ne y, H_k(x) = H_k(y)]$ where $(x, y) = A(k)$ and $A$ is any random algorithm. If this negligible when the expected cost of $A$ is below $\sqrt{2^h} = 2^{h/2}$, we say the family is collision-resistant.

    In particular, if $B_t(f)$ is a random algorithm that applies the birthday paradox to $t$ uniform random inputs to $f\colon \{0,1\}^m \to \{0,1\}^h$ as an oracle and returns a collision if there is one (for example, using van Oorschot and Wiener's parallel collision search machine), then for any equidistributed $f$, $$\Pr[x \ne y, f(x) = f(y)] = 1 - \frac{2^h!}{(2^h)^t (2^h - t)!} \approx 1 - e^{-t^2/2^{h + 1}},$$ where $(x, y) = B_t(f)$. When $t^2 \lll 2^h$, so that $t \lll \sqrt{2^h} = 2^{h/2}$, this is negligible in $h$. The best generic attack on $H_k$ with cost $t$ is $A(k) = B_t(H_k)$; if there is no known attack better than this we say that $H_k$ is collision-resistant.

We don't know how to prove this for all random algorithms $A$, however, so this property can only be conjectured of hash families for which we haven't figured out a cheaper collision search algorithm. For example, we are quite confident that Poly1305 or GHASH is not collision-resistant; it is trivial to compute two-block collisions under any key with one field multiplication and one field addition. We conjecture that keyed BLAKE2 is collision-resistant because nobody has figured out how to make it collide.

It is of little use to empirically study collision resistance by sampling outputs of a generic hash function. If you try to use the generic birthday algorithm on Poly1305 or GHASH, it won't do much better than it will on keyed BLAKE2. But it doesn't take a genius of a cryptanalyst to immediately recognize there is a trivial algorithm to find Poly1305 and GHASH collisions, given the key, much faster than the generic birthday algorithm. The best we can do is to empirically study it by sampling algorithms for finding collisions—asking a lot of smart cryptanalysts to try to think of them. So far, empirically, nobody has thought of a way to find collisions in keyed BLAKE2.

Since sampling outputs is not useful for studying collision resistance, when studying simplified versions of hash families, we don't normally study a progression of truncated output sizes. Rather, we structure the hash family to iterate some internal scrambling function for a variable number of rounds, and study a progression of numbers of rounds. For example, the best known collision attacks on reduced-round versions of BLAKE apply only to 5 rounds, which is why the BLAKE2 designers felt comfortable recommending only 10 rounds.

Loosely, we sometimes also pick a fixed hash function such as SHA3-256, and say that it is collision-resistant if nobody has found a way to compute a collision under that fixed hash function. Of course, if $h \leq m$, we are guaranteed that a collision exists, so there must exist a trivial random algorithm of negligible cost to compute it: namely an algorithm that simply returns the collision without doing any computation.

So there's no nice way to formalize this, but in practice, it seems to be hard. Twenty years ago, it was conjectured that SHA-1 was collision-resistant in this loose sense, until someone figured out a way to compute SHA-1 collisions at lower cost than the generic attack in 2004, and then someone published an actual collision last year. Today, it is still conjectured that SHA-256 is still collision-resistant in this loose sense.

$\endgroup$
5
  • $\begingroup$ Thanks @SqueamishOssifrage, I need more one weekend to study your answer, that sounds right and complete (more 1 reference?)... But, as the bounty-period is ending I need to check now, sorry if I not understanding yet... My preliminar considerations: 1) you answer the question "There are a metric for collision?" but tne question is also about "to compare", can you add some comment about comparisions? 2) when we talk about (normalized) differences like expected_value_in_perfect_hash - measured_value_in_experiments, what the metric with less standard deviation? seems equidistribution... $\endgroup$ Commented Apr 30, 2018 at 0:55
  • $\begingroup$ About "experimental vs theoretical"... In the context of these metrics, can I use some form of induction, checking for instance for $h \in \{4,6,8,10,12,14,16\}$, a tendency to characterize $H$? That is, a linear regression of $Pr[H]$ vs $h$ in a set of 7 experiments changing $h$ (by e.g. truncating digests) , is better (cost/benefit) than average of 7 experiments with constant $h$? $\endgroup$ Commented Apr 30, 2018 at 1:15
  • $\begingroup$ @PeterKrauss For the universal hash properties, we usually prove that the hash families have the desired probability bounds: for example, GHASH on messages of about $2^{24}$ octets long is proven to be equidistributed and have forgery probability ($\Pr[H(m') = a' \mathrel| H(m) = a]$ for any $m \ne m'$, $a$, and $a'$) below $2^{-108}$. The story for collision resistance is different: since we can't prove it, instead of experimentally exploring the outputs, we experimentally explore collision-finding algorithms by asking a lot of smart cryptanalysts to break it. $\endgroup$ Commented Apr 30, 2018 at 16:54
  • $\begingroup$ @PeterKrauss For collision resistance, if you conduct an experiment on the outputs of a generic hash family, i.e. an experiment that uses the hash function $H_k(m)$ as a subroutine without exploiting any details of how $H$ works internally, you will most likely learn nothing except in pathological cases. For instance, if you try a generic birthday search ($B_t$, in the answer) on GHASH or Poly1305, you almost certainly won't find collisions. But there is a very easy algorithm for finding collisions in GHASH and Poly1305 if you have the key. $\endgroup$ Commented Apr 30, 2018 at 17:02
  • $\begingroup$ Thanks Squeamish, now your explanations are perfect (!) and filled of good links for my homework. Sorry to lost bounty-period, the automatic-half was applyed before my vote. I edited the question to emphasize the black box situation. $\endgroup$ Commented May 2, 2018 at 12:33

Your Answer

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

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