3
$\begingroup$

Recently, I have been reading the original proof of GCM.

It mentioned the properties of "almost universal" and "return zero" for hash function.

I wonder if there is a connection between the two, that is

If a hash function is collision resistant, then it is "unlikely" return zero.

In a more formal way, we have the following:

For $\forall M, M^{'} \in \{0,1\}^{n}, M \ne M^{'}$,

if $\mathrm{Pr}\left[H_{K}(M)\oplus H_{K}(M^{'})=0^{n}\ \middle|\ K\stackrel{\\\$}{\leftarrow} \{0,1\}^{n}\right] \le \epsilon_{1}$ holds, then $\mathrm{Pr}\left[H_{K}(M) =0^{n} \middle|\ K\stackrel{\\\$}{\leftarrow} \{0,1\}^{n}\right] \le \mathrm{Pr}\left[H_{K}(M)\oplus H_{K}(M^{'})=0^{n}\ \middle|\ K\stackrel{\\\$}{\leftarrow} \{0,1\}^{n}\right] \le \epsilon_{1}$ also holds.

Is this statement correct?

  • If is, how to prove this?
  • If not, what is the relationship between collision resistance and zero hash result?

Thanks in advance!

$\endgroup$
8
  • 1
    $\begingroup$ Is this a homework question? $\endgroup$ Mar 7, 2022 at 3:41
  • 1
    $\begingroup$ @meshcollider Given the history of asking from Max, I don't think he's interested in making others do his homework. But that's just my personal judgement, Max will still have to explain his effort tackling this question. $\endgroup$
    – DannyNiu
    Mar 7, 2022 at 4:46
  • 1
    $\begingroup$ Hint: a more general, more precise, equally valid, and perhaps more understandable statement is: If a hash function is collision resistant, then for any value in it's defined output set, that hash function is "unlikely" to return that value for a random input. The proof is easy. $\endgroup$
    – fgrieu
    Mar 7, 2022 at 9:01
  • 1
    $\begingroup$ Note that it could be easy to find a single message for which H(m) = 0 even if you can't find two distinct such m (collision resistance does not imply preimage resistance). $\endgroup$ Mar 7, 2022 at 11:39
  • 1
    $\begingroup$ GHASH is not a 'collision resistant hash function'; instead, it is an 'almost universal hash function' - those are different things. For one, given oracle access to GHASH, it is easy to find collisions (or, for that matter, preimages) $\endgroup$
    – poncho
    Mar 7, 2022 at 13:12

2 Answers 2

2
$\begingroup$

Is this statement correct?

Actually, in the specific case of GHASH, it is not.

GHASH has the property that $\forall k: H_k(0^n) = 0$; hence that shows that the desired inequality doesn't hold.

What's going on is for GHASH, we always have $H_k(M) \oplus H_k(M') = H_k(M \oplus M')$; we also have $\mathrm{Pr}\left[H_{K}(M) =0^{n} \middle|\ K\stackrel{\\\$}{\leftarrow} \{0,1\}^{n}\right] \le \epsilon$ for $M \ne 0^n$, which is why the original inequality holds.

On a side note, you asked about 'collision resistant hash functions'; it turns out that GHASH is not a collision resistant hash function - instead, it is a "$\Delta$ almost universal hash function"; your first equation (replacing $0^n$ with a free variable) is essentially the definition.

GHASH is not a collision resistant hash function because if you are given Oracle access to GHASH, it is easy to recover $k$, and from there, it is easy to find collisions.

$\endgroup$
1
  • $\begingroup$ Thank you poncho and Mikero! I learned a lot from your answer. But How about the general cryptopgrahic hash functions ? That is, forget about GHASH and suppose there is some collision resistant hash $H$, then is the original statement correct? $\endgroup$
    – Max1z
    Mar 8, 2022 at 1:57
2
$\begingroup$

Regarding the related question on what can be said for a general cryptographic hash function. Collision resistance does not imply that it is hard to find an input where the function returns $0^n$.

For any collision resistant hash $H$, there exists a collision resistant hash $H'$, that always returns $0^n$ on a specific input. For example, the following function always return $0^n$ on input $0^n$, but is also collision resistant if $H$ is collision resistant:

$H'(M)= \begin{cases} 0^n & \text{if } M=0^n\\ H(M) & \text{if } M\ne 0^n \land H(M)\ne 0^n\\ H(0^n) & \text{otherwise.} \end{cases}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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