# 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, 2022 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, 2022 at 4:46
• 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, 2022 at 9:01
• 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). Mar 7, 2022 at 11:39
• 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, 2022 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, 2022 at 1:57

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}$$