# How does GHASH used in GCM behave as a universal hashing function?

As per my understanding, a Universal Hash Function isn't a cryptographic hash function & it's output isn't uniformly distributed. However, this is still secure because it's actually a family of functions & one or more of the random inputs to the function decides which function is actually picked from the family of functions & this is what makes it secure.

However, these are the Parameters to GHASH

$$GHASH(H, A, C)$$ where

$$H = E(K, 0^w)$$

$$K$$ is the encryption key & it's fixed, so a new one isn't picked every time, which means $$H$$ is also fixed.

$$A$$ is the Additional Authenticated Data

$$C$$ is the Ciphertext

So how exactly is this a universal hashing function - what is the family & how exactly are we randomly choosing from the family?

• Note that a universal hash function is not immediately a secure MAC (generally). For GHASH you choose the concrete function from the family using your choice of $H$. More details in an answer later (probably).
– SEJPM
Feb 12 at 11:37
• @SEJPM - yeah, that's my point - in this case H is not chosen randomly. It's fixed. Feb 12 at 11:39
• Ah, I see, it is actually chosen uniformly, because an adversary doesn't know $K$ and thus doesn't know $H$ (and the block cipher is a PRF). The thing you are probably confused about is the fact that $H$ is not chosen freshly for each message. But for the universal hash function property you don't need to pick the function freshly for each message.
– SEJPM
Feb 12 at 11:44
• @SEJPM - that's exactly what confuses me. I thought a universal hash used something like a nonce to pick a diff function from a family of function. If it uses a fixed key, then how is it different from regular hash functions used in Keyed Hashing? As a matter of fact, Boneh in his lecture on CarterWegman MAC calls the MAC as a One Time MAC. I am confused now as to how the CWMAC is a Onetime MAC Feb 12 at 12:11
• Universal hash functions are confusing, especially for the layman, and I have been unable to find a description on the Internet that explains them clearly with examples. Feb 12 at 13:49

Indeed $$H=E_k(0)$$ is used to choose from the family. This is not a problem, and here is some intuition on why.
The output of the hash function is not leaked in clear, it is "hidden" by xoring with $$E_k(iv,ctr=0)$$ which is different per each encrypted message (in contrast to $$H=E_k(0)$$). Otherwise it would be indeed trivial to recover H as the UHF is linear.
Note that the "difference" matters here because in forgery attempts you are allowed to reuse the nonce, so guessing the right difference would suffice for a break. For example, given $$(iv,m,t),~~ t=E_k(iv,ctr=0)\oplus GHASH(m))$$ and guessing the difference $$\Delta = GHASH(m)\oplus GHASH(m')$$ would allow to forge $$(iv,m',t'),~~ t'=t\oplus \Delta=E_k(iv,ctr=0)\oplus GHASH(m').$$