Can we get the msg when we know tag and key in Poly1305

Question

Assume $tag[i]=\operatorname{MAC}(key[i],msg)$

Now we know:

• $tag[0],tag[1],\ldots,tag[n]$
• $key[0],key[1],\ldots,key[n]$

Can we get the $msg$ from this?

Or can we get the $tag$ of this $msg$ using a known key?

Answer 1

Can we get the $msg$ from this?

Yes, as long as we know the nonces, and as long as $msg$ is no more than $128n$ bits long, and $n$ isn't too incredibly huge (the latter might not be a required assumption, I just need it for my approach).

Poly1305 can be modeled as computing a tag this way:

$$tag = c_a r^a + c_{a-1} r^{a-1} + … + c_1 r^1 + z - 2^{128} k \bmod {2^{130}-5}$$

where (in your scenario) you know the value $r$ and $z$ (they're a function of the key and the nonce, which you know) and don't know the values $c_a, c_{a-1}, …, c_1$ (that's an encoding of the message) and the value $k$ (which is between 0 and 3); $k$ is here to account for the outer '$\bmod 2^{128}$ operation that Poly1305 performs.

If we have $n$ such tags, we can set this up as $n$ simultaneous linear equations in the unknown $c_a, c_{a-1}, …, c_1$ variables. We don't know the $k$ variables, hence we would need to go through the $4^{n}$ combinations of the $n$ different $k$ variables, and solve each one individually (and after obtaining a solution, we would check the message to see if Poly1305 processes the message as expected - it may encode the message to a different set of $c$ variables, or assign a different value for a $k$ variable.

If $n \ge a$, this gives us enough equations to find a solution; if $n > a$, this solution is likely to be unique.

This involves assuming $4^{n}$ sets of $n$ linear equations; as long as $n$ isn't too large, this is practical.