0
$\begingroup$

Let $H$ be a collision resistant hash function and $P_c[H](S)$ the collision probability about a sample set $S$ of input elements (eg. random numbers). It increases with double hash? That is,
$P_c[H\circ H](S) \ge P_c[H](S)$   ?

Well... we need a precise $P_c$ definition. Perhaps the problem here is also the choice of a good probability definition (see notes below).


NOTES

Answer's application: the answer is important in the context of checksums used for digital preservation integrity of public files.

Imagine the checksum (the hash digest $H(x)$) of a PDF article of PubMed Central or arxiv.org... And that we need to ensure the integrity, with no "PDF atack" or minimizing it, in nowadays and in a far future, ~20 years.

If the answer is "YES there are a little increase", the recommendation will be "please don't use double-hashing as standard for checksum for PMC or arxivOrg".

General probaility

The general collision probability is defined as

Given $k$ randomly generated $x$ values, where each $x$ is a non-negative integer less than $N$, what is the probability that at least two of them are equal?

and depends only of the $|S|$, so $P_c[H\circ H] = P_c[H]$...
There are a hypothesis of "perfect hash function", but I want to metric the imperfections.

If there are no error on my interpretations, I need other probability definition.

Counting the collisions

Suppose a kind of "collision tax", $\frac{N_c}{|S|}$, based on the number of collisions $N_c$ occured with a specific sample.
So, for many different sample sets $S_i$ with same number of elements, $k=|S_1|=|S_2|=... =|S_i|$. Suppose a set $K$ of all sets $S_i$ and $P_c[H](K)$ as an average of this collision rate.

This kind of probability seems better to express the problem.

... Bloom filter efficiency

Another metric, instead a probability. Perhaps using Bloom filter theory as reference. A kind of efficiency-benchmark of two Bloom filters, one with $H$ other with $H\circ H$.

$\endgroup$
4
$\begingroup$

I'm not sure what the question here is, but obviously applying the hash function twice can never decrease the number/probability of collision as all collisions in the first invocation are maintained.

However if H is collision free( a permutation as opposed to a random function) doubling will not cause any more collision it will remain collision free. So we see the number of collision does not strictly increase.

For a PRF, the number of collision does clearly increase, this is one reason why when we iteratively hash passwords in for key derivation we mix in the input again every round and not simply hash calculate $H^n(salt || pass)$

If you look at the structure of a function you will see several cycles and threads(trees) leading into these cycles: enter image description here

The cycles do not generate more collisions when doubled. Each thread meeting a cycle contributes one collision, If All the threads are of length 1 no more collisions are added when applying twice in any other case the number of collisions increases.

$\endgroup$
  • $\begingroup$ Hi Meir. Your oriented graph is a perfect visual repesentation! And my interpretation is YES, $P_c[H\circ H](S) > P_c[H](S)$. Is it? Of course, we need a simpler graph (same nodes but only one leaving edge). There are an algebraic formal expression (the inequality) for general graphs of double hashing? $\endgroup$ – Peter Krauss Apr 21 '18 at 13:28
  • $\begingroup$ ... In the double-hashing graph the "increase of collisions" can be detected by the number of nodes that are receiving 2 or more edges. $\endgroup$ – Peter Krauss Apr 21 '18 at 13:35
  • $\begingroup$ The graph is accurate, only one outgoing edge. And if you replace the greater with greater or equal you would be correct. $\endgroup$ – Meir Maor Apr 21 '18 at 13:50
  • $\begingroup$ Thanks Meir to the answer and the effort to understand the question (I edited adding notes about applications). You show good clues. I will not accept yet: the question is open to an algebraic proof... Or, failing that, a better illustration, specialized in only-double-hash (one-edge graphs). Ah, I will correct the question with $\ge$. $\endgroup$ – Peter Krauss Apr 21 '18 at 14:00
  • $\begingroup$ The proof ia trivial, for.any collision f(x)=f(y) it follows f(f(x))=f(f(y)). For any means of counting collisions over any group. Doubling the function can only increase collisions. $\endgroup$ – Meir Maor Apr 21 '18 at 14:06
0
$\begingroup$

Complete answer for dummies

Using the @MeirMaor answer as starting point, there are good clues and illustration.

Using also the concepts of "bad hash function" (instead "good" ones like SHA3) and the "empyrical metric for collision rates" concept of this other question/answer.

Modeling

Suppose $H$ as a black box — and the two connected boxes, $H \circ H$, for our purposes will also be a black box.

enter image description here

So, we need to check it by experiments and some statistical analysis of the experimental results.

Suppose also some "metric" as defined here... There are a sample $S$ where some number of collisions $c>0$ arrives,
  $Pr_c[H]=\overline{c}/|S|$
and we do same experiment many times with sample sets with same size $|S|$, so we have an averaged $\overline{c}$.

Let $U=\{u=H(x)|\forall x\}$ and $|S|$ is not so large, that is $|S|<<|U|$.

