ChaCha Slide picoCTF 2025 Solution

Description

1. Step 1Recover the ChaCha20 keystream via nonce reuse

   Observation

   The server encrypts two messages under the same key and nonce. ChaCha20 is a stream cipher, so both get the identical keystream, and XOR-ing one ciphertext with its known plaintext hands it to you.

   Same key + same nonce = same keystream. XOR the two ciphertexts: the keystream cancels and you get pt1 XOR pt2. The server never sends a nonce, and both plaintexts are known to you already (the challenge fixes them), so you do not have to guess: XOR either ciphertext against its matching plaintext to recover the keystream directly. XOR-ing the two ciphertexts together is still a useful sanity check, because the result should equal pt1 XOR pt2. 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 the two ciphertexts gives you the XOR of the plaintexts, which says something about them but is not encrypted under the keystream, so the server rejects it. Isolate the keystream first by XOR-ing one ciphertext against its known plaintext.

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

   zip() stops at the shorter sequence, so padding the wrong side shifts which bytes pair up. The recovered keystream is then correct only as far as the shorter input reaches, and everything past that turns to garbage in your forged message.

   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

   Observation

   The same nonce reuse means Poly1305 used one (r, s) pair for both tags. Subtract the two tag equations and s cancels, leaving a polynomial in r over GF(2^130 - 5). SageMath finds its roots, and that is the authentication key.

   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 the quickest route, but a pure-Python implementation of the same root-finding works too if you would rather not install Sage 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 modulo the prime 2^130 - 5, so root-finding over ordinary integers turns up nothing: there are no integer roots matching the tags. Work in the field itself, where factoring and .roots() enumerate real candidates.

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

   The polynomial can have several roots, and Sage returns them in arbitrary order. Poly1305 clamps r, clearing the top four bits of bytes 3, 7, 11, and 15 and the bottom two bits of bytes 4, 8, and 12. An unclamped root yields the wrong s, and every tag built from that pair is rejected.

   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.

   Several public AEAD nonce-reuse toolkits implement this exact attack for ChaCha20-Poly1305: hand them two (ciphertext, tag, plaintext) tuples encrypted under the same nonce and they return the recovered (r, s) plus a tag-forging helper. Writing the root-finding yourself is about thirty lines in Sage, so either path is fast.

   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, AES-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

   Observation

   With both (r, s) and the keystream recovered, any ciphertext gets a valid tag: evaluate the polynomial and add s modulo 2^128. That pair satisfies the server's verifier.

   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 happens modulo 2^128, not modulo the field prime. Skip that and you get a 130-bit integer where a 128-bit tag belongs. The verifier compares 16 bytes, so the extra high bits fail the match even with r and s both correct.

   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 appends a 0x01 byte to each 16-byte chunk, making it 17 bytes before the reduction. Feed raw bytes without that and the polynomial coefficients differ from the server's, so the tag never verifies.

   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

This flag has been withdrawn rather than guessed, on the same basis as ricochet: filled in from a placeholder, and its body was an exact leetspeak of the challenge title, a pattern that was wrong in every checkable case in that batch. Recover yours by sending the crafted boundary string to your own instance.