4
$\begingroup$

The traditional brute force collision attack is generate $2^{N/2}$ (unique) random strings, hash them and this results in ~50% chance for collision. The attack talked in the question's title is generate hashes by the sequence $H_0 = F(S), H_n = F(S||H_{n-1})$, where $S$ is a string to make collision with, $F$ is the hash function, and the sequence stops at $2^{N/3}$.

The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes. When hashing $2^N$ random strings, there will be $(1-(1-\frac{1}{2^N})^{2^N})2^N$ possible hashes because of all the collisions.

The sequence that tells the fraction of the possible hashes for each hash in the sequence is $P_0 = 1, P_n = 1 - (1-\frac{1}{2^N})^{2^NP_{n-1}}$, which roughly approximates to $P_n = P_{n-1} - \frac{P_{n-1}^2}{2}$ as $\lim_{P_{n-1}\to 0}$, which can be approximated into a function $P(n) = \frac{2}{n + 2}$. (these reductions in precision make it easier for future calculations)

The chance for a collision to NOT happen for a hash in the sequence against all of it's following hashes is $C_n = (1 - \frac{1}{P_n2^N})^{M - n - 1}$ where $M$ is the sequence's length, because the fraction is so close to $1$, it can be approximated to $C_n = 1 - \frac{M - n}{P_n2^N} = 1 - \frac{Mn - n^2}{2^{N + 1}}$. Now to approximate the multiplication of all $C$s ($C_0C_1...C_M)$ to get the chance for collision for all hashes combined, we can discard the multiplication (because again, $C_n$ is very close to $1$) and add all the subtracted parts and subtract them from $1$, which results in $1 - \frac{M^3/2-M^3/4}{2^{N+1}} = 1 - \frac{M^3/4}{2^{N+1}}$, and to reach ~50% collision rate $M = 2^{(N+3)/3-1}$, which is just $2^{N/3}$.

Is there a reason why this won't work?

$\endgroup$
  • 1
    $\begingroup$ Welcome to Cryptography. Could you elaborate The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes. $\endgroup$ – kelalaka Aug 27 '19 at 20:17
  • $\begingroup$ @kelalaka The sentence after that meant to support that statement, is it out of place? $\endgroup$ – Yanai Eliyahu Aug 27 '19 at 20:19
8
$\begingroup$

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, \dots, X_M$. The probability of a repeated value $F(X_i) = F(X_j)$ for $i \ne j$ is at most $M^2\!\big/2^N$ by the birthday paradox. For $M = 2^{N/3}$, this is $2^{2N/3}\!\big/2^N = 1\big/2^{N - 2N/3} = 1\big/2^{N/3}$. If your calculation doesn't fit this bound, there's an error in your calculation.

‘But what if we come upon a short cycle in $H \mapsto F(S \mathbin\| H)$?’, you ask. The expected number of points before a repeat in a uniform random function on a domain of $2^N$ elements is $\frac12\sqrt{2\pi\,2^N} - 1 \approx 2^{N/2}$ (Harris 1960 Eqs. 3.4 & 3.11, see paper for more details of distribution; paywall-free). So no, this method doesn't improve the expected cost.

Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!

| improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for the classical reference to Harris, and a softcopy, which already has most of the results in later papers by crypto experts... $\endgroup$ – kodlu Aug 28 '19 at 1:44
  • $\begingroup$ I feel like Harris's paper answers about a quarter of all the questions on this site! $\endgroup$ – Squeamish Ossifrage Aug 28 '19 at 1:51
  • $\begingroup$ I have chosen this answer because of the expected cycle length, this explains directly why it doesn't work. $\endgroup$ – Yanai Eliyahu Aug 28 '19 at 8:13
  • $\begingroup$ Is the expected before repeat related to the birthday paradox by any chance? $\endgroup$ – Yakk - Adam Nevraumont Aug 28 '19 at 14:44
4
$\begingroup$

It is correct that the set of possible $H_n$ over all the possible $S$ reduces as $n$ grows. However the attack evaluates the $H_i$ for a fixed random $S$, not for multiple $S$; thus that reduction is immaterial to the success of the attack.

In other words: it is evaluated the number of possible $H_i$ for random $S$ as a function of $i$, and from that drawn conclusions for collision probability among the $H_i$ for sequential $i$ and a particular $S$. The conclusions are thus not justified, and, it happens, quite incorrect.

When we model $F$ as a random function, then until there is a collision the $H_i$ are random, and hence the probability of collision among the $H_i$ with $0\le i<n$ is per the birthday bound.

| improve this answer | |
$\endgroup$
  • $\begingroup$ each $H_i$ is random from set of $2/(n+2)*2^N$ hashes, no? That's the whole point, it's the birthday problem, but reduced for each subsequent $H_i$. $\endgroup$ – Yanai Eliyahu Aug 27 '19 at 20:26
  • $\begingroup$ @Yanai Eliyahu: more precisely, for any fixed $i$, $H_i$ is random in a set of size typicaly less than $2^N$ and reducing with $i$, when the seed $S$ is uniformly random. $n$ does not come into play here. An approximation of the size of this set may be $2/(i+2)*2^N$ (depending on the particular $H$), but again since the actual $S$ is fixed, the size of that set is immaterial to the probability of collision among the $H_i$ with $0\le i<n$ $\endgroup$ – fgrieu Aug 27 '19 at 20:38
  • $\begingroup$ you mean because there is only 1 string, there is no collision? $\endgroup$ – Yanai Eliyahu Aug 27 '19 at 20:44
  • $\begingroup$ @Yanai Eliyahu: yes, I mean that since there is a single $S$, there is single $H_i$ for any given $i$, Thus no collision for a given $i$. If we had a magic box that performs $i$ iterated hashes in a blink, and we used that box for many $S$, then the size of the set of the possible $H_i$ would matter. But no magic box in sight. $\endgroup$ – fgrieu Aug 27 '19 at 20:49
  • 1
    $\begingroup$ Got it... it makes sense now, I tested that attack on fixed $S$, and it worked like normal birthday problem, but when I only used $H_0$ and $H_1$ and made many strings it worked as expected (improved collision chance), but reaching higher $M$ reduces the collision chance to the birthday problem. $\endgroup$ – Yanai Eliyahu Aug 27 '19 at 21:14

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.