ChaCha SlidepicoCTF 2025 Solution

Description

Solution

1. Step 1Recover the ChaCha20 keystream via nonce reuse
   Because both messages are encrypted with the same key and nonce, their keystreams are identical. XOR-ing the two ciphertexts cancels the keystream and produces the XOR of the two plaintexts. If you know one plaintext (e.g., the server echoes it back or it is a known greeting), XOR it with the ciphertext-XOR to recover the keystream. Then XOR the keystream with any plaintext of your choice to produce a valid ciphertext.

   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))

   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 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 uses a secret one-time key `(r, s)` derived from the same nonce. Because the nonce is reused, `(r, s)` is identical for both messages. The authentication tag satisfies `tag = Poly1305_r(msg_blocks) + s mod 2^128`. With two known (message, tag) pairs sharing the same `(r, s)`, you can construct a polynomial equation in `r` over GF(2^130 - 5) and solve for `r` using polynomial GCD, then derive `s` from either tag.

   # 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

   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.

   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
   With `r` and `s` recovered, compute a valid Poly1305 tag for your forged ciphertext using the recovered key. Submit the forged `(ciphertext, tag)` pair to the server. Since the tag passes verification, the server decrypts and processes the message, returning the flag.

   # 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())

   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.

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.