Forgery attack on Poly1305 when the key and nonce reused

Question

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

Data: 6e05652fe6a6985c1fed6604f95b133fe7a4a9f95313a8ad15d995195528efad
Tag:  53cc694570e89ec66350b4d7877ea58a

Data: 46a683f0a164bf6e19ee0b05f4c65f1f7b1d6ec454fe0e79ec4debfb22da36c1
Tag:  cba1048b9ee15929a16f0cfe5f4547b1

Answer 1

In Poly1305

• 16-byte AES key k
• 16-byte additional key r
• 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.

Answer 2

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.