1
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.