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

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?

• If you know all the intermediate states of the tag (as you've currently indicated in the question), then yes, it's possible as the Poly1305 arithmetics are reversible. Dec 29 '19 at 11:48

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.

• @kelalaka: could you expand on your comment? I have no idea what you're trying to say Jan 2 '20 at 20:43
• If I've understood correctly, the longer messages are safe from this attack, right? That is why I said speak more to be safe. Jan 2 '20 at 20:44
• @kelalaka: well, longer messages are computationally less vulnerable against this (hard to call this an 'attack', as Poly1305 was never designed to be strong against this), and if the length of the message is > n, then obviously the message cannot be uniquely determined (by any method). Jan 2 '20 at 20:51