1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 6, 2019 at 22:12
  • $\begingroup$ 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. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 6, 2019 at 22:18
  • $\begingroup$ 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]$. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 6, 2019 at 22:24
  • $\begingroup$ 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. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 7, 2019 at 2:49

1 Answer 1

Reset to default
2
$\begingroup$

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.

In less degenerate cases, such as GCM, you could possibly use the same key for both. But you would have no easy way of arguing the security of the scheme, since the hash and the PRF would not be independent.

Improve this answer
$\endgroup$
5
  • $\begingroup$ thanks for the answer! What do you mean by "independent" here? $\endgroup$
    – David 天宇 Wong
    Commented Mar 6, 2019 at 20:15
  • 1
    $\begingroup$ They are picked using the same "randomness", instead of being picked independently at random from the set of all possible hashes / PRFs. Wegman-Carter is essentially a hash encrypted with a one-time pad, and that only works if the one-time pad is not correlated to the plaintext. $\endgroup$
    – Samuel Neves
    Commented Mar 6, 2019 at 20:20
  • $\begingroup$ This justifies the general prudence not to share keys between different cryptosystems because there might be bad interactions. But it doesn't really address the more specific question: Is it critical for the specific case of AES-CTR and GHASH that the keys be independent? $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 6, 2019 at 21:50
  • 1
    $\begingroup$ 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! $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 6, 2019 at 22:23
  • $\begingroup$ That's what I mean by "no easy way to argue security". It could be fine, GHASH and AES look "unrelated enough", but we have no good way of showing it. Otherwise you'd start seeing modes saving the one blockcipher call. $\endgroup$
    – Samuel Neves
    Commented Mar 6, 2019 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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