Why this brute force attack doesn't reduce all cryptographic hash functions' security bits against collision attacks to N/3?

Question

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?

Answer 1

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!

Answer 2

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.