# Can a collision resistant hash return zero?

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?

• Is this a homework question? Mar 7 at 3:41
• @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. Mar 7 at 4:46
• 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. Mar 7 at 6:36
• 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.
– fgrieu
Mar 7 at 9:01
• 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) Mar 7 at 13:12

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.

• 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? Mar 8 at 1:57