1
$\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 pulbic 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 a 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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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}$

Improve this answer
$\endgroup$
5
  • $\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
    Commented Feb 3, 2015 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
    Commented Feb 3, 2015 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
    Commented Feb 3, 2015 at 16:18
  • $\begingroup$ cs.berkeley.edu/~dawnsong/papers/p598-ateniese $\endgroup$
    – user13676
    Commented Feb 3, 2015 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
    Commented Feb 3, 2015 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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