# Why does Carter-Wegman (and AES-GCM) use different keys for PRF and keyed-hash

So. As I understand, Carter-Wegman transforms a one-time MAC (which must be a difference unpredictable function (DUF)) by encrypting it with a PRF.

The DUF and the PRF use two different keys, which can be understandable if:

• you're just being precautious and not mixing keys
• the PRF and the DUF might take keys of different sizes/format

Now, AES-GCM uses AES and GHASH which both take keys of size 128-bit. So why don't they use the same key?

• Carter and Wegman[1] (paywall-free) didn't do anything with a PRF—they just authenticated messages $m_1, m_2, \dots, m_n$ with a universal hash family $H$ and the $n + 1$ independent uniform random shared secrets $r, s_1, s_2, \dots, s_n$ by $m_i \mapsto H_r(m_i) + s_i$, and straightforwardly proved forgery probability bounds in terms of the difference probabilities of $H$, using independence of $r$ and $s_i$. – Squeamish Ossifrage Mar 6 '19 at 22:12
• It was Shoup[2] who first suggested using a PRP (DES) and proved forgery bounds in terms of (a) PRP advantage bounds, (b) permutation/function switching bounds, and (c) the forgery bounds of the Carter–Wegman theorem. – Squeamish Ossifrage Mar 6 '19 at 22:18
• Here independent has the standard definition in probability theory: two random variables $X$ and $Y$ are independent it for all possible values $x$ and $y$, $\Pr[X = x, Y = y] = \Pr[X = x]\,\Pr[Y = y]$, or, equivalently, $\Pr[X = x \mid Y = y] = \Pr[X = x]$. – Squeamish Ossifrage Mar 6 '19 at 22:24
• P.S. You should use ChaCha/Poly1305 with a 256-bit key if you want a ‘128-bit security level’. Simpler, faster and safer in software, better security bounds than even AES-256-GCM. – Squeamish Ossifrage Mar 7 '19 at 2:49

Let's consider a degenerate case. Suppose you're authenticating 16-byte messages, your DUF (better known as (almost) xor-universal hash) is $$\text{AES}_k$$, and your PRF is also $$\text{AES}_k$$. Then you have $$\text{WC}(m, n) = \text{AES}_k(m) \oplus \text{AES}_k(n)\,,$$ where $$m$$ is your 16-byte message, and $$n$$ is a 16-byte nonce. This is obviously forgeable by simply switching the nonce and the message! Yet, it would be perfectly secure if we used independent keys for each primitive.
• For example, if $H$ is a universal hash family and $E$ is an independent ideal block cipher, then obviously $m_i \mapsto H_k(m) + E_k(i)$ is secure up to the birthday bound even though $k$ is shared between them. How well does this model fit for GHASH as $H$ and AES as $E$? It might be perfectly fine! Or it might be a disaster. None of the existing research on AES security would have considered this case, so, it's hard to say! – Squeamish Ossifrage Mar 6 '19 at 22:23