# Carter-Wegman MAC different notations

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?

• 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. Commented Feb 6 at 15:39
• @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? Commented Feb 6 at 15:42
• 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 Commented Feb 6 at 16:09

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

• 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). Commented Feb 6 at 22:52