0
$\begingroup$

Is the following MAC secure?

For a block $y_i$ in a file, we defined a MAC as follows: $Mac_i:PRF(k,i) \cdot g^{y_i \cdot r_i} \bmod p$.

Where $p$ is a prime number, $g \in \mathbb{G}$,$PRF(k,i)$ is a pseudorandom function whose output is distributed uniformly random over $\mathbb{G}$, $k$ is a $l$ bit key, and $i$ is index of value $y_i$ in the file .

** More importantly, we define a polynomial ring $R[x]$ and $f(x) \leftarrow R[x]$. Where $f(x)$ is a linear permutation polynomial that has the form $ax+b$, where $a,b$ are picked uniformly random from $R$. We define $r_i$ as: $f(x_i)=r_i$ where $x_i \in \textbf{x}$, and $\textbf{x}$ is a pubic vector and $R$ is $\mathbb{Z_p}$.

It is clear that if $r_i$ is picked randomly the above Mac would be secure for a file. So when we define a mac for a block at index $i$ in different file, we change the key $k$ to $k'$. However, here I use a permutation polynomial and by definition its output is distributed uniformly random in $\mathbb{Z_p}$ and I make the elements in $\textbf{x}$ public (for some computation which is not the focus of this conversation).

So I pick the polynomial,$f$, once for a file, and for each block $i$, I evaluate $f$ at the corresponding value in $\textbf{x}$, so $r_i=f(x_i)$. Note that there are $|R|^2-|R|$ different linear polynomials in the field $R$.

Please let me know if it needs more explanation.

$\endgroup$
1
$\begingroup$

It is clear that if $r_i$ is picked randomly the above Mac [defined in the second paragraph] would be secure.

Actually, that's not at all clear. I would claim that if I were given that values of $Mac_i(a)$ and $Mac_i(b)$, I could compute the value of $Mac_i(x)$ for any $x$, as long as $a-b$ is relatively prime to $p-1$. To do this, I need the value of $p$, $a$ and $b$, but not $k$, $r_i$, or for that matter, $g$.

To do this, I would compute $X = Mac_i(a) / Mac_i(b) \bmod p$; that value is $X = PRF(k,i) \cdot g^{a \cdot r_i} / PRF(k,i) \cdot g^{b \cdot r_i} = (g^r_i)^{a-b}$

I then compute $X^{(a-b)^{-1}}$, giving me the value $Y = g^r_i$.

I then compute $Z = Mac_i(a) / Y^a = PRF(k,i) \cdot g^{a \cdot r_i} / g^{r_i \cdot a} = PRF(k,i)$

Once I've done that, I can compute the $Mac_i$ of an arbitrary value $Mac_i(x) = Z \cdot Y^x = PRF(k,i) \cdot g^{r_i \cdot x}$

$\endgroup$
  • $\begingroup$ Thanks for your answer, but that $Mac_i$ is for the block residing at position $i$ in the file denoted by $\textit{file_1}$ (it should have been more clearer in the question). So for the next file we change the Key, $k$ to $k'$. Thus, here we only consider Macs for different indices of a file. $\endgroup$ – user13676 Feb 3 '15 at 16:12
  • $\begingroup$ @user13676: So, you compute $Mac_i$ only once (for a specific $i, k$ pair)? If so, why don't you use the simpler construction $a_i \cdot y_i + b_i \bmod p$, for secret $a_i, b_i$? $\endgroup$ – poncho Feb 3 '15 at 16:14
  • $\begingroup$ Yes, it is more less similar to tags in PDP (provable data possession), but we try to use a linear permutation polynomial to generate the random exponent and the vector $\textbf{x}$ is public. $\endgroup$ – user13676 Feb 3 '15 at 16:18
  • $\begingroup$ cs.berkeley.edu/~dawnsong/papers/p598-ateniese $\endgroup$ – user13676 Feb 3 '15 at 16:20
  • $\begingroup$ We cannot use the tag you suggested because our tags (Macs) are gonna verify the computations, where $a_i$ and $b_i$ cannot be changed for each index $\endgroup$ – user13676 Feb 3 '15 at 16:26

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.