Suppose that we have a pseudorandom function $F$. We compute a tag on message $m=m_1,m_2,...,m_l$ with $F_k(\langle 1\rangle\mathbin\Vert m_1) \oplus \dots\oplus F_k(\langle l\rangle\mathbin\Vert m_l)$, where uniform key $k \in \{0, 1\}^n$, $m_i \in \{0, 1\}^{n/2}$ and $\langle i\rangle$ denotes an $n/2$-bit encoding of the integer $i$. I think this is secure MAC, because an efficient adversary cannot find an equal tag for two different messages, even he uses an oracle. But I can't prove it. Am I wrong?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ There are MACs in the literature that have a broadly similar structure: apply a tweakable PRF to each block of the message, with the block number as a tweak, and XOR their outputs. But they usually have some other step or detail to defeat attacks like the one poncho points out. You might want to read Bernstein's "How to stretch random functions" or Black and Rogaway's PMAC papers (e.g., this one). $\endgroup$– Luis CasillasCommented May 24, 2017 at 17:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Am I wrong?
You're wrong.
For one, the task for the adversary isn't two find an equal tag for two different messages (actually, with this MAC, he could with some work, however that is not actually required to break the security guarantee of the MAC). Instead, his task is to generate a Message, MAC pair that he has not queried, but still validates, and it doesn't matter if the MAC he generates isn't any of the MACs that the oracle has generated.
So, in this case, consider the case where the attacker queeries the Oracle for the MACS of the three messages $M^1 = m_1 m_2$, $M^2 = m'_1 m_2$ and $M^3 = m_1 m'_2$. Can we deduce the MAC of the fourth message $M^4 = m'_1 m'_2$?
-
$\begingroup$ Yes, If we XOR all of these tags, we obtain the tag of M4, but what is the usage of <i>? $\endgroup$– ThisIsMeCommented May 24, 2017 at 15:34
-
$\begingroup$ @ThisIsMe: I believe that they inserted
<i>so that $\text{MAC}( m_1m_2 ) \neq \text{MAC}( m_2m_1 )$, however that's not sufficient. $\endgroup$– ponchoCommented May 24, 2017 at 15:38
$\begingroup$
$\endgroup$
1
Your construction is the same as what Bernstein, in his brief paper on "How to stretch random functions", calls a counter sum and notates as:
$$ f^+(p) = f(\underline{1},\, p_1) + \cdots + f(\underline{k},\, p_k) $$
He notes (p. 4) that plain counter sums are predictable but protected counter sums are good PRFs:
$$ f'(p) = f(\underline{0},\, f^+(p)) $$
Quoting:
The counters $\underline{1}, \dots, \underline{k}$ hide input patterns. The sum $f^+(p_1, \dots, p_k)$ is predictable from its linear structure—if $p_1$ is changed, the output difference is independent of $p_2$—but it is protected inside $f(\underline{0}, \cdot)$, so an attacker cannot recognize output differences other than 0.
The statement about the independent output differences in unprotected counter sums gives us a property that can be used to defeat it as a MAC, which poncho's answer hints at as well.
answered May 24, 2017 at 19:23
-
1$\begingroup$ The $f'$ design is essentially a Carter-Wegman MAC; the function $f^+$ is an almost-universal hash function (a keyed function for which any two different messages $M, M'$, $f_k^+(M) \ne f_k^+(M')$ for all but a negligible portion of the keys $k$); applying a final hash to protect the au-hash function output is a standard method (albeit fallen out of fashion for some reason). This comment is just to show how this design fits into the existing framework... $\endgroup$– ponchoCommented May 24, 2017 at 20:08