In that context the main differences between $H$ and $H \circ H$ and valid hypothesis are:

  1. The doubling will not reduce the number of collisions. $Pr_c[H] \le Pr_c[H \circ H]$.

  2. There are no warranty that doubling cause will not cause new collisions, so we can suppose that it will occur.

Representing the first hashing as a set of points (no matter if there was or not a collision, as hypothesis-1), and the second hashing a transition from a point to other point in the same space.

enter image description here

(the illustration is exaggerating, the very most frequent is node-arc-node)

Answering

As showed by the illustration, a good metric is the simple counting of collisions $\overline{r}$ in the second hashing (red dots),
  $Pr_r[H]=\overline{r}/|S|$
and ignoring any collision of the first:

  • if $Pr_c[H]=0$ we can't assert anything, no red dots in the experiment.
    "Good hashes" like SHA3 or SHA256 are in this group.

  • if $Pr_c[H]>0$, a "bad hash", we can assert that $Pr_r[H]>0$
    as showed by the illustration, we expect red dots.

We conclude that the answer to the question is afirmative when $|S|<<|U|$ and $H$ is a "bad hash". That is, doubling "bad hashes" will always increase the collision rate probability.


PS: as @SqueamishOssifrage remembered here, to avoid the "nothing to say" we can study simplified versions of hash families,

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

The reduced-round versions of "good hashes", like BLAKE or SHA3, can be imagined as "bad hash" in the above method.

As reduced-round versions have the same behaviour, accepting the induction, the answer to the question will be afirmative also for "good hashes" (!).


When $|S|$ is bigger, e.g., 1% of $|U|$, even with "good" $H$ we have some non-zero probabiity of collision, so the illustration is self-evident: we can assert that $Pr_r[H]>0$, or directly that $Pr_c[H] < Pr_c[H \circ H]$.


Rigour and other considerations

General considerations, trying to consolidate @SqueamishOssifrage comments:

  • In the first hashing the domain of $H$ is larger than its codomain.

  • In the second hashing the domain and codomain have the same size.
    (preventing against length extension attacks)

  • ${Pr}_c[H]$ is never zero, not even for SHA-256... But is a so small $\epsilon$.

  • For "good hashes" the afirmative answer has no practical application: both values, of ${\epsilon}_1=Pr_c[H]$ and ${\epsilon}_2=Pr_c[H \circ H]$, are so minuscule it is silly to worry about ${\epsilon}_2-{\epsilon}_1$.

Semantic: the point about "collision probability" versus "collision resistance" cannot be emphasized enough... See comments (or please edit here, it is a Wiki!).

$\endgroup$
  • $\begingroup$ This doesn't address anything about the difficulty of deliberately finding collisions, so it's all basically irrelevant to collision resistance. Unless $H$ is injective (e.g., a permutation), which it can't be if its domain is larger than its codomain, $\Pr_c[H]$ is never zero, not even for SHA-256. But for a uniform random 256-bit function, $\Pr_c[H](S)$ and $\Pr_c[H \circ H](S)$ are both so minuscule it is silly to worry about the difference. $\endgroup$ – Squeamish Ossifrage May 2 '18 at 22:21
  • $\begingroup$ The point about collision probability versus collision resistance cannot be emphasized enough. We can prove that Poly1305 on strings of up to a megabyte in length has collision probability below $2^{108}$ under a uniform random key. But if you know the Poly1305 key, it is trivial to deliberately find collisions. And if you know the Poly1305 hashes for two messages under the same key, you can trivially recover the key. So Poly1305 is completely useless for a public repository like this, even though it has an amazing proof about collision probabilities. $\endgroup$ – Squeamish Ossifrage May 2 '18 at 22:29
  • $\begingroup$ In contrast, SHA256d(x) = SHA256(SHA256(x)) is probably not much less collision-resistant than SHA256. Does it have a slightly smaller image? Probably, but the difference between them is so small it is foolish to worry about. There are applications where SHA256d is better than SHA256, where length extension attacks are relevant. For the case of a public repository of documents, that probably doesn't matter so there's not much reason to use SHA256d. But marginally reduced collision resistance of SHA256d is not a compelling reason to reject it. (More compelling: it's needless complexity.) $\endgroup$ – Squeamish Ossifrage May 2 '18 at 22:35
  • $\begingroup$ Thanks @SqueamishOssifrage to your rigour and explanations. I edited changing "perfect" to "good" (and using quotations), and adding a final section... but I can forget something, please you can also edit, is a Wiki-answer. $\endgroup$ – Peter Krauss May 2 '18 at 23:32
  • 1
    $\begingroup$ Sorry, I'm not interested in editing this to fix the deep conceptual errors in it even if it is a community wiki, particularly after you self-accepted your own answer when someone else had already written a perfectly good one for which you had no substantive criticism or questions for clarification. The difference between collision probability and collision resistance, and the futility of studying collision probability as a proxy for collision resistance, is so fundamental it is hopeless to address it as a mere footnote. $\endgroup$ – Squeamish Ossifrage May 3 '18 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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