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

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

• I guess you might as well ask: how much effort is needed to find two strings $r_1, r_2$ where $r_i \in \{0, 1\}^n$ such that $\Delta(r_1, r_2) \leq k$, as "a small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value" (i.e. pseudo random) is a requirement for hash functions. Problem is, I only found a partial answer here. Maybe a big $\sum$ can help though (we could ask on Math...). – Maarten Bodewes Jan 2 '17 at 19:25

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.

• Am I correct in thinking that this is basically the same as - although more complete than - my comment below the question, assuming the Hamming distance of only the output and adding up the probabilities? – Maarten Bodewes Jan 5 '17 at 9:24
• Yes. Since the output of a good hash function is close to a random function. – user13741 Jan 5 '17 at 12:39
• Can you elaborate more on the last sentence? I understand that the hamming distance will have a binomial distribution if we model the hash function as a random oracle. However, what is the implication if SHA2 families don't have binomial distribution? Does it imply an attack on SHA2? – DiamondDuck May 31 '17 at 19:37
• The minimum hamming distance between pairs won't actually have the binomial distribution, you are not measuring the distances from a given fixed vector that is guaranteed to be one element of the minimising pair. So the process is not independent even if the individual vectors are drawn from a uniform distribution as in the random oracle model. – kodlu Jun 18 '17 at 3:19