How efficient are the generic attacks regarding near-collision-resistance?

Question

In a recent answer I gave a definition of near-collision-attacks. Now beyond the definition and what to do with this type of attack my knowledge is fairly limited. So here's the question:

Let $H:\{0,1\}^*\rightarrow\{0,1\}^n$ be a cryptographically secure hash function. Let $k\in\mathbb N$ be $0<k<n$. Without further details, how much effort is needed to find two strings $x_1,x_2$ such that $$\Delta(H(x_1),H(x_2))\leq k$$

holds?

---

As in the other answer $\Delta(x,y)$ shall denote the Hamming distance between $x$ and $y$.

Answer 1

The hamming distance is going to have a binomial distribution. Given two $n$-bit hashes, the probability that the hamming distance is exactly $k$ is:

$Pr(n,k) = {{n}\choose{k}}\frac{1}{2}^{k}\frac{1}{2}^{n-k} = {{n}\choose{k}}\frac{1}{2}^{n}$

So if you want to know the probability of the hamming distance being $\le k$ you need to sum:

$p = Pr(n,0) + Pr(n,1) + Pr(n,2) + ... + Pr(n,k)$

For example, if $n=128$ and $k=32$ then the probability is approximately 0.000000006421. So you'll need to try 155,738,981 times on average.

If you want to apply the birthday attack thinking to this, where the probability of success increases with the number of hashes you collect, you'll need approximately $\sqrt{\frac{1}{p}}$ messages for a 50% probability. This is a rough approximation based on the idea that the number of message pairs grows quadratically.

So in the above example, you'll need to collect 12480 hashes.