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

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.

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

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