Authentication of data using XOR and a secure function

Suppose that:

• $i$ is a zero-based index.
• $K$ is a secret key.
• $X$ is a stream of data.
• $x_{i}$ denotes the $i$th block of data in $X$.
• $s$ is the number of blocks in $X$.
• $X = x_{0}\mathbin\|x_{1}\mathbin\|\dots\mathbin\|x_{s-2}\mathbin\|x_{s-1}$.
• $y_{i}$ is a value derived from $x_{i}$, $i$, and $K$ in a way that incorporates some known-to-be-secure function (like a block cipher).
• $\alpha = \bigoplus\limits_{i=0}^{s-1} y_{i}$.

If the authentication tag is derived from $\alpha$ and $K$ in some way that uses the same function used to in deriving $y_{i}$, then would this be a secure authentication algorithm?

It can be.

Suppose $y_i = F_K(1 \mathbin\| i \mathbin\| x_i)$ and $t = \alpha \oplus F_K(0 \mathbin\| n)$ is the authentication tag, for some PRF $F_K$ and per-message nonce $n$. The security of this structure is called XMACC and analyzed by Bellare, Guérin, and Rogaway, ‘XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions’, Proceedings of CRYPTO '95, Springer LNCS 963, 1995.

Suppose $y_i = x_i {K_0}^{i + 1}$ and $t = \alpha + K_1$ with arithmetic in $\operatorname{GF}(2^{128})$, where $K_0, K_1 \in \operatorname{GF}(2^{128})$ are uniform random, and $K_1$ is only ever used once. This is the structure of GHASH, which is used by AES-GCM in Carter–Wegman mode with $K_0 = \operatorname{AES}_K(0)$ and $K_1 = \operatorname{AES}_K(n)$ for a per-message nonce $n$.

• When I said "function" I didn't mean "pseudorandom function". Sep 16 '17 at 2:09
• I don't understand. You're saying that the functional relation $y_i = f(K, i, x_i)$ is not allowed to be built out of a pseudorandom function family $F_K$ with $f(K, i, x) = F_K(i \mathbin\| x)$? Can you be more specific about the constraint you're imposing? Sep 16 '17 at 17:08
• It can be. It could also be built on a pseudorandom permutation such as a block cipher (which I mentioned). I used the term "function" in its broader sense. Sep 16 '17 at 21:27
• A PRP makes a reasonable approximation to a PRF. If it didn't, we wouldn't use AES-CTR or AES-GCM. If the parameter sizes all fit, you could certainly use $F_K(b) = \operatorname{AES}_K(b)$. Sep 17 '17 at 15:52
• What is the upper bound on the security of this scheme? Nov 29 '17 at 23:28

This is a form of what this Bernstein paper calls an (unprotected) counter sum. It is not a secure MAC, it is vulnerable to a simple attack (and I'll use 1-based indexing, unlike your question's 0-based indexes):

1. Adversary chooses a one-block message $x$ and queries for its tag; gets back $t_1 = f(1, x)$.
2. Adversary chooses a one-block message $x'$ (distinct from $x$) and queries for its tag; gets back $t_2 = f(1, x')$.
3. Adversary computes the difference of the two tags: $d = t_1 \oplus t_2$.
4. Adversary chooses a block $y$ and queries for the tag of $x \mathbin\Vert y$; gets back $t_3 = f(1, x) \oplus f(2, y)$.
5. Adversary guesses that the tag of $x' \mathbin\Vert y$ is $t_4 = t_3 \oplus d$.

The reasoning is that the difference between the tags of $x$ and $x'$ has got to be the same as that between the tags of $x \mathbin\Vert y$ and $x' \mathbin\Vert y$:

\begin{align} d &= t_1 \oplus t_2 \\ d &= f(1, x) \oplus f(1, x') \\ d \oplus t_3 &= f(1, x) \oplus f(1, x') \oplus t_3 \\ d \oplus t_3 &= f(1, x) \oplus f(1, x') \oplus f(1, x) \oplus f(2, y) \\ d \oplus t_3 &= f(1, x') \oplus f(2, y) \\ d \oplus t_3 &= t_4 \end{align}

A simple solution is to compute a protected counter sum, like Bernstein's paper describes:

$$f'(x_1, \dots, x_n) = f(0, f(1, x_1) \oplus \cdots \oplus f(n, x_n))$$

The outer, zero-indexed application of $f$ "protects" the output of the XOR from the attack above.

EDIT: @Melab has highlighted that I seem to have misinterpreted the last sentence in the question:

If the authentication tag is derived from $\alpha$ and $K$ in some way that uses the same function used to in deriving $y_{i}$, then would this be a secure authentication algorithm?

The problem here is when you say "some way," because it's not clear whether you mean to ask whether there exists some way that will yield a secure MAC, or whether your construction is secure given any way of using the same function. The answer is "yes" for the former, "no" for the latter.

• I think my calculation of the authentication tag already does that. Sep 15 '17 at 22:08
• Oh, I misunderstood that last sentence then. I'll make an edit. Sep 15 '17 at 22:48
• Are we looking at a security equal to the key size? Sep 16 '17 at 0:16