ChaCha Slide picoCTF 2025 Solution

Description

1. Step 1Recover the ChaCha20 keystream via nonce reuse
   Same key + same nonce = same keystream. XOR the two ciphertexts: the keystream cancels and you get pt1 XOR pt2. To verify nonce reuse, check whether the server transmits a nonce; if not, attempt the XOR cancellation and check whether the result looks like sane data. To guess pt1, try common formats (Hello, {}, JSON braces) and XOR with the ciphertext - valid UTF-8 confirms. With one known plaintext, XOR back to recover the keystream. That keystream encrypts any plaintext of your choice, but Poly1305 still rejects unauthenticated ciphertexts. Step 2 forges the tag.
   python

   ct1, tag1 = ...  # from server
   ct2, tag2 = ...  # from server
   pt1 = ...        # known plaintext for message 1
   
   # Recover keystream:
   keystream = bytes(a ^ b for a, b in zip(ct1, pt1.encode()))
   
   # Encrypt your own message:
   my_plaintext = b'forge me a flag'
   my_ct = bytes(a ^ b for a, b in zip(keystream, my_plaintext))

   Copied!
   Learn more

   ChaCha20 is a stream cipher: it generates a pseudorandom keystream from the key and nonce, then XOR-s the keystream with the plaintext to produce the ciphertext. Decryption is identical - XOR the ciphertext with the same keystream. The critical property is that if the nonce is reused, the same keystream is generated for both messages. XOR-ing ct1 and ct2 yields pt1 XOR pt2, completely eliminating the keystream. With one known plaintext, the other can be recovered immediately.

   This is the two-time pad attack, the same weakness that makes one-time pads insecure when reused. Stream ciphers like ChaCha20, AES-CTR, and RC4 are all vulnerable to this attack on nonce reuse. The cryptographic requirement is absolute: a nonce must never be repeated under the same key. A single repetition compromises both messages and the authentication tags. The Stream Ciphers in CTFs guide covers the same nonce-reuse pattern in AES-CTR and RC4 with worked recoveries.

   The ChaCha20 keystream for the first 64-byte block is the same for both messages, so if your forged message is no longer than the leaked keystream, you can produce a valid ciphertext without knowing the key at all.

