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!

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Is this a homework question? $\endgroup$
    – meshcollider
    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
  • $\begingroup$ Hello! Sorry for confusing you. This question is not my homework. Recently I have been learning about AES GCM proof[McGrew04]. In the GHASH property section (in appendix A) , it gives several definitions including AXU-Hash, and it also makes an additional statement about GHASH being "unlikely return zero" (lemma 4). Thus, I started to wonder if there is a connection between hash collision and zero hash result. Unfortunately, I can't prove the statement above right now. Lastly, I came to ask for help. So this question, which is indeed a little bit weird, is purely my personal thought. $\endgroup$
    – Max1z
    Mar 7, 2022 at 6:36
  • 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$ 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

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\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

Your Answer

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

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