# Forgery attack on Poly1305 when the key and nonce reused

Introduction: I've tried to find how reusing one-time key compromises itself but only found information that it breaks the encryption entirely, it is written everywhere. But since no methods to reuse or restore the key were specified I don't quite get how it can be done, even with plaintext and tag given.

Problem: we have several messages and its tags, encrypted with pure Poly1305 with the same key (generated using python's Poly1305 from chacha20poly1305, implementation code) without AES and ChaCha, as it seems from the code and according to the specification.

The inputs to Poly1305 are: A 256-bit one-time key; An arbitrary length message

I want to reuse Poly1305 key to sign custom message and therefore forge it. What should I do to reuse the same key without knowing it on my custom message or, if possible, find the key?

Example, you've got the following data, the same key is used 3 times (data in hex : tag in hex):

Data: e8962f8dada53f589eada744bf3f9bb298be47ebd3416a59a13a709d1bf6fb4d
Tag:  825f51bb7b0f05990f03998c63a51f08

Tag:  53cc694570e89ec66350b4d7877ea58a

Data: 46a683f0a164bf6e19ee0b05f4c65f1f7b1d6ec454fe0e79ec4debfb22da36c1
Tag:  cba1048b9ee15929a16f0cfe5f4547b1

• Welcome to Cryptography.SE. There are lots of questions and answer about this in our site. For example What happens if a nonce is reused in ChaCha20-Poly1305?. Search with Poly1305 key reuse. The confidentiality is lost != the key is revealed. You can only get the keystream (as stream cipher) and if the nonce is reused you can use it again with crib-dragging. If the nonce changes the confidentiality is protected. Aug 30 '20 at 11:44
• OTOH, I would like to see an answer that answers the point about the key directly. I've tried to find some answers that explain this but I haven't found one. Aug 30 '20 at 11:50
• Thank you for formatting and the link but the thing is that there is Poly1305 without ChaCha20. Also, again, thank you for reminding about "confidentality != revealed key", I've formulated the question incorrectly. I don't have to get key's plain text (but it would be interesting to), I want to try to reuse it on another custom message but don't get the way. Aug 30 '20 at 11:56
• Yes, message-forging is exactly what I should have asked. It is nice when there is a caution that you should not reuse the key but isn't nice when there is no explanation for this as there are for encryption algorithms. So I want to check possibility&result of such actions before using and just for knowledge of the danger. Aug 30 '20 at 12:08
• So I try to understand how it works: generate messages with the same key on my PC but don't get what should I do next to compromise myself. Aug 30 '20 at 12:19

In Poly1305

• 16-byte AES key k
• 16-byte $$n$$ nonce

is required. The obligations of the users

• Any protocol that uses Poly1305-AES must ensure unpredictability of the secret key $$(k, r)$$.
• The sender must never use the same nonce for two different messages

The obvious attack is the crib-dragging that destroys confidentiality and this doesn't mean that the encryption key is revealed. And this is not the case.

The nonce for Poly1305 is calcualted as $$nonce = \operatorname{AES}_k(n)$$

$$\operatorname{Poly1305}( r, m, \operatorname{AES}_k(n))$$

The $$r$$ actually $$\in \{ 2^{106} \}$$ not a full 128-bit.

The Poly1305 authentication can be simplified as

$$(((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) + \operatorname{AES}_k(n)) \bmod 2^{128}$$ where $$c_i$$'s are encoded message $$m$$, $$r_i$$ is the $$r$$ in bytes.

OPs case

if we omit the $$\operatorname{AES}_k(n)$$ for pure Poly1305 then the equation becomes

$$(((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) \bmod 2^{128}$$

Now, for simplicity only consider a small message that has 16-bytes and the same key and nonce is used. Then the for loop inside the while loop will work only once.

void poly1305_gmpxx(unsigned char *out,
const unsigned char *r,
const unsigned char *s,
const unsigned char *m,unsigned int l)
{
unsigned int j;
mpz_class rbar = 0;

for (j = 0;j < 16;++j)
rbar += ((mpz_class) r[j]) << (8 * j);

mpz_class h = 0;
mpz_class p = (((mpz_class) 1) << 130) - 5

while (l > 0) {
mpz_class c = 0;
for (j = 0;(j < 16) && (j < l);++j)
c += ((mpz_class) m[j]) << (8 * j);
c += ((mpz_class) 1) << (8 * j);
m += j; l -= j;
h = ((h + c) * rbar) % p;
}
//Omitted since Pure Poly!
//for (j = 0;j < 16;++j)
//    h += ((mpz_class) s[j]) << (8 * j);

for (j = 0;j < 16;++j) {
mpz_class c = h % 256;
h >>= 8;
out[j] = c.get_ui();
}
}


then we have

mpz_class h = 0;
mpz_class c = 0;
for (j = 0; j < 16 ;++j)
c += ((mpz_class) m[j]) << (8 * j);

h = (c * rbar) % p;

for (j = 0;j < 16;++j) {
mpz_class c = h % 256;
h >>= 8;
out[j] = c.get_ui();
}


The last loop actually outputs the 16 bytes of the $$h$$, since $$p = 2^{130}-5$$ is slightly less than the modulus.

Hint: play with the message, especially the upper part.

Note: rfc8439 replaced RFC 7539

RFC 7539, the predecessor of this document, was meant to serve as a stable reference and an implementation guide. It was a product of the Crypto Forum Research Group (CFRG). This document merges the errata filed against RFC 7539 and adds a little text to the Security Considerations section.

• This is too long to be a hint :( Aug 30 '20 at 18:20

I want to reuse Poly1305 key to sign custom message and therefore forge it. What should I do to reuse the same key without knowing it on my custom message or, if possible, find the key?

Instead of giving you a hint, I'll tell you straight out. I'll also tell you why Poly1305 without AES/ChaCha20 is insecure, even if the key is used once.

Correct Poly1305 is defined as (text stolen from kelaka's answer):

$$tag = (((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) + c_0) \bmod 2^{128}$$ where $$c_i$$'s are encoded message $$m$$, $$r_i$$ is the $$r$$ in bytes (and $$c_0$$ being a function of the nonce and the key, possibly using AES or ChaCha20).

We have no information on the value of $$c_0$$, and so the tag doesn't give us any information on what the inner polynomial may evaluate to. Hoewver, if we have two messages MAC'ed with the same tag and key, they'll share $$c_0$$ values. What we can do in that case is subtract (modulo $$2^{128}$$ the two tag values, and that'll give us:

$$tag - tag' =$$ $$((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130}-5) \bmod 2^{128}$$ $$-((c'_1 r^q + c'_2 r^{ q−1} + \cdots + c'_q r^1 ) \bmod 2^{130}-5) \bmod 2^{128}$$

We can rewrite this as:

$$tag - tag' + 2^{128}k =$$ $$(((c_1-c'_1) r^q + (c_2-c'_2) r^{ q−1} + \cdots + (c_q-c'_q) r^1 ) \bmod 2^{130}-5)$$

for $$k \in \{-4,..., 4\}$$.

This gives us 9 polynomials (for the varous possible values of $$k$$), for which we know the coefficients, and we know that the correct value of $$q$$ is a zero for one of them.

The question is then: can we efficiently find zeros of polynomials over a finite field. The answer is yes; see this Wikipedia article for a survey of the known methods (the Cantor–Zassenhaus algorithm looks to be the most practical in this scenario).

From my answer, it should be easy to see why omitting the AES/ChaCha20 step is insecure, in that the attacker can recover $$q$$ with a single message.

This modified Poly1305 algorithm is:

$$tag = (((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5)) \bmod 2^{128}$$

As you can see, we've dropped the $$c_0$$ value, so there's no need for a second message to eliminate it. The attack can proceed with this polynomial directly.