2. Step 2Recover the Poly1305 key r and s
   Poly1305's one-time key (r, s) is derived from the nonce. Reused nonce means (r, s) is the same for both tags. Subtract the two tag equations to eliminate s, leaving a polynomial in r over GF(2^130 - 5). Solve for r via polynomial root-finding (Sage's .roots()), filter candidates by the Poly1305 clamp, then back out s from either tag. Sage is faster locally but tl2cents' pure-Python lib avoids the Sage dependency for a one-time exploit.
   bash

   # Using SageMath:
   p = 2**130 - 5
   # Build the Poly1305 polynomial for each message and subtract the tags
   # The difference factors as a polynomial in r over GF(p)
   # Find roots to recover r, then s = tag1 - poly1305_eval(r, msg1) mod 2^128

   Copied!
   Learn more

   Poly1305 computes a MAC as a polynomial evaluation: the message is split into 16-byte blocks, each converted to a 130-bit integer, and evaluated as a polynomial in r over the prime field GF(2^130 - 5). The constant s is added to the polynomial value modulo 2^128. With two tag-message pairs encrypted under the same nonce (and therefore the same r and s), subtracting the two tag equations eliminates s, leaving a polynomial equation in r alone. Concretely, build P(r) = poly1305_eval(r, msg1) - poly1305_eval(r, msg2) - (tag1 - tag2) mod (2^130 - 5) in Sage with the message blocks as coefficients, call .roots() over GF(2^130 - 5), then filter the candidates by the Poly1305 clamp constraint to pick the real r.

   The Poly1305 specification requires that r has certain bits clamped to zero (the clamp). This reduces the number of valid r values and lets you filter candidate roots. Typically, solving the polynomial equation yields a small number of candidate r values; testing each against the clamp constraint and against one known tag quickly identifies the correct one.

   The AEAD-Nonce-Reuse-Attacks library by tl2cents (GitHub) implements this exact attack for ChaCha20-Poly1305. It provides a chacha_poly1305_forgery.py module that, given two (ciphertext, tag, plaintext) tuples encrypted with the same nonce, returns the recovered (r, s) and can forge new tags automatically. For competitive CTF use, this is the fastest path.

   Poly1305 forgery via root-finding:
   
   For a message M with 16-byte blocks m[1], m[2], ..., m[L]:
     poly_eval(r, M) = (m[1]*r^L + m[2]*r^(L-1) + ... + m[L]*r) mod (2^130 - 5)
     tag = (poly_eval(r, M) + s) mod 2^128
   
   Given two (M_i, tag_i) pairs sharing (r, s):
     tag_1 = poly_eval(r, M_1) + s   (mod 2^128)
     tag_2 = poly_eval(r, M_2) + s   (mod 2^128)
   
   Subtract to eliminate s:
     tag_1 - tag_2 = poly_eval(r, M_1) - poly_eval(r, M_2)   (mod 2^128)
   
   Define P(r) = poly_eval(r, M_1) - poly_eval(r, M_2) - (tag_1 - tag_2)
     P(r) is a polynomial in r of degree max(L_1, L_2).
     We know r is a root of P over GF(2^130 - 5).
   
   Solve P(r) = 0 over GF(2^130 - 5) using polynomial root-finding
   (Cantor-Zassenhaus or sage's .roots() method). Typically only a
   handful of candidate r values exist; filter using the Poly1305
   clamp constraint (specific bits of r must be zero).
   
   Once r is known, recover s:
     s = (tag_1 - poly_eval(r, M_1)) mod 2^128
   
   Forge a new tag for any chosen ciphertext M':
     forged_tag = (poly_eval(r, M') + s) mod 2^128
   
   Submit (M', forged_tag) and the server accepts.
   
   This is the catastrophic failure mode of nonce reuse in
   ChaCha20-Poly1305: integrity collapses simultaneously with
   confidentiality. SIV-mode AEAD (AES-GCM-SIV, ChaCha20-SIV)
   defends against this by deriving the nonce from the message itself,
   making accidental reuse impossible for distinct messages.

3. Step 3Forge a valid tag and submit
   Compute the Poly1305 tag for your chosen ciphertext using the recovered (r, s). Submit the (ciphertext, tag) pair. The server's verifier accepts, decrypts your payload (typically a control message that triggers the flag print), and prints picoCTF{...}.
   python

   # Compute forged tag:
   forged_tag = poly1305_eval(r, my_ct) + s  # mod 2^128
   
   # Submit to server:
   conn.send(my_ct + forged_tag)
   print(conn.recvall())

   Copied!
   Learn more

   Authenticated Encryption with Associated Data (AEAD) like ChaCha20-Poly1305 is supposed to provide both confidentiality (nobody can read the message without the key) and integrity (nobody can tamper with the ciphertext undetected). Nonce reuse breaks both guarantees simultaneously: confidentiality fails because the keystream is recoverable, and integrity fails because r and s are recoverable, allowing arbitrary tag forgery.

   Real-world AEAD systems generate nonces either as random values (with enough bits that collision probability is negligible - 96-bit nonces for ChaCha20-Poly1305 make collision probability about 1 in 2^96) or as monotonically incrementing counters that are never reset. Counter-based nonce management is generally more reliable because it eliminates the statistical possibility of collision entirely, at the cost of requiring state persistence between encryptions.

   The SIV (Synthetic IV) construction is a nonce-misuse-resistant variant of AEAD that remains secure even if nonces are reused, at the cost of being slightly more expensive. For applications where nonce management is difficult or unreliable, SIV-based schemes like AES-GCM-SIV are the recommended choice. The AES for CTF guide walks through the AEAD modes (GCM, GCM-SIV, CCM) and the equivalent forgery surface in AES-GCM nonce reuse.

Flag

Nonce reuse: XOR the two ciphertexts to cancel the keystream, recover Poly1305 (r, s) by polynomial root-finding over GF(2^130-5), then forge a valid tag for any plaintext.