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

  • $\begingroup$ When I said "function" I didn't mean "pseudorandom function". $\endgroup$
    – Melab
    Sep 16 '17 at 2:09
  • $\begingroup$ 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? $\endgroup$ Sep 16 '17 at 17:08
  • $\begingroup$ 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. $\endgroup$
    – Melab
    Sep 16 '17 at 21:27
  • $\begingroup$ 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)$. $\endgroup$ Sep 17 '17 at 15:52
  • $\begingroup$ What is the upper bound on the security of this scheme? $\endgroup$
    – Melab
    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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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