ChaCha Slide picoCTF 2025 Solution

Description

1. Step 1

   Recover the ChaCha20 keystream via nonce reuse

   Observation

   I noticed the server encrypts two messages using the same key and nonce with ChaCha20, which is a stream cipher that produces an identical keystream for both, so XOR-ing either ciphertext with its known plaintext immediately recovers the keystream needed to encrypt any forged message.

   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!

   What didn't work first

   Tried: XOR the two ciphertexts directly and try to submit that as a forged ciphertext.

   XOR-ing ct1 and ct2 gives pt1 XOR pt2, not a usable ciphertext. This tells you something about the two plaintexts but it is not encrypted under the keystream and the server will reject it as garbled. You need a known plaintext to XOR against one ciphertext to isolate the actual keystream first.

   Tried: Assume the ciphertexts are different lengths and zip them fully, padding the shorter one with zeros.

   Python's zip() silently stops at the shorter sequence, so zero-padding the wrong side shifts which bytes are XOR-ed. The keystream you recover will be correct only up to the length of the shorter input - any bytes beyond that will be wrong, producing garbage when you try to encrypt your forged message for those positions.

   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 2

   Recover the Poly1305 key r and s

   Observation

   I noticed that nonce reuse also means Poly1305 uses the same (r, s) pair for both tags, so subtracting the two tag equations cancels s and leaves a polynomial in r over GF(2^130 - 5) whose roots can be found with SageMath, giving us the authentication key needed to forge any tag.

   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!

   What didn't work first

   Tried: Solve for r by working over regular integers (Python's int arithmetic) instead of GF(2^130 - 5).

   Poly1305 evaluates the polynomial modulo the prime 2^130 - 5, so root-finding over ordinary integers finds nothing useful. The polynomial over integers has no integer roots matching the tag values. You must work in the Sage GF(2^130 - 5) ring, where the field structure enables Cantor-Zassenhaus factoring and .roots() to enumerate actual candidates.

   Tried: Skip filtering by the Poly1305 clamp constraint and just use the first root returned by Sage's .roots().

   The polynomial over GF(2^130 - 5) may have multiple roots, and Sage returns them in an arbitrary order. The clamp constraint zeros out specific bits of r (the top 4 bits of bytes 3, 7, 11, 15 are cleared, and the bottom 2 bits of bytes 4, 8, 12 are cleared; byte 0 is unaffected). Using an unclamped root will compute an s that is wrong, and every forged tag produced with that (r, s) pair will be rejected by the server.

   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 3

   Forge a valid tag and submit

   Observation

   I noticed that once (r, s) and the keystream are both recovered, I can compute a valid Poly1305 tag for any chosen ciphertext by evaluating the polynomial and adding s modulo 2^128, so submitting this forged (ciphertext, tag) pair satisfies the server's AEAD verifier and triggers the flag.

   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!

   What didn't work first

   Tried: Compute the forged tag as poly1305_eval(r, my_ct) + s without reducing modulo 2^128.

   The final addition of s in Poly1305 is performed modulo 2^128, not modulo 2^130 - 5. Omitting the mod 2^128 step produces a 130-bit integer instead of a 128-bit tag. The server's verifier truncates or compares against a 16-byte value, so the high bits cause a mismatch and the forgery is rejected even though r and s are correctly recovered.

   Tried: Evaluate poly1305_eval(r, my_ct) using the message bytes directly instead of splitting into 16-byte blocks padded with a 1 bit.

   Poly1305 pads each 16-byte chunk by appending a 0x01 byte beyond the block, making each chunk a 17-byte (136-bit) value before reducing modulo 2^130 - 5. Feeding raw bytes without this padding produces different polynomial coefficients, so the computed polynomial value diverges from what the server computes, and the tag does not verify.

   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.