5
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ 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). $\endgroup$
    – SEJPM
    Feb 12 at 11:37
  • $\begingroup$ @SEJPM - yeah, that's my point - in this case H is not chosen randomly. It's fixed. $\endgroup$
    – user93353
    Feb 12 at 11:39
  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Feb 12 at 11:44
  • $\begingroup$ @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 $\endgroup$
    – user93353
    Feb 12 at 12:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Patriot
    Feb 12 at 13:49
1
$\begingroup$

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.

Intuitively, the property used is that UHF should be hard to blindly predict the difference for any two inputs without knowing the key, even with multiple attempts, but without revealing the UHF value on each attempt.

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'). $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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