3
$\begingroup$

While studying Carter-Wegman message authentication codes MAC, I got two different notations for the broader concept and have problems with understanding the difference, if any exist.

Let $K, K_1, K_2$ be randomly sampled keys, $k_i$ be a unique randomly sampled key (random nonce) for message $M_i$, and $h$ be a keyed strongly universal function (I assume making the strongly universal (hash) function keyed corresponds to random sampling the function).

I would define the concept of Carter-Wegman MAC as follows:

$$ Mac(K, M_i) = h(K, M_i) \oplus k_i $$

Now, I have seen multiple times that (e.g. here) that it can also be noted as follows:

$$ Mac(K_1 || K_2, M_i) = h(K_1, M_i) \oplus f(K_2, k_i) $$

(I introduce a second key because I already keyed $h$ to emphasize being a secret / randomly sampled hash function)

Can someone explain the difference in more detail? I see problems with the first definition because $k_i$ can be "Xored away", a problem the second notation does not have. But this way I read it from the original paper. Could my confusion arise from the concept of numbered messages?

$\endgroup$
3
  • 1
    $\begingroup$ At a high level, CW encrypts the output of a keyed hash. Just like with normal encryption, we can encrypt with a one-time pad (1st case) or we can encrypt with a related counter mode. So the second example uses a PRF $f$ to generate a pad from a counter $k_i$, $k_i$ need not be random or secret, just unique for each invocation. $\endgroup$ Feb 6 at 15:39
  • $\begingroup$ @MarcIlunga Thank you for your answer. If we encrypt in an OTP style, $k_i$ can not be part of the tag sent between the parties, so all $k_i$ must be shared keys, right? Can I send $k_i$ as part of the tag using the second construction? $\endgroup$
    – Titanlord
    Feb 6 at 15:42
  • 2
    $\begingroup$ Yes. In the second cases. You do send $k_i$. That should not even be called a key.. It only need to unique just like a CTR nonce $\endgroup$ Feb 6 at 16:09

1 Answer 1

3
$\begingroup$

Can someone explain the difference in more detail?

Actually, there is no real difference. When the first one says $k_i$, what it means is that there is a separate (and independent) $k_i$ for each message (hence, you can't 'xor' them out by xoring two different tags). One way of generating such a $k_i$ is to transform a nonce, that is $k_i = f(K_2, n_i)$, where $n_i$ is a public nonce. If we replace $n_i$ with $k_i$, we get the second equation.

That said, I would also note that the current usage of Carter-Wegman is somewhat different from the original paper. It assumed a 'strongly universal hash function set'; we know of constructions that can do that, but current practice is to go with a computationally cheaper option; one for which, for any two messages $M_1 \ne M_2$ and any $\delta$:

$$h(k, M_1) - h(k, M_2) = \delta$$

for only a tiny fraction of the possible key values $k$, and where the $-$ operation is some group subtraction operation.

We have such $h$ functions which provably meet this goal (and are efficient and take small keys); what this means is that the MAC actually becomes:

$$Mac( K_1, K_2, M, N ) = H( K_1, M ) + f( K_2, N )$$

where $+$ operation is addition in that same group.

Note that the $+$ operation need not be bit-wise xor. For Poly1305, it is actually modular addition (and Poly1305 does not meet the required property if we use the bitwise xor operation as its group operation).

$\endgroup$
2
  • $\begingroup$ I suppose there's still arguably a difference in both schemes. The first is unconditionally secure (assuming we have a DUH and also the pad is used once). $\endgroup$ Feb 6 at 22:52
  • $\begingroup$ Thank you for your answer! $\endgroup$
    – Titanlord
    Feb 7 at 11:59

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.