# Minimum difference collision metric

Take a hash function $H$.

There will be pairs of messages of the same length $M,M'$ for which $M\ne M',H(M)=H(M')$.

Let $P(x)$ be a function counts the number of $1$s in $x$. $d=P(M\oplus M')$, or in words, $d$ is the number of bits where $M$ and $M'$ differ.

Let $T(H)$ be the minimum value of $d$ for $H$. This is the metric. It does not say anything about how hard it is to actually find these colliding messages, only that a certain minimum number of bits must change to produce a collision.

Is this metric actually useful? Is it okay for $T(H)$ to be small, as long as actually finding such a collision is infeasible, or does a small $T(H)$ imply $H$ is weak?

Are there bounds on $T(H)$ for any of the popular hash functions? (SHA2 family, SHA3 family, BLAKE2 and its variants)

Is it okay for $T(H)$ to be small, as long as actually finding such a collision is infeasible, or does a small $T(H)$ imply $H$ is weak?

If $H$ is a random function that takes large sized inputs, and produce a fixed sized output, then $T(H) = 1$ with exceedingly high probability.

Let us call then fixed size of the output of $H$ $n$ bits.

Then, for any pair of distinct messages $M, M'$, he have the probability of $H(M) = H(M')$ as $2^{-n}$ (as $H$ is assumed to be a random function).

Now, if we have $m > n$, and consider all possible $m$-bit pairs $M, M'$ that differ by one bit, we have $m2^{m-1}$ such pairs.

The probability that no such pair will collide is $(1 - 2^{-n})^{m2^{m-1}} \approx e^{-m 2^{m-n-1}}$, as $m2^{m-n-1}$ is large, this probability is tiny, and hence with high probability, there will be at least one collision that differs by a single bit.

As a collision must differ by at least one bit, we have $T(H) = 1$ (again, with high probability).

Is this metric actually useful?

Doesn't appear to be; we don't have any way of computing $T(H)$ for any strong hash function, so it's not useful in a practical sense. And, from a theoretical one, it's 1 for anything that acts like a random function, so I don't see any immediate use there.

• Very minor point, but wouldnt there be $m2^{m - 1}$ such pairs? – Guut Boy Nov 14 '17 at 15:25
• @GuutBoy: Doh! You're correct, of course... – poncho Nov 14 '17 at 15:42